Constrained Contextual Bandits with Adversarial Contexts

arXiv:2605.06190 · cs.LG · Submitted 2026-05-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Constrained Contextual Bandits with Adversarial Contexts".

Tom: The gist The authors propose a modular, unified algorithmic framework for constrained contextual bandits under general realizability assumptions, with adversarially chosen contexts.

Jane: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper called "Constrained Contextual Bandits with Adversarial Contexts," and it's by Dhruv Sarkar from IIT Kharagpur, working with Abhishek Sinha from TIFR. The title itself tells you the core challenge right away: contextual bandits where there's a budget constraint, and something tricky—adversarial contexts.

Jane: Exactly. What that means in plain language is that we are trying to make decisions over time based on what we see, like a context or situation, but we have a limit on how much money or resource we can spend across all those decisions. And the adversarial part means the worst possible situations are being designed specifically to hurt our performance.

Lu: It sets up a really interesting scenario for AI because it moves beyond just having random rewards and costs; it introduces these specific constraints that the algorithm has to manage throughout its entire run.

Meng: So, instead of just optimizing for reward, we have to think about how much we're spending versus what we need to achieve over the long haul.

Lalam: This paper is interesting because it tackles this whole budget management thing directly within a contextual setting where the inputs are chosen by an adversary.

The paper's summary: Tom: The authors summarize their approach by saying they build on the existing SquareCB framework from Foster and Rakhlin, and then they modify that to handle the constraints. They take the original problem, which is constrained, and turn it into an unconstrained one by defining some surrogate reward functions.

Jane: That means instead of solving a difficult constrained problem right away, they reformulate it so they can use established methods for standard contextual bandits, which is much easier to handle mathematically.

Lu: And the key idea here is that they use online regression oracles to estimate the losses from observed contexts and then feed those estimates into a specific policy called Inverse Gap Weighting, which helps guide the exploration part of their learning process.

Meng: So, they're using these online estimates to figure out what actions are good, while also keeping track of how much budget we've used so far.

Lalam: And the core technical contribution is this general regret decomposition inequality, which they claim controls both the regret from not finding the best action and how much we violate that cumulative cost over time.

The paper's improvements: Tom: What's really compelling here is how they present this regret decomposition inequality, Proposition one <ref:2605.06190#pg2>. It’s supposed to be a single mathematical statement that manages both the regret—how far off we are from the best possible outcome—and the cumulative cost violation simultaneously.

Jane: That’s a big deal because usually, you have separate analyses for regret and constraint violation, but this one inequality cleans up those two things into one unified control mechanism.

Lu: This structure allows them to cleanly separate three main roles: exploration, which is handled by the Inverse Gap Weighting part, estimation through the regression oracles, and then constraint management through a Lyapunov-based construction.

Meng: So they are claiming that this single inequality lets us see exactly how exploration works alongside constraint management in a constrained setting.

Lalam: They also show that this framework achieves O˜(√T)-type bounds across multiple feasibility regimes, which is better than the prior results because those older results often relied on assuming stochastic contexts.

Conclusion: Tom: So to wrap up, the paper "Constrained Contextual Bandits with Adversarial Contexts" provides a modular framework that uses online regression oracles and a Lyapunov-based construction to tackle budget constraints in adversarial settings. They manage regret and constraint violation using one decomposition inequality.

Jane: It’s about making the problem simpler by turning it into an unconstrained one through surrogate rewards, which lets them apply existing techniques while keeping the exploration, estimation, and constraint management all working together smoothly.

Lu: The implication is that we can now handle more challenging adversarial environments without needing those strong distributional assumptions that were required in earlier work.

Meng: From a practical standpoint, the oracle-efficient nature of their algorithm means it doesn't need to maintain complex confidence intervals for every possible function class, which simplifies things for real-world deployment.

Lalam: And if you look at the Long-term Feasibility setting, they get regret bounds of O(√KT UT) and a CCV bound of O˜(√KT UT + BT log T), which is much better than what we saw before.

Indian Institute of Technology Kharagpur · Tata Institute of Fundamental Research

cs.LG

Submitted: 2026-05-07

Updated: 2026-10-13

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 78/100

