A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression

• URL: http://arxiv.org/abs/2602.05019v1
• Date: Wed, 04 Feb 2026 20:19:55 GMT
• Title: A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression
• Authors: Dhruv Sarkar, Abhishek Sinha,
• Abstract summary: 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.
• Score: 7.798233121583888
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study constrained contextual bandits (CCB) with adversarially chosen 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 consider the continuing setting, in which the algorithm operates over the entire horizon even after the budget is exhausted. In this setting, the objective is to simultaneously control regret and cumulative constraint violation. Building on the seminal SquareCB framework of Foster et al. (2018), we propose a simple and modular algorithmic scheme 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 most prior work on CCB, which focuses on stochastic contexts, our reduction yields improved guarantees for the more general adversarial context setting, together with a compact and transparent analysis.

Related papers

• Conformal Bandits: Bringing statistical validity and reward efficiency to the small-gap regime [0.39082875522676397]
  We introduce Conformal Bandits, a novel framework integrating Conformal Prediction into bandit problems.<n>We bridge the regret-minimising potential of a decision-making bandit policy with statistical guarantees in the form of finite-time prediction coverage.<n>Motivated by this, we showcase our framework's practical advantage in terms of regret in small-gap settings.
  arXiv  Detail & Related papers  (2025-12-10T17:34:55Z)
• 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)
• Stochastic Conservative Contextual Linear Bandits [8.684768561839146]
  We study the problem of safe real-time decision making under uncertainty. We formulate a conservative contextual bandit formulation for real-time decision making.
  arXiv  Detail & Related papers  (2022-03-29T14:50:50Z)
• 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)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• 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)
• Corruption-robust exploration in episodic reinforcement learning [76.19192549843727]
  We study multi-stage episodic reinforcement learning under adversarial corruptions in both the rewards and the transition probabilities of the underlying system. Our framework yields efficient algorithms which attain near-optimal regret in the absence of corruptions. Notably, our work provides the first sublinear regret guarantee which any deviation from purely i.i.d. transitions in the bandit-feedback model for episodic reinforcement learning.
  arXiv  Detail & Related papers  (2019-11-20T03:49:13Z)

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.