【ゼロから作るDeep Learning④】3.4~3.6

2025年度後期輪読会 #4 (10/23) ゼロから作るDeepLearning④ 3.4~ Bellman最適方程式 京都大学 理学部 数理科学科 3回 千葉 一世 0

アジェンダ ◼ Bellman最適方程式 ◼ Bellman方程式による最適方策導出 ◼ まとめ 1

アジェンダ ◼ Bellman最適方程式 ◼ Bellman方程式による最適方策導出 ◼ まとめ 2

Bellman最適方程式：任意の方策について成立するBellman方程式を、最適方策の場合に 最適性から変形した物 𝑣∗ (𝑠) = max ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ (𝑠′)} 𝑎 𝑠′ 導出 Bellman方程式は最適方策の時にも成立するので、最適方策で考えて 𝑣∗ 𝑠 = ෍ 𝜋∗ (𝑎|𝑠) ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ (𝑠′)} 𝑎 𝑠′ 今、 σ𝑠′ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ (𝑠′)}を計算したとすると、行動aに対する価値が決まる。 この時の最適な行動の選択は、明らかに価値が最も高い行動を確率１で選び続けることである。 例 ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ 𝑠′ 4 (𝑎1 ) + 𝛾𝑣∗ 𝑠 ′ } = ቐ 2 (𝑎2 ) −1 (𝑎3 ) ⇒ 1 (𝑎1 ) 𝜋∗ 𝑎 𝑠 = ቐ0 (𝑎2 ) 0 (𝑎3 ) 常に𝑎1 を選ぶ方策が 最も価値が高くなる 3

෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ 𝑠′ ⇒ 2 (𝑎1 ) + 𝛾𝑣∗ 𝑠 ′ } = ቐ 2 (𝑎2 ) −1 (𝑎3 ) 1 (𝑎1 ) 𝜋∗1 𝑎 𝑠 = ቐ0 (𝑎2 ) 0 (𝑎3 ) 0.5 (𝑎1 ) 𝜋∗2 𝑎 𝑠 = ቐ 0.5 (𝑎2 ) 0 (𝑎3 ) 0.7 (𝑎1 ) 𝜋∗3 𝑎 𝑠 = ቐ 0.3 (𝑎2 ) 0 (𝑎3 ) 行動価値次第では、常に同じものを選ぶ以外でも最適方策になり得るが、どの方策でも 行動価値が最大値を取る行動を選ぶため、状態価値関数は変化しない。 4

最適行動価値関数：最適方策を取った時の行動価値関数(Q関数) 𝑞∗ で表す。 行動価値関数が満たすBellman方程式も最適条件を用いて変形する。 Bellman方程式に 𝑞∗ を代入して 𝑞∗ (𝑠, 𝑎) = ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾 ෍ 𝜋∗ 𝑎′ 𝑠 ′ 𝑞∗ (𝑠 ′ , 𝑎′)} 𝑠′ 𝑎′ ここで、最適方策 𝜋∗ が常に最大価値の行動を選択することから 𝑞∗ (𝑠, 𝑎) = ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾 max 𝑞∗ (𝑠 ′ , 𝑎′)} 𝑎′ 𝑠′ これをQ関数のBellman最適方程式と呼ぶ。 状態価値関数とQ関数間の関係式・状態価値関数のBellman最適方程式・Q関数の表示による変形 ෍ 𝜋∗ 𝑎′ 𝑠′ 𝑞∗ (𝑠′ , 𝑎′) = 𝑣∗ (𝑠′) = max ෍ 𝑝 𝑠 𝑠′, 𝑎′ {𝑟 𝑠′, 𝑎′, 𝑠 𝑎′ 𝑎′ 𝑠 + 𝛾𝑣∗ (𝑠)} = max 𝑞∗ (𝑠′ , 𝑎′) 𝑎′ 5

