強化学習3 -モンテカルロ法，TD学習-

強化学習3 モンテカルロ法，TD学習 公⽴⼩松⼤学 藤⽥ ⼀寿 Ver. 20240424

モンテカルロ法

モンテカルロ法 • モンテカルロ法は経験のみ⽤いる． • 経験とは環境との実際もしくはシミュレーションされた相互作⽤から状態，⾏動，報酬の サンプル列である． • 環境のダイナミクスに関する事前知識を必要とせず，それでも最適な⾏動を達成する． • ここでは，経験がエピソードに分割され，どのような⾏動を選択してもすべてのエ ピソードが最終的に終了すると仮定する． • モンテカルロ法はサンプルした収益の平均に基づき強化学習問題を解く⼿法である． • モンテカルロ法は，バンディット法と同じように各状態とアクションのペアの収益 をサンプリングして平均する． • 主な違いは複数の状態が存在し，それぞれがそれぞれのバンディット問題のように振る舞 い，それぞれのバンディット問題が相互に関連している点である． • つまり，ある状態で⾏動をとった後の収益は，同じエピソード内の後の状態でとった⾏動 に依存する．すべての⾏動選択は学習中であるため，問題は先の状態から⾒て⾮定常とな る．

モンテカルロ予測 • ある⽅策が与えられた場合の状態価値関数を学習するためのモンテカルロ法を 考える． • 状態の価値とは期待収益（将来の期待累積割引報酬）である． • それを計算する単純な⽅法は状態を訪れたあとに観測された収益の平均を求めるこ とである． • モンテカルロ法には，幾度も収益が観測されるとともに，その平均が期待価値に収 束するという考えが根底にある．

モンテカルロ予測 • ある⽅策に従い状態𝑠を経験することによって得られたエピソードが与えられた ときに，⽅策𝜋の下での状況の価値𝑣! 𝑠 を推定したい． • このとき⽤いることができる⼿法として，First-visit MC methodとEvery-visit MC methodがある． • First-visit MC methodは，𝑣! 𝑠 を推定する． • エピソードの中で，初めて状態𝑠を訪れることを初回訪問(first visit)という． • 状態𝑠のFirst-visitのreturnを平均する． • このreturnはエピソードごとに計算される． • Every-visit MC methodは，状態𝑠の訪問したときに得られるreturnを平均する． • このreturnは状態𝑠を訪問する度に計算される． • この２つの⼿法では訪問回数を無限⼤にすると，𝑉 𝑠 が𝑣! 𝑠 に収束する．

First-visit MC prediction, for estimating 𝑉 ≈ 𝑣C Input: a policy 𝜋 to be evaluated Initialize: 𝑉 𝑠 ∈ ℝ, arbitrarily, for all 𝑠 ∈ 𝑆 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑠 ← an empty list, for all 𝑠 ∈ 𝑆 Loop forever (for each episode): Generate an episode following 𝜋 : 𝑆", 𝐴", 𝑅#, 𝑆#, 𝐴#, 𝑅$, … , 𝑆%&#, 𝐴 %&#, 𝑅% エピソード:エージェントが初期状態から終状態まで⾏ 動したときの⾏動や結果の記録 𝐺←0 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0 : 𝐺 ← 𝛾𝐺 + 𝑅'(# unless 𝑆' appears in 𝑆", 𝑆#, … , 𝑆'&#: 𝑆! が𝑆", 𝑆#, … , 𝑆!$"の中になければ，つまり初めて状態𝑆! = 𝑠が出現した時． Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆' 当たり前だが，エピソード内で𝑠を初めて訪問できるのは１度だけなので， エピ ソードごとに1回状態𝑠のときの𝐺が追加される． 𝑉 𝑆' ← average 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆' )

every-visit MC prediction, for estimating 𝑉 ≈ 𝑣C Input: a policy 𝜋 to be evaluated Initialize: 𝑉 𝑠 ∈ ℝ, arbitrarily, for all 𝑠 ∈ 𝑆 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑠 ← an empty list, for all 𝑠 ∈ 𝑆 Loop forever (for each episode): Generate an episode following 𝜋 : 𝑆", 𝐴", 𝑅#, 𝑆#, 𝐴#, 𝑅$, … , 𝑆%&#, 𝐴 %&#, 𝑅% 𝐺←0 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0 : 𝐺 ← 𝛾𝐺 + 𝑅'(# Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆' 𝑠を訪問するたびに，𝑠のときの𝐺が追加される． 𝑉 𝑆' ← average 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆' )

モンテカルロ法とバックアップダイアグラム • バックアップダイアグラムでは，⼀番上のrootノードがアップデートされ ，下はすべての遷移とleafノードを表し，それらの収益と期待価値はアッ プデートに寄与する． • モンテカルロ法の場合，rootは状態で，その下は任意のエピソードの遷移 の履歴の全体である． • 動的計画法のバックアップダイアグラムでは，すべての可能な履歴を⽰し ていたが，モンテカルロ法ではサンプルされた，ただ⼀つのエピソードを ⽰す．

モンテカルロ法の特徴 • それぞれの状態における推定は独⽴である．ある状態における推定が，他のど の状態の推定に基づいて構築されることはない． • モンテカルロ法はブートストラップを⾏わない． • 1つの状態価値の予測のための計算量は状態の数に依存しない． • 状態の 1 つまたはサブセットのみの価値が必要な場合に，モンテカルロ法が特に魅 ⼒的なものになる．

⾏動価値のモンテカルロ推定 • モデルが使えない場合は，状態価値関数ではなく⾏動価値関数を推定するのが特に有効である ． • モデルがあれば，⽅策を決定するのに状態価値だけで⼗分である．この場合，単に報酬と次の状 態の最も良い組み合わせになる⾏動を選べば良い． • 𝜋 ! 𝑠 = arg max 𝑞# 𝑠, 𝑎 = arg max ∑$! ,& 𝑝 𝑠 ! , 𝑟 𝑠, 𝑎 " " 𝑟 + 𝛾𝑣# 𝑠 ! • モデルがない場合，⽅策を決定するには状態価値だけでは不⼗分で，各⾏動の価値を明確に推定 しなければならない． • つまり，モデルがない場合，最適⾏動価値𝑞∗ を推定することがゴールとなる． • ⾏動価値のための⽅策評価問題は，状態𝑠から始め，⾏動𝑎をとり，そして，その後⽅策𝜋に従 うときの ， 期待収益𝑞' 𝑠, 𝑎 を推定することである． • Every-visit MC prediction methodでは，状態𝑠と⾏動𝑎のペアの価値を，そのペアへのすべて の訪問後の収益の平均として推定する． • 𝑠と𝑎のペアはエピソード内で何度も現れる． • First-visit MC methodでは、各エピソードで最初にその状態𝑠が訪問され，⾏動𝑎が選択され た後の収益を平均する．

GPI: Generalized policy iteration • GPIでは近似⽅策と近似価値関数の両⽅を持つ． • 価値関数は現在の⽅策を⽤い，より良い価値関数に置き換える． • ⽅策は現在の価値関数に基づき改善される．

Monte Carlo control Controlとは最適⽅策を探すこと • Classical policy iterationのモンテカルロバージョンを考える． • この⼿法では，⽅策評価と⽅策改善の完全なステップが交互に⾏われる． • 任意の⽅策𝜋" から始まり，最適な⽅策と最適な⾏動価値関数で終わる． • ⽅策評価では，たくさんのエピソードが探索され，近似⾏動価値関数は真の関数 に漸近的に近づく． • 今は，無限個のエピソードを観測し，そのエピソードには開始の探索がある⽣成される 開始の探索は，開始の状態とその状態での⾏動を探索することを意味する． と仮定しよう． • ⽅策改善では現在の価値関数に基づきgreedyな⽅策が形成される． • ⾏動価値関数がわかっていれば，⽅策はgreedyで良いため，⽅策のためのモデルは必要 ない． 完全な⽅策評価 完全な⽅策改善 完全な⽅策評価 完全な⽅策改善 完全な⽅策評価 完全な⽅策改善 完全な⽅策評価

⽅策改善定理 • ⽅策改善におけるgreedyな⽅策 𝜋 𝑠 は，⾏動価値関数𝑞 𝑠, 𝑎 を⽤い次のように書ける． • 𝜋 𝑠 = arg max 𝑞 𝑠, 𝑎 ( • 𝑘回⽬の⽅策評価で⽤いた⽅策を𝜋) とすると，⾏動価値関数𝑞'( と書ける． ⽅策改善は𝑞'( に基 づき，𝑘 + 1回⽬の⽅策評価で使う𝜋)*+ を求める． • ⽅策改善定理を適⽤すると 𝑞%" についてGreedyな⾏動を選択をしている． 𝑞!! 𝑠, 𝜋:(# 𝑠 = 𝑞!! 𝑠, arg max 𝑞!! 𝑠, 𝑎 = max 𝑞!! 𝑠, 𝑎 ; ; ≥ 𝑞"& 𝑠, 𝜋# 𝑠 𝜋' 𝑠 は 𝜋#$% 𝑠 より悪いか同等の⽅策 ≥ 𝑣"& 𝑠 • つまり，Monte Carlo法においても繰り返し改善することで最適な⽅策に収束する．

モンテカルロ法における仮説 • モンテカルロ法が収束するために，２つの仮定を⽴てた． • エピソードは開始の探索を持つ． • ⽅策評価を無限個のエピソードで実⾏できる． • 実⽤的なアルゴリズムを得るためには，これらの仮説を取り除く必要がある． • 現実では開始の状態と⾏動には制限があるため，それらを無制限に探索することは できない． • 無限個のエピソードを⽣成することはできない．

