[머신 러닝/강화 학습] Markov Decision Process (MDP)

강화 학습은 주로 Markov decision process (MDP)라는 확률 모델로 표현된다. MDP는 의사결정 과정을 확률과 그래프를 이용하여 모델링한 것으로써, "시간 $t$에서의 상태는 $t-1$에서의 상태에만 영향을 받는다"는 first-order Markov assumption을 기반으로 고안되었다. First-order Markov assumption을 확률로 나타내면 식 (1)과 같다.

$$p(s_t|s_0, s_1, ..., s_{t-1}) = p(s_t|s_{t-1}) \tag{1}$$

이 글에서는 MDP에 대해 설명하기 전에 MDP의 기본 모델이 되는 Markov reward process에 대해 먼저 서술한다.

1. Markov reward process

Markov reward process는 Markov process의 각 state에 reward를 추가하여 확장한 것이다. Markov reward process는 아래와 같이 정의된 <$S, P, R, \gamma$>라는 4-tuple로 표현된다.

• $S$: state의 집합을 의미한다. State는 바둑에서 바둑판에 돌이 어떻게 놓여져 있는가를, 미로를 탈출하는 문제에서는 현재의 위치를 나타낸다.

• $P$: 각 요소가 $p(s^{'}|s) = \text{Pr}(S_{t+1}=s^{'}|S_t=s)$인 집합이다. $p(s^{'}|s)$는 현재 상태 $s$에서 $s^{'}$으로 이동할 확률을 의미하며, transition probability라고 한다.
  

• $R$: 각 요소가 $r(s) = \mathop{\mathbb{E}}[R_{t+1}|S_t=s]$인 집합이다. $r(s)$는 state $s$에서 얻는 reward를 의미한다.

• $\gamma$: 즉각적으로 얻는 reward와 미래의 얻을 수 있는 reward 간의 중요도를 조절하는 변수이다. 주로 [0, 1] 사이의 값을 가지며, discount factor라고 한다.

예를 들어, 아래의 [그림 1]과 같이 유적을 탐험하는 모험가의 상황은 Markov decision process로 표현될 수 있다. 이때 [그림 1]에서 각 원은 state, 화살표에 부여된 값은 transition probability, $R$은 state에 부여된 reward를 의미한다.

[그림 1] Markov reward process의 예시

유적은 Room 1~3과 보물이 있는 Treasure, 함정에 해당하는 Trap, 그리고 유적 외부를 뜻하는 Outside으로 구성되어 있다. 각각의 공간에서는 확률적으로 다음 공간으로 이동할 수 있으며, 각 공간에 도착할 때마다 특정 reward를 획득하게 된다. Outside 또는 Trap에 도착하게 되면 탐험은 종료된다.

Return

Return $G_t$는 시간 $t$ 이후부터 얻을 수 있는 reward의 합을 의미하며, discount factor $\gamma$를 통해 식 (2)와 같이 정의된다.

$$G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty}\gamma^{k} R_{t+k+1} \tag{2}$$

예를 들어, [그림 1]의 예시에서 $\gamma=0.5, S_1=$ Room 1이고, Room 2, Outside의 순서로 탐험하였을 때의 $G_1$은 다음과 같이 계산된다.

$$G_1 = -1 + (0.5)\times(-2) + (0.5)^2 \times 1 = -1.75$$

State-value function

State-value function $v(s)$는 state $s$에서 시작했을 때 얻을 수 있는 return의 기댓값을 의미하며, 식 (3)과 같이 정의된다.

$$v(s) = \mathbb{E}[G_t|S_t = s] \tag{3}$$

직관적으로, $v(s)$는 궁극적인 목표를 달성하는데 있어서 state $s$가 얼마나 좋은 상태인지를 나타낸다고 볼 수 있다. $v(s)$는 식 (4, 5)와 같이 재귀적인 형태로 표현될 수 있으며, 이를 Bellman equation이라 한다.

