Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs¶

会议: NeurIPS 2026
arXiv: 2605.24939
论文: https://arxiv.org/abs/2605.24939
领域: 强化学习
关键词: 强化学习, 策略梯度, 熵正则化, 线性收敛, 线性函数逼近

一句话总结¶

针对一般连续状态与动作空间下的熵正则化马尔可夫决策过程，证明了在价值函数可实现性与特定特征基条件下，对数线性 Softmax 策略梯度流具有非均匀 PŁ 不等式与基于李雅普诺夫径向无界性的全局线性收敛性。

研究背景与动机¶

策略梯度（Policy Gradient, PG）方法是强化学习与 Actor-Critic 架构的理论基石，而 Softmax 参数化形式因其自然输出概率分布并能通过熵正则化保持探索性，在连续控制与离散决策中得到了极为广泛的应用。然而，Softmax 策略中的归一化分母使得目标价值函数关于策略参数呈现出高度的非凸性，甚至在简单的多臂老虎机或具有凸代价与线性动力学的环境中，优化目标依然非凸。经典理论大多集中于有限状态动作空间的表格型（Tabular）MDP，在引入香农熵或 KL 散度正则化后，先前的突破性工作（如 Mei et al., 2020）利用非均匀 Polyak–Łojasiewicz（PŁ）不等式结合梯度沿动作坐标和为零的几何守恒律，成功建立了表格环境下的全局线性收敛速率 $\mathcal{O}(e^{-Ct})$。

但当状态与动作空间扩展至大规模或连续空间时，表格型参数化彻底失效，必须借助特征线性逼近或神经网络对对数策略密度进行参数化。此时表格分析的数学工具链全面瓦解：其一，在连续动作空间下，策略参数 $\theta$ 作用于整条条件对数密度曲面上，无法再将梯度按离散动作逐点分离，先前证明动作概率逐点有正下界的坐标守恒技术无法适用；其二，由于状态与动作无穷维，策略梯度流的非均匀 PŁ 不等式常数严重依赖于 Fisher 信息矩阵（FIM）或未中心化特征协方差矩阵的最小特征值退化；其三，传统的表格熵在全支撑测度下天然有界，根本无法直接充当阻止参数发散的李雅普诺夫函数。

为了突破表格型假设的局限，本文致力于解决一般波兰状态空间和紧致动作空间上、带有线性函数逼近的对数线性 Softmax 策略梯度流全局收敛性难题。核心 idea：在价值函数可实现性前提下推导连续状态动作空间的非均匀 PŁ 梯度支配不等式，并首次将 KL 正则化项本身证明为具有径向无界性的李雅普诺夫函数，从而在满仿射展跨特征与单纯形特征两种实用基函数机制下，严格锁定参数轨迹在紧集内并给出 Fisher 矩阵特征值的正下界，首次将熵正则化 Softmax 策略梯度的全局线性收敛证明拓展至非表格型 MDP。

方法详解¶

整体框架¶

本文考虑折扣无限时域熵正则化 MDP 模型 $(S,A,P,c,\gamma,\tau,\mu)$，其中状态空间 $S$ 为波兰空间，动作空间 $A$ 为紧致波兰空间，$\mu$ 为动作空间上的满支撑参考概率测度，$\tau > 0$ 为熵正则化强度。对任意随机策略 $\pi \in \mathcal{P}(A|S)$，正则化性能目标为： $$V_\tau^\pi(\rho) = \mathbb{E}\left[\sum_{n=0}^\infty \gamma^n \left(c(s_n, a_n) + \tau \log \frac{d\pi}{d\mu}(a_n|s_n)\right)\right]$$ 当采用线性特征基 $g: S \times A \to \mathbb{R}^p$ 对对数密度进行参数化时，策略定义为 $\pi_\theta(da|s) \propto \exp(\langle \theta, g(s,a)\rangle)\mu(da)$。策略梯度流沿连续时间演化 $\frac{d}{dt}\theta_t = -\nabla_\theta V_\tau^{\pi_{\theta_t}}(\rho)$。整体理论构建流程包含四个核心环节：性能差分与对偶近端展开、非均匀 PŁ 不等式的代数推导、特征基正定性及 KL 散度径向无界性李雅普诺夫分析、以及 Grönwall 引理下的全局线性收敛性闭环。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["连续状态/紧致动作 MDP<br/>对数线性 Softmax 策略 π_θ"] --> B["Q_τ^π 可实现性与性能差分<br/>建立近端策略与参数对偶映射"]
    B --> C["非均匀 PŁ 不等式推导<br/>建立梯度范数与次优差距的支配关系"]
    C --> D["特征机制与李雅普诺夫分析<br/>证明 KL 径向无界锁定参数有界轨道"]
    D --> E["最小特征值一致正下界<br/>λ_min(FIM) 或未中心化协方差矩阵"]
    E --> F["全局指数线性收敛<br/>次优差距按 O(exp(-C t)) 衰减"]

