마르코프 결정 과정

1 개요[ | ]

Markov decision process (MDP)
마르코프 결정 과정

상태 전이가 확률적으로 발생하는 동적 시스템(확률 시스템)의 확률 모델
상태 전이가 마르코프를 충족시키는 것을 말한다.
불확실성을 수반하는 의사결정 모델링의 수학적 프레임워크
의사결정과정을 모델링하는 수학적인 틀을 제공한다.
강화학습 등 동적계획법이 적용되는 다양한 최적화 문제의 연구에 활용되고 있다.
마르코프 연쇄의 확장된 형태로 볼 수 있다.

2 정의[ | ]

세 개의 상태(연두색 원)와 두 개의 행동(붉은색 원) 및 두 개의 보상(붉은색 화살표)가 있는 간단한 마르코프 결정 과정의 예시.

마르코프 결정 과정은 [math]\displaystyle{ (S, A, P.(\cdot,\cdot),\gamma) }[/math]의 5중쌍으로 표현되며, 각 원소의 의미는 다음과 같다.

[math]\displaystyle{ S }[/math]는 상태의 유한집합이다.
[math]\displaystyle{ A }[/math]는 의사결정자가 취할 수 있는 행동의 유한집합이다. (상태 [math]\displaystyle{ s }[/math]에서 취할 수 있는 행동의 유한 집합 [math]\displaystyle{ A_s }[/math]로 표현할 수도 있다.)
[math]\displaystyle{ P_a(s,s') = \mathrm{Pr}(s_{t+1}=s'\ |\ s_t=s,a_t=a) }[/math]는 어떠한 시점 [math]\displaystyle{ t }[/math]에 상태 [math]\displaystyle{ s }[/math]에서 행동 [math]\displaystyle{ a }[/math]를 취할 경우 다음 시점 [math]\displaystyle{ t+1 }[/math]에 상태 [math]\displaystyle{ s' }[/math]으로 전이할 확률이다.
[math]\displaystyle{ R_a(s,s') }[/math]는 상태 [math]\displaystyle{ s }[/math]에서 행동 [math]\displaystyle{ a }[/math]로 인해 상태 [math]\displaystyle{ s' }[/math]로 전이할 경우 받게 되는 즉각적인 보상(혹은 즉각적인 보상의 기댓값)이다.
[math]\displaystyle{ \gamma \in [0,1] }[/math]는 할인인자(discount factor)로서, 현재 얻게 되는 보상이 미래에 얻게 될 보상보다 얼마나 더 중요한지를 나타내는 값이다.

(주: 마르코프 결정 과정 이론 자체는 [math]\displaystyle{ S }[/math]와 [math]\displaystyle{ A }[/math]가 유한하다는 제한을 두지 않으나, 마르코프 결정 과정을 다루는 기본적인 알고리즘은 이들이 유한집합이라는 가정을 가지고 있다.)

3 같이 보기[ | ]

4 참고[ | ]