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

IEEE International Conference on Quantum Control, Computing and Learning (qCCL)

An Efficient Quantum Algorithm for Sparse Linear Bandits via Smoothed Exploration

Jiarui Hu, Wenzhi Chen, Shipra Singh, Lijun Chen

Published Jun 1, 2026• 0 citations
Publisher

Abstract

Stochastic linear bandits are an important model for sequential decision-making, for which classical algorithms typically incur a regret scaling of $\tilde {\mathcal{O}}(d\sqrt T )$. Recent quantum linear bandit algorithms use quantum mean estimation to reduce the dependence on the time horizon T, achieving O(d2poly(logT)) regret, but they do not exploit sparsity inherent in many systems and still retain polynomial dependence on the ambient dimension d. We propose Q-Lasso-OFU, a two-phase quantum algorithm for sparse linear bandits. With sparsity s, our regret bound depends logarithmically on the ambient dimension d and polynomially on the sparsity s. Suppose that the nonzero components of θ⋆are lower bounded in magnitude by γ0. Once the horizon exceeds a finite identification time, the algorithm commits to an optimal action and achieves horizon-independent problem-dependent regret $\tilde {\mathcal{O}}\left( {{s^4}\log d\log \left( {1/{\gamma _0}} \right)} \right) + \tilde {\mathcal{O}}\left( {{s^4}\log d/{\gamma _0}} \right)$. Specifically, during the exploration phase, the regret from estimation error is $\tilde {\mathcal{O}}\left( {{s^4}\log d\log T} \right)$, logarithmic in both T and d, and after that the regret is zero. Compared with prior works in quantum bandits, our bound has a logarithmic dependence on d under sparsity. Numerical experiments support our theoretical results.

DOI
10.1109/qccl70331.2026.11668575

Related papers

Regret Bounds for Quantum Linear Bandits

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

We study $d$-dimensional quantum linear bandits with bounded rewards, where the learner selects an action and queries its quantum reward oracle or its inverse in each round. For general action sets, existing algorithms achieve regret $O(d^{3/2}\operatorname{polylog}(T))$ over $T$ rounds. Prior work established a lower bound of $Ω(d\log(1+T/d))$, leaving open whether the $d^{3/2}$ dependence in the upper bound is necessary. We resolve this question by proving a minimax lower bound of $Ω(d^{3/2}\log(1+T/d^{3/2}))$. To prove this result, we construct a family of hard instances in which the reward gap of each action is proportional to its squared distance from the optimal action. We establish a posterior Fisher information bound for adaptive quantum queries with quantum memory, relating the information acquired about the optimal direction to the regret incurred. Viewing each selected action as an estimate of the optimal direction, we use a matrix Cramér--Rao argument to derive a lower bound on expected regret. When the action set is fixed and has size $K$, we propose two phased elimination algorithms, Soft-G-Elim and QG-Elim. We adapt quantum phase estimation to construct SoftQME, a mean estimator with small bias and controlled tails. Soft-G-Elim estimates the mean reward of every surviving action from independent SoftQME outputs on the support of an experimental design. Controlling the bias and fluctuations of these estimates yields regret $O(d\log T\log(dT)\sqrt{\log(KT)})$, reducing the $\log(KT)\log\log(dT)$ factor in the previous regret bound to $\sqrt{\log(KT)}$. QG-Elim further reduces this factor to $\min\{\sqrt{\log(KT)},\sqrt d\}$.

arXiv:2611.15237•Nov 11, 2026•0 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 Lipschitz Bandits

Bongsoo Yi, Yue Kang, Yao Li

The Lipschitz bandit is a key variant of stochastic bandit problems where the expected reward function satisfies a Lipschitz condition with respect to an arm metric space. With its wide-ranging practical applications, various Lipschitz bandit algorithms have been developed, achieving the cumulative regret lower bound of order $\tilde O(T^{(d_z+1)/(d_z+2)})$ over time horizon $T$. Motivated by recent advancements in quantum computing and the demonstrated success of quantum Monte Carlo in simpler bandit settings, we introduce the first quantum Lipschitz bandit algorithms to address the challenges of continuous action spaces and non-linear reward functions. Specifically, we first leverage the elimination-based framework to propose an efficient quantum Lipschitz bandit algorithm named Q-LAE. Next, we present novel modifications to the classical Zooming algorithm, which results in a simple quantum Lipschitz bandit method, Q-Zooming. Both algorithms exploit the computational power of quantum methods to achieve an improved regret bound of $\tilde O(T^{d_z/(d_z+1)})$. Comprehensive experiments further validate our improved theoretical findings, demonstrating superior empirical performance compared to existing Lipschitz bandit methods.

