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

強化学習2 ベルマン方程式，動的計画法 公立小松大学 藤田 一寿 Ver.20250410

重要な式 割引収益和 ∞ 𝐺𝑡 = 𝑅𝑡+1 + 𝛾𝑅𝑡+2 + 𝛾 2 𝑅𝑡+3 + ⋯ = ෍ 𝛾 𝑘 𝑅𝑡+𝑘+1 = 𝑅𝑡+1 + 𝛾𝐺𝑡+1 𝑘=0 状態価値に対するベルマン方程式 𝑣𝜋 𝑠 = 𝐸𝜋 𝐺𝑡 𝑆𝑡 = 𝑠 = 𝐸𝜋 𝑅𝑡 + 𝛾𝐺𝑡+1 𝑆𝑡 = 𝑠 = ෍ 𝜋 𝑎 𝑠 ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 + 𝛾𝑣𝜋 𝑠′ 𝑎 行動価値に対するベルマン方程式 𝑠 ′ ,𝑟 𝑞𝜋 𝑠, 𝑎 = 𝐸𝜋 𝑅𝑡+1 + 𝛾𝐺𝑡+1 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 + 𝛾𝑣𝜋 𝑠′ 𝑞𝜋 𝑠, 𝑎 𝑠 ′ ,𝑟 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑠 ′ ,𝑟 最適状態価値関数 𝑟 + 𝛾 ෍ 𝜋(𝑎′ ∣ 𝑠 ′ )𝑞𝜋 (𝑠 ′ , 𝑎′ ) 𝑎′ 𝑣∗ 𝑠 = max 𝑣𝜋 𝑠 = max 𝐸𝜋 𝐺𝑡 𝑆𝑡 = 𝑠 𝜋 最適行動価値関数 𝜋 𝑞∗ 𝑠, 𝑎 = max 𝑞𝜋 𝑠, 𝑎 = 𝐸 𝑅𝑡+1 + 𝛾𝑣∗ 𝑆𝑡+1 ∣ 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎 𝜋

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

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

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

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

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

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

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

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

報酬の期待値 • 報酬の期待値（期待報酬）は状態と行動で決まるため，𝑠と𝑎の変数である． • 𝑟 𝑠, 𝑎 = 𝐸 𝑅𝑡 𝑆𝑡−1 = 𝑠, 𝐴𝑡−1 = 𝑎 = σ𝑟∈R 𝑟 𝑝 𝑟 𝑠, 𝑎 = σ𝑟∈R 𝑟 σ𝑠′∈𝑆 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 周辺化 • また，状態𝑠のとき行動𝑎とったとき，状態が𝑠′になり報酬𝑟をもらうため，期 待報酬は𝑠, 𝑎, 𝑠′の3変数の関数で表現できる． • 𝑟 𝑠, 𝑎, 𝑠′ = 𝐸 𝑅𝑡 𝑆𝑡−1 = 𝑠, 𝐴𝑡−1 = 𝑎, 𝑆𝑡 = 𝑠′ = σ𝑟∈𝑅 𝑟 𝑝 𝑟 𝑠, 𝑎, 𝑠′ = σ𝑟∈R 𝑟 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 𝑝 𝑠′ 𝑠, 𝑎 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 = 𝑝 𝑟 𝑠, 𝑎, 𝑠′ 𝑝 𝑠′ 𝑠, 𝑎

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

割引報酬和 • 遠い未来の報酬はすぐ得られないから，近い未来の報酬の方が価値が高いかも しれない． • そう考えると，遠い未来の報酬と近い未来の報酬が同じ重みで足されるのでは なく，遠い未来の報酬は少なめに足したほうが良いだろう． • そこで，未来の報酬を割り引いた割引収益を使う． 𝑘 • 𝐺𝑡 = 𝑅𝑡+1 + 𝛾𝑅𝑡+2 + 𝛾 2 𝑅𝑡+3 + ⋯ = σ∞ 𝑘=0 𝛾 𝑅𝑡+𝑘+1 • また， • 𝐺𝑡 = 𝑅𝑡+1 + 𝛾𝑅𝑡+2 + 𝛾 2 𝑅𝑡+3 + ⋯ = 𝑅𝑡+1 + 𝛾 𝑅𝑡+2 + 𝛾𝑅𝑡+3 + ⋯ = 𝑅𝑡+1 + 𝛾𝐺𝑡+1 • 𝛾を割引率といい，0から1の間の値を取る．

