# Bandits with Feedback Graphs and Switching Costs

arXiv: https://arxiv.org/abs/1907.12189 · HTML: https://mlsanity.com/paper/1907.12189/

## Key facts

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

## Built on by (most cited first, 17 of 17)

- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Near-Optimal Adversarial Reinforcement Learning with Switching Costs](https://mlsanity.com/paper/2302.04374/) (2023)
- [Understanding the Role of Feedback in Online Learning with Switching Costs](https://mlsanity.com/paper/2306.09588/) (2023)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [Online Learning with Uncertain Feedback Graphs](https://mlsanity.com/paper/2106.08441/) (2021)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Laplacian Kernelized Bandit](https://mlsanity.com/paper/2601.00461/) (2026)
- [Continuous Time Bandits With Sampling Costs](https://mlsanity.com/paper/2107.05289/) (2021)
- [Asymptotically-Optimal Gaussian Bandits with Side Observations](https://mlsanity.com/paper/2505.10698/) (2025)
- [Online Learning with Multiple Fairness Regularizers via Graph-Structured Feedback](https://mlsanity.com/paper/2508.14311/) (2025)
- [Minimax-Optimal Policy Regret in Partially Observable Markov Games](https://mlsanity.com/paper/2606.02363/) (2026)
- [Two-Action Apple Tasting with Switching Costs](https://mlsanity.com/paper/2606.03851/) (2026)
- [Beyond Binary: Continuous State Optimization with Graph-Structured Objectives](https://mlsanity.com/paper/2608.09366/) (2026)

## 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.