🤖 machine learning

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

本文通过引入无需遍历性或生成模型等限制性假设、且能实现 $\widetilde{O}(1/\varepsilon^2)$ 和 $\widetilde{O}(1/\varepsilon^4)$ 界限的新型无模型方法，为从单条轨迹中学习弱通信平均奖励马尔可夫决策过程（MDP）的策略建立了首个有限样本复杂度保证。

原作者： Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

发布于 2026-06-16

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

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

大局观：在没有地图的情况下穿越迷宫

想象一下，你正试图在一个巨大且无尽的迷宫中寻找最佳路线。你的目标不仅仅是快速到达出口（这类似于“折扣”奖励，即未来的重要性较低），而是要最大化你在一段非常漫长、甚至是无限旅程中的平均速度。这就是研究人员所称的平均奖励马尔可夫决策过程（Average-Reward MDP）。

过去，寻找这些迷宫最佳策略的方法通常需要以下两种情况之一：

“上帝模式”模拟器： 一个神奇的工具，让你能够瞬间移动到迷宫中的任何位置，并精确观察接下来会发生什么（称为“生成模型”）。
完美的混合迷宫： 一种无论你从哪里开始，都保证最终会访问到每一个角落的迷宫（称为“遍历性”）。

问题在于： 现实生活并非完美的迷宫，我们也极少拥有“上帝模式”模拟器。通常情况下，我们只有一条我们走过的单一路径。我们不知道布局，而且在进入主要的循环区域（即发生行动的地方）之前，我们可能会在死胡同区域（“瞬态”状态）里徘徊很久。

该论文的突破点：
这篇论文指出：“即使迷宫很混乱且有死胡同，我们也可以仅通过你走过的这条单一路径来解决这个问题。”他们开发了两种新方法（一种基于价值，一种基于策略），即使在没有地图或模拟器的情况下，也能通过分析那一次旅程来学习最佳策略。

核心概念与类比

1. “瞬态”与“循环”状态

想象迷宫中有两类区域：

瞬态状态（走廊）： 你经过这里一次，然后就再也不会回来了。它是一个死胡同或单行道。
循环状态（主循环）： 一旦进入这个区域，你就会陷入一个循环。你会永远反复访问这些地点。

挑战： 如果你从“走廊”开始，你可能会在这里徘徊一段时间，直到最终偶然跌入“主循环”。以往的方法很难处理这种初始的徘徊时间，或者难以区分循环区域与死胡同。

论文的解决方案：
作者创建了一个聪明的“侦察兵”算法（算法 1）。它说：“先走一段路。如果你很久没看到新的地点了，那你很可能已经进入了‘主循环’。让我们只对循环中的地点开始做笔记。”
他们在数学上证明了，在行走了一定时间后，你几乎可以肯定已经进入了主循环，你可以忽略最初在走廊里的徘码时间。

2. “锚定”技术 (SAVIC)

他们提出的第一个方法叫做 SAVIC（随机锚定价值迭代）。

类比： 想象你试图通过迈步来寻找房间的中心。如果你仅仅根据上一步来决定下一步，你可能会感到头晕并原地打转。
诀窍： “锚定”技术就像是在你出发点系了一根绳子。每当你迈出新的一步时，你都会稍微把自己往起点方向拉一点。
为什么有效： 这能防止算法变得疯狂或偏离航线太远。它保持了学习过程的稳定性，并确保即使面对来自单一路径的嘈杂数据，算法也能高效地收敛到正确答案。

3. “无地图”方法 (SAVIC+)

对于每个地点都属于主循环的迷宫（称为“连通型” MDP），作者创建了 SAVIC+。

创新点： 以前的方法需要预先知道关于迷宫的特定数值（例如“绕主循环一圈需要走多久？”）。
论文的声明： SAVIC+ 是第一个不需要预先知道这些数值的方法。它在过程中自动计算出合适的行走量和学习量，使用了一种“倍增技巧”（先尝试一点点，然后是两倍，再是两倍，直到确定拥有足够的数据）。

4. 策略镜像上升 (SCPMA)

第二个方法是 SCPMA，它侧重于改变策略（即“策略”），而不是仅仅计算价值。

类比： 想象你是一位正在完善食谱的厨师。你不仅仅是在品尝汤的味道（价值），你还在调整食材（策略）。
“裁剪”诀窍： 为了确保厨师不会意外地去掉了某种核心食材（这会导致食谱失效），算法会对变化进行“裁剪”。它确保每种食材在混合物中至少保留一点点。这种数学上的安全网保证了学习过程不会崩溃，即使在混乱的迷宫中也是如此。

