📊 statistics

A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

本文针对生成模型下的有限及无限时界马尔可夫决策过程，引入了新颖的经典与量子在线强化学习算法，这些算法通过利用直接最优策略计算来绕过乐观主义和后验采样等传统范式，从而实现了改进的遗憾界限，其中包括量子方法对时间步长的多项式对数依赖性。

原作者： Andris Ambainis, Joao F. Doriguello, Debbie Lim

发布于 2026-07-20

📖 1 分钟阅读☕ 轻松阅读

原作者： Andris Ambainis, Joao F. Doriguello, Debbie Lim

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

想象一下你正在玩一款规则隐藏的电子游戏。你不知道哪些按键会带来宝藏，哪些按键会导致你掉入深坑。为了获胜，你必须不断按下按键，观察结果，并慢慢摸索出最佳策略。这就是强化学习（Reinforcement Learning, RL）的核心——它是人工智能的一个分支，其中的“智能体”（agent）通过与环境交互来最大化奖励。其数学框架被称为马尔可夫决策过程（Markov Decision Process, MDP）。你可以把 MDP 想象成一张地图，上面标明了所有可能的游戏状态（比如“站在悬崖边”或“拿着钥匙”）以及采取某种行动后发生下一步情况的概率。目标是找到一个完美的“策略”（policy）——即一本规则书，告诉智能体在每种情况下该如何行动，以获得最高分。

长期以来，科学家们一直试图让这些学习智能体变得更聪明、更快速。一个主要的障碍是“探索与利用”（exploration vs. exploitation）的权衡：智能体应该尝试新的、冒险的动作来了解更多世界知识（探索），还是坚持使用那些它已知是好的动作（利用）？大多数传统方法依赖于一种叫做“面对不确定性时的乐观主义”（optimism in the face of uncertainty）的策略，即智能体假设未知的路径可能是极好的，以此来鼓励尝试。然而，这篇论文引入了一个转折：如果智能体偶尔可以使用一个“作弊码”或“模拟器”，在不实际玩游戏的情况下测试动作，情况会怎样？作者探讨了给予智能体这种特殊权限，并结合量子计算的力量，将如何彻底改变它们的学习速度。

这篇论文的核心思想：混合训练营

作者 Andris Ambainis, Joao F. Doriguello, 和 Debbie Lim 提出了一种训练这些 AI 智能体的新方法。他们建议使用一种混合在线-离线模型（hybrid online-offline model）。想象一下智能体是一个学生。在“在线”阶段，学生是在真实的教室里参加考试。每一个错误的答案都会扣分（这就是“遗憾值”或对不完美行为的惩罚）。这是昂贵的、现实世界的环节。但随后，学生得到了休息。他们进入了一个“模拟实验室”（离线阶段）。在这个实验室里，他们拥有一个神奇的“生成模型”——一个模拟器，它可以瞬间展示任何动作的结果，无论重复多少次，且没有任何惩罚。

这里的关键创新在于，智能体可以在这两种模式之间切换。它在真实的游戏中玩一段时间，积累一些错误，然后去模拟器中进行数据计算，找出完美的策略。一旦有了更好的计划，它就回到真实的游戏中。论文认为，这种使用模拟器的“自由度”改变了一切。

抛弃旧规则

论文中最有趣的环节之一是它告诉我们“不要做什么”。几十年来，针对强化学习智能体的标准建议是使用“面对不确定性时的乐观主义”。这就像告诉一个学生：“既然你不知道那扇门后面是金子还是陷阱，那就假设它是金子，这样你才会去检查它。”作者指出，如果你拥有一个模拟器（哪怕只是偶尔使用），你就不需要靠猜测。你可以直接进入模拟器，运行数据，并直接计算出真正的最佳动作。

他们明确反对在这种特定设置下使用“乐观主义”或“后验采样”（另一种复杂的猜测方法）。智能体不再去猜测什么是真实的，而是可以直接利用模拟器数据计算出最优策略。这种转变使他们能够避开传统学习中混乱、不确定的部分，直接跳向解决方案。

量子超能力

现在，让我们谈谈“量子”部分。作者不仅停留在使用模拟器上，他们还问道：“如果这个模拟器运行在量子计算机上会怎样？”量子计算机以能够同时处理海量可能性而闻名。通过在模拟器阶段使用量子算法，智能体可以比经典计算机更快地估算动作的结果。

论文针对三种不同类型的游戏场景提出了新算法：

有限时界（Finite-Horizon）： 在固定步数内结束的游戏（如视频游戏中的关卡）。
无限时界折扣型（Infinite-Horizon Discounted）： 持续进行下去，但未来的奖励价值略低于即时奖励的游戏（如赚取利息）。
无限时界非折扣型（Infinite-Horizon Undiscounted）： 持续进行下去，且所有奖励权重相等的游戏（如一份稳定的工作）。

