Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
This resolves a long-standing open problem in online learning, providing a foundational advancement for unconstrained linear bandits with broad implications in adaptive decision-making.
The paper tackles dynamic regret minimization in unconstrained adversarial linear bandits by developing a parameter-free algorithm that adapts to the number of switches in comparator sequences, achieving an optimal regret bound of O(√(d(1+S_T)T)) up to poly-logarithmic terms without prior knowledge of S_T.
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.