[강화학습] 10. Eligibility Traces

Eligibility Traces

value function을 approximate 하기 위한 방법을 전 포스팅에서 다루면서, approximator는 s, w의 함수로 표현되며, weight w는 MSVE를 최소화 하기 위한 gradient descent 알고리즘을 적용해 update된다는 것을 배웠었다.

이번시간에는 이 weight를 update하는 또 다른 방법으로 Eligibility traces를 소개한다.

MC backup 에서 value-function을 evaluation하기 위해 위와 같이 error항인 Gt-V(St) 을 구해야 했었고, 1개 샘플을 취한 뒤 episode의 끝까지 간다는 것을 배웠다. 그러다 보니 episode의 끝을 기다려야 한다는 단점이 있었고,

이 단점을 보완하기 위해 바로 1-step 뒤에 value function을 update할 수 있는 TD(0)가 고안되었다. 

하지만 TD(0) 역시 1-step만 봤더니 bias가 높다는 단점이 있어서 n-step 까지 고려하는 n-step TD를 배웠었다. 이번 포스팅에서 다룰 것은 TD와 MC를 결합한 또 다른 approach이다.

TD(λ) : Eligibility traces

Eligibility trace TD(λ)는 Tabular problem에서 잘 동작했던 TD(0)와 MC method를 continuous space에서도 사용하기 위해 두 알고리즘을 ensemble 시킨 알고리즘이라고 할 수 있다.

The λ-return

TD(λ)에도 역시 return의 개념을 정의해야한다. 먼저 n-step return에 대해서 다시 상기해보자.

n-step return은 tabular method를 target으로 하는 유효한 update 방법이다.

그럼 절반은 2-step, 절반은 4-step return을 사용할 순 없을까? 위와 같은 average simpler update를 compound update라 한다.  그리고 이 개념을 실제 적용할 수 있다로록 일반화한 것이 λ-return의 개념이다.

λ-return은 n-step return에 weight를 주고, weight의 합이 1이 될 수 있게 (1-λ)를 앞에 multiply 해 준 형태를 가진다.

위 식에 따르면 멀리 떨어진 step의 return 가중치는 급격히 낮아짐을 알 수 있다. 마치 MC에서의 discounted reward와 유사하게 동작한다.

TD(λ)의 backup diagram을 잘 보면 λ=0일 때 one-step TD update와 동일하게 동작하고,

λ=1일 때 MC update와 같이 동작함을 확인할 수 있다.

Off-line λ-return algorithm

지난 포스팅에 continuous state space에서 value-function을 approximate 하는 방법을 배웟었는데, 그 방법과 λ-return 을 continuous space에 적용한 첫번째 leaning 알고리즘이 바로 off-line λ-return algorithm이다.

위 식은 off-line λ-return algorithm의 weight update rule이다. 위 식을 잘 보면 Gt가 w에 dependent함에도 불구하고 gradient에는 반영되지 않음으로 off-line λ-return algorithm은 semi-gradient method라고 할 수 있다.

위 예제를 보면, n을 조절해서 모델을 튜닝하는 n-step TD와 달리,

Off-line λ-return algorithm은 λ에 따라 모델의 성능이 달라짐을 확인할 수 있다. 

그리고 λ=0일 때의 결과와 n=1일때의 결과가 유사한점도 역시 관측된다.

이렇게 미래에 있을 eligibility traces에 compound update를 적용한 것이 eligibility trace의 forward approach라 한다.

Semi-gradient TD(λ)

반면 eligibility trace z를 과거의 시점부터 현재까지의 가치로 표현하는 방법도 있다.

이 때 eligibility trace는 t-1시점의 eligibility trace에 approximator의 gradient만큼 update되기 때문에, t시점의 eligibility trace는 과거의 value gradient 정보를 기억(trace)한다고 표현할 수 있다. 그리고 이 원리로 weight를 update하는 것이 바로 Semi-gradient TD(λ) 알고리즘이다.

이렇게 forward approach와 달리 과거에 있었던 eligibility traces에 compound update를 적용한 것이 eligibility trace의 backward approach라 한다.

SARSA(λ)

state-value function estimate에 eligibility trace개념을 사용할 수 있다면, action-value function estimate에도 위와 같이 동일하게 사용할 수 있다.