Dynamic Programming 3

이전 포스트에서 DP의 대표적인 방법론들인 Policy Iteration과 Value Iteration에 대해서 배웠다. 이 두 방법론을 우선 비교해보고, 그다음에 DP에 대한 추가적인 이해를 가져보도록 하자

Policy Iteration vs. Value Iteration

1-step computation cost

Policy iteration의 경우 우선 bellman expectatio equation인 $v_{\pi}(s) = \sum_{a}\pi(a\mid s)\sum_{r, s'}(r + \gamma v_{\pi}(s))$을 iterative method를 통해서 풀어야 하기 때문에 $O(k\cdot |S|^2)$만큼의 계산 복잡도가 나온다. 이후 policy improvement의 경우 각 state마다 action을 스캔하기 때문에 $O(|S|^2|A|)$의 계산 복잡도가 나와서, 결과적으로 1-step computation cost는 $O(k\cdot|S|^2+|A|\cdot|S|^2)$이다.

 

Value iteration의 경우 1 step에서 모든 $(s, a, s')$ transition에 대해서 추정하는 것이기 때문에, $O(|S|^2 \cdot |A|)$이 된다.

 

결론적으로, VI의 1-step cost는 PI보다 훨씬 낮은 것을 확인할 수 있다.

Number of total iteration

결론을 먼저 말하면, policy iteration이 value iteration에 비해서 더 적은 iteration만으로도 수렴을 도달할 수 있다. 

Policy Improvement는 global greedy step이다. 기존 policy의 value function을 fully evaluate한 뒤, 다음 policy는 그 value function에 대해 모든 state에서 argmax action 한 번으로 업데이트가 가능하기 때문이다.

즉 update가 policy space상에서 매우 큰 jump를 하는 것이고, 따라서 적은 step만으로도 최적에 도달할 수 있는 것이다.

 

반면 value iteration은 value만으로 pointwise incremental improvement하는 방식이다. 즉 state마다

$$ v^{k+1}(s)=\max_a \sum_{s',r}p(s',r\mid s,a)[r+\gamma v^k (s')] $$

으로 value를 조심씩 조정해나가는 방식이다. 특히 $\gamma$ 값에 따라 수렴 속도가 크게 달라진다. $\gamma$-contraction 식을 한번 참고해보자.

$$ \| T^*v - T^*u\|_{\infty} \leq \gamma \|v-u\|_\infty $$

으로, $\gamma$값이 커질수록 그 upper bound가 커져 수렴이 늦어지는 것을 확인할 수 있다.

Worst case evaluation

Value iteration의 computation cost는 $\gamma$에 반비례함을 알 수 있다.

우리가 원하는 정확도 $\epsilon$ 만큼 $v_k$ 가 $v_{*}$ 에 가까워지길 원한다고 하자. Bellman Optimal Operator $T^{*}$ 는 $\gamma$-contraction이다:

$$ \|T^{v} - T^{w} \|_{\infty} \le \gamma \|v-w\|_{\infty} $$

Value Iteration은

$$ v_{k+1} = T^{*}(v_k) $$

이므로 반복 적용하면

$$ \| v_k - v_{*} \|_{\infty} \le \gamma^k \| v_0 - v_{*} \|_{\infty} $$

reward가 bounded 라고 하자 ($|R|\le R_{\max}$). 그러면 $\|v_0 - v_{*}\|_{\infty}$ 의 maximum bound 는

$$ \| v_0 - v_{*} \|_{\infty} \le \frac{R{\max}}{1-\gamma} $$

따라서

$$ \| v_k - v_{*} \|_{\infty} \le \gamma^k \cdot \frac{R{\max}}{1-\gamma} $$

가 되고, 우리는 저 upper bound가 $\epsilon$보다 작게 만들어야 하므로, 결과적으로 iteration의 lower bound는 $\frac{\ln(\epsilon(1-\gamma)/R_{max})}{\ln(\gamma)}$가 된다.

 

Policy iteration의 worst case는 1회 연산량에 $|A|^{|S|}$만큼 곱해지는 경우이다. Policy를 enumeration에 준하는 방식으로 하나씩 계단식으로 올라가도록 강제될 수 있는 MDP가 존재할 수 있기 때문에, 이러한 경우 보통 Policy iteration이 다 빠르다는 직관과는 다르게 지나치게 심한 iteration을 반복해야 할 수도 있음을 알 수 있다.

 

Conclusion

그러면 VI랑 PI 둘 중 어느 것이 더 좋은가? 상황에 따라 다르겠지만 대체적으로 PI가 iteration 개수 대비 큰 jump를 하므로 practical DP context에서는 PI가 VI보다 빠른 경향이 있다. VI는 evaluation을 극단적으로 간략화한 형태이기 때문에 iteration은 많아지지만 scalable하다.

어느 개념이 더 중요하냐고 하면, 당연히 PI이다. RL의 optimization target은 value가 아니라 policy다. 앞으로 나오는 MC, TD, SARSA, Q-learning 전부 value를 evaluate하고, greedy 또는 $\epsilon$-greedy를 통해서 policy를 improve한다. 그래서 일반화되는 framework는 GPI이고, VI는 evaluation과 improvement가 fused된 special case라서 generalization 이름을 못 가지게 되는 것이다.

 

Appendix

지금까지 DP를 하면서 들었던 의문에 대해서 답을 해보자.

1. Stochastic policy가 deterministic policy보다 더 좋거나, 둘 중 하나만 좋거나 하는 경우는 없는가?

우선 Model을 온전히 다 아는 finite MDP 환경에서 항상 deterministic optimal policy가 존재한다. 즉 어떤 stochastic policy도 deterministic optimal policy보다 strict하게 더 좋을 수 없다. 물론 stochastic policy 또한 policy improvement를 얼마든지 할 수 있음은 참이다. 예전에 써놓은 것인데, 한번 확인해보면 좋겠다.

그러나 model을 알지 못하는 경우에는 stochastic policy가 exploration을 할 수 있도록 하기 때문에, 더 유리할 수 있다.

 

2. Markovian policy가 non-markovian policy와 비교해서 항상 좋다고 할 수 있는가?

우선 환경이 완전한 Markov인 경우 Non-Markov가 Markov policy를 능가하지 못한다. $\pi(s) \in \arg\max_a Q_{\pi}(s,a) $를 생각하자. 하지만 똑같이 환경이 완전한 markov가 아닌 경우 그러지 않을 수도 있다.

 

3. Markovian stationary policy가 markovian non-stationary policy보다 항상 좋다고 할 수 있는가?

1, 2에서 본 markovian stationary deterministic policy가 optimal임을 보였기 때문에, discounted Finite MDP에서는 stationary deterministic optimal이 항상 존재하고, non-stationary가 능가할 수 없다.