1. DP vs RL
Dynamic Programming은 model-based인 경우 모든 next state를 고려하여 value를 update할 때, 복잡한 계산을 효율적으로 수행할 수 있도록 고안된 방법이다. 반면 RL은 model-free 상황에서 sample에서 얻어진 state를 기반으로 value를 근사적으로 update하는 방식이다. update된 value를 바탕으로 근사적인 Bellman optimality equation의 해를 찾는다.
DP와 RL은 모두 tabular updation method르 사용하는데, 이는 value function 값을 저장할 table을 만들어두고 이것을 반복적으로 update하여 optimal policy를 찾는 것을 목적으로 하는 방식이다.
DP에서는 각 반복마다 table 내의 모든 value가 update되는데, 계산 효율성을 위해 대부분 state-value function의 값을 사용한다. update 된 value function을 기반으로 greedy policy improvement를 적용하여 policy를 개선한다.
RL에서는 각 반복마다 sample에서 주어지는 value만 update한다. 무엇보다 transition probability를 모르기 때문에 Policy update를 위해 update 대상이 되는 value function을 action value function을 사용한다. 추가로, sample 기반 update를 적용하기 때문에 state의 차원 확대에 영향을 받지 않는다. 따라서 DP가 가지는 차원의 저주 문제를 피할 수 있다는 장점을 가진다.
2. GPI
GPI는 sample을 바탕으로 PE와 PI를 진행하는 방식이다. 현재 Policy에서의 true value로 value function을 sample을 사용하여 근사하고, 그것을 기반으로 greedy policy로 policy update를 진행한다. 이때 Policy evaluation 단계에서 sample만 가지고 value update를 진행하기 때문에 수렴시까지 반복할 수 없다는 특징을 가진다. 만약 Policy가 stabilize 상태라면, 이후 iteration에서 산출되는 value 들의 변화가 거의 없을 것이다. 따라서 이때의 Q function은 Bellman optimality equation을 만족한다. 그러므로 그때의 Policy가 optimla policy가 된다.