mlsanityData to 14 Oct 2026

Bandits with Feedback Graphs and Switching Costs

arXiv 1907.12189 ↗First posted 29 Jul 2019cs.LG stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

We study the adversarial multi-armed bandit problem where partial observations are available and where, in addition to the loss incurred for each action, a switching cost is incurred for shifting to a new action. All previously known results incur a factor proportional to the independence number of the feedback graph. We give a new algorithm whose regret guarantee depends only on the domination number of the graph. We further supplement that result with a lower bound. Finally, we also give a new algorithm with improved policy regret bounds when partial counterfactual feedback is available.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 1; 2023: 3; 2024: 0; 2025: 3; 2026: 5.

17 papers.

Sort:

  1. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  2. 2021Understanding Bandits with Graph Feedbackcited by 14
  3. 2021Beyond Bandit Feedback in Online Multiclass Classificationcited by 14
  4. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  5. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  6. 2023Understanding the Role of Feedback in Online Learning with Switching Costscited by 4
  7. 2025Pure Exploration with Feedback Graphscited by 4
  8. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  9. 2021Online Learning with Uncertain Feedback Graphscited by 2
  10. 2026Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memorycited by 2
  11. 2026Laplacian Kernelized Banditcited by 1
  12. 2021Continuous Time Bandits With Sampling Costscited by 0
5 more
  1. 2025Asymptotically-Optimal Gaussian Bandits with Side Observationscited by 0
  2. 2025Online Learning with Multiple Fairness Regularizers via Graph-Structured Feedbackcited by 0
  3. 2026Minimax-Optimal Policy Regret in Partially Observable Markov Gamescited by 0
  4. 2026Two-Action Apple Tasting with Switching Costscited by 0
  5. 2026Beyond Binary: Continuous State Optimization with Graph-Structured Objectivescited by 0