Hierarchical Bayesian Bandits

Abstract

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.

Proceedings of the 25th International Conference on Artificial Intelligence and Statistics

References in corpus (8)

• A Survey on Multi-Task Learning
• Cascading Bandits: Learning to Rank in the Cascade Model
• Meta-learning of Sequential Strategies
• Meta Dynamic Pricing: Transfer Learning Across Experiments
• Information-Theoretic Confidence Bounds for Reinforcement Learning
• Meta-learning with Stochastic Linear Bandits
• Meta-Thompson Sampling
• No Regrets for Learning the Prior in Bandits