mlsanityData to 7 Oct 2026

Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback

arXiv 1409.8428 ↗First posted 30 Sep 2014cs.LG stat.MLcited by 61

Not on the map. Why?

Abstract (arXiv)

We present and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions, and observes some subset of the associated losses. This naturally models several situations where the losses of different actions are related, and knowing the loss of one action provides information on the loss of other actions. Moreover, it generalizes and interpolates between the well studied full-information setting (where all losses are revealed) and the bandit setting (where only the loss of the action chosen by the player is revealed). We provide several algorithms addressing different variants of our setting, and provide tight regret bounds depending on combinatorial properties of the information feedback structure.

Key facts. Cited by 61 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Sep 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 14; 2023: 14; 2024: 7; 2025: 10; 2026: 9.

61 papers.

Sort:

  1. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  2. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  3. 2023No-Regret Learning in Bilateral Trade via Global Budget Balancecited by 17
  4. 2022Contextual Information-Directed Samplingcited by 16
  5. 2022An α-regret analysis of Adversarial Bilateral Tradecited by 16
  6. 2023Repeated Bilateral Trade Against a Smoothed Adversarycited by 15
  7. 2023The Role of Transparency in Repeated First-Price Auctions with Unknown Valuationscited by 15
  8. 2021Understanding Bandits with Graph Feedbackcited by 14
  9. 2021Beyond Bandit Feedback in Online Multiclass Classificationcited by 14
  10. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  11. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  12. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
38 more
  1. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  2. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
  3. 2024Personalized Federated Learning with Mixture of Models for Adaptive Prediction and Model Fine-Tuningcited by 8
  4. 2023Delayed Bandits: When Do Intermediate Observations Help?cited by 7
  5. 2023Exploiting Correlated Auxiliary Feedback in Parameterized Banditscited by 6
  6. 2024Efficient Contextual Bandits with Uninformed Feedback Graphscited by 6
  7. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  8. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  9. 2022Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphscited by 5
  10. 2023Online Learning with Feedback Graphs: The True Shape of Regretcited by 5
  11. 2023Efficiently Learning the Graph for Semi-supervised Learningcited by 5
  12. 2024Stochastic contextual bandits with graph feedback: from independence number to MAS numbercited by 5
  13. 2025Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interferencecited by 5
  14. 2021Cooperative Online Learning with Feedback Graphscited by 4
  15. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  16. 2022Online Learning with Off-Policy Feedbackcited by 4
  17. 2023New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffscited by 4
  18. 2023On Interpolating Experts and Multi-Armed Banditscited by 4
  19. 2022Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimalitycited by 3
  20. 2024Improved Regret Bounds for Bandits with Expert Advicecited by 3
  21. 2025Graph Feedback Bandits on Similar Arms: With and Without Graph Structurescited by 3
  22. 2025Multi-model Online Conformal Prediction with Graph-Structured Feedbackcited by 3
  23. 2021Graph-Aided Online Multi-Kernel Learningcited by 2
  24. 2021Online Learning with Uncertain Feedback Graphscited by 2
  25. 2022Graph-Assisted Communication-Efficient Ensemble Federated Learningcited by 2
  26. 2024Graph Feedback Bandits with Similar Armscited by 2
  27. 2025Improved learning rates in multi-unit uniform price auctionscited by 2
  28. 2025Graph Learning Is Suboptimal in Causal Banditscited by 2
  29. 2022Improved Algorithms for Bandit with Graph Feedback via Regret Decompositioncited by 1
  30. 2022Invariant Lipschitz Bandits: A Side Observation Approachcited by 1
  31. 2023Stochastic Graph Bandit Learning with Side-Observationscited by 1
  32. 2024Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstentioncited by 1
  33. 2025Adversarial Combinatorial Semi-bandits with Graph Feedbackcited by 1
  34. 2025Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoringcited by 1
  35. 2026Impact of Connectivity on Laplacian Representations in Reinforcement Learningcited by 1
  36. 2022Online Learning in Supply-Chain Gamescited by 0
  37. 2023Leveraging User-Triggered Supervision in Contextual Banditscited by 0
  38. 2023Stochastic Contextual Bandits with Graph-based Contextscited by 0

50 most cited of 61 All 61 (JSON)