Deep Reinforcement Learning 2 - Markov Decision Process

Before starting

“Class” 카테고리에 있는 포스팅들은 실제로 수업에서 배운 내용을 정리하려는 목적으로 작성되었다. 이 글은 그 중 Deep Reinforcement Learning 과목의 수업을 다룬다.

Markov Process

이제 저번 글에서 간단하게 본 Reinforcement Learning을 수학적으로 표현하는 방법을 알아보자. 이를 위해 먼저 Markov Process(MP)를 알아야 한다.

MP는 앞으로 발생할 수 있는 Event들의 Sequence를 기술하는 Stochastic Model이다. 이러한 Sequence로 이루어진 확률적인 Event들은 게임뿐만 아니라 일상 생활에서도 자주 발생한다. 이러한 현상을 기술하는 데 사용하는 것이라고 보면 된다.

이러한 MP에는 Markov Property라는 가정이 존재한다. Markov Property는 다음에 일어날 Event는 현재 발생한 Event에만 종속된다는 것이다. 즉 과거에 일어났던 Event들은 이미 다 현재 Event에 반영되어 있기 때문에 과거의 Event를 굳이 다시 고려할 필요가 없다.

\[P(S_{t+1}=s^{\prime}\vert S_0,S_1,\ldots,S_t)=P(S_{t+1}=s^{\prime}\vert S_t)=P_{ss^{\prime}}\]

이를 수식으로 표현하면 위와 같다. 즉, $S_{t+1}$이 $s^{\prime}$일 확률을 고려할 때는 직전 상태인 $S_t$만 고려해도 된다. 이러한 가정 하에서는 과거의 모든 State들을 기억할 필요가 없기 때문에 이를 Memoryless Property라고도 부른다.

MP는 State의 집합 $S$와 State Transition Probability Matrix $P_{tran}$으로 구성된다. 각각의 State는 한 상태를 표현하며, 여기서 다른 State로 넘어갈 확률은 각 State마다 다르다. 이를 기록한 것이 $P_{tran}$이다. 그래서 하나의 MP는 $\langle S, P_{tran}\rangle$으로 표현 가능하다.

위 사진은 MP의 한 예시를 나타낸 것이다. 각각의 State가 다음 State로 넘어가는 확률이 적혀있음을 알 수 있다.

그리고 이 정보를 바탕으로 위와 같이 $P_{tran}$을 만들 수 있다.

Markov Reward Process

하지만 Reinforcement Learning을 표현하기 위해선 $S$와 $P_{tran}$만으로는 부족하다. 우선 MP에는 Reinforcement Learning의 핵심 요소인 Reward를 표현할 방법이 딱히 없다. 따라서 MP를 확장해서 각각의 State에 Reward를 추가한 Markov Reward Process(MRP)가 도입되었다.

MRP는 MP에 더해 Reward $r_t$와 Discounting Factor $\gamma\in\left[0,1\right]$이 추가된 형태이다. MRP에서 State간의 전환은 확률에 따라 일어나는데, 그 이동은 순차적, 연속적이기 때문에 시간 개념이 들어가게 된다. 따라서 $t$ 시간을 떠나며 받을 수 있는 Reward를 $r_{t+1}$로 표현한다. 그리고 이들 Reward의 합을 표현한 Return이라는 개념이 있다.

\[G_t=r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+\cdots=\sum_{k=0}^{\infty}\gamma^k r_{t+k+1}\]

즉, Return $G_t$는 $t$ 시간을 기준으로, 향후 받을 수 있는 모든 Reward의 합을 의미하는데, 역시 미래의 Reward를 다루기 때문에 점점 더 불확실해지고, 따라서 그만큼 $t$ 시간에서 다룰 가치는 떨어지므로 Discounting Factor를 각 항마다 누적해서 곱해준다.

또한 이를 통해 State Value Function $V(s)$를 정의할 수 있다. 특정 State가 좋은지 판단하기 위해선 그 State에서의 Return의 평균값을 계산하면 된다. 즉, $V(s)=\mathbb{E}\left[G_t\vert S_t=s\right]$로 계산할 수 있다.

