mlsanityData to 14 Oct 2026

Instance-optimal PAC Algorithms for Contextual Bandits

arXiv 2207.02357 ↗First posted 5 Jul 2022stat.ML cs.LGcited by 16

Not on the map. Why?

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.

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

26 of 49 references.

References · 26

  1. 2018A Reductions Approach to Fair Classificationcited by 587
  2. 2014Convex Optimization: Algorithms and Complexitycited by 575
  3. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  4. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  5. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  6. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  7. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  8. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 117
  9. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  10. 2014Best-Arm Identification in Linear Banditscited by 100
  11. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  12. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
14 more
  1. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  2. 2020Gamification of Pure Exploration for Linear Banditscited by 63
  3. 2018Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraintscited by 53
  4. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  5. 2017Active Learning for Cost-Sensitive Classificationcited by 41
  6. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  7. 2020Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Banditscited by 31
  8. 2020An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Banditscited by 26
  9. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20
  10. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  11. 2015Efficient and Parsimonious Agnostic Active Learningcited by 17
  12. 2018Simple Regret Minimization for Contextual Banditscited by 16
  13. 2020Bayesian Meta-Prior Learning Using Empirical Bayescited by 14
  14. 2018Linearly Convergent Frank-Wolfe with Backtracking Line-Searchcited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 5; 2024: 3; 2025: 2; 2026: 4.

16 papers.

Sort:

By area:

  1. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  2. 2023Concentrated Differential Privacy for Banditscited by 10
  3. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  4. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  5. 2022Adaptive Experimental Design and Counterfactual Inferencecited by 5
  6. 2024Experiment Planning with Function Approximationcited by 5
  7. 2024Understanding What Affects the Generalization Gap in Visual Reinforcement Learning: Theory and Empirical Evidencecited by 5
  8. 2024Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learningcited by 5
  9. 2023A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Modelscited by 3
  10. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  11. 2026A Statistical Test for the Benefits of Personalizing Interventionscited by 2
  12. 2025Experimental Design for Semiparametric Banditscited by 1
4 more
  1. 2026Active Learning for Stochastic Contextual Linear Banditscited by 1
  2. 2026Anytime-valid Optimal Policy Identificationcited by 1
  3. 2025Decentralized Contextual Bandits with Network Adaptivitycited by 0
  4. 2026Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identificationcited by 0