A Novel Confidence-Based Algorithm for Structured Bandits
This addresses the challenge of improving efficiency in structured bandit problems for machine learning applications, though it appears incremental as it builds on existing bandit methods with new confidence-based techniques.
The paper tackles the problem of finite-armed stochastic bandits with correlated arm rewards by introducing a phased algorithm that uses confidence sets to exploit structure and discard suboptimal arms, showing that suboptimal arm selections can be reduced and that in some structures, regret is uniformly bounded over time with a matching lower bound.
We study finite-armed stochastic bandits where the rewards of each arm might be correlated to those of other arms. We introduce a novel phased algorithm that exploits the given structure to build confidence sets over the parameters of the true bandit problem and rapidly discard all sub-optimal arms. In particular, unlike standard bandit algorithms with no structure, we show that the number of times a suboptimal arm is selected may actually be reduced thanks to the information collected by pulling other arms. Furthermore, we show that, in some structures, the regret of an anytime extension of our algorithm is uniformly bounded over time. For these constant-regret structures, we also derive a matching lower bound. Finally, we demonstrate numerically that our approach better exploits certain structures than existing methods.