強化学習2 -ベルマン方程式，動的計画法-

強化学習2 ベルマン⽅程式，動的計画法 公⽴⼩松⼤学 藤⽥ ⼀寿 Ver.20231126

重要な式 割引収益和 ) 𝐺! = 𝑅!"# + 𝛾𝑅!"$ + 𝛾 $ 𝑅!"% + ⋯ = ' 𝛾 & 𝑅!"&"# = 𝑅!"# + 𝛾𝐺!"# &'( 状態価値に対するベルマン⽅程式 𝑣% 𝑠 = 𝐸% 𝐺& 𝑆& = 𝑠 = 𝐸% 𝑅& + 𝛾𝐺&'( 𝑆& = 𝑠 = * 𝜋 𝑎 𝑠 * 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟 + 𝛾𝑣% 𝑠′ *+,, ) ⾏動価値に対するベルマン⽅程式 𝑞% 𝑠, 𝑎 = 𝐸% 𝑅&'( + 𝛾𝐺&'( 𝑆& = 𝑠, 𝐴& = 𝑎 = * 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟 + 𝛾𝑣% 𝑠′ 𝑞, 𝑠, 𝑎 *+,, = ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 - ! ,/ 最適状態価値関数 𝑟 + 𝛾 ' 𝜋(𝑎0 ∣ 𝑠 0 )𝑞, (𝑠 0 , 𝑎0 ) 10 𝑣∗ 𝑠 = max 𝑣% 𝑠 = max 𝐸% 𝐺& 𝑆& = 𝑠 最適⾏動価値関数 % % 𝑞∗ 𝑠, 𝑎 = max 𝑞% 𝑠, 𝑎 = 𝐸 𝑅&'( + 𝛾𝑣∗ 𝑆&'( ∣ 𝑆& = 𝑠, 𝐴& = 𝑎

価値関数とベルマン⽅程式

多腕バンディットと⼀般的な強化学習 • 多腕バンディットでは⾏動はスロットマシンを選ぶことなので，状態は⾏動は ⼀体となり，状態は考えない． • ⼀般的には，⾏動と状態は同じではない． 多腕バンディット 平均報酬 𝑄& (𝑎) を参考に スロットマシン𝑎(𝑡)を選ぶ ⼀般的な強化学習 エージェ ント (Agent) ⽅策 (Policy) 報酬 𝑅(𝑡)を得る ⾏動(Action) 環境 報酬(Reward) 状態(State)

マルコフ決定過程と強化学習の要素 • マルコフ決定過程(Markov Decision Processes: MDP)は⽬標を達成するため の相互作⽤による学習の単純なフレームワークである． • 学習者および意思決定者をエージェントと呼ぶ． • エージェントの外部にある，エージェントと相互作⽤するものを環境と呼ぶ． • エージェントは⾏動し，それに応じて環境の状態は変化する． • エージェントは⾏動を通じて報酬を受け取る． エージ ェント (Agent) ⽅策 (Policy) ⾏動 𝐴! 環境 報酬 𝑅! 状態 𝑆! 報酬 𝑅!"# 状態 𝑆!"#

状態と⾏動 • エージェントと環境は，離散時間ステップ𝑡 = 0,1,2, …ごとに相互作⽤する． • 状態が𝑁種類あるとすると状態集合は𝑆 = {𝑠! , 𝑠" , … , 𝑠# }と表せる． • 時刻𝑡のとき状態は𝑆& とし，𝑆の要素のうちのいずれかである(𝑆& ∈ 𝑆)． • 状態𝑠のとき，取りうる⾏動が𝑀種類あるとすると⾏動集合𝐴(𝑠) = {𝑎! , 𝑎" , … , 𝑎$ }と表せる． • 時刻𝑡における⾏動𝐴& は𝐴(𝑆& )の要素のうちいずれかの値をとる(𝐴& ∈ 𝐴(𝑆& ))． • 時刻𝑡において状態𝑆% で⾏動𝐴(𝑆% )をした後，環境から受け取る報酬𝑅%&! を受け 取り，状態は𝑆%&! に変わる． • 報酬集合を𝑅とすると， 𝑅%&! ∈ 𝑅である． • 有限マルコフ決定過程では，状態，⾏動，報酬の集合の要素数は有限である．

狩りの例を思い出す 𝐴(𝑠) = {池に⾏く，草原に⾏く，森に⾏く，帰る} 状態（場所）が変わっても⾏ける場所は変わらない． 𝑆 = {池, 草原, 森, 家} 𝑅 = {狩り成功10，失敗 − 5}