状態価値関数 • エージェントはそもそも何が目的だろうか？ • 収益を最大化することが最大の目的だろう． • つまり，収益を最大化する状態にしたいとエージェントは考える． • 状態𝑠で得られる割引収益の期待値を価値関数といい次のように書く． 𝑘 • 𝑣𝜋 𝑠 = 𝐸𝜋 𝐺𝑡 𝑆𝑡 = 𝑠 = 𝐸𝜋 σ∞ 𝑘=0 𝛾 𝑅𝑡+𝑘+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 𝑣𝜋 𝑠 = 𝐸𝜋 𝐺𝑡 𝑆𝑡 = 𝑠 = ෍ 𝜋 𝑎 𝑠 ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑣𝜋 𝑠 ′ 𝑠 ′ ,𝑟 𝑎 よって 𝐸𝜋 𝑅𝑡+1 𝑆𝑡 = 𝑠 = ෍ 𝜋 𝑎 𝑠 ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 𝑣𝜋 𝑠 = ෍ 𝜋 𝑎 𝑠 ෍ 𝑝 𝑎 𝑠 ′ ,𝑟 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 + 𝛾𝑣𝜋 𝑠′ 𝑎 𝑠 ′ ,𝑟

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

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

行動価値関数 • 状態𝑠になったあとは行動しなければならない．そう考えれば，行動𝑎にも依存 した価値関数も考えることができる． • 行動𝑎を考慮した価値関数を方策𝜋に対する行動価値関数といい，次のように書 く． 𝑘 • 𝑞𝜋 𝑠, 𝑎 = 𝐸𝜋 𝐺𝑡 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎 = 𝐸𝜋 σ∞ 𝑘=0 𝛾 𝑅𝑡+𝑘+1 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎 𝑠′ 𝑠 𝑎 池 草 原 𝑟 𝑟 池 草 原 𝑟 決まっている 𝑟 森 家

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

行動価値関数の式展開 1つ目の式 𝑞𝜋 𝑠, 𝑎 = 𝐸𝜋 𝐺𝑡 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎 = 𝐸𝜋 𝑅𝑡+1 + 𝛾𝐺𝑡+1 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝐸𝜋 𝑅𝑡+1 + 𝛾𝐺𝑡+1 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎, 𝑅𝑡+1 , = 𝑟 𝑆𝑡+1 = 𝑠′ 𝑠 ′ ,𝑟 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 + 𝛾𝐸𝜋 𝐺𝑡+1 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎, 𝑅𝑡+1 = 𝑟 𝑆𝑡+1 = 𝑠 ′ 𝑠 ′ ,𝑟 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 + 𝛾𝐸𝜋 𝐺𝑡+1 𝑆𝑡+1 = 𝑠 ′ 𝑠 ′ ,𝑟 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 + 𝛾𝑣𝜋 𝑠′ 𝑠 ′ ,𝑟 2つ目の式 𝑞𝜋 𝑠, 𝑎 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑟 + 𝛾𝐸𝜋 𝐺𝑡+1 𝑆𝑡+1 = 𝑠 ′ 𝑠 ′ ,𝑟 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑠 ′ ,𝑟 = ෍ 𝑝 𝑟, 𝑠 ′ 𝑠, 𝑎 𝑠 ′ ,𝑟 𝑟 + 𝛾 ෍ 𝜋(𝑎′ ∣ 𝑠 ′ )𝐸𝜋 𝐺𝑡+1 𝑆𝑡+1 = 𝑠 ′ , 𝐴𝑡+1 = 𝑎′ 𝑎′ 𝑟 + 𝛾 ෍ 𝜋(𝑎′ ∣ 𝑠 ′ )𝑞𝜋 (𝑠 ′ , 𝑎′ ) 𝑎′

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

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

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

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

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

バックアップダイアグラム • 𝑣∗ と𝑞∗ に対するベルマン最適方程式をあらわすバックアップダイアグラム(それ ぞれ左図，右図に対応) 𝑣∗ 𝑠 = max 𝑞𝜋∗ 𝑠, 𝑎 𝑎∈𝐴 𝑠 𝑞∗ 𝑠, 𝑎 = ෍ 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 𝑠 ′ ,𝑟 𝑟 + 𝛾 max 𝑞∗ 𝑠 ′ , 𝑎′ ′ 𝑎

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

動的計画法

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

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

