Finite Markov Decision Process - (1) (feat. kurly)

강화학습은 MDP를 푸는 알고리즘 중 하나로, MDP는 Sequential Decision Process로도 불린다. 의사결정이 한 시점에서만 이뤄지는 게 아니기 때문이다.($t= 0, 1, 2, 3,\cdots$)

$A_{t} \in A: Action \;\ chosen \;\ at \;\ t, \;\ depends \;\ on \;\ S_{t} \\ S_{t} \in S: State \;\ at \;\ t$

강화학습에서는 action을 수행하는 존재를 agent라 한다.

그가 놓인 state는 시점마다 바뀔 수 있고 특정 action의 가치도 state에 따라 달라진다. 그리고 $t$ 시점에서 얻는 보상 $R_{t}$는 이전 시점의 $S_{t-1}$과 $A_{t-1}$에 따라 짭짤할 수도 별로일 수도 있다.

$R_{t} \in R: \;\ Reward \;\ at \;\ t \;\ \Longleftarrow \;\ A_{t-1}, \;\ S_{t-1}$

Inventory problem을 통해 맥락을 이해해볼 수 있다. 현재 어떤 상품 재고가 10개인 상태라고 해보자. 그렇다면 이 상태에서 재고를 더 확보 할까 혹은 하지 말까, 한다면 얼마나 더 할까?

상품이 신선 식품이고 일 평균 8개가 팔린다면 현 상태에서 재고를 더 확보해 15개, 20개로 만드는 action은 쓸 데 없는 행동일 수 있다(공산품이라면 좀 다르겠지만).

반면에 재고가 2개라면 재고를 더 확보하는 게 보다 좋은 action이 될 것이다. 즉 특정 시점의 state에 따라 특정 action이 주는 reward가 달라지고, 다음 시점의 state 역시 결정된다. 현재 나의 선택은 미래의 reward만이 아니라 미래에 내가 어떤 state에서 출발하게 될지 역시 결정한다. 인생의 진리의 일면을 담고 있다.

그건 그렇다 치고, MDP 앞에 붙은 'finite'라는 수식어는 뭘까. 내가 처할 수 있는 state들의 집합, 취할 수 있는 action들의 집합, 내가 가질 수 있는 reward들의 집합인 A, S, R의 크기가 모두 무한대보다 작은 유한집합일 때 우리는 이런 MDP 문제를 finite하다고 한다.

$|A|, |S|, |R| < \infin$

그럼 finite도 알겠고 decision process도 알겠는데 Markov라는 말은 왜 붙었을까. 그것은 MDP가 러시아 수학자 안드례이 안드례이비치 마르꼬브(Андре́й Андре́евич Ма́рков)의 아이디어에 기원을 두고 있다는 뜻이다.

역사적 관점이 아닌 이론적 관점에서 Markov가 붙은 이유는 이 의사결정 프로세스가 Markov property라는 특성을 상속하기 때문이다. 강화학습 교과서의 저자는 Markov property를 이렇게 설명한다.(Sutton and Bato, 2018)

The state must include information about all aspects of the past agent–environment interaction that make a difference for the future. If it does, then the state is said to have the Markov property.

말인즉 $S_{t}$가 Markov property가 있다고 인정할 수 있으려면 과거의 정보들을 완벽히 가지고 있어야 한다는 뜻이다.

미래에 어떤 작은 변화라도 가져올 과거의 정보들을 뜻한다. agent가 $t-2, \;\ t-3, \;\ t-4 \cdots$ 등에 어떤 state들에 직면했고 어떤 action들을 취했건 구구절절 알 필요 없고,

현재 시점 $t$의 state를 알면 내가 어떤 action을 취했을 때 미래에 어떠 일이 벌어질지 결정될 수 있다는 뜻이다. 더 요약하면 현재 state로만 나의 미래가 결정된다는 것. 현재는 과거의 반영이고 현재 state는 이미 과거가 반영돼 있기 때문이다.

단, 현재인 $S_{t}$와 $R_{t}$는 직전 시점의 $S_{t-1}$, $A_{t-1}$에는 의존한다. 이 정도 범위의 인지는 필요한 이유는 $S_{t}$와 $R_{t}$의 존재 근거가 필요하기 때문이다. 그 이상 거슬러 올라갈 필요는 없지만 말이다. 이러한 Markov property를 다른 말로는 망각 성질 또는 memories property라고도 한다.

$S_{t}, \;\ R_{t} \;\ depend \;\ on \;\ S_{t-1}, \;\ A_{t-1}$

참고: SUTTON, Richard S.; BARTO, Andrew G. Reinforcement learning: An introduction. MIT press, 2018.
사사: 숭실대학교 산업정보시스템공학과 강창묵 교수님.