이렇게 MP를 확장해서 MRP를 만들 수 있고, 이 MRP는 $\langle S, P_{tran}, R, \gamma\rangle$로 표현할 수 있다. 여기서 $R$은 위에서 언급한 Reward 값 $r_t$를 계산하는 Reward function이다.

위 사진은 MP의 예시를 확장해 Reward를 추가한 MRP의 예시이다. 각 State마다 Reward가 추가로 적혀있는 것을 확인할 수 있다. Discounting factor $\gamma$는 각 State별로 다르게 지정되는 값이 아니라 MRP 전체가 공유하는 값이므로 위 예시에는 따로 적혀있지 않았다.

Markov Decision Process

MP에서 Reward 개념을 추가해 MRP를 만들었지만, 아직 Reinforcement Learning을 표현하기에는 부족하다. MP나 MRP는 각 State 간의 전환이 단순히 미리 정해진 확률대로 이루어지지만, Reinforcement Learning에서는 이 전환이 Agent의 행동, 즉 Action에 대한 조건부 확률에 따라 이루어진다. 따라서 MRP를 확장해서 Action을 추가하고 State 전환을 Action에 의존하게 해야 한다. 이것을 구현한 모델을 Markov Decision Process(MDP)라고 한다.

위 사진처럼, State $S$와 $S^{\prime}$의 중간에 Action $A_t$가 수행된다. 그래서 현재 State에서 어떠한 Action을 수행하느냐에 따라 다음 State로 전이하게 된다.

현재 State에서 어떤 Action을 고를지는 Policy로 정의한다. Policy $\pi(a\vert s)=P(A_t=a\vert S_t=s)$는 현재 State $s$에서 Action $a$를 수행할 확률을 의미한다.

또한 MRP에서는 State Value Function $V(s)$를 정의했었는데, MDP에서는 이와 비슷하게 Action Value Function $Q_\pi(s,a)$가 정의된다. 이는 State $s$에서 Action $a$를 수행했을 때 받을 수 있는 Return의 기댓값을 의미한다. 즉, 아래와 같이 표현할 수 있다.

\[Q_\pi(s,a)=\mathbb{E}_\pi\left[G_t\vert S_t=s,A_t=a\right]\]

이렇게 MRP를 다시 확장해 MDP를 만들 수 있고, 이 MDP는 $\langle S, A, P_{tran}, R, \gamma\rangle$로 표현할 수 있다. 여기서의 $A$는 가능한 모든 Action의 집합을 의미한다.

이번엔 역으로 생각해보자. MDP는 MP 및 MRP를 확장한 것이기 때문에, MDP $\langle S, A, P_{tran}, R, \gamma\rangle$이 주어지고 Policy $\pi$가 고정된다면 여기서 MP와 MRP를 유도할 수 있다.

MDP에서 State만을 나열한 Sequence $S_1,S_2,\cdots$는 MP $\langle S, P^\pi\rangle$을 구성하게 된다. 이 때 $P^\pi$는 다음과 같이 정의된다.

\[P_{ss^{\prime}}^\pi=\sum_{a\in A}\pi(a\vert s)P_{ss^{\prime}}^a\]

이 상황에서 State 간의 전환이 이루어질 확률은 정해진 Policy에 기술된 Action을 선택할 확률과 그 Action으로 인해 State가 변경될 확률만 남게 되고, 따라서 MP에서의 State Transition Probability Matrix를 기술할 수 있게 된다.

MDP에서 State와 Reward만을 나열한 Sequence $S_1,R_1,S_2,R_2,\cdots$는 MRP $\langle S, P^\pi, R_s^\pi, \gamma\rangle$을 구성하게 된다. 이 때 $R_s^\pi$는 다음과 같이 정의된다.

\[R_s^\pi=\sum_{a\in A}\pi(a\vert s)R_s^a\]

이 상황에서 Reward는 정해진 Policy에 기술된 Action을 선택할 확률에 의한 Reward의 기댓값으로 얻을 수 있다.

Bellman Expectation Equation

