Generalizing Hierarchical Bayesian Bandits
A contextual bandit is a popular and practical framework for online learning
to act under uncertainty. In many problems, the number of actions is huge and
their mean rewards are correlated. In this work, we introduce a general
framework for capturing such correlations through a two-level graphical model
where actions are related through multiple shared latent parameters. We propose
a Thompson sampling algorithm G-HierTS that uses this structure to explore
efficiently and bound its Bayes regret. The regret has two terms, one for
learning action parameters and the other for learning the shared latent
parameters. The terms reflect the structure of our model as well as the quality
of priors. Our theoretical findings are validated empirically using both
synthetic and real-world problems. We also experiment with G-HierTS that
maintains a factored posterior over latent parameters. While this approximation
does not come with guarantees, it improves computational efficiency with a
minimal impact on empirical regret.