おまけ MDPにおいて、今回考えているような状態空間・行動空間が有限で、報酬が有界なら 最適方策は必ず存在する。 最適方策は一意に存在するとは限らないが、最適状態価値関数・最適行動価値関数は一意に存在 MDPの最適方策の存在は、状態空間・行動空間が一般の空間で、 報酬が(ある程度のオーダーなら)非有界でも存在が保証される。 証明は、状態空間上の関数空間で最適状態価値関数を不動点に持つような縮小写像を構成し、 Banachの不動点定理により、最適状態価値関数が一意に存在することを示してから、 最適状態価値関数を用いて最適方策を構成する。 存在証明の方法として、作用素の繰り返し適用で近似させていく手法を取るため、 近似で求めることがしやすい。 6

アジェンダ ◼ Bellman最適方程式 ◼ Bellman方程式による最適方策導出 ◼ まとめ 7

２マス世界での最適方策導出例 {L1, L2}という状態で、{Left, Right}という行動があり、 r(L1, Left) = -1, r(L1, Right) = 1 r(L1, Left) = 0, r(L2, Right) = -1 という報酬を考えた時の最適方策を考える。 今回の例では、確率的な状態遷移ではなく状態と行動から決定論的に次の状態が決まるため、 Bellman最適方程式の確率的な状態遷移による総和の項が消える。 𝑣∗ 𝑠 = max ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ 𝑠 ′ } 𝑎 𝑠′ = max{𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ 𝑠 ′ 𝑎 1 (𝑠 ′ = 𝑓(𝑠, 𝑎)) 𝑠 = 𝑓(𝑠, 𝑎)とs, a に対して状態が決まるとき、p s s, a = ቊ 0 (𝑠 ′ ≠ 𝑓(𝑠, 𝑎)) 総和を取っても、 𝑠 ′ = 𝑓(𝑠, 𝑎) 以外の項は0で消える ′ ′ 8

割引率 0.9 で考えると、バックアップ線図からBellman最適方程式は以下になる。 −1 + 0.9𝑣∗ (𝐿1) 𝑣∗ 𝐿1 = 𝑚𝑎𝑥 ቊ 1 + 0.9𝑣∗ (𝐿2) 0.9𝑣∗ (𝐿1) 𝑣∗ 𝐿2 = 𝑚𝑎𝑥 ቊ −1 + 0.9𝑣∗ (𝐿2) これは𝑣∗ 𝐿1 と𝑣∗ 𝐿2 の2変数非線型連立方程式となっており、解ける。 9

連立方程式を解く どちらがmaxかで場合分けをして ⇒ 𝑣∗ 𝐿1 = −10 𝑣∗ 𝐿2 = −9 −1 + 0.9𝑣∗ 𝐿1 < 1 + 0.9𝑣∗ 𝐿2 でmaxに矛盾 𝑣∗ 𝐿1 = 1 + 0.9𝑣∗ (𝐿2) 𝑣∗ 𝐿2 = 0.9𝑣∗ (𝐿1) ⇒ 𝑣∗ 𝐿1 = 5.26 … 𝑣∗ 𝐿2 = 4.73 … maxにも合致するのでこれが解 𝑣∗ 𝐿1 = −1 + 0.9𝑣∗ (𝐿1) 𝑣∗ 𝐿2 = −1 + 0.9𝑣∗ (𝐿2) ⇒ 𝑣∗ 𝐿1 = −10 𝑣∗ 𝐿2 = −10 −1 + 0.9𝑣∗ 𝐿1 < 1 + 0.9𝑣∗ 𝐿2 でmaxに矛盾 𝑣∗ 𝐿1 = 1 + 0.9𝑣∗ (𝐿2) 𝑣∗ 𝐿2 = −1 + 0.9𝑣∗ (𝐿2) ⇒ 𝑣∗ 𝐿1 = −8 𝑣∗ 𝐿2 = −10 1 + 0.9𝑣∗ (𝐿2) < 0.9𝑣∗ (𝐿1) でmaxに矛盾 𝑣∗ 𝐿1 = −1 + 0.9𝑣∗ (𝐿1) 𝑣∗ 𝐿2 = 0.9𝑣∗ (𝐿1) 2変数程度＋報酬が単純な形なら、気合で解くことができる。 𝒗∗ 𝑳𝟏 = 𝟓. 𝟐𝟔 𝒗∗ 𝑳𝟐 = 𝟒. 𝟕𝟑 10

最適方策を求める 最適行動価値関数から、価値が最大となる行動を選べばgreedyな方策が求められる。 状態 s での最適な行動を𝜇∗ 𝑠 として、以下でgreedyな最適方策を表せる。 𝜇∗ 𝑠 = argmax 𝑞∗ (𝑠, 𝑎) 𝑎 最適行動価値関数のBellman方程式から、 𝜇∗ 𝑠 = argmax 𝑞∗ (𝑠, 𝑎) = argmax ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ (𝑠′)} 𝑎 𝑎 𝑠′ = argmax {𝑟 𝑠, 𝑎, 𝑓(𝑠, 𝑎) + 𝛾𝑣∗ (𝑓(𝑠, 𝑎))} 𝑎 11

