新算法让强化学习摆脱传统困境，量子版更突破时间瓶颈。
A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
- 用模拟器自由采样，直接计算最优策略，不靠试探性假设。
- 量子算法仅需多对数级依赖时间步数，打破经典平方根瓶颈。
- 适合关注高效强化学习与量子优化的科研人员参考。
我们提出新型经典与量子在线算法，用于学习有限与无限时域马尔可夫决策过程（MDPs）。算法基于混合在线-离线强化学习框架，允许智能体定期以生成式采样方式自由交互环境，即通过“模拟器”访问。利用已知的经典算法及新的量子算法，在生成模型下近似最优策略，并嵌入学习流程中，从而避免使用“不确定性乐观”和“后验采样”等传统范式，直接计算并使用最优策略，获得优于以往工作的更优遗憾界。我们的量子算法实现的遗憾界对时间步数 $T$ 仅呈 $ ext{poly}\ log{T}$ 依赖，突破经典 $O(\sqrt{T})$ 的限制。无限时域折扣遗憾界为全新结果；在有限与无限时域无折扣情形下，结果匹配部分先前量子工作的时间依赖性，但对状态空间大小 $S$ 和动作空间大小 $A$ 的依赖更优。
原文摘要 · Abstract (English)
We propose novel classical and quantum online algorithms for learning finite- and infinite-horizon Markov Decision Processes (MDPs). Our algorithms are based on a hybrid online-offline reinforcement learning model wherein the agent can, from time to time, freely interact with the environment in a generative sampling fashion, i.e., by having access to a "simulator". By employing known classical and new quantum algorithms for approximating optimal policies under a generative model within our learning algorithms, we show that it is possible to avoid several paradigms from RL like "optimism in the face of uncertainty" and "posterior sampling" and instead compute and use optimal policies directly, which yields better regret bounds compared to previous works. Our quantum algorithms obtain regret bounds which only a $\operatorname{poly}\log{T}$ dependence on the number of time steps $T$, thus breaking the $O(\sqrt{T})$ classical barrier. Our infinite-horizon discounted regret bound is brand new, while in the finite- and infinite-horizon undiscounted settings, our results match the time dependence of some prior quantum works, but with improved dependence on other parameters like state space size $S$ and action space size $A$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。