4) Model-Free prediction, control, TD Lambda

이전에 공부한 dynamic programming은 MDP를 안다고 가정한 model based 환경에서의 Planning 문제였다. 하지만 DP는 계산이 복잡하고 model 정보를 모두 알아야 한다는 단점이 있다. 이를 보완한 것이 Learning이고 Learning은 MDP에 대한 정보가 없거나 부족한 model free에서 사용할 수 있다는 장점이 있다. model free에서도 DP와 마찬가지로 prediction(true value function)과 control(optimal policy)이 가능하고 2가지 방법이 있다.

 

 

 

 

 

Prediction

 

 

Monte-Carlo: 실제로 모든 에피소드를 돌면서 나온 값들의 평균을 사용한다. first visit MC는 처음 방문한 state에 대해서만 count, every visit MC는 한 에피소드에서 매 방문마다 모두 count를 한다. 둘 다 모든 state를 방문한다고 가정했을 때 수렴한다.

 

 

Temporal-Difference: TD learns from incomplete episode, by bootstrapping, TD updates a guess towards a guess. 한 스텝 더 가서 예측치로 예측치를 업데이트한다. MC는 현재 return으로 value를 업데이트한다.

 

 

MC: update value toward actural return Gt.

 V(St) = V(St) + α( Gt - V(St) )

 

TD: update value toward estimated return Rt+1 + rV(St+1).

 V(St) = V(St) + α( Rt+1 + rV(St+1) - V(St) )

 

TD target: Rt+1 + rV(St+1)

TD error: Rt+1 + rV(St+1) - V(St)

 

학습의 관점에서 α를 사용하는 이유는 방문 횟수를 추적하는 대신, 속도를 제어하기 위해서이다. 개선 속도를 조절할 수 있게 된다.

 

TD는 final outcome이 나오기 전에 학습 가능하다. MC는 episode가 끝난 뒤에 가능하다.

TD는 non-terminating 한 환경에서 학습 가능하다. MC는 terminating 한 환경에서 가능하다.

MC의 Gt는 unbiased estimate이다. True TD target은 unbiased이지만 TD target은 biased 하다. (무한 번 sampling하지 않기 때문)

TD target은 variance(분산)이 MC return보다 적다. 그 이유는 MC는 한 episode가 끝날 때까지 여러 불확실성을 연속적으로 만나면서 계산하는데, TD는 하나의 step 사이에서의 불확실성만 있기 때문이다. 

 

 

 

 

TD가 MC보다 빨리 수렴하고 bootstrapping이 학습에 더 효율적이다. TD는 MDP에서 효과적이다.

 

 

 

참고:

RL (강화학습) 기초 - 7. Temporal-Difference Learning (tistory.com)

 

 

 

 

 

 

 

 

 

TD Lambda

 

 

TD learning에서 n-step까지 weight를 주어 step을 증가시키며 총합의 평균을 구할 수 있다. 밑에 블로그에 설명이 잘 되어있다. 추가 설명하자면 TD-λ에서 지수 형태의 가중치로 geometric mean을 사용하는데, 이전 것을 저장하지 않고 update와 동시에 평균을 낼 수 있기 때문에 메모리를 사용하지 않고 비용적으로 더 효율적이다. 그래서 TD(0)와 같은 비용으로 TD-λ를 계산할 수 있다.

 

 

RL (강화학습) 기초 - 8. TD lamda (tistory.com)

 

 

위의 블로그 내용을 정리하자면 MC는 episode가 끝난 뒤에 계산을 할 수 있다는 단점이 있기 때문에 TD를 사용했다. 하지만 TD는 bias가 높고 학습 정보가 적다는 단점 때문에 TD와 MC의 장점을 둘 다 살리기 위한 방법으로 n-step TD를 사용했다. 하지만 n-step이 클 때와 작을 때 각기 다른 장점이 있기 때문에 TD-lambda를 사용한 forward-view TD를 사용했다. 하지만 이 방식도 MC와 마찬가지로 episode가 끝난 뒤에 update를 할 수 있기 때문에 backward-view TD를 사용할 수 있다.

 

 

forward view TD는 episode가 끝나야만 학습이 가능하다. 반면 online으로 학습 가능한 backward view TD도 가능하다. backward view는 eligibility traces를 사용한다. 가장 최근에 방문했던 state와 빈도수로 책임 사유를 묻는 방식이다. state를 방문할 때마다 1을 더해주고 r를 곱해서 감책 시켜준다. 그리고 업데이트를 할 때는 TD error에 α를 곱해서 더한다.

 

 

Eligibility Traces · Fundamental of Reinforcement Learning (gitbooks.io)

 

 

 

 

 

Control

 

on-policy는 실제로 경험하고 학습하고, off-policy는 다른 경험을 보고 학습한다. OnPolicy에는 TD와 MC control이 있고 action하는 policy와 improvement하는 policy가 같다. OffPolicy에는 QLearning이 있고 action하는 policy와 improvement하는 policy가 다르다. (behavior policy와 target policy이 서로 다르지만 update를 할 수 있는 이유는 importance sampling 때문이다. 아래 링크 참고) Q learning을 사용하는 이유 중 하나는 exploration을 해도 optimal policy에 수렴할 수 있기 때문이다.

 

 

 

off-policy, sarsa vs q learning:

[Ch.7] Off-Policy Control (tistory.com)

 

 

 

1. On-Policy Learning

 

 

  MC control

 

evaluation: conrol에서 일반적인 MC로 evalutation 할 수 없다. 그 이유는 다음 state transition을 모르기 때문이다. 따라서 true value를 찾는 대신 argmax Q를 이용하면 MC로도 evaluation할 수 있고 improvement까지 할 수 있다.

 

improvement: improvement에서 greedy하게 하면 한계가 있다. optimal policy를 찾지 못할 수 있다. 그래서 e greedy exploration을 한다.

 

 

 

  TD control

 

evaluation: MC대신 TD를 사용할 수 있다. 알고리즘 이름은 'Sarsa'라 하고 관계식은

 

Q(S , A) = Q(S , A) + α( R + rQ(S' , A') - Q(S , A) )

R + rQ(S' , A') - Q(S , A): TD-error

 

improvement: e greedy policy improvement. every time step마다 evaluation과 improvement를 한다.

 

 

Sarsa:

[Ch.6] Temporal Difference Methods (tistory.com)

 

 

 

 

 

 

2. Off-Policy Learning

 

 

 

importance sampling을 MC와 TD에 적용하여 Off-Policy Learning을 할 수 있다. 하지만 현실의 문제에는 쓰기 힘들기 때문에 Q-Learning을 사용하면 off policy를 할 수 있다.

 

 

e-greedy, stochastic in Q-learning:

2020/08/07 - [공부/강화학습] - Q-learning exploit & exploration and discounted reward, stochastic(non-deterministic) world