mlsanityData to 14 Oct 2026

The Role of Contextual Information in Best Arm Identification

arXiv 2106.14077 ↗First posted 26 Jun 2021cs.LG econ.EM math.STcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the best-arm identification problem with fixed confidence when contextual (covariate) information is available in stochastic bandits. Although we can use contextual information in each round, we are interested in the marginalized mean reward over the contextual distribution. Our goal is to identify the best arm with a minimal number of samplings under a given value of the error rate. We show the instance-specific sample complexity lower bounds for the problem. Then, we propose a context-aware version of the "Track-and-Stop" strategy, wherein the proportion of the arm draws tracks the set of optimal allocations and prove that the expected number of arm draws matches the lower bound asymptotically. We demonstrate that contextual information can be used to improve the efficiency of the identification of the best marginalized mean reward compared with the results of Garivier & Kaufmann (2016). We experimentally confirm that context information contributes to faster best-arm identification.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 16 of its 47 references that are in the map. First posted on arXiv 26 Jun 2021.

Builds on

16 of 47 references.

References · 16

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  3. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 149
  4. 2014Best-Arm Identification in Linear Banditscited by 100
  5. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
  6. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
  7. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  8. 2020Optimal Best-arm Identification in Linear Banditscited by 71
  9. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 63
  10. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43
  11. 2018Nonparametric Stochastic Contextual Banditscited by 17
  12. 2018Simple Regret Minimization for Contextual Banditscited by 16
4 more
  1. 2016The Econometrics of Randomized Experimentscited by 14
  2. 2018Stratification Trees for Adaptive Randomization in Randomized Controlled Trialscited by 14
  3. 2018Sample complexity of partition identification using multi-armed banditscited by 13
  4. 2015RELEAF: An Algorithm for Learning and Exploiting Relevancecited by 7

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 1; 2024: 4; 2025: 1.

8 papers.

  1. 2025BanditSpec: Adaptive Speculative Decoding via Bandit Algorithmscited by 20
  2. 2024Cost Aware Best Arm Identificationcited by 13
  3. 2024Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choicescited by 12
  4. 2024Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Banditscited by 6
  5. 2022Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gapcited by 4
  6. 2022Best Arm Identification with Contextual Information under a Small Gapcited by 3
  7. 2023Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Boundscited by 3
  8. 2024Adaptive Experimental Design for Policy Learningcited by 2