無限個のエピソードは使えない • 無限個のエピソードを使うという仮定は⽐較的簡単に取り除くことができる． • 同じ問題は反復政策評価などの古典的な DP⼿法でも発⽣するが，これも真の価値関数に漸近的 にのみ収束する． • DP とモンテカルロのどちらの場合も問題を解決するには 2 つの⽅法がある． • 1つ⽬は、各⽅策評価において𝑞'( を近似するという考え⽅を堅持することである． • 測定と仮定は推定の誤差の⼤きさと確率の範囲を得るために⾏われ，そして，これらの範囲が⼗ 分に⼩さいことを保証するために各⽅策評価中に⼗分な反復を⾏う． • 要するに，求めるのは近似だから，それがある程度の精度に収まっていればよい（更新値の差が 閾値内に収まっていればよい）だろうと考える． • 2つ⽬のアプローチでは，⽅策改善に戻る前に⽅策評価を完了することを諦める． • 各評価ステップで状態価値関数を𝑞"& に近づけるが，多数のステップを経る場合を除いて実際に 近づくことは期待できない． • この考え⽅の極端な例は， 1回のみ価値反復を⾏う場合である．この反復では，⽅策改善の各ス テップの間に反復的な⽅策評価が 1 回だけ実⾏される． • 要するに，状態価値関数が収束していなくても，その価値関数を⽤い⽅策改善を⾏う（greedyな ⽅策を探す）．

Monte Carlo with Exploring Starts • Monte Carlo policy iterationでは，エピソードごとに評価と改善を繰り返すのが⾃ 然である． • エピソードの観測の後，観察された収益が⽅策評価に使⽤され，エピソードで訪れ たすべての状態における⽅策が改善される． • Monte Carlo with Exploring Starts (Monte Carlo ES)は，これらの⽅針に沿った完 全で単純なアルゴリズムである． • Monte Carlo ESでは，観測に使⽤された⽅策が何であれ，状態とアクションのペアのすべ てのリターンが累積され，平均化される． • Monte Carlo ESが準最適な⽅策に収束できないことは容易に分かる．そうであれば，価値 関数は最終的にその⽅策の価値関数に収束し，次に，価値関数により⽅策が変更されるこ とになる． • 安定性は⽅策と価値関数の両⽅が最適である場合にのみ実現される．時間の経過とともに ⾏動価値関数の変化が減少するため，最適な固定点への収束は避けられないと思われるが， まだ証明されていない(Sutton and Barto, 2018)．

Monte Carlo ES (Exploring Starts), for estimating 𝜋 ≈ 𝜋∗
Initialize:
𝜋 𝑠 ∈ 𝐴 𝑠 (arbitrarily), for all 𝑠 ∈ 𝑆

すべての状態において任意の可能な⾏動をする⽅策を作成する．

𝑄 𝑠, 𝑎 ∈ 𝑅 (arbitrarily), for all 𝑠 ∈ 𝑆, a ∈ 𝐴(𝑠)

⾏動価値関数を任意の値で初期化する．

𝑅𝑒𝑡𝑢𝑟𝑛 𝑠, 𝑎 ← 𝑒𝑚𝑝𝑙𝑡𝑦 𝑙𝑖𝑠𝑡, 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑠 ∈ 𝑆, a ∈ 𝐴(𝑠) 収益を保存するための空リストを作成する．
Loop forever (for each episode):

選択可能な最初の状態と⾏動をランダムに選ぶ(開始の探索)．

Choose 𝑆" ∈ 𝑆, 𝐴" ∈ 𝐴 𝑆< randomly such that all pairs have probabililty > 0
Generate an episode from 𝑆", 𝐴", following 𝜋: 𝑆", 𝐴"𝑅#, … , 𝑆'&#, 𝐴'&#, 𝑅%
⽅策𝜋に基づき𝑇までの状態，⾏動，報酬を⽣成する．

𝐺←0

Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … 0:
𝐺 ← 𝛾𝐺 + 𝑅'(#
Unless the pair 𝑆' , 𝐴' appears in 𝑆", 𝐴", 𝑆#, 𝐴#, … , 𝑆'&#, 𝐴'&#:
Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆' , 𝐴'

これまで⽣成したエピソードから得られた収益𝐺の平均をとり，⾏

𝑄 𝑆' , 𝐴' ←average(𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆' , 𝐴' ) 動価値関数を求める．
𝜋 𝑆' ← arg max 𝑄 𝑆' , 𝑎
;

𝑆& , 𝐴& が𝑆' , 𝐴' , 𝑆% , 𝐴% , … , 𝑆&(% , 𝐴&(% になければ，
つまり ， 𝑆& , 𝐴& のペアがエピソード内で初め
て現れたのなら．

⾏動価値関数からgreedyな⾏動を求める．

Monte Carlo Control without Exploring Starts • どうやって開始状態とその時の⾏動を探索するというありそうもない想定を避ける か？ • 開始時にすべての状態と⾏動を⼗分な回数探索すれば，エピソードを⼗分に探索できるだ ろうが，開始時にすべての状態と⾏動を探索する前提は現実的ではない．しかし，開始状 態とその時の⾏動の探索をしなければ局所解に陥るかもしれない． • すべての⾏動が無限に選択されるようにする唯⼀の⼀般的な⽅法は，エージェント がそれらを選択し続けることである． • エージェントは最適解を求めるために，各⾏動を⼗分な回数探索（選択）をする必要があ る． • 局所解を避けるため，エージェントは現在最適だと思っている⾏動以外の各⾏動も探索 （選択）し続けなければならない． • これを可能するために2つのアプローチがある． • on-policy methodは意思決定に使⽤される⽅策を評価または改善しようと試みる． • off-policy methodはデータ⽣成に使⽤される⽅策とは異なる⽅策を評価または改善する．

Monte Carlo Control without Exploring Starts • On-policy methodでは⽅策は⼀般に，𝜋 𝑎 𝑠 > 0 for all 𝑠 ∈ 𝑆 and for all 𝑎 ∈ 𝐴(𝑠) である．しかし，決定論的な最適⽅策に徐々に近づけていく． • はじめは⽅策はone-hot vectorではない(ソフトである，greedyではない)が，徐々にonehot vector（greedy）に近づける． • ここで説明するon-policy methodでは，𝜀-greedy⽅策を使⽤する． • つまり，ほとんどの場合，最⼤の推定⾏動価値を持つ⾏動を選択するが，𝜀の確率で⾏動 をランダムに選択する． / • すべてのnongreedyな⾏動には最⼩の選択確率 0 1 が与えられ，greedyな⾏動には1 − 𝜀 + / 0 1 • の確率が与えられる． 𝐴 𝑠 は選択可能な⾏動数なので，実はnongreedyが⾏動が選ばれる確率は𝜀 − 𝜀/|𝐴(𝑠)|である ) （𝐴(𝑠)はgreedyな⾏動も含む）．よって，greedyな⾏動をする確率は，1 − 𝜀 − * $ =1−𝜀+ 𝜀/|𝐴(𝑠)| • 𝜀-greedy⽅策は， 𝜀 > 0ですべての状態と⾏動について𝜋 𝑎 ∣ 𝑠 ≥ で定義される𝜀-soft⽅策の例である． = > ? とする⽅策

Monte Carlo Control without Exploring Starts • On-policyモンテカルロ制御の全体的な考え⽅は，依然としてGPIの考え⽅である． • Monte Carlo ESと同様に，我々は現在の⽅策における⾏動価値関数を推定するために，Firstvisit MC methodを使⽤する． • しかし，開始探索の前提が無ないため，我々は現在の価値関数における⽅策を貪欲にする事に よって，単純に⽅策改善を改善することはできない． • なぜならば，この前提がないことが⾮貪欲な⾏動のさらなる探索を妨げられるからである． 開始状態とその時の⾏動を探索する場合は，それらをランダムに選び様々なエピソードを⽣成できる （数多くの状態，⾏動， 報酬の組み合わせを探索できる）ため⽅策を最適化できる．⼀⽅，（環境，状態価値，⽅策などで）開始状態と⾏動が決まっ ている場合は，⽅策は局所的な最適解に陥り，同じ状態と⾏動を選び続ける可能性がある（現在の⽅策における⽐貪欲な⾏動 がとれない）． • 幸いなことに，GPIは⽅策が完全に貪欲な⽅策に移⾏することを要求してるわけではなく，た だ⽅策を貪欲な⽅向に移動させることのみを要求している． • on-policy methodでは，我々は⽅策を，ただ𝜀-greedy⽅策に移動させるだけである． ⽅策は完全に貪欲である必要はないため，貪欲な⾏動以外もたまにする 𝜀-greedy⽅策を使って良い． 貪欲な⾏動 以外もたまにするので，⾮貪欲な⾏動の探索もできる． • どの𝜀-soft ポリシーでも，𝑞' に関するあらゆる𝜀-greedy ポリシーは、⽅策𝜋以上であることが 保証される．

On-policy first-visit MC control (for 𝜺-soft policies), estimates 𝜋 ≈ 𝜋∗
Algorithm parameter: small 𝜀 > 0
Initialize:
⽅策を任意の𝜀-soft⽅策で初期化する．
𝜋 ← an arbitrary 𝜀-soft policy
⾏動価値関数を任意の値で初期化する．
𝑄 𝑠, 𝑎 ∈ ℝ (arbitrarily), for all 𝑠 ∈ 𝑆, 𝑎 ∈ 𝐴(𝑠)
𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑠, 𝑎) ← empty list, for all 𝑠 ∈ 𝑆, 𝑎 ∈ 𝐴(𝑠) 収益を保存するための空リストを作成する．
Repeat forever (for each episode):
⽅策𝜋に基づき エピソードを⽣成する．𝐴! は 𝜀-soft⽅策に基づき決める．𝑆!はタ
Generate an episode following 𝜋: 𝑆+ 𝐴+ 𝑅, , . . . , 𝑆-., , 𝐴 -., , 𝑅- スクによる制約に従い設定する．ランダムかもしれないし指定されているかも
しれない．
𝐺←0
Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0:
𝐺 ← 𝛾𝐺 + 𝑅/0,
Unless the pair 𝑆/ , 𝐴/ appears in 𝑆+ , 𝐴+ , 𝑆, , 𝐴, , … , 𝑆/., , 𝐴/., : 𝑆& , 𝐴& が𝑆' , 𝐴' , 𝑆% , 𝐴% , … , 𝑆&(% , 𝐴&(% になければ，つまり ， 𝑆& , 𝐴&
のペアがエピソード内で初めて現れたのなら．
Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆/ , 𝐴/ )
𝑄 𝑆/ , 𝐴/ ← average(𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆/ , 𝐴/ )) これまで⽣成したエピソードから得られた収益𝐺の平均をとり，⾏動価値関数を求める．

