Eligibility Trace(ET)는 강화학습에서 아주 기본적인 메커니즘으로 자주 쓰입니다. 예를 들어 \(TD(\lambda)\) 알고리즘의 경우, \(\lambda\)가 ET의 사용을 암시합니다. 그 어떤 TD 방법 - Q-learning이든 Sarsa든 - 도 ET와 함께 사용될 수 있습니다. ET가 TD 방법과 결합하면, 양 극단에 one-step TD와 Monte Carlo 방법을 두는 모델 family로 일반화할 수 있습니다.

물론 이전 챕터들에서 n-step 방법도 마찬가지 일반화를 하지만, ET는 이보다 더 세련된 방법을 제공합니다. z와 w라는 두 가지 벡터를 사용하는데, w는 long-term weight 벡터이고 ET 벡터인 z는 w와 동일한 사이즈로 short-term memory 벡터 역할을 합니다. 대략적인 개념은, w 벡터의 어떤 component가 추정치를 계산하는데 쓰이게 되면, 해당 component에 상응하는 z 벡터의 component의 값이 일시적으로 상승한 후, 다시 옅어지기 시작합니다. 즉, w 벡터 중에서 어느 component들이 최근에 추정치 계산에 쓰였는지를 기억하는 벡터가 z입니다.

ET가 계산에서 우위를 가지는 이유는 n-step method에서는 최근의 n feature 벡터를 저장해야 했지만 ET는 하나의 trace 벡터만 필요로 하기 때문입니다. Learning 면에서도 n-step 방법은 처음 n-1 스텝동안에는 딜레이가 있다가 에피소드가 끝난 후 그만큼 캐치업을 해야하는데, ET는 해당 상태에서 바로 learning이 일어나면서 행동에 영향을 줄 수 있고, 시간축에서 연속적으로(continually) 균일하게(uniformly) learning이 이루어집니다.

이제까지 우리가 본 알고리즘은 어떤 상태의 가치를 계산하는데 있어 그 상태 다음에 올 상태들을 참조로 했고, 이를 forward view라고 합니다. 하지만 이 방식은 구현하기가 조금 까다로운 것이, 현재 시간 t에서 아직 미래 상태와 보상들에 엑세스하는 것이 불가능하기 때문입니다. 이와는 달리 ET는 eligibility trace 벡터를 이용해서 최근에 방문한 상태값들만 보면서 완전히 동일한 업데이트를 할 수 있게 해주며 이를 backward view라고 합니다.

12.1 The \(\lambda\)-return

챕터 7에서 n-step return을 첫 n개의 보상에다 n step에서 도달한 상태의 가치함수의 합으로 계산하는 방법을 알아보았는데, 그 return을 일반화한 식은 아래와 같습니다.

그리고 이 return을 target으로 하여 가치함수를 업데이트하였습니다. 그런데 여기서 중요한 점은, 단순히 하나의 n-step return이 아니라, 여러 개의 n-step return을 평균한 값을 타겟으로 하더라도 1) 각 가중치가 positive하고 2) 가중치의 합이 1인 이상 유효하다는 것입니다. Compound update라고 불리는 이 방식 또한 error reduction property를 충족하기 때문에 수렴이 보장됩니다. \(TD(\lambda)\) 알고리즘은 이렇게 n-step update들의 평균을 취하는 하나의 특정한 방식이라고 할 수 있습니다.

위의 backup 다이어그램에서, 각 열은 순차적인 n값을 갖는 n-step update들이고, 각 열의 가장 아래에 있는 숫자는 해당 열의 가중치인데 \(\lambda\)의 n-1제곱값을 가집니다. 가중치들을 모두 더하면 \(\lambda\)의 등비수열이 되기 때문에 합이 \(\frac{1}{1 - \lambda}\)가 되고, 따라서 가중치의 전체 합을 1로 만들기 위해서 가장 마지막 열 외의 값에 \((1 - \lambda)\)값을 곱해줍니다.

가중치를 곱하는 타겟이 되는 리턴값들은 위에서 언급한 \(G_{t:t+n}\)값이고, terminal state에서는 일반적인 리턴인 \(G_t\)값을 사용합니다. Terminal state를 별도로 표기해서 전체적인 합을 표기하면 아래와 같습니다.

