From Bandits to Experts: A Tale of Domination and Independence
arXiv:1307.4564
Abstract
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.
Cited by in corpus (18)
- Efficient learning by implicit exploration in bandit problems with side observations
- Spectral bandits for smooth graph functions
- Online learning with noisy side observations
- Explore no more: Improved high-probability regret bounds for non-stochastic bandits
- Revealing graph bandits for maximizing local influence
- Adaptive Monte Carlo via Bandit Allocation
- Semi-parametric dynamic contextual pricing
- Online learning with feedback graphs and switching costs
- Understanding Bandits with Graph Feedback
- Stochastic One-Sided Full-Information Bandit
- Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
- Bandits with Feedback Graphs and Switching Costs
- Sayer: Using Implicit Feedback to Optimize System Policies
- Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek
- Thompson Sampling for Unsupervised Sequential Selection
- Experts with Lower-Bounded Loss Feedback: A Unifying Framework
- Learning to Bid Without Knowing your Value
- Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback