强化学习学习记录（一）：Bandit、MDP 与 TD

1. 多臂老虎机问题

多臂老虎机问题可以理解为：有多根拉杆，每根拉杆都有一个未知的奖励概率。算法不知道哪根拉杆最好，只能通过不断尝试来估计每根拉杆的收益，并尽量多选择收益高的拉杆。

这个问题的核心矛盾是：

探索：尝试不熟悉的拉杆，收集更多信息
利用：选择当前看起来最好的拉杆，获得更高奖励

为了解决这个问题，代码中先定义了一个通用父类 Solver。它不负责具体怎么选择拉杆，而是负责所有算法都需要的公共流程：

self.counts   # 每根拉杆被选择的次数
self.regret   # 当前累计懊悔
self.actions  # 每一步选择的动作
self.regrets  # 每一步后的累计懊悔

其中 run_one_step() 是留给具体算法实现的。父类的 run() 会反复调用它：

k = self.run_one_step()
self.counts[k] += 1
self.actions.append(k)
self.update_regret(k)

所以这个框架的设计思想是：公共记录逻辑放在父类中，具体决策策略放在子类中。

2. epsilon-贪婪算法

epsilon-贪婪算法的思想很直接：

大多数时候选择当前估计最好的拉杆
少数时候随机选择一根拉杆进行探索

如果设置 epsilon = 0.01，意思就是：

1% 的概率随机探索
99% 的概率选择当前估计收益最大的拉杆

核心代码是：

if np.random.random() < self.epsilon:
    k = np.random.randint(0, self.bandit.K)
else:
    k = np.argmax(self.estimates)

这里 self.estimates 表示算法当前对每根拉杆奖励概率的估计。每次选择拉杆并得到奖励后，需要更新这根拉杆的估计值：

self.estimates[k] += 1. / (self.counts[k] + 1) * (r - self.estimates[k])

这个式子本质上是在用增量平均的方法更新估计值：

其中：

r - self.estimates[k]

表示这一次实际奖励与旧估计之间的差距。

epsilon-贪婪算法简单有效，但它的探索是随机的。它并不知道哪些拉杆更值得探索。

3. UCB 上置信界算法

UCB 的全称是 Upper Confidence Bound，即上置信界算法。

它的核心思想是：

选择“当前估计奖励 + 不确定性奖励”最大的拉杆。

公式可以写成：

其中：

• $\hat Q(a)$：第 $a$ 根拉杆当前的平均奖励估计。
• $u(a)$：第 $a$ 根拉杆的不确定性。
• $c$：控制探索强度的系数。

如果某根拉杆被尝试得很少，那么它的不确定性比较大，UCB 会给它一个额外的探索奖励。这样它就不是盲目随机探索，而是优先探索那些“还不够确定、但可能很好”的拉杆。

常见的不确定性项是：

这里：

• $t$：当前总时间步。
• $N(a)$：第 $a$ 根拉杆被选择的次数。

当 N(a) 很小时，不确定性项会比较大；当 N(a) 很大时，说明已经充分了解这根拉杆，不确定性项就会变小。

4. 霍夫丁不等式与 UCB 的来源

UCB 背后用到了霍夫丁不等式。对于取值范围在 [0,1] 的独立随机变量，霍夫丁不等式给出：

它的含义是：

样本均值比真实均值低很多的概率，会随着样本数 n 增加而指数级下降。

在多臂老虎机中，可以把：

• $\mathbb{E}[X]$ 看作某根拉杆的真实期望奖励 $Q(a)$。
• $\bar X_n$ 看作当前样本均值估计 $\hat Q(a)$。

于是有：

这说明：

$\hat Q(a)+u$

可以看作真实期望奖励的一个上界。UCB 就是选择这个上界最大的拉杆。

如果令：

解出 u：

当取 p = 1/t 时，就得到类似：

这就是 UCB 不确定性项的来源。

5. 汤普森采样算法

汤普森采样和 epsilon-贪婪、UCB 的思路不同。它不是只维护一个奖励估计值，而是为每根拉杆维护一个奖励概率分布。

它的核心流程是：

1. 从每根拉杆的概率分布中各采样一个值
2. 选择采样值最大的拉杆
3. 拉动这根拉杆，得到奖励
4. 根据奖励更新这根拉杆的概率分布

代码核心是：

samples = np.random.beta(self._a, self._b)
k = np.argmax(samples)
r = self.bandit.step(k)
self._a[k] += r
self._b[k] += (1 - r)

汤普森采样的探索来自分布本身的不确定性。如果某根拉杆试得少，它的分布会比较宽，就有机会采到较大的值，从而被选中；如果某根拉杆试得多而且表现好，它的分布会集中在较高区域，因此经常被选中。

6. Beta 分布的直观理解

