Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB), where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon T with regret O(Klog T) for QMAB with K arms and O(d2operatornamepolylog T) for d-dimensional QLB. This leaves open the optimal dependence on K and T and whether the dependence on d can be further improved. In this work, we prove the first tight minimax regret bound of Theta(Klog(1+T/K)) for QMAB and the first lower bound of Omega(dlog(1+T/d)) for finite-action QLB, ruling out regret independent of T. Our lower bounds rely on a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. The matching QMAB upper bound is obtained using a tail bound for the Quantum Monte Carlo (QMC) estimator. For finite-action QLB, we propose a phased elimination algorithm that combines a low-bias low-variance quantum mean estimator with a small-support G-optimal design through a query allocation matched to the design weights. When the action set has size operatornamepoly(d), its regret is nearly linear in d and matches our lower bound up to polylogarithmic factors.