[RL] Flexibility of the Policy Iteration Framework

(해당 포스트는 Coursera의 Fundamentals of Reinforcement Learning의 강의 요약본입니다)

 Policy Iteration은 Policy Evaluation과 Policy Improvement를 반복하면서 현재의 policy \(\pi\)를 최대한 optimal policy \(\pi_*\)에 가깝게 update하는 방법을 말한다. 아마 Sutton책에서는 다음과 같은 그림으로 도식화를 해놨을 것이다.

그림 1. Policy Iteration

아니면 이런 그림도 같이 보았을 것이다.

그림 2. Policy Iteration (a.k.a Dance of Policy and Value)

 현재의 policy \(\pi\)와 초기의 value function \(v\)가 있으면, 처음에는 \(\pi\)에 따라 action을 취하고 이에 맞게 value function을 update하게 된다 (\(v=v_{\pi}\)) 이 과정이 Policy Evaluation이 되고, updated value function 중에서 가장 좋은 value를 내뱉어주는 action을 deterministic하게 취하는 policy가 있으면 그건 아마 기존의 policy \(\pi\)보다 좋을 것이다. (\(\pi = \text{greedy}(v)\)) 이때 기존 policy를 새로운 policy로 update해줄 수 있는데 이게 Policy Improvement이다. 그래서 이런 과정을 반복해주다보면 어느 순간인가에는 기존 policy와 새로운 policy가 동일한 순간이 나올 것이고, 이게 optimal policy \(\pi_*\)를 찾았다는 termination condition이 된다. 이렇게 왔다갔다 하는 과정이 마치 춤추는 것과 비슷해서 강의에서는 "Dance of Policy and Value"라고 표현하기도 한다. 

 그런데 만약 이렇게 왔다갔다하는 과정을 조금 완화시켜보는 것을 생각해보면 어떨까?

그림 3. Generalized Policy Iteration

  이론적으로만 놓고 보면 value function을 update하려면 현재의 policy \(\pi\)를 이용해서 모든 state를 다 탐색해야 가능하지만, 관심 범위내의 value function만 update하고, 또 현재의 value function을 바탕으로 greedy하게 action을 취하는 policy도 기존보다 조금 덜 greedy하게 action을 취하는 policy로 Improve를 시킨다면 어떨까? 직관적으로 생각해봐도, 위 그림에서도 보는 것과 같이 policy Iteration을 통해서 optimal policy \(\pi_*\)를 찾는 것처럼 위 과정도 역시 \(\pi_*\)를 찾을 수 있을 것이다. 이것을 Generalized Policy Iteration (GPI)라고 표현한다.

 전체적인 동작은 기존의 Policy Iteration과 거의 유사하다. 하지만 앞에서도 소개한 바와 같이 모든 value function를 update하는 policy evaluation이 아닌, 하나의 step 내에서 value function을 update한 후, 그 value function으로 policy를 improve시킨다. 그래서 이 과정을 Value Iteration이라고 표현을 하는데, 먼저 기존의 Policy Iteration의 Algorithm과의 차이점을 Pseudocode로 살펴보면 다음과 같다.

그림 4. Policy Iteration Algorithm

그림 5. Value Iteration Algorithm

잘보면 Policy Evaluation과 Value Iteration의 구성이 거의 비슷하지만, Value Iteration에서는 어떤 policy \(\pi\)에 따르지 않고, 현재의 value function에 직접적으로 update하는 것을 확인할 수 있다.(\(V(s)\)를 update할때 probability \(p(s', r|s, \pi(s))\)를 취한 policy evaluation과는 다르게, Value Iteration에서는 \(p(s', r|s, a)\)의 max 값으로 바로 value function을 update하는 것도 확인이 가능하다. 사실 이게 바로 이 algorithm이 value iteration이라고 부르는 이유이기도 하다. policy가 아닌 value function을 바로 update하기 때문에!!)

 그러면 한 step 내에서 value function을 update하기 위해 들어가는 state를 어떻게 선택할건지에 따라서도 결과가 달라지게 되는데, 이게 Systematic하게 순차적으로 state를 밟아가면 Synchronous Dynamic Programming으로 해결할 수 있다고 하고, 이게 아니라 어떤 state가 오던 순서에 상관없이 state에 따른 value function을 update하는 방식을 Asynchronous Dynamic Programming 이라고 한다. 물론 직관적으로 생각해보면 Asynchronous하게 state를 탐색하면, 중간에 탐색하지 못한 state도 나올 수 있기 때문에 모든 state를 탐색하기 위한 조건이 들어가 있어야 하긴 하지만, 이게 보장된다면 Synchronous DP보다는 빠르게, 그리고 효율적으로 value function을 update할 수 있다.