Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk
Tomoki Yamagami,
Etsuo Segawa,
Takatomo Mihana,
André Röhm,
Ryoichi Horisaki,
Makoto Naruse
Affiliations
Tomoki Yamagami
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
Etsuo Segawa
Graduate School of Environment and Information Sciences, Yokohama National University, 79-1 Tokiwadai, Hodogaya, Yokohama 240-8501, Kanagawa, Japan
Takatomo Mihana
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
André Röhm
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
Ryoichi Horisaki
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
Makoto Naruse
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
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.
