Logarithmic Regret from Sublinear Hints

We consider the online linear optimization problem, where at every step the algorithm plays a point xt in the unit ball, and suffers loss langle ct, xtrangle for some cost vector ct that is then revealed to the algorithm. Recent work showed that if an algorithm receives a hint ht that has non-trivial correlation with ct before it plays xt, then it can achieve a regret guarantee of O(log T), improving on the bound of Theta(√T) in the standard setting. In this work, we study the question of whether an algorithm really requires a hint at every time step. Somewhat surprisingly, we show that an algorithm can obtain O(log T) regret with just O(√T) hints under a natural query model; in contrast, we also show that o(√T) hints cannot guarantee better than Omega(√T) regret. We give two applications of our result, to the well-studied setting of optimistic regret bounds and to the problem of online learning with abstention.