关键设计¶

1. Q-可实现性驱动的非均匀 PŁ 梯度支配不等式

在连续状态动作空间中，价值函数对参数呈现非凸形态，无法直接应用强凸性或标准均匀 PŁ 条件。本文引入 $Q_\tau^\pi$-可实现性假设（Assumption 1）：对任意策略 $\pi \in \Pi_\mu$，均存在唯一参数 $\boldsymbol{\theta}(\pi) \in \mathbb{R}^p$ 使得 $\langle \boldsymbol{\theta}(\pi), g(s,a)\rangle = -\frac{1}{\tau} Q_\tau^\pi(s,a)$（例如在带转移核分解的线性 MDP 中严格成立）。通过性能差分引理与近端策略对偶展开，推导得出梯度向量具有显式的 Fisher 算子作用形式： $$\nabla_\theta V_\tau^{\pi_\theta}(\rho) = \frac{\tau}{1-\gamma} \int_S G^{\pi_\theta}(s) d_\rho^{\pi_\theta}(ds) \cdot (\theta - \boldsymbol{\theta}(\pi_\theta))$$ 其中 $G^{\pi_\theta}(s) = \int_A \nabla \log \frac{d\pi_\theta}{d\mu}(a|s) (\nabla \log \frac{d\pi_\theta}{d\mu}(a|s))^\top \pi_\theta(da|s)$ 为 Fisher 信息矩阵（FIM）。结合对数似然梯度的局部 Lipschitz 连续性与 KL-logit 夹逼定理，建立了非均匀 PŁ 不等式： $$0 \le V_\tau^{\pi_\theta}(\rho) - V_\tau^{\pi^*}(\rho) \le C_R(\theta) \|\nabla_\theta V_\tau^{\pi_\theta}(\rho)\|_2^2$$ 这里的依赖系数 $C_R(\theta)$ 核心取决于沿最优状态占优测度 $d_\rho^{\pi^*}$ 积分的 Fisher 信息矩阵最小特征值 $\lambda_{\min}(G^{\pi_\theta}(s))$（或在单纯形特征下的未中心化协方差最小特征值）。

2. 满仿射展跨特征与 KL 散度径向无界性

非均匀 PŁ 不等式的瓶颈在于：如果参数轨迹 $\|\theta_t\|_2 \to \infty$，策略概率可能退化导致 Fisher 矩阵奇异，使常数 $C_R(\theta_t)$ 爆炸趋于无穷，从而退化甚至丧失收敛速率。为此，本文设计了基于李雅普诺夫函数的参数紧集包络方案。由于沿梯度流 $\frac{d}{dt}V_\tau^{\pi_{\theta_t}}(\rho) = -\|\nabla V_\tau^{\pi_{\theta_t}}(\rho)\|_2^2 \le 0$，价值函数天然单调不增，其径向无界性直接取决于熵正则化项 $\text{KL}(\pi_\theta(\cdot|s)|\mu)$。本文提出了满仿射展跨特征假设（Assumption 2）：对任意单位方向向量 $u \in \mathbb{S}^{p-1}$，均值集合测度 $\mu(\arg\max_{a \in A} u^\top g(s,a)) = 0$（即最大值点集测度为零）。通过大偏差理论与二元划分性质，严格证明了： $$\lim_{\|\theta\|_2 \to \infty} \text{KL}(\pi_\theta(\cdot|s)|\mu) = \infty$$ 由此，有界的初始价值面迫使梯度流参数轨迹 $\{\theta_t\}_{t \ge 0}$ 终身囚禁在紧子集内，对数密度上下界 $\sup_{t \ge 0} |\log \frac{d\pi_{\theta_t}}{d\mu}|_{B_b(S \times A)} < \infty$ 一致保持。以无常数傅里叶模态的三角多项式特征（Example 1）为例，由于解析函数零点集测度为零，天然满足该机制。

