Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2301.08544 · Quantum

Multi-Armed Bandits and Quantum Channel Oracles

Simon Buchholz, Jonas M. Kübler, Bernhard Schölkopf

Published Mar 25, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2025-03-25-1672

Related papers

Quantum Exploration Algorithms for Multi-Armed Bandits

Daochen Wang, Xuchen You, Tongyang Li +1 more

Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we provide an algorithm to find the best arm with fixed confidence based on variable-time amplitude amplification and estimation. This algorithm gives a quadratic speedup compared to the best possible classical result in terms of query complexity. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

arXiv:2007.07049•Proceedings of the AAAI Conference on Artificial Intelligence•May 18, 2021•20 citations

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

Zongqi Wan, Zhijie Zhang, Tongyang Li +2 more

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.

arXiv:2205.14988•Proceedings of the AAAI Conference on Artificial Intelligence•Jun 26, 2023•13 citations

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

Maoli Liu, Zhuohua Li, John C. S. Lui

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(K\log T)$ for QMAB with $K$ arms and $O(d^2\operatorname{polylog} 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 $Θ(K\log(1+T/K))$ for QMAB and the first lower bound of $Ω(d\log(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 $\operatorname{poly}(d)$, its regret is nearly linear in $d$ and matches our lower bound up to polylogarithmic factors.

cs.LGCross-listedarXiv:2608.14319•Aug 17, 2026•0 citations

Quantum Top Arms Identification in Multi-Armed Bandits

Xuchuang Wang, Yu-Zhen Janice Chen, Matheus Guedes de Andrade +3 more

We investigate the top-$m$arm identification problem in a quantum multi-armed bandit (MAB) setting. Given$K$arms whose rewards follow Bernoulli distributions with unknown means, the objective is to return the$m$arms with the largest means with confidence at least$1-\delta$. Many practical tasks-e.g., selecting the best$m$routing paths in a quantum network or the best$m$quantum 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.$\mathrm{Q}$- GapE attains the query complexity guarantee$\tilde{O}\left(\sum_{k=1}^{K}\left(1 / \Delta_{k}^{(m)}\right) \log (1 / \delta)\right)$, where$\Delta_{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$\mathrm{Q}-\text{GapE}$consistently 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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Quantum Reinforcement Learning for Multi-Armed Bandits

Yi-Pei Liu, Kuo Li, Xi Cao +2 more

This work focuses on the multi-armed bandits (MAB) problem and proposes a quantum reinforcement learning (RL) algorithm for action selection. Existing quantum RL algorithms generally assume that some prior information about the optimal action is known, and initial probability is set unequally. Our algorithm can be executed with equal initial probability on each action, and can greatly accelerate the learning process.

Chinese Control Conference (CCC)•Jul 25, 2022•1 citation

Quantum Heavy-tailed Bandits

Wu, Yulian, Chaowen Guan, Vaneet Aggarwal +1 more

In this paper, we study multi-armed bandits (MAB) and stochastic linear bandits (SLB) with heavy-tailed rewards and quantum reward oracle. Unlike the previous work on quantum bandits that assumes bounded/sub-Gaussian distributions for rewards, here we investigate the quantum bandits problem under a weaker assumption that the distributions of rewards only have bounded $(1+v)$-th moment for some $v\in (0,1]$. In order to achieve regret improvements for heavy-tailed bandits, we first propose a new quantum mean estimator for heavy-tailed distributions, which is based on the Quantum Monte Carlo Mean Estimator and achieves a quadratic improvement of estimation error compared to the classical one. Based on our quantum mean estimator, we focus on quantum heavy-tailed MAB and SLB and propose quantum algorithms based on the Upper Confidence Bound (UCB) framework for both problems with $\Tilde{O}(T^{\frac{1-v}{1+v}})$ regrets, polynomially improving the dependence in terms of $T$ as compared to classical (near) optimal regrets of $\Tilde{O}(T^{\frac{1}{1+v}})$, where $T$ is the number of rounds. Finally, experiments also support our theoretical results and show the effectiveness of our proposed methods.

arXiv:2301.09680•Jan 23, 2023•0 citations
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.
Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we provide an algorithm to find the best arm with fixed confidence based on variable-time amplitude amplification and estimation. This algorithm gives a quadratic speedup compared to the best possible classical result in terms of query complexity. We also prove a matching quantum lower bound (up to poly-logarithmic factors).
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.
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 TTT with regret O(Klog⁡T)O(K\log T)O(KlogT) for QMAB with KKK arms and O(d2polylog⁡T)O(d^2\operatorname{polylog} T)O(d2polylogT) for ddd-dimensional QLB. This leaves open the optimal dependence on KKK and TTT and whether the dependence on ddd can be further improved. In this work, we prove the first tight minimax regret bound of Θ(Klog⁡(1+T/K))Θ(K\log(1+T/K))Θ(Klog(1+T/K)) for QMAB and the first lower bound of Ω(dlog⁡(1+T/d))Ω(d\log(1+T/d))Ω(dlog(1+T/d)) for finite-action QLB, ruling out regret independent of TTT. 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 GGG-optimal design through a query allocation matched to the design weights. When the action set has size poly⁡(d)\operatorname{poly}(d)poly(d), its regret is nearly linear in ddd and matches our lower bound up to polylogarithmic factors.
We investigate the top-mmmarm identification problem in a quantum multi-armed bandit (MAB) setting. GivenKKKarms whose rewards follow Bernoulli distributions with unknown means, the objective is to return themmmarms with the largest means with confidence at least1−δ1-\delta1−δ. Many practical tasks-e.g., selecting the bestmmmrouting paths in a quantum network or the bestmmmquantum 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\mathrm{Q}Q- GapE attains the query complexity guaranteeO~(∑k=1K(1/Δk(m))log⁡(1/δ))\tilde{O}\left(\sum_{k=1}^{K}\left(1 / \Delta_{k}^{(m)}\right) \log (1 / \delta)\right)O~(∑k=1K​(1/Δk(m)​)log(1/δ)), whereΔk(m)\Delta_{k}^{(m)}Δk(m)​denotes the gap between armkkk's mean and themmm-th largest mean. Compared with the best classical-oracle bound, this result offers a quadratic quantum speed-up. Extensive simulations confirm thatQ−GapE\mathrm{Q}-\text{GapE}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.
In this paper, we study multi-armed bandits (MAB) and stochastic linear bandits (SLB) with heavy-tailed rewards and quantum reward oracle. Unlike the previous work on quantum bandits that assumes bounded/sub-Gaussian distributions for rewards, here we investigate the quantum bandits problem under a weaker assumption that the distributions of rewards only have bounded (1+v)(1+v)(1+v)-th moment for some v∈(0,1]v\in (0,1]v∈(0,1]. In order to achieve regret improvements for heavy-tailed bandits, we first propose a new quantum mean estimator for heavy-tailed distributions, which is based on the Quantum Monte Carlo Mean Estimator and achieves a quadratic improvement of estimation error compared to the classical one. Based on our quantum mean estimator, we focus on quantum heavy-tailed MAB and SLB and propose quantum algorithms based on the Upper Confidence Bound (UCB) framework for both problems with $\Tilde{O}(T^{\frac{1-v}{1+v}})$ regrets, polynomially improving the dependence in terms of TTT as compared to classical (near) optimal regrets of $\Tilde{O}(T^{\frac{1}{1+v}})$, where TTT is the number of rounds. Finally, experiments also support our theoretical results and show the effectiveness of our proposed methods.