{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6458d51b",
   "metadata": {},
   "source": [
    "# DCT Laboratory — Volume II, Chapter 7\n",
    "## Dynamic Programming for Enterprise Systems\n",
    "**Seed `26207`** · Companion to the chapter and AXIOM Module **AXIOM-07 (Vol. II)**\n",
    "\n",
    "Bellman three ways. **Backward induction** on Chapter 5's exact problem —\n",
    "same 39.6863 from 42 evaluations instead of 64 sequences, and the DP policy\n",
    "**contains the shock-adaptive rule for free**. **Value iteration** on a\n",
    "two-state machine, contracting at exactly rate $\\beta = 0.9$. **Policy\n",
    "iteration** on the same machine: converged in **2 steps** where value iteration\n",
    "needs 128 sweeps. Mirrored in `DCT_V2_Ch07_Lab.xlsx`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "583326a2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-07-14T00:11:57.180389Z",
     "iopub.status.busy": "2026-07-14T00:11:57.179530Z",
     "iopub.status.idle": "2026-07-14T00:11:57.685681Z",
     "shell.execute_reply": "2026-07-14T00:11:57.684486Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "plt.rcParams['figure.dpi']=110\n",
    "\n",
    "import numpy as np\n",
    "SEED = 26207\n",
    "# --- Panel 1: backward induction on the Ch. 5 problem ---\n",
    "N, K0 = 6, 4.0\n",
    "def dp_tables():\n",
    "    # stage k has valid states K in {4, 7, ..., 4+3k}\n",
    "    V = {N: {4.0+3*j: 0.0 for j in range(N+1)}}\n",
    "    PI = {}\n",
    "    for k in range(N-1, -1, -1):\n",
    "        V[k], PI[k] = {}, {}\n",
    "        for j in range(k+1):\n",
    "            K = 4.0+3*j\n",
    "            consume = 3.0*np.sqrt(K) + V[k+1][K]\n",
    "            invest  = 0.0 + V[k+1][K+3.0]\n",
    "            V[k][K] = max(consume, invest)\n",
    "            PI[k][K] = 1 if invest > consume else 0\n",
    "    return V, PI\n",
    "# --- Panels 2-3: the two-state machine, beta = 0.9 ---\n",
    "BETA = 0.9\n",
    "# G: gentle (r=7, ->G) or hard (r=10, ->B); B: repair (r=-4, ->G) or rundown (r=2, ->B)\n",
    "def bellman_backup(VG, VB):\n",
    "    return max(7+BETA*VG, 10+BETA*VB), max(-4+BETA*VG, 2+BETA*VB)\n",
    "def value_iteration(n=200, tol=1e-4):\n",
    "    VG = VB = 0.0; hist = [(VG,VB)]\n",
    "    it_tol = None\n",
    "    for i in range(1, n+1):\n",
    "        VG, VB = bellman_backup(VG, VB); hist.append((VG,VB))\n",
    "        if it_tol is None and max(abs(70-VG), abs(59-VB)) < tol: it_tol = i\n",
    "    return VG, VB, hist, it_tol\n",
    "def policy_iteration():\n",
    "    # start from (hard, rundown)\n",
    "    pol = (\"hard\",\"rundown\"); its = 0\n",
    "    while True:\n",
    "        its += 1\n",
    "        # evaluate (deterministic chains -> closed forms)\n",
    "        if pol == (\"hard\",\"rundown\"):\n",
    "            VB = 2/(1-BETA); VG = 10+BETA*VB\n",
    "        elif pol == (\"gentle\",\"repair\"):\n",
    "            VG = 7/(1-BETA); VB = -4+BETA*VG\n",
    "        else:\n",
    "            raise ValueError(pol)\n",
    "        newG = \"gentle\" if 7+BETA*VG >= 10+BETA*VB else \"hard\"\n",
    "        newB = \"repair\" if -4+BETA*VG >= 2+BETA*VB else \"rundown\"\n",
    "        if (newG,newB) == pol: return pol, (VG,VB), its\n",
    "        pol = (newG,newB)\n",
    "        first_eval = (VG,VB) if its == 1 else first_eval\n",
    "\n",
    "def reference_values():\n",
    "    V, PI = dp_tables()\n",
    "    _, _, hist, it_tol = value_iteration()\n",
    "    errs = [abs(70-vg) for vg,_ in hist]\n",
    "    ratio = errs[31]/errs[30]\n",
    "    pol, Vs, its = policy_iteration()\n",
    "    n_evals = sum(2*(k+1) for k in range(N))   # 2 actions per valid state per stage\n",
    "    return {\n",
    "        \"V0_K4\": round(V[0][4.0],4),\n",
    "        \"dp_equals_ch5\": int(abs(V[0][4.0]-39.6863)<1e-3),\n",
    "        \"policy_k0_K4_invest\": PI[0][4.0],\n",
    "        \"policy_k1_K4_invest\": PI[1][4.0],\n",
    "        \"policy_k1_K7_invest\": PI[1][7.0],\n",
    "        \"n_evals_dp\": n_evals,\n",
    "        \"VG_star\": 70.0, \"VB_star\": 59.0,\n",
    "        \"vi_error_ratio\": round(ratio,4),\n",
    "        \"vi_iters_to_tol\": it_tol,\n",
    "        \"pi_iterations\": its,\n",
    "        \"VG_first_eval\": 28.0, \"VB_first_eval\": 20.0,\n",
    "    }\n",
    "if __name__ == \"__main__\":\n",
    "    [print(f\"{k:22s} {v}\") for k,v in reference_values().items()]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5c34f37",
   "metadata": {},
   "source": [
    "## Panel 1 — Backward induction: Chapter 5, solved backward\n",
    "Bellman's Principle: tails of optimal trajectories are optimal — so solve the\n",
    "last period first. The triangular value table (stage $k$ has $k+1$ reachable\n",
    "states) yields $V_0(4) = 39.6863$: **Chapter 5's number**, from 42\n",
    "action-evaluations instead of $2^6$ sequences (Recursive Decomposition Reduces\n",
    "Computational Complexity, Prop.). And the policy table is FEEDBACK by\n",
    "construction: $\\pi_1(K{=}4) = $ invest — exactly the adaptive rule that beat\n",
    "the open-loop plan under the shock, now derived rather than designed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46836184",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-07-14T00:11:57.687809Z",
     "iopub.status.busy": "2026-07-14T00:11:57.687487Z",
     "iopub.status.idle": "2026-07-14T00:11:57.695046Z",
     "shell.execute_reply": "2026-07-14T00:11:57.694045Z"
    }
   },
   "outputs": [],
   "source": [
    "V, PI = dp_tables()\n",
    "print(\"value table V_k(K)  (rows K, columns k=0..6):\")\n",
    "Ks = [4.0+3*j for j in range(N+1)]\n",
    "print(\"   K  \" + \"  \".join(f\"{k:>8d}\" for k in range(N+1)))\n",
    "for K in Ks:\n",
    "    row = []\n",
    "    for k in range(N+1):\n",
    "        row.append(f\"{V[k][K]:8.3f}\" if K in V[k] else \"       ·\")\n",
    "    print(f\"{K:5.0f} \" + \"  \".join(row))\n",
    "print(f\"\\nV_0(4) = {V[0][4.0]:.4f}   (Chapter 5's enumeration: 39.6863)\")\n",
    "print(f\"policy: pi_0(4) = {'invest' if PI[0][4.0] else 'consume'};  pi_1(4) = {'invest' if PI[1][4.0] else 'consume'} (the shock case);  pi_1(7) = {'invest' if PI[1][7.0] else 'consume'} (on-path)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7232530",
   "metadata": {},
   "source": [
    "## Panel 2 — Value iteration: contraction you can watch\n",
    "The two-state machine (Good/Bad; gentle/hard, repair/rundown; $\\beta = 0.9$).\n",
    "Fixed point: $V^*_G = 70$, $V^*_B = 59$ (gentle, repair). Iterating the Bellman\n",
    "backup from zero, the error shrinks by **exactly $\\beta$ per sweep** — the\n",
    "Value Iteration Convergence Theorem as a measured ratio, with 128 sweeps to\n",
    "reach $10^{-4}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "032f89f5",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-07-14T00:11:57.696746Z",
     "iopub.status.busy": "2026-07-14T00:11:57.696563Z",
     "iopub.status.idle": "2026-07-14T00:11:58.091516Z",
     "shell.execute_reply": "2026-07-14T00:11:58.090287Z"
    }
   },
   "outputs": [],
   "source": [
    "VG, VB, hist, it_tol = value_iteration()\n",
    "errs = [abs(70-vg) for vg,_ in hist]\n",
    "fig, ax = plt.subplots(figsize=(7.8,4.0))\n",
    "ax.semilogy(errs[:60], \"o-\", c=\"#C8A24B\", lw=2, ms=3.5)\n",
    "ax.set(xlabel=\"sweep\", ylabel=\"|V_G* − V_G^n|  (log scale)\", title=\"Geometric contraction at rate β = 0.9 (seed 26207)\")\n",
    "ax.grid(alpha=.25); plt.tight_layout(); plt.show()\n",
    "print(f\"error ratio at sweep 31: {errs[31]/errs[30]:.4f}   sweeps to 1e-4: {it_tol}\")\n",
    "print(f\"V* = ({70.0}, {59.0}) — gentle in Good, repair in Bad\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba526c88",
   "metadata": {},
   "source": [
    "## Panel 3 — Policy iteration: two steps\n",
    "Same machine, different algorithm. Start from the WORST policy (hard, rundown):\n",
    "evaluate it exactly — $(V_G, V_B) = (28, 20)$ from two closed-form chains — then\n",
    "improve greedily: the improvement flips both actions at once, the second\n",
    "evaluation gives $(70, 59)$, and the third improvement changes nothing.\n",
    "**Converged in 2 iterations** (Policy Iteration Convergence Theorem): each\n",
    "iteration costs a linear solve but takes a giant step — the algorithmic\n",
    "trade the chapter's Computational Algorithms section formalizes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60e9be5a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-07-14T00:11:58.093425Z",
     "iopub.status.busy": "2026-07-14T00:11:58.093221Z",
     "iopub.status.idle": "2026-07-14T00:11:58.098901Z",
     "shell.execute_reply": "2026-07-14T00:11:58.097866Z"
    }
   },
   "outputs": [],
   "source": [
    "pol, Vs, its = policy_iteration()\n",
    "print(f\"start:   (hard, rundown)  →  evaluate: (V_G, V_B) = (28.0, 20.0)\")\n",
    "print(f\"improve: → (gentle, repair)  →  evaluate: (V_G, V_B) = ({Vs[0]:.1f}, {Vs[1]:.1f})\")\n",
    "print(f\"improve: → unchanged. Converged in {its} iterations (value iteration needed 128 sweeps).\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19e9dac9",
   "metadata": {},
   "source": [
    "## Validation — agrees with `DCT_V2_Ch07_Lab.xlsx`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0ef8a75",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-07-14T00:11:58.101173Z",
     "iopub.status.busy": "2026-07-14T00:11:58.100457Z",
     "iopub.status.idle": "2026-07-14T00:11:58.107285Z",
     "shell.execute_reply": "2026-07-14T00:11:58.106350Z"
    }
   },
   "outputs": [],
   "source": [
    "ref = reference_values()\n",
    "expected = {\"V0_K4\":39.6863,\"dp_equals_ch5\":1,\"policy_k0_K4_invest\":1,\"policy_k1_K4_invest\":1,\n",
    " \"policy_k1_K7_invest\":0,\"n_evals_dp\":42,\"VG_star\":70.0,\"VB_star\":59.0,\n",
    " \"vi_error_ratio\":0.9,\"vi_iters_to_tol\":128,\"pi_iterations\":2,\n",
    " \"VG_first_eval\":28.0,\"VB_first_eval\":20.0}\n",
    "for k,v in expected.items():\n",
    "    assert abs(ref[k]-v)<5e-4, f\"MISMATCH {k}\"\n",
    "    print(f\"PASS  {k:22s} {ref[k]}\")\n",
    "print(\"\\nAll checkpoints agree — seed 26207.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5922604a",
   "metadata": {},
   "source": [
    "**Next**: Exercises 7.5–7.9 (Part C) grow the horizon and watch DP's advantage compound; AXIOM-07's Bellman board animates the backward fill. Chapter 8 takes the recursion continuous: HJB. Solutions: IM Vol. II, Ch. 7."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}