arxivcs.LG2026-06-26
Randomized Exploration for Linear Bandits via Absolute Perturbations
Toshinori Kitamura, Shuai Liu, Csaba Szepesvári
In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimisti…