马尔可夫阶梯（MDP）

是什么让一个状态成为”状态”

上一章结束时，“最大化期望累积奖励”仍然不是良定义的，并且点明了缺的那一块：一个关于状态的结构性假设。本章先把它补上，然后在它之上分三级搭出强化学习的标准环境模型。

先说假设本身。在能够搭建任何环境模型之前，“状态”需要一个精确的含义。并不是所有对过去的概括都配得上被称为状态；马尔可夫性质正是决定哪些概括够格的那个条件。

定义马尔可夫性质

如果在给定 $s_t$ 的条件下，未来与整个过去历史条件独立，我们就说状态 $s_t$ 是马尔可夫的：

$$P(s_{t+1} \mid s_t, s_{t-1}, \dots, s_0) = P(s_{t+1} \mid s_t)$$

当涉及动作时，同样的表述会同时对动作条件化：

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t)$$

说得直白一点：给定当前状态，未来在条件上与过去无关。

注状态即充分统计量

这其实就是经典统计学里”充分统计量”这个概念，只不过把它用在了时间上，而不是样本上。一个参数的充分统计量，是对数据的一种概括，它不会丢失任何与推断该参数相关的信息。一旦有了它，原始数据里剩下的都是噪声。一个马尔可夫状态，就是对未来的充分统计量：它是对历史的一种概括，不会丢失任何与预测接下来会发生什么相关的信息。而且并非巧合的是，正是这同一个想法，让物理学能够为动力系统写下一阶微分方程，位置和动量之所以构成经典力学里的马尔可夫状态，恰恰是因为它们把系统的整个历史，从它未来的演化中”屏蔽”掉了。“找到一个状态”和”为未来找到一个充分统计量”，其实是同一个问题换了一身外衣。

不做这个假设要付什么代价

定义说清楚了马尔可夫性质断言了什么，上面那个 remark 说清楚了它意味着什么。但两者都没说，我们究竟为什么要假设它。常见的答案是”这样数学才好处理”，这个说法把实情说轻了：不做这个假设，模型不是变得不好用，而是根本写不下来、也根本学不到。这个说法可以靠数数变得精确。

命题条件于完整历史的代价

设状态空间有限，$|S| = n$，时域为 $T$。一个条件于完整历史的转移模型需要

$$\sum_{t=0}^{T-1} n^{t+1}(n-1) = n^{T+1} - n$$

个自由参数。而一个假设了马尔可夫性质的转移模型需要 $n(n-1)$ 个，与 $T$ 无关。

证明

在时刻 $t$，历史 $(s_0, s_1, \dots, s_t)$ 有 $n^{t+1}$ 种不同的取值。每一种取值都索引着它自己的、关于 $n$ 个可能下一状态的分布，而一个 $n$ 元分布有 $n-1$ 个自由参数，因为这些概率被约束为求和等于一。所以时刻 $t$ 贡献 $n^{t+1}(n-1)$ 个参数。对 $T$ 次转移求和，并对 $n > 1$ 计算等比级数 $\sum_{t=0}^{T-1} n^{t+1} = n(n^T-1)/(n-1)$：

$$\sum_{t=0}^{T-1} n^{t+1}(n-1) = (n-1)\cdot\frac{n(n^{T}-1)}{n-1} = n^{T+1} - n.$$

注意这是 $T$ 张真正不同的表：不同 $t$ 处的历史长度不同，所以没有任何东西迫使某一时刻的模型与另一时刻共享参数。

在马尔可夫性质下，对每一个 $t$ 都有 $P(s_{t+1} \mid s_t, \dots, s_0) = P(s_{t+1} \mid s_t)$，于是这 $T$ 张表全部塌缩成一个 $n \times n$ 的随机矩阵。它有 $n$ 行，每行是一个 $n$ 元分布，因此共 $n(n-1)$ 个自由参数，而 $T$ 已经从表达式里彻底消失了。

这里拉开的差距不是一个常数倍。取一个 $10 \times 10$ 的网格世界，即 $n = 100$，回合长度 $T = 100$ 步，无论按什么标准这都是一个小问题：

条件于	自由参数	网格世界，$n=100$，$T=100$
完整历史	$n^{T+1} - n$	$\approx 10^{202}$
最近 $k$ 个状态	$n^{k}(n-1)$	$\approx 10^{2k+2}$
只有当前状态（马尔可夫）	$n(n-1)$	$9{,}900$

完整历史的模型需要 $10^{202}$ 量级的数字。而可观测宇宙里大约有 $10^{80}$ 个原子。这个要求不是”昂贵”，它是任何物理数量的内存都无法满足的要求；而马尔可夫模型回答同一个问题只用 $9{,}900$ 个数字。

更深的问题在统计，不在存储

