Lecture 1: 强化学习导论 —— 不确定下做序列决策（Introduction to RL）

目录 · ← l0 · l2 →

Lecture 1: 强化学习导论 —— 不确定下做序列决策（Introduction to RL）

对应材料：官方 lecture1pre.pdf（68 页）/ lecture1post.pdf（60 页，含课上板书与答案）｜Week 1 周一（Jan 5, 2026）｜参考阅读：Sutton & Barto (2018, 2nd ed.) Chp 1、David Silver Introduction to RL 导论幻灯片（本讲第 3 部分采用/改写）、CS229 线性代数/概率复习、NumPy 教程 一句话定位：本讲是整门课的地基——它给出 RL 的定义、四个一般性要素（优化 / 延迟后果 / 探索 / 泛化）、与监督学习的本质差别、以及从 “agent 与世界的交互循环” 一路推到 Markov 决策过程与 Bellman 方程的完整线索，之后 L2–L16 全部是这条线索上逐级放宽假设的结果。

1.1 概述

本讲回答三个问题：RL 是什么、它和已经学过的机器学习范式有什么本质不同、为什么它值得一整门课。定义只有一句话：Learning through experience/data to make good decisions under uncertainty（通过经验或数据学习，在不确定下做出好决策）；Brunskill 把它拆成四个一般性要素——优化（optimization）、延迟后果（delayed consequences）、探索（exploration）、泛化（generalization），并强调四者的组合才是 RL 的难点，任何一个单独拿出来都是已解决的经典问题。

本讲的方法论贡献是把 “决策” 写成一个可计算的数学对象：先承认历史 $h_t$ 是 agent 真正拥有的东西，再引入 Markov 假设把历史压缩成状态 $s_t$，于是 “做决策” 变成在 Markov 决策过程（Markov Decision Process, MDP） $(\mathcal{S},\mathcal{A},P,R,\gamma)$ 上最大化期望折扣回报。本讲只给出直觉版形式化（Mars Rover 的 7 状态链、折扣因子 $\gamma$ 的语义、$V^\pi$ 的定义、MRP 的 Bellman 方程与解析解 $V=(I-\gamma P)^{-1}R$），严格版定义与规划算法留给 L2。

本讲在知识链中的位置：它是唯一一讲 “不含算法” 的讲次，作用是把后续所有算法共同的坐标系立起来——L2 补上模型与规划，L3 抽掉模型做评估，L4 抽掉模型做控制，L5–L8 换成参数化策略，L9–L12 把探索做成理论，L13–L16 处理巨大状态空间与对齐问题。

1.2 核心概念的数学形式化

本节按 “严格定义 → 直观解释 → 具体示例 → 与监督学习对比” 四件套展开。记号遵循 SPEC §4；首次出现的符号用粗体。

1.2.1 RL 的定义与四个一般性要素

严格定义。给定一个 agent 与环境交互产生的数据流（可以是它自己在环境中产生的轨迹，也可以是别人产生的离线数据），RL 的目标是学到一个策略（policy） $\pi:\mathcal{S}\to\mathcal{A}$（或 $\pi(a\vert s)$），使期望折扣回报最大：

其中 $\tau=(s_0,a_0,r_0,s_1,a_1,r_1,\dots)$ 是轨迹（trajectory），$H$ 是视界（horizon），$\gamma\in[0,1]$ 是折扣因子（discount factor）。

四个要素的严格化表述（讲义第 13 页逐条列出，这里逐条严格化）：

为什么必须四个一起出现：只有优化 → 那是运筹学/规划（L2）；只有延迟后果 → 那是最优控制；只有探索 → 那是 L9/L10 的 bandit；只有泛化 → 那是监督学习。RL 的困难在于四者同时存在且相互纠缠：探索产生的数据分布又依赖当前策略，而策略又依赖泛化能力。

1.2.2 序列决策的要素

严格定义。离散时间下，每个时刻 $t$：

1. agent 依据历史选择动作 $a_t\sim\pi(\cdot\vert h_t)$；
2. 世界依据动作更新，产生观测 $o_{t+1}$ 与标量奖励 $r_t$；
3. agent 收到 $o_{t+1},r_t$，得到新历史。

历史（history）是过去观测、动作、奖励的序列：

状态（state）是对历史的一个函数 $s_t=f(h_t)$，它被假设为 “决定下一步会发生什么” 的信息。Markov 假设要求状态是历史的充分统计量（sufficient statistic）：

直观解释：$h_t$ 会无限增长，直接当输入不可行；$s_t$ 是 “$h_t$ 的压缩包”，压缩得足够好时，预测未来只需要 $s_t$。实践中最常用的近似是 $s_t=o_t$（最近一次观测就是充分统计量）。

具体示例：Mars Rover（讲义第 39–43 页）。7 个状态 $s_1,\dots,s_7$ 表示火星车位置，动作 $\mathcal{A}=\{\text{TryLeft},\text{TryRight}\}$，奖励在 $s_1$ 为 $+1$、在 $s_7$ 为 $+10$、其余为 $0$。策略 $\pi(s_1)=\pi(s_2)=\cdots=\pi(s_7)=\text{TryRight}$ 是一个确定性策略（deterministic policy）——注意它把每个状态映射到唯一动作，因此尽管写成了 “$s_i\mapsto$ TryRight” 的长串，仍然是确定性的（讲义第 43 页的 Quick Check 正考这一点）。与之相对，随机策略（stochastic policy）写成 $\pi(a\vert s)=\Pr(a_t=a\mid s_t=s)$。

状态表示的代价（讲义第 37 页明确强调）：状态表示直接决定三件事——计算复杂度、所需数据量、最终性能。这是本讲最容易被忽视的工程结论：把一个 POMDP 塞进 MDP 时，你选择的 $s_t$ 就是你的算法上限。

1.2.3 MDP 的初步形式化（五元组预告）

严格定义。Markov 决策过程（MDP）是一个五元组 $(\mathcal{S},\mathcal{A},P,R,\gamma)$：

• $\mathcal{S}$：状态空间，$S=\vert \mathcal{S}\vert $；$\mathcal{A}$：动作空间，$A=\vert \mathcal{A}\vert $；
• $P(s^{\prime}\mid s,a)$：转移/动力学模型，预测下一状态；
• $R(s,a)=\mathbb{E}[r_t\mid s_t=s,a_t=a]$：奖励模型，预测期望即时奖励；
• $\gamma\in[0,1]$：折扣因子。

本讲只给出直觉版：讲义第 38 页用三个问题给序列决策过程分类——(i) 状态是否 Markov、世界是否部分可观测（POMDP）；(ii) 动力学是确定还是随机；(iii) 动作只影响即时奖励（老虎机, bandit）还是同时影响奖励与下一状态（完整 RL）。第三问正是 L9–L12 与 L2–L8 的分界线。

渐进的数学结构（讲义第 46–59 页，本讲完整走了一遍）：

• MP / Markov 链：只有 $\mathcal{S}$ 与 $P$，无奖励无动作；有限状态时可写成矩阵 $P$。
• MRP：MP + 奖励函数 $R(s)$ + $\gamma$，仍然没有动作。
• MDP：再加动作，$P(s^{\prime}\vert s,a)$ 与 $R(s,a)$。

1.2.4 回报、值函数与折扣因子

严格定义。在一个 MRP（或固定策略 $\pi$ 下的 MDP）中：

直观解释：$G_t$ 是 “从现在起的全部未来奖励，按 $\gamma^k$ 折算成今天的价值”；$V^\pi(s)$ 是它的期望，即 “在状态 $s$ 上，长期来看这个策略有多好”。

折扣因子的三种语义（讲义第 54–55 页逐条给出，必须记准）：

1. 数学上方便：$H=\infty$ 时若 $\gamma<1$、$\vert r\vert \le R_{\max}$，则 $\vert G_t\vert \le R_{\max}/(1-\gamma)$，回报与值函数有界；$\gamma=1$ 且 $H=\infty$ 时两者都可能发散。
2. 行为建模：人类的行为表现得像有一个 $\gamma<1$（偏好即时收益）。
3. 边界情形：$\gamma=0$ 只看即时奖励；$\gamma=1$ 把未来奖励与即时奖励同等看待；若每个 episode 长度总有限（$H<\infty$），可以安全地取 $\gamma=1$——这正是作业与很多测试环境的默认设置。

