Timezone: »

Multiplier Bootstrap-based Exploration
Runzhe Wan · Haoyu Wei · Branislav Kveton · Rui Song

Thu Jul 27 01:30 PM -- 03:00 PM (PDT) @ Exhibit Hall 1 #641

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.

Author Information

Runzhe Wan (Amazon)
Haoyu Wei
Branislav Kveton (AWS AI Labs)
Rui Song (Amazon Inc)

More from the Same Authors