马尔可夫决策过程数学基础

马尔可夫决策过程（Markov Decision Process, MDP）是强化学习的理论基础，为序列决策问题提供了统一的数学框架。

1. MDP定义

1.1 基本组成

MDP由五元组定义：

$$\mathcal{M}=(S,A,T,r,\gamma )$$

符号	含义	说明
$S$	状态空间	可能状态的有限或无限集合
$A$	动作空间	可能动作的有限或无限集合
$T(s’	s, a)$	转移函数
$r(s,a)$	奖励函数	在状态$s$执行动作$a$获得的即时奖励
$\gamma \in [0,1)$	折扣因子	未来奖励的重要性权重

1.2 马尔可夫性质

MDP的核心假设是马尔可夫性质：

$$P(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},\dots )=P(s_{t+1}|s_t,a_t)$$

即下一状态仅取决于当前状态和动作，与历史无关。这一性质使得MDP具有时间无记忆性。

1.3 状态-动作序列

智能体与环境交互产生的轨迹：

$$(s_0,a_0,r_0,s_1,a_1,r_1,s_2,\dots )$$

2. 策略函数

2.1 策略定义

策略 $\pi$ 定义了智能体的行为：

$$\pi (a|s)=P(a_t=a|s_t=s)$$

2.2 策略分类

分类标准	类型	说明
确定性	贪婪策略	$\pi (s)=\arg {\max }_a{Q}^{\pi }(s,a)$
随机性	概率策略	$\pi (a\Vert s)$ 表示概率分布
平稳性	不随时变	${\pi }_t=\pi ,\forall t$
非平稳性	随时间变化	${\pi }_t$ 依赖于时间步

2.3 初始状态分布

设初始状态分布为 ${\rho }_0(s)=P(s_0=s)$。

3. 回报函数

3.1 折扣回报

智能体最大化的是折扣累积回报：

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

折扣因子的作用：

• $\gamma \to 0$：强调即时奖励（短视策略）
• $\gamma \to 1$：同等对待远期奖励（远见策略）
• $\gamma <1$：保证无限回报有界

3.2 有限horizon回报

另一种形式是不折扣但限制时间步：

$$G_t=\sum _{k=0}^{T-1}{R}_{t+k+1}$$

3.3 平均奖励

长期平均奖励：

$${\bar{R}}^{\pi }=\underset{T\to \infty }{\lim }\frac{1}{T}\mathbb{E}\left[\sum _{t=0}^{T-1}{R}_t\right]$$

4. 值函数

4.1 状态值函数

从状态 $s$ 开始、遵循策略 $\pi$ 的期望累积回报：

$$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[G_t|S_t=s\right]={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s\right]$$

4.2 动作值函数

从状态 $s$ 开始、执行动作 $a$ 后遵循策略 $\pi$ 的期望累积回报：

$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[G_t|S_t=s,A_t=a\right]={\mathbb{E}}_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a\right]$$

4.3 优势函数

衡量特定动作相对于平均值的优势：

$$A^{\pi }(s,a)=Q^{\pi }(s,a)-V^{\pi }(s)$$

5. 最优性

5.1 最优值函数

存在最优策略 ${\pi }^{\ast }$ 使得所有状态的值函数最大：

$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s),\forall s\in S$$ $$Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}^{\pi }(s,a),\forall s\in S,a\in A$$

5.2 最优策略性质

定理（最优策略存在性）：
对于任意MDP，存在确定性最优策略 ${\pi }^{\ast }$ 满足：

$${\pi }^{\ast }(s)\in \arg \underset{a\in A}{\max }\left[r(s,a)+\gamma \sum _{s^{\prime }\in S}T(s^{\prime }|s,a)V^{\ast }(s^{\prime })\right]$$

6. 强化学习问题分类

6.1 按环境知识分类

类型	环境知识	经典算法
基于模型	已知 $T$ 和 $r$	动态规划、蒙特卡洛树搜索
无模型	未知 $T$ 和 $r$	Q-learning、SARSA、策略梯度

6.2 按学习方式分类

类型	数据利用	特点
在线学习	实时交互	可探索新状态
离线学习	历史数据	避免探索风险

6.3 动作空间分类

类型	动作空间	示例
离散动作	有限集合	棋类、游戏操作
连续动作	无限集合	机器人控制
混合动作	两者兼有	多任务智能体

7. 示例：格子世界

考虑一个简单的$4\times 4$格子世界：

S = {(i,j) | i,j ∈ {1,2,3,4}}
A = {上, 下, 左, 右}
r(s,a) = -1 (除了目标状态)
T(s'|s,a) = 1/|A(s')| (确定性移动)
γ = 0.9

目标状态$V^{\ast }(s^{\ast })=0$，其他状态值函数递减。

8. 与深度学习的联系

8.1 函数近似

现代强化学习使用深度神经网络近似值函数或策略：

• Deep Q-Network (DQN)：用CNN近似 $Q(s,a)$
• 策略网络：用神经网络近似 $\pi (a|s)$
• Actor-Critic：同时学习值函数（Critic）和策略（Actor）

8.2 端到端学习

深度RL直接从原始感知输入学习决策策略，典型架构：

原始输入 → 神经网络特征提取 → 策略/值函数输出 → 动作决策

9. 数学性质

9.1 值函数的有界性

引理：若 $|r(s,a)|\le R_{\max }$，则 $|V^{\pi }(s)|\le \frac{R_{\max }}{1-\gamma }$

证明：

$$|V^{\pi }(s)|\le \mathbb{E}\left[\sum _{k=0}^{\infty }{\gamma }^k|R_{t+k+1}|\right]\le R_{\max }\sum _{k=0}^{\infty }{\gamma }^k=\frac{R_{\max }}{1-\gamma }$$

9.2 值函数的唯一性

对于给定的MDP，$V^{\ast }$ 是唯一的，但 ${\pi }^{\ast }$ 可能不唯一（多个最优策略达到相同值函数）。

10. 参考文献

---

相关主题：Bellman方程与算子理论 | 策略梯度定理 | PPO全局收敛性理论