# ベルマン方程式 ## 定義 ベルマン方程式(Bellman equation)は、強化学習における価値(状態価値・行動価値)を、隣接する時刻2つの価値と即時報酬だけの関係に分解する方程式である。強化学習が最適化しようとする収益 $G_t=\sum_k \gamma^k r_{t+k+1}$ は将来にわたる無限個の報酬の和として定義されるため直接扱えないが、ベルマン方程式はこの無限個の要素を、隣り合う時刻の価値と報酬という2つの要素だけの関係に圧縮する。これにより価値を効率的に推定できるようになる。強化学習では「ベルマン期待値方程式」と「ベルマン最適方程式」の2種類が登場する。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.5) **状態価値のベルマン期待値方程式**(任意の方策 $\pi$ について成り立つ): $V(s) = \mathbb{E}_\pi[r_{t+1}+\gamma V(s')\mid s_t=s]$ **行動価値のベルマン期待値方程式**: $Q(s,a) = \mathbb{E}_\pi\left[r_{t+1}+\gamma\sum_{a'}\pi(a'|s')Q(s',a')\mid s_t=s,a_t=a\right]$ ベルマン期待値方程式が状態価値では前掲の(即時報酬+割引付き次時刻状態価値)という単純な和になるのに対し、行動価値版では次時刻の各行動について方策の確率で重み付けした和をとる必要がある点が異なる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.5) **ベルマン最適方程式**は、最適方策 $\pi^*$(すべての方策 $\pi$ について $\pi^*\geq\pi$ を満たす、半順序上で唯一存在する方策)のもとで成り立つ式であり、非線形の $\max$ 操作を含む: $V^*(s)=\max_a\left[r(s,a)+\gamma\sum_{s'}p(s'|s,a)V^*(s')\right]$ $Q^*(s,a)=r(s,a)+\gamma\sum_{s'}p(s'|s,a)\max_{a'}Q^*(s',a')$ 最適行動価値がわかれば最適方策は $\pi^*(s)=\arg\max_a Q^*(s,a)$ で直ちに求められる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.5) ## 解析的な解法と動的計画法 状態をすべて列挙できる場合、状態価値ベクトル $v$・即時報酬ベクトル $r$・遷移行列 $P$ を使ってベルマン期待値方程式は $v=r+\gamma Pv$ と簡潔に表せ、$v=(I-\gamma P)^{-1}r$ として解析的に解ける。$(I-\gamma P)^{-1}$ は将来にわたって各状態に到達する確率を割引率で割り引いた和(後続表現、successor representation)を表し、状態価値は後続表現と報酬の積として計算できる。しかし多くの実問題では状態数が膨大・遷移行列が未知・逆行列の計算量が大きすぎるため、解析的に解くことは稀である。ベルマン最適方程式は非線形の $\max$ を含むため、そもそも解析的に解けない。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.5) そこで動的計画法(dynamic programming)を使った数値解法である**ベルマンバックアップ操作**(Bellman backup)を用いる。方策 $\pi$ に基づき状態 $s$ から $s'$ に遷移し報酬 $r$ を受け取ったとき、$V(s):=r+\gamma V(s')$ と更新する。この更新をすべての状態に同時に適用し続けると、状態価値は真の状態価値に収束することが証明できる。証明の骨子は、状態価値間の距離を測る $\infty$-ノルムのもとでベルマンバックアップ操作が割引率 $\gamma$ による**γ縮退**(操作を適用するたびに任意の2つの状態価値の差が $\gamma$ 倍ずつ指数的に小さくなる性質)であることを示す点にある。行動価値のベルマンバックアップ操作、および $\max$ を使うベルマン最適バックアップ操作についても同様にγ縮退が成り立ち、真の(最適)価値へ収束する。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.5) 状態や行動の種類数が多く、すべてを列挙してベルマンバックアップ操作を適用できない現実的な問題では、限られた経験から価値をオンラインで更新していく必要がある。これがMC学習・TD学習・SARSA・Q学習といったオンライン推定手法の出発点になる。TD学習はベルマン期待値方程式の右辺 $r+\gamma V(s')$ を「TD目標」として使い、収益の確定(エピソード終了)を待たずに価値を更新するブートストラップ手法であり、Q学習はベルマン最適方程式の右辺 $r+\gamma\max_{a'}Q(s',a')$ を目標に使う。両者ともベルマン方程式が真の価値においてのみ成立する等式であることを利用し、その等式のズレ(ベルマンバックアップ誤差)を0に近づける更新とみなせる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.5-4.7, §4.10) ## 横断的知見 1 ソース目のため、複数ソースの突き合わせによる横断的知見は今後の蓄積に委ねる。[[DQN]] の目的関数(TD目標との二乗誤差の最小化)や [[方策勾配法]] のActor-Critic法(Critic側でのTD学習)は、いずれも本ページのベルマン期待値方程式・ベルマン最適方程式を関数近似のもとで使い直したものであり、これらの concept は本ページを基礎として積み増されている。 ## 未解決の問い - 関数近似(ニューラルネットワーク)を使う場合、γ縮退の議論に基づく「唯一解への収束」保証は失われる。関数近似のもとでベルマンバックアップ操作(あるいはそれに相当するTD更新)の収束を保証する条件は何か。 - 後続表現(successor representation)は報酬・目標タスクが変わっても再利用できる表現として注目されているが、本章では詳細に扱われていない。後続表現に基づく転移学習は、DQNやAlphaGoのような大規模な関数近似モデルにどこまで応用できるか。 ## 関連 - source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] - concept: [[強化学習]] / [[方策勾配法]] / [[DQN]] ## 出典 - 岡野原大輔, 『ディープラーニングを支える技術〈2〉』, 技術評論社, 2022, 第4章, §4.5.