关于MARL的cheatsheet Part 1 - 最优控制（PMP，HJB，随机HJB）

Oct 6, 2024 · 学习笔记

文章目录

这是一个数学上的cheatsheet，包含最优控制理论PMP、HJB的知识，只记录了本科的数学（微积分、概率论、随机过程、数值计算、最优化理论）之外的内容，或者博主不太熟的相关内容。目的是：1）知道这个工具是解决什么问题的；2）理解关键的变量和推导背后的直觉；3）能在日后在多智能体强化学习的实践中需要用到时知道“往哪里查回去”。

解决最优控制问题主要有两大类方法：

1、变分法 (Calculus of Variations) 和庞特里亚金最大值原理 (PMP)：

它们都是基于微积分的方法，通过推导必要条件（如欧拉-拉格朗日方程、PMP 的哈密顿量最大化条件），将动态优化问题转化为求解一套微分方程和代数方程组。
更适合于开环控制的设计，即预先计算好整个过程的控制序列。

2、动态规划 (Dynamic Programming) 和哈密顿-雅可比-贝尔曼 (HJB) 方程：

基于贝尔曼最优性原理，它将复杂问题分解为一系列子问题。
更适合于闭环控制/反馈控制的设计，即控制输入是当前系统状态的函数 u(x,t)，可以应对扰动。

0 最优化理论中的KKT条件

KKT 条件，全称 Karush-Kuhn-Tucker (KKT) 条件，是一套一阶必要条件，用于判断一个解是否可能是约束优化问题的局部最优解。它们是拉格朗日乘数法的推广，不仅能处理等式约束，还能处理不等式约束。

“在满足一些正则条件（或称约束规范，如 Slater's condition）下，如果 $ x^* $ 是上述问题的一个局部最优解，那么存在一些乘子 $\lambda_i$ (对应不等式约束) 和 $\mu_j$ (对应等式约束)，使得四个条件（梯度平稳性、原始可行性、对偶可行性、互补松弛性）在 $x^*$ 点成立”

KKT 条件提供了一个框架，让我们在寻找最优解时，能够同时考虑目标函数的变化趋势和所有约束条件的影响。

必要性：在满足一些正则条件（例如 Slater 条件，它与我们之前讨论的凸集和凸函数密切相关）的情况下，KKT 条件是局部最优解的必要条件。这意味着，如果一个点是局部最优解，那么它一定满足 KKT 条件。当优化问题是凸问题时，升级为全局最优解的充分必要条件。

1 变分法

研究的是泛函的极值。核心问题是，给定一个泛函，如何找到一个特定的函数 $y^*(x)$，使得这个泛函的值达到最大或最小。

1.1 泛函

常见是积分形式:

$$ J[y(x)] = \int_{x1}^{x2} L(x, y(x), y^{\prime}(x)) dx $$

L被称为拉格朗日量（Lagrangian）

1.2 欧拉-拉格朗日方程

一个找到使泛函达到极值的函数的必要条件。

即在最优路径上，函数值和其变化率之间的平衡点必须满足这个关系：

