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

強化学習3 モンテカルロ法，TD学習 公立小松大学 藤田 一寿 Ver. 20250615

モンテカルロ法

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

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

モンテカルロ予測 • ある方策に従い状態𝑠を経験することによって得られたエピソードが与えられた ときに，方策𝜋の下での状況の価値𝑣𝜋 𝑠 を推定したい． • このとき用いることができる手法として，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 𝑉 ≈ 𝑣𝜋 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 , 𝐴0 , 𝑅1 , 𝑆1 , 𝐴1 , 𝑅2 , … , 𝑆𝑇−1 , 𝐴 𝑇−1 , 𝑅𝑇 エピソード:エージェントが初期状態から終状態まで行 動したときの行動や結果の記録 𝐺←0 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0 : 𝐺 ← 𝛾𝐺 + 𝑅𝑡+1 unless 𝑆𝑡 appears in 𝑆0 , 𝑆1 , … , 𝑆𝑡−1 : 𝑆𝑡 が𝑆1 , 𝑆2 , … , 𝑆𝑡−1の中になければ，つまり初めて状態𝑆𝑡 = 𝑠が出現した時． Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆𝑡 当たり前だが，エピソード内で𝑠を初めて訪問できるのは１度だけなので， エピ ソードごとに1回状態𝑠のときの𝐺が追加される． 𝑉 𝑆𝑡 ← average 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆𝑡 )

every-visit MC prediction, for estimating 𝑉 ≈ 𝑣𝜋 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 , 𝐴0 , 𝑅1 , 𝑆1 , 𝐴1 , 𝑅2 , … , 𝑆𝑇−1 , 𝐴 𝑇−1 , 𝑅𝑇 𝐺←0 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0 : 𝐺 ← 𝛾𝐺 + 𝑅𝑡+1 Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆𝑡 𝑠を訪問するたびに，𝑠のときの𝐺が追加される． 𝑉 𝑆𝑡 ← average 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆𝑡 )

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

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

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

行動価値のモンテカルロ推定 • 唯一の厄介な点は，多くの状態と行動のペアが一度も訪問されない可能性があるこ とである． • もし，方策が決定論的であるのならば，可能な行動のうち一つしか選ばれないため （探索されないため），他の行動の推定値は向上しない．これは深刻な問題である ． • 継続的な探索を保証する一つとして，各エピソードを状態と行動から開始し，その ペアを非ゼロの確率で選ぶ方法がある． • これにより，エピソード数が無限の極限において，すべての状態と行動のペアが無限回訪問 されることが保証される． • これをExploring starts（開始探索）の仮説と呼ぶ． • 探索開始の仮説が有効な場合もあるが，一般的にこれに頼ることはできない． • 特に，環境との相互作用から直接学習する場合． • すべてのペアが出現することを保証する最も一般的なアプローチは，各状態におけ る行動を非ゼロの確率で選ぶ方策を考えることである．

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

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