3. 单纯形特征机制与未中心化协方差下界分析

在概率单纯形特征基（即 $\sum_{i=1}^p g_i(s,a) = 1$ 且 $g(s,a) \ge 0$，例如伯恩斯坦多项式基 Bernstein polynomials）下，全仿射独立性不成立，常数向量 $\mathbf{1}$ 必然位于 Fisher 信息矩阵的零空间中（$G^{\pi_\theta}(s)\mathbf{1} = \mathbf{0}$）。此时 FIM 的最小特征值恒等于零。为此，本文证明了在该特征族下，策略梯度正交于全 1 向量，即 $\frac{d}{dt}(\mathbf{1}^\top \theta_t) = 0$。在正交子空间 $\theta_\perp = \theta - p^{-1}(\mathbf{1}^\top \theta)\mathbf{1}$ 上，本文证明了 KL 散度对于 $\|\theta_\perp\|_2 \to \infty$ 的径向无界性。更关键的是，利用矩阵秩 1 扰动的特征值交错定理（Eigenvalue Interlacing Theorem），将中心化 FIM 的半正定退化转化为未中心化特征协方差矩阵的分析： $$\|G^{\pi_\theta}(s) y_\perp\|_2 \ge \lambda_{\min}\left(\int_A g(s,a)g(s,a)^\top \pi_\theta(da|s)\right) \|y_\perp\|_2$$ 只要初始协方差矩阵严格正定，结合概率比值测度下界传递性，即可推导出积分特征值下界 $\inf_{t \ge 0} \lambda_{\min}(\int g g^\top \pi_{\theta_t}) \ge \lambda > 0$，成功克服单纯形基的秩亏损问题。

损失函数 / 训练策略¶

优化轨迹由连续时间策略梯度动力系统驱动： $$\frac{d}{dt}\theta_t = -\nabla_\theta V_\tau^{\pi_{\theta_t}}(\rho)$$ 其中连续梯度的显式形式满足对数似然得分函数期望。在离散化实现时，通过精确或可实现的批评者拟合 $Q_\tau^{\pi_t}$ 并执行自然步长更新。收敛性分析通过将微分不等式 $\frac{d}{dt}[V_\tau^{\pi_{\theta_t}}(\rho) - V_\tau^{\pi^*}(\rho)] \le -C_{\theta_0}^{-1} [V_\tau^{\pi_{\theta_t}}(\rho) - V_\tau^{\pi^*}(\rho)]$ 代入 Grönwall 引理积分，直接锁定目标函数收敛上界： $$0 \le V_\tau^{\pi_{\theta_t}}(\rho) - V_\tau^{\pi^*}(\rho) \le e^{-t C_{\theta_0}^{-1}} (V_\tau^{\pi_{\theta_0}}(\rho) - V_\tau^{\pi^*}(\rho))$$ 其中收敛常数 $C_{\theta_0}$ 显式依赖于初值分布容许度 $|\frac{dd_\rho^{\pi^*}}{d\rho}|_{B_b(S)}$、折扣因子 $\gamma$、温度参数 $\tau$、以及初值特征值积分 $\lambda$。

实验关键数据¶

主实验：理论收敛率与各类特征基收敛性质对比¶

本文为纯数学理论与分析论文，其核心定量结果体现为在不同函数逼近特征基机制下建立的收敛阶次、李雅普诺夫有界性与退化矩阵特征值下界：

