Stochastic Linear Bandits with Parameter Noise

arXiv:2601.23164v2 Announce Type: replace Abstract: We study the stochastic linear bandits with parameter noise model, in which the reward of action a is a^op heta where heta is sampled i.i.d. We show a regret upper bound of widetilde{O} (sqrt{d T log (K/elta) sigma^2_{max})} for a horizon T, general action set of size K of dimension d, and where sigma^2_{max} is the maximal variance of the reward for any action. We further provide a lower bound of widetilde{Omega} (d sqrt{T sigma^2_{max}}) which is tight (up to logarithmic factors) whenever log (K) approx d. For more specific action sets, ell_p unit balls with p leq 2 and dual norm q, we show that the minimax regret is widetilde{Theta} (sqrt{dT sigma^2_q)}, where sigma^2_q is a variance-dependent quantity that is always at most 4. This is in contrast to the minimax regret attainable for such sets in the classic additive noise model, where the regret is of order d sqrt{T}. Surprisingly, we show that this optimal (up to logarithmic factors) regret bound is attainable using a very simple explore-exploit algorithm.

Source: arXiv cs.LG | 2026-05-26