Policy Improvement
이전 시간 Policy Evaluation을 통해 임의의 정책에 대한 가치를 구했었다. 정책을 평가 하긴 했는데, 어떻게 해야 더 나은 정책으로 바꿀 수 있을까? 예를 들어, 상태 $s$에 있는데 현재 정책을 따라 그대로 행동할 것인지 아니면 새로운 행동($a\neq \pi(s)$)을 해야할지 결정해야한다면, 어떻게 결정하는게 좋을까? 쉽게 생각해보면, 일단 행동해보고 가치가 더 높은 쪽을 택하면 될 것이다. 이전에 가치함수간의 관계식을 다시 떠올려보면 다음과 같았다.
기존 정책과는 다른 행동한 것에 대한 가치 $q_\pi(s, \pi'(s))$ 가 현재 정책에 대한 상태 가치 $v_\pi(s)$보다 높다면, 더 좋은 행동이라 볼 수 있을 것이다.
$$q_\pi(s, \pi'(s)) \ge v_\pi(s)$$
여기서 새로운 정책($\pi'$)과 기존의 정책($\pi$)이며, 결정적(deterministic)이라고 하자. 이는 policy improvement theorem의 하나의 특별한 예이다.
근데 굳이 저렇게 볼 필요없이, 현재 정책보다 더 좋다고 판단할 수 있는 방법은 상태 가치함수끼리 비교하는 것이다. 만약 위 부등식이 성립하면, 다음 부등식도 성립한다.
$$ v_{\pi'}(s) \ge v_\pi(s)$$
이에 대한 증명은 다음과 같다.
이 때까지는 하나의 상태에 대해서 정책을 평가하고 정책을 개선(변화)시켰다. 당연히 이는 모든 상태에 대해서도 동일하게 적용이 된다. 위에서 한 것처럼 결국 각 상태 $s$마다 $q_\pi(s, a)$이 가장 높은 값을 선택하도록 정책을 변화시키면 된다. 이를 greedy policy $\pi'$라고 생각할 수 있다.
여기서 $\arg\max_a$ 는 $a$의 가치 중에 가장 높은 행동이라 보면 될 것 같다. greedy policy는 이전에 말했던 것처럼 당장 앞의(one step of lookahead) 가치만을 보고 행동하지만, 가치함수를 통해 더 먼 미래가 고려된 행동이 된다. 이렇게 greedy 방법으로 가치를 통해 기존 정책을 개선하는 방법을 policy improvement라 한다.
결국 이렇게 greedy policy $\pi'$를 통해 업데이트하다 보면, 최적에 도달해 값이 같아질 것이다. 그럼 부등식이 등식으로 바뀌면서 다음과 같이 된다.
어디서 많이 본 듯하다. 그렇다! 바로 벨만 최적의 방정식이다. $v_\pi'$를 $v_\ast$로 바꾸면 똑같이 되면서 policy improvement가 최적이 되도록 정책을 개선해줌을 알 수 있다.
아래 그림은 이전 시간의 마지막에 나온 예를 정책 평가에 따른 정책을 보인 것이다. 왼쪽은 random policy(상하좌우 행동 모두 동일한 확률로 고르는 것)에 대한 반복적으로 가치 평가를 한 것이다. 오른쪽은 가치에 따라 greedy하게 고를 경우의 정책을 보이며, k=3일 때 최적이 됨을 알 수 있다.
