마르코프 결정 과정

마르코프 결정 과정(Markov Decision Process, MDP)는 의사결정 과정의 모델로, 상태(state)와 행동(action), 그리고 현재 상태와 행동에 따라 어느 상태로 변할지에 대한 확률, 행동에 따른 보상(reward; 보상이 확률적으로 주어지는 경우 그 기댓값)으로 정의된다. 러시아의 수학자 안드레이 마르코프(Andrey Markov)에게서 이름을 따왔는데, 그가 연구한 마르코프 과정에 어떤 행동을 할지 선택할 수 있도록 확장한 것으로 볼 수 있다. 강화학습 방법이 다루는 환경은 일반적으로 이 마르코프 결정 과정으로 주어지는데, 특히 전이 확률이나 보상에 대한 지식이 없거나 문제가 너무 큰 경우를 대상으로 한다.

정의

마르코프 결정 과정은 튜플 [math]\displaystyle{ (\mathcal{S}, \mathcal{A}, P, R, \gamma) }[/math]로 정의된다.

• [math]\displaystyle{ \mathcal{S} }[/math]는 가능한 모든 상태의 집합이다.
• [math]\displaystyle{ \mathcal{A} }[/math]는 가능한 모든 행동의 집합이다.
• [math]\displaystyle{ P }[/math]는 상태 전이 확률을 나타내는 함수이다. [math]\displaystyle{ P_a(s,s') = \mathbb{P} [S_{t+1}=s'|S_t=s,A_t=a] }[/math].
• [math]\displaystyle{ R }[/math]는 행동에 따른 보상의 기댓값을 나타내는 함수이다. [math]\displaystyle{ R(s, a) = \mathbb{E} [r_{t+1}|S_t=s,A_t=a] }[/math]. 보상은 일반적으로 하나의 실수로 주어진다.
• [math]\displaystyle{ \gamma }[/math]는 할인 인자(discount factor)이다. 현재 얻게 되는 보상이 미래에 얻게 될 보상보다 얼마나 더 중요한지를 나타내는 값으로, 0 이상 1 이하의 실수로 나타난다. 많은 알고리즘이 할인 인자가 없을 경우 수렴하지 않는다. 각 시간마다 주어지는 보상에 [math]\displaystyle{ \gamma^t }[/math]를 곱해서 받은 것으로 취급하여 문제를 풀게 된다. 즉, 똑같이 보상이 1이 주어졌더라도 [math]\displaystyle{ \gamma = 0.5 }[/math]인 경우, [math]\displaystyle{ t=1 }[/math]일 때 받은 보상이 [math]\displaystyle{ t=2 }[/math]일 때 받은 보상의 2배의 가치를 가지는 것으로 본다.

정책

마르코프 결정 과정에서 가장 중요한 문제는 주어진 MDP에 대한 최선의 정책(Policy)을 찾아내는 것이다. 정책 [math]\displaystyle{ \pi(s) }[/math]는 상태를 주면 그 상태에서 취할 행동을 결정하는 함수이다. 하나의 행동을 결정하는 대신, 상태가 주어졌을 때 어떤 행동을 취할 확률 [math]\displaystyle{ \pi(a|s) = \mathbb{P} [A_t = a|S_t = s] }[/math]를 쓰기도 하는데, 이 경우 확률적 정책(stochastic policy)이라고 한다.