Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Improved Bayes Regret Bounds for Multi-Task Hierarchical Bayesian Bandit Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives improved Bayes regret bounds for hierarchical Thompson sampling (HierTS) in multi-task linear and semi-bandits, and proposes HierBayesUCB with logarithmic gap-dependent bounds, covering sequential and concurrent settings.
Problem
Bayes regret of hierarchical Bayesian bandit algorithms in multi-task Gaussian linear bandits and combinatorial semi-bandits, where task parameters are drawn from a shared hyper-prior; prior bounds were loose by log factors.
Approach
Tighter posterior-variance analysis (a Cauchy-Schwarz-type inequality, a matrix bound reducing the condition-number factor from kappa^2 to kappa) improves HierTS's bound; a new hierarchical BayesUCB algorithm with UCB-based action selection yields logarithmic gap-dependent bounds, extended to concurrent and combinatorial semi-bandit settings.
Key results
- HierTS Bayes regret improved from O(m sqrt(n) log n log(mn)) to O(m sqrt(n) log n) for infinite action sets
- HierBayesUCB achieves O(m log(mn) log n) gap-dependent regret for finite action sets
- Combinatorial HierTS attains O(m sqrt(n) log n) and combinatorial HierBayesUCB O(m log(mn) log n)
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Improve the regret analysis of HierTS | HierTS · Multi-task Gaussian linear bandit, infinite action set, sequential | Bayes regret upper bound: O(m√(n log n log (mn))) -> O(m√n log n) | Helped |
| Use HierBayesUCB instead of HierTS | Multi-task Gaussian linear bandit · Finite action set, sequential | Bayes regret upper bound: O(md√(n log (n/d))) -> O(md log (n/d) log (mn)) | Helped |
| Improve the concurrent regret analysis of HierTS | HierTS · Multi-task Gaussian linear bandit, infinite action set, concurrent | Bayes regret upper bound: O(md√(n log (n/d) log (mn))) -> O(md√(n log (n/d))) | Helped |
| Extend HierBayesUCB to combinatorial semi-bandits | Combinatorial HierBayesUCB · Multi-task Gaussian combinatorial semi-bandit, sequential | Bayes regret upper bound: O(m√n log n) -> O(m log n log (mn)) | Helped |
| Increase the number of tasks m (ablation) | HierTS · Synthetic linear bandit | regret | Hurt |
| Increase the number of rounds n (ablation) | HierTS · Synthetic linear bandit | regret | Hurt |
| Increase the action-space dimension d (ablation) | HierTS · Synthetic linear bandit | regret | Hurt |
| Increase the number of concurrent tasks L (ablation) | HierTS · Synthetic linear bandit | regret | No clear effect |
| Reduce the hyper-prior variance σq (ablation) | HierTS · Synthetic linear bandit | regret | Helped |
| Reduce the task variance σ0 (ablation) | HierTS · Synthetic linear bandit | regret | Helped |
| Reduce the reward-noise variance σ (ablation) | HierTS · Synthetic linear bandit | regret | Helped |
| Use HierBayesUCB instead of HierTS | Hierarchical Bayesian bandit algorithms · Synthetic linear bandit | regret | Helped |
Limitations
- Gap-dependent bound scales with 1/min gap, which can blow up when gaps are below 1/(mn)
- Assumes Gaussian rewards and known prior hyper-parameters
- Experiments are only synthetic linear bandit settings
Experimental setup
Datasets: synthetic Gaussian linear bandit instances
Benchmarks: synthetic Gaussian linear bandit experiments
Metrics: cumulative Bayes regret
Baselines: HierTS (Hong et al. 2022) vanilla TS OracleTS Kveton et al. 2021 combinatorial hierarchical TS
Builds on: HierTS (Hong et al. 2022) Bayes regret analysis of Thompson sampling (Russo and Van Roy; Min et al. 2021 C BayesUCB (Kaufmann et al. 2012) Hierarchical Bayesian bandit (Penicheiro/Kveton et al. 2021)
Closest papers by meaning
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.88)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.88)
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.88)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling (ICLR 2024 · similarity 0.87)
- Bayesian Analysis of Combinatorial Gaussian Process Bandits (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.