MDP

​ 马尔可夫决策过程（Markov Decision Process, MDP）并非强化学习算法本身，而是构建智能体与环境交互的数学框架。作为强化学习理论体系的基石，超过90%的强化学习算法都建立在环境满足马尔可夫性的基本假设之上

马尔科夫性：动态系统的记忆

形式化定义

​ 记代表一个随机现象的随机向量在 $t$ 时候取值为 $\boldsymbol S_t$，则一个随机过程可以表示 $t+1$ 时刻的 $\boldsymbol S_{t+1}$ 随机向量的取值概率函数为 $P(\boldsymbol S_{t+1}|\boldsymbol S_1, \dots, \boldsymbol S_t)$，当 $P(\boldsymbol S_{t+1} | \boldsymbol S_t)=P(\boldsymbol S_{t+1}|\boldsymbol S_1, \dots, \boldsymbol S_t)$ 时，称这个随机过程满足马尔科夫性

​ 马尔可夫决策过程由元组 $<\mathcal{S, A}, P, r, \gamma>$ 构成，其中：

• $\mathcal{S}$ 是状态集合，$\mathcal{A}$ 是动作集合
• $\gamma$ 为折扣因子
• $r(\boldsymbol{s,a})$ 是奖励函数，当奖励只取决于状态时退化为 $r(\boldsymbol{s})$
• $P(\boldsymbol{s}^\prime|\boldsymbol{s,a})$ 为状态转移函数，表示状态 $\boldsymbol{s}$ 下执行动作 $\boldsymbol{a}$ 之后达到状态 $\boldsymbol{s}^\prime$ 的概率

值函数：评价决策的好坏

​ 定义 $V^\pi(\boldsymbol{s})$ 为 MDP 中策略 $\pi$ 下的状态价值函数（state-value function），定义为从状态 $\boldsymbol{s}$ 出发遵循策略 $\pi$ 获得的期望回报（长期期望收益）：

$$V^\pi(\boldsymbol{s}) = \mathbb{E}_\pi [ G_t | \boldsymbol{S}_t=s]$$

定义动作价值函数 $Q^\pi(\boldsymbol{s,a})$ 为（量化某个动作的预期价值）：

$$Q^\pi(\boldsymbol{s,a}) = \mathbb{E}_\pi[G_t|\boldsymbol{S}_t=\boldsymbol{s}, \boldsymbol{A}_t=\boldsymbol{a}]$$

• 注意在强化学习里面求期望的习惯记号是存在很多省略之处的，下标 $\pi$ 代表着采样序列的时候使用策略 $\pi$ 采样，而不是对什么求期望，被求期望的对象在这里都省略掉了，其中 $Q^\pi$ 的求期望对象是转移状态 $\boldsymbol s'$，$V^\pi$ 的求期望对象是当前策略下会采用的动作 $\boldsymbol a$ 和下一个转移状态 $\boldsymbol s'$

状态值函数和动作值函数满足关系：