マルコフ決定過程と確率 • 𝑅% と𝑆% は前の状態と⾏動のみを条件とした離散確率分布で記述される． • 時刻𝑡のとき状態が𝑠′，報酬が𝑟であるとすると，これらは次の確率で決まる． • 𝑝 𝑠 ' , 𝑟 𝑠, 𝑎 = Pr{𝑆% = 𝑠 ' , 𝑅% = 𝑟 ∣ 𝑆%(! = 𝑠, 𝐴%(! = 𝑎} • これは以前の状態が𝑠′，その時とった⾏動が𝑎であるという条件のもとでの 𝑠′， 𝑟 の確率である． • 𝑝はマルコフ決定過程のダイナミクスを表す． • 状態𝑠で⾏動𝑎を⾏ったとき，状態𝑠′ が起こる確率は，先の確率を報酬𝑟で周辺化 すれば良い． • 𝑝 𝑠 ' 𝑠, 𝑎 = Pr 𝑆% = 𝑠 ' 𝑆%(! = 𝑠, 𝐴%(! = 𝑎 = ∑)∈+ 𝑝(𝑠 ' , 𝑟 ∣ 𝑠, 𝑎)

図による表記 𝑆!"# 池 成功 𝐴! エージ ェント (Agent) ⽅策 (Policy) ⾏動 𝐴! 環境 𝑆! 池 報酬 𝑅! 状態 𝑆! 報酬 𝑅!"# 状態 𝑆!"# 強化学習におけるエージェント，⽅策， 状態，⾏動，報酬の関係 𝑅!"# 失敗 池 草 原 草 原 森 森 家 家 我流の図 状態𝑆! の時，取りうる⾏動は𝐴! である．もし ハンターは草原に⾏くと⾔う⾏動を取ると，ほぼ草原に⾏くだろうが 他の場所へ⾏く可能性がある．⾏動を取ると状態が変わると，それと 同時に狩りをし報酬を受け取る．

図による表記 𝑆! 池 𝑝 𝑅"#$ , 𝑆"#$ 𝑆" , 𝐴" 草 原 池 森 家 𝐴! 𝑆! 𝑆!"# 𝐴! 𝑅!"# 𝜋 𝐴! 𝑆! 𝑅!"# 池 𝑅!"# 草 原 𝑅!"# 𝑅!"# 森 家 𝑆!"# 𝑝(𝐴! , 𝑆!"# , 𝑅!"# ∣ 𝑆! ) = 𝑝 𝑅!"# , 𝑆!"# 𝑆! , 𝐴! 𝜋 𝐴! 𝑆! グラフィカルモデル バックアップダイアグラム

報酬の期待値 • 報酬の期待値（期待報酬）は状態と⾏動で決まるため，𝑠と𝑎の変数である． • 𝑟 𝑠, 𝑎 = 𝐸 𝑅% 𝑆%(! = 𝑠, 𝐴%(! = 𝑎 = ∑)∈+ 𝑟 𝑝 𝑟 𝑠, 𝑎 = ∑)∈+ 𝑟 ∑, &∈- 𝑝 𝑠 ' , 𝑟 𝑠, 𝑎 周辺化 • また，状態𝑠のとき⾏動𝑎とったとき，状態が𝑠′になり報酬𝑟をもらうため，期 待報酬は𝑠, 𝑎, 𝑠′の3変数の関数で表現できる． • 𝑟 𝑠, 𝑎, 𝑠′ = 𝐸 𝑅% 𝑆%(! = 𝑠, 𝐴%(! = 𝑎, 𝑆% = 𝑠′ = ∑)∈. 𝑟 𝑝 𝑟 𝑠, 𝑎, 𝑠′ = 𝑠 ' , 𝑟 𝑠, 𝑎 ∑)∈+ 𝑟 / 𝑠′ 𝑠, 𝑎 / 𝑝 𝑠 - , 𝑟 𝑠, 𝑎 = 𝑝 𝑟 𝑠, 𝑎, 𝑠′ 𝑝 𝑠′ 𝑠, 𝑎

未来の報酬 • エージェントは報酬の総量の最⼤化を⽬標としている． • 報酬の累積和の期待値の最⼤化 • 単純に未来に得られるすべての報酬の和，すなわち収益（return）は次のよう に書ける． • 𝐺% = 𝑅%&! + 𝑅%&" + 𝑅%&0 + ⋯ + 𝑅1 • 𝑇は最終時間ステップである． • これは単純に同じ重みで未来のすべての報酬を⾜している．

割引報酬和 • 遠い未来の報酬はすぐ得られないから，近い未来の報酬の⽅が価値が⾼いかも しれない． • そう考えると，遠い未来の報酬と近い未来の報酬が同じ重みで⾜されるのでは なく，遠い未来の報酬は少なめに⾜したほうが良いだろう． • そこで，未来の報酬を割り引いた割引収益を使う． 2 • 𝐺% = 𝑅%&! + 𝛾𝑅%&" + 𝛾 " 𝑅%&0 + ⋯ = ∑5 234 𝛾 𝑅%&2&! • また， • 𝐺% = 𝑅%&! + 𝛾𝑅%&" + 𝛾 " 𝑅%&0 + ⋯ = 𝑅%&! + 𝛾 𝑅%&" + 𝛾𝑅%&0 + ⋯ = 𝑅%&! + 𝛾𝐺%&! • 𝛾を割引率といい，0から1の間の値を取る．

状態価値関数 • エージェントはそもそも何が⽬的だろうか？ • 収益を最⼤化することが最⼤の⽬的だろう． • つまり，収益を最⼤化する状態にしたいとエージェントは考える． • 状態𝑠で得られる割引収益の期待値を価値関数といい次のように書く． 2 • 𝑣6 𝑠 = 𝐸6 𝐺% 𝑆% = 𝑠 = 𝐸6 ∑5 234 𝛾 𝑅%&2&! 𝑆% = 𝑠 • 𝜋は⽅策で，エージェントの⾏動のルールを表す．つまり，この価値関数は⽅ 策 𝜋をとるエージェントが状態𝑠になったとき得られる割引収益の期待値であ る． • この価値関数を，⽅策𝜋に対する状態価値関数と呼ぶ．

状態価値関数 𝑣, 𝑠 = 𝐸, 𝐺! 𝑆! = 𝑠 = 𝐸, 𝑅!"# + 𝛾𝐺!"# 𝑆! = 𝑠 = 𝐸, 𝑅!"# 𝑆! = 𝑠 + 𝛾𝐸, 𝐺!"# 𝑆! = 𝑠 𝑠′ 池 第1項は 成功 𝐸, 𝑅!"# 𝑆! = 𝑠 = ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 𝜋 𝑎 𝑠 𝑟 と書ける． 𝑎 1,-! ,/ 失敗 池 𝑠 池 • • • 状態𝑠のときの価値関数は，その状態のときに収益の期 待値である． 状態𝑠のとき⾏動𝑎をする確率は𝜋(𝑎 ∣ 𝑠)である．𝜋は⾏動 を決めるのでエージェントの⽅策とみなせる． 𝑝 𝑎, 𝑠 0 , 𝑟 𝑠 = 𝑝 𝑟, 𝑠′ 𝑠, 𝑎 𝜋 𝑎 𝑠 と書ける． 𝑟 草 原 草 原 森 森 家 家

価値関数 𝑣% 𝑠 = 𝐸% 𝐺& 𝑆& = 𝑠 = 𝐸% 𝑅&'( + 𝛾𝐺&'( 𝑆& = 𝑠 = 𝐸% 𝑅&'( 𝑆& = 𝑠 + 𝛾𝐸% 𝐺&'( 𝑆& = 𝑠 𝐸% 𝐺&'( 𝑆& = 𝑠 = * 𝑝 𝐺&'( 𝑆& = 𝑠 𝐺&'( 2234 = 状態𝑠は決ま っている 𝑠 ),*+,,,2234 = 𝑟 草 原 𝑟 森 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝜋 𝑎 𝑠 𝑝 𝐺&'( * 𝑟 池 池 𝑝 𝐺&'(, 𝑎, 𝑠 - , 𝑟 𝑠 𝐺&'( * 𝑠′ 𝑎 𝑠 - 𝐺&'( 𝐺"#$ は𝑠 % にのみ依存するが，𝑠 % は𝑠, 𝑎 に依存する． ),*+,,,2234 = * 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝜋 𝑎 𝑠 * 𝑝 𝐺&'( ),*+,, 2234 = * 𝜋 𝑎 𝑠 * 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑣% 𝑠 - 𝑟 家 池 𝐸& 𝐺!"# 池 = 𝑣& 池 草 原 𝐸& [𝐺!"# ∣ 草原] = 𝑣& 草原 森 𝐸& [𝐺!"# ∣ 森] = 𝑣& 森 家 𝐸& [𝐺!"# ∣ 家] = 𝑣& 家 𝑠 - 𝐺&'( 𝑣, 𝑠 = 𝐸, 𝐺! 𝑆! = 𝑠 *+,, ) よって 𝐸" 𝑅!#$ 𝑆! = 𝑠 = : 𝜋 𝑎 𝑠 : 𝑝 𝑟, 𝑠 * 𝑠, 𝑎 𝑟 𝑣% 𝑠 = * 𝜋 𝑎 𝑠 * 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟 + 𝛾𝑣% 𝑠′ ) *+,, % ' ! ,)

価値関数（別の式変形） 𝑣, 𝑠 = 𝐸, 𝐺! 𝑆! = 𝑠 = 𝐸, 𝑅!"# + 𝛾𝐺!"# 𝑆! = 𝑠 = ' 𝜋 𝑎 𝑠 𝐸, 𝑅!"# + 𝛾𝐺!"# 𝑆! = 𝑠, 𝐴! = 𝑎 1 = ' 𝜋 𝑎 𝑠 ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 𝐸, 𝑅!"# + 𝛾𝐺!"# 𝑆! = 𝑠, 𝐴! = 𝑎, 𝑅!"# , = 𝑟 𝑆!"# = 𝑠′ 1 - ! ,/ = ' 𝜋 𝑎 𝑠 ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 𝑟 + 𝛾𝐸, 𝐺!"# 𝑆! = 𝑠, 𝐴! = 𝑎, 𝑅!"# = 𝑟 𝑆!"# = 𝑠 0 1 - ! ,/ = ' 𝜋 𝑎 𝑠 ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 𝑟 + 𝛾𝐸, 𝐺!"# 𝑆!"# = 𝑠 0 1 𝐺!"# は𝑆!"# にのみ依存する． - ! ,/ = ' 𝜋 𝑎 𝑠 ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 𝑟 + 𝛾𝑣, 𝑠′ 1 - ! ,/ 𝐸' 𝑅"#$ 𝑆" = 𝑠, 𝐴" = 𝑎, 𝑅"#$ = 𝑟 𝑆"#$ = 𝑠′ = 𝑟 𝑆" = 𝑠, 𝐴" = 𝑎, 𝑅"#$ = 𝑟 𝑆"#$ = 𝑠′が条件なので 𝑅"#$ = 𝑟と決まっている．

𝑣= に対するベルマン⽅程式 • 𝑣% 𝑠 = 𝐸% 𝑅& + 𝛾𝐺&'( 𝑆& = 𝑠 = ∑) 𝜋 𝑎 𝑠 ∑* + ,, 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟 + 𝛾𝑣% 𝑠′ • これを𝑣% に対するベルマン⽅程式という． • この⽅程式は，ある状態の価値とその後の状態の価値との関係 を表す． • 図（バックアップダイアグラム）のように，ある状態𝑠からそ の後に起こりうる状態𝑠′までを先読みすることを考えてみる． • ベルマン⽅程式は，すべての可能性を発⽣確率に従い荷重平均 をとる． • これは，始状態である状態𝑠の価値は，期待報酬 ∑) 𝜋 𝑎 𝑠 ∑* + ,, 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟と次の状態の期待（割引）価値 ∑) 𝜋 𝑎 𝑠 ∑* + ,, 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝛾𝑣% 𝑠′ の和に等しくなければなら ないことを述べている． ⽩円は状態を表し，⿊円は状態 と⾏動のペアを表す．エー ジェントは⽅策に基づいて， ルートノードである状態𝑠か ら，いずれかの可能な⾏動 （⿊丸のどれか）を取ること ができる．

⾏動価値関数 • 状態𝑠になったあとは⾏動しなければならない．そう考えれば，⾏動𝑎にも依存 した価値関数も考えることができる． • ⾏動𝑎を考慮した価値関数を⽅策𝜋に対する⾏動価値関数といい，次のように 書く． 2 • 𝑞6 𝑠, 𝑎 = 𝐸6 𝐺% 𝑆% = 𝑠, 𝐴% = 𝑎 = 𝐸6 ∑5 234 𝛾 𝑅%&2&! 𝑆% = 𝑠, 𝐴% = 𝑎 𝑠′ 𝑠 𝑎 池 草 原 決まっている 𝑟 池 𝑟 草 原 𝑟 𝑟 森 家

⾏動価値に対するベルマン⽅程式 • 状態価値関数と同様に • 𝑞6 𝑠, 𝑎 = 𝐸6 𝐺% 𝑆% = 𝑠, 𝐴% = 𝑎 = 𝐸6 𝑅%&! + 𝛾𝐺%&! 𝑆% = 𝑠, 𝐴% = 𝑎 = ∑, &,) 𝑝 𝑟, 𝑠 ' 𝑠, 𝑎 𝑟 + 𝛾𝑣6 𝑠′ • また， • 𝑞6 𝑠, 𝑎 = ∑, &,) 𝑝 𝑟, 𝑠 ' 𝑠, 𝑎 𝑟 + 𝛾 ∑8' 𝜋(𝑎' ∣ 𝑠 ' )𝑞6 (𝑠 ' , 𝑎' ) • 𝑞6 𝑠, 𝑎 は⾏動価値に対するベルマン⽅程式という． 𝑠′ 状態𝑠と⾏動𝑎 は決まっている 𝑠 池 𝑎 草 原 𝑟 𝑟 𝑟 𝑟 1つ⽬の式に対応する図 池 草 原 𝐸" 𝐺!#$ 池 = 𝑣" 池 𝐸"[𝐺!#$ ∣ 草原] = 𝑣" 草原 森 𝐸"[𝐺!#$ ∣ 森] = 𝑣" 森 家 𝐸"[𝐺!#$ ∣ 家] = 𝑣" 家 状態𝑠と⾏動𝑎は決ま っている 𝑠 池 𝑎% 池 池 𝐸" 𝐺!#$ 草原，池 = 𝑞"(草原, 池) 草 原 草 原 𝐸"[𝐺!#$ ∣ 草原，草原] = 𝑞"(草原, 草原) 森 森 𝐸"[𝐺!#$ ∣ 草原，森] = 𝑞"(草原, 森) 家 家 𝐸"[𝐺!#$ ∣ 草原，家] = 𝑞"(草原, 家) 𝑟 𝑎 𝑟 草 原 𝑟 𝑟 2つ⽬の式に対応する図 𝑠% 𝑠 " = 草原以外からも𝑎′への接続があるが省略している．

⾏動価値関数の式展開 1つ⽬の式 𝑞& 𝑠, 𝑎 = 𝐸& 𝐺! 𝑆! = 𝑠, 𝐴! = 𝑎 = 𝐸& 𝑅!"# + 𝛾𝐺!"# 𝑆! = 𝑠, 𝐴! = 𝑎 = = 𝑝 𝑟, 𝑠 6 𝑠, 𝑎 𝐸& 𝑅!"# + 𝛾𝐺!"# 𝑆! = 𝑠, 𝐴! = 𝑎, 𝑅!"# , = 𝑟 𝑆!"# = 𝑠′ 4+ ,5 = = 𝑝 𝑟, 𝑠 6 𝑠, 𝑎 𝑟 + 𝛾𝐸& 𝐺!"# 𝑆! = 𝑠, 𝐴! = 𝑎, 𝑅!"# = 𝑟 𝑆!"# = 𝑠 6 4+ ,5 = = 𝑝 𝑟, 𝑠 6 𝑠, 𝑎 𝑟 + 𝛾𝐸& 𝐺!"# 𝑆!"# = 𝑠 6 4+ ,5 = = 𝑝 𝑟, 𝑠 6 𝑠, 𝑎 𝑟 + 𝛾𝑣& 𝑠′ 4+ ,5 2つ⽬の式 𝑞& 𝑠, 𝑎 = = 𝑝 𝑟, 𝑠 6 𝑠, 𝑎 𝑟 + 𝛾𝐸& 𝐺!"# 𝑆!"# = 𝑠 6 4+ ,5 = = 𝑝 𝑟, 𝑠 6 𝑠, 𝑎 4+ ,5 = = 𝑝 𝑟, 𝑠 6 𝑠, 𝑎 4+ ,5 𝑟 + 𝛾 = 𝜋(𝑎6 ∣ 𝑠 6 )𝐸& 𝐺!"# 𝑆!"# = 𝑠 6 , 𝐴!"# = 𝑎6 76 𝑟 + 𝛾 = 𝜋(𝑎6 ∣ 𝑠 6 )𝑞& (𝑠 6 , 𝑎6 ) 76

エージェントは何を⽬的としているのか • エージェントの⽬的は収益の最⼤化である． • 我々が知りたいのは，エージェントが⽬的を達するためにはどのような⽅策を とればよいかである． • つまり，最も収益が得られる⽅策を探すことが⽬的である． • 最も良い⽅策を𝜋∗ とすると，⽅策𝜋∗ をとったときの状態価値関数は • 𝑣∗ 𝑠 = max 𝑣6 𝑠 = max 𝐸6 𝐺% 𝑆% = 𝑠 6 6 • と書ける．これを最適状態価値関数と呼ぶ．

最適⾏動価値関数 • ⽅策𝜋∗ をとったときの⾏動価値関数は • 𝑞∗ 𝑠, 𝑎 = max 𝑞6 𝑠, 𝑎 = 𝐸 𝑅%&! + 𝛾𝑣∗ 𝑆%&! ∣ 𝑆% = 𝑠, 𝐴% = 𝑎 𝑠′ 6 • と書ける．これを最適⾏動価値関数と呼ぶ． 𝑞∗ 𝑠, 𝑎 = max 𝑞, 𝑠, 𝑎 = max 𝐸 𝐺! 𝑆! = 𝑠, 𝐴! = 𝑎 , , 𝑟 + max 𝛾𝑣, 𝑠′ , = ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 𝑟 + 𝛾𝑣∗ 𝑠′ - ! ,/ 池 池 𝑟 草 原 𝑟 𝑟 = 𝐸, 𝑅!"# + 𝛾𝑣∗ 𝑆!"# ∣ 𝑆! = 𝑠, 𝐴! = 𝑎 森 max 𝑎(𝑏 + 𝑥 𝑡 ) = 𝑎𝑏 + 𝑎 max(𝑦 𝑡 ) " " - ! ,/ = ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 - ! ,/ 𝑎 草 原 決まっている , = max ' 𝑝 𝑟, 𝑠 0 𝑠, 𝑎 𝑟 + 𝛾𝑣, 𝑠′ 𝑠 𝑟 ⽅策が何であれ，状態と⾏動が決まっていれば報酬𝑟と次の状態𝑠′が出る確率は決まる． ⼀⽅，価値関数は⽅策に依存している． 家

最適な⽅策とはなんだろう • 最適な⽅策とは，状態価値関数や⾏動価値関数を最⼤にする⽅策である． • つまり，ベルマン⽅程式を最⼤化する⽅策を⾒つけたい • ベルマン⽅程式は𝑣% 𝑠 = ∑) 𝜋 𝑎 𝑠 ∑* + ,, 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟 + 𝛾𝑣% 𝑠′ • 最適な⽅策を𝜋∗ 𝑎 𝑠 とするとベルマン⽅程式は • 𝑣%∗ 𝑠 = ∑) 𝜋∗ 𝑎 𝑠 ∑* + ,, 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟 + 𝛾𝑣∗ 𝑠′ = ∑) 𝜋∗ 𝑎 𝑠 𝑞∗ (𝑎, 𝑠) • となる．最適な⽅策𝜋∗ 𝑎 𝑠 の場合，エージェントは収益を最⼤にする⾏動のみと るから • 𝜋∗ 𝑎 𝑠 = 4 1 if 𝑎 = argmax 𝑞∗ (𝑠, 𝑎) ) 0 otherwise • これは，エージェントは収益を最⼤にする⾏動しかとらないことを意味する． • すなわち𝑣%∗ = max 𝑞∗ (𝑎, 𝑠) )

状態価値に対するベルマン最適⽅程式 • 最適な⽅策𝜋∗ をとったときの状態価値関数は 𝑣∗ 𝑠 = max 𝑞%∗ 𝑠, 𝑎 = max 𝐸%∗ 𝐺& 𝑆& = 𝑠, 𝐴& = 𝑎 )∈D * )∈D(*) = max 𝐸%∗ 𝑅&'( + 𝛾𝐺&'( 𝑆& = 𝑠, 𝐴& = 𝑎 )∈D(*) = max 𝐸%∗ 𝑅&'( + 𝛾𝑣% 𝑆&'( )∈D(*) = max 𝐸 𝑅&'( + 𝛾𝑣∗ 𝑆&'( )∈D(*) = max * 𝑝 )∈D(*) *+,, 𝑠 -, 𝑟 𝑠, 𝑎 𝑆& = 𝑠, 𝐴& = 𝑎 𝑠′ 状態𝑠は決まっ ている． 𝑆& = 𝑠, 𝐴& = 𝑎 𝑟 + 𝛾𝑣∗ 𝑠′ 状態𝑠 *は確率的に決まる ため， 𝑣∗ 𝑠′ の期待値を 取る． 𝑣∗ 𝑠′ は最適⽅策 𝜋∗ に基づいている． • これを状態価値に対するベルマン最適⽅程式という． 𝑠 池 𝑎 草 原 𝑟 池 𝐸"∗ 𝐺!#$ 池 = 𝑣∗ 池 𝑟 草 原 𝐸"∗ [𝐺!#$ ∣ 草原] = 𝑣∗ 草原 森 𝐸"∗ [𝐺!#$ ∣ 森] = 𝑣∗ 森 家 𝐸"∗ [𝐺!#$ ∣ 家] = 𝑣∗ 家 𝑟 𝑟 ⾏動価値関数が最 ⼤になる⾏動𝑎は を選ぶ(最適な⽅ 策)． ⾏動𝑎が決まっても𝑠′は 確率的に決まる（𝑎の 条件が付いている）．

⾏動価値に対するベルマン最適⽅程式 • 最適な⽅策𝜋∗ をとったときの⾏動価値関数は 𝑞∗ 𝑠, 𝑎 = 𝐸 𝑅&'( + 𝛾𝑣∗ 𝑠′ 𝑆& = 𝑠, 𝐴& = 𝑎 = 𝐸 𝑅&'( + 𝛾 max 𝑞∗ 𝑆&'(, 𝑎+ ) = * 𝑝 𝑠 - , 𝑟 𝑠, 𝑎 *+,, 𝑆& = 𝑠, 𝐴& = 𝑎 𝑟 + 𝛾 max 𝑞∗ 𝑠 - , 𝑎+ ) • これを，⾏動価値に対するベルマン最適⽅程式という． ⾏動価値関数が最⼤になる ⾏動𝑎′を選ぶ． 状態𝑠と⾏動𝑎は決ま っている 𝑠 池 𝑠% 𝑎% 池 森 max 𝑞∗ 池, 𝑎* = 𝑞∗ 池, 森 " % 𝑟 𝑎 𝑟 森 max 𝑞∗ 草原, 𝑎* = 𝑞∗ 草原, 森 " 草 原 草 原 𝑟 𝑟 森 森 max 𝑞∗ 森, 𝑎* = 𝑞∗ 森, 森 " 家 森 max 𝑞∗ 家, 𝑎* = 𝑞∗ 家, 森 " ⾏動𝑎が決まっても𝑠′は確率的に決まる （𝑎の条件が付いている）． % % %

バックアップダイアグラム • 𝑣∗ と𝑞∗ に対するベルマン最適⽅程式をあらわすバックアップダイアグラム(そ れぞれ左図，右図に対応) 𝑣∗ 𝑠 = max 𝑞,∗ 𝑠, 𝑎 1∈A - 𝑞∗ 𝑠, 𝑎 = = 𝑝 𝑠 6 , 𝑟 𝑠, 𝑎 4+ ,5 𝑟 + 𝛾 max 𝑞∗ 𝑠 6 , 𝑎6 + 7

エージェントはどう⾏動すればよいか • 状態価値関数や⾏動価値関数を計算してはみたが，エージェントがどうこうど うすればよいのか分からない． • 最適⾏動価値関数𝑞∗ 𝑠, 𝑎 が分かっていれば，エージェントは𝑞∗ が最⼤となる ⾏動を取れば良い． • しかし，実際は分からない． • エージェントは過去の試⾏錯誤から得た情報から最適状態価値関数もしくは最 適⾏動価値関数を得なければならない．

動的計画法

動的計画法とは • 最適化⼿法およびプログラミング⼿法の⼀つ． • 1950年代Bellmanにより開発された． • 複雑な問題を部分的な簡単な問題に分割し，再帰計算により解く⼿法である． • 強化学習では最適な⽅策を探すことが⽬的である．強化学習における動的計画 法では，状態ごとの価値を更新しながら最適な⽅策を探していくことになる．

価値関数をどのように計算するか • 状態価値関数は次のように書けた． 𝑣, 𝑠 = 𝐸, 𝐺! 𝑆! = 𝑠 = 𝐸, 𝑅! + 𝛾𝐺!"# 𝑆! = 𝑠 = 𝐸, 𝑅! + 𝛾𝑣, (𝑆!"# ) 𝑆! = 𝑠 = ' 𝜋 𝑎 𝑠 ' 𝑝 𝑠 0 , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑣, 𝑠 0 1 - ! ,/ • 価値関数が既知ならば価値関数から最適な⾏動を求められるが，実際は価値関 数は未知である． • 環境のダイナミクスが完全に知られているのならば，価値関数を求める事はで きるが，うんざりするほどの計算をしなければならないかもしれない． • ここでは，反復的な解放が最も合理的だろう．

反復⽅策評価（Iterative policy evaluation） • まず，近似価値関数の列𝑣4 , 𝑣! , …があると考える． • 初期値𝑣4 は適当な数値で良い（ただし終状態の価値は0にする．）． • 反復回数𝑘 + 1のときの状態𝑠の価値𝑣2&! 𝑠 は，⼀つ前の時刻𝑘の価値関数から 次のように求められる． 𝑣H'( 𝑠 = 𝐸% 𝑅&'( + 𝛾𝑣H 𝑆&'( 𝑆& = 𝑠 = * 𝜋 𝑎 𝑠 * 𝑝 𝑠 - , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑣H 𝑠 ) *+,, • この反復計算は無限回繰り返すことで𝑣2 = 𝑣6 で収束する． • このアルゴリズムを反復⽅策評価（iterative policy evaluation）と呼ぶ． • ⽅策評価とは，(通常は) 特定の⽅策対する価値関数の反復計算を指す．

反復⽅策評価（Iteretive policy evaluation）の詳細 Input: π Algorithm parameter: a threshold 𝜃 > 0 Initialize V s for all s ∈ S, arbitrarily except that 𝑉 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 = 0. 任意の値ですべての状態の価値V s を初期化する．ただし，終端状態のV(s)は0にする． Loop: 𝛥←0 Loop for each 𝑠 ∈ 𝑆: 古い状態価値を保存する． 𝑣←𝑉 𝑠 𝑉 𝑠 ← ∑) 𝜋 𝑎 𝑠 ∑*+,, 𝑝 𝑠 - , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 - )] 与えられた⽅策に基づき新たな状態価値を計算する． 𝛥 ← max 𝛥, 𝑣 − 𝑉 𝑠 新旧の状態価値の差分とΔを⽐較し⼤きい⽅をΔに代⼊する． unitil 𝛥 < 𝜃 新旧の状態価値の差分が閾値より⼩さくなれば終了

