[CH02]马尔可夫决策过程

2026-07-17

零、写在前面

在老虎机问题中，只要知道每个行动的平均奖励，就可以比较行动。可一旦行动会改变未来，眼前的奖励就不再足够。

例如，向右移动的第一步可能立刻得到 $-2$，但第二步可能得到 $+6$。如果只贪图当前奖励，就会作出错误选择。我们因此需要一种统一语言描述：

$$ \text{当前状态} \xrightarrow{\text{行动}} \text{下一个状态与奖励} \xrightarrow{\text{继续决策}} \text{长期收益}. $$

这个框架就是马尔可夫决策过程（Markov Decision Process，MDP）。

之前写过一些马尔可夫的东西：马尔可夫链

一、马尔可夫决策过程

1.1 什么是MDP

1.1.1 MDP 的具体例子

机器人是智能代理，网格世界是环境；向左或向右是行动；苹果和炸弹对应奖励。与老虎机不同，向左或右后，机器人所处的位置改变了。这个“当前位置”就是状态。

状态不是环境的全部物理细节，而是为了作出后续决策必须保留的信息。

在这条一维走廊里，当前位置足以说明下一步能去哪里、能拿到什么奖励，因此可把位置作为状态。

时间步

每做一次决策、执行一次行动、发生一次迁移，就是一个时间步。第 $t$ 个时间步的状态记为 $S_t$，行动记为 $A_t$，下一个状态为 $S_{t+1}$。

我们改造一下网格：

现在右移的第一步立即得到 $-2$，但若再右移一步会得到 $+6$。因此最佳行为不应只比较“下一步奖励”，而要比较从现在起所有未来奖励的总和。

$$ \text{选择行动的依据不是即时 } R_t \text{，而是长期收益。} $$

1.1.2 智能代理与环境的互动

我们用以下时间序列描述一次持续互动：

$$ S_0,A_0,R_0,S_1,A_1,R_1,S_2,A_2,R_2,\ldots $$

在时间步 $t$，代理看到 $S_t$，选择 $A_t$，环境给出 $R_t$，并迁移到 $S_{t+1}$。

$$ (S_t,A_t)\longrightarrow(R_t,S_{t+1}). $$

奖励下标的约定

许多强化学习资料把“在 $S_t$ 执行 $A_t$ 后获得的奖励”写成 $R_{t+1}$。我们这里约定成 $R_t$。两种写法描述的是同一交互事件，只是下标对齐方式不同。后文不再赘述。

1.2 环境和智能代理的数学表示

我们依次用三个要素描述“环境与代理如何互动”：

状态迁移：状态如何迁移。
奖励：如何给予奖励。
策略：智能代理如何决定行动。

它们分别对应环境的状态迁移模型、环境的奖励函数和代理的策略。值得注意的是：前两者描述环境，第三者描述代理。

更严格地分层时，环境的 MDP 模型包含状态集合、行动集合、状态迁移 $p$ 和奖励函数 $r$；策略 $\pi$ 是代理在这个环境中采用的决策规则；折现率 $\gamma$ 属于我们定义长期目标的方式。

1.2.1 状态迁移

左图：确定性迁移

如果当前状态 $s$ 和行动 $a$ 一旦给定，下一个状态 $s'$ 唯一确定，那么迁移是确定性的：

$$ s'=f(s,a). $$

例如，在没有打滑的一维走廊中，机器人从中间向左走就一定到左边格子。

右图：随机性迁移

现实中，动作也可能失败或有噪声。若选择向左后，有 0.9 的概率真的向左、0.1 的概率留在原地，就需要表示所有可能的下一个状态：