状態L1, L2で、行動LeftとRightを取るときの行動価値を計算すると、状態遷移は以下で 𝑓 𝐿1, 𝐿𝑒𝑓𝑡 = 𝐿1, 𝑓 𝐿2, 𝐿𝑒𝑓𝑡 = 𝐿1, 𝑓 𝐿1, 𝑅𝑖𝑔ℎ𝑡 = 𝐿2 𝑓 𝑙2, 𝑅𝑖𝑔ℎ𝑡 = 𝐿2 𝑟 𝑠, 𝑎, 𝑓(𝑠, 𝑎) + 𝛾𝑣∗ (𝑓(𝑠, 𝑎))をそれぞれの場合に計算すると、 s=L1, a=Left s=L1, a=Right −1 + 0.9𝑣∗ 𝐿1 = 3.734 1 + 0.9𝑣∗ 𝐿2 = 5.257 s=L2, a=Left s=L2, a=Right 0.9𝑣∗ 𝐿1 = 4.734 −1 + 0.9𝑣∗ 𝐿2 = 3.257 各行動の行動価値より、最適方策は行動価値が最大となる行動を選んで、 𝜇∗ 𝐿1 = 𝐿2 𝜇∗ 𝐿2 = 𝐿1 Bellman方程式から、左右を行き来する方策が最適であることが示された。 12

まとめ Bellman最適方程式により、状態価値関数の連立方程式が得られ、理論上は 最適方策時の状態価値関数が求まる。 状態価値関数から行動価値関数が求められ、最適方策まで調べることができる。 現実的には状態・行動が多すぎて連立方程式が解けないことが多く、実数値パラメータなど 状態・行動が有限でないことも多く直接的には最適方策は求められない。 直接求めることが難しくても、Bellman方程式の関係から近似的に求めていくこともできる。 13

まとめ Bellman方程式 𝑣𝜋 𝑠 = ෍ 𝜋∗ (𝑎|𝑠)𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣𝜋 (𝑠′)} 𝑎,𝑠′ 𝑞𝜋 (𝑠, 𝑎) = ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾 ෍ 𝜋 𝑎′ 𝑠 ′ 𝑞𝜋 (𝑠 ′ , 𝑎′)} 𝑠′ 𝑎′ Bellman最適方程式 𝑣∗ 𝑠 = max ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ (𝑠′)} 𝑎 𝑠′ 𝑞∗ (𝑠, 𝑎) = ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾 max 𝑞∗ (𝑠 ′ , 𝑎′)} 最適方策 𝑎′ 𝑠′ 𝜇∗ 𝑠 = argmax 𝑞∗ (𝑠, 𝑎) = argmax ෍ 𝑝 𝑠 ′ 𝑠, 𝑎 {𝑟 𝑠, 𝑎, 𝑠 ′ + 𝛾𝑣∗ (𝑠′)} 𝑎 𝑎 𝑠′ 14