例：格⼦の世界 1 2 3 4 5 6 7 8 9 10 11 12 13 14 エージェントは格⼦内を移動する． 灰⾊は終端状態で，そこまで移動す るとエージェントは移動をやめる． 格⼦内の数値は，格⼦に割り振った 番号で，状態を表す． 𝑆 = {1,2, … , 14} エージェントは上下 左右に移動できる． 今回は等確率で移動 するとする． 格⼦の壁にぶつかっ た場合，その状態に 居続ける． どの状態になっても報酬 は−1 𝑅& = −1

例：格⼦の世界 初期状態𝑘 = 0 𝑘=1 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 -1 -1 0 0 0 0 -1 -1 -1 -1 0 0 0 0 -1 -1 -1 0 すべての状態の価 値は０に初期化し た． 格⼦内の数値は状 態の価値𝑉(𝑠)であ る． 状態𝑠の価値𝑉&'# (1)を計算してみる． 更新式は 𝑉 𝑠 ← ' 𝜋 𝑎 𝑠 ' 𝑝 𝑠 0 , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 0 )] 1 - ! ,/ だから 𝑉&'# 1 1 1 1 = × −1 + 0 + × −1 + 0 + × −1 + 0 4 4 4 1 + × −1 + 0 = −1 4 すべての状態に対し同じ計算を⾏うと，図のよ うになる．上下左右等確率に移動するので， 1/4がかけてある．𝛾 = 1としている．

