Reinforcement Learning: An Introduction second edition, Chapter 12 Eligibility Traces

Reinforcement Learning: An Introduction second edition
Chapter 12 Eligibility Traces

Sutton輪読会
太⽥ 晋
2019-09-10

Transcript

1. Reinforcement Learning: An Introduction second edition Richard S. Sutton and Andrew G. Barto Sutton輪読会 第12章 Eligibility Traces 2019/9/10 太⽥ 晋
2. ⽬次 • 12 Eligibility Traces • 12.1 The λ-return • 12.2 TD(λ) • 12.3 n-step Truncated λ-return Methods • 12.4 Redoing Updates: Online λ-return Algorithm • 12.5 True Online TD(λ) • 12.6 *Dutch Traces in Monte Carlo Learning • 12.7 Sarsa(λ) • 12.8 Variable λ and γ • 12.9 *Off-policy Traces with Control Variates • 12.10 Watkinsʼs Q(λ) to Tree-Backup(λ) • 12.11 Stable Off-policy Methods with Traces • 12.12 Implementation Issues • 12.13 Conclusions
3. 今回紹介する範囲 • 12 Eligibility Traces • 12.1 The λ-return • 12.2 TD(λ) • 12.3 n-step Truncated λ-return Methods • 12.4 Redoing Updates: Online λ-return Algorithm • 12.5 True Online TD(λ) • 12.6 *Dutch Traces in Monte Carlo Learning • 12.7 Sarsa(λ) • 12.8 Variable λ and γ • 12.9 *Off-policy Traces with Control Variates • 12.10 Watkinsʼs Q(λ) to Tree-Backup(λ) • 12.11 Stable Off-policy Methods with Traces • 12.12 Implementation Issues • 12.13 Conclusions
4. 適格度トレース(eligibility traces)とは • MC法とTD法を統⼀的にとらえる別の⽅法 • nステップブートストラッピング(7章)とは違う • 複合λリターン(compound λ-return)の実装⽅法 • 基本的な考え⽅ • 短時間に徐々に薄れる記憶(short-term, fading memory) • 新しいスタイルのアルゴリズム • 前⽅視点 ⇔ 後⽅視点 の変換 • 前⽅視点(forward view) • 概念としては単純 → 理論や直感にはよい • 後⽅視点(backward view) • 計算論的に適した実装(computationally congenial implementation)
5. RL⼿法の統⼀的な⾒⽅
6. nステップリターン • エピソードタスク, 線形関数近似の場合
7. 複合アップデートターゲット • 例: 2ステップを半分、4ステップを半分 • 複合バックアップ • 各項を導出 • 各項に重みをかける • 重みは正の数かつ合計が1 • nステップリターンと類似の誤差低減性?(error reduction property)を持ち収束が保証されている • nステップリターンだけではなく、異なるnに対するnス テップリターンの平均値(any average of n-step returns for different ns)も妥当なアップデートターゲットになり うる
8. λ-リターン • 複合アップデートターゲットのひとつ • 全てのn-ステップターゲットを平均し たもの • 各項は λn-1 で重み付け • 重みの和は1(等⽐級数の和で計算可能)
9. λ-リターンの重み付け関数
10. MC法, TD(0)法との関係
11. オフライン λ-リターン アルゴリズム • エピソード終了まで待つ(オフライン) • 時間を戻って以下を更新
12. ランダムウォーク タスク (p. 125) • 中央のCから開始 • 左右の終端に達したらエピソード終了 • 右 or 左 に等確率で移動 • 報酬: 右の終端で+1 • ディスカウントなし γ=1 • AからEまでの真の状態価値: 1/6, 2/6, 3/6, 4/6, 5/6 • 今回の実験では状態数19
13. オフライン λ-リターン アルゴリズム n-ステップTD法との⽐較 • 中間のλが最もよい(nも同様) • λ-リターンの⽅が若⼲n-ステップよりもよい
14. 前⽅視点(forward view) • 未来の状態と報酬を⾒てどのように現在の状態を更新するか決 める
15. 後⽅視点(backward view) • 最近訪れた状態を振り返る • TD誤差 δt を後⽅に叫ぶ • 適格度トレース zt は γλ 倍で徐々に⼩さくなる
16. 半勾配TD(λ)法(semi-gradient TD(λ)) • 重みベクトルの更新 • 誤差範囲
17. 適格度トレース(Eligibility traces) • 短期の記憶ベクトル • 毎ステップγλで減衰 • 現在の状態のトレースに状態価値の勾配を 加算 • 累積(accumulating)適格度トレース
18. 半勾配TD(λ)アルゴリズム
19. TD(λ) 実験結果 • オフラインλ-リターンアルゴリズムに類似 • αが⾼い時若⼲パフォーマンスが悪い • →より改善できるか？ オンラインで更新できるか？
20. n-ステップ 切り捨てλ-リターン⼿法 n-step Truncated λ-return Methods • 理想はオフラインλ-リターンアルゴリズム • 問題点: エピソードが終了するまでλ-リターン がわからない • → 継続タスクでは事実上永遠にわからない • ただし、⻑く遅れてくる報酬の影響は γλ 倍で 毎ステップ弱くなる • → ⾃然な近似としていくつかのステップ以降を 切り捨てる • 切り捨て(truncated)λ-リターン
21. n-ステップ切り捨てλ-リターンアルゴリズム • 適切なnに対してTD(λ)より良いかもしれない • 更新がnステップ遅延するというコストはある • だが、もっとよいのはTrueオンラインTD(λ) • まずオンラインλ-リターンアルゴリズムがオフラインλ-リターンアルゴリズム よりも優れていることを⽰す • さらに、それと等価かつ計算論的に安価に計算できるのがTrueオンラインTD(λ) であることを⽰す
22. オンライン λ-リターン アルゴリズム • n-ステップ切り捨てλ-リターンをターゲットとする • tが増えて新しいデータ(状態と報酬)がわかる毎に最初(t=0)か ら更新をやり直す(計算は膨⼤)
23. オンライン λ-リターン アルゴリズム
24. オンライン λ-リターン アルゴリズム • オンラインの⽅が若⼲良い(エピソード途中でも重みベクトルを更新しているので) • λ=0は同⼀ • 計算論的複雑性(computational complexity)を抜きにして考えれば最も良いパフォーマンス • →これを解決するのがTrueオンラインTD(λ)
25. TrueオンラインTD(λ) • オンライン λ-リターン アルゴ リズムが最良のパフォーマンス • しかし計算論的複雑性も⼤きい • 適格度トレースを使って前⽅視 点のアルゴリズムを効率的な後 ⽅視点のアルゴリズムに転換 • 基本的な考え⽅はシンプル • 証明は⼤変 (12.6節) TrueオンラインTD(λ)は 対⾓成分だけを安価に計算
26. TrueオンラインTD(λ) アルゴリズム • どのようにコンパクトで効率的に対⾓成分を計算するか • オンラインλ-リターンアルゴリズムと全く同じ重みベクトル の列を⽣成することが証明されている(van Seijen et al. 2016) ← ダッチトレース
27. TrueオンラインTD(λ) アルゴリズム • メモリ使⽤量 • TD(λ)と同⼀ • ステップ毎の計算量 • TD(λ)より50%増加 • だがO(d)に留まる
28. 3つの適格度トレース • 累積トレース(accumulating traces) • ダッチトレースが使えない⾮線形関数近似で使われる • ダッチトレース(dutch traces, 割り勘？, 累積と置換の間) • 多くの場合置換トレースより優れる。明確な理論的基盤がある • 置換トレース(replacing traces) • ダッチトレースの荒い近似
29. Sarsa(λ) • TD(λ)とほぼ同じ
30. Sarsa(λ)実験結果 • タイルコーディング、線形関数近似 • n-ステップSarsaより良いパフォーマンス
31. TrueオンラインSarsa(λ) • 右: TrueオンラインSarsa(λ) • 左: TrueオンラインTD(λ)
32. TrueオンラインSarsa(λ) 実験結果 • TrueオンラインSarsa(λ) (ダッチトレース)が最適
33. 様々なタスクにおけるλの影響 • 左2つ • シンプル • 連続状態値 • Sarsa(λ) • 右上 • ⽅策評価 • TD(λ) • λが中間の値が最適
34. 適格度トレース(eligibility traces)のまとめ • MC法とTD法を統⼀する効率的で逐次的(incremental)な⽅法 • MC法の利点 (⾮マルコフ性の問題に対して強い) • TD法の利点 (⾼速、計算論的に適している) • True オンライン TD(λ) が新しく、かつ、最適 • オンライン λ-リターン アルゴリズムと全く等価(exactly equivalent) • True オンライン Sarsa(λ) も同様に良いパフォーマンス • 3種類の適格度トレース • 累積(accumulating)・ダッチ(dutch)・置換(replacing) • 予測(prediction)とon-policy制御(control)の両⽅に使える • off-policy制御と予測にも使える • トレース⼿法は多くの場合nステップ⼿法より良い • トレースは計算コストが⼩さい (〜2倍)
35. 参考資料 • Suttonの授業スライド • https://drive.google.com/drive/folders/0B3w765rOKuKAeVZIWmFa ZW1FTW8 • Suttonの授業ビデオ • https://drive.google.com/drive/folders/0B- WvrETGtkesN29sV1g3aXZ1Z0U • Pythonコード • https://github.com/ShangtongZhang/reinforcement-learning-an- introduction/tree/master/chapter12 • マウンテンカーとランダムウォークのコードがある