MDP相关内容

---

马尔可夫决策过程（Markov Decision Process, MDP）

马尔可夫决策过程（MDP）是强化学习中的核心数学框架，用于建模智能体在不确定环境中的序列决策问题。它提供了一个形式化的方式来描述如何在动态环境中做出最优决策。

---

一、MDP 定义

MDP 是一个五元组：

$$\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma )$$

其中：

• $\mathcal{S}$：状态空间（State Space）
• $\mathcal{A}$：动作空间（Action Space）
• $P(s^{\prime }|s,a)$：状态转移概率函数
• $R(s,a)$ 或 $R(s,a,s^{\prime })$：奖励函数
• $\gamma \in [0,1]$：折扣因子（Discount Factor）

---

二、基本概念

2.1 马尔可夫性质（Markov Property）

下一时刻的状态只依赖于当前状态和当前动作：

$$P(s_{t+1}|s_t,a_t)=P(s_{t+1}|s_0,a_0,...,s_t,a_t)$$

2.2 策略（Policy）

策略 $\pi (a|s)$ 是从状态到动作的概率分布。

• 确定性策略：$\pi (s)=a$
• 随机性策略：$\pi (a|s)$

2.3 值函数（Value Function）

状态值函数：

$$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[G_t|S_t=s\right]$$

动作值函数：

$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[G_t|S_t=s,A_t=a\right]$$

其中回报定义为：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$$

---

三、Bellman 方程

3.1 Bellman 期望方程

对于任意策略 $\pi$，有：

$$V^{\pi }(s)=\sum _a\pi (a|s)\left[R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })\right]$$

$$Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })$$

3.2 Bellman 最优方程

最优值函数定义为：

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

其满足以下最优 Bellman 方程：

$$V^{\ast }(s)=\underset{a}{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V^{\ast }(s^{\prime })\right]$$

$$Q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })$$

---

四、MDP 的求解方法

根据是否知道环境模型（如 $P$ 和 $R$），分为两类：

---

4.1 已知模型（Model-Based Methods）

适用于完全已知 MDP 的情况。

(1) 策略迭代（Policy Iteration）

步骤：

1. 初始化任意策略 ${\pi }_0$
2. 对当前策略进行评估（计算值函数）
3. 对当前策略进行改进（贪心更新策略）
4. 重复直到策略收敛

(2) 值迭代（Value Iteration）

直接求解最优值函数：

$$V_{k+1}(s)=\underset{a}{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V_k(s^{\prime })\right]$$

提取策略：

$${\pi }^{\ast }(s)=\arg \underset{a}{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V^{\ast }(s^{\prime })\right]$$

(3) 线性规划法（Linear Programming）

将 Bellman 最优方程转化为线性规划问题求解。

---

4.2 未知模型（Model-Free Methods）

当环境模型未知时，只能通过采样来学习策略。

(1) 蒙特卡洛方法（Monte Carlo Methods）

• 基于完整的 episode 来估计值函数
• 不使用 bootstrapping
• 只适用于回合任务（episodic tasks）

(2) 时间差分学习（Temporal Difference Learning）

• TD(0)、SARSA、Q-learning 是典型代表
• 使用 bootstrapping 方法更新值函数
• 可以在线学习（on-policy vs off-policy）

Q-learning（off-policy）更新公式：

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_{t+1}+\gamma \underset{a}{\max }Q(s_{t+1},a)-Q(s_t,a_t)\right]$$

SARSA（on-policy）更新公式：

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right]$$

(3) 策略梯度方法（Policy Gradient Methods）

• 直接对策略参数进行优化（如 REINFORCE、Actor-Critic）
• 适用于连续动作空间

(4) 深度强化学习（Deep RL）

• 使用神经网络近似值函数或策略
• 如 DQN、DDPG、PPO、A3C 等

---

五、总结表格：MDP 核心知识点一览

概念	描述
状态空间 $\mathcal{S}$	所有可能的状态集合
动作空间 $\mathcal{A}$	所有可能的动作集合
转移概率 $P(s’	s,a)$
奖励函数 $R(s,a)$	当前动作带来的即时奖励
折扣因子 $\gamma$	控制未来奖励的权重
策略 $\pi$	状态到动作的映射
值函数 $V(s),Q(s,a)$	表示状态/动作的长期价值
Bellman 方程	值函数之间的递归关系
策略迭代 / 值迭代	已知模型下的经典求解方法
Q-learning / SARSA / MC / TD	未知模型下的强化学习方法