汤普森采样中常用 Beta 分布来描述每根拉杆的中奖概率。

Beta 分布可以理解为：

对“一个概率到底是多少”的信念分布。

因为概率一定在 [0,1] 之间，而 Beta 分布刚好定义在 [0,1] 上，所以它很适合表示中奖率、点击率、成功率这类变量。

Beta 分布写作：

在多臂老虎机里，可以直观理解为：

例如某根拉杆被拉了 10 次，其中中奖 7 次、未中奖 3 次，那么它的分布就是：

这里的均值是：

所以：

这表示算法当前认为这根拉杆的中奖概率大约在 0.667 附近。

但 Beta 分布不仅表示均值，还表示不确定性。比如：

但是它们含义不同：

• $\mathrm{Beta}(2,2)$：数据少，不确定性大。
• $\mathrm{Beta}(50,50)$：数据多，更确定概率接近 $0.5$。

所以看 Beta 分布时要同时看：

• $\frac{a}{a+b}$：分布中心在哪里。
• $a+b$：数据量有多大，分布有多确定。

另外，Beta 分布不是正态分布。它的取值范围是 [0,1]，适合表示概率；正态分布的取值范围是整个实数轴。只是当 a 和 b 都很大时，Beta 分布在中间区域可能看起来近似钟形。

7. 马尔可夫奖励过程 MRP

学习完多臂老虎机后，开始进入马尔可夫奖励过程，即 MRP。

MRP 中有几个基本要素：

状态集合
状态转移概率矩阵 P
奖励函数 rewards
折扣因子 gamma

转移概率矩阵 P 的含义是：

$P[i][j]$ 表示从状态 $s_i$ 转移到状态 $s_j$ 的概率。

奖励函数 rewards 表示每个状态对应的即时奖励：

rewards = [-1, -2, -2, 10, 1, 0]

这表示：

s1 的奖励是 -1
s2 的奖励是 -2
s3 的奖励是 -2
s4 的奖励是 10
s5 的奖励是 1
s6 的奖励是 0

折扣因子 gamma 控制未来奖励的重要程度：

当 gamma = 0.5 时，越远的奖励权重越小。

8. 计算一条状态序列的回报

对于一条状态序列：

chain = [1, 2, 3, 6]

它表示：

$s_1\rightarrow s_2\rightarrow s_3\rightarrow s_6$

对应奖励是：

$-1,-2,-2,0$

如果 gamma = 0.5，从 s1 开始的回报是：

代码中使用从后往前递推的方法：

G = gamma * G + rewards[chain[i] - 1]

它对应的公式是：

这种写法比直接展开公式更方便。

9. 贝尔曼方程求状态价值

最后学习了如何一次性求出 MRP 中每个状态的价值。

状态价值函数 V(s) 表示：

从状态 $s$ 出发，未来能够获得的期望折扣回报。

MRP 的贝尔曼方程是：

整理：

提取 V：

两边乘以逆矩阵：

代码实现是：

def compute(P, rewards, gamma, states_num):
    rewards = np.array(rewards).reshape((-1, 1))
    value = np.dot(
        np.linalg.inv(np.eye(states_num, states_num) - gamma * P),
        rewards
    )
    return value

这里算出的不是某一条具体路径的回报，而是所有状态的长期期望回报。

10. 本阶段学习总结

这一阶段的学习路线是：

多臂老虎机
-> epsilon-贪婪算法
-> UCB 上置信界算法
-> 霍夫丁不等式
-> 汤普森采样
-> Beta 分布
-> MRP
-> 状态序列回报
-> 贝尔曼方程求状态价值

目前的核心理解是：

多臂老虎机关注的是单步决策中的探索与利用；
MRP 开始关注状态转移过程中的长期回报；
贝尔曼方程则提供了递推计算状态价值的方法。

后续可以继续学习 MDP，在 MRP 的基础上加入动作，从而真正进入强化学习中的策略、价值函数、策略评估和策略改进。

11. 第 05 章：马尔可夫决策过程

这一章从随机过程出发，逐步引出强化学习中的标准环境模型：马尔可夫决策过程（Markov Decision Process, MDP）。

学习路线是：随机过程 -> 马尔可夫性质 -> 马尔可夫过程 MP -> 马尔可夫奖励过程 MRP -> 马尔可夫决策过程 MDP -> 价值函数 -> 贝尔曼方程 -> 蒙特卡洛估计 -> 占用度量 -> 最优策略。

随机过程。

随机过程描述的是“随机变量随时间变化”的过程。例如天气变化、交通状态变化、智能体在环境中的状态变化。

在时刻 $t$，系统所处状态记为 $S_t$，所有可能状态构成状态集合 $\mathcal{S}$。

