⚡ electrical engineering

Approximations and Learning for Continuous State and Action MDPs under Average Cost Criteria

本文通过将连续性假设放宽为弱连续性或 Wasserstein 连续性，为平均代价准则下的连续状态与动作 MDP 的离散化近似建立了误差界限，并提出了同步和异步量化 Q 学习算法，这些算法收敛至近似模型的最佳值，从而确保了近优性。

原作者： Ali Devran Kara, Serdar Yuksel

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Ali Devran Kara, Serdar Yuksel

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图教一个机器人如何在广阔、平滑且连续的地形（比如一个巨大的开放式田野）中导航，以找到在极长时间内能量消耗最小的路径。这就是**平均成本准则下的马尔可夫决策过程（MDPs under an Average Cost Criterion）**问题。

挑战在于，机器人的世界太大了，而且非常平滑，无法进行完美的建模。你不能把每一个点都写下来。Kara 和 Yükel 的这篇论文就像是一本指南，教你如何构建一个简化的、块状的地图，利用这个块状地图来训练机器人，并证明机器人即使在真实的、平滑的世界中也能表现得非常出色。

以下是使用简单类比对他们工作的详细解读：

1. 问题所在：“平滑世界” vs. “像素化地图”

把真实世界想象成一张高分辨率的照片。它拥有无限的细节。为了让计算机进行学习，我们通常需要将这张照片转化为低分辨率的、像素化的图像（即网格）。

旧方法： 先前的研究者认为，“为了让这种像素化地图发挥作用，像素之间的转换必须极其可预测且僵硬（全变分连续性/Total Variation continuity）。” 这就像是说，照片必须由完美的、无模糊感的方块组成。
新方法： 这些作者说：“我们不需要如此严格的照片。我们可以处理‘模糊’或‘摇晃’的照片（弱连续性或 Wasserstein 连续性）。” 他们证明了即使状态之间的转换有些“软”或“模糊”，你仍然可以构建一个可靠的像素化地图。

2. 解决方案：构建一个“块状”近似模型

作者提出了一种方法，将连续的世界切分成有限的块（bins），就像把蛋糕切成片一样。

近似过程： 与其追踪机器人的精确位置，你只需要追踪机器人处于哪一个“蛋糕片”中。
保证： 他们精确地计算了这种像素化所引入的“误差”（或额外成本）。
- 如果世界是“模糊”但稳定的，那么随着切片变得越来越薄，误差就会减小。
- 他们证明了，只要你把切片做得足够小，机器人在块状地图上学到的策略在真实的平滑世界中也会几乎同样出色。

3. 学习过程：用“量化 Q 学习”教导机器人

一旦世界被切成了片，机器人就需要学习最佳动作。论文介绍了两种教学方式：

同步学习（“课堂教学”法）： 想象一位老师问机器人：“如果你在切片 A 中并向左移动，会发生什么？” 然后，老师会同时模拟从每一个切片出发的所有可能动作，同时更新机器人的知识。作者证明了这种方法是收敛的（即停止变化并稳定在一个解上）。
异步学习（“现实生活”法）： 想象机器人在田野中独自行走，边犯错边学习。它无法同时看到所有的切片；它只能看到它当前所在的那个切片。作者证明了即使在这种混乱的、一次只能处理一步的数据情况下，机器人最终也能学会块状地图的正确数值。

关键洞察： 作者指出，机器人的“块状”视角实际上是一个技巧。因为机器人只知道自己在哪个切片里，但不知道在该切片内的精确位置，所以从技术上讲，它学习的是一个“部分可观测”的问题（就像玩一个看不清整个棋盘的游戏）。尽管如此，他们的数学证明显示，机器人仍然能学会块状地图的最优策略。

4. 结果：“近优性”

最重要的结论在于最终的结果。

