🤖 machine learning

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

本文提出了一种新算法，显著放宽了回合式马尔可夫决策过程中奖励无关探索的精度约束，并建立了奖励无关探索的紧下界，从而弥合了已知上下界之间的差距。

原作者： Oran Ridel, Alon Cohen

发布于 2026-05-18

📖 1 分钟阅读☕ 轻松阅读

原作者： Oran Ridel, Alon Cohen

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

想象你是一名侦探，被派往一座庞大而陌生的城市，以摸清街道的布局。然而，有一个限制条件：你被禁止询问方向，而且你还不知道最终的使命是什么。

也许明天你需要找到前往医院的最快路线；后天，你可能需要找到风景最美的公园；又或者，你需要定位一家特定的面包店。你并不知道将面临上述哪项任务，但你清楚自己必须为任何一种情况做好准备。

这正是该论文要解决的核心问题：当不知道“奖励”（即目标）是什么时，如何高效地探索一个环境？

作者 Oran Ridel 和 Alon Cohen 提出了一种全新的解决思路，其效率远超以往的方法。以下用简单的类比来拆解他们的工作。

两种情境

该论文考察了这种“盲眼探索”问题的两个略有不同的版本：

无奖励探索（“空白画布”情境）：
你完全盲目地探索这座城市。你不知道自己将来是否需要去医院、公园或面包店。你只需要将城市绘制得如此详尽，以至于无论之后给你什么目标，你都能立即找出最佳路径。
- 挑战： 由于目标可能是任何东西，你必须极其详尽。
奖励无关探索（“菜单”情境）：
你仍然不知道具体目标，但你确实提前知道了所有可能目标的列表。也许你知道唯一的目的地只有“医院”、“公园”或“面包店”。
- 优势： 因为你知道列表很短，所以你不需要以同样的强度去绘制每一条小巷。你可以稍微更具策略性。

旧方法：“试错”法

以往的方法（如 Li 等人，2024 年提出的方法）试图通过运行许多独立的、小型的实验来解决这个问题。

类比： 想象一下，为了了解这座城市，你为每一个街角雇佣不同的向导。你雇佣向导 A 学习北侧，然后解雇他，再雇佣向导 B 学习南侧，依此类推。
问题： 这极其浪费。你一遍又一遍地重新学习这座城市的基本规则。虽然可行，但这需要大量的时间和数据，尤其是当你需要非常精确时。

新方法：“智能导游”

作者提出了一种新算法，它像一位单一的、高度智能的导游，通过一次连续且聪明的旅程来学习这座城市。

1. “好奇心”策略（第 1 步）
该算法不再运行独立的实验，而是进行一次长期的“在线学习”会话。它生成一系列人为的、临时的目标（奖励），专门设计用来迫使智能体访问那些最难到达或最不被理解的城市区域。

隐喻： 想象导游说：“好吧，今天我们要去那个没人去过的地方。明天，我们去那个最难找的地方。”通过不断将目标转向“最困难”的地点，智能体自然地构建出城市的完整地图，而不会在已经熟知的地方浪费时间。
结果： 这生成了一个单一的“探索策略”（主计划），它收集了足够的数据来理解城市的动态（街道如何连接），所需的行程次数远少于以往。

2. “地图绘制者”（第 2 步）
一旦智能体完成探索，它就利用收集到的所有数据来构建城市转移的精确地图（例如，“如果我在喷泉处左转，我就会到达广场”）。

3. “任务规划者”（第 3 步）
现在，真实的目标揭晓了（例如，“找到面包店”）。智能体查看其高质量地图，并立即计算出前往面包店的最佳路径。由于地图如此准确，这条路径几乎是完美的。

为什么这篇论文很重要

作者取得了两项重大突破：

1. 他们使“菜单”情境变得更加实用。
以往针对“奖励无关”（菜单）情境的方法，只有在需要极其精确（误差范围非常小）时才有效。如果你允许稍大一点的误差范围，旧方法就会变得低效。

解决方案： 新算法放宽了这一要求。即使你不需要完美，它也能高效运行，使其适用于更广泛的现实世界场景。

2. 他们证明了“空白画布”情境正如我们想象的那样困难。
对于“无奖励”（空白画布）情境，最佳已知方法（我们能做到的速度）与理论极限（我们必须达到的速度）之间存在差距。

解决方案： 作者证明了一个新的“下界”。他们表明，无论你多么聪明，你无法比某个特定限制更快地完成它。这填补了差距，证明了现有的最佳方法实际上是最优的（即它们可能达到的最好程度）。

总结

可以将这篇论文视为升级了机器人学习新环境的方式。

旧机器人： “我将尝试通过分别访问每条街道 1,000 次来学习。这将耗费永恒的时间。”
新机器人： “我将进行一次聪明且蜿蜒的游览，迫使我恰好访问每一个棘手的角落，并在此过程中构建完美的地图。然后，当你告诉我该去哪里时，我会立刻知道路线。”

作者已经表明，这种“智能游览”方法不仅更快，而且在数学上被证明是某些类型问题可能的最高效方式。

技术摘要：奖励无关与奖励自由探索的改进界

问题表述