𝐴∗ ← arg max 𝑄 𝑆/ , 𝑎 (with ties broken arbitrarily)

⾏動価値関数からgreedyな⾏動を求める．

"

For all 𝑎 ∈ 𝐴(𝑆/ ):
𝜋 𝑎 ∣ 𝑆/

求めたgreedyな⾏動から𝜀-soft⽅策を作成する．

1 − 𝜀 + 𝜀/|𝐴(𝑆/ )|,
=Z
𝜀/|𝐴(𝑆/ )|

if 𝑎 = 𝐴∗
if 𝑎 ≠ 𝐴∗

⽅策改善定理 • ⾏動価値関数𝑞! に関する𝜀-greedy⽅策は𝜀-soft⽅策𝜋よりも改善されていることが⽅策改 善定理によって保証されている． - 𝑞" 𝑠, 𝜋 𝑠 :状態𝑠, ⽅策𝜋 𝑠 のときの価値関数 𝑞" 𝑠, 𝑎 :状態𝑠, ⾏動𝑎のときの価値関数 • 𝜋′を𝜀-greedy⽅策とする． 𝑞# 𝑠, 𝜋 ! 𝑠 = ` 𝜋 ! 𝑎 𝑠 𝑞# 𝑠, 𝑎 " = ` "1234 526 7* $," - 𝜀 𝜀 𝑞# 𝑠, 𝑎 + 1 − 𝜀 + 𝐴 𝑆/ 𝐴 𝑆/ 𝜀-greedy⽅策では， . / の確率でgreedyな⾏動以 max 𝑞# 𝑠, 𝑎 " ) 𝜀 =` 𝑞 𝑠, 𝑎 + 1 − 𝜀 max 𝑞# 𝑠, 𝑎 " 𝐴 𝑆/ # 外を選び，1 − . /+ . /+ + - × 𝐴 𝑆! − . / + =1−𝜀+ の確率でgreedyな⾏動(max 𝑞% 𝑠, 𝑎 )を選ぶ． 0 " 𝜀 𝜋 𝑎 𝑠 − 𝜀 𝐴 𝑆/ = ` 𝑞# 𝑠, 𝑎 + 1 − 𝜀 ` max 𝑞# 𝑠, 𝑎 " 𝐴 𝑆/ 1−𝜀 " " 𝜀 𝜋 𝑎 𝑠 − 𝜀 𝐴 𝑆/ ≥ ` 𝑞# 𝑠, 𝑎 + 1 − 𝜀 ` 𝑞# 𝑠, 𝑎 𝐴 𝑆/ 1−𝜀 " = ` 𝜋 𝑎 𝑠 𝑞# 𝑠, 𝑎 = 𝑣# 𝑠 " " ∑- , 𝑎𝑠 ( %(/ " # $% = 1 詳しくは次のスライドで． この式は⾏動価値関数の値がすべて等しいとき(𝑞, 𝑠, 𝑎 = max 𝑞, 𝑠, 𝑎 )に等号が成り⽴つ． - さらにこの式から，𝜋 . 𝑠 = 𝜋 𝑎 𝑠 のときも等号が成り⽴つ．また，𝜀-greedy⽅策𝜋′は， 𝜀-soft⽅ 策と同等かより良いことも分かる．

式展開の詳細 )𝜋 𝑎 𝑠 = 1 8 )𝜋 𝑎 𝑠 − 𝜀 = 1 − 𝜀 8 𝜀 =1−𝜀 𝐴 𝑆< 8∈: ;1 𝜀 𝜋 𝑎 𝑠 − 𝐴 𝑆< ) =1 1−𝜀 ) 𝜋 𝑎 𝑠 − 8∈: ;1 𝜀 𝜋 𝑎 𝑠 − 𝜀 𝐴 𝑆! < 𝑞% 𝑠, 𝑎 + 1 − 𝜀 < 𝑞% 𝑠, 𝑎 𝐴 𝑆! 1−𝜀 0 0 𝜀 𝜀 =< +𝜋 𝑎 𝑠 − 𝑞% 𝑠, 𝑎 𝐴 𝑆! 𝐴 𝑆! 0 = < 𝜋 𝑎 𝑠 𝑞% 𝑠, 𝑎 0

Off-policy prediction • エージェントは現在最適だと思う⾏動をして⾏動価値を学習しようとするが， 真 に最適な⾏動を⾒つけるためには，すべての⾏動を探索する（⾮最適な⾏動をす る）必要がある． • 探索的な⽅策に従って⾏動しながら，最適な⽅策をどうやって学べばよいか？ • 単純なアプローチとして，次の2つの⽅策を⽤意することが考えられる． • 学習されて最適な⽅策となるターゲット⽅策． • より探索的に⾏動を⽣成するために使⽤される⾏動⽅策． • ターゲット⽅策から得たデータを⽤いず学習を⾏うこのアプローチはoff-policy学 習と呼ばれる． • off-policy法では，学習に使うデータは異なる⽅策によるものであるため，多くの 場合分散が⼤きく，収束が遅くなる． • ⼀⽅，off-policy法は，より強⼒で汎⽤的である． • On-policy法は，ターゲット⽅策と⾏動⽅策が同じである特殊なoff-policy法である．

Off-policy prediction • ここでは，ターゲット⽅策𝜋と⾏動⽅策𝑏の両⽅が固定されている予測問題を考え ることで，off-policy⼿法を考察する． • 𝑣! または𝑞! を推定したいとするが，我々は⾏動⽅策𝑏に従うエピソードだけ持って いるとする． • 𝑏に基づき⽣成したエピソードを使⽤して𝜋の価値を推定するには，𝜋の下で実⾏さ れるすべての⾏動が，少なくとも時々b の下でも実⾏される必要がある． • 𝜋 𝑎 ∣ 𝑠 > 0のとき𝑏 𝑎 ∣ 𝑠 > 0． • これはカバレッジの仮定と呼ばれる． • 時々実⾏しなければならないから𝑏は確率的である必要がある． • ⼀⽅𝜋は決定論的だろう． • ターゲット⽅策は通常，⾏動価値関数の現在の推定値に対し決定論的なgreedy⽅策である． • Greedyなターゲット⽅策は決定論的な最適⽅策になるが，⾏動⽅策は確率的でよ り探索的なもの (たとえば𝜀-greedy⽅策) を維持する．

Importance sampling
• ここでは𝜋が不変で且つ与えられている場合の予測問題を検討する．
• ほとんどすべての off-policy法は，importance samplingを利⽤する．
• これは，ある分布からのサンプルが与えられた場合に期待値を推定するための⼀般
的な⼿法である．

• Importance-sampling ratioと呼ばれる，ターゲット⽅策および⾏動⽅策の下
で発⽣するtrajectoryが発⽣する相対確率に従って報酬に重み付けを⾏うこと
により， importance samplingを学習に適⽤する．
• 開始状態𝑆. が与えられると，ターゲット⽅策𝜋における，その後の状態と⾏動
のtrajectory 𝐴. , 𝑆./0 , 𝐴./0 , … , 𝑆1 の発⽣確率は次のようになる．
𝑃 𝐴' , 𝑆'(#, 𝐴'(#, … , 𝑆% ∣ 𝑆' , 𝐴':%&# ∼ 𝜋
= 𝜋 𝐴' 𝑆' 𝑃 𝑆'(# 𝑆' , 𝐴' 𝜋 𝐴'(# 𝑆'(# … 𝑃 𝑆% 𝑆%&#, 𝐴 %&#
%&#

= X 𝜋 𝐴: 𝑆: 𝑃 𝑆:(# 𝑆: , 𝐴:
:b'

𝐴!:3$" ∼ 𝜋は⽅策𝜋に基づき⽣
成される⼀連の⾏動を意味す
る． 𝐴!:3$" は条件付き確率の
条件に⼊っているが， 𝐴!:3$"
は確率分布𝜋から⽣成される．

Importance-sampling ratio
• ターゲット⽅策と⾏動⽅策の下での状態と⾏動のtrajectoryの相対確率
(Importance-sampling ratio) は次のようになる．
∏%&#
∏%&#
:b' 𝜋 𝐴: 𝑆: 𝑃 𝑆:(# 𝑆: , 𝐴:
:b' 𝜋 𝐴: 𝑆:
𝜌':%&# =̇ %&#
= %&#
∏:b' 𝑏 𝐴: 𝑆: 𝑃 𝑆:(# 𝑆: , 𝐴:
∏:b' 𝑏 𝐴: 𝑆:

• Importance-sampling ratioは2つの⽅策と⾏動と状態の系列のみに依存する．
• ターゲット⽅策の元での期待収益 (価値) を推定したいが，得られるのは⾏動
⽅策による収益𝐺. だけである．
• これらの収益は誤った期待値 𝐸 𝐺. ∣ 𝑆. = 𝑠 = 𝑣2 𝑠 を持つため，𝑣! を得るため
に，これらの収益を平均できない．
• ここで⽐率𝜌7:9:; を正しい期待価値を持つ収益に変換するために⽤いる．
𝐸 𝜌':%&#𝐺' ∣ 𝑆' = 𝑠 = 𝑣! 𝑠

Importance-sampling ratio
⽅策𝑏の下でtrajectoryが⽣じる確率は
𝑃 𝐴< , 𝑆<=> , 𝐴<=> , … , 𝑆? ∣ 𝑆< , 𝐴<:?A> ∼ 𝑏 = 𝑏 𝐴< 𝑆< 𝑃 𝑆<=> 𝑆< , 𝐴< 𝑏 𝐴<=> 𝑆<=> … 𝑃 𝑆? 𝑆?A> , 𝐴 ?A>
?A>

= 5 𝑏 𝐴# 𝑆# 𝑃 𝑆#=> 𝑆# , 𝐴#
#B<

⽅策𝑏の下での収益の収益の期待値は
𝐸C 𝐺< ∣ 𝑆< = 𝑠 = ) 𝑃{𝐺< ∣ 𝐴< , 𝑆<=> , 𝐴<=> , … , 𝑆? }𝑃 𝐴< , 𝑆<=> , 𝐴<=> , … , 𝑆? ∣ 𝑆< , 𝐴<:?A> ∼ 𝑏 𝐺<
D1

?A>

= ) 𝑃{𝐺< ∣ 𝐴< , 𝑆<=> , 𝐴<=> , … , 𝑆? } 5 𝑏 𝐴# 𝑆# 𝑃 𝑆#=> 𝑆# , 𝐴# 𝐺<
よって

D1

#B<

収益𝐺& は trajectory ごとに存在するた
め，𝐺& の⽣じる確率は trajectory を条
件とした条件付き確率で書ける．

?A>

∏?A>
#B< 𝜋 𝐴# 𝑆#
𝐸C 𝜌<:?A> 𝐺< ∣ 𝑆< = 𝑠 = ) ?A>
𝑃{𝐺< ∣ 𝐴< , 𝑆<=> , 𝐴<=> , … , 𝑆? } 5 𝑏 𝐴# 𝑆# 𝑃 𝑆#=> 𝑆# , 𝐴# 𝐺<
∏#B< 𝑏 𝐴# 𝑆#
D1

