강화학습 Sutton [Ch4 Dynamic Programming] #7 Effciency of Dynamic Programming

Effciency of Dynamic Programming

DP는 큰 문제에서는 실용적이지 않더라도 다른 방법에 비해서는 꽤 효율적이다. 다항식을 통해 직접 최적의 정책을 구하는 것보다 빠르기 때문이다. 그럼에도 불구하고 두 방법 모두 최적의 정책을 찾아낸다. Linear programming의 경우도 사용될 수 있으며, 어떤 경우에는 DP보다 최악의 경우에 수렴에 대한 보장이 더 잘된다. 하지만 더 작은 상태를 가진 경우에 쓰이기 때문에 DP보다 실용적이지 않다.

그럼에도 불구하고 DP가 쓰이기 어려운건 차원의 저주(curse of dimensionality) 때문이다. 상태의 수가 늘어나면 상태에 대한 변수들 수도 기하급수적으로 증가한다. 하지만 이건 DP가 아닌 문제 자체의 본질적인 문제이다. 다른 방법(direct search, linear programming)보다 그나마 DP가 나은 것이다.

실제로, DP는 수백만개 상태가 있는 MDP 문제를 푸는데 사용된다. 이론에서의 최악의 경우 실행 시간보다 빠르게 수렴하는게 보통이고, 좋은 초기 가치함수와 정책이라면 더더욱 그렇다. 가끔 상태가 많은 문제에서는 상대적으로 적은 메모리와 연산이 쓰이는 asynchronous DP 방법이 더 사용되기도 한다.