本文解决了在回合式有限时域表格马尔可夫决策过程（MDP）中，智能体在数据收集阶段无法观测外部奖励信号时的探索挑战。作者研究了两种具体框架：

奖励自由探索（RFE）： 智能体在无奖励信号的情况下探索未知环境。其目标是生成一个策略，使得在探索阶段结束后揭示任意奖励函数时，该策略均为 $\epsilon$ -最优。
奖励无关探索（RAE）： 与 RFE 类似，但奖励函数是从一个小的、预定义的有限类（大小关于 $|S|, |A|, H$ 为多项式级）中抽取的。其目标是找到针对从该类中抽取的特定奖励函数的 $\epsilon$ -最优策略。

核心难点在于收集足够的数据以准确估计状态 - 动作转移动力学，而无需奖励信号的指导，从而确保生成的模型能够支持下游任务中近最优策略的计算。

方法论

所提出的方法用统一的在线学习过程取代了先前工作中依赖的多个独立无遗憾子程序。该算法（算法 1）分为三个阶段运行：

1. 探索策略构建

作者采用单次运行**在线镜像下降（OMD）**算法来处理一系列精心构造的辅助奖励函数，而不是运行多个随机无遗憾算法（如 Jin 等人，2020b；Li 等人，2024b 所做的那样）。

机制： 算法生成一系列奖励 $\{\lambda_t\}$ ，旨在引导智能体前往访问较少的状态 - 动作对。第 $t$ 步的奖励与该状态 - 动作对的访问次数成反比（并加上一个常数 $c$ 以处理低概率访问）。
优化视角： 该过程被表述为在有效占用测度空间上近似求解一个凸优化问题。具体而言，其目标是最大化负对数障碍目标函数 $f(\mu) = -\sum \log \mu_h(s,a)$ 的最小化。
意义： 通过使用单一的在线 MDP 算法（改编自 Rosenberg & Mansour, 2019）而非 Frank-Wolfe 风格的迭代，该方法显著降低了低阶样本复杂度项。它在整个学习过程中重用样本，以构建一个“策略覆盖”，确保对重要状态 - 动作三元组的近乎均匀探索。

2. 动力学估计

利用步骤 1 中生成的探索策略，智能体收集 $N$ 条轨迹。为了处理轨迹数据中固有的时间相关性，作者利用了一个双重子采样框架（Li 等人，2024a）。该技术将数据集划分为主要集和辅助集以诱导统计独立性，从而允许构建具有严格集中保证的经验转移核 $\hat{P}$ 。

3. 策略估计

一旦真实奖励函数被揭示，算法便利用面对不确定性的悲观主义计算 $\epsilon$ -最优策略。

算法使用 $\hat{P}$ 和揭示的奖励构建经验 MDP。
它将源自 Bernstein 风格集中不等式的惩罚项 $b_h(s,a)$ 应用于 Q 值估计。该惩罚项随经验方差和访问次数缩放，从而抑制策略访问覆盖不足的状态 - 动作对。
最终策略 $\hat{\pi}$ 是该悲观经验 MDP 的最优策略。

主要贡献与结果

1. 奖励无关探索（RAE）的改进样本复杂度

本文提出了一种新算法，实现了 RAE 的最优高阶样本复杂度，与最佳策略识别（BPI）的下界相匹配。

结果： 样本复杂度为 $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$ 。
改进： 虽然先前的工作（Li 等人，2024b）实现了最优高阶项 $O(|S||A|H^3/\epsilon^2)$ ，但其界限受限于一个高复杂度的低阶项，导致该界限仅在 $\epsilon$ 极小时才为最优。所提出的方法显著降低了这一低阶项，使得该算法适用于更广泛的精度参数范围。

2. 奖励自由探索（RFE）的紧下界

作者证明了非时齐 MDP 中 RFE 样本复杂度的紧下界。

结果： 任何 RFE 算法在期望上都需要 $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ 条轨迹。
意义： 这解决了 Li 等人（2024b）的一个猜想，即非时齐 RFE 的极小极大下界比时齐情况大一个 $H$ 因子。这确立了现有上界（例如 M´enard 等人，2021）在忽略对数因子的情况下是最优的。

3. 理论框架

本文通过将探索策略构建与占用测度上的对数障碍目标最小化联系起来，提供了一个新颖的技术视角。它表明，在线镜像下降方法比先前的基于 Frank-Wolfe 的方法能更高效地近似该解，从而降低了低阶项中对问题维度的依赖。

意义与主张

本文声称通过以下方式推进了对无奖励探索的理论理解：

解耦探索与利用： 阐明了有限时域 MDP 中探索的内在样本复杂度。
RAE 的实用性： 通过放宽先前最优界限中对精度参数 $\epsilon$ 的限制性要求，所提出的方法使得奖励无关探索即使在中等精度范围内也具有实用性。
表征的完备性： 新的 RAE 上界与 RFE 紧下界的结合，提供了这些问题的完整极小极大样本复杂度表征（忽略对数因子）。

作者明确指出，他们的重点是对有限时域表格 MDP 的理论分析，将非表格 MDP 和实证结果留作未来工作的方向。他们并未声称可立即应用于机器人或医学等具体现实领域，而是强调这些基础性理论改进为实现此类应用提供了可能。