特征基类型 (Feature Basis)	适用动作/状态空间	核心几何假设	判别算子特征值下界	目标收敛速率 $V_\tau^{\pi_t} - V_\tau^*$	关键收敛依赖常数 $C_{\theta_0}^{-1}$
表格参数化 (Tabular Baseline)	有限离散 $S \times A$	满自由度独立坐标	$\inf_t \min_{s,a} \pi_t(a\\|s) > 0$	$\mathcal{O}(e^{-Ct})$ (线性收敛)	$C \propto \tau (1-\gamma)^2 \min_{s,a} \pi_0(a\\|s)$
全仿射展跨特征 (Full Affine Span)	连续紧致 Polish $S \times A$	$\mu(\arg\max u^\top g) = 0$	$\lambda_{\min}(G^{\pi_{\theta_t}}(s)) \ge \lambda > 0$	$\mathcal{O}(e^{-C_{\theta_0}^{-1} t})$ (全局线性)	依赖 $e^{-R - 2\\|\theta_0\\|_2} \lambda_{\min}(G^{\pi_{\theta_0}})$
单纯形特征 (Simplex / Bernstein)	连续紧致 Polish $S \times A$	$\sum g_i = 1, g \ge 0, u \perp \mathbf{1}$	$\lambda_{\min}(\int g g^\top \pi_{\theta_t}) \ge \lambda > 0$	$\mathcal{O}(e^{-C_{\theta_0}^{-1} t})$ (全局线性)	依赖 $e^{-R - 2\\|\theta_0\\|_2} \lambda_{\min}(\int g g^\top \pi_{\theta_0})$
非正则化标准 PG (Vanilla PG)	连续线性逼近	仅梯度有界	特征值退化趋零	$\mathcal{O}(1/t)$ (亚线性收敛)	不具备全局指数加速能力

消融实验：特征基选择对 KL 散度径向无界性的消融分析¶

论文特别针对特征基的几何结构（零测度最大值点集假设）构造了解析计算消融，深入剖析了为何不是任意特征都能诱发径向无界性：

特征基设计配置	基函数定义	最大值点集测度 $\mu(\mathcal{A}_\theta)$	$\lim_{\\|\theta\\| \to \infty} \text{KL}(\pi_\theta\\|\mu)$	是否满足径向无界	能否支撑全局线性收敛
三角多项式特征 (Example 1)	傅里叶基 $\cos(k^\top a + \ell_k^\top s), \sin$	零测度 ($\mu=0$，解析函数零点)	$+\infty$ (对数发散)	是 (满足 Assumption 2)	保证全局线性收敛
伯恩斯坦多项式 (Example 2)	单纯形基 $b_{\ell, k}(h(s,a))$	零测度 ($\mu=0$，超平面零集)	$+\infty$ (正交子空间发散)	是 (满足 Assumption 4)	保证全局线性收敛
有限元帽函数 (Example 3/4 消融)	一维 P1 有限元网格基函数	正测度 ($\mu([\frac{1}{3}, \frac{2}{3}]) = \frac{1}{3} > 0$)	收敛至常数 $\log 3 < \infty$	否 (彻底丧失无界性)	无法排除参数逃逸与奇异退化

关键发现¶

非均匀常数的可控性：虽然 Softmax 参数化破坏了全局均匀强凸性或均匀 PŁ 支配，但只要策略不塌缩到测度为零的极端边界，参数轨迹就会被李雅普诺夫能级所限制，从而使非均匀 PŁ 常数在整个梯度流积分路径上保持一致正下界。
帽函数失效根因：帽函数消融实验表明，当基函数在某个正测度区间上达到平顶最大值时，吉布斯测度在该区间均匀分布，极限 KL 散度严格趋向有限常数 $\log 3$；只有解析多项式等具有零测度极大值集的基函数，才能迫使吉布斯测度发生狄拉克激元式的完全塌缩，从而驱使 KL 散度走向无穷大。

亮点与洞察¶

从离散守恒到泛函李雅普诺夫：摆脱了表格 MDP 深度依赖离散坐标偏导数之和为零的局限，首次利用熵正则化项本身的分析性质构建李雅普诺夫函数，将连续动力系统的紧致集分析与强化学习收敛性无缝结合。
矩阵交错巧妙破除单纯形退化：在单纯形基导致 Fisher 信息矩阵天然降秩的困境下，巧妙结合矩阵秩 1 摄动的交错定理，跳过奇异的 FIM，直接以下层未中心化二阶矩协方差矩阵建立正定性保障。
可复用的泛函优化范式：本文建立的“性能差分 $\to$ 对偶 KL 展开 $\to$ 算子特征值控制 $\to$ 李雅普诺夫紧致性”技术框架，可直接迁移到连续时间非线性控制、连续空间强化学习 Actor-Critic 收敛证明以及流匹配策略优化分析中。

局限与展望¶

