1. DP vs RL
•
Dynamic Programming
◦
Model-based
◦
모든 next state 고려하여 value update 시 복잡한 계산을 효율적으로 수행할 수 있도록 고안된 방법
•
RL
◦
Model-free
◦
Sample을 기반으로 value update (근사적)
◦
Update된 value를 바탕으로 근사적인 Bellman optimality equation의 해 찾음
•
Tabular updation method
◦
DP와 RL 공통 사용
◦
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 unknown
▪
Policy update 시 update 대상: action value function
▪
Sample 기반 update를 적용하기 때문에 state의 차원 확대에 영향을 받지 않음
▪
DP가 가지는 차원의 저주 문제를 피할 수 있다는 장점을 가짐
2. GPI
•
GPI는 sample을 바탕으로 PE와 PI를 진행하는 방식
•
Value function을 sample을 사용하여 근사하고, 그것을 기반으로 greedy policy로 policy update
•
Policy evaluation 단계에서 sample만 가지고 value update를 진행하기 때문에 수렴시까지 반복 불가
◦
전이 확률/보상을 정확히 계산할 수 없음
•
만약 Policy가 stabilize 상태라면, 이후 iteration에서 산출되는 value 들의 변화가 거의 없음
◦
이때 Q function은 Bellman optimality equation을 만족
◦
그때의 policy가 optimal policy