Search
💪🏻

Temporal Difference

생성일
2024/07/16 06:17
태그
강화학습
작성자

1. Temporal Differnce 개요

Temporal Difference는 model-free인 경우에 tabular updating 방식에 적용되는 방식 중 하나이다. 특히 TD Policy iteration은 sampling 된 episode에서 1-step transition을 기반으로 GPI를 적용한다. TD는 bootstrapping 방식을 사용하여 각 state-action에 대한 value를 다음 state에서 계산한 추정량를 통해 update하며 따라서 MC와 다르게 final outcome이 산출될 때까지 기다릴 필요가 없다.

2. On-policy/Off-policy

Target policy와 behavior policy가 일치하는 것을 On-policy 일치하지 않는 것을 Off-policy라고 한다. 여기서 Target policy란 target에서 action을 선택할 때 쓰이는 policy를 말한다. Target이란 agent가 학습하려고 하는 목표에 해당하는 값이다. 또한 behavior policy는 실제로 agent가 action을 선택할 때 쓰이는 policy를 나타낸다. On-policy에서는 Policy improvement가 진행되고 나면 과거의 데이터를 사용할 수 없으나, Off-policy에서는 가능하다. 예를 들어, SARSA에서 target의 Q를 계산하는데 있어 이전 policy에서 얻은 (S’,A’)(S’, A’)은 현재 policy에서 유효한 값이 아니기 때문에 사용이 불가하다. 그러나 Q-learning에서는 target을 해당 state에서 가능한 action 중 Q-value를 최대로 만드는 값을 고르도록 설정하기 때문에, 현재 policy와 무관하므로 이전에 생성한 값들을 활용할 수 있다. 이처럼 Off-policy에서는 behavior policy와 target policy가 다르기 때문에 exploration이 적용되어 전반적인 optimal을 향해 학습한다. 반면 On policy에서는 suboptimal policy를 학습하게 될 위험이 있다.

3. SARSA

SARSA algorithm은 대표적인 On-policy TD prediction에 사용되는 알고리즘이다.
•
Q value update 과정 해석
Q(S,A)←Q(S,A)+α[R+γQ(S’,A’)−Q(S,A)]Q(S,A) ← Q(S, A) + \alpha [R + \gamma Q(S’, A’) -Q(S,A) ]
→ Q(S,A)Q(S, A) update에 Q(S’,A’)Q(S’ , A’)가 사용되었으므로 bootstrapping
→ 1-step transition인 (S,A,R,S’,A’)(S,A,R,S’,A’) 을 바탕으로 update가 진행되었으므로 TD 방식
→ Target policy와 behavior policy가 Q에 대한 ϵ−greedy\epsilon -greedy policy로 동일하기 때문에 On policy
→ QπQ^\pi를 target으로 하여 학습이 진행되기 때문에 Bellman expectation equation 사용

4. Q-learning