反復方策評価（Iterative policy evaluation） • まず，近似価値関数の列𝑣0 , 𝑣1 , …があると考える． • 初期値𝑣0 は適当な数値で良い（ただし終状態の価値は0にする．）． • 反復回数𝑘 + 1のときの状態𝑠の価値𝑣𝑘+1 𝑠 は，一つ前の時刻𝑘の価値関数から 次のように求められる． 𝑣𝑘+1 𝑠 = 𝐸𝜋 𝑅𝑡+1 + 𝛾𝑣𝑘 𝑆𝑡+1 𝑆𝑡 = 𝑠 = ෍ 𝜋 𝑎 𝑠 ෍ 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑣𝑘 𝑠 ′ 𝑎 𝑠 ′ ,𝑟 • この反復計算は無限回繰り返すことで𝑣𝑘 = 𝑣𝜋 で収束する． • このアルゴリズムを反復方策評価（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 (1)を計算してみる． 更新式は 𝑉 𝑠 ← ෍ 𝜋 𝑎 𝑠 ෍ 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 ′ )] 𝑎 𝑠 ′ ,𝑟 だから 𝑉𝑘=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 状態𝑠の価値𝑉𝑘=2 (1)を計算してみる． 𝑉𝑘=2 1 1 1 1 = × −1 + 0 + × −1 − 1 + × −1 − 1 4 4 4 1 + × −1 − 1 = −1.75 4 すべての状態に対し同じ計算を行うと，図のよ うになる． 状態𝑠の価値𝑉𝑘=3 (1)を計算してみる． 𝑉𝑘=3 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方策）とすると， 右図のような方策を取る．この方策は最適方策になっている．

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

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

方策改善 • より良い方策𝜋 ′ (𝑠)は，状態𝑠で最も𝑞𝜋 𝑠, 𝑎 が高い行動をするgreedyな方策だろ う．つまり，より良い方策𝜋 ′ (𝑠)は次のように書ける． 𝜋 ′ 𝑠 = arg max 𝑞𝜋 𝑠, 𝑎 = arg max 𝐸 𝑅𝑡+1 + 𝛾𝑣𝜋 𝑆𝑡+1 ∣ 𝑆𝑡 = 𝑠, 𝐴𝑡 = 𝑎 𝑎 𝑎 = arg max ෍ 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑣𝜋 𝑠 ′ 𝑎 𝑠 ′ ,𝑟

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

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

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

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

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 すべての状態について𝑉 𝑠 を任意の値に初期化する．ただし，終端状態の𝑉 Loop: は0にする．𝑆 + なのは終端状態が除かれているからだろう． 𝛥←0 Loop for each 𝑠 ∈ 𝑆: 古い状態価値を保存する． 𝑣←𝑉 𝑠 𝑉 𝑠 ← max σs′,r 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 ′ )] 𝑎 𝛥 ← max(𝛥, |𝑣 − 𝑉(𝑠)|) unitil 𝛥 < 𝜃 Greedyな方策に基づき新たな状態価値を計算する． 新旧の状態価値の差分とΔを比較し大きい方をΔに代入する． 新旧の状態価値の差分が閾値より小さくなれば終了 Output a deterministic policy, 𝜋 ≈ 𝜋∗ , such that 𝜋 𝑠 = arg max σ𝑠′ ,𝑟 𝑝 𝑠 ′ , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉 𝑠 ′ ] 求めた状態価値を用いgreedyな方策を求める． 𝑎

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

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

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

おまけ