이런 식으로 표기를 하면 \(\lambda\)값이 1일 때와 0일 때 어떻게 되는지 알기 쉽습니다. 1일 경우에는 마지막 항의 \(G_t\)만 남아서 Monte Carlo 알고리즘과 동일해지고, 0일 경우에는 모든 항들이 사라지고 summation 항에서 첫번째 항만 남아 \(G_{t:t+1}\)이 되어 one-step TD가 됩니다.

아래는 위의 개념을 도표로 표현한 것입니다.

이제 \(lambda\)-return을 이용한 첫번째 알고리즘인 off-line \(\lambda\)-return algorithm을 살펴 봅니다. Off-line 알고리즘이므로, 에피소드 도중에는 weight vector w에 대해서 아무런 변화를 주지 않고, 에피소드가 끝난 후 semi-gradient rule을 이용해 \(\lambda\)-return을 타겟으로 삼아 전체 시퀀스의 업데이트를 진행합니다.

(조지아텍 커리큘럼의 특성상 linear approximation보다 12과가 먼저 다뤄져서, semi-gradient method에 관해서는 챕터 9.3을 참조하시기 바랍니다. 일반적인 머신러닝에서의 gradient 방법과 동일한데, bootstrapping으로 인해 true gradient값을 사용하는 것이 아니라서 semi-gradient라는 명칭이 붙었습니다)

위는 이전 챕터 7에서 나온 n-step TD 방법과, 이 off-line \(\lambda\)-return 알고리즘의 성능을 19-state random walk 예제(Example 7.1)로 비교한 도표입니다. 두 알고리즘이 거의 동일한 것을 알 수 있습니다. 이제까지 우리는 forward view를 사용하는 알고리즘들을 알아보았습니다. Forward view란, 현재 상태에서 그 이후의 상태와 보상들을 고려해서 업데이트하는 방식입니다.

12.2 TD(\(\lambda\))

TD(\(\lambda\)) 알고리즘은 강화학습에서 가장 오래되고 많이 사용된 알고리즘 중 하나입니다. TD(\(\lambda\)) 알고리즘은 off-line \(\lambda\)-return 알고리즘을 세 가지면에서 개선합니다. 1) 에피소드의 끝에서만 weight vector를 업데하는 것이 아니라 에피소드의 각 step에서 업데이트를 하고, 2) 계산들이 에피소드의 끝에 집중된 것이 아니라 시간축에서 균일하게 분포되어 있으며, 3) 에피소드로 나뉜(episodic) 문제들 말고 연속적(continuing)인 문제들에서도 적용가능합니다. 여기서는 함수 근사(function approximation)을 사용하는 TD(\(\lambda\))의 semi-gradient 버전을 살펴봅니다.

차근차근 살펴보겠습니다. 조지아텍의 커리큘럼상 아직 function approximation 파트를 공부하기 전에 12과를 읽어서 이해하기가 힘들 수도 있는데, 이전까지 다룬 챕터에서 대부분의 경우에 상태(state) S는 연속 공간(continuous space)이 아닌 이산 공간(discrete space)에 있었습니다. 예를 들어 7 x 7 미로를 푸는 문제의 경우 49개의 각기 단절된 상태(state)들이 있었고, 그에 따라 V(S)값도 49개가 있었습니다. 하지만 어떤 1km의 길 위에 로봇의 위치가 어디있는지가 상태(state)를 나타낸다고 한다면, 위치값은 100m 지점이 될 수도 있고 10m 지점이 될 수도 있고, 10.12312312m 지점이 될 수도 있기 때문에 무한히 많은 상태(state)들이 가능해집니다. 이렇게 연속적인 공간(continuous space)에 존재하는 상태들을 다루는 문제의 경우, V(S) 또한 무한히 많기 때문에, 이를 파라미터 w를 사용하는 함수 V(S, w)로 근사합니다. 이산 공간에서는 알고리즘이 각각의 V(S)값들을 직접 배워나갔지만, 연속 공간에서는 그것이 불가능하기 때문에 파라미터 w를 조정해 나가면서 V(S, w)값이 실제 리턴값에 일치해 나가도록 배워나가는 것입니다.

