# Instance-optimal PAC Algorithms for Contextual Bandits

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 49 references that are in the map.
- First posted on arXiv 5 Jul 2022.

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

- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints](https://mlsanity.com/paper/1807.00028/) (2018)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Active Learning for Cost-Sensitive Classification](https://mlsanity.com/paper/1703.01014/) (2017)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits](https://mlsanity.com/paper/2010.12247/) (2020)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Efficient and Parsimonious Agnostic Active Learning](https://mlsanity.com/paper/1506.08669/) (2015)
- [Simple Regret Minimization for Contextual Bandits](https://mlsanity.com/paper/1810.07371/) (2018)
- [Bayesian Meta-Prior Learning Using Empirical Bayes](https://mlsanity.com/paper/2002.01129/) (2020)
- [Linearly Convergent Frank-Wolfe with Backtracking Line-Search](https://mlsanity.com/paper/1806.05123/) (2018)

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

- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Concentrated Differential Privacy for Bandits](https://mlsanity.com/paper/2309.00557/) (2023)
- [Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization](https://mlsanity.com/paper/2307.02108/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Adaptive Experimental Design and Counterfactual Inference](https://mlsanity.com/paper/2210.14369/) (2022)
- [Experiment Planning with Function Approximation](https://mlsanity.com/paper/2401.05193/) (2024)
- [Understanding What Affects the Generalization Gap in Visual Reinforcement Learning: Theory and Empirical Evidence](https://mlsanity.com/paper/2402.02701/) (2024)
- [Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning](https://mlsanity.com/paper/2402.12711/) (2024)
- [A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Models](https://mlsanity.com/paper/2304.04916/) (2023)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)
- [A Statistical Test for the Benefits of Personalizing Interventions](https://mlsanity.com/paper/2607.08951/) (2026)
- [Experimental Design for Semiparametric Bandits](https://mlsanity.com/paper/2506.13390/) (2025)
- [Active Learning for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2605.24803/) (2026)
- [Anytime-valid Optimal Policy Identification](https://mlsanity.com/paper/2606.17515/) (2026)
- [Decentralized Contextual Bandits with Network Adaptivity](https://mlsanity.com/paper/2508.13411/) (2025)
- [Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification](https://mlsanity.com/paper/2605.25592/) (2026)

## Abstract (arXiv)

In the stochastic contextual bandit setting, regret-minimizing algorithms have been extensively researched, but their instance-minimizing best-arm identification counterparts remain seldom studied. In this work, we focus on the stochastic bandit problem in the (ε,δ)-textitPAC setting: given a policy class Pi the goal of the learner is to return a policy π∈ Pi whose expected reward is within ε of the optimal policy with probability greater than 1-δ. We characterize the first textitinstance-dependent PAC sample complexity of contextual bandits through a quantity ρPi, and provide matching upper and lower bounds in terms of ρPi for the agnostic and linear contextual best-arm identification settings. We show that no algorithm can be simultaneously minimax-optimal for regret minimization and instance-dependent PAC for best-arm identification. Our main result is a new instance-optimal and computationally efficient algorithm that relies on a polynomial number of calls to an argmax oracle.