이제 MRP로 돌아가서, State Value Function $V(s)$를 확인해보자. 이 함수는 현재 State가 얼마나 높은 Return을 줄 수 있는지를 기술하는 함수이다. 즉, $V(s)=\mathbb{E}\left[G_t\vert S_t=s\right]$이다.

그런데 $s$에서 $s^{\prime}$으로 State 전환이 이루어졌다면, $V(s)$는 다음과 같이 $V(s^{\prime})$에 대한 식으로 표현할 수 있다.

\[\begin{aligned} V(s)&=\mathbb{E}\left[G_t\vert S_t=s\right] \\ &=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\cdots\vert S_t=s\right] \\ &=\mathbb{E}\left[r_{t+1}+\gamma(r_{t+2}+\gamma r_{t+3}+\cdots)\vert S_t=s\right] \\ &=\mathbb{E}\left[r_{t+1}+\gamma G_{t+1}\vert S_t=s\right] \\ &=\mathbb{E}\left[r_{t+1}+\gamma V(S_{t+1})\vert S_t=s\right] \\ &=R_s+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}V(s^{\prime}) \end{aligned}\]

즉, 현재 State에 대한 State Value Function은 당장 얻을 수 있는 Reward $R_s$에, 그 Reward를 받은 후 다음 State로 이동했을 때의 Return에 Discounting Factor를 곱한 값이 된다. 어찌 보면 상당히 직관적인 결과이다.

위의 식에서 $\sum_{s^{\prime}\in S}P_{ss^{\prime}}V(s^{\prime})$을 더한 이유는 다음에 이동할 수 있는 State가 1개란 보장이 없고 따라서 그들의 기댓값으로 계산해야 하기 때문이다. 그런데 이 형태는 Linear이기 때문에, 각각의 State들에 대해 $\sum$의 형태 대신 다음과 같이 Vector 형태로 묶어서 표현할 수 있다.

\[V=R+\gamma PV,\quad (I-\gamma P)V=R,\quad V=(I-\gamma P)^{-1}R\]

이것을 Bellman Equation이라고 부른다. 그리고 이를 좀 더 풀어서 쓰면 아래와 같은 Matrix 형태로도 쓸 수 있다.

\[\begin{bmatrix}V(1) \\ \vdots \\ V(n)\end{bmatrix}=\begin{bmatrix}R(1) \\ \vdots \\ R(n)\end{bmatrix}+\gamma\begin{bmatrix}P_{11} & \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\ P_{n1} & \cdots & P_{nn} \end{bmatrix}\begin{bmatrix}V(1) \\ \vdots \\ V(n)\end{bmatrix}\]

이 형태는 MRP가 작다면 직접 풀어볼 수도 있다. 그러나 대부분의 경우는 MRP가 상당히 크기 때문에 이를 직접 푸는 것은 어렵고, 대신 Dynamic Programming, Monte-Carlo Evaluation, Temporal-Difference Learning 등 다양한 Iterative 방식을 통해 이를 간접적으로 풀게 된다.

이제 MDP에서도 Bellman Equation을 생각해보자. MDP에서는 State Value Function과 Action Value Function이 존재한다. 이들도 위와 같이 Policy $\pi$가 고정되어 있다는 가정 하에 동일한 방식으로 Bellman Equation으로 표현이 가능하다. 이들을 Bellman Expectation Equation이라고 부른다.

\[\begin{aligned} V_\pi(s)&=\mathbb{E}\left[r_{t+1}+\gamma V_\pi(S_{t+1})\vert S_t=s\right] \\ &=\sum_{a\in A}\pi(a\vert s)\left(R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^aV_\pi(s^{\prime})\right) \end{aligned}\] \[\begin{aligned} Q_\pi(s,a)&=\mathbb{E}\left[ r_{t+1}+\gamma Q_\pi(S_{t+1},A_{t+1})\vert S_t=s,A_t=a\right] \\ &=R_s^a+\gamma\sum_{s^{\prime}}P_{ss^{\prime}}^a\sum_{a^{\prime}\in A}\pi(a^{\prime}\vert s^{\prime})Q_\pi(s^{\prime},a^{\prime}) \end{aligned}\]

