马尔可夫决策过程（Markov Decision Process，简称 MDP）是强化学习的核心数学框架。几乎所有的强化学习问题都可以形式化为 MDP——从围棋对弈到机器人控制，从自动驾驶到推荐系统。MDP 提供了一个优雅而强大的方法来描述智能体在不确定环境中通过一系列决策达成长期目标的问题。
一个马尔可夫决策过程由五元组 (S,A,P,R,γ) 正式定义：
| 符号 |
名称 |
含义 |
取值范围/说明 |
| S |
状态空间 |
环境所有可能状态的集合 |
可以是有限集或无限集 |
| A |
动作空间 |
智能体可选动作的集合 |
可以是离散或连续 |
| P |
状态转移概率 |
P(s′∣s,a) 表示在状态 s 执行动作 a 后转移到 s′ 的概率 |
∑s′∈SP(s′∣s,a)=1 |
| R |
奖励函数 |
R(s,a,s′) 表示转移后获得的即时奖励 |
通常为有界实数 |
| γ |
折扣因子 |
平衡即时奖励与未来奖励的重要性 |
γ∈[0,1) |
智能体与环境的交互是一个循环过程：
- 环境处于状态 st∈S
- 智能体选择动作 at∈A
- 环境根据转移概率 P(st+1∣st,at) 进入新状态 st+1
- 智能体获得即时奖励 rt=R(st,at,st+1)
- 重复步骤 1-4
这个过程可以用时序图表示：
时间 t: s₀ ──a₀──→ 环境 ──→ s₁, r₀ ──a₁──→ 环境 ──→ s₂, r₁ ...
↑ ↑
根据 P(s₁|s₀,a₀) 根据 P(s₂|s₁,a₁)
MDP 的核心假设是马尔可夫性：未来状态只依赖于当前状态和当前动作，与历史无关。数学表达式为：
P(st+1∣st,at,st−1,at−1,…,s0,a0)=P(st+1∣st,at)
这意味着当前状态 st 已经"充分统计"了历史信息。这个假设看似严格，但在实践中通过巧妙设计状态表示（比如将过去 N 帧图像作为状态）可以很好地满足。
为了直观理解 MDP，我们考虑一个经典的冰湖行走（FrozenLake） 问题。
一个 4×4 的网格，智能体从左上角出发，目标是到达右下角的终点。网格中有一些冰面（可安全行走）和冰窟窿（掉入则失败）。
S ⬜ ⬜ ⬜ S = 起点
⬜ 🕳 ⬜ 🕳 🕳 = 冰窟窿（失败）
⬜ ⬜ ⬜ 🕳 ⬜ = 冰面（安全）
🕳 ⬜ ⬜ G G = 终点（目标）
-
状态空间 S：16 个格子，编号 0-15
- s=0: 起点（左上角）
- s=15: 终点（右下角）
- s=5,7,11,12: 冰窟窿（终止状态）
-
动作空间 A：{上, 下, 左, 右}
-
转移概率 P（关键特点：冰面湿滑）：
- 意图方向：概率 1/3
- 垂直方向：各有概率 1/3
- 例如：意图"向上"，实际有 1/3 概率向上，1/3 向左，1/3 向右
-
奖励函数 R：
- 到达终点 G：R=+1
- 其他所有转移：R=0
-
折扣因子 γ=0.9
从状态 s=6（第1行第2列，冰面）执行动作"向右"：
| 实际方向 |
概率 |
目标状态 |
是否终止 |
| 向右（意图） |
1/3 |
s=7（冰窟窿） |
终止 |
| 向上 |
1/3 |
s=2（冰面） |
否 |
| 向下 |
1/3 |
s=10（冰面） |
否 |
这个"湿滑冰面"的设定意味着智能体不能完全控制自己的移动——这正是 MDP 中随机性的典型体现。
智能体与环境交互产生的一条轨迹（Trajectory）是状态-动作-奖励的有序序列：
τ=(s0,a0,r0,s1,a1,r1,…,sT)
对应的累计回报（Return）是折扣奖励之和：
Gt=rt+γrt+1+γ2rt+2+⋯=k=0∑∞γkrt+k
数值示例：假设一条轨迹的即时奖励序列为 [0,0,0,0,1]，γ=0.9：
G0=0+0.9×0+0.92×0+0.93×0+0.94×1=0.94=0.6561
如果改为 γ=0.5，则 G0=0.54×1=0.0625——可见折扣因子对长期目标的重要性有决定性影响。
策略（Policy）告诉智能体在某个状态下应该做什么。有两种形式：
| 类型 |
记法 |
含义 |
示例 |
| 确定性策略 |
π(s)=a |
每个状态映射到一个动作 |
π(s=6)=右 |
| 随机性策略 |
π(a∣s)=Pr[At=a∣St=s] |
每个状态上动作的概率分布 |
π(右∣s=6)=0.5 |
状态价值函数 Vπ(s) 是从状态 s 开始，遵循策略 π 所能获得的期望回报：
Vπ(s)=Eπ[Gt∣St=s]=Eπ[k=0∑∞γkrt+k∣St=s]
动作价值函数 Qπ(s,a) 是从状态 s 执行动作 a 后，再遵循策略 π 的期望回报：
Qπ(s,a)=Eπ[Gt∣St=s,At=a]
二者之间的关系：
Vπ(s)=a∈A∑π(a∣s)Qπ(s,a)
数值示例：在冰湖问题中，如果策略是"在每个状态等概率随机选择动作"，那么 Vπ(s=0) 的计算会涉及从起点出发所有可能的随机轨迹的期望。我们会在贝尔曼方程部分展示具体计算。
贝尔曼方程是 MDP 理论的核心，它给出了价值函数的递归关系。
Vπ(s)=a∑π(a∣s)s′,r∑P(s′∣s,a)[r+γVπ(s′)]
这个方程可以理解为：
Vπ(s)=考虑所有动作a∑策略概率π(a∣s)考虑所有可能的s′,r∑下一状态P(s′∣s,a)[r+γVπ(s′)]
Qπ(s,a)=s′,r∑P(s′∣s,a)[r+γa′∑π(a′∣s′)Qπ(s′,a′)]
对于最优策略 π∗，对应的最优价值函数满足：
V∗(s)=amaxs′,r∑P(s′∣s,a)[r+γV∗(s′)]
Q∗(s,a)=s′,r∑P(s′∣s,a)[r+γa′maxQ∗(s′,a′)]
考虑一个简化版 MDP：只有 3 个状态 {s0,s1,s2}，1 个动作，转移和奖励如下：
| 当前状态 |
下一个状态 |
概率 |
奖励 |
| s0 |
s1 |
0.5 |
0 |
| s0 |
s2 |
0.5 |
0 |
| s1 |
s2 |
1.0 |
1 |
| s2 |
s2 |
1.0 |
0 |
设 γ=0.9，策略全部为等概率单一动作。
迭代过程 （初始 V0(s)=0）：
| 迭代 |
V(s0) |
V(s1) |
V(s2) |
计算过程 |
| 0 |
0 |
0 |
0 |
- |
| 1 |
0 |
1 |
0 |
V(s1)=1+0.9×0=1 |
| 2 |
0.45 |
1 |
0 |
V(s0)=0.5(0+0)+0.5(0+0)=0 ❌ 等等 |
| 2 |
0.45 |
1 |
0 |
V(s0)=0.5(0+0.9×1)+0.5(0+0.9×0)=0.5×0.9=0.45 |
| 3 |
0.45 |
1 |
0 |
已收敛（s1,s2 无变化，s0→s1→s2 路径已稳定） |
最终收敛结果：V∗(s0)=0.45，V∗(s1)=1，V∗(s2)=0。
这个简单的三状态例子展示了贝尔曼方程如何通过自洽递归来计算长期期望回报。
| 特征 |
马尔可夫链 |
马尔可夫决策过程 |
| 控制输入 |
无 |
有（动作/决策） |
| 转移概率 |
P(s′∣s) |
P(s′∣s,a) |
| 奖励信号 |
无 |
有 |
| 目标 |
分析稳态分布 |
最大化累计奖励 |
| 应用 |
网页排名（PageRank） |
强化学习、最优控制 |
可以这样理解：马尔可夫链是"观察者"视角，MDP 是"参与者"视角——前者被动观察随机过程，后者主动做出决策影响过程。
| 特征 |
MDP |
POMDP |
| 状态观察 |
完全可观察 |
部分可观察 |
| 智能体知道 |
当前真实状态 |
观察值（含噪声） |
| 最优策略形式 |
π(s) |
π(b)（信念状态 b） |
| 计算复杂度 |
多项式时间 |
PSPACE-hard |
| 典型应用 |
棋盘游戏、机器人导航 |
自动驾驶、疾病诊断 |
POMDP 增加了观测函数 O(o∣s′,a)，描述在状态 s′ 和动作 a 下获得观测 o 的概率。由于需要考虑信念状态的更新，POMDP 的求解复杂度远高于 MDP。
随机过程
├── 马尔可夫链（无控制、无奖励）
│ └── 隐马尔可夫模型 HMM（不可观察状态）
└── 马尔可夫决策过程 MDP（有控制、有奖励）
├── 完全可观察 → MDP
├── 部分可观察 → POMDP
└── 连续状态 → CMDP（连续 MDP）
值迭代通过反复应用贝尔曼最优方程来逼近最优价值函数：
Vk+1(s)=amaxs′,r∑P(s′∣s,a)[r+γVk(s′)]
当 ∥Vk+1−Vk∥<ϵ 时停止迭代，然后从收敛的 V∗ 中提取最优策略：
π∗(s)=argamaxs′,r∑P(s′∣s,a)[r+γV∗(s′)]
策略迭代通过"评估-改进"的循环找到最优策略：
- 策略评估：给定策略 π，求解 Vπ（可通过迭代或直接求解线性方程组）
- 策略改进：基于 Vπ 更新策略：
π′(s)=argamaxs′,r∑P(s′∣s,a)[r+γVπ(s′)]
- 重复直到策略不再变化
| 方面 |
值迭代 |
策略迭代 |
| 迭代对象 |
价值函数 |
策略 |
| 收敛指标 |
价值函数变化 < ϵ |
策略不再变化 |
| 迭代次数 |
多（但每次计算快） |
少（但每次评估慢） |
| 收敛速度 |
线性（γ 决定） |
多项式（通常更快） |
| 适用场景 |
大规模状态空间 |
中小规模状态空间 |
| 典型实现 |
O(∣S∣2∣A∣) 每次迭代 |
O(∣S∣3) 每次策略评估 |
对于冰湖问题，我们进行 3 轮值迭代来感受收敛过程（简化版，仅展示部分关键状态）：
初始：V0(s)=0 对所有 s
第1轮：
只考虑一步奖励：只有到达终点 s=15 的状态（s=14 向下）得到 V1(14)≈1/3×1=0.33，其他状态 V1=0
第2轮（部分状态）：
| 状态 |
V2 计算 |
结果 |
| s=14 |
max 动作"向下" = (1/3)(1+0)+(2/3)(0+0) |
0.33 |
| s=10 |
动作"向右" = (1/3)(0+0.9×0.33)+(2/3)(0+0) |
0.10 |
| s=13 |
动作"向下" = (1/3)(0+0.9×0.33)+(2/3)(0+0) |
0.10 |
第3轮：
价值从终点逐渐向起点"传播"。经过足够多次迭代后，最优策略会表现为：尽量远离冰窟窿，谨慎地向终点移动。
扫地机器人可以用 MDP 建模路径规划：
- 状态：机器人的 (x,y) 坐标 + 电池电量
- 动作：前进、左转、右转、回充
- 转移概率：轮子打滑导致方向偏差（类似冰湖问题的湿滑地面）
- 奖励：清扫面积 + 成功回充，碰撞障碍物惩罚
新闻推荐可以用 MDP 建模用户交互：
- 状态：用户近期阅读历史、点击率特征
- 动作：推荐某类新闻
- 转移概率：用户点击/忽略行为模式
- 奖励：点击 +1，深度阅读 +2，忽略 0
AlphaGo 将围棋建模为 MDP（实际使用 MCTS 近似求解）：
- 状态：361 个交叉点的落子局面
- 动作：下一个落子的位置（约 250 个合法位置）
- 转移概率：对手的落子（MDP + 对手建模 -> 博弈论扩展）
- 奖励：终局 +1（赢）/ -1（输），中间步骤 0
| 年份 |
里程碑 |
人物/系统 |
| 1950s |
MDP 框架引入 |
Bellman |
| 1960 |
动态规划 |
Bellman |
| 1970s |
策略迭代 |
Howard |
| 1980s |
与 AI 结合 |
Barto, Sutton |
| 1990s |
TD-Gammon |
Tesauro |
| 2010s |
DQN |
Mnih et al. (DeepMind) |
| 2016 |
AlphaGo |
Silver et al. (DeepMind) |
| 至今 |
大规模 MDP 求解 |
各种深度 RL 算法 |
虽然 MDP 是强大而优雅的框架，但存在一些实际局限性：
- 状态空间爆炸：现实问题的状态空间往往指数级增长（"维度诅咒"），需要函数逼近
- 马尔可夫性假设：某些问题中当前状态不足以表示完整的历史
- 模型已知的假设：实际中 P 和 R 通常未知，需要从数据中学习（无模型 RL）
- 单智能体假设：多智能体环境需要扩展到博弈论框架
- 稳态环境假设：环境变化时 MDP 参数需要重新学习
| 概念 |
公式 |
| 状态序列 |
S0,A0,R1,S1,A1,R2,… |
| 马尔可夫性 |
P(st+1∣st,at,st−1,at−1,…)=P(st+1∣st,at) |
| 回报 |
Gt=∑k=0∞γkRt+k+1 |
| 状态价值函数 |
Vπ(s)=Eπ[Gt∣St=s] |
| 动作价值函数 |
Qπ(s,a)=Eπ[Gt∣St=s,At=a] |
| 贝尔曼期望方程 |
Vπ(s)=∑aπ(a∣s)∑s′,rP(s′∣s,a)[r+γVπ(s′)] |
| 贝尔曼最优方程 |
V∗(s)=maxa∑s′,rP(s′∣s,a)[r+γV∗(s′)] |
| 最优策略 |
π∗(s)=argmaxaQ∗(s,a) |
- Bellman, R. (1957). "A Markovian Decision Process". Journal of Mathematics and Mechanics.
- Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. — 第3-4章详细讲解 MDP 和贝尔曼方程
- Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley.
- 参见：强化学习基础 | Q学习 | 策略梯度方法