存储是比较容易讲、但也比较不致命的那个反对意见。假设内存是免费的，参数仍然必须从数据中估计出来，而在这一层，完整历史模型的失败是任何硬件都救不回来的。

要靠数频率来估计某个历史 $h$ 对应的 $P(\cdot \mid h)$，学习器必须多次访问 $h$。但在一条轨迹内部，每一个历史前缀 $(s_0,\dots,s_t)$ 按构造恰好只出现一次：一条轨迹从它自己的每一个前缀上只经过一遍。所以对某个给定的长度为 $t$ 的历史，访问次数只能跨轨迹累积，而有 $n^{t+1}$ 个历史在争抢这些访问。要让每一个长度为 $T$ 的历史哪怕被看到一次，就需要 $n^{T}$ 量级的轨迹，更不用说要多到足以估计一个以它为条件的分布。

马尔可夫性质改变的是数据被池化的对象。对状态 $s$ 的每一次访问，无论在哪个时刻、哪条轨迹、之前发生过什么，都是关于同一行 $P(\cdot \mid s)$ 的证据。要求从”反复访问这一条完整历史”降级成了”反复访问这一个状态”，而后者在普通的交互中随时都在被满足。这就是为什么马尔可夫性质是一个使之成为可能的假设，而不是一个便利：正是它让转移模型能够从有限的经验中被估计出来。

注这个假设有一个旋钮，而旋钮是标了价的

完整历史和只看当前状态，是一个谱系的两个极端。一个 $k$ 阶马尔可夫模型条件于最近 $k$ 个状态，代价是 $n^{k}(n-1)$ 个参数，并在 $k=1$ 时退回普通的马尔可夫性质。上面那张表给这个旋钮标了价：在这个网格世界上，$k=1$ 要 $9{,}900$ 个参数，$k=2$ 要 $990{,}000$ 个，$k=3$ 大约要 $10^{8}$ 个，而 $k=4$ 已经越过 $10^{10}$。每多记住一步，模型就再乘一个 $n$。

这也正是本节末尾提到的那些”把历史加进状态”的补救办法的账单。帧堆叠就是一个 $k$ 阶模型，而它之所以堆四帧而不是四百帧，原因就写在这个几何式增长里，不在任何深刻的原理里。

注函数近似修好了什么，没修好什么

上面的计数假设模型是被显式存下来的，是一张以历史为索引的表。把这张表换成一个函数近似器，存储那本账会变：一个把历史映射到下一状态分布的网络，参数量取决于它的架构，而不是 $n^{T+1}$。

但它并不废除那个统计论证。近似器仍然要从数据中学到这个映射，而数据里每一条长历史仍然是每条轨迹最多出现一次。函数近似真正买到的，是在历史之间泛化：一个隐含在架构里的假设，认为相似的历史有相似的未来。这不是从本节的问题里逃脱出去了，这是另一个结构性假设，在做马尔可夫性质在这里做的同一件事，出于同一个理由被选中。它应该被当作一个假设来认，而不是被误认成”没有假设”。

“是马尔可夫的”这件事并不是自动成立的，它是状态表示或有或无的一个性质，而且把它弄对很重要：

为什么状态必须信息充分

一个马尔可夫状态必须包含所有与任务相关、用来预测下一状态分布和即时奖励所需的信息。一旦动作存在，还要包含每个可用动作会带来什么后果的信息。如果状态表示遗漏了重要的历史信息，两个看起来一模一样的状态实际上可能有完全不同的未来。从这样一个信息不充分的状态学到的价值函数和策略，可能在结构意义上就是错的：智能体实际面对的是一个部分可观测的问题，它的算法却假设这是一个完全可观测的问题。

注马尔可夫性质失效时

如果当前的观测不是马尔可夫的，常见的补救办法包括：把历史信息也加入状态表示、堆叠多帧观测、使用 RNN 或其他隐状态、显式学习一个 belief state，或者干脆把问题重新建模成 POMDP（部分可观测马尔可夫决策过程）。更深层的问题从来都不只是”计算量变大了”，而是状态表示在结构上就不够用，以至于从它学出来的价值函数或策略，对真正的底层过程而言可能根本就不是良定义的。

从这里往后，一切都假设这个性质成立。下面三级阶梯，就是这个假设成立之后能够搭出来的东西，一次只加一样原料。之所以要这样一级一级加，是因为每加一样，模型能问出的问题就变了。

第一级：只有状态转移

满足马尔可夫性质的最简单对象，是一个只有状态空间和状态间移动规则、别无他物的系统。

定义马尔可夫过程

马尔可夫过程是一个在状态之间随机移动、同时满足马尔可夫性质的系统。它写作一个二元组：

$$(S, P)$$

