A Unified Approach to Translate Classical Bandit Algorithms to the Structured Bandit Setting
This work addresses the problem of efficient exploration in structured bandits for researchers and practitioners, offering a novel generalization of existing algorithms with potential for improved performance in applications like recommendations.
The paper tackles the structured bandit problem by proposing a method to generalize classical bandit algorithms like UCB and Thompson Sampling to this setting, achieving bounded regret in many practical scenarios where sub-optimal arms are pulled only O(1) times.
We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter $θ^*$. Since we do not place any restrictions of these functions, the problem setting subsumes several previously studied frameworks that assume linear or invertible reward functions. We propose a novel approach to gradually estimate the hidden $θ^*$ and use the estimate together with the mean reward functions to substantially reduce exploration of sub-optimal arms. This approach enables us to fundamentally generalize any classic bandit algorithm including UCB and Thompson Sampling to the structured bandit setting. We prove via regret analysis that our proposed UCB-C algorithm (structured bandit versions of UCB) pulls only a subset of the sub-optimal arms $O(\log T)$ times while the other sub-optimal arms (referred to as non-competitive arms) are pulled $O(1)$ times. As a result, in cases where all sub-optimal arms are non-competitive, which can happen in many practical scenarios, the proposed algorithms achieve bounded regret. We also conduct simulations on the Movielens recommendations dataset to demonstrate the improvement of the proposed algorithms over existing structured bandit algorithms.