{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TD(0) 与常数步长 MC 在 5 状态随机游走上的对比（Sutton & Barto 例 6.2）。\n",
    "\n",
    "\n",
    "\n",
    "配套教程：[时序差分（TD）学习](https://dqn.cn/basics/td-learning)（DQN.CN 强化学习中文教程）\n",
    "\n",
    "源码：`examples/basics/td_random_walk.py`，本 notebook 由 `scripts/build-notebooks.mjs` 自动生成，代码与 .py 文件一致。代码默认在 CPU 上运行，固定了随机种子；部分脚本支持设置环境变量 `DQN_QUICK=1` 只跑很短的版本（见下一个单元）。"
   ],
   "id": "basics-td_random_walk-py-0"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 环境准备：在 Colab 等缺少依赖的环境中自动安装（本地已装好依赖时什么也不做）\n",
    "import importlib.util, os, subprocess, sys\n",
    "sys.argv = sys.argv[:1]   # notebook 内核会带上 -f 等参数，清掉以免脚本把它们当成命令行参数\n",
    "# os.environ[\"DQN_QUICK\"] = \"1\"   # 取消注释：支持该开关的脚本只跑很短的版本，用于快速检查"
   ],
   "id": "basics-td_random_walk-py-1"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "N_STATES = 5                     # 非终止状态 A..E，编号 1..5；0 和 6 为终止状态\n",
    "TRUE_V = np.arange(1, 6) / 6.0   # 真实价值：1/6, 2/6, ..., 5/6"
   ],
   "id": "basics-td_random_walk-py-2"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_episode(rng):\n",
    "    s, traj = 3, []              # 从中间状态 C 出发\n",
    "    while True:\n",
    "        s2 = s + (1 if rng.random() < 0.5 else -1)\n",
    "        r = 1.0 if s2 == 6 else 0.0          # 只有从右端离开才得到奖励 1\n",
    "        traj.append((s, r, s2))\n",
    "        if s2 in (0, 6):\n",
    "            return traj\n",
    "        s = s2"
   ],
   "id": "basics-td_random_walk-py-3"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def td0(alpha, episodes, rng):\n",
    "    V = np.full(7, 0.5); V[0] = V[6] = 0.0\n",
    "    errs = []\n",
    "    for _ in range(episodes):\n",
    "        for s, r, s2 in run_episode(rng):\n",
    "            V[s] += alpha * (r + V[s2] - V[s])      # γ = 1\n",
    "        errs.append(np.sqrt(np.mean((V[1:6] - TRUE_V) ** 2)))\n",
    "    return np.array(errs)"
   ],
   "id": "basics-td_random_walk-py-4"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mc(alpha, episodes, rng):\n",
    "    V = np.full(7, 0.5); V[0] = V[6] = 0.0\n",
    "    errs = []\n",
    "    for _ in range(episodes):\n",
    "        traj = run_episode(rng)\n",
    "        G = traj[-1][1]                              # γ = 1，回报 = 最终奖励\n",
    "        for s, _, _ in traj:\n",
    "            V[s] += alpha * (G - V[s])\n",
    "        errs.append(np.sqrt(np.mean((V[1:6] - TRUE_V) ** 2)))\n",
    "    return np.array(errs)"
   ],
   "id": "basics-td_random_walk-py-5"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "runs, episodes = 100, 100\n",
    "for name, fn, alphas in [(\"TD(0)\", td0, [0.05, 0.1, 0.15]), (\"MC\", mc, [0.01, 0.02, 0.04])]:\n",
    "    for alpha in alphas:\n",
    "        err = np.mean([fn(alpha, episodes, np.random.default_rng(i)) for i in range(runs)], axis=0)\n",
    "        print(f\"{name:6s} α={alpha:<5} 第100回合 RMS 误差 = {err[-1]:.3f}\")"
   ],
   "id": "basics-td_random_walk-py-6"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "provenance": []
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}