Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
  We study the online learning with feedback graphs framework introduced by
Mannor and Shamir (2011), in which the feedback received by the online learner
is specified by a graph $G$ over the available actions. We develop an algorithm
that simultaneously achieves regret bounds of the form:
$\smash{\mathcal{O}(\sqrt{\theta(G) T})}$ with adversarial losses;
$\mathcal{O}(\theta(G)\operatorname{polylog}{T})$ with stochastic losses; and
$\mathcal{O}(\theta(G)\operatorname{polylog}{T} + \smash{\sqrt{\theta(G) C})}$
with stochastic losses subject to $C$ adversarial corruptions. Here,
$\theta(G)$ is the clique covering number of the graph $G$. Our algorithm is an
instantiation of Follow-the-Regularized-Leader with a novel regularization that
can be seen as a product of a Tsallis entropy component (inspired by Zimmert
and Seldin (2019)) and a Shannon entropy component (analyzed in the corrupted
stochastic case by Amir et al. (2020)), thus subtly interpolating between the
two forms of entropies. One of our key technical contributions is in
establishing the convexity of this regularizer and controlling its inverse
Hessian, despite its complex product structure.