对于所有这些场景，作者发现他们的量子算法所实现的“遗憾界限”（regret bound）对时间步数（ $T$ ）的依赖仅为极小的程度（例如 $T$ 的对数，或 $\log T$ ）。然而，至关重要的一点是，性能仍然显著取决于游戏世界本身的大小。 算法的效率深受游戏可能的状态数（ $S$ ）、可能的动作数（ $A$ ）以及游戏长度或有效时界（ $H$ 或 $\Gamma$ ）的影响。虽然量子智能体的误差随游戏变长增长得非常缓慢（相对于 $T$ 是多项式对数级的），但计算的复杂度仍然随状态和动作空间的大小而缩放。

用通俗的话说，这意味着随着游戏变得越来越长，量子智能体的表现相对于时间而言并不会恶化太多，但学习游戏的初始“成本”仍然由游戏地图的复杂程度决定。相比之下，经典算法的误差通常随时间的平方根（ $\sqrt{T}$ ）增长。论文表明，通过使用量子模拟器，智能体可以打破经典障碍，实现指数级的加速学习——前提是允许智能体在模拟器中投入一定的时间（由控制在 1 到 2 之间的“预算”参数 $\beta$ 控制）。如果智能体被允许在模拟器中进行足够的练习，量子优势将是巨大的；如果模拟器时间太短，这种优势就会缩小。

他们有多确定？

作者对他们的数学证明非常有信心。他们不仅仅是在电脑上运行了一个模拟实验并说“看起来有效”，而是提供了严密的数学证明，证明他们的算法会以特定的概率（通常是 $1 - \delta$ ，其中 $\delta$ 是极小的失败概率）产生最优策略。他们证明了与目前已知的最佳经典方法相比，他们的量子算法需要更少的“查询次数”（即检查模拟器的次数）即可达到理想方案。

然而，他们也谨慎地指出了条件。他们的“超快”结果高度依赖于“预算”参数（ $\beta$ ），该参数控制智能体在模拟器与现实世界中分配的时间。如果允许智能体在模拟器中花费足够的时间（特别是当 $\beta$ 在 1 到 2 之间时），量子优势是巨大的。如果模拟器时间过短，优势则会减弱。他们还指出，他们的方法依赖于智能体能够访问一个“生成模型”（即模拟器），这是一种并非在所有现实场景中都能获得的特定设置。

总结

这篇论文表明，如果我们能给 AI 智能体一个可以自由测试动作的“沙盒”——一个可以免费练习的模拟器——并且如果我们可以让那个沙盒运行在量子计算机上，我们就能以惊人的速度教会它们掌握复杂的环境。它们不需要猜测或过度乐观，只需直接计算出最佳路径。虽然这需要特定的设置（混合模型和量子访问），且当智能体拥有足够的“练习时间”（在模拟器中）时加速效果最为显著，但结果表明，这为实现一种经典计算机无法企及的效率水平的 AI 学习提供了一条清晰的路径。它提醒我们，有时，一点点无需承担后果的自由练习，就能产生极其深远的影响。

技术摘要：一点自由带来的巨大提升

问题陈述

本文探讨了在在线设置下学习马尔可夫决策过程（MDP）的问题，特别关注于最小化遗憾（regret，即智能体累积奖励与最优策略之间奖励的差值）。作者研究了三种不同的 MDP 设置：

有限时界 MDP： 智能体进行固定步数 $H$ 的交互。
无限时界折扣 MDP： 智能体进行无限次交互，奖励由因子 $\gamma \in [0, 1)$ 进行折扣。
无限时界无折扣 MDP： 智能体进行无限次交互，采用平均奖励准则，特别关注弱通信（weakly communicating）MDP。

强化学习（RL）中的一个核心挑战是探索与利用（exploration-exploitation）之间的权衡。传统的在线 RL 算法通常依赖于“面对不确定性时的乐观主义”或“后验采样”等原则来管理对环境转移概率的不确定性。本文研究了是否可以通过引入一种允许“离线”生成式访问环境的混合交互模型来绕过这些范式。

方法论

混合在线-离线 RL 模型

其核心方法论贡献是提出了一个混合在线-离线 RL 模型。该模型将学习过程分为两个交替阶段：

在线阶段（探索）： 智能体以经典方式与环境交互。它选择动作、接收奖励并观察状态转移。至关重要的是，在此阶段会累积遗憾。
离线阶段（生成式学习）： 智能体可以访问一个“模拟器”或预言机（经典形式为 $C_p$ ，量子形式为 $Q_p$ ），允许它以生成式方式采样环境的转移。在此阶段，智能体可以执行任意计算，包括量子操作和访问预言机的逆，且不会累积遗憾。

这种模型中的“自由度”受预算参数 $\beta$ 的调节。如果在线阶段持续 $\tau$ 步，智能体在随后的离线阶段被允许进行 $O(\tau^\beta)$ 次预言机查询。这一约束防止了智能体通过仅仅通过模拟环境足够多次来完美学习最优策略，从而轻易解决问题。

算法方法

提出的算法遵循分阶段结构（算法 1）：

智能体运行长度为 $\tau_\ell$ 的在线阶段。
在随后的离线阶段，智能体使用预言机计算出一个 $\epsilon_\ell$ -最优策略，该过程使用源自第 2 节的子程序。
在线阶段的长度不断增加（通过倍增技巧），以平衡探索成本与计算出的策略精度之间的关系。

