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

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

$$\begin{array}{}\text{(1)}& p(s_t|s_0,s_1,...,s_{t-1})=p(s_t|s_{t-1})\end{array}$$

이 글에서는 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^{{}^{\prime }}|s)=\text{Pr}(S_{t+1}=s^{{}^{\prime }}|S_t=s)$인 집합이다. $p(s^{{}^{\prime }}|s)$는 현재 상태 $s$에서 $s^{{}^{\prime }}$으로 이동할 확률을 의미하며, transition probability라고 한다.
  

• $R$: 각 요소가 $r(s)=\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)와 같이 정의된다.

$$\begin{array}{}\text{(2)}& G_t=R_{t+1}+\gamma R_{t+2}+...=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}\end{array}$$

예를 들어, [그림 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)과 같이 정의된다.

$$\begin{array}{}\text{(3)}& v(s)=\mathbb{E}[G_t|S_t=s]\end{array}$$

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

$$\begin{array}{}\text{(4)}& 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]\end{array}$$

$$\begin{array}{}\text{(5)}& \therefore v(s)=R_{t+1}+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s)v(s^{{}^{\prime }})\end{array}$$

모든 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^{{}^{\prime }}$으로 이동할 확률은 [식 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_{\ast }(s)$는 주어진 모든 policy에 대한 state-value function의 최대값이며, 아래의 [식 13]과 같이 정의된다.

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

Optimal policy