方策改善定理 • 方策改善におけるgreedyな方策 𝜋 𝑠 は，行動価値関数𝑞 𝑠, 𝑎 を用い次のように書ける． • 𝜋 𝑠 = arg max 𝑞 𝑠, 𝑎 𝑎 • 𝑘回目の方策評価で用いた方策を𝜋𝑘 とすると，行動価値関数𝑞𝜋𝑘 と書ける． 方策改善は𝑞𝜋𝑘 に基 づき，𝑘 + 1回目の方策評価で使う𝜋𝑘+1 を求める． • 方策改善定理を適用すると 𝑞𝜋𝑘 についてGreedyな行動を選択をしている． 𝑞𝜋𝑘 𝑠, 𝜋𝑘+1 𝑠 = 𝑞𝜋𝑘 𝑠, arg max 𝑞𝜋𝑘 𝑠, 𝑎 𝑎 = max 𝑞𝜋𝑘 𝑠, 𝑎 𝑎 ≥ 𝑞𝜋𝑘 𝑠, 𝜋𝑘 𝑠 𝜋𝑘 𝑠 は 𝜋𝑘+1 𝑠 より悪いか同等の方策 ≥ 𝑣𝜋𝑘 𝑠 • つまり，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 𝑆0 ∈ 𝑆, 𝐴0 ∈ 𝐴 𝑆𝑜 randomly such that all pairs have probabililty > 0 Generate an episode from 𝑆0 , 𝐴0 , following 𝜋: 𝑆0 , 𝐴0 𝑅1 , … , 𝑆𝑡−1 , 𝐴𝑡−1 , 𝑅𝑇 方策𝜋に基づき𝑇までの状態，行動，報酬を生成する． 𝐺←0 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … 0: 𝐺 ← 𝛾𝐺 + 𝑅𝑡+1 Unless the pair 𝑆𝑡 , 𝐴𝑡 appears in 𝑆0 , 𝐴0 , 𝑆1 , 𝐴1 , … , 𝑆𝑡−1 , 𝐴𝑡−1 : Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆𝑡 , 𝐴𝑡 これまで生成したエピソードから得られた収益𝐺の平均をとり，行 𝑄 𝑆𝑡 , 𝐴𝑡 ←average(𝑅𝑒𝑡𝑢𝑟𝑛𝑠 𝑆𝑡 , 𝐴𝑡 ) 動価値関数を求める． 𝜋 𝑆𝑡 ← arg max 𝑄 𝑆𝑡 , 𝑎 𝑎 𝑆𝑡 , 𝐴𝑡 が𝑆0 , 𝐴0 , 𝑆1 , 𝐴1 , … , 𝑆𝑡−1 , 𝐴𝑡−1 になければ， つまり ， 𝑆𝑡 , 𝐴𝑡 のペアがエピソード内で初め て現れたのなら． 行動価値関数から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な行動には最小の選択確率 𝜀 𝐴 𝑠 • 𝜀 𝐴 𝑠 が与えられ，greedyな行動には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): 方策𝜋に基づき エピソードを生成する．𝐴0 は 𝜀-soft方策に基づき決める．𝑆0 はタ Generate an episode following 𝜋: 𝑆0 𝐴0 𝑅1 , . . . , 𝑆𝑇−1 , 𝐴 𝑇−1 , 𝑅𝑇 スクによる制約に従い設定する．ランダムかもしれないし指定されているかも しれない． 𝐺←0 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0: 𝐺 ← 𝛾𝐺 + 𝑅𝑡+1 Unless the pair 𝑆𝑡 , 𝐴𝑡 appears in 𝑆0 , 𝐴0 , 𝑆1 , 𝐴1 , … , 𝑆𝑡−1 , 𝐴𝑡−1 : Append 𝐺 to 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆𝑡 , 𝐴𝑡 ) 𝑆𝑡 , 𝐴𝑡 が𝑆0 , 𝐴0 , 𝑆1 , 𝐴1 , … , 𝑆𝑡−1 , 𝐴𝑡−1 になければ，つまり ， 𝑆𝑡 , 𝐴𝑡 のペアがエピソード内で初めて現れたのなら． 𝑄 𝑆𝑡 , 𝐴𝑡 ← average(𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆𝑡 , 𝐴𝑡 )) これまで生成したエピソードから得られた収益𝐺の平均をとり，行動価値関数を求める． 𝐴∗ ← arg max 𝑄 𝑆𝑡 , 𝑎 (with ties broken arbitrarily) 行動価値関数からgreedyな行動を求める． 𝑎 For all 𝑎 ∈ 𝐴(𝑆𝑡 ): 𝜋 𝑎 ∣ 𝑆𝑡 = ቐ 求めたgreedyな行動から𝜀-soft方策を作成する． 1 − 𝜀 + 𝜀/|𝐴(𝑆𝑡 )|, if 𝑎 = 𝐴∗ 𝜀/|𝐴(𝑆𝑡 )| if 𝑎 ≠ 𝐴∗

方策改善定理 • 行動価値関数𝑞𝜋 に関する𝜀-greedy方策は𝜀-soft方策𝜋よりも改善されていることが方策改 善定理によって保証されている． ′ ′ 𝑞𝜋 𝑠, 𝜋 𝑠 :状態𝑠, 方策𝜋 𝑠 のときの価値関数 𝑞𝜋 𝑠, 𝑎 :状態𝑠, 行動𝑎のときの価値関数 • 𝜋′を𝜀-greedy方策とする． 𝑞𝜋 𝑠, 𝜋 ′ 𝑠 = ෍ 𝜋 ′ 𝑎 𝑠 𝑞𝜋 𝑠, 𝑎 𝜀 𝜀-greedy方策では， 𝐴 𝑆 𝑎 = ෍ 𝑎≠arg max 𝑞𝜋 𝑠,𝑎 𝜀 𝜀 𝑞𝜋 𝑠, 𝑎 + 1 − 𝜀 + 𝐴 𝑆𝑡 𝐴 𝑆𝑡 max 𝑞𝜋 𝑠, 𝑎 𝑎 𝑎 𝜀 =෍ 𝑞 𝑠, 𝑎 + 1 − 𝜀 max 𝑞𝜋 𝑠, 𝑎 𝑎 𝐴 𝑆𝑡 𝜋 外を選び，1 − 𝜀 + 𝐴𝑆 𝑡 𝜀 𝐴 𝑆𝑡 の確率でgreedyな行動以 𝑡 𝜀 × 𝐴 𝑆𝑡 − 𝐴 𝑆 𝑡 =1−𝜀 の確率でgreedyな行動(max 𝑞𝜋 𝑠, 𝑎 )を選ぶ． 𝑎 𝑎 𝜀 𝜋 𝑎 𝑠 − 𝜀 𝐴 𝑆𝑡 = ෍ 𝑞𝜋 𝑠, 𝑎 + 1 − 𝜀 ෍ max 𝑞𝜋 𝑠, 𝑎 𝑎 𝐴 𝑆𝑡 1−𝜀 𝑎 𝑎 𝜀 𝜋 𝑎 𝑠 − 𝜀 𝐴 𝑆𝑡 ≥ ෍ 𝑞𝜋 𝑠, 𝑎 + 1 − 𝜀 ෍ 𝑞𝜋 𝑠, 𝑎 𝐴 𝑆𝑡 1−𝜀 𝑎 = ෍ 𝜋 𝑎 𝑠 𝑞𝜋 𝑠, 𝑎 = 𝑣𝜋 𝑠 𝑎 𝑎 σ𝑎 𝜋 𝑎𝑠 − 1−𝜀 𝜀 𝐴 𝑆𝑡 = 1 詳しくは次のスライドで． この式は行動価値関数の値がすべて等しいとき(𝑞𝜋 𝑠, 𝑎 = max 𝑞𝜋 𝑠, 𝑎 )に等号が成り立つ． 𝑎 さらにこの式から，𝜋 ′ 𝑠 = 𝜋 𝑎 𝑠 のときも等号が成り立つ．また，𝜀-greedy方策𝜋′は， 𝜀-soft方 策と同等かより良いことも分かる．

