Metraipolis › archive › dc_19e441d7d136
Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms — arXiv:2608.14319
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.14319
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T02:30:38.657Z
- SHA-256 of the archived text
b823383e009f6731451b9ec16ac64bb6bb57635b13ff1ba3f85e1960426d5137- Stable URL of this page
https://metraipolis.com/documento/dc_19e441d7d136
How to cite
Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms — arXiv:2608.14319 — arXiv (en), https://arxiv.org/abs/2608.14319 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_19e441d7d136 (Metraipolis archive dc_19e441d7d136, sha256 b823383e009f6731451b9ec16ac64bb6bb57635b13ff1ba3f85e1960426d5137)
BibTeX
@misc{dc19e441d7d136,
title = {Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms — arXiv:2608.14319},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.14319},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_19e441d7d136; sha256 b823383e009f6731451b9ec16ac64bb6bb57635b13ff1ba3f85e1960426d5137},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.14319. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Theta(K\log(1+T/K))$ for QMAB and the first lower bound of $\Omega(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.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-17 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2608.14319 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T02:26:17.803Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).