💻 computer science

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-08-14

📖 1 分钟阅读☕ 轻松阅读

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

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

想象一下，你正在试图教一个机器人如何在巨大的、不断变化的迷宫中导航，以寻找最好的宝藏。在计算机科学领域，这被称为强化学习（Reinforcement Learning）。这个机器人（“智能体”）并没有地图；它只知道尝试某个动作后会发生什么。如果它走了一步撞到了墙，它就学到了那个动作是错误的。如果它发现了一条捷径，它就学到了那个动作是正确的。目标是找出获取尽可能多宝藏的最优动作序列。

通常情况下，机器人必须通过在迷宫中实际行走、犯错并陷入困境来学习。这既慢又令人沮丧。但如果机器人拥有一个“魔法模拟器”呢？这个模拟器可以让机器人暂停时间、倒带，并瞬间尝试成千上万条不同的路径，而无需在现实世界中实际行走或陷入困境。这被称为生成模型（Generative Model）。它就像视频游戏中的“存档”功能，让你可以反复练习某个 Boss 战直到完全掌握获胜的方法，而无需损失哪怕一条生命。

现在，想象一下给这个机器人一个超能力：一台量子计算机。与一次只能检查一条路径的普通计算机不同，量子计算机可以同时探索许多路径，就像一个幽灵一样，可以同时穿过所有的门。现在的关键问题是，如果我们把这个“魔法模拟器”与这个“量子幽灵”结合起来，我们能否让机器人几乎瞬间掌握迷宫，从而跳过数年的试错过程？

这篇题为《一点自由，大有裨益》（A Bit of Freedom Goes a Long Way）的论文，是一场将这两个强大想法结合在一起的大胆实验。作者 Andris Ambailis、Joao F. Doriguello 和 Debbie Lim 提出了一种新的训练 AI 智能体的方法，这种方法打破了我们通常对学习方式的认知。

关于“乐观主义”的问题

在传统的强化学习中，当智能体不知道下一步会发生什么时，它必须进行猜测。为了安全起见，它通常使用一种被称为**“面对不确定性时的乐观主义”（optimism in the face of uncertainty）**的策略。想象你在一个黑暗的房间里，面前有两扇门，你不知道门后有什么。一个“悲观”的机器人会假设最坏的情况并原地不动。而一个“乐观”的机器人则假设还没尝试过的门后面就是最好的选择，以防万一。它会尝试那扇门，了解真相，然后继续前进。

作者认为，这种“猜谜游戏”实际上是一个瓶颈。它迫使智能体浪费时间去探索一些它可能并不需要确定的事物，仅仅是为了求稳。他们提出了另一种方法：停止猜测，开始模拟。

“自由”模型

该论文引入了一个混合模型，将学习过程分为两个截然不同的阶段：在线（Online）和离线（Offline）。

在线阶段（现实世界）： 智能体与真实环境进行交互。它做出一个动作，获得奖励（或惩罚），并移动到一个新状态。这是“遗憾”（regret）发生的地方。遗憾简单来说，就是智能体如果完美掌握地图所能获得的宝藏，与它实际获得的宝藏之间的差值。智能体的目标是最小化这种遗憾。
离线阶段（魔法模拟器）： 这里就是“一点自由”。智能体暂停了现实世界。它访问一个完美的模拟器（一个“生成模型”），这个模拟器充当了一个量子预言机（quantum oracle）。在这个阶段，智能体可以询问模拟器：“如果我做 X 会发生什么？”并立即得到答案，而无需在现实世界中实际执行。至关重要的是，这里不会累积任何遗憾。 智能体可以在模拟器中尽情练习、失败和学习，而不计入其最终得分。

作者称这是一个“预算”系统。智能体必须用在现实世界中花费的时间（在线）来“支付”，以换取在模拟器中花费时间（离线）的权利。它在模拟器中练习的时间越多，它在下一轮现实世界探索中的策略就会变得越好。

量子飞跃

该论文的主要发现是，当你赋予这种“自由”给一台量子计算机时，结果是惊人的。

在经典世界中（使用普通计算机），即使有了模拟器，智能体的遗憾（损失的宝藏量）通常也会随着时间的平方根（ $\sqrt{T}$ ）而增长。这意味着如果你运行智能体 100 步，你会损失一定量的宝藏；如果你运行 10,000 步，你会损失 10 倍的宝藏。这是一种缓慢且持续的增长。