• この章で紹介した強化学習の問題の要素をまとめてみましょう。強化学習とは、目標を達成するためにどのように行動するかを相互作用から学習することです。強化学習 エージェントとその環境は、一連の離散的な時間ステップにわたって相互作用します。それらのインターフェイスの仕様によって特定のタスクが定義されます。アクショ ンはエージェントが行う選択であり、状態は選択を行うための基礎であり、報酬は選択を評価するための基礎です。エージェントの内部にあるものはすべてエージェント によって完全に認識され、制御可能です。外部にあるものはすべて不完全に制御可能ですが、完全に認識されている場合とそうでない場合があります。ポリシーは、エー ジェントが状態の関数としてアクションを選択する確率的ルールです。エージェントの目的は、時間の経過とともに受け取る報酬の量を最大化することです。 • 上記の強化学習設定が明確に定義された遷移確率で定式化されると、マルコフ決定プロセス (MDP) を構成します。有限 MDP は、有限の状態、アクション、および (ここ で定式化しているように) 報酬セットを持つ MDP です。現在の強化学習理論の多くは有限 MDP に限定されていますが、方法とアイデアはより一般的に適用されます。 • リターンは、エージェントが最大化しようとする将来の報酬の関数です (期待値)。タスクの性質と遅延報酬を割り引くかどうかに応じて、いくつかの異なる定義がありま す。割り引かない定式化は、エージェントと環境の相互作用が自然にエピソードに分かれるエピソード タスクに適しています。割り引く定式化は、相互作用が自然にエピ ソードに分かれず、無制限に続く継続タスクに適しています。2 種類のタスクのリターンを定義して、1 つの方程式セットがエピソード ケースと継続ケースの両方に適用で きるようにしようとしています。 • ポリシーの価値関数は、エージェントがポリシーを使用することを前提として、各状態または状態とアクションのペアに、その状態または状態とアクションのペアからの 期待リターンを割り当てます。最適価値関数は、各状態または状態とアクションのペアに、あらゆるポリシーで達成可能な最大の期待収益を割り当てます。価値関数が最 適なポリシーは、最適なポリシーです。状態と状態とアクションのペアの最適価値関数は、特定の MDP に対して一意ですが、最適なポリシーは多数存在する可能性があり ます。最適価値関数に関して貪欲なポリシーは、最適なポリシーである必要があります。ベルマン最適性方程式は、最適価値関数が満たす必要がある特別な一貫性条件で あり、原則として、最適価値関数に対して解くことができ、そこから比較的簡単に最適なポリシーを決定できます。 • 強化学習問題は、エージェントが最初に利用できる知識のレベルに関する仮定に応じて、さまざまな方法で提示できます。完全な知識の問題では、エージェントは環境の ダイナミクスの完全で正確なモデルを持っています。環境が MDP である場合、そのようなモデルは完全な 4 つの引数のダイナミクス関数 p (3.2) で構成されます。不完全 な知識の問題では、環境の完全で完璧なモデルは利用できません。 • エージェントが完全で正確な環境モデルを持っている場合でも、エージェントは通常、時間ステップごとに十分な計算を実行してそれを完全に使用することはできません。 使用可能なメモリも重要な制約です。価値関数、ポリシー、およびモデルの正確な近似値を構築するには、メモリが必要になる場合があります。実用的な関心のあるほと んどのケースでは、テーブルにエントリできるよりもはるかに多くの状態があり、近似値を作成する必要があります。 • 適切に定義された最適性の概念は、この本で説明する学習へのアプローチを体系化し、さまざまな学習アルゴリズムの理論的特性を理解する方法を提供しますが、強化学 習エージェントがさまざまな程度にしか近似できないというのは理想です。強化学習では、最適なソリューションが見つからないが、何らかの方法で近似する必要がある ケースに非常に関心があります。

• 強化学習の問題は、最適制御の分野におけるマルコフ決定過程 (MDP) の考え方に大きく依存しています。これらの歴史的影響と心理学からのそ の他の主要な影響については、第 1 章の簡単な歴史で説明しています。強化学習は、MDP に、現実的に大規模な問題に対する近似と不完全な情 報への重点を追加します。MDP と強化学習の問題は、人工知能における従来の学習および意思決定の問題とはほとんど関連がありません。ただ し、人工知能は現在、さまざまな観点から計画と意思決定のための MDP 定式化を精力的に研究しています。MDP は、より一般的な種類の目標 と不確実性を許容するという点で、人工知能で使用されていた以前の定式化よりも一般的です。 • MDP の理論は、たとえば Bertsekas (2005)、White (1969)、Whittle (1982、1983)、Puterman (1994) によって扱われています。有限ケースの 特に簡潔な扱いは、Ross (1983) によって示されています。MDP は確率的最適制御という見出しの下でも研究されており、適応最適制御法は強 化学習に最も密接に関連しています (例: Kumar、1985、Kumar および Varaiya、1986)。 • MDP の理論は、不確実性の下で一連の決定を行う問題を理解するための努力から発展しました。各決定は、以前の決定とその結果に依存する可 能性があります。これは、多段階決定プロセスの理論、または順次決定プロセスと呼ばれることもあり、第 2 章でバンディット問題 (複数状況問 題として定式化した場合の典型的な MDP) に関連して引用した Thompson (1933、1934) と Robbins (1952) の論文から始まる、順次サンプリン グに関する統計文献にルーツがあります。 • 我々が知る限り、強化学習がMDP形式論を用いて議論された最も古い例は、Andreae (1969b) による学習機械の統一的見解の記述である。 Witten と Corbin (1973) は、後にWitten (1977、1976a) がMDP形式論を用いて分析した強化学習システムを実験した。Werbos (1977) は、 MDPについては明示的に言及しなかったが、現代の強化学習法に関連する確率的最適制御問題の近似解法を提案した (Werbos、1982、1987、 1988、1989、1992 も参照)。Werbos のアイデアは当時は広く認識されていなかったが、人工知能を含むさまざまな領域で最適制御問題を近似 的に解くことの重要性を強調した点で先見の明があった。強化学習と MDP の最も影響力のある統合は Watkins (1989) によるものです。

