Parameter-Free Dynamic Regret for Unconstrained Linear Bandits

Abstract

We study dynamic regret minimization in unconstrained adversarial linear bandit problems. In this setting, a learner must minimize the cumulative loss relative to an arbitrary sequence of comparators ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_T$ in ${\mathbb{R}}^d$, but receives only point-evaluation feedback on each round. We provide a simple approach to combining the guarantees of several bandit algorithms, allowing us to optimally adapt to the number of switches $S_T={\sum }_t\mathbb{I}\{{\mathbf{u}}_t\ne {\mathbf{u}}_{t-1}\}$ of an arbitrary comparator sequence. In particular, we provide the first algorithm for linear bandits achieving the optimal regret guarantee of order $\mathcal{O}\left(\sqrt{d(1+S_T)T}\right)$ up to poly-logarithmic terms without prior knowledge of $S_T$, thus resolving a long-standing open problem.

10 pages. v1: AISTATS 2026