式展開の詳細 ෍𝜋 𝑎 𝑠 = 1 𝑎 ෍𝜋 𝑎 𝑠 − 𝜀 = 1 − 𝜀 𝑎 𝜀 =1−𝜀 ෍ 𝜋 𝑎 𝑠 − 𝐴 𝑆𝑡 𝑎∈𝐴 𝑆𝑡 𝜀 𝜋 𝑎 𝑠 − 𝐴 𝑆𝑡 =1 ෍ 1−𝜀 𝑎∈𝐴 𝑆𝑡 𝜀 𝜋 𝑎 𝑠 − 𝜀 𝐴 𝑆𝑡 ෍ 𝑞𝜋 𝑠, 𝑎 + 1 − 𝜀 ෍ 𝑞𝜋 𝑠, 𝑎 𝐴 𝑆𝑡 1−𝜀 𝑎 =෍ 𝑎 = ෍ 𝜋 𝑎 𝑠 𝑞𝜋 𝑠, 𝑎 𝑎 𝑎 𝜀 𝜀 +𝜋 𝑎 𝑠 − 𝐴 𝑆𝑡 𝐴 𝑆𝑡 𝑞𝜋 𝑠, 𝑎

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

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

Importance sampling • ここでは𝜋が不変で且つ与えられている場合の予測問題を検討する． • ほとんどすべての off-policy法は，importance samplingを利用する． • これは，ある分布からのサンプルが与えられた場合に期待値を推定するための一般 的な手法である． • Importance-sampling ratioと呼ばれる，ターゲット方策および行動方策の下 で発生するtrajectoryが発生する相対確率に従って報酬に重み付けを行うこと により， importance samplingを学習に適用する． • 開始状態𝑆𝑡 が与えられると，ターゲット方策𝜋における，その後の状態と行動 のtrajectory 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 の発生確率は次のようになる． 𝑃 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 ∣ 𝑆𝑡 , 𝐴𝑡:𝑇−1 ∼ 𝜋 = 𝜋 𝐴𝑡 𝑆𝑡 𝑃 𝑆𝑡+1 𝑆𝑡 , 𝐴𝑡 𝜋 𝐴𝑡+1 𝑆𝑡+1 … 𝑃 𝑆𝑇 𝑆𝑇−1 , 𝐴 𝑇−1 𝑇−1 = ෑ 𝜋 𝐴𝑘 𝑆𝑘 𝑃 𝑆𝑘+1 𝑆𝑘 , 𝐴𝑘 𝑘=𝑡 𝐴𝑡:𝑇−1 ∼ 𝜋は方策𝜋に基づき生 成される一連の行動を意味す る． 𝐴𝑡:𝑇−1 は条件付き確率の 条件に入っているが， 𝐴𝑡:𝑇−1 は確率分布𝜋から生成される．