然而，作者展示了通过他们的量子算法，遗憾仅随时间的**对数（logarithm）**而增长（ $\log T$ ）。

类比： 想象你在爬一座山。
- 经典智能体在爬一个陡峭的斜坡。越高的地方，保持进步就越困难。
- 量子智能体，得益于模拟器和量子加速，找到了一个隐藏的电梯。它几乎瞬间就能到达顶峰，而且随着山越来越高，爬山的“代价”（遗憾）也几乎不再增加。

论文证明，对于某些类型的问题（特别是“有限时界”和“无限时界”马尔可夫决策过程），这种量子方法可以实现经典计算机根本无法企及的效率水平。遗憾界限对步骤数 $T$ 的依赖仅为极小的对数多项式，有效地打破了经典屏障。

他们排除了什么

作者非常谨慎地指出了他们的模型不是什么。他们明确反对之前声称实现类似结果的量子强化学习论文。他们指出，那些早期的工作存在一个根本性的缺陷：它们试图在智能体仍处于现实世界交互的过程中使用量子技巧（如“振幅估计”）。

作者解释说，你不能在现实世界中“撤销”一个错误。如果机器人在现实世界中掉下了悬崖，你不能仅仅通过量子计算机按下“撤销”键让它没掉下去。之前的模型含蓄地假设可以无成本地倒带现实世界，这在逻辑上是不可能的。通过严格区分“现实”（在线）阶段和“模拟”（离线）阶段，作者修复了这个逻辑漏洞。他们表明，你必须拥有一个无遗憾的离线阶段，才能获得如此巨大的加速。

结论

这篇论文不仅暗示这可能奏效，还提供了数学证明和算法来展示这些结果。他们表明，通过允许智能体拥有一点在模拟器中练习的“自由”，并利用量子力学来处理这些练习，我们可以比以往任何时候都更快地学习到最优策略。

虽然论文指出，这依赖于能够访问“生成模型”（一个完美的模拟器），这在构建现实世界的每个问题时可能很难，但其理论突破是清晰的：一点自由，大有裨益。 通过将模拟与量子力量正确结合，通往完美学习的路径变得呈指数级缩短。

技术摘要：一点自由度大有裨益：生成模型下的经典与量子强化学习算法

问题陈述

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

有限时界 MDP： 交互发生在固定的步数 $H$ 内。
无限时界折扣 MDP： 交互无限进行，奖励因子为 $\gamma \in [0, 1)$ 。
无限时界非折扣 MDP： 交互无限进行，采用平均奖励准则，特别关注弱连通（weakly communicating）的 MDP。

强化学习中的一个核心挑战是探索与利用（exploration-exploitation）的权衡。在经典设置中，智能体在与环境交互的同时必须学习转移概率 $p(\cdot|s, a)$ 。在量子设置中，一个基本问题出现了：标准的量子算子允许叠加和逆操作，如果智能体在整个学习过程中以量子方式与环境交互，可能会导致遗憾度量定义不明。此外，此前试图实现相对于时间 $T$ 的多项式对数级遗憾的量子强化学习工作，依赖于关于量子振幅估计相干应用的错误假设。

方法论

混合在线-离线强化学习模型

为了解决量子强化学习中遗憾定义的争议并利用量子加速，作者提出了一个混合在线-离线强化学习模型。该模型将学习过程分为两个截然不同的阶段：

在线阶段（探索）： 智能体以经典方式与环境交互。它选择动作、接收奖励并观察状态转移。至关重要的是，遗憾在此阶段累积。智能体在此阶段无法访问量子算子。
离线阶段（生成式学习）： 智能体被授予通过生成模型以量子方式与环境交互的“自由”。
- 在经典离线阶段，智能体访问一个采样算子 $C_p$ ，该算子在给定 $(s, a)$ 的情况下返回下一个状态 $s'$ 。
- 在量子离线阶段，智能体访问一个量子算子 $Q_p$ （及其逆算子）来准备下一个状态的叠加态。
- 约束： 离线阶段的算子调用次数受限于前一个在线阶段长度 $\tau$ 的函数，具体为 $O(\tau^\beta)$ ，其中 $\beta \in [0, \infty)$ 是一个“预算”参数。这防止了智能体通过过度查询算子来获得几乎零遗憾的近优策略。

