Corralling Stochastic Bandit Algorithms
This addresses the challenge of algorithm selection in stochastic bandit settings, which is incremental as it builds on existing bandit algorithms.
The paper tackles the problem of combining multiple stochastic bandit algorithms to create a corralling algorithm that performs nearly as well as the best base algorithm, achieving regret no worse than that of the best algorithm containing the arm with the highest reward and depending on the reward gap.
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.