🤖 机器学习

Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

本文提出了 MC+QUBO，这是一种利用量子启发式求解器通过 QUBO 公式化来优化回合选择的蒙特卡洛强化学习方法，从而在具有稀疏奖励和大状态空间的环境中提高收敛速度和策略质量。

原作者： Hadi Salloum, Ali Jnadi, Yaroslav Kholodov, Alexander Gasnikov

发布于 2026-01-27

📖 1 分钟阅读☕ 轻松阅读

原作者： Hadi Salloum, Ali Jnadi, Yaroslav Kholodov, Alexander Gasnikov

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

以下是该论文的通俗易懂版解释。

核心问题：通过试错学习效率极低

想象你正在尝试学习如何穿过一个巨大且混乱的迷宫。你决定使用一种叫做**蒙特卡洛强化学习（Monte Carlo Reinforcement Learning）**的方法。用通俗的话说，这意味着你多次跑完迷宫，记录下你走的每一步以及你获得的奖励（比如找到了宝箱）。在每次尝试结束时，你通过查看笔记来搞清楚哪条路径是最优的。

问题在于，这种方法效率极低：

噪声太多： 你可能跑了 100 次迷宫，但其中 90 次你只是在原地转圈或者撞到了死胡同。
冗余性： 你可能跑了 10 次迷宫，结果每次都走了完全相同的错误路径。观察这 10 次一模一样的失败尝试并不能教给你任何新知识，只会让你的笔记变得杂乱无章。
稀疏奖励： 在一个巨大的迷宫里，找到宝藏是非常罕见的。你大部分的尝试都会以零奖励结束，这让你很难学到到底什么才是有效的。

作者称之为“高样本复杂度”。这就像是在草堆里找一根针，你甚至去检查每一根草，哪怕那些草显然只是普通的干草。

解决方案：“智能编辑师”

作者提出了一种名为 MC+QUBO 的新方法。把这想象成在你的学习过程中加入了一个“智能编辑师”。

与其使用你进行的每一次尝试来更新知识，不如让这个“智能编辑师”观察一批你的尝试（比如 50 次尝试），并从中挑选出最好的 10 次进行深入研究。它会丢弃剩下的所有内容。

但它是如何决定哪 10 次才是最好的呢？它使用了两条规则：

高奖励： “这次尝试找到宝箱了吗？”（优秀的尝试会被打上绿色对勾）。
多样性： “这次尝试是否去了新的地方？” 如果你有 10 次尝试都找到了宝藏，但走的路径完全一样，那么编辑师只会保留其中一次。它希望尝试能探索迷宫的不同部分，这样你才能学会整张地图，而不仅仅是学会一条捷径。

秘诀：“量子启发式”计算器

难点在于，从 50 次尝试中选出完美的 10 次组合是一个数学上的噩梦。这里面存在数十亿种组合方式，普通计算机需要花费很长时间才能检查完所有组合。

这就是论文引入 QUBO（二次无约束二值优化）的地方。

类比： 想象你面前有一个由山丘和山谷组成的巨大、崎岖的地形。“山谷”代表好的组合（高奖励 + 高多样性），而“山丘”代表糟糕的组合。
目标： 你想尽可能快地找到最深的那个山谷。
工具： 作者使用了“量子启发式”求解器（具体为模拟量子退火和模拟分叉）。

这些工具是什么？

模拟量子退火 (SQA)： 想象一个球在崎岖的地形中滚动。一个普通的球（经典计算机）可能会卡在一个小凹陷（局部谷底）里，并误以为那就是最低点。而一个“量子”球可以穿透山丘，从而找到即使被隐藏在山脉之后的最深谷底。
模拟分叉 (SB)： 想象一个水管系统。随着你调高压力，水流会突然分叉进入特定的通道，自然而然地流向最高效的路径。

这些工具就像一个超快速的“黑盒”，能够瞬间找到最适合智能体学习的最佳尝试组合，而无需真正的量子计算机（它在普通计算机上运行，但模拟了量子物理特性）。

实验结果如何？

作者在各种规模的数字“格点世界”（GridWorld，一种简单的基于网格的迷宫）中测试了这一方法，规模从微型（3x3）到巨型（20x20）不等。

结果： “智能编辑师”（MC+QUBO）的学习速度比标准方法（Vanilla MC）快得多。
代价： 在最大的迷宫中，标准方法会陷入停滞或学习极其缓慢，因为它被大量糟糕且重复的数据淹没了。而 MC+QUло 方法则穿透了噪声，只专注于最具信息量和多样性的路径。
惊喜： 作者发现，他们甚至不需要过度强调“奖励”（宝藏）的重要性。通过主要关注多样性（覆盖地图的不同部分），智能体学会了更好的整体策略，并且不会因为试图重复某次偶然的运气而陷入僵局。

总结

论文表明，通过使用一种“量子启发式”的数学技巧作为过滤器，你可以更快地教导 AI 智能体。与其淹没在大量糟糕或重复的数据中，智能体会获得一份经过筛选的最有用的经验清单，使其即使在奖励稀缺且地图巨大的情况下，也能高效地学习迷宫。

核心要点： 关键不在于进行更多次的尝试，而在于进行正确的尝试，并利用先进的数学工具瞬间完成筛选。

技术摘要：通过 QUBO 优化实现用于蒙特卡洛强化学习的量子启发式回合选择

