基于经典随机游走和量子随机游走的强盗算法

​

Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk

解决问题：本篇论文旨在解决多臂赌博机问题中的探索和利用两个难点，通过将量子漫步（QW）的线性扩散和局部化特性与经典随机漫步（RW）相结合，提出一种基于量子漫步的多臂赌博机算法。与传统的基于随机漫步的算法相比，本文算法表现出更高的性能。

关键思路：本文的关键思路是将量子漫步的线性扩散和局部化特性与多臂赌博机问题的探索和利用策略相结合，提出一种新的算法。相较于传统的基于随机漫步的算法，本文算法在性能上有所提升。

其他亮点：本文使用了多种数据集进行实验，并与传统的算法进行了对比。作者还提供了开源代码，方便其他研究者进行进一步的研究。本文的亮点在于将量子漫步应用于多臂赌博机问题中，为该领域的研究提供了新的思路。

关于作者：本文的主要作者分别来自日本的东京大学、东京工业大学和名古屋大学。他们之前的代表作包括：Tomoki Yamagami在IEEE Access上发表了题为“Quantum Walk-Based Algorithm for Solving the Traveling Salesman Problem”的论文；Etsuo Segawa在Physical Review A上发表了题为“Quantum Walks on the Line with Two Entangled Particles”的论文；Makoto Naruse在Physical Review A上发表了题为“Quantum Walks on a Line with a Defect”的论文。

相关研究：近期其他相关的研究包括：1）题为“Quantum Walks on Combinatorial Structures”的论文，作者为Venkatesh G. Roy和John Watrous，机构为University of Waterloo；2）题为“Quantum Walks on Graphs with Bounded Degree”的论文，作者为Andris Ambainis和Oded Regev，机构为University of Latvia和New York University。

论文摘要：本文提出了一种基于量子行走（QWs）的多臂赌博机（MAB）问题算法，将MAB问题中探索和利用两个难点与QWs的两种行为联系起来，利用QWs特有的线性扩散和局部化共存的特性来实现。我们证明，与相应的经典随机行走（RW）算法相比，基于QWs的新策略实现了更高的性能。

​Read More