이제 pseudocode를 살펴보면, 전체적인 loop의 목적은 매 step마다 weight 벡터 w를 업데이트해서, \(\hat{v} (S, w)\)가 S의 실제 가치를 잘 근사하도록 만드는 것입니다.

그러면 어떻게 w를 업데이트하는가를 보면 이전 값에다 \(\alpha\), \(\delta\), z 이렇게 3가지의 곱을 더하는데, \(\alpha\)는 learning rate이고, \(\delta\)는 target인 TD error입니다.

앞의 두 항은 실제 받은 보상에 다음 상태의 v값을 bootstrap한 값이고, 세번째 항은 현재 v값인데, 우리의 목적은 다시 말해 w를 조정해서, 앞의 두항 vs 세번째항의 차이를 0으로 만드는 것입니다.

이제 w 업데이트 식에서 z값이 무엇인지가 남았는데, 이는 weight vector w와 동일한 사이즈의 eligibility trace vector입니다. Weight vector가 알고리즘 전반에 걸쳐 결정되는 장기 메모리라고 하면, eligibility trace vector는 단기 메모리로 일반적으로 한 에피소드보다 짧은 시간동안 작용합니다.

Eligibility trace vector z는 위와 같이 처음에 0으로 초기화된 후, 매 step마다 \(\gamma\lambda\)만큼씩 할인되며, \(\gamma\)는 discount rate, \(\lambda\)는 trace-decay 파라미터라고 합니다.

이 z 벡터는 어떤 역할을 할까요? 위의 그림을 보시면 좌측이 앞에서 다룬 n-step TD가 업데이트를 하는 방식입니다. Forward view를 사용하기 때문에, 미래의 보상들을 본 이후에 현재값으로 돌아와 업데이트를 진행합니다. 반면 오른쪽은 TD(\(lambda\))가 업데이트를 하는 방식입니다. z값에 과거의 gradient를 저장해두었다가, 현재 시점에서 과거의 값들을 업데이트 해 주는 것입니다.

여기서 명확하게 이해가 되지 않는다면, 우선 위의 w 업데이트 식의 z값에서 \(\lambda\)가 0이라고 가정해보는 것도 도움이 됩니다. 그럴 경우 첫 항인 decay 부분은 사라지고 gradient부분만 남게 되고, 아래와 같이 일반적인 one-step semi-gradient TD update가 되고, 그래서 해당 알고리즘이 TD(0)라고 불립니다. (챕터 9 참조, tabular case인 경우 simple TD rule 챕터 6.2 참조) 위의 그림에서는 바로 이전의 state만 업데이트해주는 것입니다.

\(w_{t+1} = w_t + \alpha \delta_t \nabla \hat{v}(S_t, w_t)\)

\(\lambda\)값이 0에서 1 사이일 경우에는, 바로 이전보다도 더 많은 과거 state들이 업데이트되는데, \(\lambda\)값이 1일 경우에 비해서 과거로 갈수록 업데이트되는 정도가 미미해집니다. \(\lambda\)값이 1일 경우에는 과거의 상태들이 \(\gamma\)값으로만 할인되고, 이는 Monte Carlo 방식과 동일하게 됩니다. 그래서 TD(1)이라고 불립니다.

TD(1)은 이전에서 배운 MC를 구현하는 방법보다 훨씬 더 일반화가 잘되고 적용성(applicability)이 높습니다. 예를 들어 이전 방법들은 에피소드별로 끝이 있는 episodic task에만 적용가능했지만 TD(1)은 연속되는 continuing task에도 적용이 가능합니다. 또한, MC의 단점 중 하나가 에피소드가 끝날 때까지 배우는 것이 없다는 것인데 TD(1)는 실시간으로(online) 점진적으로(incrementally) 배울 수 있습니다.

아까전 12.1 섹션에서 나온 19-state 예제(Example 7.1)를 통해 \(TD(\lambda)\) 알고리즘이 얼마나 잘 off-line \(lambda\)-return 알고리즘을 근사하는지를 나타낸 것이 위의 도표입니다. 각 \(\lambda\)값에 대해 \(\alpha\)값이 최적으로 선택된다면 두 알고리즘은 거의 동일한 성능을 보입니다. 다만, \(\alpha\)값이 최적보다 더 높게 책정될 경우에는 훨씬 더 성능이 나빠지며 이 19-state 문제에서는 그것이 그렇게 나빠보이지는 않지만 문제에 따라 굉장히 나쁜 결과를 초래하는 경우도 있습니다.

