【ゼロから作るDeep Learning④】4.1~4.3

2025年度後期輪読会 #4（2025/10/27） ゼロから作るDeep Learning❹ 4.1-4.3 動的計画法 京都大学 教育学部 B2 坂本竜弥 0

アジェンダ ◼ （前回までの復習） ◼ 4.1 動的計画法と方策評価 ◼ 4.2 より大きな問題へ ◼ 4.3 方策反復法 1

アジェンダ ◼ （前回までの復習） ◼ ◼ ◼ 2

前回までの復習 ベルマン方程式と連立方程式ソルバを使って価値関数を求めた。 状態遷移確率 → 報酬関数 → ← 価値関数 方策 → 𝑣𝜋 (𝑠) = ෍ 𝜋 (𝑎|𝑠)𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑣𝜋 (𝑠’)} 𝑎, 𝑠’ 3

前回までの復習 状態遷移確率、報酬関数、方策とは…。 ← 状態遷移確率 … 実際にその行動を取るか ← 報酬関数 … どんな報酬を得るか ← 方策 … どんな行動を取るか 4

前回までの復習 価値関数とベルマン方程式とは…。 ・価値関数の定義 𝑣𝜋 (𝑠) = 𝔼[𝑅𝑡 + 𝛾𝑅𝑡+1 + 𝛾 2 𝑅𝑡+2 + ⋯ |𝑆𝑡 = 𝑠] しかし、無限を含む期待値計算は通常できない。 そこで使うのがベルマン方程式。 𝑣𝜋 (𝑠) = ෍ 𝜋 (𝑎|𝑠)𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑣𝜋 (𝑠’)} ↑ 価値関数 （現在の状態） 𝑎, 𝑠’ ↑ ↑ ↑ ↑ 方策 状態遷移確率 報酬関数 価値関数 （次の状態） 5

アジェンダ ◼ ◼ 4.1 動的計画法と方策評価 ◼ ◼ 6

方策評価と方策制御 強化学習には方策評価と方策制御の2つのタスクがある。 ・方策評価とは… その方策の価値関数を求めること。 ・方策制御とは… 方策を最適化していくこと。 方策評価 方策制御 ← ゴール 方策制御を行うには、まず方策評価を行う必要がある。 そこで、動的計画法（DP）を用いて方策評価を行う。 7

更新式化 ベルマン方程式を「更新式」にすることで、動的計画法に向けて使いやすくする。 𝑣𝜋 (𝑠) = ෍ 𝜋 (𝑎|𝑠)𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑣𝜋 (𝑠’)} ↑ 𝑎, 𝑠’ 価値関数 ↑ ↑ ↑ ↑ 方策 状態遷移確率 報酬関数 価値関数 （現在の状態） （次の状態） 「更新式」化 𝑽𝒌+𝟏 (𝒔) = ෍ 𝜋 (𝑎|𝑠)𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑽𝒌 (𝒔’)} ↑ 𝑎, 𝑠’ 価値関数 （𝑘 + 1回目の更新） ↑ ↑ ↑ ↑ 方策 状態遷移確率 報酬関数 価値関数 𝑉は真の価値関数 𝑣とは異なり 価値関数を更新する過程に おける「推測値」 （𝑘回目の更新） 8

反復方策評価 価値関数𝑉を繰り返し更新していくことで、真の価値関数 𝑣𝜋 (𝑠) を求める。 初期値𝑉0 (𝑠)（例えば、すべての状態𝑠において𝑉0 (𝑠) = 0）をもとに、 更新式を用いて、𝑉1 (𝑠)、𝑉2 (𝑠)と繰り返し更新して真の価値関数 𝑣𝜋 (𝑠) を求める。 このアルゴリズムを反復方策評価と呼ぶ。（反復方策評価は動的計画法（DP）の中の一つ） 更新式 （𝐤 = 𝟎の場合） 𝑽𝟏 (𝒔) = ෍ 𝜋 (𝑎|𝑠)𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑽𝟎 (𝒔’)} ↑ ↑ 𝑎, 𝑠’ 価値関数 価値関数 （𝒌 + 𝟏回目の更新） （𝐤回目の更新） ※ちなみに、更新によって価値関数は𝑣𝜋 (𝑠)に収束することが証明されている。証明は以下を参照。 Sutton, Richard S., and Andrew G. Barto. “Reinforcement learning: An introduction.” MIT press, 2018. 9

アジェンダ ◼ ◼ ◼ 4.2 より大きな問題へ ◼ 10