机器人学到了块状、像素化地图上的最佳策略。
作者证明了该策略对于真实的、平滑的世界也是近乎最优的。
想象一下在低分辨率屏幕的模拟器上学习驾驶。作者证明了，如果模拟器足够好（切片足够小），你在那里学到的驾驶技能可以近乎完美地迁移到在真实公路上驾驶真实汽车上。

“魔力”总结

这篇论文主要做了三件事：

放宽了规则： 他们展示了你不需要一个完美刚性的世界来构建良好的近似，一个“模糊”的世界同样可行。
搭建了桥梁： 他们创建了特定的算法（同步和异步），让机器人可以在复杂世界的简化块状版本上进行学习。
证明了迁移： 他们通过数学手段保证了在块状地图上学到的策略与完美策略非常接近，以至于在实践中几乎是一样的，前提是这些“块”足够小。

简而言之，他们找到了如何通过让机器人练习一个简化的、块状的版本，来教它如何在一个平滑的、无限的世界中导航，并且他们证明了熟能生巧。

技术摘要：连续 MDP 下基于平均成本准则的 Q-Learning

1. 问题表述

本文研究了在连续状态和动作空间下，基于无限时界平均成本准则求解马尔可夫决策过程（MDP）的挑战。模型由元组 $(X, U, \mathcal{T}, c)$ 定义，其中 $X$ 和 $U$ 是标准 Borel 空间（完全可分的度量空间）， $\mathcal{T}$ 是转移核， $c$ 是成本函数。目标是找到一个策略 $\pi$ ，以最小化长期平均成本：
$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$

作者强调，虽然有限时界和折扣成本问题在连续空间下的研究已较为成熟（利用 Bellman 算子的收缩性质），但平均成本问题呈现出独特的困难。具体而言，由于缺乏折扣因子，消除了即时的收缩映射，因此需要替代性的稳定性与遍历性假设。此外，现有的关于平均成本强化学习（RL）的文献主要集中在有限空间，或施加了限制性的结构性假设（例如线性动力学、Lipschitz 策略），这限制了其在一般连续空间中的适用性。

2. 方法论

本文采用了两种途径相结合的方法：通过量化进行有限近似，以及针对这些近似设计的强化学习算法。

2.1 离散化与近似

核心方法论是通过对连续空间进行量化，构建一个有限状态、有限动作的近似 MDP。

状态量化： 将状态空间 $X$ 划分为不相交的箱体 $\{B_i\}_{i=1}^M$ ，并定义代表状态 $y_i$ 。定义了一个映射 $q: X \to Y$ （其中 $Y$ 是有限代表集）。
动作量化： 通过有限集合 $\Lambda$ 来近似动作空间 $U$ 。
近似模型构建： 使用权重测度 $\mu$ （通常是状态过程的不变测度）定义近似模型 $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ 。近似成本和转移核是原始函数在量化箱体上的平均值：
$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$
放宽的连续性条件： 一个重要的 metodological 转变是放宽了**全变差（Total Variation, TV）**连续性条件，这是以往近似文献（如 Saldi 等人，2018）中的标准要求。作者在以下条件下建立了近似结果：
1. 弱连续性（Feller 连续性）： 足以保证误差随网格尺寸消失而渐近收敛。
2. Wasserstein 连续性： 足以在网格尺寸消失时建立显式的收敛速率（误差界）。

2.2 强化学习算法

本文提出了量化 Q-Learning 算法，直接从数据中学习近似模型的优化策略。

同步算法 (Algorithm 1)： 同时更新有限网格中所有状态-动作对的 Q 值。它依赖于根据预定测度从每个箱体中采样状态。
异步算法 (Algorithm 2)： 基于原始连续过程的单个轨迹更新 Q 值。这种方法更具实践意义，但引入了一个非马尔可夫噪声项，因为量化过程 $q(X_t)$ 不是马尔可夫链（从量化状态的角度来看，它是一个部分可观测 MDP）。
收敛机制： 为了处理平均成本准则以及 Q 迭代可能无界的问题（与折扣情况不同），作者利用了：
- 用于同步更新的 跨度半范数（Span Semi-norms）。
- 遍历性假设： 探索策略必须诱导出一个在量化箱体上具有全支撑的唯一不变测度。
- 偏移更新： 异步算法减去一个参考值（基于特定箱体）来稳定迭代，将量化过程视为 POMDP。

