mlsanityData to 7 Oct 2026

Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs

arXiv 2107.09572 ↗First posted 20 Jul 2021cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

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: smashO(√θ(G) T) with adversarial losses; O(θ(G)operatornamepolylogT) with stochastic losses; and O(θ(G)operatornamepolylogT + smash√θ(G) C) with stochastic losses subject to C adversarial corruptions. Here, θ(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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 18 of its 29 references that are in the map. First posted on arXiv 20 Jul 2021.

Builds on

18 of 29 references.

References · 18

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  5. 2015Online Learning with Feedback Graphs: Beyond Banditscited by 79
  6. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  7. 2014Nonstochastic Multi-Armed Bandits with Graph-Structured Feedbackcited by 61
  8. 2018Adversarial Attacks on Stochastic Banditscited by 56
  9. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  10. 2019Data Poisoning Attacks on Stochastic Banditscited by 52
  11. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  12. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
6 more
  1. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  2. 2016Online Learning with Feedback Graphs Without the Graphscited by 27
  3. 2020Prediction with Corrupted Expert Advicecited by 26
  4. 2017Sparsity, variance and curvature in multi-armed banditscited by 24
  5. 2019Improved Path-length Regret Bounds for Banditscited by 22
  6. 2020A Closer Look at Small-loss Bounds for Bandits with Graph Feedbackcited by 21

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 1; 2023: 1; 2024: 1.

4 papers.

  1. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  2. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  3. 2023Best of Both Worlds Policy Optimizationcited by 17
  4. 2024The Real Price of Bandit Information in Multiclass Classificationcited by 7