動的計画法：自動機から最適制御へ

もし私が、グラフ上の最短経路を見つけるためのアルゴリズムや、ニューラルネットワークの勾配計算技術、文脈自由文法の解析手法が、本質的には全く同じ原理に基づいた実装に過ぎないという事実をお伝えするとどうでしょうか？その原理こそが「動的計画法（Dynamic Programming）」であり、数学におけるシンプルなお見得の一つで、多くの分野にわたる深遠な結論へと展開されるのです。

リチャード・ベルマン氏（創始者）ご自身の言葉です：

「最適な政策は、初期状態と初期決定がどのようなものであれ、その後の決定は、最初の決定によって得られた状態に対して常に最適な政策を構成する必要がある。」

動的計画法の実装には多様な顔があります。

• メモ化（Memoization）：単純な部分問題から解き進め、解答を保存することで高速化する技術。
• 確率双動的計画法：線形計画問題を解決する大規模スケジューリング問題への応用。
• モデルベース強化学習：マルコフ決定プロセスの主要手法。

これらに共通するのは、ロケット軌道計画から TeX の改行まで適用される普遍的な原理です。

私たちは、数学の様々な領域へ旅立ちます。

• 自動機 $\rightarrow$ 最適制御
• マルコフ連鎖、動的システム、線形計画、距離空間

ご乗車ください！

---

1. 意思決定と状態機械について

状態機械（自動機）のモデル化

「レトロ風プラットフォームゲーム」を例にとりましょう。キャラクターの状態は「Idle（待機）」から「アクション中」まで変化します。これを抽象化すると、状態機械（State Machine）、あるいは「自動機」と呼ばれます。

• 状態: システムが存在しうる状態 $s \in \mathcal{S}$
• 行動: 各状態ごとに利用可能な行動セット $\mathcal{A}(s)$ から選択可能
• 遷移関数 ($T$): 行動を実行するとシステムは新しい状態に変化する $$T : (s \in \mathcal{S}) \times \mathcal{A}(s) \to \mathcal{S}$$

コストとダイナミクス

人生（そしてシステム）にはコストがかかります。これを関数 $c$ でモデル化します： $$c : (s \in \mathcal{S}) \times \mathcal{A}(s) \to \mathbb{R}$$

• 経済文脈: 金銭的なコスト
• 計画問題: 総距離や経過時間
• 報酬: 負のコストとして扱われる

制御可能な動的システム

遷移 $T$ を反復させることで、初期状態 $s_0$ から行動のシーケンス ${a_t}$ を実行し、軌跡を生成します。 $$s_{t+1} = T(s_t, a_t)$$

これにより、「制御可能な動的システム」または「意思決定プロセス」として定義されます。

• 政策（Policy）$\pi$: 各状態に対して有効な行動を選択する関数 $$\pi : (s \in \mathcal{S}) \to \mathcal{A}(s)$$
• 決定論的ダイナミクス: 政策を追従すると、確率的要素を取り除いて軌跡が生成される $$s_{t+1} = T(s_t, \pi(s_t))$$

価値関数 $v^\pi$

状態 $s_0$ から始めて政策 $\pi$ を追従する際のコストを合計（割引済み）します。 $$ \begin{aligned} v^\pi(s) = & c(s_0, \pi(s_0)) + \gamma c(s_1, \pi(s_1)) + \gamma^2 c(s_2, \pi(s_2)) + \ldots \ \text{where} & s_{t+1} = T(s_t, \pi(s_t)), \end{aligned} $$

ここで、$\gamma \in [0, 1]$ は割引因子です。将来のコストは実質価値が異なるため（インフレや金利など）、現在の価値に対する重みが減衰します。

収束の保証: コストが一様有界（$|c(s, a)| \le M$）であり $|\gamma| < 1$ の場合、この級数は幾何級数として制限され、発散しません。 $$\sum_{t=0}^\infty \gamma^{t}|c(s_t, a_t)| \le \frac{M}{1 - \gamma}$$

---

2. 最適意思決定

複数の行動コースが存在する中、**総コストが最小となる政策 $\pi$**を見つけることが目標です。

• ロボット：最短経路（時間最小化）
• 宇宙船：最少燃料消費
• バウト：最少負傷で敵を失神させる

数学的に記述すると、以下の最適化問題となります： $$ \begin{aligned} \min_{\pi} v^\pi(s) = \min_{a_t} & \sum_{t=0}^\infty \gamma^{t}c(s_t, a_t) \ \text{s.t.} & s_0 = s, \ & s_{t+1} = T(s_t, a_t), \ & a_t \in \mathcal{A}(s_t). \end{aligned} $$

このように見えても、問題は構造を持っています。ここで**ベルマンの最適性原理（Principle of Optimality）**が鍵となります：

