mlsanityData to 14 Oct 2026

Active Context Selection Improves Simple Regret in Contextual Bandits

arXiv 2605.20040 ↗First posted 19 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector p. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known p, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order √n/T , lVert p rVert1/2, whereas active sampling with allocation qj propto pj2/3 achieves the tight rate √n/T , lVert p rVert2/3. The resulting improvement can be as large as Theta(k1/4), where k is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When p is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-p active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 19 of its 32 references that are in the map. First posted on arXiv 19 May 2026.

Builds on

19 of 32 references.

References · 19

  1. 2019Variational Bayesian Optimal Experimental Designcited by 116
  2. 2016Causal Bandits: Learning Good Interventions via Causal Inferencecited by 101
  3. 2020Budgeted and Non-budgeted Causal Banditscited by 38
  4. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  5. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  6. 2018Simple Regret Minimization for Contextual Banditscited by 16
  7. 2021A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounderscited by 15
  8. 2023Best Arm Identification with Fairness Constraints on Subpopulationscited by 8
  9. 2016Maximin Action Identification: A New Bandit Framework for Gamescited by 7
  10. 2021Max-Min Grouped Banditscited by 7
  11. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  12. 2024Confounded Budgeted Causal Banditscited by 4
7 more
  1. 2022Best Arm Identification with Contextual Information under a Small Gapcited by 3
  2. 2024Fair Best Arm Identification with Fixed Confidencecited by 3
  3. 2022Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutionscited by 2
  4. 2024Adaptive Experimental Design for Policy Learningcited by 2
  5. 2025Best Group Identification in Multi-Objective Banditscited by 2
  6. 2025Graph Learning Is Suboptimal in Causal Banditscited by 2
  7. 2026Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Banditscited by 2

Built on by

Not cited yet.