Parameter-Free Dynamic Regret for Unconstrained Linear Bandits

摘要

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 u_1,…,u_T in ℝ^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 = ∑_t𝕀u_t ≠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 𝒪(√(d(1+S_T) T)) up to poly-logarithmic terms without prior knowledge of S_T, thus resolving a long-standing open problem.