# Active Context Selection Improves Simple Regret in Contextual Bandits

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

## 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 (most cited first, 19 of 19)

- [Variational Bayesian Optimal Experimental Design](https://mlsanity.com/paper/1903.05480/) (2019)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Budgeted and Non-budgeted Causal Bandits](https://mlsanity.com/paper/2012.07058/) (2020)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Simple Regret Minimization for Contextual Bandits](https://mlsanity.com/paper/1810.07371/) (2018)
- [A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounders](https://mlsanity.com/paper/2107.02772/) (2021)
- [Best Arm Identification with Fairness Constraints on Subpopulations](https://mlsanity.com/paper/2304.04091/) (2023)
- [Maximin Action Identification: A New Bandit Framework for Games](https://mlsanity.com/paper/1602.04676/) (2016)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization](https://mlsanity.com/paper/2307.02108/) (2023)
- [Confounded Budgeted Causal Bandits](https://mlsanity.com/paper/2401.07578/) (2024)
- [Best Arm Identification with Contextual Information under a Small Gap](https://mlsanity.com/paper/2209.07330/) (2022)
- [Fair Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2408.17313/) (2024)
- [Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutions](https://mlsanity.com/paper/2208.05844/) (2022)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)
- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits](https://mlsanity.com/paper/2601.21167/) (2026)

## 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.