一般情况下，未来状态可能依赖过去所有状态：

如果不做简化，预测下一步就需要知道完整历史。

马尔可夫性质。

马尔可夫性质的核心是：未来只依赖现在，不直接依赖过去。

这表示只要知道当前状态 $S_t$，过去状态 $S_1,\ldots,S_{t-1}$ 对预测下一步就不再提供额外信息。

需要注意：马尔可夫性质不是说历史完全没影响，而是说历史信息已经被当前状态压缩进去了。当前状态相当于对过去的充分总结。

马尔可夫过程 MP。

马尔可夫过程（Markov Process, MP）就是具有马尔可夫性质的随机过程，也常叫马尔可夫链。

它可以写成二元组：

其中 $\mathcal{S}$ 是状态集合，$\mathcal{P}$ 是状态转移矩阵。

如果有 $n$ 个状态，状态转移矩阵中第 $i$ 行第 $j$ 列表示：

也就是从状态 $s_i$ 转移到状态 $s_j$ 的概率。

每一行概率之和必须为 1：

马尔可夫奖励过程 MRP。

马尔可夫奖励过程（Markov Reward Process, MRP）是在 MP 的基础上加入奖励函数和折扣因子。

其中 $\mathcal{S}$ 是状态集合，$\mathcal{P}$ 是状态转移矩阵，$r$ 是奖励函数，$\gamma$ 是折扣因子。

折扣因子满足：

$\gamma$ 越接近 1，越重视长期奖励；$\gamma$ 越接近 0，越重视眼前奖励。

回报 Return。

从时刻 $t$ 开始，未来所有奖励的折扣和称为回报：

也可以写成：

例子：状态序列为 $s_1\rightarrow s_2\rightarrow s_3\rightarrow s_6$，对应奖励为 $-1,-2,-2,0$。如果 $\gamma=0.5$，那么从 $s_1$ 出发的回报是：

代码上可以从后往前递推：

G = 0
for state in reversed(chain):
    G = rewards[state] + gamma * G

这个递推对应：

MRP 中的状态价值函数。

状态价值函数表示：从某个状态出发，未来能获得的期望回报。

展开后可以得到：

这就是 MRP 中的贝尔曼方程。它的直觉是：

贝尔曼方程的矩阵形式。

如果把所有状态价值写成列向量：

把奖励写成列向量：

那么贝尔曼方程可以写成：

整理得：

所以：

对应代码：

def compute(P, rewards, gamma, states_num):
    rewards = np.array(rewards).reshape((-1, 1))
    value = np.dot(
        np.linalg.inv(np.eye(states_num, states_num) - gamma * P),
        rewards
    )
    return value

这种解析解很直接，但矩阵求逆复杂度较高，状态数量很大时不适合直接用。后面会引入动态规划、蒙特卡洛方法、时序差分等近似或迭代方法。

马尔可夫决策过程 MDP。

马尔可夫决策过程（Markov Decision Process, MDP）是在 MRP 的基础上加入动作。

