由经典随机游走和量子游走驱动的强盗算法

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

作者信息

Yamagami Tomoki, Segawa Etsuo, Mihana Takatomo, Röhm André, Horisaki Ryoichi, Naruse Makoto

机构信息

Department of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo, Tokyo 113-8656, Japan.

Graduate School of Environment and Information Sciences, Yokohama National University, 79-1 Tokiwadai, Hodogaya, Yokohama 240-8501, Kanagawa, Japan.

出版信息

Entropy (Basel). 2023 May 25;25(6):843. doi: 10.3390/e25060843.

DOI:10.3390/e25060843

PMID:37372187

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC10297529/

Abstract

Quantum walks (QWs) have a property that classical random walks (RWs) do not possess-the coexistence of linear spreading and localization-and this property is utilized to implement various kinds of applications. This paper proposes RW- and QW-based algorithms for multi-armed-bandit (MAB) problems. We show that, under some settings, the QW-based model realizes higher performance than the corresponding RW-based one by associating the two operations that make MAB problems difficult-exploration and exploitation-with these two behaviors of QWs.

摘要

量子游走（QWs）具有一种经典随机游走（RWs）所不具备的特性——线性扩散与局域化的共存——并且这种特性被用于实现各种应用。本文针对多臂老虎机（MAB）问题提出了基于RW和QW的算法。我们表明，在某些设置下，基于QW的模型通过将使MAB问题变得困难的两种操作——探索和利用——与QW的这两种行为相关联，从而实现了比相应的基于RW的模型更高的性能。