arXiv:2603.25916v1 Announce Type: new
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 $boldsymbol{u}_1,ldots,boldsymbol{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_tmathbb{I}{boldsymbol{u}_t neq boldsymbol{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}big(sqrt{d(1+S_T) T}big)$ up to poly-logarithmic terms without prior knowledge of $S_T$, thus resolving a long-standing open problem.