Quantum spatial best-arm identification via quantum walks
This work addresses the limited quantum approaches for spatial constraints in reinforcement learning, offering a novel method for decision-making in constrained environments.
The paper tackles the graph bandit problem by proposing a quantum algorithm, QSBAI, that uses quantum walks to accelerate best-arm identification, analyzing success probabilities and optimal time steps for complete and bipartite graphs.
Quantum reinforcement learning has emerged as a framework combining quantum computation with sequential decision-making, and applications to the multi-armed bandit (MAB) problem have been reported. The graph bandit problem extends the MAB setting by introducing spatial constraints, yet quantum approaches remain limited. We propose a quantum algorithm for best-arm identification in graph bandits, termed Quantum Spatial Best-Arm Identification (QSBAI). The method employs quantum walks to encode superpositions over graph-constrained actions, extending amplitude amplification and generalizing the Quantum BAI algorithm via Szegedy's walk framework. This establishes a link between Grover-type search and reinforcement learning tasks with structural restrictions. We analyze complete and bipartite graphs, deriving the maximal success probability of identifying the best arm and the time step at which it is achieved. Our results highlight the potential of quantum walks to accelerate exploration in constrained environments and extend the applicability of quantum algorithms for decision-making.