# Hierarchical Upper Confidence Bounds for Constrained Online Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 22 Oct 2024.

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

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [A Survey on Contextual Multi-armed Bandits](https://mlsanity.com/paper/1508.03326/) (2015)
- [LLMs-augmented Contextual Bandit](https://mlsanity.com/paper/2311.02268/) (2023)
- [Scout: An Experienced Guide to Find the Best Cloud Configuration](https://mlsanity.com/paper/1803.01296/) (2018)
- [Making Contextual Decisions with Low Technical Debt](https://mlsanity.com/paper/1606.03966/) (2016)
- [Regret Analysis for Hierarchical Experts Bandit Problem](https://mlsanity.com/paper/2208.05622/) (2022)

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

- [AGFT: An Adaptive GPU Frequency Tuner for Real-Time LLM Inference Optimization](https://mlsanity.com/paper/2508.01744/) (2025)

## Abstract (arXiv)

The multi-armed bandit (MAB) problem is a foundational framework in sequential decision-making under uncertainty, extensively studied for its applications in areas such as clinical trials, online advertising, and resource allocation. Traditional MAB formulations, however, do not adequately capture scenarios where decisions are structured hierarchically, involve multi-level constraints, or feature context-dependent action spaces. In this paper, we introduce the hierarchical constrained bandits (HCB) framework, which extends the contextual bandit problem to incorporate hierarchical decision structures and multi-level constraints. We propose the hierarchical constrained upper confidence bound (HC-UCB) algorithm, designed to address the complexities of the HCB problem by leveraging confidence bounds within a hierarchical setting. Our theoretical analysis establishes sublinear regret bounds for HC-UCB and provides high-probability guarantees for constraint satisfaction at all hierarchical levels. Furthermore, we derive a minimax lower bound on the regret for the HCB problem, demonstrating the near-optimality of our algorithm. The results are significant for real-world applications where decision-making processes are inherently hierarchical and constrained, offering a robust and efficient solution that balances exploration and exploitation across multiple levels of decision-making.