问题陈述
蒙特卡洛（MC）强化学习在样本效率方面面临重大挑战，特别是在具有稀疏奖励、大规模状态空间和时间相关轨迹的环境中。标准的 MC 方法依赖于样本是独立同分布（i.i.d.）的假设，而这一假设在马尔可夫性质的强化学习轨迹中被违反了。因此，MC 估计量存在以下问题：

方差传播： 回报表现出复合方差，若要降低估计误差，所需的样本数量（ $N_s$ ）随 $O(\epsilon^{-2})$ 比例缩放。
次优轨迹稀释： 在稀疏奖励领域，估计量会被低奖励轨迹所稀释，导致需要指数级增长的样本量以确保足够的覆盖范围，从而捕捉到最优路径。
组合爆炸： 从 $N$ 个候选样本中选择 $m$ 个最优子集以最大化价值估计准确性的问题，在理论上是一个 NP-hard 问题，与特征选择和集合覆盖问题同构，其解空间为 $\binom{N}{m}$ 。

方法论
作者提出了 MC+QUBO，该框架将回合选择过程重新表述为二次无约束二值优化（QUBO）问题。该方法并非使用所有采样的回合进行策略更新，而是对一批轨迹进行过滤，以选择一个既能最大化累积奖励又能促进状态空间覆盖（多样性）的子集。

QUBO 公式化： 选择问题被编码为：
$\min_{x \in \{0,1\}^n} \left( -\alpha \sum_{i=1}^n R_i x_i + \gamma \sum_{i<j} w_{ij} x_i x_j \right)$
其中：
- $x_i = 1$ 表示选择了回合 $\tau_i$ 。
- $R_i$ 是回合 $i$ 的累积奖励。
- $w_{ij}$ 代表回合之间的成对相似度（例如，访问状态集的 Jaccard 相似度）。
- $\alpha$ 是奖励缩放乘数， $\gamma$ 是惩罚项权重。
- 线性项（ $-\alpha R_i$ ）倾向于高奖励回合，而二次项（ $\gamma w_{ij}$ ）则惩罚冗余，从而鼓励选择多样化的轨迹。
量子启发式求解器： 该 QUBO 问题使用黑盒量子启发式采样器进行求解，具体包括 模拟量子退火（SQA） 和 模拟分叉（SB）。
- SQA 通过经典的随机更新和路径积分蒙特卡洛来模拟量子退火，以模拟量子隧穿效应在能量极小值之间的行为。
- SB 利用一种经典的动力系统方法，通过分叉现象使连续变量向二值状态演化。
- 作者将这些求解器视为能够在实际计算预算内提供高质量近似解的“神谕”（Oracles）。
集成： 工作流程包括生成一批回合、计算奖励和相似度、构建 QUBO、将任务分发给求解器，并使用观测到的最佳解（二值向量 $x^*$ ）来决定哪些回合用于通过首次访问 MC 更新动作价值表 $Q(s, a)$ 。

核心贡献

回合选择的重新表述： 本文建立了 MC 回合选择与组合优化之间的正式联系，证明了该选择问题可以映射到 QUBO 公式化中。
算法集成： 引入了一个具体的流水线（算法 2），在标准 MC 学习中的轨迹采样与策略评估之间插入了基于 QUBO 的过滤步骤。
实证验证： 研究在不同规模（ $3\times3$ 到 $20\times20$ ）的有限时界 GridWorld 环境中对该方法进行了评估，并将 MC+QUBO 与 vanilla MC 基准进行了对比。

结果
在 GridWorld 环境中的实验表明，MC+QUBO 在收敛速度和最终策略质量方面始终优于 vanilla MC。

可扩展性： 在较大的环境（ $\ge 10\times10$ ）中，性能差距会扩大，因为在这些环境中，稀疏奖励和指数级的状态空间增长通常会阻碍标准的 MC 评估。
收敛性： MC+QUBO 通过专注于信息丰富且多样化的轨迹，有效地过滤掉了冗余回合，从而在更少的批次内实现收敛。
设计洞察： 作者指出，优先考虑状态空间覆盖（将奖励权重影响设为接近零）比仅由奖励驱动的选择能带来更平衡的学习和更好的泛化能力，后者虽然会导致更快的收敛，但稳定性较低。
求解器性能： 在此背景下，量子启发式求解器（SQA 和 SB）的表现优于经典启发式算法（如禁忌搜索和模拟退火）。计算延迟主要由云端通信引起，而非求解器本身的时间（对于 $n \le 200$ 的情况，求解时间几乎可以忽略不计）。

意义与主张
本文声称，将量子启发式优化作为强化学习中的决策子程序，可以为 MC 方法提供切实有效的增强，特别是对于具有稀疏奖励和相关轨迹的问题。通过将 RL 与组合优化相结合，这项研究为利用量子及量子启发式方法主动引导学习过程以克服样本效率低下问题提供了路径。

作者对研究范围保持了谦逊的态度，指出虽然该框架在 GridWorld 中展现了潜力，但未来仍需探索其在连续控制、层次化 RL 及多智能体系统中的扩展，以及在真实量子硬件上的部署。目前的工作是使用物理启发式求解器来优化强化学习数据选择阶段的一个概念验证。

核心问题：通过试错学习效率极低

解决方案：“智能编辑师”

秘诀：“量子启发式”计算器

实验结果如何？

总结

类似论文