Importance-sampling ratio • ターゲット方策と行動方策の下での状態と行動のtrajectoryの相対確率 (Importance-sampling ratio) は次のようになる． ς𝑇−1 ς𝑇−1 𝑘=𝑡 𝜋 𝐴𝑘 𝑆𝑘 𝑃 𝑆𝑘+1 𝑆𝑘 , 𝐴𝑘 𝑘=𝑡 𝜋 𝐴𝑘 𝑆𝑘 𝜌𝑡:𝑇−1 =ሶ 𝑇−1 = 𝑇−1 ς𝑘=𝑡 𝑏 𝐴𝑘 𝑆𝑘 𝑃 𝑆𝑘+1 𝑆𝑘 , 𝐴𝑘 ς𝑘=𝑡 𝑏 𝐴𝑘 𝑆𝑘 • Importance-sampling ratioは2つの方策と行動と状態の系列のみに依存する． • ターゲット方策の元での期待収益 (価値) を推定したいが，得られるのは行動 方策による収益𝐺𝑡 だけである． • これらの収益は誤った期待値 𝐸 𝐺𝑡 ∣ 𝑆𝑡 = 𝑠 = 𝑣𝑏 𝑠 を持つため，𝑣𝜋 を得るため に，これらの収益を平均できない． • ここで比率𝜌𝑡:𝑇−1 を正しい期待価値を持つ収益に変換するために用いる． 𝐸 𝜌𝑡:𝑇−1 𝐺𝑡 ∣ 𝑆𝑡 = 𝑠 = 𝑣𝜋 𝑠

Importance-sampling ratio 方策𝑏の下でtrajectoryが生じる確率は 𝑃 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 ∣ 𝑆𝑡 , 𝐴𝑡:𝑇−1 ∼ 𝑏 = 𝑏 𝐴𝑡 𝑆𝑡 𝑃 𝑆𝑡+1 𝑆𝑡 , 𝐴𝑡 𝑏 𝐴𝑡+1 𝑆𝑡+1 … 𝑃 𝑆𝑇 𝑆𝑇−1 , 𝐴 𝑇−1 𝑇−1 = ෑ 𝑏 𝐴𝑘 𝑆𝑘 𝑃 𝑆𝑘+1 𝑆𝑘 , 𝐴𝑘 𝑘=𝑡 方策𝑏の下での収益の収益の期待値は 𝐸𝑏 𝐺𝑡 ∣ 𝑆𝑡 = 𝑠 = ෍ 𝑃{𝐺𝑡 ∣ 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 }𝑃 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 ∣ 𝑆𝑡 , 𝐴𝑡:𝑇−1 ∼ 𝑏 𝐺𝑡 𝐺𝑡 𝑇−1 = ෍ 𝑃{𝐺𝑡 ∣ 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 } ෑ 𝑏 𝐴𝑘 𝑆𝑘 𝑃 𝑆𝑘+1 𝑆𝑘 , 𝐴𝑘 𝐺𝑡 よって 𝐺𝑡 𝑘=𝑡 収益𝐺𝑡 は trajectory ごとに存在するた め，𝐺𝑡 の生じる確率は trajectory を条 件とした条件付き確率で書ける． 𝑇−1 ς𝑇−1 𝑘=𝑡 𝜋 𝐴𝑘 𝑆𝑘 𝐸𝑏 𝜌𝑡:𝑇−1 𝐺𝑡 ∣ 𝑆𝑡 = 𝑠 = ෍ 𝑇−1 𝑃{𝐺𝑡 ∣ 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 } ෑ 𝑏 𝐴𝑘 𝑆𝑘 𝑃 𝑆𝑘+1 𝑆𝑘 , 𝐴𝑘 𝐺𝑡 ς𝑘=𝑡 𝑏 𝐴𝑘 𝑆𝑘 𝐺𝑡 𝑘=𝑡 𝑇−1 = ෍ 𝑃{𝐺𝑡 ∣ 𝐴𝑡 , 𝑆𝑡+1 , 𝐴𝑡+1 , … , 𝑆𝑇 } ෑ 𝜋 𝐴𝑘 𝑆𝑘 𝑃 𝑆𝑘+1 𝑆𝑘 , 𝐴𝑘 𝐺𝑡 = 𝐸𝜋 𝐺𝑡 ∣ 𝑆𝑡 = 𝑠 = 𝑣𝜋 𝑠 𝐺𝑡 𝑘=𝑡

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

2つのimportance-sampling • 𝑣𝜋 𝑠 を推定するため，単純に収益をimportance-sampling ratioでスケールし， 結果を平均する． • 𝑉 𝑠 =ሶ σ𝑡∈𝒯(𝑠) 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 |𝒯(𝑠)| • このようにimportance samplingが単純な平均として行われる場合，これを ordinary importance samplingと呼ぶ． • 重要な代替手法はである加重平均を使用するweighted importance sampling である．これは次のように定義される． σ𝑡∈𝒯(𝑠) 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 • 𝑉 𝑠 =ሶ σ 𝑡∈𝒯(𝑠) 𝜌𝑡:𝑇 𝑡 −1 • ただし，分母がゼロの場合はゼロとする．