算法方法

所提出的算法（算法 1）按周期（epoch）推进。在每个周期 $\ell$ 中：

离线计算： 利用前一个在线阶段（长度为 $\tau_{\ell-1}$ $τ_{ℓ - 1}$ ）收集的数据，智能体计算一个 $\epsilon_\ell$ $ϵ_{ℓ}$ -最优策略。
- 经典： 使用已知的样本最优算法（例如 Sidford 等人的算法）来计算策略。
- 量子： 作者引入了用于在生成模型下计算最优策略的新型量子算法。这些算法利用量子均值估计（Kothari 和 O'Donnell）和量子最小/最大值查找（Dürr 和 Høyer）来加速价值迭代。
在线执行： 计算出的策略 $\pi^{(\ell)}$ 在环境中执行，其持续时间由倍增技巧（doubling trick，将时界增加因子 2 或 $2H$ ）决定。
遗憾分析： 总遗憾通过对每个在线阶段所使用的策略的次优性进行求和来界定。

关键技术贡献

针对生成模型的创新量子算法：
- 有限时界： 作者设计的量子算法改进了查询复杂度。他们结合了量化价值迭代与方差缩减技术。其查询复杂度为 $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$ ，相比经典界限，改善了对 $H$ 和 $A$ 的依赖关系。
- 无限时界折扣： 实现了类似的改进，查询复杂度为 $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$ 。
- 无限时界非折扣： 这是一个新的贡献。作者提出了一种在假设最优贝尔曼算子是 $J$ -阶段 $\nu$ -展缩（ $\nu$ -span contraction）的条件下，针对弱连通 MDP 的量子算法。其复杂度为 $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$ 。
对先前量子强化学习工作的修正：
本文批判了之前声称具有多项式对数级遗憾的工作（如 Ganguly 等人，Zhong 等人）。作者认为这些工作错误地假设量子振幅估计可以作用于一个存储的状态集合，而不是要求对算子及其逆算子进行顺序的、相干的应用。所提出的混合模型通过强制执行一个独立的离线阶段来纠正这一点，在该阶段可以进行此类相干操作而不产生遗憾。
混合模型下的遗憾界限：
作者推导了经典和量子设置下遗憾随预算参数 $\beta$ 变化的界限：
- 有限时界：
  - 经典：当 $\beta \ge 2$ 时，为 $\tilde{O}(\sqrt{HSAT})$ （符合当前最优水平）。
  - 量子：当 $\beta < 1$ 时，为 $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ ；当 $\beta \ge 1$ 时，对于 $T$ 是多项式对数级的。
- 无限时界折扣：
  - 量子：当 $\beta \ge 1$ 时，实现 $\tilde{O}(\text{polylog}(T))$ 遗憾，打破了经典的 $\Omega(\sqrt{T})$ 壁垒。
- 无限时界非折扣：
  - 量子：当 $\beta \ge 1$ 时，实现 $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ 遗憾，显著改进了先前量子工作的 $\tilde{O}(\Lambda S^5 A^4)$ 界限。

结果与意义

本文声称，通过离线生成阶段提供的“一点自由度”可以显著提高学习效率。

量子优势： 最显著的结果是证明了量子计算机可以在时间时界 $T$ 上实现多项式对数级遗憾（特别是在 $\beta \in [1, 2)$ 时），而在此类设置下，经典算法在本质上受限于 $\Omega(\sqrt{T})$ 遗憾。这代表了在 $T$ 上的指数级改进。
参数依赖性： 与经典算法及之前的量子尝试相比，量子算法改进了对状态空间大小 $S$ 、动作空间大小 $A$ 以及时界 $H$ （或有效时界 $\Gamma$ ）的依赖关系。
模型有效性： 本文确立了混合在线-离线模型是量子强化学习的一个必要且有意义的框架。它解决了量子交互中定义遗憾的歧义，并修正了先前文献中关于无需遗憾的量子探索的理论缺陷。

作者总结道，虽然当预算 $\beta$ 非常大（ $\beta \ge 2$ ，此时经典算法也能达到多项式对数级遗憾）时，在 $T$ 上的指数级量子优势会消失，但在关键范围（ $\beta \in [1, 2)$ ）内，量子计算机能提供实质性的优势。作者认为，该范围是所提模型下量子强化学习加速效果最显著的主要领域。