Bandits with Feedback Graphs and Switching Costs
This work addresses a theoretical challenge in online learning for scenarios with limited feedback and switching penalties, offering incremental algorithmic improvements.
The paper tackles the adversarial multi-armed bandit problem with partial observations and switching costs, introducing a new algorithm that reduces regret dependence from the independence number to the domination number of the feedback graph, and provides a lower bound and improved policy regret bounds with partial counterfactual feedback.
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.