马尔可夫决策过程(Markov Decision Process,简称 MDP)是强化学习的核心数学框架,也是序列决策问题最基础的形式化工具。几乎所有的强化学习问题都可以转化为 MDP——从围棋对弈到机器人控制,从自动驾驶到推荐系统,从对话系统到股票交易。MDP 提供了一个优雅而强大的方法来描述智能体在不确定环境中通过一系列决策达成长期目标的问题。
现实中的序列决策问题面临三个核心挑战:
| 挑战 |
描述 |
例子 |
| 时间延迟的后果 |
当前决策的后果可能在多步后才能显现 |
下围棋时某一步的布局可能在几十步后才被证明是好棋还是坏棋 |
| 环境的不确定性 |
动作执行结果存在随机性 |
机器人轮子打滑导致实际位移与预期不符 |
| 长期 vs 短期权衡 |
短期利益与长期目标可能冲突 |
股市交易中追涨杀跌(短期)与价值投资(长期)的冲突 |
MDP 通过 状态-动作-奖励-转移 的四元组形式化,为这些问题提供了统一的数学语言。
想象你每天要选餐馆吃午饭:
- 状态:你的位置、时间、已有评分数据
- 动作:选择 A 餐馆或 B 餐馆
- 转移概率:A 可能今天营业(90%)也可能休息(10%)
- 奖励:吃到好菜得 +5,普通 +1,白跑一趟得 -2
- 长期:今天去 A 可能积累了积分(未来奖励),也可能错过了 B 的优惠
这就是一个典型的 MDP——你无法 100% 确定结果,但可以基于概率做最优决策。
一个马尔可夫决策过程由五元组 (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) |
智能体与环境的交互是一个循环过程:
sequenceDiagram
participant Agent as 智能体
participant Env as 环境
Note over Agent,Env: 时间步 t
Env->>Agent: 当前状态 sₜ
Agent->>Env: 选择动作 aₜ
Env->>Agent: 新状态 sₜ₊₁ 和即时奖励 rₜ
Note over Agent,Env: 时间步 t+1,继续循环
具体步骤如下:
- 环境处于状态 st∈S
- 智能体选择动作 at∈A
- 环境根据转移概率 P(st+1∣st,at) 进入新状态 st+1
- 智能体获得即时奖励 rt=R(st,at,st+1)
- 重复步骤 1-4
这个循环生成了交互轨迹:
时间 t: s₀ --a₀--> 环境 --(P(s₁|s₀,a₀))--> s₁, r₀ --a₁--> 环境 --(P(s₂|s₁,a₁))--> s₂, r₁ --> ...
MDP 的核心假设是马尔可夫性:未来状态只依赖于当前状态和当前动作,与历史无关:
P(st+1∣st,at,st−1,at−1,…,s0,a0)=P(st+1∣st,at)
这意味着当前状态 st 已经"充分统计"了历史信息。用通俗的话说:"未来只通过现在依赖于过去"。
为什么这个假设很重要? 如果状态设计得当(例如在围棋中将整个棋盘作为状态,在 Atari 游戏中将最近 4 帧画面叠加作为状态),马尔可夫性可以很好地满足。这大大简化了决策问题的数学处理。
为了直观理解 MDP,我们详细分析一个经典问题——冰湖行走(FrozenLake)。
一个 4×4 的网格,智能体从左上角出发,目标是到达右下角终点。网格中有冰面(可安全行走)和冰窟窿(掉入则失败)。
graph TD
subgraph "4×4 FrozenLake 网格"
S[S<br/>起点] --> G1[⬜] --> G2[⬜] --> G3[⬜]
G1 --> H1[⬜] --> H2[🕳️<br/>冰窟窿] --> H3[⬜] --> H4[🕳️<br/>冰窟窿]
G2 --> H5[⬜] --> H6[⬜] --> H7[⬜] --> H8[🕳️<br/>冰窟窿]
G3 --> H9[🕳️<br/>冰窟窿] --> H10[⬜] --> H11[⬜] --> G[G<br/>终点🎯]
end
网格状态编号:
| 0 (S) 🟢 |
1 |
2 |
3 |
| 4 |
5 🔴 |
6 |
7 🔴 |
| 8 |
9 |
10 |
11 🔴 |
| 12 🔴 |
13 |
14 |
15 (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列,冰面)执行动作"向右":
| 实际方向 |
概率 |
目标状态 |
结果 |
说明 |
| 向右(意图) |
33.3% |
s=7 |
❌ 掉入冰窟窿,终止 |
意图方向不一定最安全 |
| 向上 |
33.3% |
s=2 |
✅ 冰面,存活 |
偏离方向可能救了智能体 |
| 向下 |
33.3% |
s=10 |
✅ 冰面,存活 |
一样的存活概率 |
这个"湿滑冰面"的设定意味着智能体不能完全控制自己的移动——这正是 MDP 中随机性的典型体现。最优策略并不能保证 100% 成功,而是最大化期望成功率。
经过值迭代最终收敛后,冰湖各状态的近似最优价值为:
| 状态 |
V∗(s) |
最优动作 |
含义 |
| 0 |
0.05 |
下 |
起点,需冒一定风险 |
| 1 |
0.02 |
右 |
靠近边缘,风险低 |
| 2 |
0.01 |
下 |
避开冰窟窿 5 |
| 3 |
0.01 |
左或下 |
谨慎靠近终点 |
| 4 |
0.08 |
右 |
中间道价值开始上升 |
| 6 |
0.05 |
下 |
避开两侧的冰窟窿 |
| 8 |
0.12 |
右 |
低路径的核心 |
| 9 |
0.23 |
右 |
接近安全区域 |
| 10 |
0.37 |
右 |
安全,但需防 11 |
| 13 |
0.41 |
右 |
接近终点 |
| 14 |
0.63 |
下 |
一步之遥到终点 |
| 15 |
0 |
— |
终点,无后续价值 |
注意冰窟窿(5,7,11,12)已经是终止状态,价值为 0 且无法继续。起点 0 的价值很低(约 0.05),说明在湿滑条件下从起点到终点的期望成功率约 5%——这就是随机性带来的挑战。
智能体与环境交互产生的一条轨迹(Trajectory)是状态-动作-奖励的有序序列:
τ=(s0,a0,r0,s1,a1,r1,…,sT)
对应的累计回报(Return)是折扣奖励之和:
Gt=rt+γrt+1+γ2rt+2+⋯=k=0∑∞γkrt+k
数值示例:假设一条轨迹的即时奖励序列为 [0,0,0,0,1],不同折扣因子下的回报对比:
| γ |
G0 计算 |
G0 值 |
含义 |
| 0.9 |
0.94×1 |
0.656 |
适度关注长期 |
| 0.99 |
0.994×1 |
0.961 |
强烈关注长期 |
| 0.5 |
0.54×1 |
0.063 |
几乎只看短期 |
| 0.0 |
04×1 |
0.000 |
只看即时奖励(短视) |
γ 越接近 1,智能体考虑的未来步数越长。在围棋中通常使用 γ=1(无折扣),因为终局奖励是最重要的。
策略(Policy)告诉智能体在某个状态下应该做什么:
| 类型 |
记法 |
含义 |
示例 |
| 确定性策略 |
π(s)=a |
每个状态映射到一个动作 |
π(s=6)=右 |
| 随机性策略 |
π(a∣s) |
每个状态上动作的概率分布 |
π(右∣s=6)=0.5 |
随机性策略在实际中非常重要:
- 探索 vs 利用平衡:早期需要随机性来探索未知
- 对抗对手:在博弈中随机性防止被预测
- 不确定性下的鲁棒性:随机策略通常比确定性策略更鲁棒
状态价值函数 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)
在冰湖问题中,如果使用随机均匀策略(每个动作概率 25%),Vπ(s=0) 约为 0.01——几乎难以到达终点,因为纯随机移动很难走出最优路径。
可以把价值函数看作一种**"远见度量"**:
| 状态位置 |
V∗(s) 数量级 |
直观解释 |
| 终点附近 |
~0.6 |
"我马上就要赢了" |
| 中间路径 |
~0.2-0.4 |
"走在正确的路上" |
| 起点附近 |
~0.05 |
"前面还有很多不确定性" |
| 冰窟窿附近 |
~0 |
"危险就在隔壁" |
| 冰窟窿内 |
0 |
"已经失败了" |
贝尔曼方程是 MDP 理论的核心,它给出了价值函数的递归关系,将当前状态的价值与后继状态的价值联系起来。
Vπ(s)=a∑π(a∣s)s′,r∑P(s′∣s,a)[r+γVπ(s′)]
这个方程可以分解理解:
Vπ(s)=遍历所有动作a∑按策略概率选择π(a∣s)遍历所有可能的下个状态s′∑转移概率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个动作),转移和奖励如下:
graph LR
s0[s₀] -->|0.5, r=0| s1[s₁]
s0 -->|0.5, r=0| s2[s₂]
s1 -->|1.0, r=1| s2
s2 -->|1.0, r=0| s2
设 γ=0.9,仅有单一确定性策略。
手动迭代计算(初始 V0(s)=0):
| 迭代 |
V(s0) |
V(s1) |
V(s2) |
关键计算 |
| 0 |
0 |
0 |
0 |
初始化 |
| 1 |
0 |
1.0 |
0 |
V(s1)=1+0.9×0=1.0 |
| 2 |
0.45 |
1.0 |
0 |
V(s0)=0.5(0+0.9×1.0)+0.5(0+0.9×0)=0.45 |
| 3 |
0.45 |
1.0 |
0 |
✅ 收敛 |
详细计算:
第1轮:V(s1)=即时奖励1+0.9×V(s2)=00=1.0
第2轮:
- V(s1) 不变(已收敛)
- V(s0)=0.5(0+0.9×1.0)+0.5(0+0.9×0)=0.5×0.9+0=0.45
最终:V∗(s0)=0.45,V∗(s1)=1.0,V∗(s2)=0
直觉解读:s1 的价值最高因为它一步就能得到 +1 奖励;s0 有一半概率到达 s1 再获奖励,所以价值刚好是 0.9×0.5=0.45。
值迭代通过反复应用贝尔曼最优方程来逼近最优价值函数:
Vk+1(s)=amaxs′,r∑P(s′∣s,a)[r+γVk(s′)]
完整流程:
flowchart TD
A["初始化 V₀(s) = 0 对所有 s"] --> B["对每个状态 s:\nVₖ₊₁(s) = maxₐ Σ P[ r + γVₖ(s') ]"]
B --> C{"|Vₖ₊₁ - Vₖ| < ε 对所有 s?"}
C -->|"否"| B
C -->|"是"| D["从 V* 提取最优策略:\nπ*(s) = argmaxₐ Σ P[ r + γV*(s') ]"]
当 ∥Vk+1−Vk∥<ϵ 时停止迭代,然后从收敛的 V∗ 中提取最优策略:
π∗(s)=argamaxs′,r∑P(s′∣s,a)[r+γV∗(s′)]
策略迭代通过"评估-改进"的循环找到最优策略,收敛更快但每轮计算更重:
flowchart TD
A["初始化随机策略 π₀"] --> B["策略评估:
求解 V^π(s) = Σπ(a|s)ΣP[r + γV^π(s')]
(线性方程组求解)"]
B --> C["策略改进:
π'(s) = argmaxₐ ΣP[r + γV^π(s')]"]
C --> D{"π' == π 对所有 s?"}
D -->|"否"| B
D -->|"是"| E["✅ 找到最优策略"]
| 方面 |
值迭代 |
策略迭代 |
| 优化对象 |
价值函数 |
策略本身 |
| 每轮成本 |
O(∥S∥2∥A∥) |
O(∥S∥3)(求解线性系统) |
| 迭代次数 |
多(可能数百轮) |
少(通常 10-50 轮) |
| 收敛类型 |
线性收敛(率由 γ 决定) |
超线性收敛(二次收敛速率) |
| 实现复杂度 |
简单 |
中等(需解线性方程) |
| 存储需求 |
∥S∥ 个浮点数 |
∥S∥ 个浮点数 + 策略表 |
| 适用场景 |
大规模状态空间 |
中小规模(<10⁶ 状态) |
| 截断策略 |
需要 ϵ 阈值 |
自然收敛(策略不变) |
| 早期策略质量 |
差(价值未收敛前不宜提取策略) |
好(每轮都在改进策略) |
选择指南:
- 状态数 < 10⁵:优先策略迭代(总计算量更小)
- 状态数 > 10⁶:优先值迭代(每轮成本更低)
- 需要中间可用的策略:策略迭代
- 实现简单性优先:值迭代
对于冰湖 4×4 网格,值迭代的 3 轮计算过程(部分关键状态):
flowchart LR
subgraph "第0轮"
V0_0["V(s₀)=0"]
V0_14["V(s₁₄)=0"]
V0_10["V(s₁₀)=0"]
end
subgraph "第1轮"
V1_0["V(s₀)=0"]
V1_14["V(s₁₄)=0.33"]
V1_10["V(s₁₀)=0"]
end
subgraph "第2轮"
V2_0["V(s₀)=0"]
V2_14["V(s₁₄)=0.33"]
V2_10["V(s₁₀)=0.10"]
end
subgraph "第3轮"
V3_0["V(s₀)=0.01"]
V3_14["V(s₁₄)=0.43"]
V3_10["V(s₁₀)=0.17"]
end
V0_0 -->|"无奖励"| V1_0
V0_14 -->|"下→终点: ⅓×1"| V1_14
V1_0 -->|"价值还未传播到"| V2_0
V1_14 -->|"仍为0.33"| V2_14
V1_10 -->|"右→14: ⅓×0.9×0.33"| V2_10
V2_0 -->|"下→4, 下→8: 远未到终点"| V3_0
V2_14 -->|"下: ⅓×1 + ⅔×0.9×0.10"| V3_14
V2_10 -->|"右: ⅓×0.9×0.33 + ⅔×..."| V3_10
详细计算:
第1轮:只有靠近终点 s=15 的状态能一步获奖励
- V1(14): 动作"向下"有 1/3 概率到终点,获得 +1:V1(14)=31×(1+0.9×0)=0.33
第2轮:价值开始从终点"反传"
第3轮:更多状态获得非零价值
经过约 100 轮迭代,价值从终点逐步传播到整个网格,最终得到前文给出的最优价值表。
将冰湖问题的完整 MDP 求解流程整合如下:
flowchart TD
A["定义 MDP 五元组<br/>(S, A, P, R, γ)"] --> B["选择求解方法"]
B --> C1["值迭代<br/>简单、可扩展"]
B --> C2["策略迭代<br/>高效、收敛快"]
C1 --> D1["初始化 V(s)=0"]
D1 --> E1["Vₖ₊₁(s)=maxₐ ΣP[r+γVₖ(s')]"]
E1 --> F1{"收敛?"}
F1 -->|"否"| E1
F1 -->|"是"| G["提取最优策略"]
C2 --> D2["初始化随机策略"]
D2 --> E2["求解 V^π 线性方程组"]
E2 --> F2["策略改进:<br/>π'(s)=argmaxₐ ΣP[r+γV^π(s')]"]
F2 --> H{"策略不变?"}
H -->|"否"| E2
H -->|"是"| G
G --> I["最优策略示例:<br/>s₁₄ → 下<br/>s₁₀ → 右<br/>s₆ → 下"]
graph TD
RP["随机过程"] --> MC["马尔可夫链<br/>无控制、无奖励"]
RP --> MDP["马尔可夫决策过程<br/>有控制、有奖励"]
MC --> HMM["隐马尔可夫模型<br/>不可观察状态"]
MC --> MRP["马尔可夫奖励过程<br/>有奖励、无控制"]
MDP --> FullObs["完全可观察 → MDP"]
MDP --> PartObs["部分可观察 → POMDP"]
MDP --> MultiAg["多智能体 → MDP-MM"]
MDP --> ContAct["连续动作 → CMDP"]
FullObs --> DDisc["离散状态<br/>值/策略迭代"]
FullObs --> DCont["连续状态<br/>函数逼近 + RL"]
PartObs --> Belief["信念状态<br/>PSPACE-hard"]
| 特征 |
马尔可夫链 |
马尔可夫决策过程 |
| 控制输入 |
❌ 无 |
✅ 有(动作/决策) |
| 转移概率 |
P(s′∣s) |
P(s′∣s,a) |
| 奖励信号 |
❌ 无 |
✅ 有 |
| 核心目标 |
分析稳态分布 |
最大化累计奖励 |
| 典型应用 |
网页排名(PageRank) |
强化学习、最优控制 |
关键区别:马尔可夫链是被动观察的随机过程,MDP 是智能体主动参与决策的过程。一句话:"马尔可夫链属于概率论,MDP 属于决策论"。
| 特征 |
MDP |
POMDP |
| 状态观察 |
完全可观察 |
部分可观察(如自动驾驶中的传感器噪声) |
| 智能体知道 |
当前真实状态 s |
信念状态 b(s)(概率分布) |
| 最优策略形式 |
π(s) |
π(b) — 信念空间连续 |
| 计算复杂度 |
多项式时间 O(∥S∥2∥A∥) |
PSPACE-hard |
| 典型应用 |
棋盘游戏、机器人定位 |
自动驾驶、疾病诊断、对话系统 |
POMDP 增加了观测函数 O(o∣s′,a),描述在状态 s′ 和动作 a 下获得观测 o 的概率。由于信念状态是高维连续空间,POMDP 通常需要近似求解。
当状态空间连续时(如机器人关节角度),MDP 直接求解不可行。常用策略:
| 方法 |
思路 |
例子 |
| 离散化 |
将连续状态网格化 |
将 [-1,1] 区间分为 20 等份 |
| 线性函数逼近 |
V(s)=wTϕ(s) |
使用 tile coding |
| 神经网络逼近 |
V(s;θ) |
DQN 用 CNN 逼近 Q 函数 |
| 核方法 |
使用核函数在再生核希尔伯特空间中逼近 |
RBF 核 + LSTD |
扫地机器人可以用 MDP 建模路径规划:
- 状态:机器人 (x,y) 坐标 + 电池电量 + 已清扫面积
- 动作:前进、左转、右转、回充
- 转移概率:轮子打滑导致方向偏差(类似冰湖的湿滑地面)
- 奖励:
- 清扫面积增加:+0.01 / 格
- 成功回充:+10
- 碰撞障碍物:-1
- 电池耗尽:-100
典型问题:机器人需要权衡"多清扫一会儿"(短期收益)vs "早点回充"(避免耗尽的长期惩罚)。
新闻推荐可以用 MDP 建模用户交互:
- 状态:用户画像 + 近期阅读历史 + 当前 session 特征
- 动作:推荐某类/某篇新闻
- 转移概率:用户点击/忽略/跳转的行为模式
- 奖励:点击 +1,深度阅读(>30s)+2,分享 +5,忽略 0,取关 -10
实际效果:阿里巴巴等公司将推荐系统中的用户交互建模为 MDP,通过强化学习优化长短期收益平衡,用户参与度提升 10-20%。
AlphaGo 将围棋建模为 MDP(实际使用 MCTS + 深度神经网络近似求解):
- 状态:19×19 棋盘上的落子局面(3361 种可能)
- 动作:下一个合法落子位置(平均约 250 个合法位置)
- 转移概率:对手的落子(实际通过自我对弈模拟)
- 奖励:终局 +1(赢)/ -1(输),中间步骤 0
为什么围棋需要 MDP 的高级变体? 因为 ∣S∣=3361 是一个天文学数字,传统值迭代完全不可行。AlphaGo 的关键创新是使用深度神经网络 + MCTS 来近似求解这个超大规模 MDP。
| 领域 |
MDP 应用 |
代表性系统 |
| 游戏 AI |
⭐⭐⭐⭐⭐ |
AlphaGo, DQN (Atari), OpenAI Five (Dota 2) |
| 机器人 |
⭐⭐⭐⭐ |
路径规划、机械臂控制 |
| 推荐系统 |
⭐⭐⭐⭐ |
YouTube RL 推荐、阿里巴巴 |
| 自动驾驶 |
⭐⭐⭐ |
决策规划层(POMDP) |
| NLP/对话系统 |
⭐⭐⭐ |
任务型对话(POMDP 框架) |
| 金融交易 |
⭐⭐ |
最优执行、组合管理 |
| 医疗 |
⭐⭐ |
治疗方案优化、药物剂量控制 |
| 能源 |
⭐⭐ |
电网调度、储能管理 |
timeline
title MDP 发展历程
1950s : MDP 框架由 Bellman 提出
: 动态规划(Dynamic Programming)奠基
1960s : 策略迭代(Howard)
: 线性规划求解 MDP(Manne)
1970s : 与人工智能结合
: 强化学习雏形(Minsky)
1980s : 时序差分学习(Sutton)
: 与动物学习理论的联系
1990s : TD-Gammon 击败人类
: Q-learning(Watkins)
2010s : DQN 玩 Atari 游戏
: DDPG、PPO、SAC 等深度 RL 算法
2016 : AlphaGo 击败李世石
至今 : 大规模 MDP 求解
: 离线 RL、基于模型的 RL
| 年份 |
里程碑 |
人物/系统 |
对 MDP 的意义 |
| 1957 |
MDP 框架提出 |
Richard Bellman |
MDP 概念的正式诞生 |
| 1960 |
动态规划 |
Bellman |
求解 MDP 的基础算法 |
| 1973 |
策略迭代 |
Ronald Howard |
更高效的 MDP 求解算法 |
| 1988 |
时序差分学习 |
Richard Sutton |
无模型 MDP 求解 |
| 1992 |
Q-learning |
Chris Watkins |
首个无模型离线 RL |
| 1995 |
TD-Gammon |
Gerald Tesauro |
MDP 首次击败人类高手 |
| 2013 |
DQN |
Mnih et al. |
深度学习+ MDP = 突破 |
| 2016 |
AlphaGo |
DeepMind |
MDP 战胜围棋世界冠军 |
| 2019 |
MuZero |
DeepMind |
无需环境模型的 MDP 求解 |
| 2022 |
Gato |
DeepMind |
通用 MDP 求解器 |
- 定义状态空间 S:什么信息是决策需要的?是否满足马尔可夫性?
- 检查:当前状态包含所有决策相关信息吗?
- 如果不行:考虑增加状态维度或使用 POMDP
- 定义动作空间 A:智能体可以做什么?
- 定义转移概率 P:动作执行后的结果分布
- 已知模型:直接使用
- 未知模型:采集数据学习 / 使用无模型 RL
- 定义奖励函数 R:什么行为应该被鼓励/惩罚?
- 最关键也最容易犯错的一步
- 奖励工程(Reward Shaping)影响巨大
- 选择折扣因子 γ:多看重未来?
| 陷阱 |
描述 |
例子 |
| 奖励过于稀疏 |
大多数状态奖励为 0 |
只有到终点才有 +1,中间无信号 |
| 奖励过于密集 |
每一步都定义奖励,干扰学习 |
每一步都 +0.01,掩盖了真正的目标 |
| 奖励黑客 |
智能体找到作弊获取奖励的方式 |
游戏 AI 卡在某个位置反复获分 |
| 未对齐 |
奖励与真实目标不一致 |
推荐系统追求点击率导致标题党泛滥 |
| 奖励尺度不当 |
不同奖励信号量级相差太大 |
奖励 -100 到 +100,学习不稳定 |
值迭代收敛速度:值迭代的收敛速度由折扣因子 γ 决定。误差上界为:
∥Vk+1−V∗∥∞≤γk∥V1−V∗∥∞
这意味着:
- γ=0.9:每轮减少 10% 误差,约 44 轮减少 99%
- γ=0.99:每轮减少 1% 误差,约 459 轮减少 99%
- γ=0.999:约 4600 轮减少 99%
实际实现技巧:
import numpy as np
def value_iteration(P, R, gamma, theta=1e-6, max_iter=10000):
"""
值迭代求解 MDP
参数:
P: 转移概率矩阵, shape (|S|, |A|, |S|)
R: 奖励函数矩阵, shape (|S|, |A|)
gamma: 折扣因子
theta: 收敛阈值
max_iter: 最大迭代次数
"""
n_states, n_actions = R.shape
V = np.zeros(n_states)
for i in range(max_iter):
V_prev = V.copy()
# 对每个状态计算所有动作的价值
for s in range(n_states):
q_values = np.zeros(n_actions)
for a in range(n_actions):
q_values[a] = R[s, a] + gamma * np.dot(P[s, a], V_prev)
V[s] = np.max(q_values)
# 检查收敛
if np.max(np.abs(V - V_prev)) < theta:
print(f"收敛于第 {i+1} 轮迭代")
break
# 提取最优策略
policy = np.zeros(n_states, dtype=int)
for s in range(n_states):
q_values = np.zeros(n_actions)
for a in range(n_actions):
q_values[a] = R[s, a] + gamma * np.dot(P[s, a], V)
policy[s] = np.argmax(q_values)
return V, policy
虽然 MDP 是强大而优雅的框架,但存在一些实际局限性:
| 局限性 |
描述 |
缓解方案 |
| 状态空间爆炸 |
连续状态或高维离散导致维度诅咒 |
函数逼近(神经网络)、状态抽象 |
| 马尔可夫性假设 |
某些问题当前状态不足以表示历史 |
状态增强(如带历史窗口)、POMDP |
| 模型已知的假设 |
P 和 R 通常未知 |
无模型 RL(Q-learning, PPO)、基于模型的 RL |
| 单智能体假设 |
多智能体环境需扩展 |
博弈论扩展(马尔可夫博弈、势博弈) |
| 稳态环境假设 |
环境变化时需重新学习 |
上下文 MDP、元学习、迁移学习 |
| 奖励函数设计 |
奖励工程困难且容易出问题 |
逆强化学习、偏好学习(RLHF) |
| 概念 |
公式 |
说明 |
| 状态序列 |
S0,A0,R1,S1,A1,R2,… |
标准交互序列 |
| 马尔可夫性 |
P(st+1∣st,at,…)=P(st+1∣st,at) |
无后效性 |
| 折扣回报 |
Gt=∑k=0∞γkRt+k+1 |
累计折扣奖励 |
| 状态价值函数 |
Vπ(s)=Eπ[Gt∣St=s] |
从状态 s 出发的期望回报 |
| 动作价值函数 |
Qπ(s,a)=Eπ[Gt∣St=s,At=a] |
从 s 执行 a 后的期望回报 |
| 贝尔曼期望方程 |
Vπ(s)=∑aπ(a∣s)∑s′P(s′∣s,a)[r+γVπ(s′)] |
递归自洽条件 |
| 贝尔曼最优方程 |
V∗(s)=maxa∑s′P(s′∣s,a)[r+γV∗(s′)] |
最优价值递归 |
| 值迭代更新 |
Vk+1(s)=maxa∑s′P(s′∣s,a)[r+γVk(s′)] |
迭代逼近最优 |
| 最优策略 |
π∗(s)=argmaxaQ∗(s,a) |
选择最高 Q 值的动作 |
现代应用中的 MDP 往往具有超大规模状态空间(如围棋 10170,Go 游戏 10360),传统算法完全不可行:
| 方法 |
核心思想 |
代表工作 |
| 深度 Q 网络(DQN) |
用深度神经网络逼近 Q(s,a) |
Mnih et al. 2013 |
| 策略梯度 |
直接优化策略参数 |
PPO (Schulman 2017), SAC (Haarnoja 2018) |
| MuZero |
将模型学习和规划统一 |
Schrittwieser et al. 2019 |
| 分布强化学习 |
学习回报的完整分布 |
C51, IQN (Dabney et al. 2018) |
传统 RL 需要在线交互,但很多场景只能使用历史数据(如医疗、自动驾驶):
- 离线策略学习(Offline RL):从固定数据集中学习最优策略,不与环境交互
- 分布外泛化(OOD Generalization):处理数据分布之外的未见状态
- 保守 Q 学习(CQL):通过对 Q 值施加惩罚来避免 OOD 动作的过估计
多智能体场景扩展为博弈框架,面临新的挑战:
| 主题 |
挑战 |
方法 |
| 非平稳性 |
每个智能体的策略都在变化 |
独立学习、集中训练分散执行 |
| 信用分配 |
哪个智能体的决策导致了结果 |
反事实基线(COMA)、差异奖励 |
| 通信 |
智能体间共享信息 |
通信协议学习、隐式信息传递 |
- Bellman, R. (1957). "A Markovian Decision Process". Journal of Mathematics and Mechanics. — MDP 框架的原始论文
- Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. — RL 圣经,第 3-4 章详细讲解 MDP 和贝尔曼方程
- Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. — MDP 的理论专著
- Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control (4th ed.). Athena Scientific. — 动态规划的权威参考
- Mnih et al. (2013). "Playing Atari with Deep Reinforcement Learning". — DQN 的开创之作
- Silver et al. (2016). "Mastering the Game of Go with Deep Neural Networks and Tree Search". — AlphaGo
- Schrittwieser et al. (2019). "Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model". — MuZero
- Schulman et al. (2017). "Proximal Policy Optimization Algorithms". — PPO