?A>

#B<

= ) 𝑃{𝐺< ∣ 𝐴< , 𝑆<=> , 𝐴<=> , … , 𝑆? } 5 𝜋 𝐴# 𝑆# 𝑃 𝑆#=> 𝑆# , 𝐴# 𝐺< = 𝐸" 𝐺< ∣ 𝑆< = 𝑠 = 𝑣" 𝑠
D1

#B<

importance-sampling • これで，𝑣! 𝑠 を推定するために，⽅策𝑏に従って観察されたエピソードのバッチか ら収益を平均するモンテカルロアルゴリズムを与える準備が整う． • ここでは，エピソードの境界を越えて増加するタイムステップに番号を使う． • 例えば，バッチの最初のエピソードが時刻100で終了状態で終了したとき，次のエピソー ドは時刻𝑡 = 101から始まる． • これにより，タイムステップ番号を使⽤して特定のエピソードの特定のステップを参照で きるようになる． 特に，状態𝑠が訪問されるすべての時間ステップのセットを𝒯(𝑠)と定義 できる． これはevery-visit methodの場合である． • First-visit methodの場合，𝒯(𝑠)は各エピソードで𝑠に最初訪問したタイムステップのみを 含む． • また，𝑇(𝑡)は時刻𝑡の後に起こる最初の終了時間を表し，𝐺' は𝑡から𝑇(𝑡)までの収益 を表す． • 𝐺' '∈𝒯(?) は状態𝑠に対する収益であり， 𝜌':% ' &# '∈𝒯(?) はそれに対応する importance-sampling ratioである．

2つのimportance-sampling • 𝑣! 𝑠 を推定するため，単純に収益をimportance-sampling ratioでスケールし， 結果を平均する． • 𝑉 𝑠 =̇ ∑>∈𝒯(B) 4>:E > FG5> |𝒯(7)| • このようにimportance samplingが単純な平均として⾏われる場合，これを ordinary importance samplingと呼ぶ． • 重要な代替⼿法はである加重平均を使⽤するweighted importance sampling である．これは次のように定義される． ∑>∈𝒯(B) 4>:E > FG5> • 𝑉 𝑠 =̇ ∑ >∈𝒯(B) 4>:E > FG • ただし，分⺟がゼロの場合はゼロとする．

2つのimportance-sampling
• ordinary importance samplingとweighted importance samplingの2 種類のimportance-samplingを
理解するために，状態𝑠から⼀つの収益を観察した後のfirst-visit methodによる推定値を考える．
• weighted importance-samplingでは，単⼀の収益を得たときの𝜌<:? < A> は分⼦と分⺟で相殺されるた
め，推定値は⽐率に関係なく観測された収益と等しくなる (⽐率が⾮ゼロであると仮定して)．
8

• 𝑉 𝑠 = 8+:1 + 23

9+

+:1 + 23

= 𝐺/

• この収益が観測された唯⼀のものであることを考えると，これは合理的な推定値ではあるが，その期
待値は𝑣" (𝑠)ではなく𝑣C (𝑠)であり，この統計的な意味ではバイアスがある．
• 対照的に，ordinary importance samplingのfirst-visitバージョンは，期待値において常に𝑣" (𝑠) であ
る(バイアスはない) が，極端になる可能性がある．
• 𝑉 𝑠 =

8+:1 + 23 9+
|𝒯($)|

= 𝜌/:- / ., 𝐺/

• ratioが10であると仮定すると，これは観察されたtrajectoryがターゲット⽅策の下で観測される確率
は⾏動⽅策の下での10 倍であるを⽰しめす． この場合， ordinary importance samplingは観測され
た収益の 10 倍を推定する．つまり，たとえエピソードのtrajectoryが⽬標とする⽅策を⾮常によく表
していると考えられるとしても，推定値は観察された収益からはかなり離れたものとなるだろう．

Importance samplingとバイアス • First-visit法における2種類のimportance sampling間の違いは，バイアスと分散で表される． • ordinary importance samplingにはバイアスはないが， weighted importance-samplingにはバイア スがある (ただし，バイアスは漸近的にゼロに収束する)． • ⼀⽅，ordinary importance samplingの分散は，ratioの分散に制限がないため，⼀般に制限がない． また，weighted importance-samplingでは，単⼀の収益に対する重みの最⼤値は1である． • 実際，収益に制限がある（有界である）と仮定すると，ratio⾃体の分散が無限であっても， weighted importance-samplingの推定量の分散はゼロに収束する (Precup, Sutton, and Dasgupta 2001)． • 実践では，通常，重み付き推定量の分散が⼤幅に低くなり，強く推奨される． • それにもかかわらず，関数近似を使⽤した近似⼿法への拡張するが簡単であるため， ordinary importance samplingを完全に放棄するわけではない． • 2種類のimportance samplingのevery-visit⼿法には両⽅ともバイアスがかかりるが，サンプル数が増 加するにつれてバイアスは漸近的にゼロに下がる． • 実際には，every-visit⼿法が好まれることがよくある．これは，どの状態が訪問されたかを追跡する 必要がなく，近似に拡張するのがはるかに簡単であるためである．

Incremental Implementation • Ordinary importance samplingでは，価値は収益は𝜌.:1 . 90 によってスケーリ ングされ次のように単純に平均化される． • 𝑉 𝑠 =̇ ∑E∈𝒯(H) fE:J E KLgE |𝒯(?)| • これは，次のようにincremental methodsにおいて使⽤することができる． • 新たに観測𝐺. を観測したときの新たな価値𝑉:/0 𝑠 は 𝑉?0, 𝑠 =̇ = = 1 𝒯?0, 𝑠 1 𝒯?0, 𝑠 = 𝑉? 𝑠 + ∑/∈𝒯453 ($) 𝜌/:- / ., 𝐺/ 𝒯?0, 𝑠 𝜌/:- / ., 𝐺/ + = 1 𝒯?0, 𝜌/:- / ., 𝐺/ + ` 𝜌/:- / ., 𝐺/ /∈𝒯4 ($) 𝒯?0, 𝑠 − 1 ` 𝜌/:- / ., 𝐺/ 𝒯?0, 𝑠 − 1 /∈𝒯4 ($) 𝜌/:- / ., 𝐺/ + 𝒯?0, 𝑠 − 1 𝑉? 𝑠 1 𝒯?0, 𝑠 𝜌/:- / ., 𝐺/ − 𝑉? 𝑠 新たに観測されたので，時刻𝑡が 𝒯M (𝑠)に追加される．追加された 𝒯M (𝑠)を 𝒯M=> (𝑠)とする．1つ追加 されたので 𝒯M (𝑠) = 𝒯M=> (𝑠) − 1である．

Off-policy MC prediction • weighted importance-samplingを使⽤するケースでは，収益の加重平均を形成する必要があり，少し異なる incremental algorithmが必要となる． • 収益列𝐺, , 𝐺A , … , 𝐺?., があるとする．ただし，すべて同じ状態で開始され，それぞれに対応するランダムな重 み𝑊B （例えば𝑊B = 𝜌/4:- /4 ., ）がある．この時，価値を次のように推定したい． • 𝑉? =̇ ∑ 786 &56 D & 9 & ∑ 786 &56 D & , 𝑛≥2 • そして，単⼀の収益𝐺? を取得すると同時に価値を最新の状態に保ちたい．𝑉? を更新することに加え，最初の 𝑛個の収益に与えられた重みの累積和𝐶? も状態ごとに維持しなければならない．以上を満たす𝑉? の更新ルール は次のとおりである． D • 𝑉?0, =̇ 𝑉? + E 7 𝐺? − 𝑉? 7 • 𝐶?0, =̇ 𝐶? + 𝑊?0, • ここで，𝐶+ =̇ 0 (𝑉, は任意なので指定する必要はない)． • 次のスライドにモンテカルロ⽅策評価のためのincremental algorithmを⽰す． • このアルゴリズムは，名⽬上， weighted importance-samplingを使⽤したoff-policyの場合に適⽤されるが，ターゲット⽅ 策と⾏動⽅策を同じon-policyの場合にも適⽤できる(この場合 (𝜋 = 𝑏)，𝑊 = 1)． • 近似 𝑄 は 𝑞% (遭遇したすべての状態と⾏動のペアについて)に収束するが，⾏動は潜在的に異なる⽅策 𝑏 に従って選択される．