arXiv:2504.02251•Apr 3, 2025•2 citations

Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities

Su, Yuexin, Ziyi Yang, Huang, Peiyuan +2 more

Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon $T$ achieve a problem-independent regret bound of ${O}(\sqrt{T})$ and a problem-dependent bound of ${O}(\log T)$. In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of $(1+\sqrt{B/\mathrm{OPT}_\mathrm{LP}})$, where $B$ is budget constraint in BwK and $\mathrm{OPT}_{\mathrm{LP}}$ denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints and hence shed light on operations research.

arXiv:2507.04438•Jul 6, 2025•2 citations

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•15 citations

Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret

Han Zhong, Jiachen Hu, Yecheng Xue +2 more

While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design provably efficient quantum RL algorithms that can address the exploration-exploitation trade-off. To this end, we propose a novel UCRL-style algorithm that takes advantage of quantum computing for tabular Markov decision processes (MDPs) with $S$ states, $A$ actions, and horizon $H$, and establish an $\mathcal{O}(\mathrm{poly}(S, A, H, \log T))$ worst-case regret for it, where $T$ is the number of episodes. Furthermore, we extend our results to quantum RL with linear function approximation, which is capable of handling problems with large state spaces. Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with $d$-dimensional linear representation and prove that it enjoys $\mathcal{O}(\mathrm{poly}(d, H, \log T))$ regret. Our algorithms are variants of UCRL/UCRL-VTR algorithms in classical RL, which also leverage a novel combination of lazy updating mechanisms and quantum estimation subroutines. This is the key to breaking the $Ω(\sqrt{T})$-regret barrier in classical RL. To the best of our knowledge, this is the first work studying the online exploration in quantum RL with provable logarithmic worst-case regret.