例：格⼦の世界 𝑘=1 𝑘=2 𝑘=3 0 -1 -1 -1 0 −1.7 −2 −2 0 −2.4 −2.9 −3 -1 -1 -1 -1 −1.7 −2 −2 −2 −2.4 −2.9 −3 −2 -1 -1 -1 -1 −2 −2 −2 −1.7 −2.9 −3 −2.9 −2.9 -1 -1 -1 0 −2 −2 −1.7 0 −3 −2.9 −2.4 0 状態𝑠の価値𝑉&'$ (1)を計算してみる． 𝑉&'$ 1 1 1 1 = × −1 + 0 + × −1 − 1 + × −1 − 1 4 4 4 1 + × −1 − 1 = −1.75 4 すべての状態に対し同じ計算を⾏うと，図のよ うになる． 状態𝑠の価値𝑉&'% (1)を計算してみる． 𝑉&'% 1 1 1 1 = × −1 + 0 + × −1 − 1.7 + × −1 − 2 4 4 4 1 + × −1 − 2 = −2.425 4 すべての状態に対し同じ計算を⾏うと，図のよ うになる．

例：格⼦の世界 最終的に得られた 状態価値 ⽅策 0 −14 −20 −22 −14 −18 −20 −20 −20 −20 −18 −14 −22 −20 −14 0 何度か計算すると状態価値の値は収束する．この状態価値から⽅策を導い てみよう． エージェントは最も状態価値の⾼い⾏動を取る（greedy⽅策）とすると， 右図のような⽅策を取る．この⽅策は最適⽅策になっている．