他们究竟证明了什么？

论文提供了关于需要多少“行走”（数据）才能找到近乎完美策略的数学保证（证明）。

对于价值法 (SAVIC)： 他们证明了要获得一个非常接近完美的策略（误差范围在 $\epsilon$ 之内），你大约需要 $1/\epsilon^2$ 步的数据。
对于策略法 (SCPMA)： 他们证明你需要大约 $1/\epsilon^4$ 步。

为什么这很重要？
在此之前，没有人能证明你可以仅使用单一轨迹在混乱的弱连通迷宫中获得这些特定的保证。以往的大多数工作都假设你拥有神奇的模拟器或一个完美的混合迷宫。这篇论文移除了这些“魔法”要求，并表示：“这就是如何从你的一次真实的行走中进行学习的。”

总结

这篇论文就像是一本指南，教你如何仅通过你刚刚走过的路径，在复杂且不可预测的迷宫中学习最佳路线。它引入了新的数学工具（锚定、裁剪和停止时间）来处理现实世界数据的混乱性，并证明了你不需要地图或模拟器也能进行有效的学习——你只需要知道如何分析你所经历的那次旅程。

技术摘要：从单条轨迹中学习平均奖励马尔可夫决策过程的策略

问题陈述

本文研究了在平均奖励马尔可夫决策过程（MDPs）中，利用单条轨迹获得有限样本复杂度保证以寻找 $\epsilon$ -最优策略的挑战。

虽然关于折扣累积奖励 MDPs 的样本复杂度的文献已非常广泛，但针对平均奖励 MDPs 的分析在历史上一直依赖于一些限制性假设。现有的工作通常需要以下条件之一：

生成模型（即可以重置到任意状态的模拟器）。
i.i.d. 离线数据。
强结构性假设，例如遍历性（ergodicity）（即任何策略都诱导单个循环类）或对行为策略的具体覆盖条件。

本研究针对的特定空白是**弱通信（weakly communicating）*设置。在弱通信 MDP 中，在任何“良好行为”的策略下，状态空间会分解为一个循环类和一组瞬态状态，但系统并不一定是遍历的（即存在瞬态状态）。在此项工作之前，在这一设置下从单条轨迹*进行平均奖励强化学习的有限样本复杂度分析尚处于空白。

方法论

作者开发了一个理论框架和新型无模型算法，这些方法利用了弱通信 MDP 的结构特性，特别是状态的循环-瞬态分类（recurrent-transient classification）。

1. 单条轨迹的结构分析

其核心技术贡献是对由行为策略 $\pi_b$ 生成的单条轨迹进行的随机分析。作者确立了以下几点：

循环-瞬态不变性： 对于策略空间内部（ $\Pi_+$ ）的策略，状态被划分为单个循环类（ $R$ ）和瞬态集（ $T$ ）的分类是保持不变的，且仅由转移核 $P$ 决定，而非特定的策略选择。
逃离瞬态状态： 利用马尔可夫不等式和强马尔可夫性质，作者证明了从瞬态状态开始的轨迹会以高概率在有限的命中时间（hitting time）（ $t_{hit}$ ）内到达循环类 $R$ 。
覆盖循环类： 一旦进入 $R$ ，轨迹会在有限的覆盖时间（covering time）（ $t_{cov}$ ）内覆盖 $R$ 中的所有状态。
通过停时进行 i.i.d. 采样： 通过利用停时（具体而言是轨迹返回特定状态 $s$ 的时刻），作者表明单条轨迹中的样本可以被视为独立同分布（i.i.d.）样本，从而用于浓度不等式（引理 2.3）。这解决了单条轨迹分析中固有的依赖问题，而无需混合时间假设。

2. 基于价值的方法：SAVIC

**随机锚定价值迭代（Stochastic Anchored Value Iteration, SAVIC）**是一种专为弱通信 MDP 设计的无模型基于价值的算法。它分为三个阶段：