$$\boxed{ \begin{aligned} V^\pi(\boldsymbol s) =& \sum_{\boldsymbol a}\pi(\boldsymbol{a|s}) Q^\pi(\boldsymbol{s,a}) \\ Q^\pi(\boldsymbol{s,a}) =& r(\boldsymbol{s,a}) + \gamma\sum_{\boldsymbol s'}P(\boldsymbol s'|\boldsymbol{s,a}) V^\pi(\boldsymbol s') \end{aligned} }$$

贝尔曼期望方程：沿时序递推

贝尔曼方程

1. 状态值函数沿时序递推：

$$\begin{aligned} Q^\pi(\boldsymbol{s,a}) =& \mathbb{E}_\pi[G_t|\boldsymbol{S}_t=\boldsymbol{s}, \boldsymbol{A}_t=\boldsymbol{a}]\\ =& \mathbb{E}_\pi[R_t + \gamma G_{t+1}|\boldsymbol{S}_t=\boldsymbol{s}, \boldsymbol{A}_t=\boldsymbol{a}]\\ =& \mathbb{E}_{\pi, \boldsymbol{s}^\prime \sim P(\cdot|\boldsymbol{s,a})}[R_t + \gamma Q^\pi(\boldsymbol{s}^\prime ,\boldsymbol{a}^\prime)|\boldsymbol{S}_t=\boldsymbol{s}, \boldsymbol{A}_t=\boldsymbol{a}]\\ =& r(\boldsymbol{s},\boldsymbol{a}) + \gamma\sum_{\boldsymbol{s'}}P(\boldsymbol{s'}|\boldsymbol{s,a})\mathbb{E}_{\boldsymbol{a}' \sim \pi(\cdot|\boldsymbol{s}')}[Q^\pi(\boldsymbol{s',a'})]\\ =& r(\boldsymbol{s},\boldsymbol{a}) + \gamma\sum_{\boldsymbol{s'}}P(\boldsymbol{s'}|\boldsymbol{s,a}) V^\pi(\boldsymbol s')\\ =& \boxed{r(\boldsymbol{s},\boldsymbol{a}) + \gamma\sum_{\boldsymbol{s'}}P(\boldsymbol{s'}|\boldsymbol{s,a}) \sum_{\boldsymbol a'}\pi(\boldsymbol a'|\boldsymbol{s}') Q^\pi(\boldsymbol{s',a'})} \end{aligned}$$

2. 动作值函数沿时序递推：

$$\begin{aligned} V^\pi(\boldsymbol s) =& \mathbb{E}_\pi [ G_t | \boldsymbol{S}_t=s] \\ =& \mathbb{E}_{\boldsymbol a \sim \pi(\cdot | \boldsymbol s)}\left[ \mathbb{E}_{\boldsymbol s' \sim P(\cdot | \boldsymbol{s,a})}[R_t + \gamma G_{t+1}|\boldsymbol S_t=\boldsymbol s, \boldsymbol A_t=\boldsymbol a \right] \\ =& \mathbb{E}_{\boldsymbol a \sim \pi(\cdot | \boldsymbol s)}\left[ R_t + \gamma \mathbb{E}_{\boldsymbol s' \sim P(\cdot | \boldsymbol{s,a})}[ G_{t+1}|\boldsymbol S_{t+1}=\boldsymbol s' \right] \\ =& \boxed{\sum_{\boldsymbol a} \pi(\boldsymbol a| \boldsymbol s) \left( r(\boldsymbol{s,a}) + \gamma\sum_{\boldsymbol s'}P(\boldsymbol s'| \boldsymbol{s,a})V^\pi(\boldsymbol s') \right)} \end{aligned}$$

贝尔曼最优方程：