Off-policy MC prediction (policy evaluation) for estimating 𝑄 ≈ 𝑞@
Input: an arbitrary target policy 𝜋 ターゲット⽅策が⼊⼒される．つまり，ターゲット⽅策は固定であり，最適化されない．
Initialize, for all 𝑠 ∈ 𝑆, 𝑎 ∈ 𝐴(𝑠):
⾏動価値関数を任意の値で初期化する．
𝑄 𝑠, 𝑎 ∈ 𝑅 (arbitrarily)
𝐶 𝑠, 𝑎 ← 0
Loop forever (for each episode):
𝑏 ← any policy with coverage of 𝜋
⽅策𝑏に基づき𝑇までの状態，⾏動，報酬を⽣成する．
Generate an episode following 𝑏: 𝑆N , 𝐴N , 𝑅> , … , 𝑆?A> , 𝐴 ?A> , 𝑅?
𝐺←0
𝑊←1
Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0, while 𝑊 ≠ 0: 𝑊 = 0になると，その後値が更新されない．
収益を計算する．
𝐺 ← 𝛾𝐺 + 𝑅<=>
𝐶 𝑆< , 𝐴< ← 𝐶 𝑆< , 𝐴< + 𝑊 重みの累積和を計算する．
O
𝑄 𝑆< , 𝐴< ← 𝑄 𝑆< , 𝐴< +
𝐺 − 𝑄 𝑆< , 𝐴< ⾏動価値を計算する．
P ;1 ,:1
" 𝐴 𝑆
𝑊 ← 𝑊 C 𝐴< 𝑆<
重みを計算する．
< <
このアルゴリズムで得られるのはQである．

式展開 ∑ACD; 𝑊C 𝐺C 𝑊A 𝐺A + ∑A:; 1 CD; 𝑊C 𝐺C 𝑉AB; = = = ∑ACD; 𝑊C 𝐶A 𝐶A 1 = 𝑊 𝐺 + 𝑉A 𝐶A − 𝑊A 𝐶A A A 𝑊A = 𝑉A + 𝐺 − 𝑉A 𝐶A A A:; 𝐶A:; 𝑊A 𝐺A + / 𝑊C 𝐺C 𝐶A:; CD; 𝐶M=> =̇ 𝐶M + 𝑊M=> 𝐶M =̇ 𝐶MA> + 𝑊M 𝐶MA> = 𝐶M − 𝑊M M 𝐶M = 𝑊> + ⋯ + 𝑊M = ) 𝑊# #B>

Off-policy Monte Carlo Control • off-policy⼿法では，⾏動の⽣成に使⽤される⾏動⽅策𝑏と，評価および改善される ターゲット⽅策𝜋がある． • この分離の利点は，ターゲット⽅策が決定論的 (greedyなど) である⼀⽅で，⾏動 ⽅策がすべての可能な⾏動をサンプリングし続けることができる点である． • ⾏動⽅策は，ターゲット⽅策によって選択される可能性のあるすべての⾏動を選択 する確率が⾮ゼロであることを要求する． • つまり，あらゆる可能性を探るためには⾏動⽅策がソフトであることを要求する． • 次のスライドは𝜋∗ と𝑞∗ を推定するための，GPIとweighted importance-samplingに 基づく off-policy Monte Carlo Controlを⽰す． • ターゲット⽅策𝜋 ≈ 𝜋∗ は，𝑞' の推定値である𝑄に関するgreedy⽅策である． • ⾏動⽅策𝑏は何でも構わないが，𝜋を最適⽅策に確実に収束させるためには，状態と⾏動の 各ペアに対して無限個の収益を取得する必要がある．これは𝑏を𝜀-softに選択することで保 証される．

Off-policy MC Control, for estimating 𝜋 ≈ 𝜋∗
Initialize, for all 𝑠 ∈ 𝑆, 𝑎 ∈ 𝐴(𝑠):
𝑄 𝑠, 𝑎 ∈ ℝ (arbitrarily) ⾏動価値関数を任意の値で初期化する．
𝐶 𝑠, 𝑎 ← 0
𝜋 𝑠 ← arg max 𝑄 𝑠, 𝑎 (with ties broken consistently)
8

ターゲット⽅策を初期の⾏動価値関数に対するgreedy⽅策
にする．同点の場合の対処は⼀貫している．

Loop forever (for each episode):
𝑏 ← any soft policy 𝑏を何らかのsoft policyにする． Softなら何でも良い．
Generate an episode using 𝑏: 𝑆N , 𝐴N , 𝑅> , … , 𝑆?A> , 𝐴 ?A> , 𝑅? ⽅策𝑏に基づき𝑇までの状態，⾏動，報酬を⽣成する．
𝐺←0
𝑊←1
Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, . . . , 0:
𝐺 ← 𝛾𝐺 + 𝑅<=> 収益を計算する．
𝐶 𝑆< , 𝐴< ← 𝐶 𝑆< , 𝐴< + 𝑊 重みの累積和を計算する．
O
𝑄 𝑆< , 𝐴< ← 𝑄 𝑆< , 𝐴< +
𝐺 − 𝑄 𝑆< , 𝐴< ⾏動価値を計算する．
P ;1 ,:1

ターゲット⽅策を現在の⾏動価値関数に対するgreedy⽅策

𝜋 𝑆< ← arg max 𝑄 𝑆< , 𝑎 (with ties broken consistently) にする．同点の場合の対処は⼀貫している．
8

If 𝐴< ≠ 𝜋 𝑆< then exit inner Loop (proceed to next episode)
𝐴& が現在のgreedy⾏動でなければ第２のループを抜ける（
>
重みを計算する．
𝑊←𝑊
次のエピソードを処理する）．
C 𝐴< 𝑆<
このアルゴリズムの⽬的は最適なターゲット⽅策 𝜋 を求めることである．

Discounting-aware importance sampling • これまで検討してきたoff-policy⼿法は，割引された報酬の合計としての収益 の内部構造を考慮せず，単⼀の収益を全体としてみなし，その収益のために importance sampling重みを計算する． • ここで，収益の内部構造を使⽤してoff-policy推定量の分散を⼤幅に削減する ための⽅法に検討する．

Discounting-aware importance sampling • たとえば，エピソードが⻑く，𝛾が 1より⼤幅に⼩さい場合を考えてみる，具体的にするために，エ ピソードが100ステップ続き，𝛾 = 0であるとする．時刻0からの収益は単に𝐺N = 𝑅> になる． • しかし，importance sampling ratioは次の積になる． • " 𝐴N 𝑆N " 𝐴> 𝑆> C 𝐴N 𝑆N C 𝐴> 𝑆> … " 𝐴TT 𝑆TT C 𝐴TT 𝑆TT • Ordinary importance samplingでは，収益は全体の積でスケールされるが，実際に必要なのは最初の " 𝐴N 𝑆N 部分 だけである． C 𝐴N 𝑆N " 𝐴 𝑆 " 𝐴 𝑆 • 最初の報酬の後，収益はすでに決定されているので，他の99の要素C 𝐴> 𝑆> … C 𝐴TT 𝑆TT は無関係で ある． > > TT TT • 𝐺+ = 𝑅+ だからtrajectoryは𝐴+ だけだと考えて良い．よって，𝜋 𝐴+ 𝑆+ と𝑏 𝐴+ 𝑆+ のみ考えれば良く，確率の⽐ # 𝐴+ 𝑆+ だけ必要になる． F 𝐴+ 𝑆+ • Ratioの最初の部分だけ使うため，価値関数の分散は⼤幅に増加する． • ここで⼤きな分散を回避する⽅法を考えてみる．

Discounting-aware importance sampling • このアイデアの本質は，割引を終端の確率または，それと同等の部分的終端の 度合いを決定するものとして考える点である． • 任意の𝛾 ∈ 0, 1 において，収益𝐺" は1ステップにおける部分終端とみなし， 𝑅0 に度合い1 − 𝛾をかける．2ステップにおける部分終端は𝑅0 + 𝑅H に 1 − 𝛾 𝛾をか ける． • 1 − 𝛾 𝛾は2ステップでの終了度を表し， 𝛾は1ステップが終端でない確率を表 す． • 3 ステップの終了度は 1 − 𝛾 𝛾 H となり， 𝛾 H は最初の 2 つのステップのどちら も終端でなかったことを反映する． • なぜ割引を確率と⾒なすのか？ # • lim ∑kb# 1 − 𝛾 𝛾 k = 1 − 𝛾 #&n = 1，つまり𝑛 → ∞ のとき係数の総和は1に収束す k→m る．𝑛が⼗分⼤きければ 1 − 𝛾 𝛾 k は確率と⾒なしてよいだろう．

