Deep Reinforcement Learning 3 - Planning by Dynamic Programming

Before starting

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

Dynamic Programming & MDP

저번 글에서 다뤘던 MDP를 실제로 푸는 법을 알아보자. 우선 Reinforcement Learning에서 Agent가 Environment를 예측하는 Model을 가지고 있는 경우를 Model-based, 가지지 않은 경우를 Model-free라고 한다. 그리고 Model-based MDP를 푸는 문제를 Planning이라고도 부른다.

이 Planning 문제, 즉 Model-based MDP를 푸는 가장 쉬운 방법 중 하나가 Dynamic Programming이다. 알고리즘, 혹은 Problem Solving에서 다루는 바로, 점화식을 세워서 푸는 그 DP를 말하는 것이 맞다.

어떤 문제를 DP로 풀려면 몇 가지 조건이 필요한데, 우선 큰 문제를 여러 Optimal한 Subproblem으로 나눌 수 있어야 한다. 즉, Optimal solution에 subproblem의 optimal solution이 항상 포함된다는 Principle of optimality를 만족해야 한다. 그리고 이들 subproblem들이 전부 같은 형태를 가져서 저장 및 재사용이 용이해야 한다. 이를 Overlapping subproblems라고 한다.

그리고 MDP는 이 두 조건을 모두 만족한다. Bellman Equation이 바로 DP로 문제를 풀기 위해 구성하는 점화식 형태로 구성되며, 그 값들은 memoization이 가능하기 때문이다. 다만 DP로 풀기 위해선 현재 State에서 어떤 Action을 취했을 때 어떤 State로 이동할지를 알고 있어야 한다. 즉, Model-based MDP만 DP로 풀 수 있다.

이러한 Planning은 크게 2가지로 분류할 수 있다. 첫번째는 Prediction 문제로, MDP와 Policy $\pi$가 주어질 때 Value Function $V_\pi$를 예측하는 문제다. Policy Evaluation이라고도 부른다. 두번째는 Control 문제로, MDP만 주어질 때 Optimal Value Function $V^{\ast}$ 및 Optimal Policy $\pi^{\ast}$를 찾는 문제다. Control 문제를 풀기 위한 방법으로 Policy Iteration과 Value Iteration 등이 있다.

이제 DP로 이들 각 문제를 어떻게 해결할 수 있는지 알아보자.

Iterative Policy Evaluation

먼저 Prediction 문제를 해결하기 위해서는 주어진 Policy를 Iterative하게 Evaluation한다. 즉, Bellman Expectation Equation을 반복 적용해서 Value Function을 계속 업데이트하는데, 그러다보면 어느 순간 수렴하게 되고 그 때의 Value Function이 이 Policy의 Value Function이 된다.

즉, Bellman Expectation Equation의 모든 State에 대해 Synchronous Backup을 해서, 다음과 같이 $V_{k+1}(s)$를 구한다.

\[V_{k+1}(s)=\sum_{a\in A}\pi(a\vert s)\left(R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^aV_k(s^{\prime})\right)\]

이 때 $s^{\prime}$은 State $s$에서 이어질 수 있는 State를 의미한다.

아래와 같은 길찾기 예시를 통해 실제로 어떻게 수행되는지 확인해보자.

위의 상황에서, 취할 수 있는 Action은 4방향 각각으로 이동하는 것, 그리고 $1,\cdots,14$까지의 State가 주어져 있다. 우리의 목표는 임의의 State에서 시작했을 때 Terminal State인 검은 칸 둘 중 아무 곳에나 도달하는 것으로, 그 때의 최적 경로를 찾는 것이다. 문제를 간단히 하기 위해 Discounting Factor $\gamma=1$로, Reward는 이동 한번당 -1로 설정한다. 이는 이동 횟수를 최소화하기 위함이다.

그리고 우리가 이번에 Evaluation할 Policy는 아래와 같이 Uniform Random Policy라고 가정해보자.

\[\pi(n\vert\cdot)=\pi(e\vert\cdot)=\pi(s\vert\cdot)=\pi(w\vert\cdot)=0.25\]

그리고 매 Iteration마다 각 State의 Value Function의 값 $V_k$를 계산해보면 위 표와 같다. 빨간 칸, 즉 State 1에서의 $V_k$값을 따라가보자. $k=0$이라면 모든 State에서의 값은 0이 된다.

이 상황에서 $A={a_1,a_2,a_3,a_4}$, $\pi(a_i\vert s)=0.25$, $r=-1$, $\gamma=1$이다. 또한 모든 Action이 반드시 하나의 State로만 변환되므로 항상 $P_{ss^{\prime}}^a=1$이 된다.

이를 바탕으로 $k=1$이면 다음과 같이 $V_k$를 계산할 수 있다.

\[\begin{aligned} V_{k+1}(s)&=\sum_{a\in A}\pi(a\vert s)\left(R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^aV_k(s^{\prime})\right) \\ &= 0.25(-1) + 0.25(-1) + 0.25(-1) + 0.25(-1) \\ &= -1 \end{aligned}\]

같은 방식으로 $k=2$에서는 다음과 같이 $V_k$를 계산할 수 있다.

\[\begin{aligned} V_{k+1}(s)&=\sum_{a\in A}\pi(a\vert s)\left(R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^aV_k(s^{\prime})\right) \\ &= 0.25(-1 + 0) + 0.25(-1 - 1) + 0.25(-1 - 1) + 0.25(-1 - 1) \\ &= -1.75 \end{aligned}\]

이렇게 MDP를 알고 있으면 매 State 및 매 시간마다 각각의 State들을 모두 다 Update할 수 있다. 이러한 흐름을 따라가며 Iterative하게 Policy Evaluation을 수행한다는 이야기이고, 위 예시에선 이런 식으로 쭉 진행하다보면 다음과 같이 특정한 값으로 수렴하게 된다.

이렇게 더 이상 값의 Update가 이루어지지 않는 상태가 되면 Iteration을 종료하면 된다. 그리고 이렇게 Update된 Value Function을 보고 Policy를 세울 때에는 Greedy하게 선택하면 Optimal한 Policy를 얻을 수 있다.

Policy Iteration

분명 이 예시에서 시작은 Random Policy였다는 사실에 주목하자. 우리는 어떠한 가정도 넣지 않은 채로 Policy Evaluation을 시작했는데, 결국 Optimal Value Function으로 수렴하게 되었으며 이를 통해 Optimal Policy까지 얻을 수 있었다.

이 과정은 다음과 같이 두 줄로 요약할 수 있다.

• Evaluate Policy $\pi$: $V_\pi(s)=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\cdots\vert S_t=s\right]$
• Improve Policy: $\pi^{\prime}=\text{greedy}(V_\pi)$

이렇게 매 Iteration마다 Greedy하게 Policy를 Update하게 되면 결국 Optimal Policy를 얻을 수 있음이 Policy Improvement Theorem에 의해 증명되었다. Policy Improvement Theorem은 다음과 같이 간단하게 요약할 수 있다.

$\pi^{\prime}=\text{greedy}(V_\pi)$이면 $Q_\pi(s,\pi^{\ast}(s))\ge V_\pi(s)$가 된다. 따라서 $V_{\pi^{\prime}}\gt V_\pi$가 된다. 또한 유한 MDP는 Deterministic Policy가 유한 개 존재하므로 반드시 유한 번 안에 멈춘다. 즉 수렴하게 된다.

물론 수학적인 증명 외에도 다음과 같이 직관적으로 이해가 가능하다.

즉, Value Function을 업데이트한 것으로부터 최적의 Policy를 찾고, 이것이 저번 Iteration보다는 조금 더 나아진 Policy가 되며, 이 더 나아진 Policy로 Value Function을 업데이트하니 다시 조금 더 최적의 Policy가 나오는 식의 선순환이 이루어지는 것이다.

Value Iteration

앞에서 간단하게 살펴봤던 Principle of Optimality를 생각해보자. Optimal Solution에 Subproblem의 Optimal Solution이 포함되어야 한다. 이를 MDP에서 생각해보자.

State $s$, 그리고 $s$로부터 도달할 수 있는 State $s^{\prime}$가 있다고 하자. 이 때 $s^{\prime}$에서의 Optimal Value Function $V^{\ast}(s^{\prime})$은 명백하게 $s$에서의 Optimal Value Function $V^{\ast}(s)$의 subproblem이므로, 만일 Policy $\pi$가 $V_\pi(s)=V^{\ast}(s)$를 만족한다면 이는 곧 $V_\pi(s^{\prime})=V^{\ast}(s^{\prime})$과 동치가 된다.

이 이야기를 뒤집으면, 현재 State에서의 Optimal Solution $V^{\ast}(s)$는 그 다음 State의 Optimal Solution $V^{\ast}(s^{\prime})$으로부터 구할 수 있다는 이야기가 된다. 구체적으로는 다음과 같이 계산할 수 있다.

\[V^{\ast}(s)\leftarrow\max_{a\in A}\left(R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^aV^{\ast}(s^{\prime})\right)\]

딱히 새로운 형태는 아니고, Bellman Optimality Equation이 그대로 등장한 것이다. 즉, 현재 State의 Optimal Value Function은 다음 State의 Optimal Value Function으로 표현이 되니까 이를 반복적으로 풀어가면 우리가 원하는 Optimal Solution 또한 구할 수 있게 된다. 이를 Value Iteration이라고 부른다.

아까 있었던 Bellman Expectation Equation의 Synchronous Backup과 마찬가지로, 이번에는 Bellman Optimality Equation을 Synchronous Backup을 통해 반복적으로 계산하면 된다. 다만 이번엔 순서가 다음 State로부터 현재 State로 거슬러 올라가는 것이므로 맨 마지막에 있는 Terminal State에서 시작해서 Initial State까지 거슬러 올라가는 형태가 될 뿐이다.

즉, Bellman Optimality Equation의 모든 State에 대해 Synchronous Backup을 해서, 다음과 같이 $V_{k+1}(s)$를 구한다.

\[V_{k+1}(s)=\max_{a\in A}\left(R_s^a+\gamma\sum_{s^{\prime}\in S}P_{ss^{\prime}}^aV_k(s^{\prime})\right)\]

이 때 $s^{\prime}$은 State $s$에서 이어질 수 있는 State를 의미한다.

다만 이번에는 Policy Evaluation과 달리 값 전체가 $\max$로 감싸져있는 형태가 되므로, Policy를 직접 구한다기보단 그냥 Value를 가장 최대화하는 Action만 따라가겠다는 의도가 된다.

이번에도 길찾기 예시를 통해 실제로 어떻게 수행되는지 확인해보자.

이번에는 Terminal State가 왼쪽 위의 1개만 존재한다. 그리고 Bellman Optimality Equation으로 Update를 하게 되면 위 사진과 같은 식으로 점점 Value가 구해지게 된다. 처음에는 모든 State에서의 Value값이 전부 동일하게 구해지지만, Iteration이 진행될수록 점점 Terminal State 주변의 State들이 Terminal State의 영향을 받아 값이 달라지게 된다.

이러한 식으로 Value가 계속 Update되면서 어느 순간 더 이상 Update가 되지 않는, 수렴하는 상태가 될 것이다. 이 때의 Value들을 점점 커지는 순으로 따라가다보면 그것이 곧 Optimal Policy가 될 것이다. 이러한 방식으로 문제를 푸는 것이 Value Iteration이다.