摘要
我们提出了新颖的经典与量子在线算法，用于学习有限和无限时域的马尔可夫决策过程（MDP）。我们的算法基于一种混合在线-离线强化学习模型，代理可以不时地以生成采样的方式自由与环境交互，即通过访问“模拟器”。
通过在我们的学习算法中应用已知的经典算法和新的量子算法来近似生成模型下的最优策略，我们展示了可以避免强化学习中的几个范式，如“面对不确定性的乐观”和“后验采样”，而是直接计算并使用最优策略，从而获得比以往工作更好的悔恨界限。
我们的量子算法获得的悔恨界限仅与时间步数 $ \operatorname{poly} \log{T} $ 相关，突破了经典的 $O(\sqrt{T})$ 界限。我们的无限时域折扣悔恨界限是全新的，而在有限和无限时域未折扣设置下，我们的结果与一些先前的量子工作在时间依赖性上相匹配，但对状态空间大小 $S$ 和动作空间大小 $A$ 的其他参数依赖性有了改善。
博主点评： 本文通过结合经典与量子算法，展现了在强化学习领域中生成模型的重要性，尤其是量子算法在悔恨界限上的突破，为未来的研究开辟了新的方向。该成果不仅在理论上具有突破意义，也为实际应用提供了新的思路。