可实现性假设较强：理论完全建立在 $Q_\tau^\pi$-可实现性假设之上，对于深度神经网络等存在逼近误差（Function Approximation Error）的场景，尚需进一步引入分布偏移与不可逼近残差项。
聚焦于连续时间梯度流：论文主要证明了连续时间梯度流（ODE）的指数收敛，实际工程使用的离散步长欧拉法（离散时间 PG）需要额外的步长选择与平滑性分析以避免超调震荡。
积分常数依赖隐式上界：常数 $C_{\theta_0}$ 包含指数项 $e^{-R}$，在极端探索要求或高维复杂特征空间中，该常数可能存在较大的尺度因子，未来可探索更紧致的局部曲率估计。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次克服非表格连续空间的 Fisher 矩阵退化问题，建立对数线性 Softmax PG 的全局线性收敛性。
实验充分度: ⭐⭐⭐⭐☆ 纯理论数学论证严谨详实，并配有精巧的反例（帽函数）解析消融证明假设的必要性。
写作质量: ⭐⭐⭐⭐⭐ 测度论与泛函分析表述规范，定理与引理推导逻辑清晰。
价值: ⭐⭐⭐⭐⭐ 为强化学习核心算法在连续空间的理论奠基补齐了重要拼图。

特征基类型 (Feature Basis)	适用动作/状态空间	核心几何假设	判别算子特征值下界	目标收敛速率 \(V_\tau^{\pi_t} - V_\tau^*\)	关键收敛依赖常数 \(C_{\theta_0}^{-1}\)
表格参数化 (Tabular Baseline)	有限离散 \(S \times A\)	满自由度独立坐标	\(\inf_t \min_{s,a} \pi_t(a\\|s) > 0\)	\(\mathcal{O}(e^{-Ct})\) (线性收敛)	\(C \propto \tau (1-\gamma)^2 \min_{s,a} \pi_0(a\\|s)\)
全仿射展跨特征 (Full Affine Span)	连续紧致 Polish \(S \times A\)	\(\mu(\arg\max u^\top g) = 0\)	\(\lambda_{\min}(G^{\pi_{\theta_t}}(s)) \ge \lambda > 0\)	\(\mathcal{O}(e^{-C_{\theta_0}^{-1} t})\) (全局线性)	依赖 \(e^{-R - 2\\|\theta_0\\|_2} \lambda_{\min}(G^{\pi_{\theta_0}})\)
单纯形特征 (Simplex / Bernstein)	连续紧致 Polish \(S \times A\)	\(\sum g_i = 1, g \ge 0, u \perp \mathbf{1}\)	\(\lambda_{\min}(\int g g^\top \pi_{\theta_t}) \ge \lambda > 0\)	\(\mathcal{O}(e^{-C_{\theta_0}^{-1} t})\) (全局线性)	依赖 \(e^{-R - 2\\|\theta_0\\|_2} \lambda_{\min}(\int g g^\top \pi_{\theta_0})\)
非正则化标准 PG (Vanilla PG)	连续线性逼近	仅梯度有界	特征值退化趋零	\(\mathcal{O}(1/t)\) (亚线性收敛)	不具备全局指数加速能力

特征基设计配置	基函数定义	最大值点集测度 \(\mu(\mathcal{A}_\theta)\)	\(\lim_{\\|\theta\\| \to \infty} \text{KL}(\pi_\theta\\|\mu)\)	是否满足径向无界	能否支撑全局线性收敛
三角多项式特征 (Example 1)	傅里叶基 \(\cos(k^\top a + \ell_k^\top s), \sin\)	零测度 (\(\mu=0\)，解析函数零点)	\(+\infty\) (对数发散)	是 (满足 Assumption 2)	保证全局线性收敛
伯恩斯坦多项式 (Example 2)	单纯形基 \(b_{\ell, k}(h(s,a))\)	零测度 (\(\mu=0\)，超平面零集)	\(+\infty\) (正交子空间发散)	是 (满足 Assumption 4)	保证全局线性收敛
有限元帽函数 (Example 3/4 消融)	一维 P1 有限元网格基函数	正测度 (\(\mu([\frac{1}{3}, \frac{2}{3}]) = \frac{1}{3} > 0\))	收敛至常数 \(\log 3 < \infty\)	否 (彻底丧失无界性)	无法排除参数逃逸与奇异退化