$$v(s) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s] = E[R_{t+1} + \gamma v(S_{t+1}) | S_t = s] \tag{4}$$

$$\therefore v(s) = R_{t+1} + \gamma \sum_{s^{'} \in S}p(s^{'} | s)v(s^{'}) \tag{5}$$

모든 state에 대한 $v(s)$는 아래와 같이 행렬로 표현될 수 있다.

$v(s)$는 아래와 같은 과정을 통해 계산된다.

예를 들어, [그림 1]에 표현된 Markov reward process의 각 state에 대한 state-value function은 [식 7]을 통해 아래의 [그림 2]와 같이 계산된다.

[그림 2] State-value function의 계산

그러나 [식 7]과 같이 state-value function을 계산하는 방법은 $O(n^3)$ 시간복잡도를 필요로 하기 때문에 state의 수가 많은 경우에는 적용이 불가능하다. 이를 해결하기 위해 동적 프로그래밍 (dynamic programming, 몬테카를로 방법 (Monte Carlo method), 시간차 학습 (temporal-difference learning) 등이 제안되었다.

2. Markov decision process (MDP)

MDP는 Markov reward process에 action이라는 요소가 추가된 모델로써, <$S, A, P, R, \gamma$>라는 tuple로 정의된다. 아래의 [그림 3]은 MDP의 동작을 구조화한 것이다. 우리가 학습시키고자 하는 인공지능, 로봇, 시스템 등에 해당하는 agent는 $S_t$에 해당하는 state에서 $A_t$에 해당하는 action을 수행한다. 그러면 게임 법칙, 물리 엔진 등에 해당하는 environment는 다음 state에 해당하는 $S_{t+1}$과 그에 상응하는 reward $R_{t+1}$을 agent에게 반환한다.

[그림 3] MDP의 동작

우리의 목적은 MDP로 정의된 문제에 대해 각 state마다 전체적인 reward를 최대화하는 action이 무엇인지를 결정하는 것이다. 이때 각각의 state마다 action의 분포 (action이 선택될 확률)를 표현하는 함수를 policy $\pi$라고 하며, $\pi$는 [식 8]과 같이 주어진 state $s$에 대한 action의 분포로 표현된다.

MDP가 주어진 $\pi$를 따를 때, $s$에서 $s^{'}$으로 이동할 확률은 [식 9]와 같이 계산된다.

또한, $s$에서 얻을 수 있는 reward는 [식 10]과 같이 계산된다.

State-value function with policy

MDP에서 state-value function $v(s)$는 Markov reward process의 state-value function과 마찬가지로 state $s$에서 시작했을 때 얻을 수 있는 return의 기댓값을 의미한다. 그러나 MDP는 주어진 policy $\pi$를 따라 action을 결정하고, state를 이동하기 때문에 MDP에서의 state-value function은 다음의 [식 11]과 같이 정의된다.

Action-value function

Action-value function $q_{\pi}(s,a)$는 state $s$에서 시작하여 $a$라는 action을 취했을 때 얻을 수 있는 return의 기댓값을 의미한다. Action-value function $q_{\pi}(s,a)$는 [식 12]와 같이 정의된다.

State-value function은 어떠한 state가 더 많은 reward를 얻을 수 있는지를 알려준다면, action-value function은 어떠한 state에서 어떠한 action을 취해야 더 많은 reward를 얻을 수 있는지 알려준다. 만약 우리가 모든 state에 대해 action-value function을 계산할 수 있다면, 우리는 모든 state에 대해 optimal action을 선택할 수 있게 되는 것이다.

Optimal state-value function and optimal action-value function

Optimal state-value function $v_{*}(s)$는 주어진 모든 policy에 대한 state-value function의 최대값이며, 아래의 [식 13]과 같이 정의된다.

비슷하게 optimal action-value function $q_{*}(s,a)$는 주어진 모든 policy에 대한 state-value function의 최댓값이며, 아래의 [식 14]와 같이 정의된다.

Optimal policy