강화학습 학습하기 - [6] n step TD

6편 - n-step TD methods

"강화학습 학습하기"시리즈는 KAIST 신하용 교수님의 수업 IE540 "DP and RL"수업 내용을 제가 제 방식대로 요약 및 정리한 것입니다. 퍼가실때는 미리 물어봐주시고, 내용은 제가 변형하고 추가하되 렉쳐노트에 쓰인 그림은 사용해도 된다고 교수님께 허락 받았습니다. 

0. Previously on..

저번에 배운 MC,TD methods 중 우린 TD methods에 대한 것을 더 배울 예정이다. 여전히 value based RL이다. 이번 시간은 N-step TD methods 혹은 N-step bootstrapping이다. 1-step TD는 현재상태의 값을 업데이트 하기 위해서 바로 다음 상태의 값을 사용했다. 만약 2-step이라면 현재상태의 값을 업데이트하기 위해서 바로 다음 상태와 그 다음 상태까지의 값을 사용한다. 즉, 오늘의 날씨를 업데이트를 하기 위해서 내일과 내일모레의 정보를 이용하는 것이다. 

1. N-step TD

n-step TD를 위해서 우린 n-step return을 정의한다. 현재 reward와 n번째 더 진행한 후까지의 모든 reward의 discounted reward와 n-step으로 건너갔을때의 상태함수를 n-step return이다. 만약 n이 1이라면 기존에 배웠던 1-step return과 같다. n-step TD의 target은 n-step을 겪고 난 후의 return인 것이다. 만약 n이 무한대, 즉 terminal state를 지났다면, MC method와 같음을 알 수 있다. 

우리가 저번에 TD(0)와 MC를 비교한 예제를 확장한 random walk이다. state의 갯수가 늘었다. 이 것을 

결과로 뽑으면 이런 결과가 나온다. n-step TD를 사용하면서 n을 값을 정하는 것은 매우 중요하다. n이 커지면, MC와 비슷해지는 것이므로 variance가 커지고, bias는 작아지는 한편, n이 작아지면 variance는 작아지지만, bias는 커진다. 결과를 보면 n이 무조건 작은 것도 큰 것도 좋다고 볼 수 없고, learning rate에 따라서도 달라진다. 즉 우린 문제에 따라서 다른 n-step과 learning rate를 적절히 최적화해서 사용함을 알 수 있다. 이 경우는 n=4, learning rate가 약 0.4인 것이 가장 정확하다. n-step이 커지면 생각해봐야할 것이 the only meaningful information은 terminal state에 닿았을때 들어온다는 것이다. 예를 들어 random walk의 오른쪽 terminals state에 닿았다고 생각해보자. 이때 n이 1이라면 V(19)만이 업데이트될 것이다. 우린 다음 스텝만 고려하기 때문이다. 그리고 이때 2-step TD를 사용했다면, V(19)와 V(18)까지 업데이트 될 것이다. 적절한 n을 고르기가 어려운 것을 알 수 있다. 그렇다면 우린 매번 다른 n을 가지고 tuning해야하는 것일까? 이러한 질문에 해결하기 위해서 λ-return이 생긴 것이다. 

2. λ - return

n이 무한대라면 terminal state에 닿으면 지나온 모든 상태를 update할 수 있지만, 변동성도 크고, terminal state에 닿아야만 한다는 문제점이 있다. 그리고 n이 1이라면 이러한 문제점은 없지만, terminal state에 닿으면 그 전 상태만 update되기 때문에 정보 흐름이 굉장히 느리다는 것을 알 수 있다. 그 중간 적절한 n을 찾아야만 하는데 이건 사실 쉽지 않다. 그래서 생겨난 것이 λ-return이다. 모든 것을 고려하되 적절한게 decay하여 가중치를 다르게 두는 것이다. 

λ-return을 자세히 보면, exponential decay하는 가중치 w_n이 있고, 그 곱으로 앞에서 정의한 n-step return이 있다. 합치면 λ-return이란 exponentially weighted average of n-step returns이다. 현재 시점에서의 얻을 수 있는 1-step return과 2-step return 그리고 나아가서 n-step return의 적절한 가중치를 곱해서 평균을 낸 것이다. 

