An Analysis of Ensemble Sampling
  Ensemble sampling serves as a practical approximation to Thompson sampling
when maintaining an exact posterior distribution over model parameters is
computationally intractable. In this paper, we establish a Bayesian regret
bound that ensures desirable behavior when ensemble sampling is applied to the
linear bandit problem. This represents the first rigorous regret analysis of
ensemble sampling and is made possible by leveraging information-theoretic
concepts and novel analytic techniques that may prove useful beyond the scope
of this paper.
