🏠 总目录📚 本教程 02 · MDP ← →

02 · MDP:把问题写成数学

怎样用 MDP 描述决策环境,再从一步转移算到多步和长期?

  1. 建模:五元组与马尔可夫性质
  2. 算分布:一步、两步与长期
  3. 做决策:奖励、策略与建模检查

一句话 用 MDP 描述状态、动作和奖励,固定同一转移矩阵后可逐步算状态分布,而有限且不可约、非周期时,任意初始分布都会收敛到唯一平稳分布。

读完会做:写五元组、算两步概率、判长期极限。

前置:状态、动作和奖励,条件概率的乘加。

📑 本页目录(点开跳转)

智能体和环境怎样交互

马尔可夫决策过程(Markov decision process,MDP)是强化学习常用的数学模型。下图沿两个方向读:智能体选动作,环境给出下一状态和奖励。

智能体 Agentπ(a | s) ← 你要学的环境 EnvironmentP(s' | s,a)动作 a状态 s′、奖励 r奖励只说「结果好不好」,不说「该做什么」—— 这就是它和监督学习的根本区别
环境返回状态和奖励,智能体据此继续决策。

📦 一、MDP 的五元组

$$\text{MDP} = \langle \mathcal{S},\ \mathcal{A},\ P,\ R,\ \gamma \rangle$$

符号 名字 是什么
$\mathcal{S}$ 状态空间 所有可能局面的集合
$\mathcal{A}$ 动作空间 所有可能动作的集合
$P(s'\mid s,a)$ 转移概率 在 s 做 a,到 s' 的概率 ⭐
$R(s,a)$ 奖励函数 在 s 做 a 得到的(期望)奖励
$\gamma$ 折扣因子 未来奖励打多少折

这五项分别回答有哪些局面、能做什么、会到哪里、给多少分、未来给的分要打多少折。

动作相同,转移结果仍可随机

同一动作下达「前进 1 米」,地面打滑时可能只走了 0.8 米。推荐同一件商品时,用户可能买也可能划走。语言模型在生成 token 时也可以随机抽样。


二、马尔可夫性质

给定当前状态和动作,下一状态的概率与更早的历史无关。依据 Sutton 与 Barto §3.1。

$$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)$$

把影响下一步的历史信息纳入状态,就可以用同一条条件概率规则推进。

状态设计:把转移需要的信息放进状态

国际象棋中,完整局面要包括棋子位置和行棋方,还要保留会影响后续规则的信息,例如王车易位权。依据 FIDE 规则 3.8.2.1。乒乓球游戏里只看当前一帧,可能看不出球正在上升还是下落。连续帧能帮助估计速度,堆叠最近 4 帧是一种做法。建模时还要检查是否有其他会影响未来的信息。

三种场景怎样补信息

场景 ❌ 差的状态 ✅ 好的状态
Atari 游戏 当前 1 帧 最近 4 帧堆叠(能看出速度)
推荐系统 当前用户画像 画像 + 最近 N 次交互序列 ⭐
对话/RLHF 最后一句话 完整对话历史(即上下文) ⭐

在逐 token 生成的简化模型中,可以把当前可用的上下文作为状态。截断会丢掉可能影响下一步的信息。智能体工程第 4 章讨论怎样管理这些信息。

只用一步规则,怎么算到多步和长期?

假设一个设备只有状态 A 和 B,每个状态只有一个动作,转移规则每步相同。现在确定在 A。一步到 A 的概率是 0.8,两步后仍在 A 的概率该怎么算?下面用马尔可夫链(Markov chain)来追踪状态随步数变化的概率。这里每个状态只有一个动作,当前状态就足以决定下一步的概率,暂时也无需计算奖励。有多个动作时,可固定同一套只依赖当前状态的动作策略,再把各动作的转移概率按选择概率加权,得到固定的状态转移矩阵。

一步:矩阵的行是当前状态,列是下一状态

把演示用的四个概率排成一步转移矩阵(transition matrix)$P$。约定状态顺序始终是 A、B。记 $P_{ij}$ 为当前在 $i$ 时下一步到 $j$ 的概率,$i,j$ 都可以是 A 或 B。

一步转移矩阵 P
当前\下一步到 A到 B
从 A0.80.2
从 B0.30.7

每个元素都是 0 到 1 之间的概率,没有单位。从每个起点出发,下一步一定落在 A、B 之一,所以两行分别满足 $0.8+0.2=1$、$0.3+0.7=1$。这种每行概率加起来等于 1 的矩阵叫行随机矩阵(row-stochastic matrix)。

用状态分布行向量 $\mu_t=(\Pr(S_t=A),\Pr(S_t=B))$ 表示走了 $t$ 步后各状态的概率,$S_t$ 是第 $t$ 步的状态,$t=0,1,2,\ldots$。$\pi(a\mid s)$ 回答在状态 $s$ 选动作 $a$ 的概率,$\mu_t$ 回答第 $t$ 步在哪个状态的概率。 本例从 A 出发,$\mu_0=(1,0)$。第一步沿 A 那一行得到 $\mu_1=(0.8,0.2)$。

两步:沿路径相乘,按中间状态相加

第二步可以从 A 或 B 开始。先用第一步到达中间状态的概率,乘以从该状态走到终点的条件概率,再把互斥路径的概率加起来。可以回看贝叶斯网络 17 的分支乘加。表中只求「从 A 出发,两步后到 A」,所以第二步始终读 P 的「到 A」列。

用路径乘积算两步返回概率
路径第一步 × 第二步路径概率
A → A → A0.8 × 0.80.64
A → B → A0.2 × 0.30.06
两条互斥路径相加0.70
第二段的概率要沿中间状态所在行取值。依据 Gallager §3.3。

两步后只可能在 A 或 B,到 B 的概率是 $1-0.70=0.30$。从 A 出发,两步状态分布为 $(0.70,0.30)$。

写成矩阵乘法时,$\mu_t$ 的一行分别乘 P 的两列,每一列都做同样的乘加。用 $\mu_t(i)$ 表示状态 $i$ 的分量,终点 $j$ 的分量是:

$$\mu_{t+1}(j)=\mu_t(A)P_{Aj}+\mu_t(B)P_{Bj}, \qquad \mu_{t+1}=\mu_t P.$$

连续两步就先乘一次 P,再乘一次 P,即 $\mu_2=(\mu_0P)P=\mu_0P^2$。$P^2=PP$ 是矩阵乘矩阵,每个 $(i,j)$ 位置把从 $i$ 经各中间状态到 $j$ 的两步概率加起来。这一步用的是行乘列的乘加规则。

平稳:找再走一步也保持原样的分布

如果某个概率分配更新一次还原样,就能用同一条更新规则反复保持。这叫平稳分布(stationary distribution),记为 $\mu_*$,星号标识固定点。它的两个分量非负、相加等于 1,并满足 $\mu_*=\mu_*P$。每个个体仍可从 A 去 B 或从 B 去 A。

设平稳时在 A 的概率为 $p$。总概率为 1,所以在 B 的概率是 $1-p$。把这两个概率和 P 的 A 列代入,要求更新后的 A 概率仍然等于 $p$:

$$\begin{aligned} p &= 0.8p+0.3(1-p) \\ &= 0.3+0.5p \\ 0.5p &= 0.3 \\ p &= 0.6,\quad 1-p=0.4. \end{aligned}$$

检查 B 列:$0.6\times0.2+0.4\times0.7=0.12+0.28=0.40$。这张矩阵的平稳分布为 $(0.6,0.4)$。 依据 Gallager §3.3.3。

收敛:任意起点是否都越来越接近平稳分布?

设 $p_t$ 是第 $t$ 步在 A 的概率。从某个初始分布出发,如果各状态的概率随步数增加逐渐趋向各自的平稳值,就说分布收敛(convergence)到平稳分布。上面的更新给出 $p_{t+1}=0.3+0.5p_t$。平稳值本身也满足这条更新,即 $0.6=0.3+0.5\times 0.6$。两式相减,就能直接看出每步怎样缩小偏差:

$$\begin{aligned} p_{t+1}-0.6 &=(0.3+0.5p_t)-(0.3+0.5\times0.6)\\ &=0.5p_t-0.5\times0.6\\ &=0.5(p_t-0.6). \end{aligned}$$

所以第 $t$ 步的偏差是 $0.5^t(p_0-0.6)$,也就是初始偏差连续乘 $t$ 次 0.5。比如从 A 出发,A 的概率依次是 $1\to0.8\to0.70$,相对 0.6 的偏差是 $0.4\to0.2\to0.1$。任意 $p_0$ 都在 0 到 1 之间,$0.5^t$ 越乘越小并趋于 0,故 $p_t$ 趋于 0.6,B 的概率随之趋于 0.4。

一般情况下,固定转移矩阵的有限链若不可约且非周期,从任意初始分布都收敛到唯一平稳分布。 这是充分条件。不可约(irreducible)指任意两个状态能沿正概率路径互相到达。非周期(aperiodic)指正概率回到同一状态的所有正整数步数的最大公约数为 1。例如上面的 P 可以在 A、B 之间互相到达,而且 A 可以一步留在自己。在不可约链中,各状态周期相同,所以发现一个可以一步返回自己的状态(称为自环)就足以判断整条链非周期。依据 Gallager §§3.2–3.3。

再试一张固定矩阵:从 A 必到 B;从 B 到 A 和留在 B 各占 $1/2$。两状态互相可达,B 可以一步留在自己。现在更新为 $p_{t+1}=0\cdot p_t+\tfrac12(1-p_t)$。从 A 出发有 $p_1=0,\ p_2=\tfrac12,\ p_3=\tfrac14$,每步 B 的概率用 1 减去 A 的概率。平稳时 $p=\tfrac12(1-p)$,所以 $3p=1$,得到 $(\tfrac13,\tfrac23)$。

把第二张矩阵的 B 自环去掉,再将 B 行的剩余概率从 $1/2$ 归一到 1。这样每一步交换 A 和 B 的概率,更新就是 $p_{t+1}=1-p_t$。令 $p=1-p$,得到平稳分布 $(\tfrac12,\tfrac12)$。从 A 出发只在偶数步回到 A,周期是 2。交替链有平稳分布 $(1/2,1/2)$,但从 A 出发会在 $(1,0)$ 和 $(0,1)$ 间一直交替。

两张矩阵与分布对照(列顺序 A、B)
从 A 出发保留 B 自环去掉 B 自环
P 的 A 行(0, 1)(0, 1)
P 的 B 行(1/2, 1/2)(1, 0)
第 1 步(0, 1)(0, 1)
第 2 步(1/2, 1/2)(1, 0)
第 3 步(1/4, 3/4)(0, 1)
平稳分布(1/3, 2/3)(1/2, 1/2)
长期变化收敛到平稳分布在奇偶步交替

代码验证:逐步乘矩阵,并把平稳分布再乘一次

把下面的 Python 代码保存后直接运行,只用标准库。数据是上面三张演示矩阵,没有抽样、训练或随机种子。step 实现“行乘列”并检查概率和。trace 从 A 逐步更新。最后逐一核对路径乘积、演算过的分布和平稳方程,输出用分数保留精确值。

from fractions import Fraction as F

def step(distribution, matrix):
    assert all(value >= 0 for row in matrix for value in row)
    assert all(sum(row) == 1 for row in matrix)
    next_distribution = tuple(
        sum(distribution[i] * matrix[i][j] for i in range(2))
        for j in range(2)
    )
    assert all(value >= 0 for value in next_distribution)
    assert sum(next_distribution) == 1
    return next_distribution

def trace(matrix, steps):
    distribution = (F(1), F(0))
    results = []
    for _ in range(steps):
        distribution = step(distribution, matrix)
        results.append(distribution)
    return results

main = ((F("0.8"), F("0.2")), (F("0.3"), F("0.7")))
with_loop = ((F(0), F(1)), (F(1, 2), F(1, 2)))
alternating = ((F(0), F(1)), (F(1), F(0)))

back_paths = tuple(main[0][k] * main[k][0] for k in range(2))
other_paths = tuple(main[0][k] * main[k][1] for k in range(2))
assert back_paths == (F("0.64"), F("0.06"))
assert other_paths == (F("0.16"), F("0.14"))
assert (sum(back_paths), sum(other_paths)) == (F("0.70"), F("0.30"))

main_steps = trace(main, 2)
assert main_steps == [(F("0.8"), F("0.2")), (F("0.70"), F("0.30"))]
errors = [F(1) - F("0.6")] + [row[0] - F("0.6") for row in main_steps]
assert errors == [F("0.4"), F("0.2"), F("0.1")]

loop_steps = trace(with_loop, 3)
assert loop_steps == [(0, 1), (F(1, 2), F(1, 2)), (F(1, 4), F(3, 4))]
alternating_steps = trace(alternating, 3)
assert alternating_steps == [(0, 1), (1, 0), (0, 1)]
for name, matrix, stationary, steps in (
    ("主例", main, (F(3, 5), F(2, 5)), main_steps),
    ("有 B 自环", with_loop, (F(1, 3), F(2, 3)), loop_steps),
    ("交替链", alternating, (F(1, 2), F(1, 2)), alternating_steps),
):
    assert step(stationary, matrix) == stationary
    distributions = " → ".join(f"({a}, {b})" for a, b in steps)
    print(f"{name}: {distributions} | 平稳分布 ({stationary[0]}, {stationary[1]})")

预期输出:主例 $(4/5,1/5)\to(7/10,3/10)$,平稳分布 $(3/5,2/5)$。有 B 自环时 $(0,1)\to(1/2,1/2)\to(1/4,3/4)$,平稳分布 $(1/3,2/3)$。交替链 $(0,1)\to(1,0)\to(0,1)$,平稳分布 $(1/2,1/2)$。有限步的输出核对算例。长期判断用上面的递推或收敛条件。


三、学生的一天:查转移和奖励

状态有上课、刷手机和睡觉(终止)。可选动作有学、玩。

转移与奖励:

状态 动作 到哪(转移概率) 奖励
上课 学 上课 (0.8) / 睡觉 (0.2) +2
上课 玩 刷手机 (1.0) +1
刷手机 学 上课 (0.6) / 刷手机 (0.4) -1
刷手机 玩 刷手机 (0.9) / 睡觉 (0.1) +1

刷手机时,玩给 +1 并有 0.9 的概率继续刷,学给 −1 但有 0.6 的概率去上课。如果低分动作能带你去更好的状态,它的长期回报可能更高。 眼前分数与未来能去的状态,是比较动作时的两笔账。

第 4 章会用这个 MDP 求最优策略。


四、策略给出各动作的选择概率

$$\pi(a\mid s) = \text{在状态 } s \text{ 下选动作 } a \text{ 的概率}$$

类型 含义 例子
确定性策略 每个状态只输出一个动作 π(上课) = 学
随机策略 ⭐ 输出一个概率分布 π(学|上课)=0.7, π(玩|上课)=0.3

随机策略支持探索和策略梯度

随机选择可以用来探索(第 7 章)。给动作概率使用可微的参数化,就能用梯度更新策略(第 9 章)。直接对选取最大项的 argmax 求梯度,无法获得这种更新信号。

有些博弈的最优策略也需要随机化,例如石头剪刀布。这里的随机策略梯度依赖动作概率对参数可微。


五、MDP 的几个变体

变体 差别 典型场景
POMDP(部分可观测) 看不到完整状态,只看到观测 o 扑克(看不到对手的牌)、真实机器人
多臂老虎机 只有一个状态,退化成纯探索利用问题 ⭐ 推荐、广告、A/B 测试
上下文老虎机 有状态但动作不影响下一状态 推荐(推什么不改变用户是谁)⭐
连续 MDP 状态/动作是连续的 机器人控制、自动驾驶

动作改变未来状态时,需要考虑多步影响。 推荐算法第 13 章用 Thompson Sampling 处理上下文老虎机的探索。长期推荐也可能改变用户兴趣,推荐算法挑战 B展示了这种状态演化。


六、检查状态、奖励稀疏与奖励漏洞

错误 后果 正确做法
状态里漏了关键信息 马尔可夫性破坏,怎么学都学不好 ⭐ 问自己:「只看这个状态,我能做出好决策吗?」
奖励设计得太稀疏 只在最后给 +1,中间全是 0 → 几乎学不动 加中间奖励(reward shaping),但小心引入偏差
把「想要的结果」写成奖励,而不是「想要的行为」 奖励黑客(第 1 章那个赛艇) 想清楚:优化到极致会发生什么?

每回合独立且成功概率为 0.001 时,平均要 1000 回合才第一次见到非零奖励。

例如迷宫只在到达终点时给 +1,其余为 0。随机探索很少到终点时,单靠非零回报给出的更新信号会很少。RLHF 的奖励模型可以给每段回答打分,比等到结束才给一次 0 或 1 更细。


七、和站内其他章的关系

相关的地方 这里的位置
语言模型的上下文窗口 逐 token 生成的简化模型中,可把当前可用上下文作为状态
智能体工程 04 上下文工程 状态设计的工程版
推荐算法 13 上下文老虎机(MDP 的退化情形)
推荐算法 挑战B 老虎机假设失效、变回真 MDP 的例子
第 1 章的五个零件 这一章给了它们精确定义
⭐ 博弈论与集体决策 09 · 正常形博弈 MDP 的一条隐藏前提:环境有随机性,但它没有偏好、不想赢你 —— 转移概率是写死的一张表,不会因为你学会了就偷偷改。⭐ 那一章讲的是这个前提失效之后的世界:对面也在最大化,你的「最优」一旦被看穿就不再最优。「我改进了所以收益变高」在那里不成立

检查点

  1. MDP 五元组分别是什么?
  2. 为什么转移 P 是概率而不是确定的?举两个例子。
  3. 马尔可夫性质说的是什么?乒乓球那个反例问题在哪、怎么修?
  4. 「马尔可夫性不是问题的属性」这句话什么意思?
  5. 语言模型的上下文窗口对应 MDP 里的什么?这解释了什么现象?
  6. 为什么深度强化学习常用随机策略而不是确定性策略?(说出关键的那一条)
  7. 上下文老虎机和完整 MDP 差在哪?推荐系统属于哪个?什么时候这个假设会失效?
  8. 奖励稀疏为什么要命?RLHF 怎么绕开的?
👀 答案
  1. ⟨S 状态空间, A 动作空间, P 转移概率, R 奖励函数, γ 折扣因子⟩。
  2. 因为世界有随机性。例:机器人下"前进1米"但地面打滑实际走0.8米;推荐了商品但用户可能买可能划走。
  3. 给定当前状态和动作,下一状态的概率与更早历史无关。乒乓球单帧缺少速度信息,加入连续帧能帮助判断球在上升还是下落。
  4. 马尔可夫性取决于你怎么定义状态。不满足时,把缺的信息塞进状态里就能恢复。
  5. 逐 token 生成的简化模型可以把当前可用上下文当作状态。截断可能移除会影响下一步的信息。
  6. 把动作概率参数化为可微函数,就能用梯度更新策略。直接对 argmax 求梯度无法获得这种更新信号。随机性还可用于探索,有些博弈也需要随机策略,如石头剪刀布。
  7. 上下文老虎机建模当轮收益,把上下文视为外部给定。若推荐只考虑当轮反馈,可以用这一模型和 Thompson Sampling 进行探索。若推荐会改变用户兴趣并影响后续反馈,就需要把状态演化纳入多步模型。
  8. 只在终点给 +1、各回合独立且成功概率为 0.001 时,平均 1000 回合才第一次见到非零奖励。RLHF 用奖励模型给每段回答打分,提供更细的信号。

动手算:换终点,再判断长期极限

  1. 主例从 A 出发,分别经 A 和 B,两步后到 B 的路径概率各是多少?把它们相加。
  2. 每步交换 A 和 B 时,从 A 出发,第 8 步和第 9 步的分布各是什么?能否把平稳分布当作这个起点的长期极限?在什么条件下可以把唯一的平稳分布当作任意起点的长期极限?
👀 答案
  1. A → A → B 的贡献为 $0.8\times0.2=0.16$,A → B → B 的贡献为 $0.2\times0.7=0.14$,合起来为 $0.30$。两个乘积的第二项都要查「到 B」列。
  2. 第 8 步为 $(1,0)$,第 9 步为 $(0,1)$。偶数步和奇数步一直不同,所以这个起点没有分布极限。从平稳分布 $(1/2,1/2)$ 起步则每一步都一样。固定的有限链若不可约且非周期,从任意起点都收敛到唯一平稳分布,此时才有这个结论的充分保证。

本节回顾

先记住这几件事

下一节仍然利用一步转移,进一步把即时奖励和未来的价值接起来。03 · 价值函数与贝尔曼方程

打卡记录保存在你的浏览器里,首页能看到总进度