An Analysis of Ensemble Sampling
This provides a theoretical foundation for ensemble sampling in bandit problems, which is incremental but addresses a known bottleneck in computational tractability.
The paper tackled the problem of analyzing ensemble sampling as an approximation to Thompson sampling in linear bandits, establishing a rigorous regret bound to ensure desirable behavior.
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 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.