Temporal Difference Learning

** policy가 정해진상태에서 V, Q 구하는 것 = prediction

** policy를 정하는 것 = control

 

1. Temporal Difference Learning - TD Prediction

 

Monte Carlo method의 단점

episode가 너무 길거나, 끝나지 않는 episode이면(continuous tasks)

return값을 계산할 수 없으므로 temporal difference learning을 사용함

 

 

Monte Carlo method의 장점

현실은 dynamic programming을 쓸 수 없는 경우가 많다(model-free method 필요)

Dynamic programming의 장점

bootstrapping을 사용하여 episode가 끝날때까지 기다리지 않아도 V(s)를 구할 수 있음

Temporal Difference Learning 

DP와 MC를 결합하여 사용하는 것

MC = Monte Carlo

DP =  Dynamic Programming

참고 ) Dynamic Programming

bootstrapping: 다음 state의 가치를 이용해서 내 state의 가치를 계산하는 것

MC와 TD비교

MC에서는 retrun값을 구하기 위해 끝까지 episode를 진행해봐야 하지만

TD는 return값을 추정(DP의 bootstrap)하여 사용할 수 있음

(추정한 return값을 사용하므로, TD가 MC보다 덜 정확함)

** 참고로 incremental mean을 사용함

TD수식에서의 용어정리

TD prediction 알고리즘 예시

주어진 오른쪽의 policy에 따라

alpha가 0.1, gamma가 1 이라고할 때 value table은 아래와 같이 update 됨 

위의 값 계산하는거 스스로 할 수 있어야 함!!

2. Temporal Difference Learning - TD Control

•  On-policy TD control - SARSA 

– The agent behaves using one policy and tries to improve the same policy. 

• Off-policy TD control - Q-learning 

– The agent behaves using one policy and tries to improve a different policy.

On-Policy TD Control: SARSA 

SARSA: "State-Action-Reward-State-Action" 

SARSA예시

위와 같이 Q table이 random하게 주어졌을 때,

 

((4,2), right)를 update하기 위해서는 그 다음 단계의 (4,3) 단계에서 취한 action값을 가지고

update할 수 있음 (이게 Q-learning과의 차이임)

 

즉, next state에서 next action을 고르고 시작함( epsilon-greedy policy에 의해서)

 

 

아래 코드에서도 보다시피, 그냥 s와 a로 덮어 씌우는게 아니라,

new_s, new_a로 기억하고 있는 것과

new_a를 q table update하기전에 정의함

Off-Policy TD Control: Q-learning

 

SARSA에서는 epsilon-greedy policy로 action을 고르는데,

Q-learning에서는 greedy policy로 action을 selection함 (현재버전 가장 좋은 policy임)

즉, SARSA에서는 해당위치에 selection a’이 존재했으나,

Q-learning에서는 greedy policy로 정하기 때문에 selection a’이 필요 없음

(next state에서의 action은 update하지 않고, max값을 선택해서 나가지만,

현재 Q-table을 update하기 위해서는 현재의 action은

epsilon greedy policy로 이동하기 때문에 Q-table을 업데이트 해 나감)

next state에서만 greedy policy를 취함

 

 

코드에서도 next state에서의 action만 max가 있음

그전의 action은 EPS(epsilon greedy policy에 의해 결정함)

 

 

Summary So Far: DP, MC, and TD 

• Dynamic Programming (DP) 

– methods: value iteration, policy iteration 

– model-based method: need model dynamics 

 

• Monte Carlo (MC) method

– on-policy MC, off-policy MC 

– model-free method 

– applicable to episodic tasks and not to continuous tasks 

 

• Temporal Difference (TD) learning 

– SARSA (on-policy TD), Q-learning (off-policy TD) 

– model-free method 

– uses bootstrapping: applicable to continuous tasks as well as episodic tasks 3

** 실제 현업에서는 on-policy가 좋을 수 있음(minus reward를 받게 되면 risk가 큰 경우 = 실험 비용이 큰경우)