Discounting-aware importance sampling • つまり，収益を次のように式変形する． 𝐺' ≐ 𝑅'(# + 𝛾𝑅'($ + 𝛾 $𝑅'(p + ⋯ + 𝛾 %&'&#𝑅% = 1 − 𝛾 𝑅'(# + 𝛾 𝑅'(# + 𝑅'($ + 𝛾 $𝑅'(p + ⋯ + 𝛾 %&'&#𝑅% = 1 − 𝛾 𝑅'(# + 1 − 𝛾 𝛾 𝑅'(# + 𝑅'($ + 𝛾 $ 𝑅'(# + 𝑅'($ + 𝑅'(p + ⋯ + 𝛾 %&'&#𝑅% = 1 − 𝛾 𝑅'(# + 1 − 𝛾 𝛾 𝑅'(# + 𝑅'($ + 1 − 𝛾 𝛾 $ 𝑅'(# + 𝑅'($ + 𝑅'(p + ⋯ + 1 − 𝛾 𝛾 q&'&$ 𝑅'(# + 𝑅'($ + ⋯ + 𝑅%&'&$ + 𝛾 %&'&# 𝑅'(# + 𝑅'($ + ⋯ + 𝑅% = 1 − 𝛾 𝐺̅':'(# + 1 − 𝛾 𝛾𝐺̅':'($ + ⋯ + 𝛾 %&'&$ 1 − 𝛾 𝐺̅':%&# + 𝛾 %&'&#𝐺̅':'(% %&# = 1−𝛾 f 𝛾 o&'&#𝐺̅':o + 𝛾 %&'&#𝐺̅':'(% ob'(# • ここで，𝐺̅':o ≐ 𝑅'(# + 𝑅'($ + ⋯ + 𝑅o , 0 ≤ 𝑡 < ℎ ≤ 𝑇である． • この部分収益 𝐺̅':o はフラット部分収益と呼ばれる． • フラットとは割引しないことを意味し，部分とはこれらの収益が終了まで延⻑され ず，horizon ℎで停⽌することを表す (𝑇はエピソードの終了時刻である)．

Discounting-aware Importance Sampling • 次に，先を切り捨てられたimportance sampling ratioにより，フラット部分収益をスケールす る必要がある． • フラット部分収益𝐺̅L:M にはℎまでの報酬のみが含まれるため，必要なのはℎまでの確率の⽐だけ である． • ℎまでの確率の⽐しか使わないので，先が切り捨てられている． • importance sampling推定量を次のように定義する． • 𝑉 𝑠 =̇ • 𝑉 𝑠 =̇ INGNL Q MNGNL Q ̅ ∑G∈𝒯(H) +OP ∑MNL G:INL S̅ G:I *P G:M G NL SG:M G IJGKL P |𝒯(1)| INGNL Q MNGNL Q ̅ ∑G∈𝒯(H) +OP ∑MNL G:INL S̅ G:I *P G:M G NL SG:M G IJGKL P INGNL Q MNGNL Q ∑G∈𝒯(H) +OP ∑MNL G:INL *P G:M G NL IJGKL P • これら 2 つの推定量をdiscounting-aware importance sampling推定量と呼ぶ． • これらは割引率を考慮するが，𝛾 = 1のときは効果はない (off-policy推定量と同である)．

Discounting-aware Importance Sampling • Trajectoryが1つだとして • 𝑉 𝑠 = 𝜌.:1 . 90 𝐺. と I9.90 • 𝑉 𝑠 = 1 − 𝛾 ∑190 𝜌.:I90 𝐺̅.:I + 𝛾 19.90 𝜌.:1 . 90 𝐺̅.:./1 IJ./0 𝛾 • を⽐べる． • 𝑉 𝑠 = 𝜌.:1 . 90 𝐺. の場合，推定量に対し𝜌.:1 . 90 のばらつきが与える影響が⼤ きいが，改良された推定量はフラット部分収益の和となっており，その係数で ある𝜌.:I90 のばらつきの影響を抑えている．

Per-decision importance sampling • Off-policy importance samplingにおいて，報酬の合計である収益の構造を考慮できる⽅法が もう 1 つある．これは，割引がない場合でも分散を削減できる可能性がある (つまり，𝛾 = 1 の場合)． • Off-policy推定量では，分⼦における総和の各項も総和の形である． • 𝜌L:UO+ 𝐺L = 𝜌L:UO+ 𝑅L*+ + 𝛾𝑅L*V + 𝛾 V 𝑅L*W + ⋯ + 𝛾 UOLO+ 𝑅U • = 𝜌L:UO+ 𝑅L*+ + 𝛾𝜌L:UO+ 𝑅L*V + 𝛾 V 𝜌L:UO+ 𝑅L*W + ⋯ + 𝛾 UOLO+ 𝜌L:UO+ 𝑅U • Off-policy推定量は，これらの項の期待値に依存しする．たとえば，最初の項は次のように書 くことができる． • 𝜌L:UO+ 𝑅L*+ = ' 𝐴L 𝑆L ' 𝐴L*+ 𝑆L*+ X 𝐴L 𝑆L X 𝐴L*+ 𝑆L*+ … ' 𝐴 UO+ 𝑆UO+ X 𝐴 UO+ 𝑆UO+ 𝑅L*+ ' 𝐴 𝑆 • しかし， 𝑅L*+ を観測したとき実際に起っているのは𝑆L と𝐴L だから，最初X 𝐴L 𝑆L と最後の L L 𝑅L*+ (報酬) だけが考えればよいように思える．さらに，他のすべての因⼦の期待値は1である． ' 𝐴 𝑆 • 𝐸 X 𝐴) 𝑆) ) ) = ∑( 𝑏 𝑎 𝑆) ' 𝑎 𝑆) X 𝑎 𝑆) = ∑( 𝜋 𝑎 𝑆) = 1

Per-decision importance sampling • さらにいくつかのステップを踏むと，思った通り，これら他の因⼦はすべて期待通りに効果を持たない． • 𝐸 𝜌/:-., 𝑅/0, = 𝐸 𝜌/:/ 𝑅/0, • 𝑘番⽬の項についても同様に • 𝐸 𝜌/:-., 𝑅/0O = 𝐸 𝜌/:/0O., 𝑅/0O • さらに収益の期待値は次のように書ける． • 𝐸 𝜌/:-., 𝐺/ = 𝐸 𝐺N/ • ここで，𝐺N/ = 𝜌/:/ 𝑅/0, + 𝛾𝜌/:/0, 𝑅/0A + 𝛾 A 𝜌/:/0A 𝑅/0P + ⋯ + 𝛾 -./., 𝜌/:-., 𝑅• このアイデアをPer-decision importance samplingと呼ぶ． • Ordinary importance samplingと同様にバイアスの無い期待値を持つ，first-visitの場合， 𝐺N/ を使⽤した代替 のimportance sampling推定量があることがすぐに分かる． • 𝑉 𝑠 =̇ ∑ 1∈𝒯(<) 9Q1 |𝒯($)| • これは，分散が⼩さくなることが期待できるかもしれない． • 各報酬にかけられる⽐は起こった事象に関する確率しか使っていないため極端な値を取らないのではないか．時刻𝑡から遠 い報酬は割引により⼩さな値となり，より不確実であろう遠い未来の報酬のばらつきの影響を抑えられるのではないか．

