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

2.1K Views

November 27, 23

スライド概要

profile-image

コンピュータを使って色々計算しています.個人的な技術に関するメモと講義資料が置いてあります.気が向いた時に資料を修正しています. 公立小松大学臨床工学科准教授 https://researchmap.jp/read0128699

シェア

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

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

2.

モンテカルロ法

3.

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

4.

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

5.

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

6.

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度だけなので, エピ ソードごとに1回状態𝑠のときの𝐺が追加される. 𝑉 𝑆' ← average 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆' )

7.

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 𝑅𝑒𝑡𝑢𝑟𝑛𝑠(𝑆' )

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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).

17.
[beta]
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な⾏動を求める.

18.

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

19.

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 / 0 1 • / 1 が与えられ,greedyな⾏動には1 − 𝜀 + の確率が与えられる. 𝐴 𝑠 は選択可能な⾏動数なので,実はnongreedyが⾏動が選ばれる確率は𝜀 − 𝜀/|𝐴(𝑠)|である (𝐴(𝑠)はgreedyな⾏動も含む).よって,greedyな⾏動をする確率は,1 − 𝜀 − 𝜀/|𝐴(𝑠)| • 𝜀-greedy⽅策は, 𝜀 > 0ですべての状態と⾏動について𝜋 𝑎 ∣ 𝑠 ≥ で定義される𝜀-soft⽅策の例である. = > ? ) * $ =1−𝜀+ とする⽅策

20.

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

21.
[beta]
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 𝑎 ≠ 𝐴∗

22.

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

23.

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

24.

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

25.

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

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

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

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

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

27.

Importance-sampling ratio • ターゲット⽅策と⾏動⽅策の下での状態と⾏動のtrajectoryの相対確率 (Importance-sampling ratio) は次のようになる. 𝜌':%&# ∏%&# ∏%&# :b' 𝜋 𝐴: 𝑆: 𝑃 𝑆:(# 𝑆: , 𝐴: :b' 𝜋 𝐴: 𝑆: =̇ %&# = %&# ∏:b' 𝑏 𝐴: 𝑆: 𝑃 𝑆:(# 𝑆: , 𝐴: ∏:b' 𝑏 𝐴: 𝑆: • Importance-sampling ratioは2つの⽅策と⾏動と状態の系列のみに依存する. • ターゲット⽅策の元での期待収益 (価値) を推定したいが,得られるのは⾏動 ⽅策による収益𝐺. だけである. • これらの収益は誤った期待値 𝐸 𝐺. ∣ 𝑆. = 𝑠 = 𝑣2 𝑠 を持つため,𝑣! を得るため に,これらの収益を平均できない. • ここで⽐率𝜌6:89: を正しい期待価値を持つ収益に変換するために⽤いる. 𝐸 𝜌':%&#𝐺' ∣ 𝑆' = 𝑠 = 𝑣! 𝑠

28.
[beta]
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<

29.

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

30.

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 • ただし,分⺟がゼロの場合はゼロとする.

31.

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

32.

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

33.
[beta]
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である.

34.

式展開 𝑉@A: = ∑@BC: 𝑊B 𝐺B ∑@BC: 𝑊B = 𝑊@ 𝐺@ + 1 = 𝑊 𝐺 + 𝑉@ 𝐶@ − 𝑊@ 𝐶@ @ @ ∑@9: BC: 𝑊B 𝐺B 𝐶@ @9: 1 𝐶@9: = 𝑊@ 𝐺@ + / 𝑊B 𝐺B 𝐶@ 𝐶@9: 𝑊@ = 𝑉@ + 𝐺 − 𝑉@ 𝐶@ @ BC: 𝐶M=> =̇ 𝐶M + 𝑊M=> 𝐶M =̇ 𝐶MA> + 𝑊M 𝐶MA> = 𝐶M − 𝑊M M 𝐶M = 𝑊> + ⋯ + 𝑊M = ) 𝑊# #B>

35.

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

36.
[beta]
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

𝜋 𝑆< ← arg max 𝑄 𝑆< , 𝑎 (with ties broken consistently)
8

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

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

37.

Temporal-Difference (TD) learning

38.

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

39.

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

40.

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

41.

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 状態が終端状態になるまでループを続ける.

42.

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

43.

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

44.

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

45.

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

46.

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

47.

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

48.

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

49.

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

50.

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である.

51.

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

52.

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 8 状態が終端状態になるまでループを続ける. Q-learningも⾏動価値関数を推定する⼿法だが,その推定値に基づき𝜀-greedyな⽅策が求ま る.しかし,価値関数の更新においてgreedy⽅策(価値関数が最⼤になる⾏動を取る)を採 ⽤しているためoff-policyである.

53.

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を包含し⼀般化する.

54.

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

55.

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

56.

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

57.
[beta]
Double Q-learning, for estimating Q1 ⇡ Q 2⇡ q

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

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

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

− 𝑄V 𝑆, 𝐴

58.

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