はじめに

ベルマン方程式は、動的計画法と強化学習の中心にある再帰式です。
ただし、式だけを見ると

V(s)=\max_a \left\{ r(s,a) + \beta \mathbb{E}[V(s') \mid s,a] \right\}

がなぜ成立するのか、どこで「最適化」と「期待値」が入ってくるのかが見えにくくなりがちです。

この記事では、ベルマン方程式をいきなり提示するのではなく、

逐次最適化問題をどう書くか
価値関数をどう定義するか
最適性原理が何を意味するか
そこからどう再帰式が導かれるか

を順番に整理します。

主眼は、ベルマン方程式は新しい魔法の公式ではなく、「全期間の問題を今期と将来に分解した結果」として自然に現れることを明確にすることです。

1. 問題設定

まず、離散時間の逐次意思決定問題を考えます。時点は

t=0,1,2,\dots

で進み、各時点で主体は状態 $s_t \in \mathcal{S}$ を観測し、行動 $a_t \in \mathcal{A}(s_t)$ を選ぶとします。

行動を選ぶと 1 期利得

r(s_t,a_t)

を得て、次期状態 $s_{t+1}$ は遷移法則

P(\mathrm{d}s' \mid s_t, a_t)

に従って確率的に決まるとします。

ここでの記号は次の意味です。

$s_t$ : その時点での状態
$a_t$ : その時点での行動
$r(s_t,a_t)$ : 即時報酬
$P(\mathrm{d}s' \mid s,a)$ : 次期状態の確率分布
$\beta \in (0,1)$ : 割引因子

割引因子 $\beta$ を入れるのは、将来の報酬を現在価値に直すためです。
このとき、ある方策 $\pi$ のもとでの目的関数は

\mathbb{E}^{\pi}\left[ \sum_{t=0}^{\infty} \beta^t r(s_t,a_t) \;\middle|\; s_0=s \right]

です。

ここで方策 $\pi$ は、各状態でどの行動を選ぶかを決めるルールです。
以降では説明を簡単にするため、まず定常なマルコフ方策

a_t = \pi(s_t)

を考えます。

2. 価値関数とは何か

状態 $s$ から出発したとき、その後に得られる割引総報酬の期待値を価値関数と呼びます。

方策 $\pi$ を固定した価値関数は

V^{\pi}(s) = \mathbb{E}^{\pi}\left[ \sum_{t=0}^{\infty} \beta^t r(s_t,\pi(s_t)) \;\middle|\; s_0=s \right]

で定義されます。

この式が表しているのは、状態 $s$ からスタートして、方策 $\pi$ をずっと使い続けたときの将来価値です。

最適価値関数は

V^*(s) = \sup_{\pi} V^{\pi}(s)

で定義されます。
これは「状態 $s$ にいるとき、最もよい行動ルールを使った場合に達成できる最大価値」です。

ベルマン方程式は、この $V^\pi$ や $V^*$ が満たす再帰的な関係式です。

3. まず有限ホライズンで考える

無限期間の式にいきなり入る前に、有限ホライズンの問題を見ると導出の骨格が分かりやすくなります。

終端時点を $T$ として、時点 $t$ における価値関数を

V_t(s) = \sup_{\pi} \mathbb{E}\left[ \sum_{\tau=t}^{T} \beta^{\tau-t} r(s_{\tau}, a_{\tau}) \;\middle|\; s_t=s \right]

とします。

このとき、時点 $t$ の問題は

今期に行動 $a_t$ を選ぶ
即時報酬 $r(s_t,a_t)$ を得る
次期状態 $s_{t+1}$ に移る
そこから先は、残り期間 $T-(t+1)$ の最適問題になる

という 2 段階に分けられます。

したがって

V_t(s) = \max_{a \in \mathcal{A}(s)} \left\{ r(s,a) + \beta \mathbb{E}\left[ V_{t+1}(s_{t+1}) \mid s_t=s, a_t=a \right] \right\}

が成り立ちます。

これが有限ホライズン版の Bellman 方程式です。

重要なのは、ここで突然新しい理論を導入しているわけではないことです。
単に「今期の利得」と「次期以降の最適継続価値」に問題を分解しただけです。

終端条件は例えば

V_T(s) = \max_{a \in \mathcal{A}(s)} r(s,a)

や、終端価値関数 $g(s)$ を使って

V_T(s)=g(s)

のように与えます。

4. 方策を固定したときの Bellman 方程式

次に、無限ホライズンで方策 $\pi$ を固定した場合を考えます。
この導出が最も基本です。

価値関数の定義は

V^{\pi}(s) = \mathbb{E}^{\pi}\left[ \sum_{t=0}^{\infty} \beta^t r(s_t,\pi(s_t)) \;\middle|\; s_0=s \right]

でした。ここで和の最初の 1 項を取り出すと

V^{\pi}(s) = \mathbb{E}^{\pi}\left[ r(s_0,\pi(s_0)) + \sum_{t=1}^{\infty} \beta^t r(s_t,\pi(s_t)) \;\middle|\; s_0=s \right].

$s_0=s$ なので最初の項は確定しており、

r(s_0,\pi(s_0)) = r(s,\pi(s))

です。よって

V^{\pi}(s) = r(s,\pi(s)) + \mathbb{E}^{\pi}\left[ \sum_{t=1}^{\infty} \beta^t r(s_t,\pi(s_t)) \;\middle|\; s_0=s \right].

次に、残りの和から $\beta$ を 1 つくくり出し、添字を 1 つずらすと

\sum_{t=1}^{\infty} \beta^t r(s_t,\pi(s_t)) = \beta \sum_{t=0}^{\infty} \beta^t r(s_{t+1},\pi(s_{t+1})).

したがって

V^{\pi}(s) = r(s,\pi(s)) + \beta \mathbb{E}^{\pi}\left[ \sum_{t=0}^{\infty} \beta^t r(s_{t+1},\pi(s_{t+1})) \;\middle|\; s_0=s \right].

ここで、 $s_1$ が分かれば、その先の期待割引総報酬はちょうど $V^\pi(s_1)$ です。
したがって条件付き期待値の塔の性質を使うと

V^{\pi}(s) = r(s,\pi(s)) + \beta \mathbb{E}^{\pi}\left[ V^{\pi}(s_1) \mid s_0=s \right].

つまり

V^{\pi}(s) = r(s,\pi(s)) + \beta \mathbb{E}\left[ V^{\pi}(s') \mid s, \pi(s) \right]

が成り立ちます。これが方策評価の Bellman 方程式です。

離散状態なら期待値は総和で書けます。

V^{\pi}(s) = r(s,\pi(s)) + \beta \sum_{s' \in \mathcal{S}} P(s' \mid s,\pi(s))V^{\pi}(s').

この式の意味は単純で、

今すぐ得る報酬
次期状態に移った後の継続価値の期待値

の和が、現在の価値だということです。

5. 最適性原理

ここで、最適価値関数 $V^*$ に進むために必要なのが最適性原理です。

最適性原理の核心は次です。

ある状態 $s$ から出発した最適計画は、最初の行動を選んだ後に到達する任意の次期状態 $s'$ から見ても、その先の部分計画が最適でなければならない。

これは直観的には当然です。
もし将来のある時点から見てもっとよい部分計画があるなら、その部分だけ差し替えることで現在から見た総価値も改善できてしまい、もともとの計画は最適ではなかったことになります。

この原理があるからこそ、将来部分を単なる「何かの続き」ではなく、その状態から始まる最適価値 $V^*(s')$ としてまとめられます。

6. 最適価値関数の Bellman 方程式の導出

最適価値関数は

V^*(s)=\sup_{\pi} V^\pi(s)

でした。

時点 0 で状態 $s$ にいるとします。このとき最初にどの行動 $a$ を取るかは自由に選べます。
その行動を選ぶと、今期の報酬は $r(s,a)$ です。さらに次期状態 $s'$ に移った後は、最適性原理より、その時点から再び最適に振る舞えばよいので継続価値は $V^*(s')$ です。

したがって、最初に行動 $a$ を選んだときの総価値は

r(s,a)+\beta \mathbb{E}[V^*(s') \mid s,a]

です。

今期に取りうる行動は複数あるので、その中で最もよいものを選べば

V^*(s) = \max_{a \in \mathcal{A}(s)} \left\{ r(s,a)+\beta \mathbb{E}[V^*(s') \mid s,a] \right\}

となります。これがBellman 最適方程式です。

離散状態空間なら

V^*(s) = \max_{a \in \mathcal{A}(s)} \left\{ r(s,a)+ \beta \sum_{s' \in \mathcal{S}} P(s' \mid s,a)V^*(s') \right\}

と書けます。

この式は

いま行動を選ぶ最適化
その結果として生じる次期状態の期待値
その先の最適継続価値

の 3 つをまとめたものです。

6.1 導出の本質

ベルマン方程式の導出で本当に使っているのは次の 3 点だけです。

目的関数を「今期」と「将来」に分解できること
状態 $s'$ が与えられれば、将来部分はその状態だけで要約できること
最適計画の将来部分も最適であること

この 3 点がそろうと、全期間問題は再帰式として書けます。

7. Bellman 作用素と不動点

Bellman 方程式は単なる記述式ではなく、作用素の不動点問題として理解できます。

任意の関数 $V$ に対して Bellman 作用素 $T$ を

(TV)(s) = \max_{a \in \mathcal{A}(s)} \left\{ r(s,a)+\beta \mathbb{E}[V(s') \mid s,a] \right\}

で定義します。

すると Bellman 最適方程式は

V^* = TV^*

と書けます。
つまり最適価値関数は Bellman 作用素の不動点です。

7.1 なぜ縮小写像になるのか

sup-norm

\|V-W\|_\infty = \sup_{s \in \mathcal{S}} |V(s)-W(s)|

を考えます。
このとき任意の $s$ について

(TV)(s) = \max_a \left\{ r(s,a)+\beta \mathbb{E}[V(s') \mid s,a] \right\}

と

(TW)(s) = \max_a \left\{ r(s,a)+\beta \mathbb{E}[W(s') \mid s,a] \right\}

の差を比較すると、報酬項 $r(s,a)$ は共通なので差は継続価値の部分だけから出ます。

最大値どうしの差は、それぞれの候補の差の最大値以下なので

|(TV)(s)-(TW)(s)| \le \beta \sup_a \left| \mathbb{E}[V(s')-W(s') \mid s,a] \right|.

期待値の絶対値は期待値の絶対値以下であり、

\left| \mathbb{E}[V(s')-W(s') \mid s,a] \right| \le \mathbb{E}[|V(s')-W(s')| \mid s,a] \le \|V-W\|_\infty

なので

|(TV)(s)-(TW)(s)| \le \beta \|V-W\|_\infty.

両辺の $s$ に関する上限を取ると

\|TV-TW\|_\infty \le \beta \|V-W\|_\infty

です。 $\beta \in (0,1)$ なので $T$ は縮小写像です。

したがって Banach の不動点定理より、 $T$ には一意な不動点が存在し、それが最適価値関数 $V^*$ です。

この議論が重要なのは、Bellman 方程式が

解を持つ
その解が一意である
反復計算で近づける

ことを保証してくれるからです。

8. Value Iteration がうまくいく理由

縮小写像であることから、初期関数 $V_0$ を適当に選んで

V_{n+1}=TV_n

と繰り返せば

V_n \to V^*

が成り立ちます。

これは Value Iteration の理論的根拠です。
計算手順としては単純ですが、本質的には「Bellman 作用素が誤差を毎回 $\beta$ 倍に縮める」ことに支えられています。

9. 具体例

最小限の 2 状態 2 行動の例で、ベルマン方程式が何をしているかを見ます。

状態空間を

\mathcal{S} = \{ s_G, s_B \}

行動集合を

\mathcal{A}=\{ a_0, a_1 \}

とします。

報酬は次のように与えるとします。

良い状態 $s_G$ では、保守的行動 $a_0$ の報酬は 2
良い状態 $s_G$ で積極的行動 $a_1$ の報酬は 3
悪い状態 $s_B$ では、 $a_0$ の報酬は 1
悪い状態 $s_B$ では、 $a_1$ の報酬は 0

さらに遷移は例えば

P(s_G \mid s_G,a_0)=0.8,\qquad P(s_G \mid s_G,a_1)=0.6

P(s_G \mid s_B,a_0)=0.4,\qquad P(s_G \mid s_B,a_1)=0.7

とします。割引因子を $\beta=0.9$ とすると、Bellman 方程式は

V^*(s_G) = \max \left\{ 2 + 0.9 \left(0.8V^*(s_G)+0.2V^*(s_B)\right), \; 3 + 0.9 \left(0.6V^*(s_G)+0.4V^*(s_B)\right) \right\}

V^*(s_B) = \max \left\{ 1 + 0.9 \left(0.4V^*(s_G)+0.6V^*(s_B)\right), \; 0 + 0.9 \left(0.7V^*(s_G)+0.3V^*(s_B)\right) \right\}

です。

ここで各候補の中身は

その行動を今すぐ取ったときの即時報酬
その行動がもたらす将来状態分布のもとでの継続価値

を表しています。

ベルマン方程式は、各状態ごとに「どちらの行動が総価値を最大化するか」を比較しているだけです。
1 期先だけを見ているように見えて、実際には $V^*(s_G), V^*(s_B)$ の中にさらにその先の全期間の価値が入っているので、結果として無限期間の最適化を実現しています。

10. Bellman 方程式が成立するための仮定

ベルマン方程式は強力ですが、いつでも無条件に使えるわけではありません。
少なくとも次の点が重要です。

将来価値が現在の状態で十分に要約されること
これは Markov 性に対応します。過去の履歴全体が必要なら、状態定義を拡張しなければなりません。
期待割引総報酬が有限であること
$\beta \in (0,1)$ や報酬の有界性は、この点で重要です。
実行可能な行動集合 $\mathcal{A}(s)$ が適切に定義されていること
最適化がそもそも意味を持つ必要があります。
最適性原理が使えること
将来部分を切り出したとき、それが再び同型の問題として書ける必要があります。

厳密な数学では、可測性、コンパクト性、上半連続性なども必要になります。
ただし初学段階では、まず「なぜ再帰式が書けるのか」という骨格を理解する方が重要です。

11. 強化学習との接続

強化学習では、ベルマン方程式は価値推定や方策改善の出発点になります。

方策評価では $V^\pi$ の Bellman 方程式を使う
最適制御では $V^*$ の Bellman 最適方程式を使う
Q-learning では状態価値ではなく行動価値関数 $Q^*(s,a)$ の Bellman 方程式を使う

つまり強化学習は、ベルマン方程式そのものを発明したというより、遷移確率や報酬が未知でもサンプルからこの再帰構造を学習する方法を発展させた分野と見ると整理しやすいです。

まとめ

ベルマン方程式の導出で本質的なのは、全期間の最適化問題を

今期の報酬
次期以降の継続価値

に分解することです。

方策 $\pi$ を固定すれば

V^{\pi}(s) = r(s,\pi(s)) + \beta \mathbb{E}[V^\pi(s') \mid s,\pi(s)]

が成り立ち、さらに最適性原理を使うことで

V^*(s) = \max_{a \in \mathcal{A}(s)} \left\{ r(s,a)+\beta \mathbb{E}[V^*(s') \mid s,a] \right\}

が得られます。

この再帰式は、単なる書き換えではありません。
Bellman 作用素を通じて不動点問題になり、縮小写像の性質から一意性と反復計算の収束まで保証されます。

ベルマン方程式を「暗記する式」ではなく、「逐次問題を再帰化した結果」として理解すると、動的計画法、最適制御、強化学習の見通しがかなりよくなります。