Corralling Stochastic Bandit Algorithms
arXiv:2006.09255
Abstract
We study the problem of corralling stochastic bandit algorithms, that is combining multiple bandit algorithms designed for a stochastic environment, with the goal of devising a corralling algorithm that performs almost as well as the best base algorithm. We give two general algorithms for this setting, which we show benefit from favorable regret guarantees. We show that the regret of the corralling algorithms is no worse than that of the best algorithm containing the arm with the highest reward, and depends on the gap between the highest reward and other rewards.
References in corpus (14)
- The best of both worlds: stochastic and adversarial bandits
- More Adaptive Algorithms for Adversarial Bandits
- An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
- Learning in Games: Robustness of Fast Convergence
- Model selection for contextual bandits
- An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
- Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
- Model Selection in Contextual Stochastic Bandit Problems
- Deterministic MDPs with Adversarial Rewards and Bandit Feedback
- Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
- KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints
- Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
- OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
- Corralling a Band of Bandit Algorithms