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:2611.15237

Regret Bounds for Quantum Linear Bandits

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

Published Nov 11, 2026• 0 citations
arXivHTMLPDF

Abstract

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\}$.

DOI
10.48550/arxiv.2611.15237

Related papers

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

Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states

Josep Lumbreras, Erkka Haapasalo, Marco Tomamichel

We initiate the study of tradeoffs between exploration and exploitation in online learning of properties of quantum states. Given sequential oracle access to an unknown quantum state, in each round, we are tasked to choose an observable from a set of actions aiming to maximize its expectation value on the state (the reward). Information gained about the unknown state from previous rounds can be used to gradually improve the choice of action, thus reducing the gap between the reward and the maximal reward attainable with the given action set (the regret). We provide various information-theoretic lower bounds on the cumulative regret that an optimal learner must incur, and show that it scales at least as the square root of the number of rounds played. We also investigate the dependence of the cumulative regret on the number of available actions and the dimension of the underlying space. Moreover, we exhibit strategies that are optimal for bandits with a finite number of arms and general mixed states.

arXiv:2108.13050•Quantum•Jun 29, 2022•27 citations

An Efficient Quantum Algorithm for Sparse Linear Bandits via Smoothed Exploration

Jiarui Hu, Wenzhi Chen, Shipra Singh +1 more

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.

IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Jun 1, 2026•0 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

Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means

Yen-Huan Li, Wei-Fu Tseng

We study the problem of online learning of quantum states with logarithmic loss, which is a quantum generalization of online portfolio selection and has applications to quantum state tomography, the task of estimating an unknown quantum state from measurement outcomes. We first establish a regret lower bound, showing that the regret rates of Exponential Weights and the algorithm of Tseng et al. (2025) have optimal polynomial dependence on the dimension. Our analysis leads to two further results. First, our lower-bound proof leads to a quantum state tomography algorithm that is sample optimal up to polylogarithmic factors in the sample size. Second, we develop an algorithm for constructing confidence sequences for the mean of a matrix-valued random variable. A numerical experiment shows that the latter algorithm is competitive with existing methods.

cs.LGCross-listedarXiv:2610.21273•Oct 16, 2026•0 citations

Bandits roaming Hilbert space

Josep Lumbreras

This thesis studies the exploration and exploitation trade-off in online learning of properties of quantum states using multi-armed bandits. Given streaming access to an unknown quantum state, in each round we select an observable from a set of actions to maximize its expectation value. Using past information, we refine actions to minimize regret; the cumulative gap between current reward and the maximum possible. We derive information-theoretic lower bounds and optimal strategies with matching upper bounds, showing regret typically scales as the square root of rounds. As an application, we reframe quantum state tomography to both learn the state efficiently and minimize measurement disturbance. For pure states and continuous actions, we achieve polylogarithmic regret using a sample-optimal algorithm based on a weighted online least squares estimator. The algorithm relies on the optimistic principle and controls the eigenvalues of the design matrix. We also apply our framework to quantum recommender systems and thermodynamic work extraction from unknown states. In this last setting, our results demonstrate an exponential advantage in work dissipation over tomography-based protocols.

arXiv:2509.24569•Sep 29, 2025•1 citation
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.
We initiate the study of tradeoffs between exploration and exploitation in online learning of properties of quantum states. Given sequential oracle access to an unknown quantum state, in each round, we are tasked to choose an observable from a set of actions aiming to maximize its expectation value on the state (the reward). Information gained about the unknown state from previous rounds can be used to gradually improve the choice of action, thus reducing the gap between the reward and the maximal reward attainable with the given action set (the regret). We provide various information-theoretic lower bounds on the cumulative regret that an optimal learner must incur, and show that it scales at least as the square root of the number of rounds played. We also investigate the dependence of the cumulative regret on the number of available actions and the dimension of the underlying space. Moreover, we exhibit strategies that are optimal for bandits with a finite number of arms and general mixed states.
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.
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.
We study the problem of online learning of quantum states with logarithmic loss, which is a quantum generalization of online portfolio selection and has applications to quantum state tomography, the task of estimating an unknown quantum state from measurement outcomes. We first establish a regret lower bound, showing that the regret rates of Exponential Weights and the algorithm of Tseng et al. (2025) have optimal polynomial dependence on the dimension. Our analysis leads to two further results. First, our lower-bound proof leads to a quantum state tomography algorithm that is sample optimal up to polylogarithmic factors in the sample size. Second, we develop an algorithm for constructing confidence sequences for the mean of a matrix-valued random variable. A numerical experiment shows that the latter algorithm is competitive with existing methods.
This thesis studies the exploration and exploitation trade-off in online learning of properties of quantum states using multi-armed bandits. Given streaming access to an unknown quantum state, in each round we select an observable from a set of actions to maximize its expectation value. Using past information, we refine actions to minimize regret; the cumulative gap between current reward and the maximum possible. We derive information-theoretic lower bounds and optimal strategies with matching upper bounds, showing regret typically scales as the square root of rounds. As an application, we reframe quantum state tomography to both learn the state efficiently and minimize measurement disturbance. For pure states and continuous actions, we achieve polylogarithmic regret using a sample-optimal algorithm based on a weighted online least squares estimator. The algorithm relies on the optimistic principle and controls the eigenvalues of the design matrix. We also apply our framework to quantum recommender systems and thermodynamic work extraction from unknown states. In this last setting, our results demonstrate an exponential advantage in work dissipation over tomography-based protocols.