「最適な政策は、初期状態と初期決定がどのようなものであれ、残りの決定は最初の決定によって得られた状態に対して常に最適な政策を構成する性質を持っている。」

これは問題を二つに分解することを意味します：

1. 即時コスト: 現在の行動によるコスト $c(s, a)$
2. 将来のコスト: 遷移した状態 $s'$ から始まる後の最適価値 $\gamma v^\star(s')$

この帰納的な関係式こそが、**ベルマン方程式（Bellman Equation）**です。 $$ \boxed{ \begin{array}{rl} v^\star(s) = \min_{a} & c(s, a) + \gamma v^\star(s') \ \text{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array} } $$

---

3. 存在性、一意性と不動点

ベルマン方程式 $v^\star = \mathcal{B}v^\star$ を解くことは、ベルマン演算子（Bellman Operator） $\mathcal{B}$ の**不動点（Fixed Point）**を見つける問題です。

ベルマン演算子の定義

$$ \begin{aligned} (\mathcal{B}v)(s) = \min_{a} & c(s, a) + \gamma v(s') \ \text{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{aligned} $$

ベルマン演算子は縮小写像であること

割引因子 $\gamma < 1$ の場合、$\mathcal{B}$ は距離を縮める**縮小写像（Contraction Mapping）となります。ここでバナッハの不動点定理（Banach Fixed Point Theorem）**が適用されます：

• 性質: 完全距離空間上の縮小写像は、一意の不動点を持ちます。
• アルゴリズム的意味: どんな初期値 $v_0$ から始めても、反復 $v_{n+1} = \mathcal{B}v_n$ を行うことで必ず不動点（最適価値）に収束します。

function fixed_point(f; v0, tol)
  v = f(v0)
  while distance(v, v0) > tol
    v0 = v
    v  = f(v)  # Update rule
  end
  return v
end

---

4. ベルマン方程式を解く（動的計画法のアルゴリズム）

動的計画法とは、ベルマン演算子を反復して不動点を見つける手法です。実装における主要な決定は、価値関数の表現形式（配列やハッシュマップなど）と、計算順序です。

4.1 値反復（Value Iteration）

任意の初期値 $v_0$ から始めて、ベルマン演算子を反復適用する最も単純なアプローチです。

function bellman_operator(prob :: Process)
  return function(v)
    Bv = Values{States}()
    for s in States
      # 全行動中で最小コストを選定（Min-step）
      Bv[s] = minimum(a -> total_cost(prob)(v, s, a), Actions(s))
    end
    return Bv
  end
end

function value_iteration(prob :: Process; v0, tol)
  # 固定点定理による収束保証
  v_opt  = fixed_point(bellman_operator(prob); v0, tol)
  
  # 最終的な最適政策の抽出
  π_opt  = argmin_policy(v_opt) 
  return π_opt, v_opt
end

4.2 インプレース値反復（In-Place Value Iteration）

逐次計算機向けに、全状態を巡回してから更新するのではなく、即座に新しい情報を反映させる方式です。

• メリット: メモリ使用量の削減、高速化（並列化と両立し得る調整あり）。
• 注意点: 情報伝播の順序が結果に影響し得るため、適切な順序処理が必要になる場合があります。

function fixed_point_inplace!(f, v; tol)
  maxerr = Inf
  while maxerr > tol
    maxerr = 0
    for s in States
      prev = v[s]
      # 同期更新なしでの即時計算
      v[s] = f(v)[s] 
      maxerr = max(maxerr, abs(v[s] - prev))
    end
  end
  return v
end

4.3 政策反復（Policy Iteration）

値反復とは異なり、評価と改善を交互に行うアルゴリズムです。より少ない反復数で収束する傾向があります。

1. 政策評価: 与えられた政策 $\pi$ に対する価値関数 $v^\pi$ を計算（固定点問題）。
2. 政策改善: 現在の価値関数に基づき、より良い行動 $\arg\min (\dots)$ を選択して新しい政策を作成。

function policy_iteration(prob :: Process)
  # 1. 初期政策
  π0 = rand(Policy) 
  
  while true
    # 2. 評価: 現在の政策に従った価値関数を計算
    v = policy_evaluation(prob, π0)
    
    # 3. 改善: より良い行動を選択
    π_new = argmin_policy(v)
    
    if π_new == π0 break end
    π0 = π_new
  end
  return π0, v
end

4.4 後方帰納法（Backward Induction）

有限スパン問題において特化した高速アルゴリズムです。

• 前提: 状態図は「非巡回的（DAG）」であり、終端状態が存在する。
• 戦略: 状態をトポロジカル順序でソートし、終端状態から初期状態へ逆順に計算を行う。
• 特徴: 単一のパス（反復）で厳密に最適解へ収束。割引因子 $\gamma$ を使わない場合でも機能する。

function backward_induction(p :: Process)
  # 終端状態から初期状態への順路探索（トポロジカルソート）
  for s in topological_sort(States, Actions) 
    # ローカル最小化と即時更新
    v[s], π[s] = minimize(a -> total_cost(p)(v, s, a), Actions(s))
  end
  return π, v
end

4.5 後方帰納法（時間ステージ順）

さらに構造化された問題（例：時間の経過とともに状態が変化し、各ステップに明確な境界がある場合）では、時刻 $t$ を降順で処理することで並列性を最大化できます。

function backward_induction_in_time(p :: Process)
  for t in N:1           # N から 0 へ逆順
    # ステージ内の全状態は同時更新可能（並列化）
    for s in States(t)  
      v[s], π[s] = minimize(a -> total_cost(p)(v, s, a), Actions(s))
    end
  end
  return π, v
end

---

5. 非決定性：すべてを知ることはできない

これまで扱ってきたのは「完全情報」の状況でしたが、現実には不確実性や他者の行動が存在します。これをモデル化するために、遷移関数 $T$ を一般化し、値関数 $\rho$ に集約関数を導入します。

非決定論的遷移の型

• 集合: パワerset $\mathcal{P}$（全ての可能な次状態）
• 確率分布: 各状態が持つ確率
• 他プレイヤー: ゲーム理論における対手行動
• 関数: $M \mathcal{S} \to \mathbb{R}$ のような集約関数

これらに対処するため、ベルマン方程式は以下の拡張形を持ちます： $$ \begin{aligned} v^\star(s) = \min_{a} & c(s, a) + \gamma \rho(v, s') \ \text{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{aligned} $$

重要なのは、既存のアルゴリズム（値反復、政策反復、後方帰納法）はこの拡張形にそのまま適用できるという点です。コスト関数さえ決定論的であれば、内部の不確実性や他者の戦略も同様の枠組みで扱えます。

例：フィボナッチ数列

再帰関係 $f(n)$ は、非決定論的意思決定プロセスの一例としてモデル化できます。

• 状態: 数字 $0, \dots, N$
• 行動: ダミー $\blacklozenge$ のみ
• 遷移: 再帰的に参照される以前の数々（不確定性を持つ集合）
• コスト: 基礎ケースのコストのみ

これにより、フィボナッチ数列を計算するアルゴリズムも動的計画法の特殊なケースであることがわかります。

---

6. 確率動的計画法（PDP）と MDP

現実世界の多くの問題（ゲーム、ロボット制御など）は確率的です。これを記述するのが**マルコフ決定プロセス（MDP）**です。

マルコフ性

現在の状態と行動だけで未来が決定され、過去の履歴とは独立しています。

• アクター: 行動 $a$ を選択
• 環境: 確率で遷移 $s \to s'$ を起こし、コスト $c$ を課す
• 集約関数 $\rho$: 期待値（Expectation）を取ることで不確実性を平均化する $$\rho(v, S) = \mathbb{E}[v(S)]$$

これにより、ベルマン方程式は以下の形になります： $$ \begin{aligned} v^\star(s) = \min_{a} & c(s, a) + \gamma \mathbb{E}\left[v^\star(s') \right] \ \text{s.t.} & s' = T(s, a). \end{aligned} $$

有限状態空間において、この方程式は決定論的な場合と同じように収束します。強化学習（Reinforcement Learning）の基礎をなすものです。

---

7. 私たちの旅の終わり

動的計画法は、**「最適性の原理」**という単純で強力な数学的性質から派生する、驚くほど多様な技術群の核となっています：

• グラフアルゴリズム（最短経路）
• 再帰計算の加速（メモ化）
• 強化学習における制御問題解決
• 経済学やオペレーションズ・リサーチ

価値関数の推定、無限状態空間、連続時間など、未踏の領域がまだ残っていますが、**「現在の状況で最適な判断が、将来的な最適性を保証する」**というこの原理さえ理解できれば、多くの複雑な問題を分解して解決するための強力な武器を手に入れることになります。

さようなら、次回会いましょう！

---

謝辞

• ペドロ・シャヴィアー氏: 有益な会話と議論の提供。
• Ivani Ivanova: 誤字脱字の修正に尽力してくれたことへのお礼。

付録：無限スパンでの収束（概要）

割引因子 $\gamma < 1$ の場合、ベルマン演算子 $\mathcal{B}$ はLipschitz 連続であり、距離空間上の縮小写像となります。 $$|\mathcal{B}v - \mathcal{B}w|\infty \le \gamma |v - w|\infty$$ これによりバナッハの不動点定理が保証され、一意の最適価値関数 $v^\star$ が存在することが証明されます。