Continuing task처럼 무한히 진행하는 task에도 적용할 수 있고, episodic task의 경우는 terminate되기 전과 된 후로 나눠서 기술할 수 있다. TD(λ)라고도 기술하는데 λ가 0인 경우는 우리가 잘 아는 1-step TD method, 1인 경우는 MC이다. 

3. Forward view and Backward view of λ - return

3-1. Forward view of λ - return

Forward view란 앞으로 나아가는 관점이라는 뜻이고, 이는 이 그림으로 쉽게 알 수 있다. 현재 시각 t에서 앞으로 시간동안 어떤 오류들(G^(λ)_t - V(S_t))이 생기고 이것들을 기다렸다가 모아서 업데이트하면 된다. 

앞을 바라보면서 λ-return을 구한다. 끝나길 기다렸다가 한번에 update한다.

Forward view의 문제점은 MC의 문제점처럼 terminal state에 도달하기 전까지는 trajectory(=episode)에 있는 state들이 update를 못한다. 즉, information flow가 느리게 전파된다. 그래서 효과적인 적용이 매우 어렵다. TD target에서 현재값을 빼준 것이 TD error라고 하듯이 λ-error는 다음과 같다. 

 λ return이 n-step return들의 exponential decaying average인 것처럼, λ -error도 1-step TD error들의 exponential decaying(not only λ, but λ*discount factor) average이다. 이 특성을 우린 backward view에서 계산할 것이다. 

3-2.Switching from forward view to backward view

이 부분이 이번 6편에서 가장 중요한 부분이다. n-step TD는 n을 고르기 모호하다는 점에서 문제가 생겼다. n이 크면 변동성이 커지고 n이 작으면 information flow가 느리게 흐른다. 그래서 이걸 해결하기 위해서 현재시각에서 끝날때까지의 return을 가중치로 계산하는 λ return을 고안했다. 하지만 여기서 문제가 해결된 것이 아니라, 이걸 이용해도 forward view로 계산하면 MC처럼 에피소드가 끝날때까지 상태들이 업데이트하지 못한다. 이 문제를 해결하기 위해 TD(λ)의 target(G^(λ)_t)와 현재 상태값의 차이인 TD λ error를 분석했다. 분석결과로 TD(λ) error는 1-step TD error들을 잘 exponential decaying하면 구해진다는 것을 알았다. 이 사실을 가지고 이제 매 step마다 update하는 backward view를 알아보겠다. 

Forward view(up,green) and Backward view(down,purple)

위쪽을 보면 Forward view임을 알 수 있다. 현재 상태에서 다음에 생기는 td error와 다음상태와 다음 다음 상태에서 생기는 td error들이(이는 terminal state에 도달할때까지 계속 계산된다.) 가중치(λ*gamma)를 가지고 한꺼번에 learning rate를 곱한 후에 현재 상태로 업데이트된다. 앞서 말했듯이 이렇게 update를 하면 terminal state에 도달할때까지 기다렸다가 업데이트가 되기때문에 converge하기 어렵고, 비효율적이다. 

이를 해결한 것이 앞서 말했던 Backward view(purple, down)이다. 오류가 생기자마자 바로 업데이트하는 것이다. 만약 현재 상태와 그 다음상태가 오류가 생기면 그건 바로 현재상태에 영향을 주고, 만약 다음상태와 다음 다음 상태가 오류가 생겨도 이에 대한 적절한 가중치(또는 책임감)을 가지고 현재 상태값을 update한다.

즉 모든 스텝마다 update하기 때문에, incomplete task에도 사용할 수 있다. 만약 즉각 업데이트한다면 asynchronous backup이고 상태 함수를 2 set로 나눠서 하나는 update하고 하나는 update하지말고 진행한다면 synchronous backup이다. 일반적으로 async backup이 더 online performance가 좋다. 

3-3.Backward view of TD(λ)

모든 step마다 1-step TD error는 발생할 것이다. 지나온 경로마다 계산된 1 - step TD error를 통해 V값을 update한다. 만약 state space가 크고 에피소드(trajectory)가 짧을 수록 좋다. 이유는 중복되는 state 조합이 되도록 없고, 에피소드가 짧을 수록 reward decay이 적어서 더 적절하게 update한다. 

