[강화학습 #04] Monte-Carlo and Temporal-Difference

Model-Free Reinforcement Learning

기존의 MDP는 모델 기반이라 환경에 적합한 모델을 정확히 알고 있어야 하는데, 이는 복잡한 환경에서는 현실적으로 어려울 수 있다. 따라서 환경에 대한 정보 없이도 학습이 가능한 Model-Free RL이 존재하는데, 이번 단원에서 Model-Free RL의 대표적인 방식인 MC와 TD를 알아볼 것이다.

 

Monte-Carlo

Monte-Carlo(MC) : 에피소드가 진행되는 동안 발생한 reward들을 Gt에 저장했다가 에피소드가 종료되면 Gt값으로 평균을 계산해서 한번에 V(s)를 업데이트한다. 그래서 에피소드가 종료 시점이 존재하는 완전한 에피소드에서만 사용 가능하다. 이로 인해 에피소드가 끝날때까지 기다려야 한다는 단점이 존재한다.

• N(St) : 방문한 state의 총 수
• Gt : 에피소드에서 얻은 총 리턴(reward)값 : 이 Gt값을 정하는 방법은 2가지가 존재한다.
  • First-Visit MC : 각 s의 최초 방문 시의 reward만을 Gt에 기록
  • Every-Visit MC : 각 s를 방문할 때마다 reward를 Gt에 기록

Temporal Difference

 

Temporal-Difference Learning(TD) : 에피소드가 끝나지 않아도 중간중간 value 업데이트 가능하다. 그래서 MC의 Gt와 달리 다음 state로 이동 시 발생하는 state value를 예측하여 업데이트한다. 이러한 특징으로 TD는 종료 시점이 없는 에피소드에서도 사용 가능하며, 모델을 조금씩 업데이트하여 학습 속도가 빠르다.

• α : Learning rate (0 < α <= 1), 클수록 학습 속도가 빠르지만 불안정
• TD target : state value를 업데이트 하기 위한 목표값 = 다음 t+1시점에서 예상되는 state value값
• TD error : TD target과 현재 state value사이의 오차값

MC는 Gt의 평균을 기반으로 학습하는데 에피소드마다 Gt값이 매우 다를 수 있기에 Variance가 높아 과적합이 날 수 있지만, 충분한 에피소드가 주어진 상황에서의 MC 예측값과 실제 값 차이가 거의 없어 Bias가 매우 낮다.

 

반대로 TD는 각 단계에서 state value를 계속 업데이트해서 안정적이므로 Variance가 낮지만, 이 업데이트가 추정치에 기반하기에 약간의 Bias가 존재할 수 있다.

Bias는 모델의 예측값과 실제 값의 차이로 높을수록 underfitting이고, Variance는 training dataset에 의해 모델의 예측값이 변동하는 정도로 높을수록 overfitting을 나타낸다. 

---

Model-Free RL Performance

Model-free RL은 에피소드를 많이 돌릴수록 true values에 가까워지는걸 볼 수 있다.

위 그래프는 학습률에 따른 MC와 TD의 실제값과 예측값의 차이를 보여주는 그래프인데, 전체적으로 TD가 다양한 학습률에서도 오차가 확실히 줄어드는 모습을 보여 MC보다 좋은 성능을 보였음을 알 수 있다.