Small-Loss Bounds for Online Learning with Partial Information

We consider the problem of adversarial (nonstochastic) online learning with partial-information feedback, in which, at each round, a decision maker selects an action from a finite set of alternatives. We develop a black-box approach for such problems in which the learner observes as feedback only losses of a subset of the actions that includes the selected action. When losses of actions are nonnegative, under the graph-based feedback model introduced by Mannor and Shamir, we offer algorithms that attain the so called “small-loss” $o(\alpha L^{\mathrm{\star }})$ regret bounds with high probability, where α is the independence number of the graph and $L^{\mathrm{\star }}$ is the loss of the best action. Prior to our work, there was no data-dependent guarantee for general feedback graphs even for pseudo-regret (without dependence on the number of actions, i.e., utilizing the increased information feedback). Taking advantage of the black-box nature of our technique, we extend our results to many other applications, such as combinatorial semi-bandits (including routing in networks), contextual bandits (even with an infinite comparator class), and learning with slowly changing (shifting) comparators. In the special case of multi-armed bandit and combinatorial semi-bandit problems, we provide optimal small-loss, high-probability regret guarantees of $\tilde{\mathcal{O}}(\sqrt{d{L}^{\mathrm{\star }}})$, where d is the number of actions, answering open questions of Neu. Previous bounds for multi-armed bandits and semi-bandits were known only for pseudo-regret and only in expectation. We also offer an optimal $\tilde{\mathcal{O}}(\sqrt{\kappa L^{\mathrm{\star }}})$ regret guarantee for fixed feedback graphs with clique-partition number at most κ.