⽅策改善 • 価値関数を求めたのは，より良い⽅策を⾒つけるためである． • ある⽅策𝜋に対する価値関数が既知であるとする．もし，現在の⽅策𝜋に従って⾏ 動するより，より良い⾏動があるのならば⽅策を更新しなければならない． • 状態𝑠で⾏動𝑎をとり，その後⽅策𝜋に従い⾏動するとしたときの価値は次のように 書ける． • 𝑞% 𝑠, 𝑎 = 𝐸 𝑅&'( + 𝛾𝑣% 𝑆&'( 𝑆& = 𝑠, 𝐴& = 𝑎 = ∑* + ,, 𝑝 𝑠 - , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑣% 𝑠 - • この値が𝑣% 𝑠 より⼤きい場合，状態𝑠のとき⾏動𝑎をし，その後⽅策𝜋を取り続ける ⽅が，状態𝑠のときから⽅策𝜋に従うより良いということになる． • 𝑣< 𝑠 は状態𝑠のとき⽅策𝜋に従い⾏動して得られる収益の期待値である． • 現在の⽅策𝜋に従うより良い⾏動があるということは，⽅策は改善の余地がある（ ⽅策は最適ではない）ということになる．

⽅策改善定理 • 決定論的な⽅策𝜋と𝜋 ' を考える．これらの法則はすべての状態に対し次の数式 を満たすとする． • 𝑞6 𝑠, 𝜋 ' 𝑠 ≥ 𝑣6 𝑠 • この場合，⽅策𝜋 ' は⽅策𝜋と同等かより良くなければならない． • つまり，すべての状態についての期待収益は同じか多くなければならない． • 𝑣6' 𝑠 ≥ 𝑣6 𝑠 • もし， ⽅策𝜋と𝜋 ' が 𝜋 ' 𝑠 = 𝑎 ≠ 𝜋 𝑠 以外同⼀であるような変更が⾏われたと する．もし𝑞6 𝑠, 𝑎 > 𝑣6 𝑠 であるのならば，明らかに 𝜋 ' は改善された⽅策で ある．

⽅策改善 • より良い⽅策𝜋 ' (𝑠)は，状態𝑠で最も𝑞6 𝑠, 𝑎 が⾼い⾏動をするgreedyな⽅策だ ろう．つまり，より良い⽅策𝜋 ' (𝑠)は次のように書ける． 𝜋 - 𝑠 = arg max 𝑞% 𝑠, 𝑎 = arg max 𝐸 𝑅&'( + 𝛾𝑣% 𝑆&'( ∣ 𝑆& = 𝑠, 𝐴& = 𝑎 ) = arg max * 𝑝 𝑠 - , 𝑟 𝑠, 𝑎 ) *+,, ) 𝑟 + 𝛾𝑣% 𝑠 -