2つのimportance-sampling • ordinary importance samplingとweighted importance samplingの2 種類のimportance-samplingを 理解するために，状態𝑠から一つの収益を観察した後のfirst-visit methodによる推定値を考える． • weighted importance-samplingでは，単一の収益を得たときの𝜌𝑡:𝑇 𝑡 −1は分子と分母で相殺されるた め，推定値は比率に関係なく観測された収益と等しくなる (比率が非ゼロであると仮定して)． 𝜌 • 𝑉 𝑠 = 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 𝑡:𝑇 𝑡 −1 = 𝐺𝑡 • この収益が観測された唯一のものであることを考えると，これは合理的な推定値ではあるが，その期 待値は𝑣𝜋 (𝑠)ではなく𝑣𝑏 (𝑠)であり，この統計的な意味ではバイアスがある． • 対照的に，ordinary importance samplingのfirst-visitバージョンは，期待値において常に𝑣𝜋 (𝑠) であ る(バイアスはない) が，極端になる可能性がある． • 𝑉 𝑠 = 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 |𝒯(𝑠)| = 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 • 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 によってスケーリ ングされ次のように単純に平均化される． • 𝑉 𝑠 =ሶ σ𝑡∈𝒯(𝑠) 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 |𝒯(𝑠)| • これは，次のようにincremental methodsにおいて使用することができる． • 新たに観測𝐺𝑡 を観測したときの新たな価値𝑉𝑛+1 𝑠 は 𝑉𝑛+1 𝑠 =ሶ = = 1 𝒯𝑛+1 𝑠 1 𝒯𝑛+1 𝑠 = 𝑉𝑛 𝑠 + σ𝑡∈𝒯𝑛+1 (𝑠) 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 𝒯𝑛+1 𝑠 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 + = 1 𝒯𝑛+1 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 + ෍ 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 𝑡∈𝒯𝑛 (𝑠) 𝒯𝑛+1 𝑠 − 1 ෍ 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 𝒯𝑛+1 𝑠 − 1 𝑡∈𝒯𝑛 (𝑠) 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 + 𝒯𝑛+1 𝑠 − 1 𝑉𝑛 𝑠 1 𝒯𝑛+1 𝑠 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 − 𝑉𝑛 𝑠 新たに観測されたので，時刻𝑡が 𝒯𝑛 (𝑠)に追加される．追加された 𝒯𝑛 (𝑠)を 𝒯𝑛+1 (𝑠)とする．1つ追加 されたので 𝒯𝑛 (𝑠) = 𝒯𝑛+1 (𝑠) − 1である．

Off-policy MC prediction • weighted importance-samplingを使用するケースでは，収益の加重平均を形成する必要があり，少し異なる incremental algorithmが必要となる． • 収益列𝐺1 , 𝐺2 , … , 𝐺𝑛−1 があるとする．ただし，すべて同じ状態で開始され，それぞれに対応するランダムな重 み𝑊𝑖 （例えば𝑊𝑖 = 𝜌𝑡𝑖:𝑇 𝑡𝑖 −1 ）がある．この時，価値を次のように推定したい． • 𝑉𝑛 =ሶ σ𝑛−1 𝑘=1 𝑊𝑘 𝐺𝑘 σ𝑛−1 𝑘=1 𝑊𝑘 , 𝑛≥2 • そして，単一の収益𝐺𝑛 を取得すると同時に価値を最新の状態に保ちたい．𝑉𝑛 を更新することに加え，最初の 𝑛個の収益に与えられた重みの累積和𝐶𝑛 も状態ごとに維持しなければならない．以上を満たす𝑉𝑛 の更新ルール は次のとおりである． 𝑊 • 𝑉𝑛+1 =ሶ 𝑉𝑛 + 𝐶 𝑛 𝐺𝑛 − 𝑉𝑛 𝑛 • 𝐶𝑛+1 =ሶ 𝐶𝑛 + 𝑊𝑛+1 • ここで，𝐶0 =ሶ 0 (𝑉1 は任意なので指定する必要はない)． • 次のスライドにモンテカルロ方策評価のための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 𝑏: 𝑆0 , 𝐴0 , 𝑅1 , … , 𝑆𝑇−1 , 𝐴 𝑇−1 , 𝑅𝑇 𝐺←0 𝑊←1 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, … , 0, while 𝑊 ≠ 0: 𝑊 = 0になると，その後値が更新されない． 収益を計算する． 𝐺 ← 𝛾𝐺 + 𝑅𝑡+1 𝐶 𝑆𝑡 , 𝐴𝑡 ← 𝐶 𝑆𝑡 , 𝐴𝑡 + 𝑊 重みの累積和を計算する． 𝑊 𝑄 𝑆𝑡 , 𝐴𝑡 ← 𝑄 𝑆𝑡 , 𝐴𝑡 + 𝐺 − 𝑄 𝑆𝑡 , 𝐴𝑡 行動価値を計算する． 𝐶 𝑆𝑡 ,𝐴𝑡 𝜋 𝐴𝑡 𝑆𝑡 𝑊←𝑊 重みを計算する． 𝑏 𝐴𝑡 𝑆𝑡 このアルゴリズムで得られるのはQである．