具体示例（带数字）。取 Mars Rover 的奖励 $\{+1,+10,0,\dots\}$ 与 $\gamma=0$，讲义第 64、67–68 页的板书答案是

即 $V^\pi(s_1)=+1,\ V^\pi(s_7)=+10$，其余为 $0$：折扣为 0 时值函数退化为即时奖励。作为对照，我们自己的 5×5 GridWorld 中，$\pi_{\text{down}}$ 的 8 步轨迹奖励为 $(-0.04)\times 7$ 后接 $+1$，取 $\gamma=0.9$ 时 $G_0=+0.2696$，而 $\gamma=0$ 时 $G_0=-0.04$（见 §1.4 实验 A）。

1.2.5 RL vs 监督学习 vs 无监督学习 vs 上下文老虎机

这是本讲最重要的一张对比表。核心概念是两种反馈信号：

• 指导性反馈（instructive feedback）：反馈直接告诉你正确的动作是什么——”这张图是猫”。这是监督学习。信息量 $=\log_2 A$ 比特（$A$ 个动作里指认一个）。
• 评价性反馈（evaluative feedback）：反馈只告诉你刚才那个动作有多好——”你这一步得了 $-0.04$”。这是 RL。它不包含任何关于未尝试动作的信息（反事实缺口）。

这一差别是可测量的，不是修辞。§1.4 实验 C 用同一个 25 上下文 × 4 动作的问题对比：专家标签在每个上下文上 1 个样本就把该上下文的 argmax 完全确定（测得的 “已覆盖上下文上的准确率” 恒为 100.0%）；而 RL agent 用 2000 个标量奖励样本，准确率只有 91.8%，因为每个标量奖励只能确定 4 个 $(c,a)$ 值中的 1 个。

1.2.6 探索与利用

严格定义。设 agent 对每个动作有一个估计 $\hat{Q}(a)$。利用（exploitation）指选 $a_t=\arg\max_a \hat{Q}(a)$；探索（exploration）指选一个可能 $\hat{Q}$ 不是最大、但可能提供新信息的动作。最小引言是 $k$-臂老虎机（$k$-armed bandit）：状态空间为空、动作立即产生奖励且不影响下一状态，$\mathcal{A}=\{1,\dots,k\}$，拉臂 $a$ 得到 $r\sim\nu_a$。

用遗憾（regret）刻画代价：

直观解释：$R(T)$ 是 “与一直拉最优臂的先知相比，你总共亏了多少”。$R(T)$ 随 $T$ 线性增长意味着每步都在稳定地漏掉奖励——你没有在学习；$R(T)=O(\sqrt{KT\log T})$ 才说明学习在起作用。

日常类比：选餐厅。已知公司楼下的面馆稳定 7 分（利用），但隔壁新开的店可能是 9 分（探索）；天天吃面馆你不会饿着，但永远不知道隔壁有多好。信息是有价值的，而它只能通过行动获得——讲义第 17 页的说法是 “agent as scientist”。

本讲的立场：L1 只需要你承认 “探索不可避免”；把 $\epsilon$-greedy 做对、给出 UCB 的 $O(\sqrt{KT\log T})$ 保证、以及 Thompson Sampling 的贝叶斯版本，分别是 L9、L9 与 L10 的主题。

1.3 算法伪代码与完整推导

本讲没有待学的算法，但有三个必须能亲手推的数学对象：交互循环、MRP 的 Bellman 方程、以及由它导出的两种求解方式（解析解与迭代解）。下面逐个给出伪代码与推导。

1.3.1 算法 1：Agent–Environment 交互循环（采样一个 episode）