其中 $\mathcal{S}$ 是状态集合，$\mathcal{A}$ 是动作集合，$P(s'\mid s,a)$ 是状态转移函数，$r(s,a)$ 是奖励函数，$\gamma$ 是折扣因子。

MP 和 MRP 是“系统自己随机变化”，而 MDP 中多了智能体的动作。智能体可以在状态 $s$ 下选择动作 $a$，动作会影响下一状态和奖励。

强化学习里的交互过程：

1. 智能体观察状态 $S_t$。
2. 智能体根据策略选择动作 $A_t$。
3. 环境根据 $P(s'\mid s,a)$ 转移到新状态 $S_{t+1}$。
4. 环境给出奖励 $R_t$。
5. 智能体继续决策。

策略 Policy。

策略描述智能体在某个状态下如何选择动作，记作：

如果策略是确定性策略，每个状态只对应一个动作；如果策略是随机性策略，每个状态对应一个动作概率分布。

因为 MDP 满足马尔可夫性质，所以策略只需要依赖当前状态，不需要依赖完整历史。

状态价值函数和动作价值函数。

在 MDP 中，状态价值必须和策略绑定。原因是：同一个状态下，不同策略可能选不同动作，后续轨迹和奖励都会不同。

状态价值函数定义为：

动作价值函数定义为：

状态价值和动作价值之间有两个重要关系。

第一，状态价值是动作价值的策略加权平均：

第二，动作价值等于即时奖励加上下一状态价值期望：

贝尔曼期望方程。

状态价值的贝尔曼期望方程：

动作价值的贝尔曼期望方程：

这一组公式非常重要。后面的很多强化学习算法，本质上都是围绕这些价值函数和贝尔曼方程展开的。

从 MDP 转成 MRP。

如果给定一个策略 $\pi$，MDP 就可以被“固定”为一个 MRP。因为策略决定了每个状态下动作的概率，于是可以把动作维度求期望消掉。

新的奖励函数：

新的状态转移概率：

直觉是：

所以“策略评估”本质上就是：在某个固定策略下，计算每个状态的价值。

蒙特卡洛方法。

蒙特卡洛方法的核心是：不用知道完整模型，只通过大量采样轨迹来估计期望。

在 MDP 中，状态价值是期望回报：

因此可以用多次采样的平均回报来近似：

基本流程：

1. 按照策略 $\pi$ 与环境交互，采样很多条完整序列。
2. 对序列中出现过的状态，从该时刻往后计算回报 $G$。
3. 用这些回报的平均值更新状态价值。

增量平均更新写法是：

这和前面多臂老虎机里估计奖励均值的更新形式非常像。

占用度量。

不同策略会导致智能体访问不同的状态和动作，因此策略的价值不同。

状态访问分布描述策略 $\pi$ 下智能体访问状态 $s$ 的概率：

其中 $P_t^\pi(s)$ 表示按照策略 $\pi$ 行动时，第 $t$ 时刻处于状态 $s$ 的概率。

占用度量进一步描述状态-动作对被访问的概率：

它和状态访问分布的关系是：

直观理解：某个状态动作对出现得越频繁，它在该策略下的占用度量越大。

最优策略。

强化学习的目标通常是找到一个最优策略，使得智能体获得最大的期望回报。

如果对所有状态都有：

就可以说策略 $\pi$ 不差于策略 $\pi'$。

最优状态价值函数定义为：

最优动作价值函数定义为：

最优状态价值和最优动作价值之间的关系是：

贝尔曼最优方程。

贝尔曼期望方程描述的是“给定策略 $\pi$ 时”的价值关系；贝尔曼最优方程描述的是“选择最优动作时”的价值关系。

最优状态价值方程：

最优动作价值方程：

这两个公式是后续动态规划、值迭代、Q-learning 等方法的理论基础。

小结。

MP、MRP、MDP 的区别：

回报和价值的区别：

• 回报 $G_t$ 是某一条具体轨迹上实际得到的折扣奖励和。
• 价值 $V(s)$ 是从状态 $s$ 出发的期望回报。

状态价值和动作价值的区别：

• $V^\pi(s)$：只指定当前状态，之后按策略行动。
• $Q^\pi(s,a)$：指定当前状态和当前动作，之后按策略行动。

贝尔曼期望方程和贝尔曼最优方程的区别：

• 贝尔曼期望方程：评估一个给定策略。
• 贝尔曼最优方程：寻找最优策略或最优价值。
• 期望方程里通常有策略概率 $\pi(a\mid s)$；最优方程里通常有 $\max$。

这一章最重要的结论是：强化学习中的环境可以建模为 MDP；给定策略后，MDP 可以退化为 MRP；MRP 和 MDP 的状态价值都满足贝尔曼方程；要求最优策略，就需要求解贝尔曼最优方程。

后续学习动态规划、蒙特卡洛方法、时序差分、SARSA、Q-learning 时，重点就是看这些算法如何估计或求解：

12. 第 06 章：动态规划算法

参考链接：

• 学习平台：动态规划算法
• 原教材：动态规划算法

这一章讲的是如何在已知完整 MDP 模型的情况下，用动态规划求解最优策略。

这里的“已知完整 MDP 模型”指的是我们已经知道：

• 状态集合 $\mathcal{S}$
• 动作集合 $\mathcal{A}$
• 状态转移函数 $P(s'\mid s,a)$
• 奖励函数 $r(s,a)$ 或 $R(s,a,s')$
• 折扣因子 $\gamma$

动态规划类强化学习算法的典型前提是：环境是白盒的，状态空间和动作空间通常是离散且有限的。

本章核心算法有两个：

1. 策略迭代（Policy Iteration）
2. 价值迭代（Value Iteration）

动态规划在强化学习中的作用。

动态规划的基本思想是：把大问题拆成子问题，先求子问题，再用子问题结果求当前问题。

在强化学习里，这个“子问题”就是下一状态的价值。贝尔曼方程正好提供了这种递推结构：

所以动态规划算法本质上就是反复用贝尔曼方程更新所有状态的价值。

和蒙特卡洛方法、时序差分方法不同，动态规划不需要通过采样轨迹来估计价值。它直接使用环境模型 $P$ 和 $r$ 来做计算。

它的优点是理论清晰、能直接求解最优策略；缺点是必须提前知道完整模型，现实中很多环境做不到这一点。

悬崖漫步环境。

本章使用 Cliff Walking，也就是悬崖漫步环境，作为策略迭代和价值迭代的例子。

环境是一个 $4\times 12$ 的网格世界：

• 左下角是起点。
• 右下角是终点。
• 起点和终点之间是一段悬崖。
• 智能体可以执行上、下、左、右 4 个动作。
• 每走一步奖励为 $-1$。
• 掉入悬崖奖励为 $-100$，并结束当前回合。
• 到达终点也结束当前回合。

代码中环境的核心是转移表：

P[state][action] = [(p, next_state, reward, done)]

其中：

• p 是转移概率。
• next_state 是下一个状态。
• reward 是奖励。
• done 表示是否终止。

在悬崖漫步中，状态转移基本是确定性的，所以每个状态动作对通常只对应一个下一个状态。

策略迭代总览。

策略迭代由两个步骤循环组成：

1. 策略评估：计算当前策略 $\pi$ 的状态价值 $V^\pi(s)$。
2. 策略提升：根据当前价值函数，贪心地改进策略。

循环过程可以理解为：

如果某次策略提升之后，策略不再变化，就说明已经找到最优策略。

策略评估。

策略评估的目标是：给定一个策略 $\pi$，求出它的状态价值函数 $V^\pi(s)$。

回顾贝尔曼期望方程：

这个公式右边又包含 $V^\pi(s')$，所以可以用迭代方式近似求解：

这里 $V_k$ 是第 $k$ 轮的价值估计，$V_{k+1}$ 是用贝尔曼期望方程更新后的新估计。

在代码里，策略评估大致做的是：

for s in states:
    value = 0
    for a in actions:
        qsa = 0
        for p, next_state, r, done in env.P[s][a]:
            qsa += p * (r + gamma * V[next_state] * (1 - done))
        value += pi[s][a] * qsa
    new_V[s] = value

当一轮更新前后差异足够小，就可以停止：

其中 $\theta$ 是收敛阈值。

策略提升。

策略提升的目标是：利用当前价值函数 $V^\pi$，构造一个更好的策略 $\pi'$。

先计算在状态 $s$ 下执行动作 $a$ 的动作价值：

如果某个动作满足：

说明在状态 $s$ 下选择这个动作，比原策略在这个状态的平均表现更好。

策略提升定理说，如果新策略 $\pi'$ 在每个状态下都满足：

那么新策略不会比旧策略差：

因此可以直接构造贪心策略：

代码中就是对每个状态计算所有动作的 qsa，然后把最大值对应的动作设为概率 1，其余动作设为 0。

策略迭代算法流程。

策略迭代可以总结为：

1. 初始化策略 $\pi$，通常可以初始化为均匀随机策略。
2. 初始化状态价值 $V(s)$。
3. 进行策略评估，得到当前策略的 $V^\pi(s)$。
4. 根据 $V^\pi(s)$ 做策略提升，得到新策略 $\pi'$。
5. 如果新旧策略相同，停止。
6. 否则令 $\pi\leftarrow\pi'$，回到策略评估。

伪代码可以写成：

while True:
    policy_evaluation()
    old_policy = policy
    policy_improvement()
    if policy == old_policy:
        break

在悬崖漫步环境中，策略迭代会逐步把策略改成一条避开悬崖并到达终点的路径。

策略迭代的特点是：

• 每次策略提升前，会尽量把当前策略的价值评估准确。
• 策略提升次数可能较少。
• 但每次策略评估可能需要很多轮，因此计算成本可能较高。

价值迭代。

价值迭代可以理解成一种更直接的做法：不显式维护策略，而是直接用贝尔曼最优方程更新状态价值。

贝尔曼最优方程是：

把它写成迭代更新形式：

与策略评估相比，区别在于：

• 策略评估是对动作按 $\pi(a\mid s)$ 加权求和。
• 价值迭代是直接对动作取最大值 $\max_a$。

也就是说，价值迭代每一步都假设当前要选择最优动作。

当 $V_k$ 收敛后，再从价值函数中恢复策略：

策略迭代和价值迭代的区别。

二者都基于贝尔曼方程，但更新方式不同。

策略迭代：

• 有显式策略 $\pi$。
• 先评估当前策略。
• 再基于价值函数改进策略。
• 结构是“评估 -> 提升 -> 评估 -> 提升”。

价值迭代：

• 主要维护价值函数 $V$。
• 不需要每轮完整评估某个策略。
• 每次更新都直接使用 $\max_a$。
• 最后从收敛的价值函数中恢复策略。

可以粗略理解为：

冰湖环境。

本章还使用 Frozen Lake，也就是冰湖环境，进一步测试策略迭代和价值迭代。

冰湖环境也是网格世界，常见大小是 $4\times4$：

• 起点在左上角。
• 终点在右下角。
• 中间有若干冰洞。
• 动作包括左、下、右、上。
• 到达目标奖励为 1。
• 掉入冰洞或到达目标后终止。
• 因为冰面会滑，执行一个动作后不一定精确到达预期方向。

因此冰湖环境的状态转移是随机的。比如智能体想往右走，可能会滑到其他相邻方向。这时 env.P[s][a] 里就可能有多个转移结果：

[(p1, next_state1, reward1, done1),
 (p2, next_state2, reward2, done2),
 ...]

这正好体现了 MDP 中 $P(s'\mid s,a)$ 的含义。

在冰湖环境中，策略迭代和价值迭代也能求出最优策略。由于环境有随机滑动，最优策略不一定是“看起来最短”的路径，而是要综合考虑掉入冰洞的风险。

收敛性直觉。

策略迭代为什么会收敛？

因为策略提升定理保证每次提升后，新策略至少不比旧策略差：

在有限 MDP 中，确定性策略总数是有限的。如果状态数为 $|\mathcal{S}|$，动作数为 $|\mathcal{A}|$，那么确定性策略数量最多为：

每次策略提升都不变差，因此最终会收敛到最优策略。

价值迭代为什么会收敛？

价值迭代可以定义贝尔曼最优算子：

当 $\gamma<1$ 时，贝尔曼最优算子是一个压缩算子：

这表示每次迭代后，当前价值函数和最优价值函数之间的距离都会缩小。因此：

小结。

这一章的核心是：在已知完整 MDP 的情况下，可以用动态规划直接求解最优策略。

最重要的两个算法：

• 策略迭代：反复进行策略评估和策略提升。
• 价值迭代：直接用贝尔曼最优方程更新价值函数。

最关键的区别：

• 策略迭代使用贝尔曼期望方程评估当前策略。
• 价值迭代使用贝尔曼最优方程直接逼近最优价值。

动态规划方法的局限：

• 需要知道完整的 $P(s'\mid s,a)$ 和 $r(s,a)$。
• 通常要求状态空间和动作空间有限。
• 状态数量很大时，对所有状态反复扫一遍会很贵。

本章和后续章节的关系：

• 如果知道完整模型，可以用动态规划。
• 如果不知道模型，但可以采样完整轨迹，可以用蒙特卡洛方法。
• 如果不知道模型，而且想边采样边更新，可以用时序差分方法。

所以动态规划是强化学习算法的理论起点，后续很多无模型算法都可以看成是在没有完整模型时，对贝尔曼方程做近似求解。

13. 第 07 章：时序差分算法

参考链接：

• 学习平台：时序差分算法
• 原教材：时序差分算法

这一章进入无模型强化学习（model-free reinforcement learning）。前一章的动态规划要求我们已知完整 MDP，也就是已知 $P(s'\mid s,a)$ 和 $r(s,a)$。但现实中很多环境的转移概率无法直接写出来，智能体只能通过和环境交互采样数据来学习。

本章核心内容：

1. 时序差分方法（Temporal Difference, TD）
2. Sarsa 算法
3. 多步 Sarsa 算法
4. Q-learning 算法
5. 在线策略与离线策略

从动态规划到无模型学习。

动态规划的更新依赖完整模型：

这里必须知道 $P(s'\mid s,a)$ 和 $r(s,a)$。

无模型强化学习不再要求知道这些东西。它只需要智能体采样到一条条交互数据：

然后直接根据这些样本更新价值函数或策略。

时序差分方法 TD。

时序差分方法结合了蒙特卡洛方法和动态规划方法的思想。

蒙特卡洛方法的状态价值更新是：

其中 $G_t$ 是从当前时刻开始直到序列结束得到的完整回报。因此蒙特卡洛方法必须等一整条轨迹结束后才能更新。

TD 方法不等完整轨迹结束，只用一步奖励和下一个状态的价值估计来更新：

其中：

叫作 TD 误差。

直观理解：

• $V(s_t)$ 是旧估计。
• $r_t+\gamma V(s_{t+1})$ 是新的学习目标。
• 两者之差就是当前估计错了多少。

TD 更新可以写成：

TD 公式的推导。

TD 公式本质上来自贝尔曼方程。

状态价值函数的定义是：

完整回报为：

把回报拆成当前奖励和下一时刻回报：

两边取条件期望：

而从下一状态 $S_{t+1}$ 开始的期望回报就是下一状态价值：

所以得到贝尔曼形式：

实际学习时，我们不知道真实的 $V^\pi$，只能维护一个估计 $V$。当智能体真实走出一步，得到样本：

就用单步样本近似贝尔曼期望，把下面这个量作为 TD 目标：

旧估计是 $V(s_t)$，目标是 $r_t+\gamma V(s_{t+1})$，两者差值就是 TD 误差：

让旧估计朝目标移动一步：

代入 $\delta_t$，得到 TD 更新公式：

直观理解是：原来估计 $s_t$ 的价值是 $V(s_t)$；现在走了一步，发现这一步奖励是 $r_t$，下一状态估计价值是 $V(s_{t+1})$，所以 $s_t$ 的价值应该更接近 $r_t+\gamma V(s_{t+1})$。

TD、MC、DP 的关系。

TD 方法和前面两类方法的关系很重要。

蒙特卡洛方法：

• 不需要环境模型。
• 使用完整回报 $G_t$。
• 无偏，但方差较大。
• 必须等序列结束才能更新。

动态规划：

• 需要完整环境模型。
• 使用贝尔曼方程做期望更新。
• 不需要采样轨迹。
• 适用于已知模型的小规模离散 MDP。

时序差分：

• 不需要环境模型。
• 不需要等整条序列结束。
• 使用一步奖励和下一状态价值估计。
• 有偏，但方差较小。

可以粗略记成：

这里“自举”（bootstrapping）指的是：用当前价值函数自己的估计 $V(s_{t+1})$ 来更新 $V(s_t)$。

需要特别区分两个概念：MC 也可以使用增量式更新，但它的更新目标 $G_t$ 必须等完整 episode 结束后才能得到。

MC 的增量更新可以写成：

这个公式是增量式的，但 $G_t$ 是完整回报：

因此 MC 要先知道 $t$ 之后整条轨迹的奖励，才能计算这一次的 $G_t$。而 TD 的目标是：

走完一步后，$r_t$ 和 $s_{t+1}$ 已经知道，表里也已经有 $V(s_{t+1})$ 的当前估计，所以 TD 可以立刻更新。

总结成一句话：

• MC 可以增量更新价值估计，但要等完整回报 $G_t$。
• TD 不需要完整回报，用一步奖励加下一状态价值估计，所以当前步结束就能更新。

Sarsa 算法。

TD 方法可以用来估计状态价值 $V(s)$，也可以用来估计动作价值 $Q(s,a)$。

Sarsa 的核心更新公式是：

它用到了五个量：

所以叫 Sarsa。

这五个量分别是：

• 当前状态 $s_t$
• 当前动作 $a_t$
• 当前奖励 $r_t$
• 下一个状态 $s_{t+1}$
• 下一个动作 $a_{t+1}$

$\epsilon$-贪婪策略。

Sarsa 中需要一边学习 $Q$，一边根据 $Q$ 选择动作。为了避免只选当前看起来最好的动作而失去探索，通常使用 $\epsilon$-贪婪策略。

实际代码里通常是：

if np.random.random() < epsilon:
    action = np.random.randint(n_action)
else:
    action = np.argmax(Q_table[state])

也就是大多数时候利用当前 $Q$ 表，少数时候随机探索。

Sarsa 的代码主线。

Sarsa 类通常维护一个 Q 表：

self.Q_table = np.zeros([nrow * ncol, n_action])

含义是：

• 每一行对应一个状态。
• 每一列对应一个动作。
• Q_table[s][a] 表示状态 s 下执行动作 a 的价值估计。

训练流程：

1. 初始化环境，得到初始状态 $s$。
2. 用 $\epsilon$-贪婪策略选出动作 $a$。
3. 执行动作，得到 $r$ 和 $s'$。
4. 在 $s'$ 下继续用 $\epsilon$-贪婪策略选出 $a'$。
5. 用 Sarsa 公式更新 $Q(s,a)$。
6. 令 $s\leftarrow s'$，$a\leftarrow a'$。
7. 重复直到回合结束。

对应的训练循环核心是：

state = env.reset()
action = agent.take_action(state)
done = False

while not done:
    next_state, reward, done = env.step(action)
    next_action = agent.take_action(next_state)
    agent.update(state, action, reward, next_state, next_action)
    state = next_state
    action = next_action

注意：Sarsa 更新时用的是实际采样出来的下一个动作 next_action，所以它学习的是当前 $\epsilon$-贪婪策略本身的价值。

多步 Sarsa。

一阶 TD 只看一步：

蒙特卡洛会一直看到序列结束。多步 Sarsa 介于两者之间：先看 $n$ 步真实奖励，再接上第 $n$ 步后的价值估计。

多步目标为：

更新公式是：

直观理解：

• $n=1$ 时，就是普通 Sarsa。
• $n$ 越大，越接近蒙特卡洛。
• 小 $n$ 方差较小，但偏差更明显。
• 大 $n$ 偏差较小，但方差更大。

代码上，多步 Sarsa 会额外保存最近若干步：

self.state_list = []
self.action_list = []
self.reward_list = []

当列表长度达到 $n$，就可以回头更新 $n$ 步前的状态动作价值。

Q-learning 算法。

Q-learning 也是基于 TD 的算法，但它和 Sarsa 的更新目标不同。

Q-learning 的更新公式是：

和 Sarsa 对比：

Sarsa 用实际按照当前策略选出来的下一个动作 $a_{t+1}$；Q-learning 直接假设下一步会选择最优动作。

因此 Q-learning 更接近贝尔曼最优方程：

Sarsa 和 Q-learning 的核心区别。

Sarsa 是在线策略（on-policy）算法。

它的行为策略和目标策略是同一个策略。也就是说，它用当前 $\epsilon$-贪婪策略采样，也评估这个 $\epsilon$-贪婪策略。

Q-learning 是离线策略（off-policy）算法。

它可以用一个带探索的行为策略采样，但更新目标却是贪心最优策略：

所以：

• Sarsa 学的是“我实际怎么走时的价值”。
• Q-learning 学的是“如果我下一步总选最优动作时的价值”。

在悬崖漫步中，这个区别很直观：

• Sarsa 考虑 $\epsilon$-贪婪探索带来的风险，所以学到的路径往往离悬崖远一点，更保守。
• Q-learning 学最优贪心路径，可能更贴近悬崖，因为它的目标里默认下一步会选最优动作。

在线策略和离线策略。

在线策略和离线策略要区分两个策略：

• 行为策略（behavior policy）：用来和环境交互、采样数据的策略。
• 目标策略（target policy）：真正被学习、被优化的策略。

在线策略算法：

离线策略算法：

Sarsa 的更新必须使用五元组：

其中 $a'$ 来自当前策略，所以它是在线策略算法。

Q-learning 只需要四元组：

它不要求 $s'$ 后面的动作来自当前行为策略，而是直接取 $\max_{a'}Q(s',a')$，所以它是离线策略算法。

这里的“离线策略”对应英文 off-policy，不等于“离线强化学习” offline reinforcement learning。

更准确地说：

• on-policy / off-policy：讨论采样策略和学习目标策略是不是同一个。
• online RL / offline RL：讨论学习过程中还能不能继续和环境交互采新数据。

所以 Q-learning 的经典用法是：

也就是：它一边和环境交互，一边学习；但它实际采样可以用 $\epsilon$-greedy，更新目标却用贪心策略。

Q-learning 中可以有两套动作：

这里的 $b$ 是行为策略，例如 $\epsilon$-greedy，负责真实执行动作、让环境转移到 $s_{t+1}$。

更新时却使用：

这相当于目标策略是：

所以可以这样记：

实际走路时可以探索，更新价值时假设未来走当前最优路。

这也是 Q-learning 在悬崖问题中更激进的原因。它实际训练时虽然有 $\epsilon$-greedy 探索，但更新目标默认下一步会选最优动作，因此更容易学到贴近悬崖的最短路径；Sarsa 会把真实探索动作也算进更新目标，所以会考虑随机探索掉下悬崖的风险。

Replay buffer 和离线强化学习。

Replay buffer 是经验回放池，用来存储过去和环境交互得到的样本：

在线强化学习加 replay buffer 的流程是：

1. 智能体继续和环境交互，得到新样本。
2. 把新样本放进 buffer。
3. 训练时从 buffer 里随机抽样更新网络或 $Q$ 表。

因此 replay buffer 通常还是在线强化学习的一部分，因为数据池会不断加入新经验。

离线强化学习则不同。离线强化学习只有一个固定数据集：

训练过程中不能再和环境交互，也不能试错。因此离线强化学习最怕的问题是：模型给数据集中很少出现的动作一个过高的 $Q$ 值，但又没有机会真实试一下来纠正。

所以三者关系可以这样区分：

Q-learning 收敛性证明。

Q-learning 可以看成对贝尔曼最优算子的随机近似。

先看 Q-learning 的原始更新：

为了证明它收敛，我们关心 $Q_t$ 会不会越来越接近最优动作价值函数 $Q^*$。

证明通常需要这些条件：

• 状态集合和动作集合有限。
• 奖励有界。
• 折扣因子满足 $0\le \gamma<1$。
• 每个状态动作对 $(s,a)$ 被访问无限多次。
• 学习率满足 Robbins-Monro 条件：

第一个条件表示“不能太早停止学习”，第二个条件表示“后期噪声影响要逐渐变小”。

定义误差：

目标就是证明：

也就是：

贝尔曼最优算子记为 $\mathcal{H}$：

最优 $Q^*$ 是这个算子的不动点：

把一次采样得到的随机更新目标写成：

这里的 $s'$ 是从真实环境转移中采样出来的，所以 $F_t(s,a)$ 是随机的。它的条件期望是：

也就是：

又因为 $Q^*=\mathcal{H}Q^*$，所以：