Per-decision importance samplingにおける期待値の計算 𝐸 𝜌':%&#𝑅'(# = 𝐸 𝜋 𝐴' 𝑆' 𝜋 𝐴'(# 𝑆'(# 𝜋 𝐴 %&# 𝑆%&# … 𝑅 𝑏 𝐴' 𝑆' 𝑏 𝐴'(# 𝑆'(# 𝑏 𝐴 %&# 𝑆%&# '(# それぞれ独⽴だとすると， 𝐸 𝜌':%&#𝑅'(# = 𝐸 ! 𝐴 𝑆 𝐸 r 𝐴: 𝑆: : : 𝜋 𝐴' 𝑆' 𝜋 𝐴'(# 𝑆'(# 𝑅'(# 𝐸 𝑏 𝐴' 𝑆' 𝑏 𝐴'(# 𝑆'(# …𝐸 𝜋 𝐴 %&# 𝑆%&# 𝑏 𝐴 %&# 𝑆%&# = 1より 𝜋 𝐴' 𝑆' 𝑅 = 𝐸 𝜌':' 𝑅'(# 𝑏 𝐴' 𝑆' '(# 𝐸 𝜌':%&#𝐺' = 𝐸 𝜌':%&#𝑅'(# + 𝛾𝜌':%&#𝑅'($ + 𝛾 $𝜌':% ' &#𝑅'(p + ⋯ + 𝛾 %&'&#𝜌':%&#𝑅% = 𝐸 𝜌':' 𝑅'(# + 𝛾𝜌':'($𝑅'(# + ⋯ + 𝛾 %&'&#𝜌':%&#𝑅% = 𝐸 𝐺g' 𝐸 𝜌':% ' &#𝑅'(# = 𝐸

Temporal-Difference (TD) learning

TD learning • TD learningは、モンテカルロの考え⽅と動的プログラミング (DP) の考え⽅ を組み合わせたものである． • TD法は，モンテカルロ法と同様に環境のダイナミクスのモデルを使⽤せずに ⽣の経験から直接学習できる． • TD法は， DPと同様に最終結果を待たずに他の学習された推定値に部分的に基 づいて推定値を更新する． • 制御問題 (最適なポリシーを⾒つけること) のために，DP，TD，およびモン テカルロ法のすべてが⼀般化ポリシー反復 (GPI) のバリエーションを使⽤する． • これらの⽅法の違いは主に予測問題へのアプローチの違いである．

𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡-𝛼 MC • TD 法とモンテカルロ法は経験を使⽤して予測問題を解決する． • ⽅策𝜋に基づく何らかの経験が与えられると，どちらの⽅法も，その経験で発 ⽣する⾮終端状態𝑆. に対する𝑣! の推定値𝑉を更新する． • ⼤まかに⾔うと，モンテカルロ法は訪問後の収益が判明するまで待機し，その収益 を𝑉 𝑆' の⽬標として使う． • ⾮定常環境に適した単純なevery-visit Monte Carlo methodは次のとおりであ る． • 𝑉 𝑆. ← 𝑉 𝑆. + 𝛼 𝐺. − 𝑉 𝑆. 収益 𝐺! が 𝑉 𝑆! の⽬標となるので差をとっている． • ここで，𝐺. は時刻𝑡後の実際の収益，𝛼は固定のステップサイズパラメーターで ある． • この⽅法を𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡-𝛼 MCと呼ぶ．

TD(0) • モンテカルロ法では𝑉 𝑆' への増分を決定するためにエピソードの終了まで待たな ければならない． • エピソードが終わらないと𝐺L が決まらない． • TD法では次のタイムステップまで待てば良い． • TD法は時刻𝑡 + 1で直ちに𝑉 𝑆' を形成し，観察された報酬𝑅' + 1と推定値𝑉 𝑆' + 1 を使⽤して更新を⾏う． • 最も単純なTD法では，状態𝑆'(# に遷移して報酬𝑅'(# を受け取るとすぐに次の式で更 新する． • 𝑉 𝑆' ← 𝑉 𝑆' + 𝛼 𝑅'(# + 𝛾𝑉 𝑆'(# − 𝑉 𝑆' • TD法では，更新のターゲットは𝑅'(# + 𝛾𝑉 𝑆'(# である． • このTD法はTD(0)やone-step TDと呼ばれる． • TD(0)は推定値を使って推定するのでブートストラップ法である．

Tabular TD(0) for estimating 𝑣C Input: the policy 𝜋 to be evaluated 評価する⽅策を⽤意する． Algorithm parameter: step size 𝛼 ∈ 0, 1 Initialize 𝑉 𝑠 , for all 𝑠 ∈ 𝑆 = , arbitrarily except that 𝑉 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 = 0 価値関数を任意の値で初期化するが，終端状態の価値だけ0とする． Loop for each episode: Initialize 𝑆 Loop for each step of episode: 状態𝑆のときの⾏動を⽅策𝜋に基づき⽣成する． 𝐴 ← action given by 𝜋 for 𝑆 Take action 𝐴, observe 𝑅, 𝑆 ⾏動𝐴を取り，報酬と次の状態を観測する． 𝑉 𝑆 ← 𝑉 𝑆 + 𝛼 𝑅 + 𝛾𝑉 𝑆 - − 𝑉 𝑆 状態を次の状態にする． 𝑆 ← 𝑆until 𝑆 is terminal 状態が終端状態になるまでループを続ける．

TD法はモンテカルロ法とブートストラップの組み合わせ • 状態価値は次の式で表される． • 𝑣! 𝑠 = 𝐸! 𝐺' 𝑆' = 𝑠 = 𝐸! 𝑅' + 𝛾𝐺'(# 𝑆' = 𝑠 = 𝐸! 𝑅' + 𝛾𝑣! 𝑆'(# 𝑆' = 𝑠 • モンテカルロ法は𝐺' の推定値をターゲットとして使⽤する． • 𝐺L の期待値は不明だから，モンテカルロ法のターゲットはサンプルから得られた推定値で ある ． • サンプルのみから収益を推定するので，モンテカルロ法はブートストラップではない． • DP法では𝑅' + 𝛾𝑣! 𝑆'(# の推定値をターゲットとして使⽤する． • DP法では，真の𝑣' 𝑆L*+ の代わりに現在の推定値𝑉 𝑆L*+ を使⽤し，𝑅L + 𝛾𝑣' 𝑆L*+ をサン プリングする． • TD法はモンテカルロのサンプリングとDPのブートストラップを組み合わせている． • 完全な環境モデルが無いため𝑅L をサンプルし（モンテカルロのサンプリング），推定値 𝑉 𝑆L*+ を使⽤することで（DPのブートストラップ） 𝑅L + 𝛾𝑣' 𝑆L*+ を計算する．

Tabular TD(0) • 図はTabular TD(0) のバックアップ図である． • 状態ノードの推定値は，直後の状態への1つのサンプル遷移に基づいて更新さ れる． • TD更新とモンテカルロ更新をサンプル更新と呼ぶ． • 後続の状態（または状態と⾏動のペア）をサンプリングし，後続の価値と途中の報 酬を使⽤してbacked-up価値を計算し，それに応じて現在の状態（または状態と⾏ 動のペア）の価値を更新するからである． • 単純に⾔えば，後続の状態をサンプリングした結果を⽤いるから．

TD誤差 • TD(0) 更新の括弧内の量， 𝑆. の推定値とより良い推定値𝑅./0 + 𝛾𝑉 𝑆./0 との 差は⼀種の誤差を表す． • これはTD誤差と呼ばれ，強化学習を通じてさまざまな形で⾒られる． • 𝛿. 𝑡 = 𝑅./0 + 𝛾𝑉 𝑆./0 − 𝑉 𝑆. • 各時刻のTD 誤差は，その時点で⾏われた推定値の誤差である． • 𝛿. は時刻𝑡 + 1で得られる𝑉(𝑆. )の誤差である．

TD誤差の合計 • 配列𝑉がエピソード中に変化しない場合 (モンテカルロ法ではエピソード全体 をサンプルするため𝑉は変化しない)，モンテカルロ誤差はTD誤差の合計とし て書くことができる． 𝐺' − 𝑉 𝑆' = 𝑅'(# + 𝛾𝐺'(# − 𝑉 𝑆' + 𝛾𝑉 𝑆'(# − 𝛾𝑉 𝑆'(# = 𝑅'(# + 𝛾𝑉 𝑆'(# − 𝑉 𝑆' + 𝛾𝐺'(# − 𝛾𝑉 𝑆'(# = 𝛿' + 𝛾 𝐺'(# − 𝑉 𝑆'(# = 𝛿' + 𝛾 𝑅'($ + 𝛾𝐺'($ − 𝑉 𝑆'(# + 𝑉 𝑆'(# %&# = 𝛿' + 𝛾𝛿'(# + 𝛾 $𝛿'(# + ⋯ + 𝛾 %&'&#𝛿%&'&# + 𝛾 %&' 0 − 0 = f 𝛾 :&#𝛿: :b' • TD(0) のように𝑉がエピソード中に更新される場合，この恒等式は正しくない が，ステップサイズが⼩さい場合はその後もおおよそ保持されるだろう． • この恒等式の⼀般化はTD学習の理論とアルゴリズムにおいて重要な役割を果 たす．

TDの利点 • TD法はDP法に対し，環境のモデル（報酬と次の状態の確率分布）を必要としない 利点がある． • モンテカルロ法に対するTD 法の最も明らかな利点は，TD法がオンラインで完全に incrementalな⽅式で⾃然に実装できる点である． • モンテカルロ法では，収益が分かるのはエピソードの終了まで待たなければならないが， TD法では待つ必要があるのは 1 タイムステップだけである． • TD(0) 法は，任意の固定⽅策𝜋に対して， • ⼀定のステップサイズパラメーターが⼗分に⼩さい場合，𝑣' はconvergence in meanで収 束する． • 通常の確率的近似条件に従いステップサイズパラメーターが減少する場合，convergence ] V with probability 1で𝑣' に収束する．(∑] [\+ 𝛼[ 𝑎 = ∞, ∑[\+ 𝛼[ 𝑎 < ∞) • ことが保証されている． • TD⼿法とモンテカルロ⼿法の両⽅が正しい予測に漸近的に収束する場合，確率的 タスクでは，通常TD法の⽅がconstant-𝛼 MC法よりも速く収束する．

バッチ更新 • たとえば10エピソードまたは100タイムステップのように，有限の経験しか利 ⽤できないとする． • この場合，incremental learningの⼀般的なアプローチは，⼿法が答えに収束 するまで経験を繰り返し提⽰することである． • 近似価値関数𝑉が与えられると， 𝑉 𝑆. ← 𝑉 𝑆. + 𝛼 𝐺. − 𝑉 𝑆. または 𝑉 𝑆. ← 𝑉 𝑆. + 𝛼 𝑅./0 + 𝛾𝑉 𝑆./0 − 𝑉 𝑆. で指定された増分は⾮終端状態を 訪問したタイムステップ𝑡ごとに計算されるが，価値関数はすべての増分の合 計により1回だけ変更される． • その後，価値関数が収束するまで，新しい全体的な増分を計算するため利⽤可 能なすべての経験が新しい価値関数で処理される． • 更新は訓練データの完全なバッチを処理した後にのみ⾏われるため，これを バッチ更新と呼ぶ．

on-policyとoff-policy • TD予測法における，制御問題（最適⽅策を探す問題）では，⼀般化ポリシー 反復 (GPI) を⽤いる．今回は評価または予測部分にTD ⼿法を⽤いる． • TD制御法はモンテカルロ法と同様に探索と活⽤をトレードする必要性に直⾯ しており，アプローチはここでもon-policyとoff-policyの2つの主要なクラス に分類される．

Sarsa • まずはon-policy TD制御法を⾒る． • 最初のステップは，状態価値関数ではなく⾏動価値関数を学習することである． • On-policy⼿法の場合，現在の⾏動⽅策𝜋とすべての状態𝑠および⾏動𝑎について𝑞" 𝑠, 𝑎 を推定し なければならない． • 状態と⾏動のペアから状態と⾏動のペアへの遷移を考え，状態と⾏動のペアの価値を学習する． • 状態から状態への遷移を考え，状態価値を学習するケースと同⼀である． • どちらも報酬プロセスを伴うマルコフ連鎖である． • TD(0)における状態価値の更新式を⾏動価値の対応するアルゴリズムにも適⽤する． • 𝑄 𝑆L , 𝐴L ← 𝑄 𝑆L , 𝐴L + 𝛼 𝑅L*+ + 𝛾𝑄 𝑆L*+ , 𝐴L*+ − 𝑄 𝑆L , 𝐴L • この更新は，それぞれの⾮終端状態𝑆L から遷移の後⾏われる． • 𝑆L*+ が終端の場合，𝑄 𝑆L*+ , 𝐴L*+ はゼロとする． • この更新では，ある状態と⾏動のペアから次の状態と⾏動のペアへの遷移を構成する5つの要 素 𝑆L , 𝐴L , 𝑅L*+ , 𝑆L*+ , 𝐴L*+ のすべてを使⽤する． • この 5 つの要素を⽤いることから，アルゴリズムはSarsaと呼ばれる．

Sarsa • Sarsaはすべてのon-policy⼿法と同様に，⾏動⽅策𝜋について𝑞! を継続的に推 on-policy 定し，同時に𝜋を𝑞! におけるgreedy⽅策に変更する． • Sarsaの制御アルゴリズムの⼀般的な形式を次のスライドに⽰す． • Sarsaアルゴリズムの収束特性は，𝑄に対する⽅策の依存性の性質に依る． • 例えば，𝜀-greedyまたは𝜀-soft⽅策を使ったとする． • すべての状態と⾏動のペアが無限回アクセスされ，極限で⽅策はgreedy⽅策に収束 する限り(たとえば𝜀 = 1/𝑡の𝜀-greedy⽅策) ，Sarsaはconvergence with probability 1で最適⽅策と最適⾏動価値関数に収束する．

Sarsa (on-policy TD control) for estimating 𝑄 ≈ 𝑞∗ Algorithm parameters: step size 𝛼 ∈ 0, 1 , small 𝜀 > 0 Initialize 𝑄(𝑠, 𝑎), for all 𝑠 ∈ 𝑆 = , 𝑎 ∈ 𝐴 𝑠 , arbitrarily except that 𝑄 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙,⋅ = 0 価値関数を任意の値で初期化するが，終端状態の価値だけ0とする． Loop for each episode: Initialize 𝑆 状態𝑆のときの⾏動を価値関数𝑄から⽅策に基づき⽣成する． Choose 𝐴 from 𝑆 using policy derived from 𝑄 (e.g., 𝜀-greedy) Loop for each step of episode: Take action 𝐴, observe 𝑅, 𝑆 - ⾏動𝐴をとり報酬𝑅と次の状態𝑆 . を観測する． . のときの⾏動を価値関数𝑄か Choose 𝐴- from 𝑆 - using policy derived from 𝑄 (e.g., 𝜀-greedy) 状態𝑆 ら⽅策に基づき⽣成する． 𝑄 𝑆, 𝐴 ← 𝑄 𝑆, 𝐴 + 𝛼 𝑅 + 𝛾𝑄 𝑆 - , 𝐴- − 𝑄 𝑆, 𝐴 状態を次の状態にする． 𝑆 ← 𝑆 - ; 𝐴 ← 𝐴- ; until 𝑆 is terminal 状態が終端状態になるまでループを続ける． Sarsaは⾏動価値関数を推定する⼿法だが，その推定値に基づき𝜀-greedyな⽅策を求まる． 価値関数が更新されるたびに⽅策も改善されるためon-policyである．

Q-leaning: Off-policy TD control • Q-learning (Watkins、1989)はoff-policy TD制御アルゴリズムである． • 𝑄 𝑆. , 𝐴. ← 𝑄 𝑆. , 𝐴. + 𝛼 𝑅./0 + 𝛾max 𝑄 𝑆./0 , 𝑎 − 𝑄 𝑆. , 𝐴. Q • Q-learninでは，⾏動価値関数𝑄は，⽅策とは無関係に最適な⾏動価値関数であ る𝑞∗ を直接近似する． ⾏動価値関数が最⼤値をとる⾏動を採⽤す る(greedy⽅策)ためoff policyである． • 正しく収束するために必要なのは，すべての状態と⾏動のペアが更新され続け ることである．この仮定とステップサイズパラメタ列に対する通常の確率近似 条件の変形により，convergence with probability 1で𝑄は𝑞∗ に収束することが ⽰されている．

Q-learning (off-policy TD control) for estimating 𝜋 ≈ 𝜋∗ Algorithm parameters: step size 𝛼 ∈ 0, 1 , small 𝜀 > 0 Initialize 𝑄 𝑠, 𝑎 , for all 𝑠 ∈ 𝑆 = , 𝑎 ∈ 𝐴 𝑠 , arbitrarily except that 𝑄(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙,⋅) = 0 価値関数を任意の値で初期化するが，終端状態の価値だけ0とする． Loop for each episode: Initialize 𝑆 状態𝑆のときの⾏動を価値関数𝑄から⽅策に基づき⽣成する． Loop for each step of episode: Choose 𝐴 from 𝑆 using policy derived from 𝑄 (e.g., 𝜀-greedy) Take action 𝐴, observe 𝑅, 𝑆 - ⾏動𝐴をとり報酬𝑅と次の状態𝑆 . を観測する． 𝑄 𝑆, 𝐴 ← 𝑄 𝑆, 𝐴 + 𝛼[𝑅 + 𝛾 max 𝑄 𝑆 - , 𝑎 − 𝑄 𝑆, 𝐴 8 𝑆 ← 𝑆until S is terminal 状態が終端状態になるまでループを続ける． Q-learningも⾏動価値関数を推定する⼿法だが，その推定値に基づき𝜀-greedyな⽅策が求ま る．しかし，価値関数の更新においてgreedy⽅策（価値関数が最⼤になる⾏動を取る）を採 ⽤しているためoff-policyである．

Expected Sarsa • Expected Sarsaは，次の状態とアクションのペアの最⼤値の代わりに現在の⽅策に基づいた 期待値を使⽤したQ-learningである． • 更新式は次のようになる． 𝑄 𝑆< , 𝐴< ← 𝑄 𝑆< , 𝐴< + 𝛼[𝑅<=> + 𝛾𝐸" 𝑄 𝑆<=> , 𝐴<=> ∣ 𝑆<=> − 𝑄 𝑆< , 𝐴< ] ← 𝑄 𝑆< , 𝐴< + 𝛼[𝑅<=> + 𝛾 ) 𝜋 𝑎 ∣ 𝑆<=> 𝑄 𝑆<=> , 𝐴<=> − 𝑄 𝑆< , 𝐴< ] 8 • 式以外はQ-learningと同じスキーマに従う． • SarsaのTD誤差は確率的に決まるが， Expected Sarsaでは決定論的に決まる． • Expected Sarsaは確率的なブレがないため，同じ経験の量であればExpected SarsaはSarsaより わずかに性能が良いだろう． • Expected Sarsaはon-policyとoff-policyの両⽅で使⽤できる． 𝜋がgreedyであれば，Qの期待値はQの最⼤値と なり，Expected SarsaはQ-learningになる． • 例えば，ターゲット⽅策𝜋がgreedy⽅策であるのに対し，⾏動⽅策はより探索的であるとする． そうすると，Expected SarsaはまさにQ-learningである． • この意味で，Expected Sarsa は，Sarsaを確実に改善しながらQ-learningを包含し⼀般化する．

Maximization Bias and Double Learning • Q-learningでは，ターゲット⽅策は現在の⾏動価値から求まるgreedy⽅策であ る． • Sarsaでは，多くの場合，⽅策は𝜀-greedyである． • これらのアルゴリズムでは，推定価値の最⼤値が暗黙のうちに最⼤価値の推定 値として使われる． • 真の価値𝑞 𝑠, 𝑎 はすべてゼロである場合を考える．推定価値𝑄 𝑠, 𝑎 は不確実で あるため，ゼロより上にも下にもなり得る．このとき，真の最⼤価値はゼロで あるが，最⼤価値の推定値は正であり，正のバイアスとなる． • これを最⼤化バイアスと呼ぶ。

最⼤化バイアスの回避とDouble learning • 推定価値の最⼤値を最⼤価値の推定値として使⽤すると正の最⼤化バイアスが発⽣する． • ⼀つの⾒⽅として，この問題は，最⼤化する⾏動の決定とその価値の推定の両⽅のために同じ サンプルが⽤いられることに起因する． ⼀つのサンプルだけ⽤いた場合，間違った価値から間違った⽅策が求まり，その⽅策から価値が求まる，といったことが起こる．これは間違った⾏ 動の過⼤評価となる．しかし，複数のサンプルから複数の価値関数を推定し，それらを⽤い⽅策を求めれば，このようなことは起こらない． • ここで，サンプルを2つのセットに分割し，それらを2つの独⽴した推定価値𝑄+ 𝑎 ，𝑄V 𝑎 を 学習するために使⽤するとする． • ⼀⽅の推定価値𝑄+ を⽤い最⼤化する⾏動𝐴∗ = arg max 𝑄+ 𝑎 を決定し，もう⼀⽅の推定価値𝑄V ( を⽤いその価値の推定値𝑄V 𝐴∗ = 𝑄V arg max 𝑄+ 𝑎 を求める． ( • また，𝑄+ 𝐴∗ = 𝑄+ arg max 𝑄V 𝑎 り返す事もできる． ( を求めるために，2つの推定値の役割を逆にして処理を繰 • これがdouble learningの考え⽅である． • 2 つの推定値を学習するが，各更新で1つの推定値のみが更新される．

Double Q-learning • Double learningの考え⽅は，MDPのアルゴリズムにも適⽤できる． • Q-learningに類似したdouble learningであるDouble Q-learningは，各ステッ プでコインを投げることにより，時間ステップを2つに分割する． • コインが表になった場合，更新は次のようになる． コイントスにより更新する価値関数を切り替え ることで，サンプルを2つに分割している． • 𝑄0 𝑆. , 𝐴. ← 𝑄0 𝑆. , 𝐴. + 𝛼 𝑅./0 + 𝛾𝑄H 𝑆./0 , arg max 𝑄0 𝑆./0 , 𝑎 Q − 𝑄0 𝑆. , 𝐴. • Double Q-learningでは，2つの近似価値関数は完全に対称的に扱われる． • ⾏動⽅策では，両⽅の⾏動価値の推定値を使⽤できる． • たとえば，Double Q-learningの𝜀-greedyポリシーは2つの⾏動価値の推定値の平均 （または合計）を⽤いることができる． • SarsaとExpected SarsaのDouble learningもある．

Double Q-learning, for estimating 𝑄j ≈ 𝑄k ≈ 𝑞∗

Algorithm parameters: step size 𝛼 ∈ 0, 1 , small " > 0
Initialize 𝑄> 𝑠, 𝑎 and 𝑄W 𝑠, 𝑎 , for all 𝑠 ∈ 𝑆=, 𝑎 ∈ 𝐴 𝑠 , such that 𝑄 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙,⋅ = 0
価値関数を任意の値で初期化するが，終端状態の価値だけ0とする．

Loop for each episode:
Initialize 𝑆
Loop for each step of episode:
状態𝑆のときの⾏動を価値関数の和𝑄% + 𝑄6 から 𝜀-greedy⽅策に基づき⽣成する．
Choose 𝐴 from 𝑆 using the policy 𝜀-greedy in 𝑄> + 𝑄W
Take action 𝐴, observe 𝑅, 𝑆With 0.5 probabilility: 同じ確率で 𝑄% と𝑄6 のどちらかを更新する．
𝑄> 𝑆, 𝐴 ← 𝑄> 𝑆, 𝐴 + 𝛼 𝑅<=> + 𝛾𝑄W 𝑆, arg max 𝑄> 𝑆, 𝑎 − 𝑄> 𝑆, 𝐴
8

else:
𝑄W 𝑆, 𝐴 ← 𝑄W 𝑆, 𝐴 + 𝛼 𝑅<=> + 𝛾𝑄> 𝑆, arg max 𝑄W 𝑆, 𝑎
8
𝑆 ← 𝑆until 𝑆 is terminal 状態が終端状態になるまでループを続ける．

− 𝑄W 𝑆, 𝐴

バックアップ図 状態 ⾏動 最⼤値を取る 期待値を取る 状態 TD(0) Sarsa Q-learning Expected Sarsa