קוונטי מיולטי-ארמד בנדיטס ולינארי בנדיטס: גבולות ואלגוריתמים

תקציר מקורי באנגליתarXiv:2608.14319v2 Announce Type: replace Abstract: 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