3. 主要贡献

本文做出了三项主要贡献，推进了连续空间平均成本控制领域的研究现状：

具有更弱条件的近似理论：
- 作者在 弱连续性 和 Wasserstein 连续性 下提供了有限近似的误差界，放宽了先前工作（如 Saldi 等人，2018）所要求的严格的全变差连续性。
- 他们证明，在 Wasserstein 连续性下（伴随收缩常数 $K_T < 1$ ），最优平均成本的误差以与量化误差（具体为 $L_X^\delta$ ）成比例的速度衰减。
- 仅在弱连续性下，他们证明了随着离散化变得更加精细，近似策略的成本趋于最优成本。
量化 Q-Learning 的收敛性：
- 本文证明了连续空间下同步和异步 Q-learning 算法的几乎处处收敛性。
- 至关重要的是，它证明了这些算法收敛到构建的有限近似模型的优化 Q 值，而不仅仅是原始连续模型。这一区别至关重要，因为量化过程并非严格的马尔可夫过程。
- 该分析将以往的结果（如 Kara 和 Yüksel, 2023）从折扣成本推广到了更具挑战性的平均成本准则，需要新的技术分析来处理无界的 Q 迭代。
近优性保证：
- 通过结合近似误差界与学习算法的收敛性，本文证明了通过量化 Q-learning 学习到的策略对于原始连续 MDP 是近优的。
- 性能损失被明确地限制在量化分辨率和成本及转移核的 Lipschitz 常数范围内。

4. 关键结果与定理

定理 1 & 2 (近似界)： 建立了原始模型最优平均成本 ( $\rho$ $ρ$ ) 与近似模型 ( $\hat{\rho}$ $\overset{ρ}{^}$ ) 之间差异的上界。
- 在 Wasserstein 连续性下： $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$ ，其中 $L_X$ 是量化误差。
- 在弱连续性下： $\lim_{n \to \infty} \rho(\pi_n) = \rho$ 。
定理 5 & 6 (算法收敛性)： 证明了同步和异步 Q-learning 迭代收敛到有限近似模型的优化 Q 值。异步收敛性依赖于状态过程在探索策略下的遍历性。
推论 1： 结合近似和学习结果，表明学习到的策略 $\hat{\pi}$ 满足 $\rho(\hat{\pi}) - \rho \leq \epsilon$ ，其中当离散化网格尺寸趋于零时， $\epsilon$ 消失。

5. 重要性与主张

作者将这项工作定位为解决连续空间平均成本 MDP 强化学习文献中开放问题的方案。

放宽假设： 本文声称通过从全变差连续性（这在实际模型中往往过于苛刻）转向弱连续性和 Wasserstein 连续性，实现了显著的理论进步。这扩大了可以提供理论保证的系统类别（例如具有加性噪声或特定动力学的系统）。
架起理论与实践的桥梁： 通过证明 Q-learning 收敛于一个定义良好的有限近似解，本文为使用基于离散化的强化学习在连续平均成本设置下的做法提供了严谨的理论依据。它阐明了“近优性”是近似质量的直接结果，而非学习算法的人为产物。
处理非马尔可夫量化： 本文明确解决了量化状态过程是 POMDP 而非 MDP 这一技术难题，并提供了在平均成本准则下异步学习的收敛性证明，填补了此前文献（如 Wan 等人，2021）中存在的空白。

本文最后通过一个连续控制问题的数值案例研究进行了总结，展示了值函数的收敛情况以及遗憾值（regret）随量化率增加而减少的过程，验证了所述理论界限。