Dynamic Programming
Dynamic programming (DP)란 MDP같은 환경의 완벽한 모델을 가지고 최적의 정책을 계산하는 알고리즘들을 말한다. 이전처럼 수식 전체를 한 번에 계산하지 않기에 계산량이 좀 더 적다는 장점이 있다. 하지만 환경을 완전히 알아야 하는 단점이 있기에, 실제로 잘 사용하지는 않는다. 앞으로 나올 강화학습 알고리즘들은 정확한 계산을 하는 이 알고리즘만큼 효과를 보도록 근사하는 것이라 볼 수 있다.
상태, 행동 그리고 보상이 유한하게 존재하고 dynamic $p(s', r | s, a)$이 주어져서 알고있는 episodic finite MDP라 가정한다. (물론 continuous 경우에도 DP를 적용할 수는 있다. 상태화 행동을 양자화해서 finite-state DP 방법에 적용하는 식으로 Chapter 9에서 이 방법을 좀 더 확장한 형태로 보여줄 예정이다.)
DP의 핵심 아이디어는 가치함수를 이용해 좋은 정책을 찾는 것이다. 이는 이미 Chapter 3에서 보았지만, 다른 점은 원하는 가치 함수의 근사치로 개선하기 위해 업데이트하는 방식으로 바꾸었다는 점이다.(즉, 한 번에 구하는 게 아닌 여러 차례의 업데이트를 통해 구한다는 뜻이다)
Policy Evaluation (Prediction)
임의의 어떤 정책에 대한 상태 가치함수 $v_\pi$를 계산해야 한다. 이를 DP에서 정책 평가(policy evaluation)라 부른다. 또한 이를 예측 문제(prediction problem)라고 부른다.
정책이나 보상, dynamic을 알고 있다면 $v_\pi(s)$를 알려면 결국 $v_\pi(s')$를 알아야 하고, $v_\pi(s')$를 알려면 $v_\pi(s'')$를...이런 식으로 마지막 상태의 가치 $v_\pi(s^T)$까지 알아야한다. 바로 구하기는 힘들지만, 마지막 상태 전의 $v_\pi(s^{T-1})$ 가치는 구하면, 그 이전 상태의 가치$v_\pi(s^{T-2})$를 구할 수 있고, 반복하다보면 $v_\pi(s)$를 알수 있게 된다. 각 상태에 동일하게 적용해서 이를 반복하는 이 방법을 반복적인 정책 평가(iterative policy evaluation)라 부른다.
$v_k=v_\pi$로 바뀐 것 뿐이다. $k \rightarrow \infty$가 되어 반복한다면 결국 수렴하게 될 것이고, 가치 $v_\pi(s)$는 곧 정책 $\pi$를 따랐을 때, 상태 $s$에서의 가치가 된다.
한 번의 step으로 이동 가능한 모든 상태에 대한 가치와 보상으로 업데이트 하는 것이기 때문에, 이를 expected update라 부른다.
이를 실제로 프로그래밍 하기 위한 방법이 두 가지가 있다. 하나는 배열 두 개로 업데이트하는 방법, 또 하나는 배열 하나로만 업데이트하는 방법(in-place)이다. 차이라면 in-place 방법으로 할 경우, 업데이트 하기 이전 가치 $v_{k+1}$를 쓰기 전에 이미 업데이트된 $v_{k+1}$를 쓸 수도 있다는 점 뿐이다. (순서가 있을 수 밖에 없으므로..)예상했는지 모르겠지만, 빠르게 최신 가치로 업데이트 하는 in-place 방법이 더 빠르다. 이렇게 전체 state에 대해서 업데이트 하는 것을 sweep이라 볼 수 있다. sweep 할 때 순서는 수렴 속도에 굉장히 영향을 많이 끼친다.
PsuedoCode
Iterative policiy evaluation를 in-place 방법으로 구현한 의사 코드다.
Example
어떤 undiscounted, episodic task가 있고 dynamic은 모든 움직임에 대해 확률 1인 격자 세계(grid world)가 있다고 하자. 회색은 종료 지점이며, 이동할 때마다 보상을 -1을 받고(종료 상태 제외), 정책은 상하좌우 모두 동일한 확률로 고르는 것이라고 하면, 이 정책에 대한 가치는 어떻게 될지 생각해보자.(상태 가치, 행동가치 둘 다 생각해보면 좋을 듯하다.)