Q-learning algorithm은 대표적인 Off-policy TD prediction에 사용되는 알고리즘이다.
•
Q value update 과정 해석
Q(S,A)←Q(S,A)+α[R+γmax⁡aQ(S’,a)−Q(S,A)]Q(S,A) ← Q(S, A) + \alpha [R + \gamma \displaystyle\max_a Q(S’, a) -Q(S,A) ]
→ Q(S,A)Q(S, A) update에 Q(S’,a)Q(S’ , a)가 사용되었으므로 bootstrapping
→ 1-step transition인 (S,A,R,S′)(S,A,R,S') 을 바탕으로 update가 진행되었으므로 TD 방식
→ Target policy는 Q에 대한 greedygreedy policy이나, behavior policy가 Q에 대한 ϵ−greedy\epsilon -greedy policy로 다르기 때문에 Off policy
→ Q∗Q^*를 target으로 하여 학습이 진행되기 때문에 Bellman optimality equation 사용
→ 직접 Optimal Q-function을 학습하기 때문에 성능이 우수하다.

5. Importance Sampling

MC, SARSA에서 off-policy의 장점을 활용하기 위해 behavior policy를 교체해줄 수 있다. 이때 사용하는 것이 Importance Sampling이다. Importance Sampling은 E[f]E[f]를 추정하기 위해 Sample mean을 사용하고자 하는데, 이때 Sampling 과정이 까다로울 경우 더 쉬운 분포에서 sampling을 진행하고 importance weights를 통해 보정해주는 방식이다. 수식으로 살펴보면 아래와 같다.
이것을 활용하여 on policy 방식을 off policy로 변형 가능하다. SARSA와 MC 모두 behavior policy에서 qπ(s,a)=Eπ[Gt∣St=s,At=a]q_\pi(s,a)=E_\pi[G_t|S_t=s, A_t=a]를 사용한다. 그리고 return은 전체 trajectory의 확률을 따라 추출된다. 이때 behavior policy를 다른 policy로 교체해준다면, GtG_t가 다른 distribution에서 추출되는 것이므로 이때 다른 policy를 μ\mu라고 가정하면, importance weights는 아래와 같이 계산된다.
여기서 p(Sk+1∣Sk,Ak)p(S_{k+1}|S_k, A_k) 항이 약분되므로 transition probability를 모르는 경우에도 weights를 구할 수 있고 weights를 구할 수 있다는 것은 policy의 교체가 model-free에서 가능하다는 것이므로 off policy의 장점을 on policy의 behavior policy 교체를 통해 활용할 수 있음을 의미한다. 따라서 MC와 SARSA에 이를 적용하면 아래와 같다.
Importance sampling을 적용했다고 가정하면, MC에서는 behavior policy μ\mu에 의하여 experience를 쌓고 그것을 바탕으로 GtG_t를 계산하기 때문에 GtG_t에 weights를 곱해주어야 하며, TD에서는 1-step transition에서 behavior policy μ\mu를 사용하기 때문에 target에 weights를 곱해주어서 π\pi에 대한 수치로 보정해주어야 한다.
결과적으로 MC와 TD (SARSA)에서 모두 Off policy를 이용할 수 있다. 그러나 MC에서는 target의variance가 증가되어 (확률값이 계속 곱해지므로) 수렴 속도가 느려질 수 있다. 반면 TD에서는 MC에 비해 variance의 증가가 적은 편이다.

6. Bias vs Variance

•
Bias
추정량들의 평균이 실제 값으로부터 얼마나 떨어져 있는지를 나타내는 것으로 작을수록 수렴이 빠르다.
⇒ MC에서 Target으로 사용하는 Return은 qπ(St,At)q_\pi(S_t, A_t)의 불편추정량이다.
⇒ TD target은 Rt+1+γQ(St+1,At+1)R_{t+1}+\gamma Q(S_{t+1}, A_{t+1})을 사용하므로 biased estimate이다.
(Q(St+1,At+1)Q(S_{t+1}, A_{t+1}) 대신에 qπ(St+1,At+1)q_\pi (S_{t+1}, A_{t+1})을 사용하면 불편 추정량)
•
Variance
추정량의 기댓값이 그들의 중심으로부터 퍼져있는 정도를 나타내며 작을수록 수렴 속도가 빠르다.
⇒ TD target은 MC의 return과 비교했을 때 variance가 낮은데, 이는 Return이 많은 random 과정에 의해 결정되기 때문이다.
따라서 MC는 Variance가 높고 TD는 bias가 높다.

7. MC, TD 정리

MC와 TD 둘 다 Model free 상황에서 sample을 기반으로 직접 학습하는 방식이다. MC는 Return을 target으로 사용하기 때문에, episode의 마지막까지 기다려야 하며 반드시 종료되는 환경에서만 사용 가능하다. 그러나 Markov property에 대해 적은 영향을 받기 때문에 non-markov environments에서 효과적이다. 또한 MC는 어차피 종료 상태까지 진행하고 update하기 때문에 초기값에 강건하며 Return이 불편추정량이므로 bias가 낮다. TD는 최종 결과까지 기다리지 않고 update하기 때문에 메모리 사용 측면에서 효율적이고, continuning environmet에서도 잘 작동한다. 그러나 Markov property 가정에서 자유롭지 못하고, 초기값에 민감하다. 그리고 불편추정량을 target으로 사용하지 않기 때문에 bais가 높다. 반면 variance는 MC에 비해 낮은 편이다.

8. Expected SARSA

기존의 SARSA에서 next action을 선택할 때 Q에 대한 ϵ−greedy\epsilon -greedy 방식을 사용했다면, Expected SARSA에서는 이 확률값들을 사용하여 action에 대한 기댓값을 적용한 target을 사용한다.

9. Double Q-learning

Q-learning에서는 target에 maximization operation이 포함되어 있기 때문에, 초기 단계에서 Q-value에 대한 overestimate가 발생하는 문제가 있다. 이것은 수렴 속도를 느리게 하는 문제가 있기 때문에, 두개의 Q-function을 사용하여 문제를 해결한다. 하나의 Q-table은 target을 위한 Q-table이고 다른 하나는 maximization operation을 위한 Q-table이 된다.

10. TD(λ\lambda)

n-step return이란, 현재 time step t에서 n-step만큼 진행하여 reward를 받고 n-step 이후에는 state value를 적용하여 return을 계산하는 방식이다. 이때 이 n-step return을 target으로 사용하여 TD를 적용하는 것이 TD(n)이 된다. 그리고 여기에서 n-step return 여러개를 가중 평균 방식으로 합하여 Target으로 적용한 TD(λ\lambda) 방식으로의 변형이 가능하며, 이와 같이 적용하게 되면 어떤 return 값을 더 중요하게 판단할 것인지에 대한 정보를 λ\lambda의 조정을 통해 추가할 수 있어 유용하다.
→ TD(1)인 경우 Return으로 취급하여 MC 방식이 된다.

11. Examples

•
AB example
•
Answer
결과적으로 TD가 아직 생성되지 않은 future data까지 고려한다면 더 나은 성능을 보인다고 볼 수 있다. 왜냐하면 새로운 data를 더 생성한다면 75%의 비율만큼 reward를 1을 받는 data가 생성될 것이기 때문이다. 반면 MC는 기존에 존재하는 data에 충실한 답을 제공한다.
•
Cliff working
이 경우 Q-learning이 SARSA에 비해 성능이 낮게 나온다. 왜냐하면 SARSA의 경우 Target Policy와 behavior policy가 모두 Q에 대해 ϵ−greedy\epsilon -greedy policy이기 때문에, Cliff 근처에서 ϵ\epsilon만큼의 확률로 cliff로 빠지게 될 가능성을 고려하므로 항상 Q value를 Maximization 하는 방향으로 학습하는 Q-learning에 비해 안전한 경로를 선택하게 되고, 따라서 성능이 SARSA가 Q-learning이 ϵ\epsilon만큼 cliff에 빠지는 수치만큼 우수해진다.