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

arXiv: https://arxiv.org/abs/2608.14319 · HTML: https://mlsanity.com/paper/2608.14319/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 14 Aug 2026.

## Builds on (most cited first, 16 of 16)

- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Quantum exploration algorithms for multi-armed bandits](https://mlsanity.com/paper/2007.07049/) (2020)
- [Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach](https://mlsanity.com/paper/1711.05174/) (2017)
- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Linear bandits with polylogarithmic minimax regret](https://mlsanity.com/paper/2402.12042/) (2024)
- [Learning pure quantum states (almost) without regret](https://mlsanity.com/paper/2406.18370/) (2024)
- [A Sublinear-Time Quantum Algorithm for Approximating Partition Functions](https://mlsanity.com/paper/2207.08643/) (2022)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Multi-Armed Bandits and Quantum Channel Oracles](https://mlsanity.com/paper/2301.08544/) (2023)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)

## Abstract (arXiv)

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.