Constrained Contextual Bandits with Adversarial Contexts

• URL: http://arxiv.org/abs/2605.06190v1
• Date: Thu, 07 May 2026 13:04:49 GMT
• Title: Constrained Contextual Bandits with Adversarial Contexts
• Abstract summary: We study budget-constrained contextual bandits with adversarial contexts.<n>In this setting, the objective is to simultaneously control regret and the violation of the budget constraint.
• Score: 7.798233121583888
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study budget-constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. We adopt the standard realizability assumption: conditioned on the observed context, rewards and costs are drawn independently from fixed distributions whose expectations belong to known function classes. We focus on the continuing setting, in which the algorithm operates over the entire horizon even after the budget for cumulative cost is exhausted. In this setting, the objective is to simultaneously control regret and the violation of the budget constraint. Building on the seminal $\mathsf{SquareCB}$ framework of Foster et al. [2018], we propose a simple and modular framework that leverages online regression oracles to reduce the constrained problem to a standard unconstrained contextual bandit problem with adaptively defined surrogate reward functions. In contrast to prior works, which focus on stochastic contexts, our reduction yields improved guarantees for more general adversarial contexts, together with an efficient algorithm with a compact and transparent analysis.

Related papers

• α-Fair Insurance Pricing: A Fairness Continuum [9.531754248649962]
  Fairness in insurance pricing remains a long-standing and deeply debated puzzle.<n>We propose an $$-textbfFair textbfIndividual textbfSolvent textbfPremium ($$-FISP) framework for insurance pricing.
  arXiv  Detail & Related papers  (2026-06-12T19:05:12Z)
• A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression [7.798233121583888]
  We study constrained contextual bandits with adversarially chosen contexts, where each action yields a random reward and incurs a random cost.<n>We adopt the standard realizability assumption: conditioned on the observed context, rewards and costs are drawn independently from fixed distributions whose expectations belong to known function classes.
  arXiv  Detail & Related papers  (2026-02-04T20:19:55Z)
• Conformal Thinking: Risk Control for Reasoning on a Compute Budget [60.65072883773352]
  Reasoning Large Language Models (LLMs) enable test-time scaling, with dataset-level accuracy improving as the token budget increases.<n>We re-frame the budget setting problem as risk control, limiting the error rate while minimizing compute.<n>Our framework introduces an upper threshold that stops reasoning when the model is confident and a novel lower threshold that preemptively stops unsolvable instances.
  arXiv  Detail & Related papers  (2026-02-03T18:17:22Z)
• AdaGReS:Adaptive Greedy Context Selection via Redundancy-Aware Scoring for Token-Budgeted RAG [4.69377227249912]
  We present AdaGReS, a redundancy-aware context selection framework for token-budgeted RAG.<n>AdaGReS performs greedy selection under a token-budget constraint using marginal gains derived from the objective.<n> Experiments on open-domain question answering (Natural Questions) and a high-redundancy biomedical (drug) corpus demonstrate consistent improvements in redundancy control and context quality.
  arXiv  Detail & Related papers  (2025-12-31T18:48:07Z)
• Multi-Armed Bandits with Minimum Aggregated Revenue Constraints [27.081997104464012]
  We design and analyze algorithms that either optimistically prioritize performance or pessimistically enforce constraint satisfaction.<n>We establish a lower bound demonstrating that the dependence on the time horizon in our results is optimal in general.
  arXiv  Detail & Related papers  (2025-10-14T13:47:34Z)
• Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization [29.579719765255927]
  We propose a new family of efficient bandit algorithms for the contextual bandit setting. Our algorithms work with any function class, are robust to model misspecification, and can be used in continuous arm settings.
  arXiv  Detail & Related papers  (2023-07-05T08:34:54Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  We present the first algorithm with provably vanishing regret for Contextual Bandits with Concave Rewards (CBCR) We derive a novel reduction from the CBCR regret to the regret of a scalar-reward problem. Motivated by fairness in recommendation, we describe a special case of CBCR with rankings and fairness-aware objectives.
  arXiv  Detail & Related papers  (2022-10-18T16:11:55Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  We casting online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$m resource constraints. Our framework allows the decision maker to handle its evidence flexibility and costoretic functions.
  arXiv  Detail & Related papers  (2022-02-28T12:10:48Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  Lipschitz bandits is a prominent version of multi-armed bandits that studies large, structured action spaces.<n>A central theme here is the adaptive discretization of the action space, which gradually zooms in'' on the more promising regions.<n>We provide the first algorithm for adaptive discretization in the adversarial version, and derive instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-06-22T16:06:25Z)

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.