循环状态识别： 智能体运行行为策略以逃离瞬态状态，并使用 算法 1 (RECUR) 收集所有循环状态（ $R$ ）的列表。
带方差缩减的锚定迭代： 在循环类内，算法执行锚定价值迭代（Anchored Value Iteration, Anc-QI）。与标准 VI 不同，Anc-QI 计算下一个迭代值为 Bellman 更新与初始点（ $Q_0$ $Q_{0}$ ）的凸组合。这种“锚定”项确保了非渐近收敛。
- 为了实现高效的样本复杂度，该方法采用了递归采样技术。它不是在每一步都估计完整的 Bellman 算子 $T(Q_k)$ ，而是使用方差缩减采样来估计差值 $T(Q_k) - T(Q_{k-1})$ 。
策略扰动： 由于算法仅在循环类 $R$ 上进行优化，因此最终策略会被扰动，以确保其在包括瞬态状态在内的整个状态空间 $S$ 上都是 $\epsilon$ -最优的。

3. 无需先验知识的无模型方法：SAVIC+

对于通信（communicating）MDPs（即 $S=R$ ，不存在瞬态状态），作者引入了 SAVIC+。

该变体消除了对问题相关常数（如 $t_{hit}$ 、 $t_{cov}$ 或最小平稳分布概率）的先验知识的需求。
它采用**倍增技巧（doubling trick）**以及基于经验 Bellman 残差误差（ $\|Q - TQ\|_{sp}$ ）的显式停止规则。
它使用 算法 4 (SAMPLE+) 来自动收集样本，直到每个状态-动作对都达到足够的计数。

4. 基于策略的方法：SCPMA

**随机 $\alpha$ -裁剪策略镜像上升（Stochastic $\alpha$ -clipped Policy Mirror Ascent, SCPMA）**是一种用于弱通信 MDP 的策略梯度方法。

它利用一种新型的策略评估算法（SAVIPE），该算法使用与 SAVIC 相同的锚定和方差缩减机制来近似状态-动作价值函数。
策略更新遵循**策略镜像上升（Policy Mirror Ascent）**框架，但应用了 $\alpha$ -裁剪 以确保策略保持在策略空间的内部（ $\Pi_\alpha$ ）。这种裁剪对于界定样本复杂度分析中的系数至关重要。
该方法支持常数步长和自适应步长。

关键结果

本文建立了在弱通信设置下，从单条轨迹学习平均奖励 MDP 的首个有限样本复杂度保证。

SAVIC (基于价值)：
- 实现寻找 $\epsilon$ -最优策略的 $\tilde{O}(1/\epsilon^2)$ 样本复杂度。
- 该界限取决于命中时间（ $t_{hit}$ ）、覆盖时间（ $t_{cov}$ ）、最优价值函数的跨度（ $\|Q^*\|_{sp}$ ）以及最小平稳分布概率的倒数（ $1/d_{min}^\pi$ ）。
SAVIC+ (无模型，无需先验知识)：
- 对于通信 MDP，SAVIC+ 实现了 $\tilde{O}(1/\epsilon^2)$ 的样本复杂度。
- 至关重要的是，它不需要先验知识来设置参数（如 $t_{cov}$ 或 $d_{min}$ 等问题相关量）。
SCPMA (基于策略)：
- 实现 $\tilde{O}(1/\epsilon^4)$ 的样本复杂度（使用常数步长），或者在使用自适应步长时获得改进的速率。
- 这代表了在弱通信 MDP 中，从单条轨迹进行策略梯度方法的首个有限样本复杂度保证。

意义与主张

作者声称，这项工作提供了在弱通信设置下，从单条轨迹学习平均奖励 MDP 的首个有限样本复杂度保证。

打破遍历性假设： 与以往需要遍历性（所有状态均为循环状态）的工作不同，本研究处理了更通用的弱通信情况，即存在瞬态状态。
单条轨迹的现实性： 研究结果超越了不切实际的生成模型或 i.i.d. 数据假设，为智能体顺序与环境交互的标准在线学习设置提供了保证。
无模型的高效性： 所提出的方法是无模型的，并且在 SAVIC+ 的情况下，不需要先验了解 MDP 的混合特性或平稳分布，这使其在处理未知环境时更具实用性。
理论工具： 本文引入了新的理论工具，包括使用停时和强马尔可夫性质，从单条弱通信轨迹中生成 i.i.d. 样本，从而能够应用此前仅限于 i.i.d. 设置的浓度不等式。

文章最后指出，虽然基于价值的方法实现了比基于策略方法更紧凑的 $\tilde{O}(1/\epsilon^2)$ 界限（相比于后者的 $\tilde{O}(1/\epsilon^4)$ ），但缩小这一差距并将这些结果扩展到参数化函数逼近设置仍是开放的未来研究方向。