강화학습 Sutton [Ch4 Dynamic Programming] #7 Effciency of Dynamic Programming
Effciency of Dynamic Programming DP는 큰 문제에서는 실용적이지 않더라도 다른 방법에 비해서는 꽤 효율적이다. 다항식을 통해 직접 최적의 정책을 구하는 것보다 빠르기 때문이다. 그럼에도 불구하고 두 방법 모두 최적의 정책을 찾아낸다. Linear programming의 경우도 사용될 수 있으며, 어떤 경우에는 DP보다 최악의 경우에 수렴에 대한 보장이 더 잘된다. 하지만 더 작은 상태를 가진 경우에 쓰이기 때문에 DP보다 실용적이지 않다. 그럼에도 불구하고 DP가 쓰이기 어려운건 차원의 저주(curse of dimensionality) 때문이다. 상태의 수가 늘어나면 상태에 대한 변수들 수도 기하급수적으로 증가한다. 하지만 이건 DP가 아닌 문제 자체의 본질적인 문제이다. 다른..
