New Insights into Bootstrapping for Bandits

Understand

We investigate the use of bootstrapping in the bandit setting.

• We first show that the commonly used non-parametric bootstrapping (NPB) procedure can be provably inefficient and establish a near-linear lower bound on the regret incurred by it under the bandit model with Bernoulli rewards.
• We show that NPB with an appropriate amount of forced exploration can result in sub-linear albeit sub-optimal regret.
• As an alternative to NPB, we propose a weighted bootstrapping (WB) procedure.