데이터를 얻기 위한 행동의 기반이 되는 정책과 업데이트 하는 대상이 되는 정책이 동일한 on-policy learning과 달리, off-policy learning에서는 behavior policy b에 따라 데이터를 획득하면서 target policy \(\pi\)의 가치 함수를 배웁니다. Control 문제에서 보통 \(\pi\)는 greedy 정책이고, b는 좀더 exploration에 초점을 둔 \(\epsilon\)-greedy 정책 등을 사용합니다. 결국 off-policy를 사용하는 이유는 exploitation과 exploitation의 trade-off를 해결하기 위함인데, on-policy 방법과 달리 off-policy 방법은 이론적으로 깔끔하게 정립된 상황은 아닙니다.

11.1 Semi-gradient Methods

많은 off-policy 알고리즘이 아래의 importance sampling ratio를 사용합니다. (챕터 5.5 참조)

Off-policy semi-gradient 방법에는 이 ratio를 추가해주면 됩니다. 예를 들어, one-step state-value 알고리즘은 semi-gradient off-policy TD(0)로, 아래와 같습니다.

여기서 \(\delta\)는 episodic/discounted이냐, 아니면 continuing/undiscounted이냐에 따라 아래처럼 정의됩니다.

Action value 알고리즘은 아래와 같이 semi-gradient Expected Sarsa가 있습니다.

위의 알고리즘은 importance sampling을 사용하지 않는데, tabular case의 경우 유일한 샘플 action이 \(A_t\)라서 이 가치를 배우는데 있어 다른 action을 고려하지 않아도 된다는 것이 명확합니다. 하지만 함수 근사에 있어서는 조금 애매한 부분이 있고 연구 중에 있습니다.

Multi-step으로 일반화한 알고리즘에서는 state-value와 action-value 알고리즘 모두 importance sampling을 사용합니다. 예를 들어 n-step semi-gradient Expected Sarsa는 아래와 같습니다.

여기서 에피소드가 끝난 후의 값들은, \(\rho_k\)는 \(k \geq T\)일 때 (여기서 T는 에피소드의 마지막 step) 1의 값을 가지고, \(G_{t:n}\)는 \(t+n \geq T\)의 경우 \(G_t\)가 됩니다.

챕터 7에서 importance sampling 자체를 사용하지 않는 off-policy algorithm인 n-step tree-backup algorithm을 다룬 바 있는데, 그것의 semi-gradient 버전은 아래와 같습니다.

11.2 Examples of Off-policy Divergence

Off-policy learning을 함수 근사(function approximation)을 이용해서 실행할 때 문제 중 하나는 업데이트의 분포가 on-policy 분포를 따르지 않는다는 것입니다. 이 섹션에서는 semi-gradient와 다른 단순한 알고리즘이 불안정하고 diverge하는 예제를 살펴봅니다.

먼저, 위의 간단한 MDP를 봅시다. 함수 근사 벡터 w는 딱 하나의 요소밖에 없고, 위 두 상태의 feature가 각각 1과 2인 경우입니다. \(\gamma\)가 거의 1이고 w의 초기값이 10라고 하면, 두 상태의 가치 추정치는 각각 10과 20이 되고, TD error는 10이 됩니다. 여기서 \(\alpha\)가 0.1라고 가정하면, 첫번째 상태의 가치는 10에서 11로 업데이트가 됩니다. 문제는, 두번째 상태의 추정 가치도 22로 업데이트가 되어서 TD error는 이번에는 11이 되고, 업데이트는 11에서 12.1이 됩니다. 즉, 무한히 diverge가 되는 것입니다.

이 예제에서 가장 중요한 키포인트는, w가 다른 transition에서 업데이트되는 일 없이 이 두 상태 사이의 transition에서만 반복적으로 업데이트된다는 부분입니다. On-policy 방법에서 이런 일은 불가능한데 off-policy 방법에서는 이런 일이 일어나는 이유는, target policy와 behavior policy가 다르기 때문입니다. 만약 behavior policy가, target policy는 절대로 하지 않을, 확률 0으로 행동을 하게 된다면 importance sampling ratio는 0이 되고 업데이트는 일어나지 않습니다. 그래서 어떤 특정한 transition에서만 업데이트가 반복되면서 diverge하게 되는 것입니다. 다른 관점에서 보면, 두번째 상태에서 20이란 가치는 미래 수익에 대한 어떤 약속입니다. On-policy 방법에서는 이 약속이 차후에 행동이 진행되면서 지켜지지만, off-policy 방법에서는 target policy가 약속하는 미래 수익이, behavior policy의 행동이 많이 어긋남으로 인해 실현되지 않게 되면서 가치가 diverge한다고 볼 수도 있습니다.

위의 예제는 너무 간단해서 조금 더 완성된 MDP 예제를 보는 것도 도움이 되는데 Baird의 counterexample이란 예제는 페이지 261를 참조바랍니다. 결론은 똑같이, diverge 가능하다는 결론입니다. 페이지 263에서는 Q-learning이나 DP에서도 diverge되는 예들이 나옵니다.

이러한 불안정성을 예방하는 하나의 방법은 averagers라는 방법인데, 관찰된 타겟들에서 extrapolate를 하지 않는 함수 근사법이며 nearest neighbor 방법이나 locally weighted regression 등의 알고리즘을 통해 사용할 수 있지만 tile coding이나 neural network와 사용할 수는 없습니다.

11.3 The Deadly Triad

이제까지 논의를 종합해보면, 불안정성과 divergence는 이 세 가지를 함께 사용할 경우 생겨나며, 이를 죽음의 삼인조(deadly triad)라고 부릅니다.

• 함수 근사(function approximation)
• Bootstrapping
• Off-policy training

이러한 불안정성의 위험은 control이나 generalized policy iteration에서 오는 것이 아니라 더 단순한 prediction 케이스에서 옵니다. 또한 위험은 learning 과정이나 환경에 대한 불확실성에서 오는 것도 아니라서, 더 단순한 planning method 등에서도 발생합니다.

세 가지 중에서 하나만 버려야한다면, 일단 함수 근사는 절대로 버릴 수 없습니다. State space가 큰 문제를 풀기 위해서는 필수이기 때문입니다. Bootstrapping 없이 하는 것은 가능은 하지만, 계산 효율과 샘플 효율이 굉장히 떨어져 버립니다. 마지막으로 off-policy learning은 편리는 하지만 필수적으로 보이지는 않습니다. 하지만 이 책에서 다뤄지지 않는 더 심화된 응용으로 들어갈 경우 필수가 됩니다. 실제 사람과 동물에게서도 심리학적으로 off-policy에 더 가까운 사고를 한다는 것이 점점 더 밝혀지고 있는 실정입니다.