{"id":"arxiv/2608.14319","url":"https://arxiv.org/abs/2608.14319","tags":["cs.LG","quant-ph"],"score":0,"title":"Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms","domain":"cs.LG","source":"arxiv","authors":["Maoli Liu","Zhuohua Li","John C. S. Lui"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-14","reactions":{}}