Hierarchical Bayesian Bandits
This provides a universal and statistically efficient framework for learning in similar bandit tasks, though it is incremental as it builds on existing bandit and hierarchical methods.
The paper tackles the problem of learning across similar tasks in meta-, multi-task, and federated learning by unifying them as hierarchical Bayesian bandits, proposing a Hierarchical Thompson Sampling algorithm (HierTS) that reduces regret with more informative priors and shows improved knowledge sharing in experiments.
Meta-, multi-task, and federated learning can be all viewed as solving similar tasks, drawn from a distribution that reflects task similarities. We provide a unified view of all these problems, as learning to act in a hierarchical Bayesian bandit. We propose and analyze a natural hierarchical Thompson sampling algorithm (HierTS) for this class of problems. Our regret bounds hold for many variants of the problems, including when the tasks are solved sequentially or in parallel; and show that the regret decreases with a more informative prior. Our proofs rely on a novel total variance decomposition that can be applied beyond our models. Our theory is complemented by experiments, which show that the hierarchy helps with knowledge sharing among the tasks. This confirms that hierarchical Bayesian bandits are a universal and statistically-efficient tool for learning to act with similar bandit tasks.