  We propose algorithms based on a multi-level Thompson sampling scheme, for
the stochastic multi-armed bandit and its contextual variant with linear
expected rewards, in the setting where arms are clustered. We show, both
theoretically and empirically, how exploiting a given cluster structure can
significantly improve the regret and computational cost compared to using
standard Thompson sampling. In the case of the stochastic multi-armed bandit we
give upper bounds on the expected cumulative regret showing how it depends on
the quality of the clustering. Finally, we perform an empirical evaluation
showing that our algorithms perform well compared to previously proposed
algorithms for bandits with clustered arms.
