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(KlogT) for QMAB with
K arms and
O(d2polylogT) 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
Θ(Klog(1+T/K)) for QMAB and the first lower bound of
Ω(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
poly(d), its regret is nearly linear in
d and matches our lower bound up to polylogarithmic factors.
Multi-armed bandits are one of the theoretical pillars of reinforcement learning. Recently, the investigation of quantum algorithms for multi-armed bandit problems was started, and it was found that a quadratic speed-up (in query complexity) is possible when the arms and the randomness of the rewards of the arms can be queried in superposition. Here we introduce further bandit models where we only have limited access to the randomness of the rewards, but we can still query the arms in superposition. We show that then the query complexity is the same as for classical algorithms. This generalizes the prior result that no speed-up is possible for unstructured search when the oracle has positive failure probability.
We investigate the top-
marm identification problem in a quantum multi-armed bandit (MAB) setting. Given
Karms whose rewards follow Bernoulli distributions with unknown means, the objective is to return the
marms with the largest means with confidence at least
1−δ. Many practical tasks-e.g., selecting the best
mrouting paths in a quantum network or the best
mquantum circuits for a given computation-fit naturally into this framework. We introduce Q-GapE, an elimination-based algorithm that queries each arm through a weak quantum oracle.
Q- GapE attains the query complexity guarantee
O~(∑k=1K(1/Δk(m))log(1/δ)), where
Δk(m)denotes the gap between arm
k's mean and the
m-th largest mean. Compared with the best classical-oracle bound, this result offers a quadratic quantum speed-up. Extensive simulations confirm that
Q−GapEconsistently outperforms leading classical MAB algorithms in both query complexity and running time. These findings highlight the potential of quantum bandit algorithms to deliver substantial efficiency gains over their classical counterparts.
Best arm identification (BAI) is a key problem in stochastic multi-armed bandits, where K arms each has an associated reward distribution, and the objective is to minimize the number of queries needed to identify the best arm with high confidence. In this paper, we explore BAI using quantum oracles. For the case where each query probes only one arm (m=1), we devise a quantum algorithm with a query complexity upper bound of O((K/Delta)log(1/delta)), where delta is the confidence parameter and Delta is the reward gap between best and second best arms. This improves on the classical bound by a factor of 1/Delta. For the general case where a single query can probe m arms (1
Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon T suffer from the regret of at least the square root of T. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with the order of the polylog T regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.
Quantum multi-armed bandits (MAB) and stochastic linear bandits (SLB) have recently attracted significant attention, as their quantum counterparts can achieve quadratic speedups over classical MAB and SLB. However, most existing quantum MAB algorithms assume ideal quantum Monte Carlo (QMC) procedures on noise-free circuits, overlooking the impact of noise in current noisy intermediate-scale quantum (NISQ) devices. In this paper, we study a noise-robust QMC algorithm that improves estimation accuracy when querying quantum reward oracles. Building on this estimator, we propose noise-robust QMAB and QSLB algorithms that enhance performance in noisy environments while preserving the advantage over classical methods. Experiments show that our noise-robust approach improves QMAB estimation accuracy and reduces regret under several quantum noise models.