式展開 σ𝑛𝑘=1 𝑊𝑘 𝐺𝑘 𝑊𝑛 𝐺𝑛 + σ𝑛−1 1 𝑘=1 𝑊𝑘 𝐺𝑘 𝑉𝑛+1 = = = σ𝑛𝑘=1 𝑊𝑘 𝐶𝑛 𝐶𝑛 = 1 𝑊𝑛 𝐺𝑛 + 𝑉𝑛 𝐶𝑛 − 𝑊𝑛 𝐶𝑛 = 𝑉𝑛 + 𝑛−1 𝐶𝑛−1 𝑊𝑛 𝐺𝑛 + ෍ 𝑊𝑘 𝐺𝑘 𝐶𝑛−1 𝑘=1 𝑊𝑛 𝐺𝑛 − 𝑉𝑛 𝐶𝑛 𝐶𝑛+1 =ሶ 𝐶𝑛 + 𝑊𝑛+1 𝐶𝑛 =ሶ 𝐶𝑛−1 + 𝑊𝑛 𝐶𝑛−1 = 𝐶𝑛 − 𝑊𝑛 𝑛 𝐶𝑛 = 𝑊1 + ⋯ + 𝑊𝑛 = ෍ 𝑊𝑘 𝑘=1

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) 𝑎 ターゲット方策を初期の行動価値関数に対するgreedy方策 にする．同点の場合の対処は一貫している． Loop forever (for each episode): 𝑏 ← any soft policy 𝑏を何らかのsoft policyにする． Softなら何でも良い． Generate an episode using 𝑏: 𝑆0 , 𝐴0 , 𝑅1 , … , 𝑆𝑇−1 , 𝐴 𝑇−1 , 𝑅𝑇 方策𝑏に基づき𝑇までの状態，行動，報酬を生成する． 𝐺←0 𝑊←1 Loop for each step of episode, 𝑡 = 𝑇 − 1, 𝑇 − 2, . . . , 0: 𝐺 ← 𝛾𝐺 + 𝑅𝑡+1 収益を計算する． 𝐶 𝑆𝑡 , 𝐴𝑡 ← 𝐶 𝑆𝑡 , 𝐴𝑡 + 𝑊 重みの累積和を計算する． 𝑊 𝑄 𝑆𝑡 , 𝐴𝑡 ← 𝑄 𝑆𝑡 , 𝐴𝑡 + 𝐺 − 𝑄 𝑆𝑡 , 𝐴𝑡 行動価値を計算する． 𝐶 𝑆𝑡 ,𝐴𝑡 ターゲット方策を現在の行動価値関数に対するgreedy方策 𝜋 𝑆𝑡 ← arg max 𝑄 𝑆𝑡 , 𝑎 (with ties broken consistently) にする．同点の場合の対処は一貫している． 𝑎 If 𝐴𝑡 ≠ 𝜋 𝑆𝑡 then exit inner Loop (proceed to next episode) 𝐴𝑡 が現在のgreedy行動でなければ第２のループを抜ける（ 1 重みを計算する． 𝑊←𝑊 次のエピソードを処理する）． 𝑏 𝐴𝑡 𝑆𝑡 このアルゴリズムの目的は最適なターゲット方策 𝜋 を求めることである．

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

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

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

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

Discounting-aware Importance Sampling • 次に，先を切り捨てられたimportance sampling ratioにより，フラット部分収益をスケールす る必要がある． • フラット部分収益𝐺ҧ𝑡:ℎ にはℎまでの報酬のみが含まれるため，必要なのはℎまでの確率の比だけ である． • ℎまでの確率の比しか使わないので，先が切り捨てられている． • importance sampling推定量を次のように定義する． • 𝑉 𝑠 =ሶ • 𝑉 𝑠 =ሶ ℎ−𝑡−1 𝜌 𝑇−𝑡−1 𝜌 σ𝑡∈𝒯(𝑠) 1−𝛾 σ𝑇−1 𝑡:ℎ−1 𝐺ҧ 𝑡:ℎ +𝛾 𝑡:𝑇 𝑡 −1 𝐺ҧ 𝑡:𝑇 𝑡 ℎ=𝑡+1 𝛾 |𝒯(𝑠)| ℎ−𝑡−1 𝜌 𝑇−𝑡−1 𝜌 σ𝑡∈𝒯(𝑠) 1−𝛾 σ𝑇−1 𝑡:ℎ−1 𝐺ҧ 𝑡:ℎ +𝛾 𝑡:𝑇 𝑡 −1 𝐺ҧ 𝑡:𝑇 𝑡 ℎ=𝑡+1 𝛾 ℎ−𝑡−1 𝜌 𝑇−𝑡−1 𝜌 σ𝑡∈𝒯(𝑠) 1−𝛾 σ𝑇−1 𝑡:ℎ−1 +𝛾 𝑡:𝑇 𝑡 −1 ℎ=𝑡+1 𝛾 • これら 2 つの推定量をdiscounting-aware importance sampling推定量と呼ぶ． • これらは割引率を考慮するが，𝛾 = 1のときは効果はない (off-policy推定量と同である)．

