Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
  We propose a bandit algorithm that explores by randomizing its history of
rewards. Specifically, it pulls the arm with the highest mean reward in a
non-parametric bootstrap sample of its history with pseudo rewards. We design
the pseudo rewards such that the bootstrap mean is optimistic with a
sufficiently high probability. We call our algorithm Giro, which stands for
garbage in, reward out. We analyze Giro in a Bernoulli bandit and derive a $O(K
\Delta^{-1} \log n)$ bound on its $n$-round regret, where $\Delta$ is the
difference in the expected rewards of the optimal and the best suboptimal arms,
and $K$ is the number of arms. The main advantage of our exploration design is
that it easily generalizes to structured problems. To show this, we propose
contextual Giro with an arbitrary reward generalization model. We evaluate Giro
and its contextual variant on multiple synthetic and real-world problems, and
observe that it performs well.