$$ p(s'\mid s,a). $$

它表示“当前为 $s$，采取 $a$ 的条件下，迁移到 $s'$ 的概率”。固定 $s,a$ 后，对所有可能 $s'$ 的概率必须构成一个分布：

$$ \sum_{s'}p(s'\mid s,a)=1. $$

在上图的例子中，若当前位置是 L3，选择 Left，且地面会打滑，则一个具体分布可以是：

$$ p(L2\mid L3,\text{Left})=0.9,\qquad p(L3\mid L3,\text{Left})=0.1, $$

其余格子的迁移概率为 0。注意这里不是说策略有 0.9 概率选 Left；行动 Left 已经给定，0.9 和 0.1 描述的是环境对该行动的响应。

确定性迁移是随机性迁移的特例：真正会抵达的状态概率为 1，其他状态概率为 0。因此后续理论通常用 $p(s'\mid s,a)$ 统一描述两种情形。

马尔可夫性

本章的“马尔可夫”指：一旦给定当前状态 $s$ 和行动 $a$，下一个状态的分布不需要更早的历史。

$$ p(S_{t+1}\mid S_t,A_t,S_{t-1},A_{t-1},\ldots) =p(S_{t+1}\mid S_t,A_t). $$

这不是说过去从未发生过，而是说过去对未来的影响已经被当前状态完整概括了。

一个有用的建模检查是：若你发现“只知道当前状态仍无法预测行动后果”，状态就漏掉了关键信息。例如，若地面是否湿滑会影响移动结果，而状态里只记录坐标、不记录湿滑程度，那么仅靠坐标并不满足马尔可夫性；把该信息加入状态才可能恢复这一性质。

1.2.2 奖励函数

我们首先假定奖励是确定性的。若状态从 $s$ 经过行动 $a$ 迁移到 $s'$，奖励由：

$$ r(s,a,s') $$

给出。这个函数叫作奖励函数。

它的三个输入告诉你：从哪里出发、做了什么、最后到哪里。具体任务可以更简单。若奖励只取决于终点，例如“到苹果格奖励 +1”，则可写成：

$$ r(s'). $$

当然奖励可以是随机的。此时只要把 $r(s,a,s')$ 理解为该随机奖励的期望值，后续的 MDP 推导仍可使用。为了清晰，先把奖励当作确定值。

1.2.3 智能代理的策略

策略（policy）说明代理在各状态下如何选择行动。

确定性策略是一个函数：

$$ a=\mu(s). $$

例如，若 $\mu(L3)=\text{Left}$，就表示在 L3 必定向左。

随机性策略是一个条件概率分布：

$$ \pi(a\mid s). $$

例如，在状态 L3 以 0.4 的概率向左、0.6 的概率向右：

$$ \pi(\text{Left}\mid L3)=0.4,\qquad \pi(\text{Right}\mid L3)=0.6. $$

对每个固定状态 $s$，策略也必须满足：

$$ \sum_a\pi(a\mid s)=1. $$

确定性策略可以看作随机策略的特例：被选行动的概率为 1，其他行动的概率为 0。正因如此，我们后续主要使用更一般的 $\pi(a\mid s)$。

1.3 MDP 的目标

现在，环境有状态迁移概率 $p(s'\mid s,a)$ 与奖励函数 $r(s,a,s')$，代理有策略 $\pi(a\mid s)$。MDP 的目标是找到最优策略，即让长期收益最大的策略。

1.3.1 回合制任务和连续性任务

回合制任务的例子

强化学习任务常分成两类：

类型	有没有自然结束	例子	重新开始
回合制任务（episodic）	有	一局围棋、走到迷宫终点	到终点后回到初始状态
连续性任务（continuing）	没有	库存管理、持续控制	理论上一直运行

不要把“回合制或连续性”与“确定性或随机性”混为一谈。这是两组独立维度：任务可以是确定性的连续任务，也可以是随机性的回合任务。

1.3.2 收益

代理不只关心这一步奖励，而关心从当前时刻起得到的总回报。我们把它称为收益（return）：

$$ G_t=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+\cdots. $$

$\gamma$ 是折现率（discount rate）。在连续性任务中通常取 $0\le\gamma<1$，例如 $\gamma=0.9$：

$$ G_t=R_t+0.9R_{t+1}+0.81R_{t+2}+\cdots. $$

折现有两个作用：

对连续性任务，避免无穷多奖励的和轻易发散；
让更近的奖励权重更大，明确“今天的收益”和“很久以后的收益”如何权衡。

例如，若向右第一步是 $-2$，第二步是 $+6$，且之后奖励都为 0，那么从这一步开始的两步收益为：

$$ -2+0.9\times6=3.4. $$

因此，即时奖励 $-2$ 并不代表“向右一定不好”。

γ 的直觉

γ 的取值	偏好	需要注意
接近 0	主要看眼前奖励	容易忽略长期后果
接近 1	更重视长期奖励	连续任务中要防止收益不收敛
等于 1	回合制且回合有限时常可使用	对无穷持续任务通常不能仅靠它保证有限收益

以后每看到价值函数或贝尔曼方程，都要先确认它使用的 $\gamma$ 是多少。它不是无关紧要的实现常数，而是任务目标的一部分。

1.3.3 状态价值函数

即使状态相同，策略可能随机选行动，环境也可能随机迁移，所以一次实际收益 $G_t$ 仍是随机变量。比较策略时，应比较收益的期望：

$$ v_\pi(s) =\mathbb{E}_\pi\left[G_t\mid S_t=s\right]. $$

这叫作状态价值函数（state-value function）。它回答的是：

从状态 $s$ 出发，此后始终遵循策略 $\pi$，平均而言可以获得多大的折现收益？

下标 $\pi$ 不能省略，因为同一状态下换一套决策规则，未来的行动、状态和奖励都会改变，价值自然也会改变。

$\mathbb E_\pi$ 的下标突出“策略被固定为 $\pi$”。这个期望还会平均环境本身的随机性，例如状态迁移概率 $p(s'\mid s,a)$，以及存在时的奖励随机性；它不只是在平均代理随机选行动。

记号	含义
$G_t$	一次实际轨迹得到的折现收益，具有随机性
$v_\pi(s)$	真实的期望收益
$V_\pi(s)$	对真实价值的估计，后续算法将学习它

1.3.4 最优策略和最优价值函数

两个策略不能只凭某一个起点的表现判断好坏。我们采用逐状态比较：

$$ v_{\pi'}(s)\ge v_\pi(s),\qquad\text{对所有状态 }s. $$

若上式成立，策略 $\pi'$ 至少不差于 $\pi$；若某些状态严格更大，就有更强的理由选择 $\pi'$。

反过来，若 $\pi'$ 在一个状态更好、在另一个状态更差，则不能说它在这个意义下全面优于 $\pi$。

最优策略写作 $\pi^*$，它在所有状态的价值都不低于任何其他策略。对应的最优状态价值函数为：

$$ v^*(s)=\max_\pi v_\pi(s). $$

不过我们这里讨论的有限、折现 MDP 中至少存在一个最优策略，而且可以取为确定性策略。

直观上，一旦已经知道每个状态下各行动的长期效果，选择其中一个最优行动即可；随机混合不会超过最优行动本身。不要把这句话不加条件地推广到所有连续空间、部分可观测或受额外约束的强化学习问题。

1.4 MDP 的例子

我们现在用一个只有两个方格的连续性网格世界，把本章概念收束为可手算的问题。

代理可在每个状态选择 Left 或 Right。迁移和奖励如下：

当前状态	行动	下一个状态	奖励	原因
L1	Left	L1	-1	撞左墙
L1	Right	L2	+1	吃到苹果
L2	Left	L1	0	返回，苹果重新出现
L2	Right	L2	-1	撞右墙

这是一个确定性、连续性 MDP：给定状态和行动，下一状态与奖励唯一确定；没有终点，过程一直继续。

1.4.1 回溯线形图

我们可以用回溯线形图表示从一个起点出发，状态、行动和奖励随时间如何展开：

1.4.2 找出最优策略

两个状态各有两个行动，所以确定性策略共有：

$$ 2^2=4 $$

种。为了避免依赖图中的编号，下面用“在 L1 的行动 / 在 L2 的行动”列举它们，折现率 $\gamma=0.9$。

记号	L1 的行动	L2 的行动	$v_{\mu}(L1)$	$v_{\mu}(L2)$
$\mu_1$	Right	Right	-8	-10
$\mu_2$	Right	Left	5.263…	4.737…
$\mu_3$	Left	Right	-10	-10
$\mu_4$	Left	Left	-10	-9

以 $\mu_1$ 为例，展示一下收益计算过程：

若从 L1 出发，奖励序列是：
$$ > 1,-1,-1,-1,\ldots > $$
因此：
$$ > \begin{aligned} > v_{\mu_1}(L1) > &=1+0.9(-1)+0.9^2(-1)+\cdots\\ > &=1-\frac{0.9}{1-0.9}\\ > &=-8. > \end{aligned} > $$
若从 L2 出发，立刻撞右墙，之后也一直撞墙：
$$ > v_{\mu_1}(L2)=-1-0.9-0.9^2-\cdots=-10. > $$

那么我们把每个策略的收益都算出来就知道哪个最优了。

那么显然Right / Left 最优

它的奖励循环是：

$$ 1,0,1,0,\ldots $$

故从 L1 开始：

$$ v_{\mu_2}(L1)=1+\gamma^2+\gamma^4+\cdots =\frac{1}{1-\gamma^2} =\frac{1}{1-0.9^2} \approx5.263. $$

从 L2 开始则先得到 0，再进入 L1：

$$ v_{\mu_2}(L2)=\gamma v_{\mu_2}(L1)\approx4.737. $$

它在 L1 和 L2 两个状态的价值都高于其余三种策略，因此是的最优策略。

1.5 小结

我们把第 1 章的“行动—奖励”框架推广为：

$$ S_t \xrightarrow[\text{环境}]{A_t} (R_t,S_{t+1}), \qquad A_t\sim\pi(\cdot\mid S_t). $$

环境由状态迁移和奖励函数描述，代理由策略描述。

马尔可夫性要求当前状态已经包含预测未来所需的信息；因此，策略可以只根据当前状态作出选择。

本章最终的目标不是最大化某一步的奖励，而是找出在每个状态都使期望折现收益最大的策略。先定义：