$$V^*(\boldsymbol s) = \max_{a \in A} \left\{ r(\boldsymbol {s, a}) + \gamma \sum_{s' \in S} P(\boldsymbol s' \mid \boldsymbol{s, a}) \boldsymbol{V^*(\boldsymbol s')} \right\} \\ Q^*(\boldsymbol{s, a}) = r(\boldsymbol {s, a}) + \gamma \sum_{\boldsymbol s' \in S} P(\boldsymbol s' \mid \boldsymbol{s, a}) \max_{a' \in A} \boldsymbol{Q^*(\boldsymbol s', \boldsymbol a')}$$

• 注意，由贝尔曼最优方程的推导可知，只有在满足马尔科夫性的时候最优方程才能成立

实际中的估算方式

​ 由于实际中状态转移是完全随机的，我们只能采样出大量的 $G_t,R_t$，因此我们需要用 $G_t,R_t$ 去估计 $V^\pi, Q^\pi$ 来引导策略的执行，根据 $V^\pi(\boldsymbol s), Q^\pi(\boldsymbol{s,a})$ 的定义（期望），实际中常常使用蒙特卡洛方法进行估算，例如 $V^\pi(\boldsymbol s)$：

$$V^\pi(\boldsymbol{s}) = \mathbb{E}_\pi [ G_t | \boldsymbol{S}_t=s] \approx\frac{1}{N}\sum_{i=1}^N G_t^{(i)}$$

• 值得注意的是这个需要固定策略，因为 $V^\pi$ 的值是依赖于策略的

占用度量：刻画策略行为的空间

占用度量

​ 占用度量（Occupancy Measure）是刻画策略与环境交互过程中状态-动作分布特征的指标，包含两种形式：

• 状态占用度量：设初始状态分布为 $\nu_0(\boldsymbol s)$，策略 $\pi$ 下第 $t$ 步访问状态 $\boldsymbol s$ 的概率为 $P^\pi(\boldsymbol S_t=\boldsymbol s)$。称状态 $\boldsymbol s$ 的折扣访问频率

$$\nu^\pi(\boldsymbol s) = (1-\gamma)\sum_{t=0}^\infty \gamma^t P^\pi(\boldsymbol S_t=\boldsymbol s)$$

注意这里的归一化因子是必要的，为保证 $\sum_s \nu^\pi(s) = 1$，需乘以归一化因子 $(1-\gamma)$，使得：

$$\sum_s \nu^\pi(\boldsymbol s) = (1-\gamma)\sum_{t=0}^\infty \gamma^t \underbrace{\sum_s P^\pi(\boldsymbol S_t=\boldsymbol s)}_{=1} = 1$$

• 状态-动作占用度量（可以视作强化学习的数据分布）：在状态占用度量的基础上，考虑策略的决策过程（类似 $Q^\pi$ 与 $V^\pi$ 之间的关系）：

$$\begin{aligned} \rho^\pi(\boldsymbol {s,a}) =& \mathbb{E}\left[ \sum_{t=0}^\infty \gamma^t \mathbb{I}(\boldsymbol S_t = \boldsymbol s, \boldsymbol A_t = \boldsymbol a) | \pi \right] \\ =& (1-\gamma)\sum_{t=0}^\infty \gamma^t P^\pi(\boldsymbol S_t=\boldsymbol s, \boldsymbol A_t=\boldsymbol a) \end{aligned}$$

由条件概率分解：

$$\rho^\pi(\boldsymbol{s,a}) = \underbrace{(1-\gamma)\sum_{t=0}^\infty \gamma^t P^\pi(\boldsymbol S_t=\boldsymbol s)}_{\nu^\pi(s)} \cdot \underbrace{P^\pi(\boldsymbol A_t=\boldsymbol a|\boldsymbol S_t=\boldsymbol s)}_{\pi(\boldsymbol a|\boldsymbol s)}$$

故得 $\nu^\pi(s),\rho^\pi(s,a)$ 之间的关系式（很好理解，甚至可以直接写出）：

$$\boxed{\rho^\pi(\boldsymbol{s,a}) = \nu^\pi(\boldsymbol s)\pi(\boldsymbol {a|s})}$$

Theorem 1:

智能体分别以策略 $\pi_1$ 和 $\pi_2$ 和同一个 MDP 交互得到的占用度量 $\rho^{\pi_1}$ 和 $\rho^{\pi_2}$ 满足

$$\boldsymbol{\rho^{\pi_1} = \rho^{\pi_2}} \Leftrightarrow \boldsymbol{\pi_1 = \pi_2}$$

Theorem 2:

给定一合法占用度量 $\rho$，可生成该占用度量的唯一策略是

$$\boldsymbol{\pi_\rho = \frac{\rho(s, a)}{\sum_{a'} \rho(s, a')}}$$

​ 这两个定理揭示了强化学习理论中策略空间与占用度量空间之间的同构关系。定理一指出策略与占用度量存在严格的双射对应：不同策略必然产生不同的状态-动作分布（$\rho^{\pi_1} \neq \rho^{\pi_2}$当且仅当$\pi_1 \neq \pi_2$），而定理二给出了从占用度量逆向构造策略的解析表达式$\pi_\rho(a|s)=\rho(s,a)/\sum_{a'}\rho(s,a')$。这种对应关系的核心意义体现在：

1. 表示形式的转换：策略作为条件概率分布$\pi(a|s)$，在优化过程中常面临维度灾难和策略梯度方差大的问题。而占用度量$\rho(s,a)$作为联合分布，天然满足线性约束$\sum_a\rho(s,a)=(1-\gamma)\mu_0(s)+\gamma\sum_{s',a'}\rho(s',a')P(s|s',a')$，为凸优化提供了更友好的数学结构。
2. 问题重构的桥梁：通过这种双射，可将策略搜索问题转化为占用度量空间的线性规划问题：

   $$\max_\rho \sum \rho(s,a)r(s,a) \quad \text{s.t.} \quad \rho \in \mathcal{D}$$

   其中约束集$\mathcal{D}$由贝尔曼流方程定义。这种转换将复杂的策略梯度计算简化为凸优化问题

​ 在推导时可以自由选择最适合问题特性的数学空间——需要策略显式表达时使用$\pi(a|s)$，需要分析状态-动作分布时使用$\rho(s,a)$

状态占用度量的动态方程

​ 从时间递推视角分析：

\begin{align*} \nu^\pi(s') &= (1-\gamma)\sum_{t=0}^\infty \gamma^t P^\pi(\boldsymbol S_t=\boldsymbol s') \\ &= (1-\gamma)\nu_0(\boldsymbol s') + (1-\gamma)\sum_{t=1}^\infty \gamma^t P^\pi(\boldsymbol S_t=\boldsymbol s') \end{align*}

对于 $t \geq 1$ 的情况，应用全概率公式：

$$P^\pi(\boldsymbol S_t=\boldsymbol s') = \sum_{s,a} P^\pi(\boldsymbol S_{t-1}=\boldsymbol s)\pi(\boldsymbol{\boldsymbol {a|s}})P(\boldsymbol s'|\boldsymbol {s,a})$$

代入后得：

\begin{align*} \nu^\pi(\boldsymbol s') &= (1-\gamma)\nu_0(\boldsymbol s') + \gamma(1-\gamma)\sum_{t=1}^\infty \gamma^{t-1} \sum_{s,a} P^\pi(\boldsymbol S_{t-1}=\boldsymbol s)\pi(\boldsymbol{a|s})P(\boldsymbol s'|\boldsymbol{s,a}) \\ &= (1-\gamma)\nu_0(\boldsymbol s') + \gamma\sum_{s,a} \underbrace{(1-\gamma)\sum_{\tau=0}^\infty \gamma^\tau P^\pi(\boldsymbol S_\tau=\boldsymbol s)}_{\nu^\pi(\boldsymbol s)} \pi(\boldsymbol {a|s})P(\boldsymbol s'|\boldsymbol{s,a}) \end{align*}

最终得到递归方程：

$$\boxed{\nu^\pi(s') = (1-\gamma)\nu_0(s') + \gamma\sum_{s,a}\nu^\pi(s)\pi(a|s)P(s'|s,a)}$$

在连续状态和动作空间时将求和变为积分

应用场景

应用领域	作用机理	典型案例
约束强化学习	通过占用度量约束状态分布： $\rho^\pi(s,a) \leq b(s,a)$	确保机器人避开危险区域
模仿学习	最小化专家与智能体占用度量差异： $\min_\pi D_{KL}(\rho^{expert} | \rho^\pi)$	自动驾驶行为克隆
迁移学习	分析源域与目标域占用度量差异	机械臂跨任务技能迁移
探索策略分析	计算占用度量的熵值： $H(\rho^\pi)=-\sum\rho^\pi\log\rho^\pi$	评估探索效率

深度思考：超越马尔可夫性

当面对非马尔可夫环境时，可通过扩展占用度量处理历史依赖：

$$\rho^\pi(h,a) = (1-\gamma)\sum_{t=0}^\infty \gamma^t P^\pi(H_t=h)\pi(a|h)$$

其中$h=(s_0,a_0,...,s_t)$为历史轨迹。这种扩展为处理：

• 传感器受限的POMDP问题
• 长程依赖的决策场景
• 多时间尺度任务

提供统一的分析框架，彰显占用度量理论的强大扩展能力。

关键推导的可视化表达

graph TB
    A[初始分布μ0] --> B[状态访问概率 P^\pi(S_t=s)]
    B --> C[折扣求和ν^π(s)]
    C --> D[动作分解ρ^π(s,a)=ν^π(s)π(a|s)]
    D --> E[价值函数V^π=Σρr/(1-γ)]
    B -.-> |时间递推| F[递归方程ν(s')=...]
    F --> G[对偶优化约束]