ベルマン方程式とは？～導出と具体例～

ベルマン方程式は、強化学習や動的計画法で使われる数理モデルで、「最適な行動を選ぶための指針」を提供します。特に、長期的な報酬を最大化するために、各状態で取るべき最適な行動を求めるために利用されます。

ベルマン方程式とは？

ベルマン方程式は、ある状態における「価値関数」を、次の状態の価値関数と受け取る報酬を使って再帰的に表現したものです。

具体的には、各状態の価値は、
– 今すぐに得られる 即時報酬 と、
– 次の状態から得られる期待報酬 の割引された総和
で決まります。

この「現在の状態が未来の価値に依存する」という考え方を、動的計画法と呼びます。

ベルマン方程式の導出

ベルマン方程式は、MDP (マルコフ決定過程) を前提にしています。

状態価値関数 V(s)

状態 $s$ にいるときに、将来得られる総報酬の期待値を表します。

$$V(s) = \mathbb{E}\left[ \sum_{t=0}^{\infty} \gamma^t R_{t+1} \mid s_0 = s \right]$$

• $R_{t+1}$: 時刻 $t+1$ に得られる報酬
• $\gamma \in [0, 1]$: 割引率 (未来の報酬の価値をどれだけ減少させるか)
• $s_0 = s$: 現在の状態が $s$ であることを示します。

ベルマン方程式の導出の流れ

状態 $s$ にいるとき、最適な行動を取ることで最大の価値を得たいとします。ベルマン方程式では、次のように価値関数を再帰的に表現します：

1. 即時報酬 $R(s, a)$ を受け取る。
2. 次の状態 $s'$ に移行する。次の状態の価値は $V(s')$ です。
3. 次の状態の価値を、割引率 $\gamma$ をかけて考慮する。

これを数式で表すと：

$$V(s) = \max_a \mathbb{E}_{s'} \left[ R(s, a) + \gamma V(s') \right]$$

• $a$ : 取るべき行動
• $\mathbb{E}_{s'}$ : 次の状態 $s'$ への期待値を取る操作
• $\max_a$ : 最適な行動を選択することで得られる最大の価値

具体例：左右への遷移が確率 0.5 で起きる迷路

今回の例では、エージェントは各状態で左右のいずれかに確率 0.5 ずつで遷移するものとします。
エージェントの目的は、迷路のゴール (G) にたどり着き、できるだけ高い報酬を得ることです。
ただし、確率的な遷移のため、どの経路を進むかが完全に決まっているわけではありません。

迷路の構造

今回の迷路は以下のような1次元構造とします：

A1 → B1 → G

• A1 (スタート): 初期状態
• B1: 中間の状態
• G (ゴール): ゴールに到達すると報酬 $+10$
• 各状態では、左右のどちらかに確率 0.5で移動します。

遷移と報酬の定義

• A1 では「右」に進むと $B1$、「左」に戻ると変化なし。
• B1 では「右」に進むと $G$ に到達し、「左」に戻ると $A1$。

ベルマン方程式の定義（確率付き）

確率的な遷移がある場合、次の状態の価値は遷移確率を考慮した期待値として計算します。

例えば、状態 $s$ から行動 $a$ を取ったとき、次の状態 $s'$ に遷移する確率が $P(s' \mid s, a)$ である場合、ベルマン方程式は次のようになります：

$$V(s) = \sum_{s'} P(s' \mid s, a) \left[ R(s, a) + \gamma V(s') \right]$$

• $R(s, a)$：状態 $s$ から行動 $a$ を取ったときの即時報酬
• $\gamma$：割引率

具体例：1次元迷路の価値計算

割引率 $\gamma = 0.9$ として、次のように遷移を考えます：

• A1 から：
• 0.5 の確率で B1 へ移動

• 0.5 の確率でそのまま A1 に残る

• B1 から：

• 0.5 の確率で G へ移動（報酬 $+10$）
• 0.5 の確率で A1 に戻る（報酬 0）

Pythonコードでの実装

以下のコードは、確率的な遷移を考慮した迷路の価値をベルマン方程式に基づいて計算します。

# 状態と報酬の定義
states = ["A1", "B1", "G"]
rewards = {"A1": 0, "B1": 0, "G": 10}
gamma = 0.9  # 割引率

# 初期化：各状態の価値を0で開始
V = {s: 0 for s in states}

# ベルマン方程式による価値反復
for i in range(1000):  # 1000回反復
    V["G"] = rewards["G"]  # ゴールの価値は固定

    # B1 の価値計算：0.5 の確率で G、0.5 の確率で A1 に遷移
    V["B1"] = 0.5 * (rewards["B1"] + gamma * V["G"]) + \
              0.5 * (rewards["B1"] + gamma * V["A1"])

    # A1 の価値計算：0.5 の確率で B1、0.5 の確率で A1 に遷移
    V["A1"] = 0.5 * (rewards["A1"] + gamma * V["B1"]) + \
              0.5 * (rewards["A1"] + gamma * V["A1"])

# 結果の表示
for state, value in V.items():
    print(f"状態 {state}: 価値 = {value:.2f}")

価値計算の流れ

1. ゴール (G) の価値は 10 で固定です。
2. B1 では、0.5 の確率で $G$ に行き、0.5 の確率で $A1$ に戻るため：

$$V(B1) = 0.5 \times (0 + 0.9 \times 10) + 0.5 \times (0 + 0.9 \times V(A1))$$

3. A1 では、0.5 の確率で $B1$ に行き、0.5 の確率でそのまま $A1$ に留まるため：

$$V(A1) = 0.5 \times (0 + 0.9 \times V(B1)) + 0.5 \times (0 + 0.9 \times V(A1))$$

これを1000回の反復で解き、最適な価値が収束します。

連立方程式を解く

上記の例では繰り返しによって解を収束させましたが、連立方程式を解くことでもそれぞれの価値を求めることができます。

from sympy import symbols, Eq, solve

# 各状態の価値をシンボルとして定義
V_A1, V_B1 = symbols('V_A1 V_B1')

# 割引率
gamma = 0.9

# ゴールの価値は固定で10
V_G = 10

# 連立方程式を定義
eq1 = Eq(V_B1, 0.5 * (gamma * V_G) + 0.5 * (gamma * V_A1))
eq2 = Eq(V_A1, 0.5 * (gamma * V_B1) + 0.5 * (gamma * V_A1))

# 連立方程式を解く
solution = solve((eq1, eq2), (V_A1, V_B1))

# 結果の表示
print(f"V(A1) = {solution[V_A1]:.2f}")
print(f"V(B1) = {solution[V_B1]:.2f}")

実行すると
V(A1) = 5.83
V(B1) = 7.12
になります。

最適方策

各状態の価値がわかれば、その値を使うことで、各状態における行動の価値を数値化できるため、よりよい行動を知ることができます。
先ほどの迷路の例では、A1の時の
右への移動は：
$$0.5 \times (0 + 0.9 \times 7.12) = 3.204$$

左への移動は：
$$0.5 \times (0 + 0.9 \times 5.83) = 2.6235$$

となり、右に行く行動が最適行動になります。

まとめ

ベルマン方程式は、現在の状態と行動が未来の報酬に与える影響を定量的に捉える重要な数式です。この記事の迷路の例のように、未来の価値を再帰的に計算することで、エージェントは最適な行動方針を見つけることができます。

この考え方は、迷路探索だけでなく、ゲームAI、ロボット制御、さらには株式取引などの分野でも応用されています。