$$ \frac{\partial L}{\partial y} - \frac{d}{dx}\left(\frac{\partial L}{\partial y'}\right) = 0 $$

1.3 横截条件

欧拉-拉格朗日方程是在边界条件固定的情况下推导出来的（比如，从A点到B点，A和B是固定的）。

当一个或两个端点是自由的，或者必须落在某个给定曲线上时，除了欧拉-拉格朗日方程外，还必须满足额外的条件，这些条件就叫做横截条件。

1.4 Legendre 条件

欧拉-拉格朗日方程和横截条件都只是必要条件，它们找到的函数可能是使泛函取最大值、最小值，甚至是鞍点的函数。Legendre 条件是用来帮助我们判断找到的极值是最小值还是最大值的二阶条件。

比如局部最小值：

$$ \frac{\partial^{2}L}{\partial(y^{\prime})^{2}} \geq 0 $$

2 庞特里亚金最大值原理 (Pontryagin's Maximum Principle, PMP)

2.0 PMP

PMP 最终会给出三组微分方程和代数方程，它们是求解最优控制问题的必要条件.

PMP 提供了一个必要条件，用于找到受控动态系统从一个状态转移到另一个状态的最优控制策略。它不像变分法那样直接操作泛函，而是引入了协态变量和哈密顿函数，将问题转化为一个类似于 KKT 条件的形式，但针对的是动态系统。

核心结论：在最优控制 $u^*(t)$ 下，哈密顿函数在几乎所有时刻都必须达到其最大值

$$ H(x^*(t), u^x(t), \lambda^{*}(t), t) = \max_{u \in U} H(x^{*}(t), u, \lambda^{*}(t), t) $$

PMP 最终会给出三组微分方程和代数方程，它们是求解最优控制问题的必要条件。以及末端条件（横截条件）用于确定协态变量子终端时刻的边界值。即给定了T时刻的 $\lambda$

2.1 协态变量

$\lambda(t)$ 它们衡量了在某个时刻t，如果系统状态发生微小变化，会对最终的总成本（或总收益）产生多大影响。协态变量是随时间变化的动态变量，它们满足一组独立的微分方程，我们称之为协态方程。

协态变量通常定义为性能指标对状态变量的偏导数：

$$ \lambda(t) = \frac{\partial{J}}{\partial{x(t)}} $$

其中 $J$ 是要优化的性能指标， $x(t)$ 是系统的状态变量。

2.2 哈密顿函数

$H(x, u, \lambda, t)$ PMP 的核心思想就是：在每一个时刻，都要选择一个控制输入 $u(t)$，使得这个哈密顿函数达到最大值。

$$ H(x, u, \lambda, t) = L(x,u,t) + \lambda^{T}(t)f(x,u,t) $$

L是瞬时成本函数，表示时刻t的即时成本。f是系统动力学方程/状态方程。$\lambda$时协态变量，$\lambda^{T}(t)f(x,u,t)$ 表示当前状态变化对未来变化的累积影响。

2.3 其他背景

PMP是开环方法，即不依赖于系统实时状态反馈，即 $u^*(t)$ 只依赖时间，里面不用输入 $x$

求解过程需要先解出状态轨迹 $x^{*}(t)$ 和协态轨迹 $\lambda^{*}(t)$ . 求解一般用打靶或者迭代。

状态方程是一个初始值问题 (Initial Value Problem, IVP)：从已知起点 $x(t_0)$ 开始，向前积分得到 $x(t)$

协态方程是一个终端值问题 (Terminal Value Problem)：从已知终点 $λ(t_f)$ 开始，向后积分得到 $λ(t)$。

2.4 部分应用

经典的两点边值问题：

1、行星轨道计算：知道探测器发射时的位置和速度，以及它在某个未来时间点要到达的位置（比如火星），计算中间的轨道轨迹。

2、桥梁设计中的悬链线问题：确定在给定两端点和总长度下，悬挂链条的形状（最小势能）。

3、弹性力学：求解梁或板在两端受力或位移约束下的变形。

4、化学反应过程控制：在给定初始和最终浓度的条件下，优化温度曲线以最大化产率。

与RL没有明确联系，但是提供了启发：

1、最优控制 (Inverse Optimal Control, IOC)（通过观测到的专家行为，即一段最优控制策略的样本，反推专家在执行这些行为时，内心所遵循的奖励函数），PMP在此给出了一个必要条件，可作为一个过滤器使用，即IOC的算法可以尝试许多不同的奖励函数，然后利用PMP来验证。

2、协态变量可以告诉反映在整个过程中，哪些状态变量的变化是真正有价值的，以及它们的价值有多大，从而用于设计更精细的奖励。例如：“每靠近终点一单位距离 +0.5”，或者“每避开一个障碍物 +2”

3 哈密顿-雅可比-贝尔曼 (HJB) 方程

3.1 HJB

HJB的推导是将离散时间的贝尔曼方程推广到连续时间。即对 $\Delta t$ 取0的极限。随后PMP和HJB可以互相推导。

HJB的核心是引入了一个价值函数 $V(x, t)$ 表示从状态 $x$ 在时间 $t$ 开始，到 $T$ 时所能获得的最小代价。

$$ V(x,t) = \min_{u}{\int_{t}^{T}{L(x(s), u(s), s)ds + E(x(T))}} $$

$L(·)$ 即时代价， $E(·)$ 终端代价。

对于确定性系统（即系统动力学给定），HJB如下：

$$ -\frac{\partial{V}}{\partial{t}}(x,t) = \min_{u}{L(x,u,t)+\nabla{V}(x,t)\cdot{f(x,u,t)}} $$

等式右边第一项可理解为瞬时代价，第二项表示由于状态变化而引起的未来代价的变化率。

3.2 HJB建模的完整流程

1、领域知识与系统动力学 $f(x,u,t)$ 的确立：

定义状态变量 $x(t)$ ：确定哪些变量能完整描述agent所处的环境在某一时刻的状态。
确立系统动力学 $f(x,u,t)$ ：根据物理定律、工程原理、经济模型或任何相关领域知识，来建立一个数学方程，描述agent的状态 $x(t)$ 如何随时间变化，以及如何受其行动 $u(t)$ 和时间 $t$ 的影响。即 $\dot{x} = f(x(t), u(t), t)$
定义动作 $u(t)$ ： agent可以做那些动作来影响状态。

2、定义代价函数 $L(x,u,t)$ 和 $E(x(T))$

即时代价 $L(x,u,t)$：描述agent在某一瞬时、某一状态下执行某一行动所付出的代价（例如，能源消耗、时间流逝、偏离理想路径的惩罚）。

终端代价 $E(x(T))$：描述在系统终止时，agent 最终状态所产生的代价（例如，未完成任务的罚款，最终产品质量的奖励）。

agent的学习目标就是最小化这个总的代价函数。

3、构建 HJB 方程：

有了系统动力学 $f$ 和代价函数 $L$ , $E$ ，就可以根据 HJB 方程的通用形式来构建针对特定问题的 HJB 方程了。这一步将最优控制问题从“寻找最优轨迹”转化为“求解偏微分方程”。

4、求解 HJB 方程以得到价值函数 $V(x,t)$ ：

解析解：只有在非常简单且理想化的模型中才能找到。

近似求解（数值方法）：在绝大多数实际应用中，由于 HJB 方程的非线性和高维性，得不依赖数值方法（如有限差分法、有限元法、深度学习方法等）来近似地求解 $V(x,t)$ 。这个 $V(x,t)$ 就是价值函数，它代表了从状态 $x$ 在时间 $t$ 开始，按照最优策略所能达到的最小未来总代价。

5、提取最优策略并指导 agent 行动：

一旦有了（近似的）价值函数 $V(x,t)$ ，agent 就可以根据这个函数来做出决策：

最优策略 $u^{*}(x,t)$ ： HJB 方程的关键在于其右侧的最小化（或最大化）操作。通过对 HJB 方程右侧表达式中的控制变量 $u$ 求导并令导数为零（如果可行），或者通过数值搜索，我们可以得到一个最优的反馈控制律 $u^{*}(x,t)$ .

agent 输出 action：这个 $u^{*}(x,t)$ 就是 agent 在当前状态 $x$ 和当前时间 $t$ 下应该采取的最佳行动。agent 依据这个策略实时地输出其行动，从而实现其最小化代价的目标。

3.3 HJB求解

HJB 方程是一个非线性偏微分方程.

1、解析解：

只有在非常特殊和简单的情况下才能找到解析解，例如线性系统和二次性能指标 (Linear Quadratic Regulator, LQR) 问题。LQR 问题的 HJB 方程可以简化为黎卡提方程 (Riccati Equation)，它是一个常微分方程，可以有解析解或数值解。

解析解非常强大，因为它能给出全局最优解和闭环控制律（即 $u^{*}(x,t)$ 。

2、数值解：

对于大多数非线性或高维问题，HJB 方程没有解析解，必须依靠数值方法。

网格法 (Grid-based Methods)：将状态空间和时间离散化，在每个网格点上近似求解 HJB 方程。但是，这种方法会面临“维度灾难 (Curse of Dimensionality)”，即随着状态变量数量的增加，网格点的数量呈指数级增长，计算变得不可行。

近似动态规划 (Approximate Dynamic Programming, ADP) 或强化学习 (Reinforcement Learning, RL)：这些是处理高维 HJB 方程的现代方法。它们通过函数逼近器（如神经网络）来近似价值函数 $V^{*}(x,t)$ 或最优策略，从而避免了维度灾难。RL 算法（如 Q-learning, Actor-Critic）本质上就是在不完全知道系统动力学的情况下，寻找 HJB 方程的近似解。

3.4 HJB与RL

其实没有什么关系。

HJB方程的“形式”本身，在RL的model-free方法（不需要预先知道精确的系统动力学f或者即时代价L）中不再需要显式地被写出来或者直接求解。并且，HJB 方程是连续时间最优控制领域的工具，它将贝尔曼最优性原理用偏微分方程的形式表达出来。而强化学习，尤其是日常讨论的马尔可夫决策过程（MDP）框架下的RL，通常是建立在离散时间的基础上的。

贝尔曼最优性原理是 RL 的核心思想，它认为：

最优策略具有这样的性质：无论过去的状态和决策如何，剩余的决策都必须是针对由过去决策所形成的状态的最优决策。

在离散时间下，这个原理直接引出了贝尔曼方程（Bellman Equation）和贝尔曼最优方程（Bellman Optimality Equation）。

贝尔曼方程：描述了在给定策略下，一个状态的价值（或Q值）与其后续状态的价值之间的关系。

贝尔曼最优方程：描述了最优策略下，一个状态的最优价值与其后续状态的最优价值之间的关系。

几乎所有的现代 RL 算法，无论是 Q-learning、SARSA、DQN、Policy Gradients、Actor-Critic 等，都是基于这些离散时间的贝尔曼方程家族来设计和推导的。它们的目标都是通过迭代更新或函数逼近的方式，来找到满足贝尔曼最优方程的价值函数或最优策略。

HJB 方程更像是贝尔曼最优方程在连续时间确定性系统下的一个“高级表亲”。它在理论上提供了连续时间最优控制的严格数学框架，并且在某些特定情况下（如状态和动作空间连续，动力学已知且精确）可以作为分析工具。

所以，知道 HJB 方程只是有助于更深入地理解最优控制的理论全貌，认识到离散和连续时间问题的内在联系。对于处理连续时间、模型已知的复杂系统，HJB 方程是直接的分析工具。对于RL，没有什么直接关系。

3.5 PMP 与HJB

PMP是从变分法和两点边值问题来的，基于轨迹优化视角，必要条件。寻找最优轨迹和控制策略。状态 $x(t)$ 是作为时间和控制 $u(t)$ 的函数（ $\dot{x}(t)=f(x(t),u(t),t) $ ）考虑的而不是 $u$ 的自变量。

而HJB与经典物理学中的 Hamilton-Jacobi (HJ) 方程有着深刻的联系.

物理学中的 HJ 方程是基于变分原理（如最小作用量原理）推导出来的，它寻找使某个物理量（作用量）达到最小或最大的路径。
HJB 方程则是在最优控制的背景下，寻找使某个性能指标（成本函数）最小或最大的控制策略和轨迹。两者都涉及到在一个函数空间中寻找“最优”的解。
在物理学中，HJ 方程的解是作用量，它代表了系统沿某一路径所积累的“成本”或“能量”。
在最优控制中，HJB 方程的解是值函数，它代表了从某个点到目标的最优“成本”或“收益”。两者在概念上和数学结构上具有高度的相似性。可以将物理中的作用量类比为最优控制中的值函数。

HJ 方程是经典力学的一种重新表述，与牛顿定律、拉格朗日力学和哈密顿力学等价。它是一个一阶非线性偏微分方程，描述了物理系统在时间上的演化。HJ 方程的一个重要特点是它将粒子运动与波传播联系起来，这在经典力学向量子力学的过渡中扮演了关键角色，被认为是经典力学最接近量子力学的地方。

HJ 方程是一个关于系统作用量 S 的偏微分方程，其形式是将作用量对时间的偏导数加上哈密顿量等于零。： $$ \frac{\partial{S}}{\partial{t}} + H(q_1, ..., q_N, \frac{\partial{S}}{\partial{q_1}}, ..., \frac{\partial{S}}{\partial{q_N}}, t) = 0 $$

其中，$S(q_1, ..., q_N, t)$ 是哈密顿主函数，也被称为作用量（action）。它是广义坐标 $q_i$ 和时间 $t$ 的函数。 $S=\int_{t_1}^{t_2}{L(q(t), \dot{q}(t), t) dt}$ 其中，$L=T-V$ 是拉格朗日量，$T$ 是动能，$V$ 是势能, $q(t)$ 是系统的广义坐标轨迹。

$H$ 是系统的哈密顿量（广义坐标 $q_i$, 广义动量 $p_i$ 和时间 $t$ 的函数 $H(q_i, p_i, t)$ ）. $p_i = \frac{\partial{S}}{\partial{q_i}}$

作用量沿着实际物理轨迹是‘稳态’的，这是由于最小作用量原理（也被称为哈密顿原理）指出：在所有可能的连接两个给定端点（例如，在 $t_1$ 时刻的 $q_1$ 和在 $t_2$ 时刻的 $q_2$）的路径中，系统实际遵循的路径是使得作用量 S 的一阶变分为零的路径。

HJ 方程正是这个最小作用量原理的直接推论。它的解 $S(q,t)$ 被称为哈密顿主函数，这个函数包含了系统所有可能的实际轨迹的信息。通过求解 HJ 方程，我们可以得到系统的动量 $p_i = \frac{\partial{S}}{\partial{q_i}}$ 和能量 $E = -\frac{\partial{S}}{\partial{t}}$ ，进而描述系统的完整动态。

4 随机最优控制与HJB方程

4.1 新的数学工具：伊藤积分 (Itô Integral)、随机微分方程（Stochastic Differential Equations, SDEs）

在随机最优控制中，系统的演化路径会受到随机噪声的影响，我们只能知道其演化的统计特性，需要使用新的数学工具来描述这种不确定性。

1、伊藤积分

因为随机过程通常是不可微的，统的微积分（黎曼积分）无法直接处理随机过程的积分。伊藤积分的定义与黎曼积分类似，也是通过黎曼和的极限来构建的，但其关键区别在于采样点的选择。

伊藤等距同构 它给出了伊藤积分的平方期望

2、随机微分方程

SDEs 是用来描述受随机噪声影响的动态系统的方程。它们是传统常微分方程 (ODEs) 在引入随机项后的推广。

一般形式： $$ dX(t) = f(X(t), u(t), t)dt + g(X(t), u(t), t)dW(t) $$

其中：

$X(t)$ ：系统的状态变量（现在通常是大写，表示它是随机过程）。
$f(X(t), u(t), t)dt$ ：漂移项 (Drift Term)，对应于确定性系统中的动力学，描述了状态的平均变化趋势。
$g(X(t), u(t)$ ：扩散项 (Diffusion Term)，描述了随机噪声对系统状态的影响程度（或波动性）。
$dW(t)$ ：维纳过程 (Wiener Process) 或布朗运动 (Brownian Motion) 的微分，代表了连续时间下的随机冲击或噪声。

3、伊藤引理

随机微积分中最核心的公式，被称为随机过程中的“链式法则” 不同于传统积分的地方是额外的二阶项。这是由于高阶无穷小在此不能忽略了（$dW(t)^2$ 不是零）。

表述：如果 $dX(t) = f(X(t), u(t), t)dt + g(X(t), u(t), t)dW(t)$ ，且 $G(X, t)$ 是一个二阶连续可微的函数，那么 $G(X, t)$ 的微分 $dG(X, t)$ 为：

$$ dG(X,t) = \left( \frac{\partial G}{\partial t} + \frac{\partial G}{\partial X} f(X,t) + \frac{1}{2} \frac{\partial^2 G}{\partial X^2} g^2(X,t) \right) dt + \frac{\partial G}{\partial X} g(X,t) dW(t) $$

伊藤引理告诉我们，一个随机过程的函数如何演变。最重要的特点是多了一个二阶导数项 $\frac{1}{2} \frac{\partial^2 G}{\partial X^2} g^2(X,t) dt$ ，这个项反映了随机性（扩散项 g）对函数均值演变的影响，它与随机过程的波动性密切相关。

4.2 随机HJB方程

推导思路：

1、同样定义一个最优价值函数 $V^{*}(x,t)$ ，表示从状态 $x$ 和时间 $t$ 开始，最优控制下获得的未来期望总成本。

2、应用贝尔曼最优性原理在一个微小时间间隔 Δt 上，考虑当前成本和未来期望价值。

3、关键在于，在展开 $V^{*}(X(t+\Delta{t}),t + \Delta{t})$ 时，需要使用伊藤引理，而不是泰勒展开。

4、取 $Δt→0$ 的极限，最终得到随机 HJB 方程。

$$ -\frac{\partial V}{\partial t}(x,t) = \min_u \left[ L(x,u,t) + \frac{\partial V}{\partial x}(x,t) \cdot f(x,u,t) + \frac{1}{2} g^T(x,u,t) \frac{\partial^2 V}{\partial x^2}(x,t) g(x,u,t) \right] $$

其中，$\frac{\partial^2 V}{\partial x^2}(x,t)$ 是价值函数V的海森矩阵。$g^T\frac{\partial^2 V}{\partial x^2}(x,t) g$ 是二次项，是伊藤引理中额外项的体现，代表了随机性对最优价值函数演化的贡献。