  We present a modular approach to reinforcement learning that uses a Bayesian
representation of the uncertainty over models. The approach, BOSS (Best of
Sampled Set), drives exploration by sampling multiple models from the posterior
and selecting actions optimistically. It extends previous work by providing a
rule for deciding when to resample and how to combine the models. We show that
our algorithm achieves nearoptimal reward with high probability with a sample
complexity that is low relative to the speed at which the posterior
distribution converges during learning. We demonstrate that BOSS performs quite
favorably compared to state-of-the-art reinforcement-learning approaches and
illustrate its flexibility by pairing it with a non-parametric model that
generalizes across states.
