New Insights into Bootstrapping for Bandits
  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. For Bernoulli rewards, WB with multiplicative
exponential weights is mathematically equivalent to Thompson sampling (TS) and
results in near-optimal regret bounds. Similarly, in the bandit setting with
Gaussian rewards, we show that WB with additive Gaussian weights achieves
near-optimal regret. Beyond these special cases, we show that WB leads to
better empirical performance than TS for several reward distributions bounded
on $[0,1]$. For the contextual bandit setting, we give practical guidelines
that make bootstrapping simple and efficient to implement and result in good
empirical performance on real-world datasets.