선형(linear) TD(\(\lambda\))는 on-policy 케이스에서 step-size parameter가 시간과 함께 특정한 형태로 감소하는 조건(챕터 6.2에 stochastic approximation 조건 참조)을 만족한다면 수렴(converge)이 보장되는데, 챕터 9.4 (조지아텍 커리큘럼상 챕터 9는 추후에 다룰 예정입니다)에서 나오듯이 오류를 최소화하는 weight (minimum-error weight vector)가 아닌, 그 부근에 있는 \(\lambda\)값에 의존하는 값으로 수렴합니다.

여기서 \(\bar{VE}\)는 Mean Squared Value Error로, (챕터 9.2 참조) 가치함수 v값의 오류가 얼마인지를 측정하는 값이고(머신러닝에서 MSE를 생각하시면 됩니다), 위의 식은 이 알고리즘의 극한(asymptotic)에서의 오류가 최저로 가능한 오류 수치의 \(\frac{1-\gamma \lambda}{1 - \gamma}\)배 이하임이 보장된다는 뜻입니다. \(\lambda\)가 1에 가까워질수록 이 오류의 bound가 최저로 가능한 수치에 근접하게 되는데, 나중에 다루겠지만 실제 문제에 적용할 때 \(\lambda\)를 1로 두는 것은 그렇게 좋은 선택은 아닙니다.

12.3 n-step Truncated \(\lambda\)-return Methods

Off-line \(\lambda\)-return 알고리즘은 실제로 효용이 크게 없는데, 그것은 \(\lambda\)-return이 에피소드가 끝날 때까지 계산되지 알 수가 없기 때문입니다. 만약 episodic이 아닌 continuing 케이스일 경우에 영원히 \(\lambda\)-return을 계산할 수 없습니다. 그런데 time step마다 \(\gamma \lambda\)의 속도로 decay를 하기 때문에, 먼 시점의 보상들은 사실상 무시할 수(truncate) 있습니다.

위와 같이 데이터를 어떤 시점 h까지만 사용하는 리턴을 truncated \(\lambda\)-return이라고 합니다. 이전에 원래 \(\lambda\)-return과 비교하면 사실상 terminal step T가 h로 대체된 것뿐임을 알 수 있습니다. 이를 사용하는 Truncated TD(\(\lambda\)), 혹은 TTD(\(\lambda\))는 아래와 같이 정의됩니다.

이 알고리즘을 구현하는 과정에서 각 step의 계산량이 n에 비례해서 늘어나지 않고 효율적으로 구현하는 방법이 있는데, k-step \(\lambda\)-return을 아래의 등식으로 풀어쓸 수 있기 때문입니다.

여기서 델타는 아래와 같습니다.

12.4 Redoing Updates: Online \(\lambda\)-return Algorithm

TTD(\(\lambda\))에서 truncation parameter n을 선택하는 데에는 균형이 필요합니다. n이 충분히 커서 off-line \(\lambda\)-return을 잘 근사해야하면서도, 충분히 작아서 업데이트들이 빨리 되고 행동에 빨리 영향을 줄 수 있어야 합니다. 그런데 계산량이 충분하다면 두 가지를 모두 성취하는 방법이 있습니다.

그것은 매 step에서 새로운 데이터가 들어올 때마다, 현재 에피소드의 제일 처음부터 모든 업데이트를 새로 하는 것입니다. 그러면 매 step마다 모든 업데이트들이 이전보다 더 나아져서, 결국 우리는 매 step마다 조금 더 긴 horizon과 조금 더 나은 결과를 얻을 수 있게 됩니다.

위는 아까 전에 나온 truncated \(\lambda\)-return이고, 아래는 3번째 step까지의 업데이트들이 나열된 것입니다.

여기 \(w^h_t\) 표기에서 h가 horizon, 즉 현재 에피소드에서 몇 step까지 보았는가를 나타냅니다. 이를 일반화하면 아래와 같습니다.