The gist: The gist The authors propose a modular, unified algorithmic framework for constrained contextual bandits under general realizability assumptions, with adversarially chosen contexts.

Key concepts

Realizability Assumption: This assumption ensures that for any given context and action, the expected reward and cost functions are well-defined. It means there exist underlying functions ($f^ ext{*} $ and $g^ ext{*} $) that govern these expectations, allowing the algorithm to aim towards an optimal stationary policy.
Surrogate Reward Estimates: Instead of directly optimizing the complex constrained problem, the framework creates simplified 'surrogate' reward estimates. These estimates are constructed by linearly combining the actual reward and cost functions, with weights that increase based on how much budget has been spent so far. This allows the algorithm to manage constraints more effectively.
General Regret Decomposition Inequality: This is a central technical result that provides a single mathematical tool to analyze performance. It cleanly separates the challenges of exploration (how much we explore), estimation (how well we learn), and constraint management (how much we violate the budget). This separation is key to proving strong bounds in complex, adversarial environments.

Terminology

Adversarial Context — 3× in this paper · explained in 1 episode
Contextual Bandits — 2× in this paper · explained in 3 episodes
Contextual Bandit Problem — 1× in this paper · explained in 2 episodes
Regret — 1× in this paper · explained in 3 episodes
Reward Function — 1× in this paper · explained in 3 episodes

Summary

The gist The authors propose a modular, unified algorithmic framework for constrained contextual bandits under general realizability assumptions, with adversarially chosen contexts.

Problem Formulation and Assumptions

The study considers a budget-constrained contextual bandit problem under realizability assumptions where each action yields a random reward and incurs a random cost<ref:2605.06190#pg3>. The learner observes a context xt, selects an action at in [K], and receives a random reward ft(xt, at) and incurs a random cost gt(xt, at)<ref:2605.06190#pg4>. Assumption 1 (Realizability) states that there exist functions f⋆ ∈ F and g⋆ ∈ G such that E[ft(xt, at)xt = x, at = a] = f⋆(x, a) and E[gt(xt, at)xt = x, at = a] = g⋆(x, a),∀x ∈ X, a ∈ [K], t ⩾ 1<ref:2605.06190#pg4>. The learner aims to perform as well as an optimal stationary policy π⋆ that maximizes the cumulative rewards while satisfying the cost constraints<ref:2605.06190#pg4>. Benchmarks include (Round-wise feasible) and (Long-term feasible) settings<ref:2605.06190#pg4>.

Algorithm Framework

The proposed algorithm builds upon the seminal SquareCB framework of Foster and Rakhlin [2020], reducing the constrained problem to an unconstrained contextual bandit with adaptively defined surrogate reward functions<ref:2605.06190#pg5>. Algorithm 1, SquareCB, employs an online regression oracle Osq to estimate each arm’s losses from observed contexts and then feeds these estimates into the classic Inverse Gap Weighting (IGW) policy<ref:2605.06190#pg6>. The core of the constrained solution is Algorithm 2, which constructs surrogate reward estimates Lˆt(xt, a) by linearly combining reward and cost functions weighted appropriately by a non-decreasing function of the cumulative cost accrued so far<ref:2605.06190#pg8>.

Key Technical Contributions

The central technical contribution is a general regret decomposition inequality for the constrained setting (Proposition 1), which simultaneously controls regret and cumulative constraint violation (CCV)<ref:2605.06190#pg9>. This single inequality separates the roles of exploration, estimation, and constraint management<ref:2605.06190#pg9>. The framework yields improved guarantees for more general adversarial contexts, achieving O˜(√T)-type bounds across multiple feasibility regimes<ref:2605.06190#pg10>. Specifically, Theorem 1(a) shows that for Round-wise Feasibility in Expectation, the algorithm achieves ERegretT = O(√KT3/4U1/4T), ECCVT = O(√KT3/4U1/4T)<ref:2605.06190#pg10>.

Performance Guarantees

The paper establishes several improved bounds over prior results that relied on stochastic contexts<ref:2605.06190#pg10>. Under Slater’s condition, the average CCV can be improved to O(√KT UTϵ), with Corollary 1.1 showing that for any fixed percentage of rounds, the CCV is at most O(√KT UTϵ)<ref:2605.06190#pg10>. For Long-term Feasibility with Non-negative Cost (CBwK), Theorem 1(e) yields ERegretT = O(√KT UT) and ECCVT = O˜(√KT UT + BT log T)<ref:2605.06190#pg18>. Furthermore, the analysis extends to hard-stopping settings, where Theorem 3 shows that for CBwK with non-negative costs, OPT(BT) − O(log T)ALG(B′T) = O˜(√KT UT)<ref:2605.06190#pg22>.

Limitations and Extensions

The results rely on the realizability assumption, which may be violated in practice<ref:2605.06190#pg19>. The framework focuses on long-term (cumulative) constraint satisfaction rather than per-round feasibility<ref:2605.06190#pg19>. The analysis also shows that for CBwK, the online policy incurs a cumulative cost of O(BT log T)+O(√T), which is unavoidable when comparing against the offline benchmark<ref:2605.06190#pg23>.

Conclusion

The work proposes a modular, unified algorithmic framework for constrained contextual bandits under general realizability assumptions, with adversarially chosen contexts<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>. This framework subsumes several prior settings as special cases while extending them to more challenging adversarial environments<ref:2605.06190#pg4>. The central technical contribution is a general regret decomposition inequality that cleanly separates the roles of exploration (via Inverse Gap Weighting), constraint management (via Lyapunov-based surrogates), and statistical estimation (via online regression oracles)<ref:2605.06190#pg19>.

Improvements for AI systems

Bold surrogate reward construction enables simultaneous control over regret and constraint violation by defining surrogate rewards as Lˆt(xt, a) = ˆft(xt, a) − Φ'(Q(t − 1))gˆt(xt, a) where the non-decreasing convex function Φ is used to handle cumulative cost. This allows the algorithm to simultaneously control regret and the violation of the budget constraint in the continuing setting.
The use of a unifying Regret-CCV decomposition via Proposition 1 provides a single inequality that cleanly separates exploration, estimation, and constraint management, allowing for a streamlined analysis across different feasibility regimes. This leads to bounds like ERegretT = O(√KT3/4U1/4T) for round-wise feasible in expectation benchmarks.
The framework handles general adversarial contexts without relying on distributional assumptions, yielding improved guarantees: In Theorem 1, we obtain O˜(√T)-type bounds across multiple feasibility regimes, improving over prior O(T3/4)-type guarantees that additionally rely on stochastic contexts.
The algorithm is oracle-efficient by building on the SquareCB framework, which reduces the problem to an online regression oracle, thereby obviating the need for maintaining confidence intervals common with UCB-type algorithms. This makes it suitable for black-box learning scenarios where function classes F and G are complex neural networks or decision trees.
The system can adapt its exploration strategy based on accumulated cost through the adaptive parameter γt = 1/2zt√KUT∑τ=1 zτ, where zt ≡ max (1, (Φ'(Q(t − 1))) 2), which dynamically balances exploration and constraint satisfaction. This ensures that the policy naturally balances exploration, exploitation, and constraint satisfaction.
The system can be applied to Contextual Bandits with Knapsacks (CBwK) under long-term budget feasibility, achieving a regret bound of ERegretT ⩽ O(√KT UT) and a CCV bound of ECCVT = O˜(√KT UT + BT log T), generalizing beyond prior work's reliance on large budgets.
The framework can be extended to handle linear constraints (CBwLC) in the i.i.d. stochastic setting by defining modified cost functions g¯t(x, a) ∶= gt(x, a) − b, which allows the application of results from the single-resource case while maintaining performance bounds like ERegretT = O(√KT3/4U1/4T).
The system can provide lower bounds for competitive ratios in hard-stopping settings, showing that for CBwK, the ratio is bounded below by omega(log(T/BT)) when the budget constraint is tight. This informs resource allocation strategies under strict budget limitations.

Abstract

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most U T, our algorithm achieves O(sqrt KTU T) regret and O(sqrt KTU T T) cumulative expected cost, with high probability, improving upon the previous O(T 3/4) type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.