Parameter-Free Dynamic Regret for Unconstrained Linear Bandits

Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi, Fabio Vitale
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2998-3006, 2026.

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 \emph{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 \emph{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 \emph{without prior knowledge of $S_T$}, thus resolving a long-standing open problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-rumi26a, title = { Parameter-Free Dynamic Regret for Unconstrained Linear Bandits }, author = {Rumi, Alberto and Jacobsen, Andrew and Cesa-Bianchi, Nicol\`{o} and Vitale, Fabio}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2998--3006}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/rumi26a/rumi26a.pdf}, url = {https://proceedings.mlr.press/v300/rumi26a.html}, 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 \emph{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 \emph{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 \emph{without prior knowledge of $S_T$}, thus resolving a long-standing open problem. } }
Endnote
%0 Conference Paper %T Parameter-Free Dynamic Regret for Unconstrained Linear Bandits %A Alberto Rumi %A Andrew Jacobsen %A Nicolò Cesa-Bianchi %A Fabio Vitale %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-rumi26a %I PMLR %P 2998--3006 %U https://proceedings.mlr.press/v300/rumi26a.html %V 300 %X 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 \emph{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 \emph{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 \emph{without prior knowledge of $S_T$}, thus resolving a long-standing open problem.
APA
Rumi, A., Jacobsen, A., Cesa-Bianchi, N. & Vitale, F.. (2026). Parameter-Free Dynamic Regret for Unconstrained Linear Bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2998-3006 Available from https://proceedings.mlr.press/v300/rumi26a.html.

Related Material