arXiv:2302.10796•Feb 21, 2023•8 citations
Stochastic linear bandits are an important model for sequential decision-making, for which classical algorithms typically incur a regret scaling of O~(dT)\tilde {\mathcal{O}}(d\sqrt T )O~(dT​). Recent quantum linear bandit algorithms use quantum mean estimation to reduce the dependence on the time horizon T, achieving O(d2poly(logT)) regret, but they do not exploit sparsity inherent in many systems and still retain polynomial dependence on the ambient dimension d. We propose Q-Lasso-OFU, a two-phase quantum algorithm for sparse linear bandits. With sparsity s, our regret bound depends logarithmically on the ambient dimension d and polynomially on the sparsity s. Suppose that the nonzero components of θ⋆are lower bounded in magnitude by γ0. Once the horizon exceeds a finite identification time, the algorithm commits to an optimal action and achieves horizon-independent problem-dependent regret O~(s4log⁡dlog⁡(1/γ0))+O~(s4log⁡d/γ0)\tilde {\mathcal{O}}\left( {{s^4}\log d\log \left( {1/{\gamma _0}} \right)} \right) + \tilde {\mathcal{O}}\left( {{s^4}\log d/{\gamma _0}} \right)O~(s4logdlog(1/γ0​))+O~(s4logd/γ0​). Specifically, during the exploration phase, the regret from estimation error is O~(s4log⁡dlog⁡T)\tilde {\mathcal{O}}\left( {{s^4}\log d\log T} \right)O~(s4logdlogT), logarithmic in both T and d, and after that the regret is zero. Compared with prior works in quantum bandits, our bound has a logarithmic dependence on d under sparsity. Numerical experiments support our theoretical results.
We study ddd-dimensional quantum linear bandits with bounded rewards, where the learner selects an action and queries its quantum reward oracle or its inverse in each round. For general action sets, existing algorithms achieve regret O(d3/2polylog⁡(T))O(d^{3/2}\operatorname{polylog}(T))O(d3/2polylog(T)) over TTT rounds. Prior work established a lower bound of Ω(dlog⁡(1+T/d))Ω(d\log(1+T/d))Ω(dlog(1+T/d)), leaving open whether the d3/2d^{3/2}d3/2 dependence in the upper bound is necessary. We resolve this question by proving a minimax lower bound of Ω(d3/2log⁡(1+T/d3/2))Ω(d^{3/2}\log(1+T/d^{3/2}))Ω(d3/2log(1+T/d3/2)). To prove this result, we construct a family of hard instances in which the reward gap of each action is proportional to its squared distance from the optimal action. We establish a posterior Fisher information bound for adaptive quantum queries with quantum memory, relating the information acquired about the optimal direction to the regret incurred. Viewing each selected action as an estimate of the optimal direction, we use a matrix Cramér--Rao argument to derive a lower bound on expected regret. When the action set is fixed and has size KKK, we propose two phased elimination algorithms, Soft-G-Elim and QG-Elim. We adapt quantum phase estimation to construct SoftQME, a mean estimator with small bias and controlled tails. Soft-G-Elim estimates the mean reward of every surviving action from independent SoftQME outputs on the support of an experimental design. Controlling the bias and fluctuations of these estimates yields regret O(dlog⁡Tlog⁡(dT)log⁡(KT))O(d\log T\log(dT)\sqrt{\log(KT)})O(dlogTlog(dT)log(KT)​), reducing the log⁡(KT)log⁡log⁡(dT)\log(KT)\log\log(dT)log(KT)loglog(dT) factor in the previous regret bound to log⁡(KT)\sqrt{\log(KT)}log(KT)​. QG-Elim further reduces this factor to min⁡{log⁡(KT),d}\min\{\sqrt{\log(KT)},\sqrt d\}min{log(KT)​,d​}.
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.
The Lipschitz bandit is a key variant of stochastic bandit problems where the expected reward function satisfies a Lipschitz condition with respect to an arm metric space. With its wide-ranging practical applications, various Lipschitz bandit algorithms have been developed, achieving the cumulative regret lower bound of order O~(T(dz+1)/(dz+2))\tilde O(T^{(d_z+1)/(d_z+2)})O~(T(dz​+1)/(dz​+2)) over time horizon TTT. Motivated by recent advancements in quantum computing and the demonstrated success of quantum Monte Carlo in simpler bandit settings, we introduce the first quantum Lipschitz bandit algorithms to address the challenges of continuous action spaces and non-linear reward functions. Specifically, we first leverage the elimination-based framework to propose an efficient quantum Lipschitz bandit algorithm named Q-LAE. Next, we present novel modifications to the classical Zooming algorithm, which results in a simple quantum Lipschitz bandit method, Q-Zooming. Both algorithms exploit the computational power of quantum methods to achieve an improved regret bound of O~(Tdz/(dz+1))\tilde O(T^{d_z/(d_z+1)})O~(Tdz​/(dz​+1)). Comprehensive experiments further validate our improved theoretical findings, demonstrating superior empirical performance compared to existing Lipschitz bandit methods.
Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon TTT achieve a problem-independent regret bound of O(T){O}(\sqrt{T})O(T​) and a problem-dependent bound of O(log⁡T){O}(\log T)O(logT). In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of (1+B/OPTLP)(1+\sqrt{B/\mathrm{OPT}_\mathrm{LP}})(1+B/OPTLP​​), where BBB is budget constraint in BwK and OPTLP\mathrm{OPT}_{\mathrm{LP}}OPTLP​ denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints and hence shed light on operations research.
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.
While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design provably efficient quantum RL algorithms that can address the exploration-exploitation trade-off. To this end, we propose a novel UCRL-style algorithm that takes advantage of quantum computing for tabular Markov decision processes (MDPs) with SSS states, AAA actions, and horizon HHH, and establish an O(poly(S,A,H,log⁡T))\mathcal{O}(\mathrm{poly}(S, A, H, \log T))O(poly(S,A,H,logT)) worst-case regret for it, where TTT is the number of episodes. Furthermore, we extend our results to quantum RL with linear function approximation, which is capable of handling problems with large state spaces. Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with ddd-dimensional linear representation and prove that it enjoys O(poly(d,H,log⁡T))\mathcal{O}(\mathrm{poly}(d, H, \log T))O(poly(d,H,logT)) regret. Our algorithms are variants of UCRL/UCRL-VTR algorithms in classical RL, which also leverage a novel combination of lazy updating mechanisms and quantum estimation subroutines. This is the key to breaking the Ω(T)Ω(\sqrt{T})Ω(T​)-regret barrier in classical RL. To the best of our knowledge, this is the first work studying the online exploration in quantum RL with provable logarithmic worst-case regret.