• MDP のダイナミクスを p(s 0 , r | s, a) で特徴付けるという私たちのやり方は、少し変わっています。MDP の文献では、ダイナミクスを状態遷移確率 p(s 0 | s, a) と期待 される次の報酬 r(s, a) で記述する方が一般的です。しかし、強化学習では、期待値だけではなく、個々の実際の報酬またはサンプル報酬を参照しなければならないことが 多くなります。私たちの表記法では、S t と R t は一般に共同で決定されるため、同じ時間インデックスを持つ必要があることも明確になります。強化学習を教える際に、 私たちの表記法の方が概念的にわかりやすく、理解しやすいことがわかりました。 • システム理論的な状態の概念に関する優れた直感的な説明については、Minsky (1967) を参照してください。 • バイオリアクターの例は、Ungar (1990) と Miller と Williams (1992) の研究に基づいています。リサイクル ロボットの例は、Jonathan Connell (1989) が作成した缶収集 ロボットにヒントを得たものです。Kober と Peters (2012) は、強化学習のロボット工学への応用例を紹介しています。 • 報酬仮説は Michael Littman (個人的なコミュニケーション) が提案しました。 • 3.3–4 エピソード タスクと継続タスクの用語は、MDP 文献で通常使用される用語とは異なります。その文献では、次の 3 つのタイプのタスクを区別するのが一般的です。 (1) 有限期間タスク。特定の固定数のタイム ステップ後にインタラクションが終了します。(2) 不定期間タスク。インタラクションは任意の長さで継続できますが、最終的 には終了する必要があります。(3) 無限期間タスク。インタラクションは終了しません。エピソードタスクと継続タスクは、それぞれ不定期間タスクと無限期間タスクに似 ていますが、相互作用の性質の違いを強調することを好みます。この違いは、通常の用語で強調される目的関数の違いよりも根本的なようです。エピソードタスクでは不 定期間目的関数を使用し、継続タスクでは無限期間目的関数を使用することがよくありますが、これは根本的な違いではなく、よくある偶然の一致であると考えています。 • 極バランスの例は、Michie と Chambers (1968) および Barto、Sutton、Anderson (1983) からのものです。 • 3.5–6 長期的に何が良いか悪いかに基づいて価値を割り当てることは、古くから行われています。制御理論では、制御決定の長期的な結果を表す数値に状態をマッピングす ることが最適制御理論の重要な部分であり、これは 19 世紀の古典力学の状態関数理論を拡張して 1950 年代に開発されました (Schultz と Melsa、1967 などを参照)。コン ピューターをチェスをプレイするようにプログラムする方法を説明する際に、Shannon (1950) はチェスの位置の長期的な利点と欠点を考慮した評価関数を使用することを 提案しました。

• Watkins (1989) の q ⇤ を推定する Q 学習アルゴリズム (第 6 章) によって、動作価値関数が強化学 習の重要な部分となり、その結果、これらの関数はしばしば「Q 関数」と呼ばれます。しかし、動 作価値関数の考え方はこれよりずっと古いものです。Shannon (1950) は、関数 h(P, M) をチェス プログラムで使用して、位置 P での動き M が探索する価値があるかどうかを判断できると示唆し ました。Michie (1961、1963) の MENACE システムと Michie と Chambers (1968) の BOXES シ ステムは、動作価値関数を推定するものと理解できます。古典物理学では、Hamilton の主な関数は 動作価値関数であり、ニュートン力学はこの関数に関して貪欲です (例: Goldstein、1957)。アク ション価値関数は、縮約写像の観点から見た動的計画法の理論的扱いにおいて、デナード (1967) の 中心的な役割も果たしました。 • ベルマン最適性方程式 (v ⇤ の場合) は、リチャード ベルマン (1957a) によって普及され、彼はそ れを「基本関数方程式」と呼びました。連続時間と状態の問題に対するベルマン最適性方程式の対 応物は、ハミルトン ヤコビ ベルマン方程式 (または単にハミルトン ヤコビ方程式と呼ばれることが 多い) として知られており、その起源は古典物理学にあることを示しています (例: シュルツとメル サ、1967)。 • ゴルフの例は、クリス ワトキンスによって提案されました。