Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality

We show that, surprisingly, the notion of optimal finite-time regret is not a uniquely defined property in this context and that, in general, it is decoupled from the asymptotic rate. We discuss alternative choices and propose a notion of finite-time optimality that we argue is meaningful .