⽅策改善 • Greedyな⽅策 𝜋 = (𝑠) が古い⽅策 𝜋(𝑠)と同等で，より良くはないとしよう．このとき，すべて の状態について𝑣<@ 𝑠 = 𝑣< 𝑠 となる． • Greedyな⽅策のとき 𝜋 = 𝑠 = arg max 𝑞<@ 𝑠, 𝑎 だから > 𝑣%+ 𝑠 = * 𝜋 - 𝑎 𝑠 * 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 𝑟 + 𝛾𝑣%+ 𝑠′ *+,, ) = * 𝑝 𝑟, 𝑠 - 𝑠, arg max 𝑞 𝑠, 𝑎 ) *+,, = max * 𝑝 𝑟, 𝑠 - 𝑠, 𝑎 ) 𝑟 + 𝛾𝑣%+ 𝑠′ 𝑟 + 𝛾𝑣%+ 𝑠′ *+,, • これは，ベルマン最適⽅程式は𝑣∗ = max ∑B@ ,C 𝑝 𝑠 = , 𝑟 𝑠, 𝑎 >∈A(B) 𝑟 + 𝛾𝑣∗ 𝑠′ と同じである．よって ，𝑣<@ 𝑠 = 𝑣∗ でなければならず， 𝜋 = (𝑠) と𝜋(𝑠)は両⽅とも最適⽅策でなければならない． • つまり，もとの⽅策が最適⽅策である場合を除いて，⽅策改善は厳密でより良い⽅策を我々に 与える．