より大きな問題へ 「3×4マスのグリッドワールド」を用いて、反復方策評価の流れを確認する。 ｻﾖﾅﾗ > ルールの変更点 ・エージェントは上下左右の4方向に進む。 ・壁にあたってもマイナス報酬はない。 ・リンゴを取るとタスク終了。 その他の条件 ・エージェントの方策𝜋はランダム。（上下左右それぞれ25%の確率で移動する） ・初期値𝑉0 (𝑠)は、すべての状態𝑠において𝑉0 (𝑠) = 0。 ・状態遷移は決定論的に決まる。（後ほど解説） 11

更新式の復習 状態遷移が決定論的な場合の更新式を求める。 状態遷移が決定論的とは ある状態𝑠で、ある行動𝑎を行うと、次の状態𝑠’は1つに決まるということ。 たとえば、右に移動するという行動に対しては、100%右に移動する場合など。 ← 従来の更新式 ← 赤枠部分σ𝑠’ 𝑝(𝑠’|𝑠, 𝑎)は、今回次の状態𝑠’が 1つに決まるので、和を求める必要がない。 ← 状態遷移が決定論的な場合の更新式 12

反復方策評価の実践 1ステップ更新の流れを通して、反復方策評価の求め方を確認する。 各状態（グリッド）を順に更新 各状態に対して、価値関数を更新していく。 ・それぞれの状態（グリッド）に価値関数の初期値𝑉0 (𝑠) = 0 があらかじめ設定されている。 ・各行動は、上下左右への移動という4種類がある。 𝑽𝒌+𝟏 (𝒔) = ෍ 𝜋 (𝑎|𝑠){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑽𝒌 (𝒔’)} 𝑎 ↑ ↑ 各遷移先𝑠’の価値関数を参照 各行動によって遷移先𝑠’が異なる この更新を繰り返して、真の価値関数 𝑣𝜋 (𝑠) を求める。 （実装の際は更新量の閾値を設定して、近似値を求める） 13

アジェンダ ◼ ◼ ◼ ◼ 4.3 方策反復法 14

方策反復法 最適方策を得るために、方策反復法を使用する。 方策評価 方策制御 ← ゴール 反復方策評価 まずは「最適方策」について復習する。 𝜇∗ 𝑠 = argmax 𝑞∗ 𝑠, 𝑎 = argmax ෍ 𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑣∗ (𝑠’)} 𝑎 ↑ 最適方策 𝑎 ↑ 𝑞∗ 𝑠, 𝑎 が最大値を取る行動𝑎 𝑠’ 𝑞∗ 𝑠, 𝑎 …最適方策における行動価値関数 𝑣∗ (𝑠) …最適方策における状態価値関数 上式より、最適方策𝜇∗ を得るには𝑣∗ が必要。だが、 𝑣∗ は最適方策における状態価値関数。 つまり、𝑣∗ を得るには最適方策𝜇∗ が必要。結局どちらも分からない。 15

greedy化 ﾋｻｼﾌﾞﾘ> 最適方策の式を使ってgreedy化する。 最適方策𝜇∗ の式を、「何らかの決定論的方策𝜇」の式として考えてみる。 𝜇’ 𝑠 = argmax 𝑞𝜇 𝑠, 𝑎 = argmax ෍ 𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑣𝜇 (𝑠’)} 𝑎 ↑ 新たな方策 𝑎 𝑠’ ↑ 方策𝜇(s’)における状態価値関数 上式によって、方策𝜇 𝑠 を更新していくとする。（これを「greedy化」という） このとき、実は方策改善定理によって、すべての状態𝑠において𝜇‘ 𝑠 ≥ 𝜇 𝑠 であることが 分かっている。 また、𝜇‘ 𝑠 = 𝜇 𝑠 のとき、つまり方策𝜇 𝑠 が更新されないとき、𝜇 𝑠 は最適方策である。 ※方策改善定理の証明は以下を参照。 Sutton, Richard S., and Andrew G. Barto. “Reinforcement learning: An introduction.” MIT press, 2018. 16

評価と改善を繰り返す 反復方策評価とgreedy化を用いて、最適方策を求める。 反復方策評価の更新式 𝑉𝑘+1 (𝑠) = ෍ 𝜋 (𝑎|𝑠)𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑉𝑘 (𝑠’)} 𝑎, 𝑠’ greedy化の式 𝜇’ 𝑠 = argmax ෍ 𝑝(𝑠’|𝑠, 𝑎){𝑟(𝑠, 𝑎, 𝑠’) + 𝛾𝑣𝜇 (𝑠’)} 𝑎 𝑠’ この評価と改善を繰り返すアルゴリズムを、 「方策反復法」と呼ぶ。 方策反復法の実装へと続く… 17