mlsanityData to 7 Oct 2026

From Bandits to Experts: A Tale of Domination and Independence

arXiv 1307.4564 ↗First posted 17 Jul 2013cs.LG stat.MLcited by 28

Not on the map. Why?

Abstract (arXiv)

We consider the partial observability model for multi-armed bandits, introduced by Mannor and Shamir. Our main result is a characterization of regret in the directed observability model in terms of the dominating and independence numbers of the observability graph. We also show that in the undirected case, the learner can achieve optimal regret without even accessing the observability graph before selecting an action. Both results are shown using variants of the Exp3 algorithm operating on the observability graph in a time-efficient manner.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Jul 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 4; 2024: 2; 2025: 4; 2026: 10.

28 papers.

Sort:

  1. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  2. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  3. 2021Understanding Bandits with Graph Feedbackcited by 14
  4. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  5. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  6. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
  7. 2021Retrieving Black-box Optimal Images from External Databasescited by 6
  8. 2023Online Learning with Feedback Graphs: The True Shape of Regretcited by 5
  9. 2026Efficient learning by implicit exploration in bandit problems with side observationscited by 5
  10. 2026Spectral bandits for smooth graph functions with applications in recommender systemscited by 5
  11. 2026Online learning with noisy side observationscited by 4
  12. 2022Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimalitycited by 3
16 more
  1. 2024User-Side Realizationcited by 3
  2. 2024Improved Regret Bounds for Bandits with Expert Advicecited by 3
  3. 2026Revealing graph bandits for maximizing local influencecited by 2
  4. 2022Invariant Lipschitz Bandits: A Side Observation Approachcited by 1
  5. 2025Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failurecited by 1
  6. 2026Online learning with ErdHos-R'enyi side-observation graphscited by 1
  7. 2021Sayer: Using Implicit Feedback to Optimize System Policiescited by 0
  8. 2022Sequential Decision Problems with Weak Feedbackcited by 0
  9. 2025Asymptotically-Optimal Gaussian Bandits with Side Observationscited by 0
  10. 2025Online Learning with Multiple Fairness Regularizers via Graph-Structured Feedbackcited by 0
  11. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  12. 2026Laplacian Kernelized Banditcited by 0
  13. 2026Spectral bandits for smooth graph functionscited by 0
  14. 2026Spectral banditscited by 0
  15. 2026Bandits on graphs and structurescited by 0
  16. 2026Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctionscited by 0