作者避免了标准的“乐观主义”启发式方法。相反，他们在离线阶段直接使用以下手段计算近似最优策略：

经典子程序： 基于 Sidford 等人 [55] 的方差缩减值迭代（variance-reduced value iteration）和标准反向归纳法（backward induction）。
量子子程序： 利用量子均值估计（Quantum Mean Estimation, Kothari 和 O'Donnell [57]）来估计期望值，以及利用量子最小查找（Quantum Minimum Finding, Dürr 和 Høyer [58]）来选择最优动作，从而实现量化的值迭代。

对先前量子 RL 研究工作的修正

本文批判性地分析了之前的量子 RL 工作（例如 [23, 24, 98]），认为它们包含一个根本性的缺陷。这些工作假设量子振幅估计可以在一组存储的量子态 $\{Q_p|s\rangle, Q_p^\dagger|s\rangle\}$ 上进行。作者澄清，振幅估计需要对单个量子态进行连续、相干的预言机应用，而不是访问一个静态的态集合。所提出的混合模型通过将探索步骤视为“在线”阶段，并将相干量子计算视为“离线”阶段，解决了这一问题。

核心贡献与结果

1. 用于策略计算的新型量子算法

作者提出了用于在生成模型下计算 $\epsilon$ -最优策略的新型量子算法，作为在线学习过程的子程序：

有限时界： 一个查询复杂度为 $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$ 的量子算法。这改进了经典界限，并与同期工作 [60] 相匹配。
无限时界折扣： 一个查询复杂度为 $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$ 的量子算法。
无限时界无折扣： 一种针对弱通信 MDP 的新型量子算法，其查询复杂度为 $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$ ，假设 Bellman 算子是一个 $J$ -阶段 $\nu$ -span 收缩。

2. 改进的遗憾界限

通过利用混合模型和新的子程序，本文推导出了新的在线学习遗憾界限：

有限时界：
- 经典： 在特定参数范围内匹配了最先进的 $\tilde{O}(\sqrt{HSAT})$ ，但避免了先前工作中存在的额外项。
- 量子： 实现了 $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ 。对于 $\beta \in [1, 2)$ ，对 $T$ 的依赖关系降低为多项式对数级，打破了经典的 $\sqrt{T}$ 壁垒。
无限时界折扣：
- 经典： 在某些条件下匹配了 He 等人 [97] 的 $\tilde{O}(\sqrt{\Gamma^3SAT})$ 界限。
- 量子： 实现了 $\tilde{O}(\min\{\Gamma^{1.5}SA, \Gamma^3S\sqrt{A}\} T^{1-\beta})$ 。对于 $\beta \ge 1$ ，遗憾度相对于 $T$ 是多项式对数级的，这是一个新结果。
无限时界无折扣：
- 经典： 将 Bartlett 和 Tewari [26] 的 $\tilde{O}(\Lambda \sqrt{S^2AT})$ 改进为 $\tilde{O}(\sqrt{\Lambda SAT})$ 。
- 量子： 实现了 $\tilde{O}(\Lambda S \sqrt{A} T^{1-\beta})$ 。对于 $\beta \ge 1$ ，遗憾度是多项式对数级的，相比于之前量子工作 [98] 的 $\tilde{O}(\Lambda S^5 A^4)$ 界限有了显著提升。

3. 对预算参数 $\beta$ 的分析

本文确定了预算参数 $\beta$ 的“甜点区”（sweet spot）：

$\beta < 1$ ： 经典和量子算法在 $T$ 上都表现出多项式遗憾。
$\beta \in [1, 2)$ ： 与经典算法（仍为 $\tilde{O}(\sqrt{T})$ ）相比，量子算法在 $T$ 上实现了指数级改进（多项式对数级遗憾）。
$\beta \ge 2$ ： 随着经典算法也达到多项式对数级遗憾，量子在 $T$ 上的优势消失。

重要性与主张

本文声称，引入“一点自由”（离线生成阶段）从根本上改变了强化学习的格局。通过将遗憾的累积与策略计算解耦，作者证明了：

范式转变： 可以避免标准的 RL 启发式方法（如“面对不确定性时的乐观主义”），转而使用生成式访问直接计算最优策略。
量子优势： 量子计算机可以为学习过程提供实质性的优势，具体表现为在特定的预算参数范围（ $\beta \in [1, 2)$ ）内，实现相对于时间步数 $T$ 的多项式对数级遗憾。
模型修正： 本文纠正了先前量子 RL 文献中关于振幅估计实现的根本错误，为未来的量子 RL 研究建立了严谨的框架。

作者总结道，虽然他们的模型假设了一个离线阶段（这在所有物理设置中可能并不存在），但它激发了对新 RL 模型的探索，并强调了当智能体能够获得受限且结构化的环境模拟访问时，量子加速的潜力。他们承认，在不使用离线阶段的情况下，仍能实现多项式对数级遗憾的具有实际意义的量子 RL 模型，目前仍是一个开放性问题。