Parameter-Free Dynamic Regret for Unconstrained Linear Bandits

View PDF HTML (experimental)

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_t\mathbb{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.

Comments: 10 pages. v1: AISTATS 2026

Subjects:

Machine Learning (cs.LG); Machine Learning (stat.ML)

Cite as: arXiv:2603.25916 [cs.LG]

(or arXiv:2603.25916v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2603.25916

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Andrew Jacobsen [view email] [v1] Thu, 26 Mar 2026 21:16:18 UTC (37 KB)