02 - 马尔可夫决策过程¶
⚠️ 时效性说明：本章涉及前沿模型/价格/榜单等信息，可能随版本快速变化；请以论文原文、官方发布页和 API 文档为准。
学习时间: 3小时 重要性: ⭐⭐⭐⭐⭐ 强化学习的数学基础，必须掌握
🎯 学习目标¶
完成本章后，你将能够： - 理解马尔可夫性质及其重要性 - 掌握马尔可夫决策过程（MDP）的五个组成部分 - 区分episodic和continuing任务 - 理解状态转移概率和奖励函数 - 能够用MDP框架描述实际问题
1. 马尔可夫性质¶
1.1 什么是马尔可夫性质？¶
马尔可夫性质（Markov Property）：
未来只依赖于当前状态，而与历史无关。
数学表达： $\(P[S_{t+1} | S_t, A_t] = P[S_{t+1} | S_t, A_t, S_{t-1}, A_{t-1}, ..., S_0, A_0]\)$
换句话说：当前状态包含了所有历史信息。
1.2 直观理解¶
Text Only
好的状态表示:
├── 下围棋：当前棋盘局面
├── 开车：当前位置、速度、方向
└── 股票：当前价格、成交量、趋势
不好的状态表示:
├── 下围棋：只记住最后一步棋
├── 开车：只记得当前位置（没有速度）
└── 股票：只记得今天的价格（没有历史趋势）
1.3 为什么重要？¶
- 简化问题：不需要记住完整历史
- 数学可处理：可以使用动态规划等方法
- 计算可行：状态空间不会随时间指数增长
2. 马尔可夫决策过程（MDP）¶
2.1 MDP的五个组成部分¶
MDP是一个五元组：\((S, A, P, R, \gamma)\)
Text Only
┌─────────────────────────────────────────────────────────────┐
│ MDP五元组 │
├─────────────────────────────────────────────────────────────┤
│ │
│ S: 状态空间 (State Space) │
│ - 所有可能状态的集合 │
│ - 例如：{空闲, 忙碌}, {位置1, 位置2, 位置3} │
│ │
│ A: 动作空间 (Action Space) │
│ - 所有可能动作的集合 │
│ - 例如：{工作, 休息}, {上, 下, 左, 右} │
│ │
│ P: 状态转移概率 (Transition Probability) │
│ - P(s'|s,a): 在状态s执行动作a，转移到状态s'的概率 │
│ - 满足：Σ P(s'|s,a) = 1 │
│ │
│ R: 奖励函数 (Reward Function) │
│ - R(s,a,s'): 在状态s执行动作a，转移到s'获得的奖励 │
│ - 也可以是 R(s,a) 或 R(s) │
│ │
│ γ: 折扣因子 (Discount Factor) │
│ - 0 ≤ γ ≤ 1 │
│ - 平衡即时奖励和未来奖励 │
│ │
└─────────────────────────────────────────────────────────────┘
2.2 状态转移概率 P(s'|s,a)¶
定义：在状态s执行动作a，转移到状态s'的概率。
示例：Grid World
Text Only
┌─────┬─────┬─────┐
│ S1 │ S2 │ S3 │
├─────┼─────┼─────┤
│ S4 │ S5 │ S6 │
├─────┼─────┼─────┤
│ S7 │ S8 │ S9 │
└─────┴─────┴─────┘
假设在S5，执行动作"上"：
├── 70%概率到达S2（正确移动）
├── 10%概率到达S1（向左滑）
├── 10%概率到达S3（向右滑）
└── 10%概率留在S5（滑倒没动）
数学表达：
P(S2|S5,"上") = 0.7
P(S1|S5,"上") = 0.1
P(S3|S5,"上") = 0.1
P(S5|S5,"上") = 0.1
2.3 奖励函数 R(s,a,s')¶
定义：在状态s执行动作a，转移到状态s'获得的即时奖励。
示例：Grid World
Text Only
┌─────┬─────┬─────┐
│ +1 │ │ -1 │
├─────┼─────┼─────┤
│ │ │ │
├─────┼─────┼─────┤
│ │ │ │
└─────┴─────┴─────┘
奖励设置：
├── 到达+1位置：+10奖励
├── 到达-1位置：-10奖励
├── 其他移动：-1奖励（鼓励快速到达目标）
└── 撞墙：-5奖励（惩罚无效动作）
2.4 完整MDP示例¶
问题：学生考试复习的MDP建模
Text Only
动作：{刷Facebook, 学习, 睡觉, 放弃}
状态转移和奖励：
Facebook → Facebook: 刷FB，奖励+1，但浪费时间
学习1 → 学习2: 学习，奖励-2，但进度+1
学习3 → 考试: 准备充分，奖励+10
学习3 → 挂科: 考试失败，奖励-10
睡觉 → 睡觉: 休息，奖励+1
目标：最大化期望奖励（通过考试）
3. Episodic vs Continuing任务¶
3.1 Episodic任务（回合制）¶
特点： - 有明确的开始和结束 - 可以自然地分成多个episode - 每个episode独立
例子：
数学表达： - 状态空间包含终止状态（terminal states） - 到达终止状态后，episode结束 - 可以重新开始新的episode
3.2 Continuing任务（连续）¶
特点： - 没有自然终点 - 持续进行，理论上无限 - 需要考虑长期性能
例子：
数学处理： - 使用折扣因子 γ < 1 保证收敛 - 考虑无限时间范围内的累积奖励
3.3 统一框架¶
Text Only
Episodic任务可以看作特殊的Continuing任务:
├── 终止状态 → 吸收状态（absorbing state）
├── 到达后永远停留
├── 奖励为0
└── 等价于episode结束
4. 实际问题的MDP建模¶
4.1 机器人导航¶
Text Only
问题：机器人在房间中导航到目标位置
MDP建模：
├── 状态：机器人的位置 (x, y)
├── 动作：{上, 下, 左, 右}
├── 转移：动作可能失败（滑到相邻位置）
├── 奖励：
│ ├── 到达目标：+100
│ ├── 撞墙：-10
│ ├── 每步：-1（鼓励快速到达）
└── 折扣：γ = 0.9
挑战：
├── 连续状态空间需要离散化
├── 动作不确定性
└── 障碍物处理
4.2 库存管理¶
Text Only
问题：商店管理商品库存
MDP建模：
├── 状态：当前库存量
├── 动作：订购数量
├── 转移：需求随机（泊松分布）
├── 奖励：
│ ├── 销售收入：+p×min(库存, 需求)
│ ├── 订购成本：-c×订购量
│ ├── 库存成本：-h×剩余库存
│ └── 缺货惩罚：-l×max(0, 需求-库存)
└── 折扣：γ = 0.95
目标：最大化长期利润
4.3 网络路由¶
Text Only
问题：数据包在网络中选择最优路径
MDP建模：
├── 状态：当前节点 + 网络状态（拥塞情况）
├── 动作：选择下一跳节点
├── 转移：网络状态变化 + 数据包移动
├── 奖励：
│ ├── 成功到达：+100
│ ├── 传输延迟：-延迟时间
│ └── 丢包：-1000
└── 折扣：γ = 0.99
挑战：
├── 大规模状态空间
├── 动态网络环境
└── 多目标优化（延迟 vs 丢包率）
5. 代码实现：Grid World MDP¶
让我们实现一个简单的Grid World环境来理解MDP：
Python
import numpy as np
import matplotlib.pyplot as plt
class GridWorldMDP:
"""
简单的Grid World MDP实现
"""
def __init__(self, width=4, height=3, gamma=0.9):
self.width = width
self.height = height
self.gamma = gamma
# 状态空间：每个格子是一个状态
self.states = [(i, j) for i in range(height) for j in range(width)]
# 动作空间：上下左右
self.actions = ['up', 'down', 'left', 'right']
# 特殊状态
self.goal_state = (0, 3) # 目标状态
self.hole_state = (1, 3) # 陷阱状态
self.start_state = (2, 0) # 起始状态
# 初始化转移概率和奖励
self.init_transition_prob()
self.init_rewards()
def init_transition_prob(self):
"""初始化状态转移概率"""
self.P = {}
for state in self.states:
self.P[state] = {}
for action in self.actions:
self.P[state][action] = {}
# 计算下一个状态
next_state = self.get_next_state(state, action)
# 确定性转移（简化版本）
self.P[state][action][next_state] = 1.0
def get_next_state(self, state, action):
"""根据当前状态和动作计算下一个状态"""
i, j = state
if action == 'up':
i = max(0, i - 1)
elif action == 'down':
i = min(self.height - 1, i + 1)
elif action == 'left':
j = max(0, j - 1)
elif action == 'right':
j = min(self.width - 1, j + 1)
return (i, j)
def init_rewards(self):
"""初始化奖励函数"""
self.R = {}
for state in self.states:
self.R[state] = {}
for action in self.actions:
next_state = self.get_next_state(state, action)
# 根据下一个状态确定奖励
if next_state == self.goal_state:
self.R[state][action] = 10.0 # 到达目标
elif next_state == self.hole_state:
self.R[state][action] = -10.0 # 掉入陷阱
else:
self.R[state][action] = -1.0 # 普通移动
def step(self, state, action):
"""执行一步MDP"""
# 检查是否是终止状态
if state in [self.goal_state, self.hole_state]:
return state, 0.0, True, False, {} # 保持在终止状态，奖励为0
# 获取下一个状态和奖励
next_state = self.get_next_state(state, action)
reward = self.R[state][action]
done = next_state in [self.goal_state, self.hole_state]
return next_state, reward, done, False, {}
def display_mdp(self):
"""显示MDP结构"""
print("Grid World MDP:")
print(f"状态空间: {len(self.states)} 个状态")
print(f"动作空间: {self.actions}")
print(f"折扣因子: {self.gamma}")
print("\n奖励结构:")
for i in range(self.height):
row = []
for j in range(self.width):
state = (i, j)
if state == self.goal_state:
row.append("+10")
elif state == self.hole_state:
row.append("-10")
else:
row.append("-1")
print(f"Row {i}: {row}")
# 测试MDP
mdp = GridWorldMDP()
mdp.display_mdp()
# 测试状态转移
print(f"\n从状态(2,0)执行'up':")
next_state, reward, done, _, _ = mdp.step((2, 0), 'up')
print(f"下一个状态: {next_state}, 奖励: {reward}, 是否结束: {done}")
print(f"\n从状态(1,2)执行'right':")
next_state, reward, done, _, _ = mdp.step((1, 2), 'right')
print(f"下一个状态: {next_state}, 奖励: {reward}, 是否结束: {done}")
输出示例：
Text Only
Grid World MDP:
状态空间: 12 个状态
动作空间: ['up', 'down', 'left', 'right']
折扣因子: 0.9
奖励结构:
Row 0: ['-1', '-1', '-1', '+10']
Row 1: ['-1', '-1', '-1', '-10']
Row 2: ['-1', '-1', '-1', '-1']
从状态(2,0)执行'up':
下一个状态: (1, 0), 奖励: -1.0, 是否结束: False
从状态(1,2)执行'right':
下一个状态: (1, 3), 奖励: -10.0, 是否结束: True
6. 本章总结¶
核心概念回顾¶
Text Only
马尔可夫决策过程 (MDP) = 五元组 (S, A, P, R, γ)
├── S: 状态空间 - 所有可能状态的集合
├── A: 动作空间 - 所有可能动作的集合
├── P: 状态转移概率 - P(s'|s,a)
├── R: 奖励函数 - R(s,a,s')
└── γ: 折扣因子 - 平衡现在和未来
关键性质：
└── 马尔可夫性质 - 未来只依赖当前状态
任务类型：
├── Episodic - 有自然终点（如下棋）
└── Continuing - 无限进行（如股票交易）
学习路径¶
✅ 自测问题¶
-
什么是马尔可夫性质？为什么它对RL很重要？
-
MDP的五个组成部分是什么？分别有什么作用？
-
状态转移概率 P(s'|s,a) 和奖励函数 R(s,a,s') 有什么区别？
-
Episodic任务和Continuing任务的区别是什么？各举一个例子。
-
如何将一个实际问题建模为MDP？需要考虑哪些因素？
📚 延伸阅读¶
推荐资源¶
- Sutton & Barto《Reinforcement Learning: An Introduction》
-
第3章：Finite Markov Decision Processes
-
David Silver的RL课程（YouTube）
-
Lecture 2: Markov Decision Processes
-
CS285: Deep Reinforcement Learning
- Lecture 2: MDP and Value Functions
准备好进入下一阶段了吗？ 下一章我们将学习贝尔曼方程，这是RL最核心的数学工具。
→ 下一步：03-贝尔曼方程.md