Dynamic Programming은 강화학습인가? 강화학습과 Model-based / Model-free

※해당 포스팅은 제 네이버 블로그 https://blog.naver.com/gusals1620/222488077108 에서도 확인하실 수 있습니다.

 

 

 

강화학습을 처음 공부할 때 Dynamic programming, TD method 등 다양한 방법론들을 배웠습니다.

 

처음에는 Dynamic Programming도 강화 학습의 한 종류인 것처럼 배웠는데요.

 

대학원에서 연구를 하며 강화학습에 대해 깊이 공부할 수록, Dynamic Programming은 과연 강화학습의 인가?

라는 의문이 들었습니다.

 

흔히 강화학습은 시간 순서에 따라 정의되는 문제인 Markov Decision Process(MDP)를 해결하기 위한 방법(method)이라고 하지만,

 

정확히 말하면 강화학습은 MDP를 해결하기 위한 method들 중 하나라고 하는 것이 좀 더 맞지 않을까 싶습니다.

 

그 외의 방법으로 Dynamic Programming, Tree Search가 있는 것이구요.

 

아래 그림을 보시면 강화학습이라는 category가 어디에 위치하는지 알 수 있습니다.

출처 : 본인

 

 

강화학습이라는 알고리즘은 MDP를 풀기 위한 method인 model-based method, model-free method 중 model-free method에 속하는 것이라 할 수 있습니다.

 

Model-based method는 model을 알고 있기 때문에 최적의 수를 planning(계산)할 수 있습니다.

이리 저리 헤맬 필요 없이 최적의 수를 딱 계산을 해낼 수 있다는 것이죠.

 

Model-free method는 model을 모르기 때문에 이리 저리 헤매며 learning(학습), 즉 강화학습을 통해 최적의 수를 찾습니다.

 

Dynamic Programming은 planning에 해당되므로, Dynamic Programming은 강화학습에 속하는 것이 아닌 별개의 알고리즘이라고 보는 것이 맞을 것 같습니다.

아래 위키피디아 캡쳐를 봐도 강화 학습과 깊은 연관이 있다고 되어 있지, Dynamic Programming이 강화 학습에 속하는 것은 아님을 알 수 있습니다.

출처 : 

 

 

Model을 안다는 것은 무엇일까요?

그것은 학습 주체인 agent가 State Transition Probability(상태 변환 확률)를 안다는 것입니다.

 

상태 변환 확률은 Frozen Lake 예시로 쉽게 이해할 수 있습니다. Frozen Lake는 꽁꽁 얼은 호수를 걸으면서 목적지에 도착하는 게임인데, H (Hole)에 빠지면 게임이 즉시 종료됩니다.

16개의 각 칸은 state를 나타내며, 상하좌우의 움직임이 action에 해당합니다.

 

출처 : 본인

 

 

위 그림의 Start 지점의 agent가 오른쪽으로 움직입니다. 그러면 당연히 오른쪽 칸의 state로 갈 것 같지만..

바람이 불거나 미끄러져서 아래 쪽으로 갈 확률도 있습니다.

이렇게 특정 상태에서 action을 취했을 때 여러 state로 이동할 수 있습니다. 여러 개의 state들 중 각 state로 변할 확률이 바로 상태 변환 확률이 되겠습니다.

 

수식으로는 아래 처럼 나타낼 수 있습니다.

 

 

사진 삭제

사진 설명을 입력하세요.

 

위 예시의 경우는 Start 상태에서 action →를 취했을 때의 상태 변환 확률은

· 오른쪽 state로 갈 확률 = 0.8

· 아래쪽 state로 갈 확률 = 0.2

라 할 수 있습니다.

 

위의 상태 변환 확률을 agent도 알고 있다면, 즉 model을 알고 있다면 이리 저리 헤맬 필요 없이 계산을 통해 최적의 수를 찾는 Model-based method를 적용하는 것입니다.

반면에 상태 변환 확률을 모르면 이리 저리 헤매며 (강화)학습을 통해 최적의 수를 찾는 Model-free method를 적용하는 것입니다.

 

Frozen Lake 게임에서 agent는 상태 변환 확률을 모르기 때문에, 강화학습을 통해 최적의 수를 찾는 Model-free method를 적용합니다. 즉 강화학습을 통해 Frozen Lake 게임의 문제를 해결하는 것이죠.

강화학습을 하는 Model-free method로는 Monte Carlo method, SARSA, Q-learning이 있습니다.

세 알고리즘 중 Q-learning이 가장 성능이 좋아서 Q-learning이 많이 쓰입니다.

 

강화학습과 다른 알고리즘과의 관계에 대한 이론적인 내용이 애매한 것 같아서, 부족하지만 제 의견을 통해 정리를 해보았습니다.

 

다른 분들은 어떻게 생각하시는지 궁금하네요.