其中 $S$ 是状态空间，$P$ 是转移概率 $P(s' \mid s)$：如果当前状态是 $s$，系统以概率 $P(s' \mid s)$ 转移到状态 $s'$。

这里没有智能体，也没有奖励。世界只是按照 $P$ 自行演化，模型里没有任何东西去问某个特定状态是好是坏。它只描述状态是如何随时间变化的。压缩地说：MP = 状态转移，仅此而已。

第二级：加入”好坏”的概念

要在纯粹的马尔可夫过程之上加的第一层结构，是对结果的标量评判，即奖励，再加上一种把奖励在一个可能无限长的未来上聚合起来的方式。

定义马尔可夫奖励过程

马尔可夫奖励过程是在马尔可夫过程的基础上加入了奖励和折扣：

$$(S, P, R, \gamma)$$

其中 $R$ 是奖励函数，$\gamma \in [0,1]$ 是折扣因子。压缩地说：MRP = MP + 奖励 + 折扣。

有了奖励，模型终于能够问出一个纯粹的马尔可夫过程问不出的问题：从状态 $s$ 出发，我们应该期望获得多少长期奖励？ 要精确回答这个问题，还需要两样新的工具，折扣回报和价值函数，内容足够多，值得单独用一章来处理。就目前而言，重要的结构性事实要窄一些：一个 MRP 仍然没有智能体的动作。系统仍然按照 $P(s' \mid s)$ 转移，和纯粹的马尔可夫过程完全一样；奖励只是叠加在一个没有任何东西在操控的转移过程之上的旁白。

第三级：加入控制

最后一级阶梯，是把一个被动演化、带有打分的系统，变成一个智能体真正可以在其中行动的东西。

定义马尔可夫决策过程

马尔可夫决策过程是在马尔可夫奖励过程的基础上加入了动作：

$$(S, A, P, R, \gamma)$$

其中 $A$ 是动作空间。压缩地说：MDP = MRP + 动作。

加入 $A$ 改变的是转移函数和奖励函数本身，而不只是它们的解释方式。在马尔可夫过程或马尔可夫奖励过程里，转移按照 $P(s' \mid s)$ 进行；而在马尔可夫决策过程里，转移按照

$$P(s' \mid s, a)$$

进行，奖励通常也写成 $R(s,a)$ 或 $R(s,a,s')$，而不再是 $R(s)$。未来不再只是世界自顾自地演化、附带一个滚动的分数；它是由智能体在每一步选择的动作塑造出来的。

这个改变有一个直接的后果，也正是这一级不只是”上一级多加一个字母”的原因。

命题动作迫使我们需要第二个价值函数

一旦动作存在，仅凭一个状态的价值就不足以比较不同动作了。我们需要两个价值函数：状态价值函数 $V^\pi(s)$，回答从状态 $s$ 出发、并遵循策略 $\pi$，我们应该期望获得多少长期回报？；以及动作价值函数 $Q^\pi(s,a)$，回答从状态 $s$ 出发、先采取动作 $a$、然后遵循 $\pi$，我们应该期望获得多少长期回报？

$V^\pi$ 与 $Q^\pi$ 之间的这个划分，以及把它们彼此、以及与奖励联系起来的那套递归 Bellman 方程，正是下一章的内容。本章就停在这个问题刚好能被精确地问出来的地方。

阶梯，压缩版

$$\underbrace{(S,P)}_{\text{MP：状态转移}} \ \xrightarrow{\ +\,\text{奖励},\ \gamma\ }\ \underbrace{(S,P,R,\gamma)}_{\text{MRP：状态转移 + 奖励}} \ \xrightarrow{\ +\,\text{动作}\ }\ \underbrace{(S,A,P,R,\gamma)}_{\text{MDP：状态转移 + 奖励 + 动作}}$$

模型	状态转移	奖励	动作
马尔可夫过程（MP）	有，$P(s' \mid s)$	无	无
马尔可夫奖励过程（MRP）	有，$P(s' \mid s)$	有，$R$，按 $\gamma$ 折扣	无
马尔可夫决策过程（MDP）	有，$P(s' \mid s,a)$	有，$R(s,a)$	有，$A$

用大白话说：MP 是一个自己演化的世界。MRP 是一个自己演化、但每一步都带着一个分数的世界。MDP 是一个智能体选择动作、世界做出响应、每一步仍然带着分数的世界。强化学习，在几乎所有经典表述里，研究的都是：一旦你站在这架阶梯的顶端，接下来该怎么做。

这架阶梯不仅要会往上爬，也要会往下走。后面几章会反复地、有意地把 MDP 打回下面一级：固定一个策略 $\pi$、把动作平均掉，MDP 就退化成它诱导出的那个 MRP。正是这个手法，让策略评估不是一个新问题，而是一个早就解决过的问题。

参考资料

• Datawhale Easy RL 第二章