Multiplier Bootstrap-based Exploration
This work addresses the problem of designing efficient bandit algorithms for complex models, which is significant for researchers and practitioners in machine learning, though it appears incremental as it builds on existing bootstrap methods.
The paper tackles the challenge of quantifying uncertainty in bandit problems by proposing Multiplier Bootstrap-based Exploration (MBE), a novel exploration strategy applicable to any reward model using weighted loss minimization, and proves instance-dependent and instance-independent rate-optimal regret bounds for sub-Gaussian multi-armed bandits.
Despite the great interest in the bandit problem, designing efficient algorithms for complex models remains challenging, as there is typically no analytical way to quantify uncertainty. In this paper, we propose Multiplier Bootstrap-based Exploration (MBE), a novel exploration strategy that is applicable to any reward model amenable to weighted loss minimization. We prove both instance-dependent and instance-independent rate-optimal regret bounds for MBE in sub-Gaussian multi-armed bandits. With extensive simulation and real data experiments, we show the generality and adaptivity of MBE.