[Reinforcement Learning] The Limits of Dynamic Programming

1. 계산 복잡도

DP를 적용하는 문제의 규모가 거대하다면 계산만으로 풀어내기에는 한계가 있다.

DP의 계산 복잡도는 State 크기의 3제곱에 비례한다.

따라서 DP로는 경우의 수가 우주의 원자 수보다 많은 바둑과 같은 문제는 절대 풀 수 없다.

 

2. 차원의 저주

State가 2차원으로 표현되는 (x, y)가 아닌 n차원이라면, State의 수가 지수적으로 증가한다.

계산 복잡도가 증가하므로 해결할 수 없다.

 

3. Environment에 대한 완벽한 정보

Reward와 State 변환 확률을 정확히 알고 해결할 수 있는 문제는 거진 없다.

 

따라서 Environment를 모르지만 Env와의 상호작용을 통해

경험을 바탕으로 학습하는 방법이 강화학습이다.

 

RL과 DP의 차이는 RL은 Env의 Model을 몰라도 Env와의 상호작용을 통해 Optimal Policy를 학습한다는 것이다.

Agent는 Env와의 상호작용을 통해 주어진 Policy에 대한 Value Function을 학습할 수 있는데, 이를 Prediction이라고 한다.

또한, Value Function을 토대로 Policy를 끊임없이 Develop하여 Optimal Policy를 학습하려는 것이 Control이다.

 

------------------------------------------------------------------------------------------

REINFORCE Algorithm

REINFORCE Algorithm은 일종의 Monte Carlo Policy Gradient로서 Episode마다만 학습할 수 있다는 단점이 있다.

또한 Episode의 길이가 길어지면 길어질수록 특정 상태(s, a)에 대한 반환값의 변화가 커져 분산이 큰 경향이 있다. 이는 학습을 느리게 만든다.

이 단점을 극복하고 매 time step마다 학습할 수 있도록 한 것이 Actor-Critic이다.