Active Context Selection Improves Simple Regret in Contextual Bandits

• URL: http://arxiv.org/abs/2605.20040v1
• Date: Tue, 19 May 2026 16:01:58 GMT
• Title: Active Context Selection Improves Simple Regret in Contextual Bandits
• Abstract summary: We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations)<n>Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector $p$.<n>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.
• Score: 25.361115767570244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\sqrt{n/T \, \lVert p \rVert_{1/2}}$, whereas active sampling with allocation $q_j \propto p_j^{2/3}$ achieves the tight rate $\sqrt{n/T} \, \lVert p \rVert_{2/3}$. The resulting improvement can be as large as $Θ(k^{1/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.

Related papers

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
  In this paper, we revisit the linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process.<n>We propose a novel variance-adaptive algorithm textttVAEE for large action set, which actively explores actions that maximize the information gain.<n>We establish a nearly matching lower bound for the fixed action set setting indicating that emphharmonic-mean dependent rate is unavoidable.
  arXiv  Detail & Related papers  (2026-07-26T14:24:34Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions [1.0098114696565863]
  SupSplitLog is the first algorithm for logistic bandits that achieves $tildemathcalO(sqrtdT)$ regret without any context diversity assumption.<n>SupSplitLog strictly improves on the existing algorithms in terms of the dependence on dimension $d$ in the regret upper bound.
  arXiv  Detail & Related papers  (2026-04-24T02:21:59Z)
• Active Bipartite Ranking with Smooth Posterior Distributions [1.9838140219494644]
  Bipartite ranking is a statistical learning problem involved in many applications and widely studied in the passive context.<n>We propose a novel algorithm, referred to as smooth-rank and designed for the continuous setting, which aims to minimise the distance between the ROC curve of the estimated ranking rule and the optimal one w.r.t. the $sup$ norm.<n>We provide a problem dependent upper bound on the expected sampling time of smooth-rank and establish a problem dependent lower bound on the expected sampling time of any PAC$(,)$ algorithm.
  arXiv  Detail & Related papers  (2026-02-27T18:32:08Z)
• Optimal Best Arm Identification with Post-Action Context [15.613350380708798]
  We introduce the problem of best arm identification with post-action context.<n>We analyze two different types of the post-action context.<n>For the non-separator setting, we do so by demonstrating that the Track-and-Stop algorithm can be extended to this setting.<n>For the separator setting, we propose a novel sampling rule called $textitG-tracking$, which uses the geometry of the context space to directly track the contexts rather than the actions.
  arXiv  Detail & Related papers  (2025-02-05T10:47:05Z)
• Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration [40.73142019282658]
  We study whether injecting randomization can help a society of agents it concurently explore an environment.<n>We demonstrate worst-case regret bounds in both finite- and infinite-horizon environments.<n>We reduce the space complexity by a factor of $K$ while incurring only a $sqrtK$ increase in the worst-case regret bound.
  arXiv  Detail & Related papers  (2025-01-23T05:37:33Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  We consider a contextual bandit problem with $S$ contexts and $K$ actions. We give an algorithm that outputs an $epsilon$-optimal policy after using at most $widetilde O(r (S +K )/epsilon2)$ samples. In the regret setting, we give an algorithm whose cumulative regret up to time $T$ is bounded by $widetilde O(sqrtr3(S+K)T)$.
  arXiv  Detail & Related papers  (2023-06-22T17:20:30Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models [25.336599480692122]
  We consider the regret minimization task in a dueling bandits problem with context information. We propose a computationally efficient algorithm, $texttCoLSTIM$, which makes its choice based on imitating the feedback process. Our experiments demonstrate its superiority over state-of-art algorithms for special cases of CoLST models.
  arXiv  Detail & Related papers  (2022-02-09T17:44:19Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states.
  arXiv  Detail & Related papers  (2021-06-18T07:54:23Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.