外观
马尔可夫决策过程（MDP）
一句话定位：这一页讲清楚马尔可夫决策过程（Markov Decision Process, MDP）——它是几乎所有强化学习问题的统一数学语言；读完后你能把任意"顺序决策"问题写成 MDP 五元组，写出策略、价值函数和贝尔曼方程，并判断该走三条求解路线中的哪一条。
如果你还不确定"强化学习解决什么问题"，建议先看什么是强化学习；如果你在找术语定义，本页是术语表的"主词条页"。
一、为什么需要 MDP：顺序决策需要一门通用语言
人类和机器面对的大量问题不是"一张图分类"式的单步决策，而是一连串决策：
- 下棋：每一步落子影响后续所有局面；
- 自动驾驶：每秒几十次转向/刹车/变道决策，环环相扣；
- 对话：每一句话影响对方下一句；
- 机器人抓取：每一帧力矩决定最终能否抓住物体。
这类问题有一个共同结构：当前决策影响未来状态，未来状态影响未来决策。如果我们给每个问题都发明一套自己的描述方式，理论就无从谈起。MDP 的价值在于：用五个要素把"顺序决策"统一描述出来，然后所有算法——动态规划、Q-learning、PPO、SAC——都在同一门语言上工作。
text
┌────────────────────────────────────────────┐
│ MDP 五元组 │
│ │
│ (S, A, P, R, γ) │
│ ├─ S 状态集合 │
│ ├─ A 动作集合 │
│ ├─ P 状态转移概率 P(s'|s,a) │
│ ├─ R 奖励函数 R(s,a,s') │
│ └─ γ 折扣因子 γ ∈ [0,1) │
└────────────────────────────────────────────┘记忆口诀
"状态动作转移奖励折扣"——记住五个字母 S A P R γ，就记住了 MDP 的全部。
1. 五元组逐个拆解
| 要素 | 记号 | 含义 | 例子（CartPole 小车平衡） |
|---|---|---|---|
| 状态 S | $s \in \mathcal{S}$ | 智能体能观测到的一切对决策有用的信息 | 小车位置、速度、杆子角度、角速度（4 维连续向量） |
| 动作 A | $a \in \mathcal{A}$ | 每个状态下可选的操作 | 向左推 / 向右推（2 个离散动作） |
| 转移概率 P | $P(s' \mid s, a)$ | 在 s 做 a 后，下一状态 s' 出现的概率 | 推杆后杆子角度如何变化（由物理规律决定） |
| 奖励 R | $R(s, a, s')$ | 即时反馈信号，量化"这一步好不好" | 杆子还立着 = 0，倒下 = -1（或每步 +1） |
| 折扣因子 γ | $\gamma \in [0, 1)$ | 未来奖励相对现在奖励的贬值系数 | 0.99：看重 99 步以内的未来 |
注意 $P$ 是一个概率分布：对任意固定的 $(s,a)$，$\sum_{s'} P(s' \mid s,a) = 1$。它不是"下一步一定到哪个状态"，而是"下一步可能到各个状态的概率"。奖励 $R$ 既可能写成 $R(s,a,s')$（与到达的状态有关），也可能简化成 $R(s,a)$ 或 $R(s)$，不同教材记号略有差别，含义一致。
二、马尔可夫性质与状态表示
1. 马尔可夫性质
MDP 的灵魂是马尔可夫性质（Markov property）：
未来只依赖于当前状态和当前动作，与过去的历史无关。
写成概率形式：
$$ P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t) $$
也就是说，一旦给出 $s_t$，过去的所有历史都是多余的。这就像"鱼的记忆"：状态 $s_t$ 已经包含了做最优决策所需的全部信息，"它怎么走到这一步的"不重要。
2. "状态表示"是最容易被忽略的关键工程
马尔可夫性质不是白送的，它取决于你如何定义状态。现实中几乎没有一个问题天然满足马尔可夫性质，工程师通过状态设计来"制造"它：
| 问题 | 天真状态（不满足） | 好的状态（满足或近似满足） |
|---|---|---|
| 自动驾驶 | 单帧摄像头画面 | 多帧堆叠 + 自身速度 + 地图定位（因为单帧看不出物体速度） |
| 玩 Atari 游戏 | 单帧画面 | 最近 4 帧堆叠（因为单帧看不出球的速度） |
| 交易 | 当前价格 | 价格序列特征 + 持仓 + 仓位（因为单点价格不含趋势信息） |
| 对话 | 上一句话 | 完整对话历史（因为回答依赖上下文） |
常见坑：把"部分可观测"当成"马尔可夫"
大部分真实问题是 POMDP（部分可观测 MDP）：智能体看不到完整状态，只能看到观测 $o_t$。此时 $o_t$ 不满足马尔可夫性质，直接按 MDP 处理会决策失准。工程上的常用折衷：
- 把历史观测拼进状态（帧堆叠、对话历史、滑动窗口）；
- 用 RNN 压缩历史到隐状态；
- 承认近似，靠探索与泛化兜底。 学术界把 POMDP 当作独立领域，工业界大多数"够用"的解法是方案 1。
三、回报 G 与折扣因子 γ
1. 智能体的目标是最大化"回报"，而不是某一步奖励
单步奖励 $r_t$ 只是碎片。智能体的目标是对整条轨迹（trajectory）求累积回报（return），最常用的是折扣回报（discounted return）：
$$ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} $$
也可以写成递推形式（后面推导贝尔曼方程会反复用到）：
$$ G_t = r_{t+1} + \gamma G_{t+1} $$
2. 为什么 γ 必须小于 1
折扣因子有三个作用，缺一不可：
| γ 的作用 | 解释 |
|---|---|
| 数学收敛 | 若 γ<1 且奖励有界，无限和收敛；γ=1 时无限时域回报可能发散 |
| 刻画不确定性 | 未来越远越不确定，今天到手的 1 元比明天的 1 元更值钱（类比经济学"贴现"） |
| 调平衡 | γ 接近 1 时智能体"看得远"（如围棋 γ=1 也无妨，因为对局有终局）；γ 较小时智能体"急功近利" |
直觉例子：γ=0.9 时，10 步后的奖励只值现在的 $0.9^{10}\approx 0.35$ 倍；γ=0.99 时 10 步后还值 0.90 倍，100 步后 0.37 倍。"有效时域"约等于 $1/(1-\gamma)$：γ=0.99 意味着智能体大致考虑未来 100 步，γ=0.9 只考虑未来 10 步。
3. 两种回报：有限时域 vs 无限时域
- 分幕式（episodic）：任务有终止状态（game over、到达终点），$T$ 有限，回报是 $G_t = r_{t+1}+\gamma r_{t+2}+\cdots+\gamma^{T-t-1}r_T$。例如一盘棋、一轮对话。
- 持续式（continuing）：没有终止，$T=\infty$，靠 γ<1 保证收敛。例如实时控制、推荐系统。
分幕式任务可以看成持续式任务的特例：把终止状态设为一个"吸收状态"（进入后永远停留、奖励为 0），两者就统一了。
四、策略、状态价值 V 与动作价值 Q
1. 策略 π：智能体的"行为手册"
策略（policy） $\pi(a \mid s)$ 是从状态到动作概率的映射：在状态 $s$ 下采取动作 $a$ 的概率。它定义了智能体"怎么做"。
- 确定性策略：$\pi(s) = a$，每个状态只选一个动作；
- 随机策略：$\pi(a \mid s)$ 给出动作概率分布。
为什么要随机？两个原因：一是探索需要（总要尝试没走过的路）；二是不确定性下最优策略本身就是随机的（例如德州扑克中纯确定性策略会被对手针对，随机"诈唬"才最优）。
2. 状态价值函数 V
状态价值函数（state-value function） $V^\pi(s)$ 是"从状态 s 出发，按照策略 π 行动，往后能拿到的期望回报"：
$$ V^\pi(s) = \mathbb{E}\pi \left[ G_t \mid s_t = s \right] = \mathbb{E}\pi \left[ \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t = s \right] $$
注意两个关键点：
- 它是期望：未来有随机性（转移、策略本身随机），价值是平均意义下的；
- 它依赖策略：换一个策略，同一状态的价值就变了。所以 $V^\pi$ 也叫"策略 π 的表现"。
直觉：$V^\pi(s)$ 回答"如果我持续用这套打法，从当前位置出发平均能赢多少"。
3. 动作价值函数 Q
动作价值函数（action-value function） $Q^\pi(s,a)$ 是"从状态 s 出发，先执行动作 a，之后按照策略 π 行动"的期望回报：
$$ Q^\pi(s, a) = \mathbb{E}_\pi \left[ G_t \mid s_t = s, a_t = a \right] $$
两者的关系：
$$ V^\pi(s) = \sum_a \pi(a \mid s) , Q^\pi(s, a) $$
即状态价值 = 按策略概率对动作价值求加权平均。直觉：$Q$ 回答"这个动作值多少"，$V$ 回答"这个局面值多少"。
为什么工程师更常用 Q 而不是 V
V 只能告诉你"这个局面好不好"，无法直接告诉你"该怎么做"；Q 直接比较"这个动作 vs 那个动作"，可以从中导出策略（选 Q 最大的动作）。所以表格时代的 Q-learning 和深度时代的 DQN 都学 Q。而 V 在策略梯度/Actor-Critic 里作为 baseline 极有用——详见价值学习和Actor-Critic 家族。
五、贝尔曼方程：RL 的全部数学起点
1. 直觉：价值可以"拆成现在 + 未来"
贝尔曼方程（Bellman equation）说的是一件事：当前状态的价值 = 立即奖励 + 折扣后的下一状态价值。因为回报 $G_t = r_{t+1} + \gamma G_{t+1}$，两边同时取期望就得：
$$ V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V^\pi(s') \right] $$
逐项理解这个公式：
- $\sum_a \pi(a \mid s)$：策略说每个动作有概率，全部动作的价值按概率加权；
- $\sum_{s'} P(s' \mid s,a)$：环境可能转移到各个 $s'$，同样加权；
- $R(s,a,s') + \gamma V^\pi(s')$：本步奖励 + 折扣后的下一步价值。
动作价值版本同理：
$$ Q^\pi(s,a) = \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma \sum_{a'} \pi(a' \mid s') Q^\pi(s', a') \right] $$
2. 贝尔曼最优方程
定义最优价值函数 $V^*(s) = \max_\pi V^\pi(s)$，即"最优策略能拿到的最大价值"。最优策略满足：每个状态都选 Q 最大的动作。于是得到贝尔曼最优方程（Bellman optimality equation）：
$$ V^(s) = \max_a \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V^(s') \right] $$
$$ Q^(s,a) = \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma \max_{a'} Q^(s', a') \right] $$
直觉：贝尔曼最优方程把"找最优策略"变成了"解一组互相依赖的方程"。注意它把 $\sum_a \pi$ 换成了 $\max_a$——最优策略只在最优动作上有概率 1，其余为 0。
3. 为什么贝尔曼方程是"所有算法的基础"
几乎所有 RL 算法都是贝尔曼方程的某种变形或近似：
| 算法族 | 与贝尔曼方程的关系 |
|---|---|
| 值迭代 | 把贝尔曼最优方程当作迭代公式反复应用 |
| 策略迭代 | 用贝尔曼方程做策略评估 |
| TD / Q-learning | 用一次采样代替对 $s'$ 的求和（抽样版本的贝尔曼更新） |
| DQN | 用神经网络近似 $Q^*$，优化目标就是让预测满足贝尔曼方程（TD 误差） |
| 策略梯度 | 不需要显式满足贝尔曼方程，但仍把"回报"作为目标 |
贝尔曼方程需要模型 P 和 R？
写贝尔曼方程需要知道 $P(s'|s,a)$ 和 $R$。但 Q-learning、TD 这类算法不需要模型——它们用实际采样到的 $(s,a,r,s')$ 来"近似"公式中的求和。这正是"模型已知/未知"两种求解路线的分水岭，详见第七节。
六、一个网格世界小例子：把上面的符号全部落一遍
以 3×4 网格世界（Sutton & Barto 书中的经典示例）为例：
text
┌─────┬─────┬─────┬─────┐
│ s1 │ s2 │ s3 │ +1 │ +1 = 终点（正奖励）
├─────┼─────┼─────┼─────┤
│ s4 │ s5 │ s6 │ -1 │ -1 = 陷阱（负奖励）
├─────┼─────┼─────┼─────┤
│ s7 │ s8 │ s9 │ s10│ s7 = 起点
└─────┴─────┴─────┴─────┘- 状态：11 个格子（含终点与陷阱，陷阱后进入吸收态）；
- 动作：上、下、左、右；
- 关键设定：动作有噪声——你向上走，有 80% 概率真上去，10% 概率滑到左边，10% 滑到右边（碰到墙则原地不动）；
- 奖励：进入 +1 或 -1 格子给对应奖励，其余步骤奖励 0，γ=0.9；
- 终止：进入终点或陷阱后游戏结束。
1. 先算一个"无脑策略"的价值（策略评估）
假设"随机策略"：每个格子四方向等概率（各 25%）。我们来手算 $V^\pi(s)$。先看最靠近终点的格子 $s_3$：
$$V(s_3) = 0.25 \cdot \gamma V(终点) + 0.25 \cdot \gamma V(上面墙→原地 s_3) + \dots$$
由于最优策略下从 $s_3$ 向上走有 80% 概率直接到 +1，价值会明显高于其它格子。完整求解需要迭代（下面第 2 步的算法），这里只给直觉方向：离终点越近、路径越短的格子价值越高，邻近陷阱的格子价值被拉低。
2. 表格算法：价值迭代 3 步示意
价值迭代（value iteration） 就是把贝尔曼最优方程当迭代公式：
$$ V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V_k(s') \right] $$
初值 $V_0(s)=0$，迭代直到收敛：
| 迭代 | s7（起点） | s3（近终点） | s6（陷阱旁） | 说明 |
|---|---|---|---|---|
| k=0 | 0 | 0 | 0 | 全 0 起步 |
| k=1 | 0 | 0.8×1=0.8 | 0.8×(-1)=-0.8 | 一步可达的奖励开始"发光" |
| k=2 | ≈0.5 | ≈0.8 | ≈-0.8 | 信息向四周扩散 |
最终收敛后，策略为：在 $s_3$ 向上、$s_8$ 向上、$s_9$ 向左，形成绕开陷阱的安全路径。
价值迭代的直觉
每轮迭代，价值信息像水波一样从奖励源向外扩散一圈。k 轮迭代意味着智能体"看得见 k 步之内"的信息。这正是后面所有"自举（bootstrap）"算法的原型。
七、三种求解路线：从"知道模型"到"不知道模型"
贝尔曼最优方程给出了"答案"，但解它需要知道 $P$ 和 $R$——这在现实中几乎永远拿不到。于是 RL 演化出三条求解路线：
text
┌─────────────────────────────┐
│ 已知 P, R（有模型） │
│ 动态规划 DP │
│ 策略迭代 / 值迭代 │
└──────────────┬──────────────┘
│ 实际中拿不到模型
┌──────────────────────────┴───────────────┐
│ 未知模型，但有交互能力 │
│ 从样本学习（无模型） │
│ ├── 蒙特卡洛 MC：整条轨迹结束后学 │
│ └── 时序差分 TD：每步都学（Q-learning） │
└──────────────────────────┬───────────────┘
│ 状态空间太大/连续
┌──────────────────────────┴───────────────┐
│ 函数近似 / 深度 RL │
│ DQN / PPO / SAC（神经网络当价值或策略） │
└──────────────────────────────────────────┘| 路线 | 需要什么 | 优点 | 缺点 | 代表方法 |
|---|---|---|---|---|
| 动态规划 | 完整模型 P、R | 有理论保证、精确 | 现实中模型几乎没有；状态空间大时不可行 | 策略迭代、值迭代 |
| 蒙特卡洛 | 与环境交互采完整轨迹 | 无模型、无偏 | 方差大、必须等到回合结束 | First-visit MC |
| 时序差分 TD | 与环境交互、逐步入步更新 | 无模型、低方差、在线 | 有偏（依赖初始估值） | TD(0)、Q-learning、SARSA |
| 深度 RL | 无模型 + 神经网络 | 处理连续/高维状态 | 样本效率低、不稳定、难调 | DQN、PPO、SAC |
本手册的内容组织
三条路线正好对应本模块的主线：动态规划与 TD 是价值学习的前半部分；直接学策略见策略梯度方法；想把"环境模型"也学出来用，见基于模型的 RL 与世界模型；数学背景查数学基础速查。
八、MDP 的常见误区与坑（面试高频）
坑 1：把"回报"和"单步奖励"搞混
目标函数是期望折扣回报 $\mathbb{E}[G_t]$，不是单步奖励。奖励是"信号"，回报才是"目标"。奖励设计得再好，若定义错了回报（如 γ=0），智能体就会变短视。
坑 2：以为马尔可夫性质是环境的属性
马尔可夫性质是"状态表示"的属性，不是环境本身的属性。同样的物理过程，单帧观测不满足、四帧堆叠满足。状态设计 = 建模工作。
坑 3：贝尔曼方程默认模型已知
贝尔曼最优方程里写的是 $P(s'|s,a)$ 的显式求和。很多初学者在推导 TD 时困惑"为什么 Q-learning 没有模型"——因为 Q-learning 把求和换成了单次采样 $r + \gamma \max Q(s',a')$，期望上等价，细节见价值学习。
坑 4：V 与 Q 混用
V 不含动作、Q 含动作；$\max_a Q^(s,a) = V^(s)$。工程师选 Q 直接出策略；科研论文里 V 常作 baseline。写公式前先问自己"这页纸学的是 V 还是 Q"。
坑 5：γ 拍脑袋
γ 是超参数。γ 太大 → 方差大、收敛慢、对远期奖励敏感；γ 太小 → 短视、学不到长期策略。通常按"有效时域 ≈ 1/(1-γ)"反推：任务关键决策跨 50 步 → γ ≈ 0.98~0.99。
九、与本站其他页面的关系
MDP 是本站的根节点：
text
┌─────────────────┐
│ MDP（本页） │
└────────┬────────┘
┌─────────────────┼──────────────────┐
▼ ▼ ▼
┌─────────────┐ ┌─────────────┐ ┌────────────────┐
│ 价值学习 │ │ 策略梯度 │ │ 基于模型的 RL │
│ 学 Q 再导策略 │ │ 直接学策略 │ │ 学环境再规划 │
└─────────────┘ └─────────────┘ └────────────────┘
│ │ │
└────────────┬────┘ │
▼ ▼
┌─────────────────┐ ┌───────────────┐
│ Actor-Critic │ │ RLHF / 离线 RL │
│ 两条路线合流 │ │ 把 MDP 用到 │
└─────────────────┘ │ 真实世界 │
└───────────────┘- 没理解 MDP，后面 11 个概念页都是空中楼阁；理解了本页，价值学习只是"把贝尔曼方程用神经网络近似"；
- 策略梯度方法换了一个角度：不学价值、直接优化策略的参数；
- 基于模型的 RL 与世界模型显式去学 $P$ 和 $R$；
- 数学背景不足时先补数学基础速查：期望、条件期望、马尔可夫链都与本页直接相关；
- 名词记不牢随时回术语表。
延伸阅读
- 什么是强化学习 —— 智能体-环境循环、奖励假设与最小例子，MDP 的入门前置
- 价值学习：从动态规划到 DQN —— 贝尔曼方程落地为策略迭代、Q-learning 与 DQN 的完整路径
- 策略梯度方法 —— 不学价值、直接学策略的另一条主线
- 基于模型的 RL 与世界模型 —— 显式学习 P 与 R，再用它们做规划
- 数学基础速查 —— 期望、条件期望、马尔可夫链与动态规划原理
- 术语表 —— 60+ RL 词条速查
参考资料
- Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. 第 3 章（MDP 与价值函数）、第 4 章（动态规划）、第 17 章（POMDP 简介）。官方免费版：http://incompleteideas.net/book/the-book-2nd.html
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. 贝尔曼方程与最优性原理的原始出处。
- Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. 数学化、严格的 MDP 教材。
- Silver, D. (2015). UCL Course on RL（Lecture 1-3）：MDP、DP 的精讲，公开课件：https://www.davidsilver.uk/teaching/