# From Bandits to Experts: A Tale of Domination and Independence

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

## Key facts

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

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

- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Retrieving Black-box Optimal Images from External Databases](https://mlsanity.com/paper/2112.14921/) (2021)
- [Spectral bandits for smooth graph functions with applications in recommender systems](https://mlsanity.com/paper/2605.20552/) (2026)
- [Online Learning with Feedback Graphs: The True Shape of Regret](https://mlsanity.com/paper/2306.02971/) (2023)
- [Efficient learning by implicit exploration in bandit problems with side observations](https://mlsanity.com/paper/2604.24555/) (2026)
- [Online learning with noisy side observations](https://mlsanity.com/paper/2604.13740/) (2026)
- [Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality](https://mlsanity.com/paper/2206.10022/) (2022)
- [User-Side Realization](https://mlsanity.com/paper/2403.15757/) (2024)
- [Improved Regret Bounds for Bandits with Expert Advice](https://mlsanity.com/paper/2406.16802/) (2024)
- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)
- [Revealing graph bandits for maximizing local influence](https://mlsanity.com/paper/2605.00489/) (2026)
- [Invariant Lipschitz Bandits: A Side Observation Approach](https://mlsanity.com/paper/2212.07524/) (2022)
- [Laplacian Kernelized Bandit](https://mlsanity.com/paper/2601.00461/) (2026)
- [Online learning with ErdHos-R'enyi side-observation graphs](https://mlsanity.com/paper/2604.25271/) (2026)
- [Sayer: Using Implicit Feedback to Optimize System Policies](https://mlsanity.com/paper/2110.14874/) (2021)
- [Sequential Decision Problems with Weak Feedback](https://mlsanity.com/paper/2212.11603/) (2022)
- [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)
- [Best-of-Both Worlds for linear contextual bandits with paid observations](https://mlsanity.com/paper/2510.07424/) (2025)
- [Spectral bandits for smooth graph functions](https://mlsanity.com/paper/2604.18420/) (2026)
- [Spectral bandits](https://mlsanity.com/paper/2604.25272/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)
- [Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions](https://mlsanity.com/paper/2605.22438/) (2026)

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