Policy iteration（⽅策反復） • より良い⽅策𝜋 ' を得るために価値関数𝑣6 を利⽤し⽅策を改善し，さらにその⽅ 策𝜋 ' を使い価値関数を更新する，という⼿順で⽅策を改善していくことで，最 適⽅策を⾒つける⽅法をPolicy iterationという． ⽅策評価 ⽅策評価 ⽅策改善 ⽅策評価 ⽅策評価 ⽅策改善 ⽅策改善

Policy Iteration (using iterative policy evaluation) for estimating 𝝅 ≈ 𝝅∗ 1. Initialization 𝑉 𝑠 ∈ 𝑅，𝜋(𝑠) ∈ 𝐴 𝑠 arbitrarily for all 𝑠 ∈ 𝑆 すべての状態について価値関数𝑉 𝑠 と⽅策𝜋(𝑠)を初期化 2. Policy evaluation Loop: 𝛥←0 Loop for each 𝑠 ∈ S: 𝑣←𝑉 𝑠 古い状態価値を保存する． 𝑉 𝑠 ← ∑7 𝜋 𝑎 𝑠 ∑4+ ,5 𝑝 𝑠 6 , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 6 )] 現在の⽅策に基づき，古い状態価値から新しい状態価値を計算する． 𝛥 ← max(𝛥, |𝑣 − 𝑉(𝑠)|) 新旧の状態価値の差分とΔを⽐較し⼤きい⽅をΔに代⼊する． unitil 𝛥 < 𝜃 (a small positive number determining the accuracy of estimation) 3. Policy improvement 𝑝𝑜𝑙𝑖𝑐𝑦_𝑠𝑡𝑎𝑏𝑙𝑒 ← 𝑡𝑟𝑢𝑒 For each 𝑠 ∈ 𝑆: 𝑜𝑙𝑑_𝑎𝑐𝑡𝑖𝑜𝑛 ← 𝜋 𝑠 古い⽅策を保存する． 𝜋 𝑠 ← arg max ∑4+ ,5 𝑝 𝑠 6 , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑉 𝑠 6 7 現在の状態価値におけるgreedyな⽅策を求める． If 𝑜𝑙𝑑_𝑎𝑐𝑡𝑖𝑜𝑛 ≠ 𝜋 𝑠 , then 𝑝𝑜𝑙𝑖𝑐𝑦_𝑠𝑡𝑎𝑏𝑙𝑒 ← 𝑓𝑎𝑙𝑠𝑒 ⽅策に変更があれば 𝑝𝑜𝑙𝑖𝑐𝑦_𝑠𝑡𝑎𝑏𝑙𝑒に𝑓𝑎𝑙𝑠𝑒代⼊する． If 𝑝𝑜𝑙𝑖𝑐𝑦_𝑠𝑡𝑎𝑏𝑙𝑒 = 𝑡𝑟𝑢𝑒, then stop and return 𝑉 ≈ 𝑣∗ , 𝜋 = 𝜋∗ ; else go to 2 ⽅策に変更がなければ終了する．

