逐次意思決定と動的計画

🎓 レベル：発展　|　重要度：B（推奨）

📎 前提：二項モデルによる評価・決定木と後ろ向き帰納　|　関連：機械学習（マルコフ決定過程）・数理最適化（動的計画）

要点（BLUF）

逐次意思決定は、状態が時間とともに変化する中で何度も決定を下す問題。動的計画（dynamic programming） で、各状態の価値関数を満期から後ろ向きに解いて最適化します。
中心はベルマン方程式： $V(s) = \max_a \big\{\,\text{即時報酬} + \mathbb{E}[\,V(\text{次状態})\,]\,\big\}$ 。「今の最適は、即時報酬＋将来の最適価値の和を最大化」。
決定木の後ろ向き帰納（決定木と後ろ向き帰納）と二項モデル（二項モデルによる評価）を、一般の状態・行動へ拡張したもの。最適停止（いつ受諾するか）が代表例です。

1. ベルマン方程式：未来から現在へ

逐次意思決定の最適化は、「最適な方策の部分も最適である」（最適性の原理, Bellman）という性質に立脚します。これを式にしたのがベルマン方程式。状態 $s$ の価値 $V(s)$ を、

V(s) = \max_{a}\Big\{\, r(s,a) + \sum_{s'} P(s'\mid s,a)\,V(s')\,\Big\}

と定めます。 $r(s,a)$ は即時報酬、 $\sum P V$ は次状態の価値の期待値。「今の行動の良さ＝即時の得＋その結果たどり着く未来の価値」 を最大化します。 $\max_a$ （決定）と $\mathbb{E}_{s'}$ （自然）が交互に現れる構造は、決定木と後ろ向き帰納の決定ノードと偶然ノードそのもの。決定木が「特定の木」なら、ベルマン方程式は「状態空間上の漸化式」です。求解は満期から後ろ向き（後ろ向き帰納＝価値反復）に進めます。

2. 最適停止問題：いつ受諾するか

具体例として最適停止を解きます。家を売るとき、毎期オファーが $\{100,150,200,250,300\}$ から等確率で1つ届く。受諾すればそのオファーで売却、拒否すれば次期へ（全4期、最終期は必ず受諾）。問いは「いくら以上なら受諾すべきか（留保価格）」。

状態は「現在のオファー」、行動は「受諾／継続」。継続の価値 $V_{t+1}$ （次期以降の最適価値）が分かれば、オファー $x$ に対し $\max(x, V_{t+1})$ を取ればよい。後ろ向きに $V_t = \mathbb{E}[\max(x, V_{t+1})]$ を解きます。

import numpy as np

offers = np.array([100, 150, 200, 250, 300])
T = 4
V_next = offers.mean()           # 最終期：必ず受諾 -> 期待オファー
print(f"第{T}期（最終・必ず受諾）: 継続価値 V = {V_next:.2f}（留保価格なし）")

for t in range(T-1, 0, -1):
    V_t = np.mean(np.maximum(offers, V_next))     # ベルマン更新
    reservation = V_next                          # x >= V_next なら受諾
    accept = [int(x) for x in offers[offers >= reservation]]
    print(f"第{t}期: 継続価値 V = {V_t:.2f}  留保価格 = {reservation:.2f}  受諾 >= {reservation:.0f} {accept}")
    V_next = V_t

出力：

第4期（最終・必ず受諾）: 継続価値 V = 200.00（留保価格なし）
第3期: 継続価値 V = 230.00  留保価格 = 200.00  受諾 >= 200 [200, 250, 300]
第2期: 継続価値 V = 248.00  留保価格 = 230.00  受諾 >= 230 [250, 300]
第1期: 継続価値 V = 258.80  留保価格 = 248.00  受諾 >= 248 [250, 300]

出力の意味：留保価格は、残り期数が多い序盤ほど高くなります。第1期は248以上（実質250か300）でないと受諾せず、待ちます。第3期になると残りが少ないので200以上で受諾、と基準が下がる。「まだ時間があるうちは強気、終わりが近いと妥協」という、誰もが経験する売り時の感覚が、ベルマン方程式から自動的に出てきます。継続価値 $V$ （258.8 → 248 → 230 → 200）が、各期の「待つことの価値」＝留保価格そのもの。後ろ向き帰納が、最適な意思決定ルール（方策）を期ごとに与えています。

3. 動的計画とリアルオプション・他分野の繋がり

この最適停止は、実はリアルオプションそのものです。「いつ受諾するか」＝「いつオプションを行使するか」。二項モデルによる評価の各ノードでの「今投資 vs 待つ」の比較を、一般の状態・期間に広げたのが動的計画。延期オプションの価値＝継続価値で、行使境界＝留保価格です。

動的計画は意思決定分析を越えて広く使われます。

機械学習（強化学習）：マルコフ決定過程（MDP）の価値関数・方策をベルマン方程式で学習。確率 $P$ や報酬 $r$ が未知なら、データから推定しつつ解く（Q学習など）。
数理最適化：在庫管理・設備更新・最短経路など、多段階最適化の標準手法。
オペレーションズ：逐次的な資源配分・スケジューリング。

意思決定分析の決定木が、これら全分野に通じる動的計画の「最も具体的な入口」だったわけです。MDP の一般論や強化学習のアルゴリズムは機械学習のturf、大規模最適化の手法は数理最適化へ繋ぎ、ここでは「逐次決定をベルマンで後ろ向きに解く」という意思決定の核を押さえます。

数式の直観的意味：なぜ後ろ向きに解けるのか

ベルマン方程式が後ろ向きに解ける鍵は、最適性の原理——「最適方策の途中から先も、その時点からの最適方策になっている」——です。だから未来（満期）の最適価値 $V_{t+1}$ さえ確定すれば、現在の最適行動は $\max_a\{r + \mathbb{E}[V_{t+1}]\}$ で局所的に決まり、過去を振り返る必要がありません。これは「未来の最適が現在の最適を支える」という時間構造で、決定木と後ろ向き帰納で「先の最適行動が決まらないと手前を評価できない」と述べたのと同じこと。逐次決定の複雑さ（行動の系列は指数的に多い）を、状態ごとの価値関数という多項式サイズの表に圧縮できる——これが動的計画の威力で、「系列を全探索せず、状態の価値だけ覚えればよい」という計算の節約です。ただし状態が高次元だと価値関数の表が爆発する（次元の呪い）ため、近似（関数近似・強化学習）が要り、そこが機械学習に繋がります。

⚠️ よくある誤解

「前向きに貪欲に解けばよい」ではない：各期で目先の最良を取る貪欲法は、将来の価値を織り込めず最適になりません。必ず後ろ向きに価値関数を解きます。
「留保価格は一定」ではない：残り期数（状態）によって留保価格は変わります。終わりが近いほど妥協する、という時間依存が本質です。
「動的計画はリアルオプションと別物」ではない：オプションの逐次行使は動的計画の一例。二項モデルの後ろ向き帰納はベルマン方程式の離散版です。
「状態をいくらでも増やせる」ではない：状態空間が大きいと価値関数が爆発します（次元の呪い）。厳密に解けるのは小規模か構造のある問題で、大規模は近似が必要です。

対応シミュレーション

本文のコードで、期数 $T$ やオファー分布を変えると留保価格の推移が変わります。終盤ほど留保価格が下がる（妥協する）構造や、期数を増やすと序盤の留保価格が上がる様子を観察できます。