Discounting-aware Importance Sampling • Trajectoryが1つだとして • 𝑉 𝑠 = 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 と ℎ−𝑡−1 • 𝑉 𝑠 = 1 − 𝛾 σ𝑇−1 𝜌𝑡:ℎ−1 𝐺ҧ𝑡:ℎ + 𝛾 𝑇−𝑡−1 𝜌𝑡:𝑇 𝑡 −1 𝐺ҧ𝑡:𝑡+𝑇 ℎ=𝑡+1 𝛾 • を比べる． • 𝑉 𝑠 = 𝜌𝑡:𝑇 𝑡 −1 𝐺𝑡 の場合，推定量に対し𝜌𝑡:𝑇 𝑡 −1 のばらつきが与える影響が大 きいが，改良された推定量はフラット部分収益の和となっており，その係数で ある𝜌𝑡:ℎ−1 のばらつきの影響を抑えている．

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

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

Per-decision importance samplingにおける期待値の計算 𝐸 𝜌𝑡:𝑇−1 𝑅𝑡+1 = 𝐸 それぞれ独立だとすると， 𝐸 𝜌𝑡:𝑇−1 𝑅𝑡+1 = 𝐸 𝐸 𝜋 𝐴𝑘 𝑆𝑘 𝑏 𝐴𝑘 𝑆𝑘 𝜋 𝐴𝑡 𝑆𝑡 𝜋 𝐴𝑡+1 𝑆𝑡+1 𝜋 𝐴 𝑇−1 𝑆𝑇−1 … 𝑅 𝑏 𝐴𝑡 𝑆𝑡 𝑏 𝐴𝑡+1 𝑆𝑡+1 𝑏 𝐴 𝑇−1 𝑆𝑇−1 𝑡+1 𝜋 𝐴𝑡 𝑆𝑡 𝜋 𝐴𝑡+1 𝑆𝑡+1 𝑅𝑡+1 𝐸 𝑏 𝐴𝑡 𝑆𝑡 𝑏 𝐴𝑡+1 𝑆𝑡+1 …𝐸 𝜋 𝐴 𝑇−1 𝑆𝑇−1 𝑏 𝐴 𝑇−1 𝑆𝑇−1 = 1より 𝜋 𝐴𝑡 𝑆𝑡 𝑅 = 𝐸 𝜌𝑡:𝑡 𝑅𝑡+1 𝑏 𝐴𝑡 𝑆𝑡 𝑡+1 𝐸 𝜌𝑡:𝑇−1 𝐺𝑡 = 𝐸 𝜌𝑡:𝑇−1 𝑅𝑡+1 + 𝛾𝜌𝑡:𝑇−1 𝑅𝑡+2 + 𝛾 2 𝜌𝑡:𝑇 𝑡 −1 𝑅𝑡+3 + ⋯ + 𝛾 𝑇−𝑡−1 𝜌𝑡:𝑇−1 𝑅𝑇 = 𝐸 𝜌𝑡:𝑡 𝑅𝑡+1 + 𝛾𝜌𝑡:𝑡+2 𝑅𝑡+1 + ⋯ + 𝛾 𝑇−𝑡−1 𝜌𝑡:𝑇−1 𝑅𝑇 = 𝐸 𝐺෨𝑡 𝐸 𝜌𝑡:𝑇 𝑡 −1 𝑅𝑡+1 = 𝐸

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

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

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

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

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

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

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

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