n-1 step까지는 아무 업데이트를 하지 않는 off-line \(\lambda\)-return 알고리즘과 비교해서 on-line \(\lambda\)-return 알고리즘은 더 계산량이 많은 반면 더 성능이 뛰어난데, 단순히 에피소드 도중에 더 성능이 좋은 건 당연하지만 에피소드가 다 끝난 후에도 아래와 같이 미묘하게 더 좋게 나옵니다. 그것은 bootstrapping 횟수가 많아지면서 더 많은 수의 업데이트를 했기 때문입니다.

12.5 True Online TD(\(\lambda\))

방금 다룬 online \(\lambda\)-return 알고리즘은 현재 TD 알고리즘 중에서 가장 성능이 좋은 알고리즘입니다. 그리고 이전에 offline \(\lambda\)-return 알고리즘을 TD(\(\lambda\)) 알고리즘으로 근사한 것과 비슷하게, 이 forward-view 알고리즘을 eligibility trace를 이용해서 backward-view로 효율적으로 구현한 것이 true online TD(\(\lambda\))입니다. TD(\(\lambda\))에 비해 근사가 좀 덜하기 때문에 "truer"하다고 부릅니다.

이 true online TD(\(\lambda\)) 알고리즘의 유도는 너무 복잡해서 여기서 다루지는 않지만, 아이디어는 간단합니다.

Online \(\lambda\)-return 알고리즘에서 업데이트 되는 w를 나열해 보면 위의 삼각형처럼 됩니다. 그런데 여기서 우리에게 사실상 필요한건 대각에 있는 \(w^t_t\)뿐이고, 그러면 이 값들을 가장 효율적으로 계산하는 방법만 찾으면 됩니다. 그렇게 계산하고 나면, 선형 모델, 즉 \(\hat{v}(s, w) = w^Tx(s)\)일 경우의 true online TD(\(\lambda\)) 알고리즘은 아래와 같습니다.

아래는 pseudocode입니다.

여기서 사용된 eligibility trace는 기존의 TD(\(\lambda\))에서 쓰인 것과 구분하기 위해 dutch trace라고 부르고, 기존의 것은 accumulating trace라고 부릅니다. 그 외에 이전에는 아래와 같은 replacing trace라는 것도 쓰였으나, 요즘에는 replacing trace는 dutch trace의 부정확한 근사로 보기 때문에 잘 쓰이지 않습니다.

일반적으로 dutch trace가 가장 이론적으로 잘 정립되어 있고 성능도 좋아 자주 쓰이고, accumulating trace는 dutch trace가 쓰일 수 없는 비선형(nonlinear) 함수와 관련해서 쓰입니다.

12.7 Sarsa(\(\lambda\))

이제까지 배운 eligibility trace 방법을 행동-가치함수(action-value function)로 확장하려면 그저 상태 가치함수 v를 행동-가치함수 q로 치환하면 됩니다.

n-step return은 위와 같으며, \(t + n \geq T\)일 경우에는 \(G_{t:t+n} = G_t\)입니다. Off-line \(\lambda\)-return 알고리즘에서의 업데이트도 아래처럼 v대신 q를 사용합니다.

행동 가치(action value)를 이용한 TD 방법인 Sarsa(\(\lambda\))는 TD(\(\lambda\))와 업데이트식이 아래와 같이 v를 q로 치환한 것 외엔 동일합니다.

Eligibility trace도 q로 치환한 형태입니다.

아래는 eligibility trace를 이용한 Sarsa의 성능을 보여줍니다. 한 번의 에피소드가 끝난 후에, one-step Sarsa는 보상이 주어지는 마지막 골 상태의 직전 상태만 업데이트 되지만, 10-step Sarsa는 마지막 10개 상태를 업데이트합니다. 반면, Sarsa(\(\lambda\))는 eligibility trace를 통해 에피소드의 시작부터 끝까지 할인이 되면서 업데이트가 전부 됩니다.

아래는 Sarsa(\(\lambda\))의 pseudocode인데, binary feature 방법도 포함되어 있습니다.

마찬가지로, online-\(\lambda\)-return 알고리즘에서 행동-가치함수를 사용하는 버전인 true online Sarsa(\(\lambda\))의 pseudocode가 아래에 있습니다.