여기서 eligibility trace라는 용어가 나온다. 이 용어는 중요하다. Eligibility란 영어로 responsibility와 비슷한 뜻으로 발생하는 1-step TD 오차에 대해서 얼마나 책임이 있냐 라는 의미이다. 만약 내가 오늘 어떤 결정을 내렸는데, 어제 상태랑 한달 전 상태 중 어떤 것이 더 책임이 크냐라고 생각하면 직관적으로 어제 상태가 한달 전 상태보다 오늘의 결정에 "책임"이 있다. TD(λ)도 똑같다. 에피소드에 있는 현재 state에서 다른 state로 transition될 때 이전에 지났던 state의 책임은 λ*discount factor로 점점 작아진다. 

오류가 발생하면 즉각 책임여부를 가리고 바로 상태 값을 update한다. 발생한 오류와 가까우면 크게 update하고 발생한 오류와 멀면 작게 update한다. 

현재 시각에 일어난 것을 과거의 상태에 대해서 추궁하는 것이다. 

Policy evaluatoin of TD (λ)

E(s)>0인 state, 다른 말로 하면 지나온 state들만 update하고 책임여부를 줄여준다. 이때 밑에 보이는 그림처럼 Eligibility를 update하는 세 가지 방법(accumulating trace, replacing trace, dutch trace)이 있다. 첫 번째는 MC method의 every visit처럼 계속 방문할 때 마다 1을 더하는 것이다. 두 번째 방법은 MC method의 first visit처럼 최댓값은 1로 하고 계산하는 것이다. 세 번째 방법은 앞선 두 가지 방법의 절충방법이다.  

4. λ- Control (SARSA(λ), Q-Learning (λ))

1. SARSA(λ)

You can check e-greedy policy.

위에 보이는 알고리즘을 그대로 적용하면, 밑의 그림과 같은 결과가 나온다. 이때 S3,A3와 S0,A0는 같다고 정의했다. 

2. Q-Learning (λ)

Q-learning은 off-policy이고,현재 상태에 대해서 eps-greedy action을 하고 다음상태에서 최대값을 주는 action을 취하는 방식이다. 노란색으로 강조한 부분처럼 max함수를 사용한 것을 알 수 있고, 이렇게 생긴 1-step TD error를 책임 여부를 묻는 eligibility trace를 이용해서 update한다. 

결과는 다음과 같다. 

문제는 여기서 현재 상태에서 non-greedy action을 한 것에 대해서 이전 상태들이 책임을 져야하는 문제이다. S2까지는 문제 없었으나, t=2인 A2에서 non-greedy action을 했다. 그리고 이 것에 대해서 이제 exploration을 할 텐데, exploration을 하는 것까지 이전 상태들이 책임이 있는가에 대한 우려가 생긴다. Naive Q-Learning (λ)은 그래도 책임이 있지 않을까 하는 관점이고 뒤에 나올 Watkins's Q-Learning (λ)은 책임이 없는 관점이다. 뭐가 맞는지에 대해서 정확한 증명은 없지만 개인적으로는 non-greedy action을 한 순간부터는 이전 상태가 어떠한 책임이 없다고 생각한다. 어떠한 랜덤성이기 때문이다. 

그래서 Watkins's Q-Learning (λ)은 미리 다음 상태에 대한 action을 선정하고, 이 선정한 값이 greedy action과 다르고 Q값마저 다르다면, 이전 상태들에 대한 책임은 0으로 update한다. 

일명, break the chain이 되는 것이다. 이전 상태들에 대해서 연결고리가 해제된다. 

5. Information Flow and Windy gridworld and No-wind gridworld

1. Windy gridworld

밑에서 위쪽으로 바람이 지나가기때문에 검은색 원에 해당되는 state에서 밑으로 가는 action을 하면 그대로 그 자리에 멈춘다. eps-greedy SARSA를 사용했고, 그래프의 y축은 terminal state, 여기서는 Goal에 해당되는 부분까지 도달할때까지 걸린 에피소드이다. 즉 2000 time step정도 되어야 한 에피소드가 끝난 것을 알 수 있다. 8천 steps정도 지나면, 평균 17 step을 지나면 episode에 도달함을 알 수 있다. 여기서 검은색 원 예제를 든 것은 MC method때문이다. MC 방법은 무조건 episode가 끝나야지 update를 하는데, 이는 만약 검은색 원에 들어가고 down action을 선택하면 계속 그자리에 머물기 때문에 episode가 끝나지 않게 된다. 

2. No-wind gridworld

SARSA(λ)은 information flow가 빠르기 때문에, terminal state에 도달하면 천천히 update한다.