# An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2020.

## Built on by (most cited first, 30 of 45)

- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2106.04763/) (2021)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Sample-Efficient Alignment for LLMs](https://mlsanity.com/paper/2411.01493/) (2024)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation](https://mlsanity.com/paper/2312.09196/) (2023)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [AHA: Human-Assisted Out-of-Distribution Generalization and Detection](https://mlsanity.com/paper/2410.08000/) (2024)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [Near Instance Optimal Model Selection for Pure Exploration Linear Bandits](https://mlsanity.com/paper/2109.05131/) (2021)
- [Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap](https://mlsanity.com/paper/2201.04469/) (2022)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [SPRT-based Efficient Best Arm Identification in Stochastic Bandits](https://mlsanity.com/paper/2207.11158/) (2022)
- [Best Arm Identification with Contextual Information under a Small Gap](https://mlsanity.com/paper/2209.07330/) (2022)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)
- [Best Arm Identification in Stochastic Bandits: Beyond β-optimality](https://mlsanity.com/paper/2301.03785/) (2023)

## Abstract (arXiv)

This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. Leveraging ideas from the theory of suprema of empirical processes, we provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. Unlike previous approaches which sample based on minimizing a worst-case variance (e.g. G-optimal design), we define an experimental design objective based on the Gaussian-width of the underlying arm set. We provide a novel lower bound in terms of this objective that highlights its fundamental role in the sample complexity. The sample complexity of our fixed confidence algorithm matches this lower bound, and in addition is computationally efficient for combinatorial classes, e.g. shortest-path, matchings and matroids, where the arm sets can be exponentially large in the dimension. Finally, we propose the first algorithm for linear bandits in the the fixed budget setting. Its guarantee matches our lower bound up to logarithmic factors.