또한 생각해보면 State Value Function에서 다루는 Return과 Action Value Function에서 다루는 Return은 사실 동일한 지표이다. 그래서 이 두 함수의 관계를 생각해볼 수 있다.

위 사진과 같이, State Value Function은 Policy $\pi$에 의해 Action이 선택될 확률과 그 Action이 선택되었을 때의 Action Value Function의 기댓값으로 표현할 수 있다.

\[V_\pi(s)=\sum_{a\in A}\pi(a\vert s)Q_\pi(s,a)\]

반대로 Action Value Function은 현재 State의 Reward와 다음 State의 State Value Function의 기댓값의 합으로 표현할 수 있다.

\[Q_\pi(s,a)=R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^aV_\pi(s^{\prime})\]

이렇게 얻은 두 식과, Bellman Expectation Equation을 통해 얻은 두 식을 합쳐서 현재 State 및 다음 State에서의 State Value Function과 Action Value Function이 서로 상호 변환이 가능함을 알 수 있다.

Bellman Optimality Equation

위에서 확인한 Bellman Expectation Equation은 결국 특정한 Policy $\pi$가 고정되어 있을 때 이를 평가하는 방법을 제공한다. 그러나 우리의 목적은 평가가 아니라 최적의 Value Function을 찾아 Return을 최대로 해야 한다.

즉 각 Value Function의 값이 최대가 되어야 한다. 이러한 경우의 각 함수들을 각각 Optimal State Value Function $V^{\ast}(s)$, Optimal Action Value Function $Q^{\ast}(s,a)$라고 부른다.

\[V^{\ast}(s)=\max_\pi V_\pi(s),\quad Q^{\ast}(s,a)=\max_\pi Q_\pi(s,a)\]

그리고 최적의 Policy $\pi^{\ast}$는 Optimal Action Value Function $Q^{\ast}(s,a)$로부터 얻을 수 있다. 만일 우리가 $Q^{\ast}(s,a)$를 알고 있다면, 다음과 같이 최적의 Policy $\pi^{\ast}(a\vert s)$도 쉽게 구할 수 있게 된다.

\[\pi^{\ast}(a\vert s)=\begin{cases} 1 & \text{if } a=\arg\max_{a\in A}Q^{\ast}(s,a) \\ 0 & \text{otherwise} \end{cases}\]

그리고 결국 Optimal Action Value Function $Q^{\ast}(s,a)$는 존재할 수 밖에 없기 때문에, 이에 따라 Optimal Policy 또한 임의의 MDP에서 반드시 존재함을 알 수 있다. 따라서 Reinforcement Learning의 목표를 Optimal Policy를 찾는 것이 아니라 Optimal Action Value Function을 찾는 것으로 바꿔도 되며, 실제로 이를 이용한 방법도 존재한다.

그러면 앞에서 봤던 Bellman Expectation Equation이 Optimal Value Function에 대해선 어떻게 적용될까?

위의 사진과 같이, 전반적인 형태가 크게 다르진 않다. 다만 기댓값으로 표현했던 Bellman Expectation Equation과 달리, 여기서는 Optimal Value Function을 다루기 때문에 최댓값으로 표현한다.

\[V^{\ast}(s)=\max_a\left(R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^a V^{\ast}(s^{\prime})\right)\] \[Q^{\ast}(s,a)=R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^a\left(\max_{a^{\prime}}Q^{\ast}(s^{\prime},a^{\prime})\right)\]

즉, 위와 같은 형태가 된다. 이 형태의 식을 Bellman Optimality Equation이라고 부른다. 또한 각각의 Optimal Value Function 간의 관계 또한 다음과 같이 표현할 수 있다.

\[V^{\ast}(s)=\max_a Q^{\ast}(s,a)\] \[Q^{\ast}(s,a)=R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^a V^{\ast}(s^{\prime})\]

그런데 이들 Equation들은 더 이상 Linear한 형태가 아니기 때문에, 일반적으로 Closed form solution이 존재하지 않는다. 따라서 이 문제를 풀기 위해 Value Iteration, Policy Iteration, Q-Learning, Sarsa 등 다양한 Iterative 방법을 사용하게 된다.