When and why randomised exploration works (in linear bandits)

arXiv:2502.08870v2 Announce Type: replace Abstract: We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation. With this, we demonstrate that in the d-dimensional linear bandit setting, when the action space is smooth and strongly convex, randomised exploration algorithms enjoy an n-step regret bound of the order O(dsqrt{n} log(n)). Notably, this shows for the first time that there exist non-trivial linear bandit settings where Thompson sampling can achieve optimal dimension dependence in the regret.

Source: arXiv cs.LG | 2026-06-04