Chapter 4 Dynamic Programming
Dynamic Programming을 RL에 적용하기 위해서는 MDP와 같은 완전한 환경 모델이 주어져야 한다. 다만 고전적인 DP 알고리즘은 굉장히 많은 연산량이 필요하기 때문에 현실적으로는 진행하지 못할 가능성이 크다. 책의 뒤에서 다루는 MC나 TD 방법론들은 적은 연산으로도 동일한 효과를 얻기 위한 과정이라고 볼 수 있다.
| 책에서는 DP를 소개할 때의 환경을 Finite MDP로 가정한다. 즉, State나 Action이 유한개이고, Transition Probability $P(r, s’ | s, a)$가 주어져 있다고 가정하는 것이다. Continuous space 또한 근사나 양자화를 통해서 finite하게 다룰 수 있으므로 Finite MDP가 기본이다. |
DP는 3장에서 다룬 Value function을 구하고 value를 maximize하는 행동을 선택하도록 policy를 구하는 과정을 거친다. 결국 Optimal Value Function을 구하는 과정이 DP라고 생각할 수 있다. 3장에서 다루었던 것처럼 최적 가치함수는 아래의 수식을 만족한다.
\[\begin{align} v_*(s) &\doteq \max_{a\in\mathcal{A}(s)} \mathbb{E}\!\left[ R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t=s,\; A_t=a \right] \\[8pt] &= \max_{a\in\mathcal{A}(s)} \sum_{s'\in\mathcal{S}}\sum_{r\in\mathcal{R}} p(s',r\mid s,a)\, \Bigl[r + \gamma v_*(s')\Bigr]. \end{align}\] \[\begin{align} q_*(s,a) &= \mathbb{E}\!\left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1},a') \;\middle|\; S_t=s,\; A_t=a \right] \\[8pt] &= \sum_{s'\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s',r\mid s,a)\, \left[ r + \gamma \max_{a'} q_*(s',a') \right]. \end{align}\]DP의 큰 두 축은 위 Bellman Equation을 Assignment Rule로 변경하는 과정으로 이해할 수 있다.
4.1 Policy Evaluation
임의의 정책 $\pi$에 대한 정확한 가치함수를 계산하는 과정을 Policy Evaluation / Prediction Problem이라 한다. 정책에 대한 정확한 가치함수를 알고 있다면 아래의 수식이 성립한다.
\[\begin{align} v_\pi(s) &= \sum_{a\in\mathcal{A}(s)} \pi(a\mid s)\; q_\pi(s,a) \\[4pt] &= \sum_{a\in\mathcal{A}(s)} \pi(a\mid s) \sum_{s'\in\mathcal{S}}\sum_{r\in\mathcal{R}} p(s',r\mid s,a)\; \Bigl[r + \gamma v_\pi(s')\Bigr]. \end{align}\]모든 환경 정보를 알고 있다면 $\mid S \mid$개의 선형연립방정식을 푸는 것이기에 풀 수 있지만 Iterative Method을 사용하여 해결하는 것이 가능하다. $v_k$의 존재를 보장한다면, 아래와 같은 Update 식을 $\infty$번 반복하여 최종적으로 정확하게 $v_{\pi}$로 성립하게 된다. 아래와 같은 반복적인 방법을 사용하는 것을 Iterative Policy Evaluation이라 한다.
\[\begin{align} v_{k+1}(s) &= \mathbb{E}_{\pi}\!\left[ R_{t+1} + \gamma v_k(S_{t+1}) \mid S_t = s \right] \\ &= \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma v_k(s') \right]. \end{align}\]위 수식을 생각해보면, One step transition으로 발생할 수 있는 즉각적인 Reward와 다음 state의 가치의 기댓값을 활용하여 현재 state의 가치를 갱신하는 것으로 이해할 수 있다. 따라서 이를 Expected Update(기댓값 갱신) 이라고 부른다. 기댓값을 어떻게 활용하여 사용하느냐에 따라 다양한 기댓값 갱신이 존재한다.
$v_k$를 구현하는 과정을 자세히 살펴보면, value function 변경을 즉각적으로 반영하느냐 아니냐에 따라서 나눌 수 있다. 두 개의 배열을 사용하여 이전의 step의 value function만을 사용하는 synchronous backup 또한 존재할 수 있지만, 하나의 배열을 사용하여 업데이트된 최신 value function을 활용하는 일종의 asynchronous backup도 활용할 수 있기 때문이다. 다만, 비동기적 갱신 방법을 사용하는 경우 상태 공간에 대한 sweep(일괄처리) 순서가 순서에 큰 영향을 미친다.