Quantum Heavy-Tailed Bandits: Lower Bounds and Improved Dimension Dependence

We study stochastic multi-armed and linear bandits with heavy-tailed rewards under quantum access. The learner chooses one action at a time and accesses a quantum procedure representing that action’s reward distribution, which it can run forwards and backwards to estimate the expected reward. Assume that the reward $Y_a$ associated with each action $a$ satisfies $\mathbb{E}|Y_a{|}^{1+\alpha }\le 1$, where $\alpha \in (0,1]$. For $K$ arms and a budget of $T$ oracle queries, with $T$ at least a constant multiple of $K$, we achieve regret $\tilde{O}\left(K^{2\alpha /(1+\alpha )}{T}^{(1-\alpha )/(1+\alpha )}\right)$ and prove a lower bound matching up to logarithmic factors. This improves the linear dependence on $K$ in Wu et al. (2023) whenever $\alpha <1$. For $d$-dimensional linear bandits with $T\ge d$, we obtain the same exponent in $T$, with dimension dependence $d^{1/2+\alpha /(1+\alpha )}$ for finite action sets and $d^{1/2+2\alpha /(1+\alpha )}$ for general compact action sets. The finite-action bound depends only logarithmically on the number of actions; the compact-action result assumes access to routines for experimental design and linear optimization. These results improve the quadratic dimension dependence of Wu et al. (2023) over their established range $\alpha \in [1/3,1]$ and extend regret guarantees to the full range $\alpha \in (0,1]$. The improvements come from jointly allocating estimation queries across actions and reconstructing linear rewards from a small set of representative actions. We also establish worst-case lower bounds for linear bandits and extend the analysis to bounded central moments. Numerical simulations illustrate the theoretical trade-offs.