Sarsa • まずはon-policy TD制御法を見る． • 最初のステップは，状態価値関数ではなく行動価値関数を学習することである． • On-policy手法の場合，現在の行動方策𝜋とすべての状態𝑠および行動𝑎について𝑞𝜋 𝑠, 𝑎 を推定し なければならない． • 状態と行動のペアから状態と行動のペアへの遷移を考え，状態と行動のペアの価値を学習する． • 状態から状態への遷移を考え，状態価値を学習するケースと同一である． • どちらも報酬プロセスを伴うマルコフ連鎖である． • TD(0)における状態価値の更新式を行動価値の対応するアルゴリズムにも適用する． • 𝑄 𝑆𝑡 , 𝐴𝑡 ← 𝑄 𝑆𝑡 , 𝐴𝑡 + 𝛼 𝑅𝑡+1 + 𝛾𝑄 𝑆𝑡+1 , 𝐴𝑡+1 − 𝑄 𝑆𝑡 , 𝐴𝑡 • この更新は，それぞれの非終端状態𝑆𝑡 から遷移の後行われる． • 𝑆𝑡+1 が終端の場合，𝑄 𝑆𝑡+1 , 𝐴𝑡+1 はゼロとする． • この更新では，ある状態と行動のペアから次の状態と行動のペアへの遷移を構成する5つの要 素 𝑆𝑡 , 𝐴𝑡 , 𝑅𝑡+1 , 𝑆𝑡+1 , 𝐴𝑡+1 のすべてを使用する． • この 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制御アルゴリズムである． • 𝑄 𝑆𝑡 , 𝐴𝑡 ← 𝑄 𝑆𝑡 , 𝐴𝑡 + 𝛼 𝑅𝑡+1 + 𝛾max 𝑄 𝑆𝑡+1 , 𝑎 − 𝑄 𝑆𝑡 , 𝐴𝑡 𝑎 • 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 𝑄 𝑆 ′ , 𝑎 − 𝑄 𝑆, 𝐴 𝑎 𝑆 ← 𝑆′ until S is terminal 状態が終端状態になるまでループを続ける． Q-learningも行動価値関数を推定する手法だが，その推定値に基づき𝜀-greedyな方策が求ま る．しかし，価値関数の更新においてgreedy方策（価値関数が最大になる行動を取る）を採 用しているためoff-policyである．

Expected Sarsa • Expected Sarsaは，次の状態とアクションのペアの最大値の代わりに現在の方策に基づいた 期待値を使用したQ-learningである． • 更新式は次のようになる． 𝑄 𝑆𝑡 , 𝐴𝑡 ← 𝑄 𝑆𝑡 , 𝐴𝑡 + 𝛼[𝑅𝑡+1 + 𝛾𝐸𝜋 𝑄 𝑆𝑡+1 , 𝐴𝑡+1 ∣ 𝑆𝑡+1 − 𝑄 𝑆𝑡 , 𝐴𝑡 ] ← 𝑄 𝑆𝑡 , 𝐴𝑡 + 𝛼[𝑅𝑡+1 + 𝛾 ෍ 𝜋 𝑎 ∣ 𝑆𝑡+1 𝑄 𝑆𝑡+1 , 𝐴𝑡+1 − 𝑄 𝑆𝑡 , 𝐴𝑡 ] 𝑎 • 式以外は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つの独立した推定価値𝑄1 𝑎 ，𝑄2 𝑎 を 学習するために使用するとする． • 一方の推定価値𝑄1 を用い最大化する行動𝐴∗ = arg max 𝑄1 𝑎 を決定し，もう一方の推定価値𝑄2 𝑎 を用いその価値の推定値𝑄2 𝐴∗ = 𝑄2 arg max 𝑄1 𝑎 を求める． 𝑎 • また，𝑄1 𝐴∗ = 𝑄1 arg max 𝑄2 𝑎 り返す事もできる． 𝑎 を求めるために，2つの推定値の役割を逆にして処理を繰 • これがdouble learningの考え方である． • 2 つの推定値を学習するが，各更新で1つの推定値のみが更新される．

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

Double Q-learning, for estimating 𝑄1 ≈ 𝑄2 ≈ 𝑞∗ Algorithm parameters: step size 𝛼 ∈ 0, 1 , small " > 0 Initialize 𝑄1 𝑠, 𝑎 and 𝑄2 𝑠, 𝑎 , for all 𝑠 ∈ 𝑆 +, 𝑎 ∈ 𝐴 𝑠 , such that 𝑄 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙,⋅ = 0 価値関数を任意の値で初期化するが，終端状態の価値だけ0とする． Loop for each episode: Initialize 𝑆 Loop for each step of episode: 状態𝑆のときの行動を価値関数の和𝑄1 + 𝑄2 から 𝜀-greedy方策に基づき生成する． Choose 𝐴 from 𝑆 using the policy 𝜀-greedy in 𝑄1 + 𝑄2 Take action 𝐴, observe 𝑅, 𝑆 ′ With 0.5 probabilility: 同じ確率で 𝑄1 と𝑄2 のどちらかを更新する． 𝑄1 𝑆, 𝐴 ← 𝑄1 𝑆, 𝐴 + 𝛼 𝑅𝑡+1 + 𝛾𝑄2 𝑆, arg max 𝑄1 𝑆, 𝑎 𝑎 − 𝑄1 𝑆, 𝐴 else: 𝑄2 𝑆, 𝐴 ← 𝑄2 𝑆, 𝐴 + 𝛼 𝑅𝑡+1 + 𝛾𝑄1 𝑆, arg max 𝑄2 𝑆, 𝑎 𝑎 𝑆 ← 𝑆′ until 𝑆 is terminal 状態が終端状態になるまでループを続ける． − 𝑄2 𝑆, 𝐴

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