算法 1  Rollout(env, policy, gamma, H_max)
──────────────────────────────────────────────────────────────
输入: 环境 env (提供 reset() 与 step(s,a)->(s',r,done))
      策略 policy (s -> a 或 s -> 动作分布)
      折扣因子 gamma, 最大步数 H_max
输出: 轨迹 tau = [(s_0,a_0,r_0), ..., (s_{T-1},a_{T-1},r_{T-1})]
      折扣回报 G_0
──────────────────────────────────────────────────────────────
 1: s <- env.reset()                       # 得到 s_0
 2: tau <- [] ; ptr <- 0
 3: for t = 0, 1, ..., H_max-1 do
 4:     a <- policy(s)                     # 确定性: a=pi(s)
 5:                                        # 随机性: a ~ pi(.|s)
 6:     (s_next, r, done) <- env.step(s, a)
 7:     tau.append( (s, a, r) )
 8:     s <- s_next
 9:     if done then break
10: end for
11: G_0 <- sum over i of gamma^i * tau[i].r        # 折扣回报
12: return tau, G_0
──────────────────────────────────────────────────────────────

算法逻辑解说。第 4 行是策略唯一出现的地方：策略是 “从状态到动作的映射”，它不知道自己会被怎么评价。第 6 行把世界全部封装进 step：世界只需要接收动作、返回观测与标量奖励。第 9 行的 done 是 episode 边界的抽象。整个 RL 的所有算法都在这 12 行之上做同一件事：把 $(s,a,r,s^{\prime})$ 收集起来，据此改进策略。

与理论的对应。第 3–9 行采样出的 $\tau$ 服从 $p_\pi(\tau)=p(s_0)\prod_t \pi(a_t\mid s_t)P(s_{t+1}\mid s_t,a_t)$——这正是 §1.2.1 中 $J(\pi)$ 的期望所针对的分布。注意这个分布依赖 $\pi$，这是 RL 数据非 i.i.d. 的根源，也是 §1.2.5 对比表的第一行。

为什么 $H_{\max}$ 必须存在：若策略永不进入终止状态，循环不终止。$\gamma<1$ 时理论上有界但采样上仍不终止，所以工程上都需要截断。

1.3.2 推导 1：MRP 的 Bellman 方程

从 $V(s)=\mathbb{E}[G_t\mid s_t=s]$ 出发，把 $G_t$ 拆成第一项和其余：

第一项就是奖励函数 $R(s)$。第二项用全期望公式对 $s_{t+1}$ 展开，再用 Markov 性质 $p(s_{t+1}\vert s_t=s)=p(s_{t+1}\vert h_t)$：

于是得到 Bellman 方程（Bellman equation）：

数学推导（矩阵形式与可逆性）。把 $N$ 个状态的值堆成向量 $V\in\mathbb{R}^N$，$P$ 为 $N\times N$ 行随机矩阵，$R$ 为奖励向量：

$(I-\gamma P)$ 为什么可逆：$P$ 的谱半径 $\rho(P)\le 1$（行随机矩阵的最大特征值为 1），故 $\gamma P$ 的特征值满足 $\vert \lambda\vert \le\gamma<1$，于是 $1$ 不是 $\gamma P$ 的特征值，$(I-\gamma P)$ 非奇异。讲义第 58 页明确写出这一点。代价是矩阵求逆的 $\sim O(N^3)$。

1.3.3 算法 2：MRP 的值迭代（动态规划解）

算法 2  IterativePolicyEvaluation_MRP(P, R, gamma, eps)
──────────────────────────────────────────────────────────────
输入: 转移矩阵 P (N x N), 奖励向量 R (N), 折扣 gamma, 容差 eps
输出: 近似值函数 V
──────────────────────────────────────────────────────────────
 1: V <- zeros(N)                       # V_0(s) = 0 for all s
 2: k <- 0
 3: repeat
 4:     V_new <- R + gamma * P @ V      # 同步更新: V_{k+1} = R + gamma P V_k
 5:     delta <- max(|V_new - V|)
 6:     V <- V_new ; k <- k + 1
 7: until delta < eps
 8: return V, k
──────────────────────────────────────────────────────────────

复杂度：每次迭代 $O(\vert \mathcal{S}\vert ^2)$（讲义第 59 页原文给出）。收敛速度：因为 $\vert \gamma P\vert _\infty=\gamma$，迭代是 $\gamma$-压缩，故

即达到精度 $\epsilon$ 需要 $k=\lceil \log(\vert V_0-V^\star\vert _\infty/\epsilon)/\log(1/\gamma)\rceil$ 次迭代——线性收敛，收敛率 = $\gamma$。$\gamma\to 1$ 时迭代次数爆炸，这正是 “用 $\gamma=1$ 处理无限视界” 在数值上危险的原因。与理论的对应：这就是 L2 值迭代的 MRP 特例（MDP 版本在 $V$ 前多套一层 $\max_a$）。

本讲与 L2 的边界：讲义到第 59 页就停了，没有给出 $V^\pi$ 的 Bellman 期望方程、$V^\star$ 的 Bellman 最优方程、动作值函数 $Q$、或策略迭代。这些是 L2 的内容，本讲只建立 “MRP + 折扣 + 值函数” 这套语言。

1.4 代码实现与实验分析

三个脚本位于 cs234/code/，只依赖 numpy / matplotlib / 标准库（环境为 Python 3.9.21，numpy 2.0.1，matplotlib 3.9.2；无 torch / gym / scipy，环境全部手写）。三个脚本实测运行时间分别为 2.8 s / 4.1 s / 9.2 s，均远低于 60 s 上限。

1.4.1 实验 A：Agent–Environment 交互循环与 5×5 GridWorld

脚本：cs234/code/L01_agent_env_loop.py（输出图 L01_gridworld.png）。

"""L01 实验 A/B/C — 手写 5x5 GridWorld 上的 agent-environment 交互循环。"""
import numpy as np
import matplotlib
matplotlib.use("Agg")          # 无显示环境
import matplotlib.pyplot as plt
np.random.seed(0)

N = 5
START, GOAL = (0, 0), (4, 4)
PITS = {(2, 1), (2, 2), (2, 3)}          # 陷阱：终止且奖励 -1
STEP_REWARD, GOAL_REWARD, PIT_REWARD = -0.04, 1.0, -1.0
ACTIONS = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}   # 上右下左
ACTION_NAMES = {0: "U", 1: "R", 2: "D", 3: "L"}


class GridWorld:
    """最小表格 MDP。接口：reset() / step(state, a) -> (s', r, done)。"""

    def __init__(self, slip=0.0, rng=None):
        self.slip = slip                                   # 随机动力学概率
        self.rng = rng if rng is not None else np.random.default_rng(0)

    def reset(self):
        return START

    def step(self, state, a):
        if state in PITS or state == GOAL:                 # 终止态吸收
            return state, 0.0, True
        if self.slip > 0.0 and self.rng.random() < self.slip:
            a = (a + int(self.rng.choice([1, 3]))) % 4     # 打滑：转 ±90 度
        dr, dc = ACTIONS[a]
        nr = min(max(state[0] + dr, 0), N - 1)             # 撞墙停在原地
        nc = min(max(state[1] + dc, 0), N - 1)
        ns = (nr, nc)
        if ns == GOAL:
            return ns, GOAL_REWARD, True
        if ns in PITS:
            return ns, PIT_REWARD, True
        return ns, STEP_REWARD, False


def pi_down(s):        # 安全策略：先沿第 0 列下到底，再沿第 4 行向右（8 步）
    return 1 if s[0] == N - 1 else 2


def pi_right(s):       # 安全策略：先沿第 0 行向右到头，再沿第 4 列向下（8 步）
    return 2 if s[1] == N - 1 else 1


def pi_pit(s):         # 自杀策略：向右两格后向下，必然踩进陷阱
    return 1 if s[1] < 2 else 2


def pi_random(s, rng=None):        # 随机策略：忽略状态，均匀采样 4 个动作
    rng = rng if rng is not None else np.random.default_rng(0)
    return int(rng.integers(0, 4))


def rollout(env, policy, max_steps=50, rng=None):
    """采样一个 episode，返回 (trajectory, states, rewards, actions)。"""
    s = env.reset()
    states, rewards, acts = [s], [], []
    for _ in range(max_steps):
        a = policy(s) if policy is not pi_random else pi_random(s, rng)
        ns, r, done = env.step(s, a)
        acts.append(a); rewards.append(r); states.append(ns)
        s = ns
        if done:
            break
    return list(zip(states[:-1], acts, rewards)), states, rewards, acts


def discounted_return(rewards, gamma):
    """G_0 = sum_t gamma^t r_t。"""
    return sum((gamma ** t) * r for t, r in enumerate(rewards))


POLICIES = {"pi_down (safe)": pi_down, "pi_right (safe)": pi_right,
            "pi_pit  (suicidal)": pi_pit}

env = GridWorld(slip=0.0)                       # 同一环境，四个不同策略
for name, pol in POLICIES.items():
    traj, states, rewards, acts = rollout(env, pol)
    print(f"\n[{name}]  steps = {len(rewards)}   terminal = {states[-1]}")
    print("   r_t  :", np.round(rewards, 3).tolist())
    print("   G_0  : " + "  ".join(f"gamma={g:<4} -> {discounted_return(rewards, g):+.4f}"
                                   for g in [0.0, 0.5, 0.9, 1.0]))

env_s = GridWorld(slip=0.2, rng=np.random.default_rng(3))     # 随机动力学
for ep in range(5):
    _, states, rewards, _ = rollout(env_s, pi_down, max_steps=50)
    print(f"  episode {ep}: terminal={states[-1]!s:8s} steps={len(rewards):2d} "
          f"r_sum={sum(rewards):+7.3f}  G_0(g=0.9)={discounted_return(rewards, 0.9):+8.4f}")

# 蒙特卡洛估计 V^pi(s0)：注意这是"期望"，上面每一条只是它的一个样本
env_mc = GridWorld(slip=0.2, rng=np.random.default_rng(11))
mc = np.array([discounted_return(rollout(env_mc, pi_down, 50)[2], 0.9)
               for _ in range(5000)])
se = mc.std(ddof=1) / np.sqrt(len(mc))
print(f"  MC V^pi(s0) over 5000 episodes, gamma=0.9: {mc.mean():+.4f} "
      f"+/- {1.96*se:.4f} (95% CI), std={mc.std(ddof=1):.4f}")

# 手算 G_0 与确定性环境的对照（slip=0 时轨迹唯一，方差应为 0）
env_d = GridWorld(slip=0.0)
_, _, rewards_d, _ = rollout(env_d, pi_down)
g = 0.9
for t, r in enumerate(rewards_d):
    print(f"  t={t}: gamma^t = {g**t:.8f}   r_t = {r:+.2f}   term = {g**t*r:+.8f}")
G_hand = sum(g ** t * r for t, r in enumerate(rewards_d))
print(f"  G_0 = {G_hand:+.8f}   (闭式: -0.04*(1-g^7)/(1-g) + g^7 = "
      f"{-0.04*(1-g**7)/(1-g) + g**7:+.8f})")
print(f"  确定性环境下 500 次 rollout 的 MC 均值 = "
      f"{np.mean([discounted_return(rollout(env_d, pi_down)[2], 0.9) for _ in range(500)]):+.8f}"
      "   <- 零方差")

fig, axes = plt.subplots(1, 2, figsize=(10, 4.2))              # 出图 -> L01_gridworld.png
grid = np.zeros((N, N))
for (r, c) in PITS:
    grid[r, c] = -1
grid[GOAL] = 1
axes[0].imshow(grid, cmap="RdYlGn", vmin=-1, vmax=1)
axes[0].set_title("5x5 GridWorld (green=goal, red=pit)")

env_v = GridWorld(slip=0.2, rng=np.random.default_rng(5))     # 逐状态 MC 估值 V^pi(s)
V = np.zeros((N, N))
for r in range(N):
    for c in range(N):
        if (r, c) in PITS:
            V[r, c] = PIT_REWARD
            continue
        if (r, c) == GOAL:
            V[r, c] = GOAL_REWARD
            continue
        vals = []
        for _ in range(300):                                  # 从 (r,c) 出发各跑一条
            s, rew = (r, c), []
            for _ in range(50):
                ns, rr, done = env_v.step(s, pi_down(s))
                rew.append(rr); s = ns
                if done:
                    break
            vals.append(discounted_return(rew, 0.9))
        V[r, c] = np.mean(vals)
axes[1].imshow(V, cmap="viridis"); axes[1].set_title(
    r"MC estimate of $V^{\pi_{down}}(s)$, $\gamma=0.9$, slip=0.2")
for r in range(N):
    for c in range(N):
        axes[1].text(c, r, f"{V[r,c]:.2f}", ha="center", va="center",
                     color="white", fontsize=8)
plt.tight_layout(); plt.savefig("L01_gridworld.png", dpi=110)

代码做什么。GridWorld 把 §1.3.1 的 reset/step 接口实现为一个 5×5 表格 MDP：起点 $(0,0)$、终点 $(4,4)$、陷阱 $\{(2,1),(2,2),(2,3)\}$，每步奖励 $-0.04$（鼓励走短路），进终点 $+1$，进陷阱 $-1$ 并终止。rollout 就是算法 1 的 12 行。四个策略中 pi_down/pi_right 都是 8 步到达终点的最优长度路径，pi_pit 会踩陷阱，pi_random 是随机策略。slip=0.2 的版本让动作有 20% 概率被旋转 ±90°，用来演示随机动力学。

RL 机制透视。这段代码把 §1.2.5 对比表的第一行变成可执行的：rollout 产生的 $\tau$ 不是 i.i.d. 样本，因为 $a_t$ 由 policy 决定，$s_{t+1}$ 由 $P$ 决定。同一行 rewards 里，前 7 个 $-0.04$ 与最后那个 $+1$ 之间的因果关系无法从数据直接读出——这正是 “延迟后果 + 信用分配”（§1.2.1 要素 2）。discounted_return 则把 $\gamma$ 的作用即时显现：同一个 rewards 列表，换 $\gamma$ 就换出一个完全不同的排序。

实验观察（真实运行输出，Python 3.9.21 / numpy 2.0.1）：

同一 environment、同一初始状态，只是换了策略，$\gamma=0.9$ 下的回报从 $+0.2696$ 变成 $-0.8374$——这就是 “策略决定一切” 的最直接证据。三个必须指出的细节：

1. $\gamma=0$ 时三个策略完全无法区分（都是 $-0.04$）：只看即时奖励时，走 8 步还是 4 步、进终点还是进陷阱，都无所谓。$\gamma$ 决定了 “远期” 有多远。
2. $\gamma=0$ 下的排序与 $\gamma=0.9$ 下的排序完全不同：这正是 §1.2.1 “延迟后果” 要素的后果——优化目标的选择本身就在定义问题。
3. $\pi_{\text{pit}}$ 的步数更少、$\gamma=1$ 时的 $r$ 和是 $-1.12$，看起来 “更快”，但在任何 $\gamma>0.5$ 的合理目标下都是灾难。

随机动力学的 5 次 rollout（slip=0.2，真实输出）：

  episode 0: terminal=(4, 4)   steps=12 r_sum= +0.560  G_0(g=0.9)= +0.0393
  episode 1: terminal=(4, 4)   steps= 9 r_sum= +0.680  G_0(g=0.9)= +0.2027
  episode 2: terminal=(4, 4)   steps=12 r_sum= +0.560  G_0(g=0.9)= +0.0393
  episode 3: terminal=(4, 4)   steps= 8 r_sum= +0.720  G_0(g=0.9)= +0.2696
  episode 4: terminal=(2, 1)   steps= 3 r_sum= -1.080  G_0(g=0.9)= -0.8860
  Monte-Carlo V^pi(s0) over 5000 episodes, gamma=0.9: -0.1246 +/- 0.0127 (95% CI)

同一个策略、同一个起点，5 条轨迹里 4 条到达终点、第 4 条踩进陷阱：$G_0$ 是随机变量，$V^\pi(s)$ 是它的期望。实测 Monte-Carlo 估计 $V^{\pi_{\text{down}}}(s_0)=-0.1246$，95% 置信区间 $\pm0.0127$，样本标准差 $0.4598$。最后一段验证了确定性环境（slip=0）的对照：500 次 rollout 全部得到 $+0.26961566$，方差为零——手算值 $G_0=-0.04\cdot\frac{1-0.9^7}{1-0.9}+0.9^7\cdot 1=+0.26961566$ 与蒙特卡洛完全一致，说明实现与 $\sum_t\gamma^t r_t$ 的定义严格对应。

1.4.2 实验 B：探索 vs 利用（10 臂老虎机）

脚本：cs234/code/L01_bandit_intro.py（输出图 L01_bandit.png）。10 臂的真实 Bernoulli 均值固定为 $[0.10,0.50,\mathbf{0.90},0.30,0.70,0.20,0.40,0.60,0.15,0.35]$，最优臂是 arm 2（$\mu^\star=0.9$），$T=1000$，200 个独立种子。

"""L01 实验 B — 10 臂老虎机：贪心为何会卡死，以及遗憾如何增长。"""
import random
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
np.random.seed(0)

K = 10
TRUE_MEANS = [0.10, 0.50, 0.90, 0.30, 0.70, 0.20, 0.40, 0.60, 0.15, 0.35]
MU_STAR, OPT_ARM, T, N_SEEDS = max(TRUE_MEANS), 2, 1000, 200


def run(mean_list, t_max, rnd, eps, trace=0):
    """eps=0 纯贪心 / eps=1 均匀随机 / 0<eps<1 为 eps-greedy。

    返回 (rewards, actions, trace_log)；trace_log 记录前 trace 步的
    (t, 并列最优集合, 所选动作, 奖励, 该动作的 q_hat)。
    """
    n, q = [0] * K, [0.0] * K
    rewards, actions, tin = [0.0] * t_max, [0] * t_max, []
    for t in range(t_max):
        if eps > 0.0 and rnd.random() < eps:
            a = rnd.randrange(K)                       # 探索
        else:                                          # 利用（并列随机打破）
            best = max(q)
            cands = [i for i in range(K) if q[i] == best]
            a = cands[rnd.randrange(len(cands))]
        r = 1.0 if rnd.random() < mean_list[a] else 0.0
        n[a] += 1
        q[a] += (r - q[a]) / n[a]                      # 增量式样本均值
        rewards[t], actions[t] = r, a
        if t < trace:
            tin.append((t, cands, a, r, q[a]))
    return rewards, actions, tin


SPECS = [("always greedy  ", 0.0), ("eps-greedy 0.01", 0.01),
         ("eps-greedy 0.10", 0.10), ("uniform random ", 1.0)]
stats = {name: {"tot": [], "opt": [], "curve": np.zeros(T), "final_arm": [0] * K,
                "reg": {C: [] for C in (250, 500, 1000)}} for name, _ in SPECS}

for i in range(N_SEEDS):
    for name, eps in SPECS:
        rewards, actions, _ = run(TRUE_MEANS, T, random.Random(1000 + i), eps)
        s, cum = stats[name], np.cumsum(rewards)
        s["curve"] += cum
        s["tot"].append(cum[-1])
        s["opt"].append(sum(1 for a in actions if a == OPT_ARM) / T)
        s["final_arm"][actions[-1]] += 1
        for C in (250, 500, 1000):
            s["reg"][C].append(C * MU_STAR - cum[C - 1])

for name, _ in SPECS:
    s = stats[name]
    print(f"{name:17s} total={np.mean(s['tot']):7.2f} "
          f"regret(1000)={np.mean(s['reg'][1000]):7.2f} "
          f"opt-arm={100*np.mean(s['opt']):5.1f}%  "
          f"R(250/500/1000)={np.mean(s['reg'][250]):6.1f}/"
          f"{np.mean(s['reg'][500]):6.1f}/{np.mean(s['reg'][1000]):6.1f}")

g = stats[SPECS[0][0]]
print(f"greedy 最终停在最优臂的种子数: {g['final_arm'][OPT_ARM]}/{N_SEEDS}")
print(f"greedy 最终动作分布: "
      f"{ {k: v for k, v in enumerate(g['final_arm']) if v > 0} }")

代码做什么。run 是 §1.2.6 的 $\epsilon$-greedy：以 $1-\epsilon$ 概率选 $\hat{Q}$ 最大的臂（并列时随机打破），以 $\epsilon$ 概率均匀随机拉一臂，然后用增量式样本均值 $\hat{Q}(a)\leftarrow \hat{Q}(a)+\frac{1}{N(a)}(r-\hat{Q}(a))$ 更新（这条更新式在 L3 会作为常数步长 TD 的特例重新出现）。四个配置共享同一种子，保证比较公平。

RL 机制透视。$\hat{Q}$ 初值为 $0$ 意味着 t=0 时 10 个臂完全并列，第一个动作由 rnd.randrange 这个纯粹的平局规则决定——这不是策略，是任意的。随后 $\epsilon=0$ 时，未尝试的臂永远停留在 $\hat{Q}=0$。由于奖励是 Bernoulli（$r\in\{0,1\}$），任何一次成功的初体验都会把该臂的 $\hat{Q}$ 顶到 $1.0$，于是它永远无法被超过。这就是 “探索” 要素在代码里最赤裸的形态：if rnd.random() < eps 这一行，是整个 RL 里唯一主动获取信息的机制。

实验观察（真实运行输出，T=1000，200 种子平均）：

贪心锁死的实测证据：在 200 个种子中，纯贪心只有 29 个（14.5%） 最终停在最优臂 arm 2，171 个（85.5%）停在一个错误的臂上并再也出不来。最终动作分布为

{0: 7, 1: 25, 2: 29, 3: 12, 4: 32, 5: 8, 6: 26, 7: 39, 8: 4, 9: 18}

——有 39 个种子（19.5%）把整整 1000 步全部花在了 arm 7（真实均值只有 0.60）上。注意标准差 $216.97$ 是所有算法中最大的：贪心的表现极不稳定，好起来 $900$ 分，坏起来 $200$ 分，完全取决于 t=0 那次任意平局的结果。

机制追踪（真实输出，两个种子）：种子 1009 里，t=0 时 10 臂并列，随机选中了 arm 2（即最优臂），第一次就拿到 $r=1$，$\hat{Q}(2)=1.000$；此后 999 步再也没有试过任何别的臂（distinct arms ever tried = 1 of 10: [2]）。种子 1000 里，t=0 选中 arm 6（$r=0$），t=1 仍在并列中选中 arm 1（$r=1$，$\hat{Q}=1.000$），此后永远停在 arm 1（真实均值 0.50），最终奖励率 $0.500$ 对比最优 $0.900$。两个种子的唯一差别是平局时 randrange 落到了哪个索引。

遗憾增长（真实输出）：

纯贪心的 $R(1000)/R(500)$ 恰为 $2.000$：$T$ 翻倍、遗憾也翻倍，意味着每一步都在以恒定速率漏掉奖励——遗憾是线性的，数学上等价于 “什么都没学到”。固定 $\epsilon>0$ 的 $\epsilon$-greedy 同样是线性的（$\epsilon=0.1$ 的比值为 1.458，$\epsilon=0.01$ 为 1.561——比值在减小，但仍趋于 2）。这不是实现缺陷，而是内在性质：若始终留 $\epsilon$ 比例的随机探索，长期看每步仍会以约 $\epsilon\cdot(\mu^\star-\bar\mu)$ 的速率损失。要拿到次线性保证，必须让探索量随时间衰减或用乐观主义——这正是 L9（UCB：$O(\sqrt{KT\log T})$，比值随 $T$ 下降）与 L10（Thompson Sampling） 要解决的问题。L1 只要理解 “为什么必须有 $\epsilon$”，”如何去掉 $\epsilon$” 是 L9–L12 的全部内容。

1.4.3 实验 C：评价性反馈 vs 指导性反馈（可测量的差异）

脚本：cs234/code/L01_evaluative_feedback.py（输出图 L01_feedback.png）。构造一个手写的 25 上下文 × 4 动作的上下文老虎机，奖励带噪 $r(c,a)=M[c,a]+\mathcal{N}(0,1)$，专家标签取无噪 argmax（即标准的行为克隆数据集）。

"""L01 实验 C — 评价性反馈 vs 指导性反馈：单样本信息量的实测差异。"""
import random
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
np.random.seed(0)

NC, NA, SIGMA = 25, 4, 1.0                       # 25 上下文, 4 动作, 奖励噪声
_rng0 = np.random.default_rng(20260105)
M = _rng0.normal(0.0, 1.0, size=(NC, NA))
M -= M.max(axis=1, keepdims=True)                # 平移到 "最优动作值 = 0"
M[np.arange(NC), _rng0.integers(0, NA, size=NC)] += 1.5      # 制造明确赢家
OPT_A = M.argmax(axis=1)                          # 专家标签（无噪 argmax）


def draw(c, a, rnd):
    """一次带噪奖励采样。rnd 是标准库 random.Random（标量工作负载下更快）。"""
    return M[c, a] + SIGMA * rnd.gauss(0.0, 1.0)


def supervised_accuracy(n_samples, rnd):
    """返回 (总体准确率, 上下文覆盖率, 已覆盖上下文上的准确率)。"""
    counts = [[0] * NA for _ in range(NC)]
    for _ in range(n_samples):
        c = rnd.randrange(NC)
        counts[c][int(OPT_A[c])] += 1             # 指导性反馈：直接给 a*
    covered = [c for c in range(NC) if sum(counts[c]) > 0]
    ok = sum(int(np.argmax(counts[c])) == int(OPT_A[c]) for c in covered)
    return (sum(int(np.argmax(counts[c])) == int(OPT_A[c]) for c in range(NC)) / NC,
            len(covered) / NC, ok / len(covered) if covered else float("nan"))


def rl_accuracy(n_samples, rnd, eps):
    """评价性反馈：只拿到标量奖励 + eps-greedy 交互。"""
    n = [[0] * NA for _ in range(NC)]
    q = [[0.0] * NA for _ in range(NC)]
    for _ in range(n_samples):
        c = rnd.randrange(NC)
        if rnd.random() < eps:
            a = rnd.randrange(NA)                 # 探索
        else:
            qr = q[c]; best = max(qr)
            cands = [i for i in range(NA) if qr[i] == best]
            a = cands[rnd.randrange(len(cands))]  # 利用
        r = draw(c, a, rnd)                       # 只反馈一个标量
        n[c][a] += 1
        q[c][a] += (r - q[c][a]) / n[c][a]        # 增量式样本均值
    correct = sum(int(np.argmax(q[c])) == int(OPT_A[c]) for c in range(NC))
    return correct / NC, np.array(n, dtype=float)


for B in [25, 50, 100, 500, 2000]:                # 300 次独立重复
    s = r = r0 = cov = cond = 0.0
    n_rl = np.zeros((NC, NA))
    for k in range(300):
        a1, cv1, cd1 = supervised_accuracy(B, random.Random(5000 + k))
        a2, n2 = rl_accuracy(B, random.Random(9000 + k), 0.10)
        a3, _ = rl_accuracy(B, random.Random(9000 + k), 0.00)
        s += a1; cov += cv1; cond += cd1; r += a2; r0 += a3; n_rl += n2
    print(f"samples={B:5d} sup_acc={100*s/300:6.1f}% sup_cover={100*cov/300:6.1f}% "
          f"sup_acc|cover={100*cond/300:6.1f}%  RL(e=.1)={100*r/300:6.1f}% "
          f"RL(e=0)={100*r0/300:6.1f}%  visits/(c,a)={n_rl.mean()/300:.2f}")

代码做什么。supervised_accuracy 模拟指导性反馈：每个样本给出 “上下文 $c$ 的正确动作是 $a^\star$”，因此它只需用计数投票就能学出精确的 argmax。rl_accuracy 模拟评价性反馈：agent 必须自己挑动作、只拿到一个标量奖励 $r$、只能用样本均值估计 $\hat{Q}(c,a)$。两者的上下文采样方式完全相同（都均匀采样 $c$），因此差异只能来自反馈信号本身——这是一个干净的受控对比。

RL 机制透视。关键在 counts[c][OPT_A[c]] += 1 与 r = draw(c, a, rnd) 的对比：前者把 “正确答案” 直接写进表里，一次就把该行的 $\arg\max$ 钉死；后者只在 $4$ 个格子里填了 $1$ 个带噪数字，另外 $3$ 个格子的值是反事实的、永远观测不到的。要在 $4$ 个带噪估计之间正确地排序，需要每个格子都采到足够多次——这就是 RL 的样本复杂度天然高于监督学习的原因。eps=0 那一列则复现了实验 B 的锁死机制。

实验观察（真实运行输出，每档 300 次重复）：

这张表是 “评价性 vs 指导性” 差异的定量证明：

1. 监督学习的误差只有一个来源——上下文覆盖。一旦某个上下文被访问过，”已覆盖上的准确率” 就恒为 100.0%（从 25 个样本起一直如此），因为专家的标签把该行的 argmax 完全确定了。
2. RL 的误差有两个来源——覆盖 加上 “一个标量奖励只能确定 4 个值中的 1 个”。即使到 2000 个样本、每格平均访问 20 次，准确率也只有 $91.8\%$，而监督学习早已是 $100\%$。
3. 代价可以量化：在 25 个样本时，RL 每格只访问了 $0.25$ 次（约 $75\%$ 的格子从未被碰过）；监督学习在同样 25 个样本下已经达到 $100\%$ 的条件准确率。

第三段代码做了覆盖率的账目统计（单次运行，$T=200$）：监督学习在 $25/25$ 个上下文上知道了最优动作（$100\%$），等价于递交给学习者 $25\times 3=75$ 条 “$a^\star$ 优于 $a$” 的约束；而 RL 观测到 $85/100$ 个 $(c,a)$ 格的标量奖励，等价于 0 条 argmax 形式的约束——一个 $-0.04$ 的奖励不是一条 “这个动作不是最优” 的标签。

第四段的结果值得单独强调（一个反直觉的实测）：在 $\epsilon=0$ 时，这个实例里贪心并没有灾难性地锁死——1000 个样本后准确率仍有 $92.0\%$，$21/25$ 个上下文尝试了多个动作。原因很清楚：该实例被平移成 “只有最优动作的值约为 $0$”，其余均值为负，于是第一次倒霉的采样会把 $\hat{Q}(c,a)$ 压到 $0$ 以下，而未尝试的动作仍保持 $\hat{Q}=0$，贪心规则被迫去试别的动作。这是初始化带来的意外探索，不是设计出来的探索。对照实验 B：那里奖励是 Bernoulli（$r\in\{0,1\}$），一次成功就把 $\hat{Q}$ 顶到 $1.0$，于是同一个 $\epsilon=0$ 规则在 $85.5\%$ 的种子上锁死。结论：绝不能依赖意外探索；正确做法是显式的 $\epsilon$ / UCB / Thompson Sampling（L9/L10），或原理化的探索奖励（L11/L12）。

1.5 评估指标与理论保证

本讲不引入新算法的性能界，但给出了后续所有讲次将使用的评估语言。

（1）评估 vs 控制（evaluation vs control）——讲义第 44 页的定义，措辞必须记准：

• 评估（Evaluation）：给定策略 $\pi$，估计/预测跟随它所能获得的期望奖励，即求 $V^\pi$；
• 控制（Control）：优化——找到最好的策略。用统一记号写就是 $\pi^\star\in\arg\max_\pi J(\pi)$ 与 $V^\star(s)=\max_\pi V^\pi(s)$。

课程结构正按此展开：L2 做有模型的控制，L3 做无模型的评估，L4 做无模型的控制。

（2）本讲可给出的定量保证（MRP 值迭代）。算法 2 的误差界（§1.3.3 推导）为

每轮计算复杂度 $O(\vert \mathcal{S}\vert ^2)$（讲义第 59 页），解析解 $V=(I-\gamma P)^{-1}R$ 的复杂度 $\sim O(\vert \mathcal{S}\vert ^3)$ 但一步到位。两者的取舍是标准的：$\gamma$ 小时迭代法更快，状态数中等且需要极高精度时解析解更可靠。

（3）老虎机的遗憾界。$\epsilon$-greedy 的遗憾是 $\Theta(\Delta_{\min}\cdot\epsilon T)$ 量级，即线性——§1.4.2 实测的比值 $2.000/1.458$ 就是这个事实的数值指纹。次线性保证的标准形式是

其中 $\Delta_a=\mu^\star-\mu_a$。后续讲次会给出 PAC 界 $O(\vert \mathcal{S}\vert \vert \mathcal{A}\vert T)$ 形式的样本复杂度、以及 PAC-MDP 的 $\tilde{O}(\vert \mathcal{S}\vert \vert \mathcal{A}\vert /\epsilon^3)$ 样本界（L11/L12）。

（4）条件依赖分析——这是判断 “一个界能不能用在我问题上” 的清单：

（5）经验性能的评估方式。本讲的三段代码恰好演示了三种：单条轨迹的回报（方差极大、不能作为评价）、多次 rollout 的均值与置信区间（实验 A 的 $-0.1246\pm0.0127$）、以及与先知基准的遗憾（实验 B 的 $R(T)$ 曲线）。CS234 反复强调：在 RL 里，”我跑出来一个数” 几乎从不是证据——必须说明种子数、置信区间和基线。

1.6 与其他讲次的关联

向前依赖：本讲无前置，只需要 CS229 的概率/线代基础（条件期望、全期望公式、矩阵谱半径）与 NumPy 编程。

向后引出（讲义第 21 页 Course Outline 的顺序，与 SPEC §0 的讲次映射一致）：

跨讲的记号连续性：$V^\pi,Q^\pi,A^\pi,V^\star,Q^\star,G_t,d^\pi(s),\rho,J(\theta)$ 在 L1 只出现 $V^\pi$ 与 $G_t$，其余全部在 L2–L5 引入，但含义按 SPEC §4 固定不变。

1.7 关键要点

• 一句话定义：RL = learning through experience/data to make good decisions under uncertainty。目标函数是长期期望折扣回报 $J(\pi)=\mathbb{E}_\pi[\sum_t\gamma^t r_t]$，不是任何单步指标。
• 四个要素必须同时在场：优化、延迟后果、探索、泛化。任何一个单独拎出来都是已有工具（规划、最优控制、bandit、监督学习），四者纠缠才是 RL 的独有难度。
• RL 与监督学习的根本差别在反馈信号：指导性反馈给 “正确答案”（1 个样本定死 1 个 argmax），评价性反馈只给 “刚才有多好”（$A$ 个值里有 $A-1$ 个永远观测不到）。加上 “数据由策略产生 → 非 i.i.d.、分布随策略漂移”，构成了 RL 全部理论困难（重要性采样、离线分布偏移、探索）的来源。
• Markov 假设是唯一的工程杠杆：$p(s_{t+1}\vert s_t,a_t)=p(s_{t+1}\vert h_t,a_t)$。它把无限长的历史 $h_t$ 压成一个状态 $s_t$，代价是状态表示直接决定计算复杂度、所需数据量与最终性能（讲义第 37 页）。
• 折扣因子有三个语义：数学有界性（$\vert V\vert \infty\le R{\max}/(1-\gamma)$）、人类行为建模、以及 “有限视界下可安全取 $\gamma=1$”。$\gamma=0$ 只看即时奖励——本讲实测中它让三个策略的回报无法区分。
• 不探索就一定锁死：纯贪心在 200 个种子中只有 $14.5\%$ 找到最优臂，$19.5\%$ 的种子把 1000 步全花在均值 $0.60$ 的臂上，遗憾 $R(1000)/R(500)=2.000$（严格线性）。$\epsilon$-greedy（$\epsilon=0.1$）把平均总奖励从 $538.03$ 提到 $814.99$，但它仍然是线性遗憾——去掉 $\epsilon$ 是 L9–L12 的任务。
• RL 特别强大的两类问题（讲义第 19 页）：(1) 没有理想行为样本（目标超越人类、或任务没有现成数据）；(2) 带延迟结果的巨大搜索/优化问题（AlphaTensor）。

1.8 常见误区与注意事项

误区 1：把 RL 当成 “带奖励的监督学习”，直接拿轨迹数据做监督回归。 错在哪：轨迹里的动作是当前策略选的，不是专家选的，把它当标签会同时引入两种偏差——(i) 只覆盖策略访问过的动作（实验 C 实测：25 个样本时每格只访问 $0.25$ 次）；(ii) 奖励是带噪的标量，不是 argmax 标签（实验 C：2000 个样本后准确率仍只有 $91.8\%$，而监督学习 $100\%$）。正确认识：这正是离线 RL 的核心难题，必须处理分布偏移（L8、L11–L12）；若数据确实来自专家，应改用模仿学习并显式弥补 $d^{\pi_{\text{expert}}}\neq d^{\pi}$（L7 的 DAgger）。

误区 2：以为 “奖励” 就是 “目标”，奖励函数随手写。 错在哪：RL 会精确地优化你写下的奖励，而不是你心里想的那个目标。讲义第 28–29 页的 AI Tutor 练习就是反例：学生答对给 $+1$、答错给 $-1$，则最优策略会永远只出加法题（学生正确率高、即时奖励最大），完全放弃更难的减法——系统的长期教学目标（让学生学会减法）被短视的即时奖励彻底牺牲。正确认识：奖励设计属于目标设定问题；要鼓励学习本身，需要换奖励（如以 “学习增益” 而非 “答对” 计分，或对信息增益给奖励）。这也是 L16（Value Alignment）的正题。

误区 3：认为 “块状” 假设不重要，随手把观测当状态。 错在哪：$s_t=o_t$ 只是近似。当世界是部分可观测时（POMDP），把观测当状态的策略会做出在 Markov 意义上完全错误的选择。讲义第 37 页把后果写得非常明确：状态表示同时决定计算复杂度、所需数据量、最终性能。正确认识：$s_t=f(h_t)$ 中的 $f$ 是你必须自己设计并承担后果的建模决策；从帧堆叠、RNN/LSTM 隐状态，到 Transformer 的上下文窗口，本质都是构造 $f$ 的不同尝试（L15 整个世界模型讲次都在做这件事）。

误区 4：把 “$\gamma$ 是一个无关紧要的超参数” 或者 “$\gamma$ 越接近 1 越好”。 错在哪：$\gamma$ 改变的是问题本身，不是求解精度。本讲实测：同一 environment 下，$\gamma=0$ 时 pi_down（安全的 8 步）与 pi_pit（4 步踩陷阱）的回报完全相同（都是 $-0.04$），因为它们只看即时奖励；只有 $\gamma>0.5$ 之后二者才拉开（$\gamma=0.9$ 时是 $+0.2696$ 对 $-0.8374$）。同时，值迭代的收敛率就是 $\gamma$（$\vert V_k-V^\star\vert _\infty\le\gamma^k\vert \cdot\vert _\infty$），$\gamma\to1$ 会让迭代轮数爆炸。正确认识：$\gamma$ 编码 “远期有多远” 的业务判断；无限视界问题必须 $\gamma<1$，有限视界才可安全取 $1$。

误区 5：以为 “$\epsilon$-greedy 已经解决了探索问题”。 错在哪：$\epsilon$-greedy 只是让探索存在，它并不让探索高效。实测遗憾 $R(1000)/R(500)$：$\epsilon=0$ 为 $2.000$，$\epsilon=0.01$ 为 $1.561$，$\epsilon=0.10$ 为 $1.458$——全部是线性遗憾，因为固定的 $\epsilon$ 意味着永久以 $\Theta(\epsilon)$ 的速率浪费。正确认识：$\epsilon$-greedy 是 L1 级别的直觉工具；真正的最优性保证需要 UCB（乐观面对不确定性，$O(\sqrt{KT\log T})$）或 Thompson Sampling（L9/L10），以及 MDP 版的乐观初始化/RMax（L11/L12）。

误区 6：把 “$H<\infty$ 所以可设 $\gamma=1$” 与 “$\gamma=1$ 总是安全的” 混淆。 错在哪：讲义第 55 页的原文是 “If episode lengths are always finite ($H<\infty$), can use $\gamma=1$”。一旦环境可能永不终止（如 GridWorld 里策略原地打转、或机器人一直不结束任务），$\gamma=1$ 会让回报发散，$V$ 无定义。正确认识：检查两件事——episode 是否保证终止，以及数值上迭代是否收敛；二者都不成立时必须取 $\gamma<1$。工程上还常加 $H_{\max}$ 硬截断（实验 A 用了 max_steps=50）。

误区 7：用小样本的 rollout 均值当作 $V^\pi$ 的证据。 错在哪：实验 A 实测，同一个策略在 slip=0.2 下 5 条轨迹的 $G_0$ 从 $-0.8860$ 到 $+0.2696$，样本标准差 $0.4598$——单条轨迹与期望可以差出一倍以上。正确认识：报告 RL 结果时必须给出种子数、均值、标准差/置信区间（实验 A 的 5000 次 MC 得到 $-0.1246\pm0.0127$，即 $\pm10\%$ 的相对精度），并与明确基线对比。

1.9 思考题（带答案）

题 1（手算折扣回报 + 与 $\gamma$ 的相互作用）——必做题

考虑 §1.4.1 的 5×5 GridWorld：起点 $(0,0)$，每步奖励 $-0.04$，进终点奖励 $+1$ 且终止，进陷阱奖励 $-1$ 且终止。策略 $\pi_{\text{down}}$ 走 8 步到达终点：$r_0=\cdots=r_6=-0.04$，$r_7=+1$。

(a) 取 $\gamma=0.9$，手算 $G_0=\sum_{t=0}^{7}\gamma^t r_t$。 (b) 若走到 $(2,0)$ 后改走第 2 行（该行第 1、2、3 列是陷阱）会踩陷阱。此时 $r_0=r_1=r_2=-0.04$，$r_3=-1$。取 $\gamma=0.9$ 算 $G_0$，并与 (a) 比较。 (c) 求使 (a) 的 $G_0$ 恰好为 $0$ 的 $\gamma$ 的大致取值（提示：解 $-0.04\frac{1-\gamma^7}{1-\gamma}+\gamma^7=0$）。 (d) 解释：为什么在 $\gamma=0$ 时 (a) 与 (b) 的 $G_0$ 完全相同？

答案：

(a) 几何级数部分：

逐项计算（与脚本输出完全一致）：$1+0.9+0.81+0.729+0.6561+0.59049+0.531441=5.217031$，故 $-0.04\times 5.217031=-0.20868124$；$0.9^7=0.4782969$。因此

(b) $G_0=-0.04(1+0.9+0.81)+0.9^3(-1)=-0.04\times 2.71-0.729=-0.1084-0.729=\boxed{-0.8374}$。（与脚本 pi_pit 一行的 $\gamma=0.9$ 输出 $-0.8374$ 一致。）

(c) 令 $g=\gamma$，需 $-0.04\frac{1-g^7}{1-g}+g^7=0$，即 $-0.04\sum_{t=0}^{6}g^t+g^7=0$。数值扫描（$S(g)=\sum_{t=0}^{6}g^t$）：

变号区间在 $(0.75,0.80)$；二分求解得 $g^\star\approx\boxed{0.756}$。（脚本对 $\gamma=0.5$ 输出 $-0.0716$、对 $\gamma=0.9$ 输出 $+0.2696$，与此一致。）含义：$\gamma<0.756$ 时 “走 8 步只为拿终点奖励” 是亏的，agent 应当宁可就地不动；$\gamma$ 必须足够大，”延迟后果” 才值得追求。

(d) 因为折扣因子是唯一把未来奖励算进目标的机制。$\gamma=0$ 时 $\gamma^t=0$ 对一切 $t\ge 1$ 成立，$G_0=r_0=-0.04$ 无论后续发生什么——终点、陷阱、步数全部被抹掉。三个策略在 $\gamma=0$ 下给出同一个数值，正是 $§1.2.4$ “$\gamma=0$：Only care about immediate reward” 的直接后果。

题 2（用本讲数据论证 “没有探索就没有学习”）

根据 §1.4.2 的真实输出回答：

(a) 纯贪心在 200 个种子中最终停在最优臂 arm 2 的有 29 个。若贪心完全等价于 “随机猜一个臂然后永远只用它”，预期的种子数应是多少？实测 29 与预期相比说明了什么？ (b) 种子 1009 的追踪显示它 1000 步里只尝试过 1 个臂（arm 2）。用 $\hat{Q}$ 的更新式解释为什么它能一直不变。 (c) 有人主张 “让贪心多跑一会儿自然就会探索到别的臂”。用 $R(1000)/R(500)=2.000$ 反驳这个主张。 (d) 为什么 $\epsilon$-greedy($0.1$) 的标准差 ($47.01$) 远小于纯贪心 ($216.97$)？

答案：

(a) 若贪心只是 “随机挑一个臂并永远锁定”，则它选中 arm 2 的概率是 $1/10$，200 个种子中预期 $200\times 0.1=20$ 个。实测 $29$ 个略高于 $20$，因为贪心还会经历 “第一次失败、换臂、第二次成功并锁定” 的两步过程，但量级完全一致。这说明：贪心在 1000 步后的表现基本由最初 1–2 次采样的运气决定，它并不是在学习，而是在抽签。实测最终动作分布 {0:7, 1:25, 2:29, 3:12, 4:32, 5:8, 6:26, 7:39, 8:4, 9:18} 甚至比均匀分布更偏（arm 7 拿到 39 个种子，而它均值只有 0.60），进一步印证了这种随机性。

(b) 增量式更新为 $\hat{Q}(a)\leftarrow \hat{Q}(a)+\frac{1}{N(a)}(r-\hat{Q}(a))$。种子 1009 中 t=0 时 10 个臂 $\hat{Q}$ 全为 $0$，平局规则选中 arm 2，$r=1$，于是 $\hat{Q}(2)=0+\frac{1}{1}(1-0)=1.000$。此后每步 $\arg\max_a\hat{Q}(a)=2$ 唯一（其余都是 $0$），故 $a_t=2$ 永远被选中。更新式只改被选中臂的值：$\hat{Q}(2)$ 会随 $r$ 在 $1.000\to0.667\to0.750\to0.800\to0.833$ 之间浮动，但它始终大于 0，而未尝试的 9 个臂始终是 $0$，因此 argmax 永不改变。关键洞察：锁死不是因为估计准确，而是因为未探索的臂没有估计。

(c) $R(1000)/R(500)=362.0/181.0=2.000$ 意味着观测时长翻倍、累计损失也精确地翻倍，即每步的损失速率是常数（约 $0.362$ 奖励/步）。这是 “没有任何信息被获取” 的数学指纹：如果存在学习，随着时间推移新臂被尝试、损失速率会下降，$R(T)$ 会变成次线性（例如 $R(1000)/R(500)\approx\sqrt{2}=1.41$）。跑到无限久也不会改善。

(d) 因为纯贪心的结果由 t=0 那次任意平局决定，而平局是均匀随机的，所以 “选中好臂”（得分接近 900）与 “选中差臂”（得分低到 200 上下）的概率都不小，200 个种子的总奖励取值高度分散——标准差 $216.97$。$\epsilon=0.1$ 的算法每步都有 $10\%$ 概率随机试臂，因此无论起点多差，它都会在长期内把注意力转移到好臂上，最终稳定在 $79.3\%$ 的最优臂比例上，种子间差异被大幅压缩——标准差只有 $47.01$。这揭示了探索的第二重价值：它不只提高平均性能，更降低方差（降低 “运气决定一切” 的风险）。

题 3（设计题：把 AI Tutor 写成决策过程）

讲义第 28–29 页的练习：学生初始既不会加法（较易）也不会减法（较难），AI 辅导 agent 可以出加法或减法题，学生答对得 $+1$、答错得 $-1$。请

(a) 定义状态空间 $\mathcal{S}$、动作空间 $\mathcal{A}$ 与奖励模型 $R$； (b) 说明动力学模型 $P$ 在这里代表什么； (c) 论证 “最大化期望折扣回报” 的策略会出什么题，以及为什么这不是教育上想要的； (d) 给出一个能鼓励学习的替代奖励设计。

答案：

(a) 状态：至少要记录 “学生对两类技能的掌握程度” 与 “当前的题目类型/难度”。最小可行的表示是 $s=(\text{skill}+,\text{skill}-)$，其中 $\text{skill}_\pm\in\{0,1,2\}$ 表示未掌握/部分/熟练（也可以把 “上一题的作答结果” 编进状态以捕捉学习动态）。动作：$\mathcal{A}=\{\text{出加法题},\text{出减法题}\}$。奖励：$R(s,a)=\mathbb{E}[r\mid s,a]=P(\text{答对}\mid s,a)\cdot(+1)+P(\text{答错}\mid s,a)\cdot(-1)=2P(\text{答对}\mid s,a)-1$。

(b) $P(s^{\prime}\mid s,a)$ 代表学生学习过程的动力学：出某类题之后，学生在对应技能上的掌握度如何迁移（可能进步、可能遗忘、可能因挫败而退步）。它同时编码了教学效果与遗忘效应——注意本讲 §1.2.3 的分类：这里动作同时影响即时奖励与下一状态，所以是完整 MDP，而不是 bandit。

(c) 在 $\text{skill}-=0$（不会减法）时，$P(\text{答对}\mid s,\text{出减法})=0$ 而 $P(\text{答对}\mid s,\text{出加法})=1$。于是 $R(s,\text{加法})=+1>R(s,\text{减法})=-1$。若 $\gamma$ 不够小且学习效应不足以在几步内把减法正确率抬起来，最优策略会永远只出加法题：它拿到稳定的 $+1$，并且（关键）由于减法从未被练习，$\text{skill}-$ 永远停在 $0$，减法题的价值永远看起来很差——这是一个自我实现的信息闭环，与 §1.4.2 中贪心锁死是同一个机制（”未尝试的动作没有估计”）。从教育目标看这是失败的：系统的真实目标是让学生学会减法，那个目标需要学生犯错（负奖励）才能达成。

(d) 至少三种可行方向：(i) 以学习增益计奖励，如 $R=\text{skill}+’(s^{\prime})+\text{skill}-‘(s^{\prime})-\text{skill}+(s)-\text{skill}-(s)$（即 “这一题让学生进步了多少”）；(ii) 以信息增益/不确定性降低计奖励（把 “探索” 直接写进奖励，与 L9–L12 的探索奖励同源）；(iii) 把评估与训练解耦：用最终考试成绩（一个延迟的、稀疏的奖励）作为目标，让 agent 自己发现 “现在多做减法练习” 是长期最优的——这恰好把 §1.2.1 的延迟后果要素变成教学策略的来源。注意 (i)/(ii) 都改变了 MDP 本身，这也再次说明：奖励设计就是目标设定，不是调参（对应 §1.8 误区 2、以及 L16 的 alignment 主题）。

题 4（概念辨析：为什么 $V=(I-\gamma P)^{-1}R$ 一定存在）

(a) 证明 $(I-\gamma P)$ 可逆（$P$ 为行随机矩阵，$\gamma<1$）。 (b) 若 $\gamma=1$ 且 $P$ 是某个吸收链的转移矩阵（存在达到吸收态的正概率），$(I-P)$ 还可逆吗？给出一个 2 状态的例子。 (c) 解释 (b) 的结果与讲义 “有限视界可安全取 $\gamma=1$” 并不矛盾。

答案：

(a) 行随机矩阵满足 $P\mathbf{1}=\mathbf{1}$，故 $\vert P\vert \infty=1$。对任意矩阵范数，谱半径 $\rho(P)\le\vert P\vert _\infty=1$。于是 $\gamma P$ 的谱半径 $\rho(\gamma P)=\gamma\rho(P)\le\gamma<1$。若 $(I-\gamma P)$ 奇异，则存在 $x\neq 0$ 使 $\gamma P x=x$，即 $\gamma P$ 有特征值 $1$，与 $\rho(\gamma P)<1$ 矛盾。故 $(I-\gamma P)$ 非奇异。并且可直接展开 Neumann 级数：$(I-\gamma P)^{-1}=\sum{k=0}^{\infty}\gamma^kP^k$（因为 $\vert \gamma P\vert \infty<1$ 时级数绝对收敛），这与 $V=\sum{k\ge0}\gamma^kP^kR$ 的直觉完全一致——解析解就是 “沿所有长度 $k$ 的路径把奖励折扣累加”。

(b) 取 $P=\begin{pmatrix}1&0\\0&1\end{pmatrix}$（两个状态都是吸收态）。则 $I-P=\begin{pmatrix}0&0\\0&0\end{pmatrix}$，奇异，不可逆；对应 $V(s_1)=R(s_1)+V(s_1)$，除了 $R(s_1)=0$ 无解（若 $R(s_1)\neq0$ 则方程无解，若 $R=0$ 则解不唯一）。几何解读：$V=(I-P)^{-1}R$ 之所以能工作，是因为 $\sum_{k\ge0}P^k$ 收敛；吸收链上状态的 $P^k$ 对角元恒为 1，级数发散。

(c) “有限视界 $H<\infty$ 可安全取 $\gamma=1$” 之所以成立，是因为此时回报被定义为有限和 $G_t=\sum_{k=0}^{H-1-t}r_{t+k}$，而不是无穷级数。对无限视界且保证以概率 1 终止的 properly terminating 情形，$\sum_k r_{t+k}$ 仍是几乎必然有限的（期望可能无穷，需要用 $H$ 截断或 $\gamma<1$ 来保证数值稳定）。因此 (b) 的奇异并不构成矛盾：它只是说明 ”$\gamma=1$ + 无限视界 + 非终止” 是唯一真正危险的组合。工程上的对策正是实验 A 里那句 max_steps=50。