Hierarchical Bayesian Bandits
arXiv:2111.06929
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.
arXiv commentProceedings of the 25th International Conference on Artificial Intelligence and Statistics
References in corpus (14)
- Analysis of Thompson Sampling for the multi-armed bandit problem
- A Survey on Multi-Task Learning
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Cascading Bandits: Learning to Rank in the Cascade Model
- Online Clustering of Bandits
- DCM Bandits: Learning to Rank with Multiple Clicks
- Sequential Transfer in Multi-armed Bandit with Finite Set of Models
- 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