[Dynamic Programming - 4] Generalized Policy Iteration(GPI)

Generalized Policy Iteration (GPI)

 

GPI는 대부분의 강화학습 알고리즘의 general template 이다. Monte Carlo methods는 model of the environment가 정의되지 않은 상태의 알고리즘이지만, environment에서 수집된 experience로 value를 update한다는 차이점만 있고 큰 형식은 GPI를 따른다.

많은 강화 학습 알고리즘들은 GPI를 개념적으로 차용하지만 DP를 사용하지는 않는다. 왜냐하면, DP의 단점들 때문이다.

Disadvantages of dynamic programming

DP는 High computational cost가 발생한다. 왜냐하면, 매 Iteration 에서 우리는 모든 states를 update 해야한다. 따라서, Complexity가 states의 수에 따라서 기하급수적으로 증가한다. 그런데, 현실세계의 control problems는 매우 광범위한 범위의 states를 가지고 있다.

 

또한, 대부분의 Contral tasks에서 우리는 perfect model of the environment with all state transitions를 가지고있지 않다. 하지만 이러한 DP의 단점들에도 우리가 DP를 공부하는 이유는 더 나은 알고리즘을 고안하기 위한 전략인 GPI 때문이다.