Hybrid quantum-classical algorithm for near-optimal planning in POMDPs
Gilberto Cunha, Alexandra Ramôa, André Sequeira, Michael de Oliveira, Luís Barbosa
强化学习(RL)为部分可观察到的环境的决策提供了一个原则框架,可以建模为马尔可夫决策过程,并通过动态决策贝叶斯网络紧凑地表示。 最近的进展表明,使用量子排斥采样和振幅放大相结合,可以加速对稀疏贝叶斯网络的推断,从而加快估计接受概率的计算速度。 在这一结果的基础上,我们引入了Quantum Bayesian Reinforcement Learning(QBRL),这是一种混合量子经典展望算法,用于部分可观察到的环境中基于模型的RL。 我们在量子设备的容错假设下提出了严格的、无神谕的时间复杂性分析。 与假设黑盒神谕的标准治疗不同,我们明确指定了推理过程,允许我们的界限更准确地反映真正的计算成本。 我们表明,对于动态形成稀疏的贝叶斯网络的环境,通过量子增强的信念更新,基于视界的近乎最优的规划可以更快地实现亚量子化。 此外,我们提出了数字实验,将QBRL与经典对应物在简单但说明性的决策任务上进行基准测试。 我们的研究结果详细分析了量子计算优势如何转化为决策性能,突出表明该优势在不同部署环境中的幅度可能有很大差异。
Reinforcement learning (RL) provides a principled framework for decision-making in partially observable environments, which can be modeled as Markov decision processes and compactly represented through dynamic decision Bayesian networks. Recent advances demonstrate that inference on sparse Bayesian networks can be accelerated using quantum rejection sampling combined with amplitude amplification, leading to a computational speedup in estimating acceptance probabilities. Building on this result, ...