Value iteration（価値反復） • Policy iterationの⽋点の⼀つは，各ステップで⽅策評価をする必要がある点で ある． • ⽅策評価⾃体も状態について何度もスイープする必要がある⻑期に渡る繰り返し計 算であるかもしれない． • １回のスイープで⽅策評価をやめる特殊なアルゴリズムを，Value iterationと いう． • Value iterationは各ステップで次式を更新する． • 𝑣2&! 𝑠 = max 𝐸[𝑅%&! + 𝛾𝑣2 𝑆%&! ∣ 𝑆% = 𝑠, 𝐴% = 𝑎] = 8 max ∑, &,) 𝑝 𝑠 ' , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑣2 (𝑠 ' )] 8 • この式はベルマン最適⽅程式 𝑣∗ 𝑠 = max ∑, &,) 𝑝 𝑠 ' , 𝑟 𝑠, 𝑎 8∈:(,) 新ルールに変えることで単純に得られる． 𝑟 + 𝛾𝑣∗ 𝑠′ を更

Value Iteration, for estimating 𝝅 ≈ 𝝅∗
• Value iterationでは，価値の反復更新のとき常に最⼤の⾏動を選ぶ．
• この点のみPolicy iterationと異なる．
Algorithmic parameter: a small threshold 𝜃 > 0 determining accuracy of estimation
Initialize 𝑉 𝑠 , for all 𝑠 ∈ 𝑆 " , arbitrarily except that 𝑉(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙) = 0
すべての状態について𝑉 𝑠 を任意の値に初期化する．ただし，終端状態の𝑉
は0にする．𝑆 # なのは終端状態が除かれているからだろう．

Loop:
𝛥←0

Loop for each 𝑠 ∈ 𝑆:
古い状態価値を保存する．
𝑣←𝑉 𝑠
𝑉 𝑠 ← max ∑L! ,M 𝑝 𝑠 0 , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 0 )]
1

𝛥 ← max(𝛥, |𝑣 − 𝑉(𝑠)|)
unitil 𝛥 < 𝜃

Greedyな⽅策に基づき新たな状態価値を計算する．

新旧の状態価値の差分とΔを⽐較し⼤きい⽅をΔに代⼊する．

新旧の状態価値の差分が閾値より⼩さくなれば終了

Output a deterministic policy, 𝜋 ≈ 𝜋∗ , such that
𝜋 𝑠 = arg max ∑- ! ,/ 𝑝 𝑠 0 , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉 𝑠 0 ]
1

求めた状態価値を⽤いgreedyな⽅策を求める．

⽅策反復と価値反復 • ⽅策反復と価値反復は，MDPに関する完全な知識があれば，有限MDPに対す る最適な⽅策と価値関数を確実に計算できる．

⼀般化⽅策反復(GPI: generalized policy iteration) • GPIは，⽅策評価と⽅策改善が相互作⽤するという⼀般的な考え⽅である． • GPIで，ほとんどの強化学習を説明できる． • 強化学習の⼿法のすべてが，確認可能な⽅策と価値関数を持つ．そして，図が⽰す ように，⽅策は常に価値関数に対して改善され，価値関数は常にその⽅策対する価 値関数として計算される． • 評価プロセスと改善プロセスが安定化すれば，それ以上変化が起こらない．す なわち，⽅策と価値関数は最適となっている．

ブートストラップ • DP法では，次の状態の価値の推定値に基づいて状態の価値の推定値を更新す る． • つまり，他の推定値に基づいて推定値を更新する．この⼀般的なアイデアを ブートストラップと呼ぶ． • 多くの強化学習⼿法は，DP法が要求するような完全で正確な環境モデルを必 要としない⼿法であっても，ブートストラップを実⾏する．