[Dynamic Programming - 3] Policy Iteration

Policy Iteration

Policy Iteration은 optimal policy와 이의 value function을 alternating하면서 서로를 개선한다. 이렇게 현재의 policy으로 value를 계산하고 해당 value를 통해서 policy을 개선하는 반복적인 과정은 많은 강화학습 알고리즘에 영향을 끼쳤다. 이 점에서 Policy Iteration은 강화학습에서 매우 중요한 의의를 가진다.

Algorithm

1. $\pi(a|s)$(Policy)와 $V(s)$ (각 State에 대한 State Value)를 임의의 값으로 initialize한다.
2. [Policy Evaluation] 현재 임의로 정한 Policy를 기준으로 각 State에 대한(모든 Action을 고려) Expected return을 각 State의 State Value로 업데이트한다.
   • Value Iteration의 경우 가장 큰 Expected Return을 주는 Action의 Value를 State Value로 사용하는 Value function을 사용하였다.
     
     $$V(s) \gets \sum_a \pi(a|s) \sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]$$
     
     
   • 그러나 Policy Evaluation에서는 모든 가능한 Actions를 고려하여 각 Action들의 Expected Return의, Expected Return을 State Value로 사용하는 Value function을 사용한다.
     • 즉, $V(s)$ 는 현재 Policy하에, 해당 State에서의 가능한 모든 결과들의 weighted sum이다.
     • 이는 곧 Bellman Equation이다.
   • 위와 같은 방식으로 각 State Value의 최대 변화량이 Delta보다 작아질 때 까지 반복한다.

3. [Policy Improvement] 산출된 State Value들을 기반으로 Expected return을 최대화하는 방향으로 현재 Policy를 개선한다.
   
   $$q_\pi(s,a) = \sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]$$
   
   
   • 현재 Policy를 개선하기 위해서는 Q-value를 사용한다. 왜냐하면 Q-value는 각 State에서 각 Action들의 가치를 표현하기 때문이다.
   • 따라서 특정 Action에 대한 Q-value가 현재 State value보다 높을 경우 현재 Policy $\pi$ 를 현재 State에서 해당 Action을 선택하는 Policy $\pi'$으로 변경한다.
   • 이를 모든 State에 반복한다.

4. Policy Improvement 단계에서 단 하나의 State에 대한 Policy라도 변했다면, Policy Evaluation부터 다시 수행한다. Policy가 더이상 변하지 않는다면 반복을 멈춘다.

• Policy Evaluation과 Policy Improvement는 하나의 과정이 다른 과정의 결과를 바탕으로 작동하기 때문에 서로 경쟁적인 관계에 있을 수 있다. 그러나 두 과정은 서로를 최적의 해결책으로 밀어내는 협력적인 역할이기도 하다.

Practice

[실습 환경 (Maze)]

 

 

[1번째 Iteration] - 모든 Action의 확률이 같은 상태
Policy Evaluation
: 아래에서 볼 수 있듯이 매우 낮은 State value를 가지고 있다. 왜나하면, Random policy이므로 목표 상태에 도달하기까지 매우 많은 시행착오를 거쳐야하고, 그 과정에서 negative rewards들이 쌓이기 때문이다.

Policy Improvement
: Policy Improvement 수행 후 Policy는 Optimal이다. 왜냐하면, 기존 Policy가 랜덤 Policy이긴 하지만, Agent는 결국에 Goal에 더 가까운 State일 수록 Goal에 더 빨리 도달한다는 것은 자명하므로 Policy는 이를 통해 개선하기 때문이다.

[2번째 Iteration]
Policy Evaluation
: 이미 Optimal Policy인 상태에서의 Policy Evaluation

Policy Improvement
: 이미 Policy는 Optimal 이며, Policy가 바뀌지 않았으므로 Iteration이 종료된다.