# Deep Hierarchy in Bandits

arXiv: https://arxiv.org/abs/2202.01454 · HTML: https://mlsanity.com/paper/2202.01454/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 3 Feb 2022.

## Builds on (most cited first, 23 of 23)

- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://mlsanity.com/paper/1911.09724/) (2019)
- [PECOS: Prediction for Enormous and Correlated Output Spaces](https://mlsanity.com/paper/2010.05878/) (2020)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Latent Bandits Revisited](https://mlsanity.com/paper/2006.08714/) (2020)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [Contextual Bandits with Latent Confounders: An NMF Approach](https://mlsanity.com/paper/1606.00119/) (2016)
- [Efficient Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2006.06040/) (2020)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Bounded Regret for Finite-Armed Structured Bandits](https://mlsanity.com/paper/1411.2919/) (2014)
- [A Novel Confidence-Based Algorithm for Structured Bandits](https://mlsanity.com/paper/2005.11593/) (2020)

## Built on by (most cited first, 19 of 19)

- [Exponential Smoothing for Off-Policy Learning](https://mlsanity.com/paper/2305.15877/) (2023)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Hierarchical Conversational Preference Elicitation with Bandit Feedback](https://mlsanity.com/paper/2209.06129/) (2022)
- [Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning](https://mlsanity.com/paper/2406.05064/) (2024)
- [Multi-Task Off-Policy Learning from Bandit Feedback](https://mlsanity.com/paper/2212.04720/) (2022)
- [Thompson Sampling with Diffusion Generative Prior](https://mlsanity.com/paper/2301.05182/) (2023)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling](https://mlsanity.com/paper/2303.09033/) (2023)
- [Unified PAC-Bayesian Study of Pessimism for Offline Policy Learning with Regularized Importance Sampling](https://mlsanity.com/paper/2406.03434/) (2024)
- [Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis](https://mlsanity.com/paper/2401.11565/) (2024)
- [Online Posterior Sampling with a Diffusion Prior](https://mlsanity.com/paper/2410.03919/) (2024)
- [Human-in-the-Loop Contextual Bandits for Short-Term Rental Dynamic Pricing: Structural Equivalence of Historical Warm-Up and Approval-Gated Live Learning](https://mlsanity.com/paper/2606.02595/) (2026)
- [Overcoming Prior Misspecification in Online Learning to Rank](https://mlsanity.com/paper/2301.10651/) (2023)
- [A Classification View on Meta Learning Bandits](https://mlsanity.com/paper/2504.04505/) (2025)
- [Certified Policy Optimisation for Nested Causal Bandits via PAC-Bayes Risk](https://mlsanity.com/paper/2605.29788/) (2026)
- [Manifold Bandits: Bayesian Curriculum Learning over the Latent Geometry of Large Language Models](https://mlsanity.com/paper/2606.19750/) (2026)
- [Leveraging Similarities in Multi-Armed Bandits](https://mlsanity.com/paper/2606.23414/) (2026)
- [Gated Decoupled Compositional Bandits: A Unified Theory of Contextual Bandits with Supervised-Calibrated Action Scaling and Pre-Execution Gating](https://mlsanity.com/paper/2608.21993/) (2026)

## Abstract (arXiv)

Mean rewards of actions are often correlated. The form of these correlations may be complex and unknown a priori, such as the preferences of a user for recommended products and their categories. To maximize statistical efficiency, it is important to leverage these correlations when learning. We formulate a bandit variant of this problem where the correlations of mean action rewards are represented by a hierarchical Bayesian model with latent variables. Since the hierarchy can have multiple layers, we call it deep. We propose a hierarchical Thompson sampling algorithm (HierTS) for this problem, and show how to implement it efficiently for Gaussian hierarchies. The efficient implementation is possible due to a novel exact hierarchical representation of the posterior, which itself is of independent interest. We use this exact posterior to analyze the Bayes regret of HierTS in Gaussian bandits. Our analysis reflects the structure of the problem, that the regret decreases with the prior width, and also shows that hierarchies reduce the regret by non-constant factors in the number of actions. We confirm these theoretical findings empirically, in both synthetic and real-world experiments.