Structure Adaptive Algorithms for Stochastic Bandits
This work addresses the challenge of efficiently exploiting structural assumptions in bandit problems, which is incremental as it generalizes recent iterative methods from pure exploration to reward maximization.
The paper tackles the problem of reward maximization in structured stochastic multi-armed bandits by developing flexible, efficient algorithms that adapt to various structural constraints like linearity or sparsity, achieving asymptotically optimal performance with finite-time regret bounds and computational efficiency compared to prior methods.
We study reward maximisation in a wide class of structured stochastic multi-armed bandit problems, where the mean rewards of arms satisfy some given structural constraints, e.g. linear, unimodal, sparse, etc. Our aim is to develop methods that are flexible (in that they easily adapt to different structures), powerful (in that they perform well empirically and/or provably match instance-dependent lower bounds) and efficient in that the per-round computational burden is small. We develop asymptotically optimal algorithms from instance-dependent lower-bounds using iterative saddle-point solvers. Our approach generalises recent iterative methods for pure exploration to reward maximisation, where a major challenge arises from the estimation of the sub-optimality gaps and their reciprocals. Still we manage to achieve all the above desiderata. Notably, our technique avoids the computational cost of the full-blown saddle point oracle employed by previous work, while at the same time enabling finite-time regret bounds. Our experiments reveal that our method successfully leverages the structural assumptions, while its regret is at worst comparable to that of vanilla UCB.