Bandits with Feedback Graphs and Switching Costs
arXiv:1907.12189
Abstract
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 \emph{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.
arXiv commentCamera ready from NeurIPS 2019, new algorithm and improved results in Section 3.2
References in corpus (8)
- Efficient learning by implicit exploration in bandit problems with side observations
- Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
- Online Learning with Switching Costs and Other Adaptive Adversaries
- From Bandits to Experts: A Tale of Domination and Independence
- Online Learning with Abstention
- Online Learning with Feedback Graphs Without the Graphs
- Information Directed Sampling for Stochastic Bandits with Graph Feedback
- Corralling a Band of Bandit Algorithms