Eluder-Dimension-Free Regret for Stage-Wise Constrained Contextual Bandits via Offline Regression

Haichen Hu; David Simchi-Levi; Navid Azizan

stat.MLMay 11, 2025

Eluder-Dimension-Free Regret for Stage-Wise Constrained Contextual Bandits via Offline Regression

Authors: Haichen Hu, David Simchi-Levi, Navid Azizan

Organizations: Massachusetts Institute of Technology

Abstract

Contextual bandits with stage-wise constraints model decisions that must control risk while learning from their outcomes. We study this problem when only the selected action's reward and cost are observed, with a general reward class and a convex class of nonlinear cost functions. We propose CS-UCCB, which combines offline regression, cost confidence sets, and upper counterfactual confidence bounds. Each regression fit defines a valid cost confidence set, while a geometry derived from covering entropy controls cumulative cost uncertainty along the sampled decisions. Under polylogarithmic covering entropy for both classes and polylogarithmic offline estimation error, the finite-action algorithm guarantees, with high probability, feasibility at every round and $\widetilde{\mathcal O}(\sqrt T)$ regret without an eluder-dimension term. We also extend the analysis to infinite actions under an explicit reward-design condition and compare our bound with existing eluder-dimension bounds.

Figures & tables

Method	Function classes	Regression	Constraint	Feedback for constraints	ED	Regret
Amani et al. (2019)	Linear	Ridge LS	Stage-wise	Loss; shared parameter	–	$\widetilde{O}(T^{2/3})$
Pacchiano et al. (2021)	Linear	Ridge LS	Stage-wise	Selected-action cost	–	$\widetilde{O}(\sqrt{T})$
Slivkins et al. (2023)	Regression classes	Online oracle	Packing/covering	Selected-action consumption	–	Problem dependent
Deb et al. (2025)	Nonlinear	Online oracle	Cumulative baseline	Loss; known baseline	–	$\widetilde{O}(\sqrt{T})$
Pacchiano et al. (2025)	Finite nonlinear	Offline LS	Stage-wise	Selected-action cost	Yes	$\widetilde{O}(\sqrt{Td_{E}}+d_{E})$
This work	General reward; convex cost	Offline oracle	Stage-wise	Selected-action cost	No	$\widetilde{O}(\sqrt{T})$

Table 1: Comparison under each work’s assumptions and feedback model. Rates suppress logarithms and fixed safety and complexity parameters, with polylogarithmic regression error where applicable. We show the general rate of Amani et al. (2019) , without an additional known positive optimal-action safety gap. Our rate uses the stated reward covering profile and convex cost entropy assumptions. ED denotes an explicit eluder-dimension term;

d_{E}

abbreviates its combined reward and cost dependence.

{\mathcal{S}}_{t}=\left\{c\in\mathcal{C}:\sum_{i=1}^{t-1}(c(Z_{i})-\widehat{c}^{t}(Z_{i}))^{2}\leq B_{t}^{\mathcal{C}}\right\}.

Algorithm 2 Cost Confidence Set Construction

Panel of Figure 1 — Figure 1: CS-UCCB with selected-action cost feedback. The current offline fit defines a convex confidence set. Its upper costs certify feasible policies, and its widths enter the UCCB objective. The selected action supplies the observations for the next update.

Contextual Bandits

Contextual bandits learn which action to take from features of each situation when only the chosen action’s reward is observed.

See all 152 papers

Constrained Contextual Bandits with Adversarial Contexts
May 7, 2026Dhruv Sarkar, Abhishek SinhaContextual Bandits Adversarial Bandits
Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India
Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits
Feb 10, 2026Hao Qin, Chicheng ZhangExploration-Exploitation Tradeoff Contextual Bandits
The University of Arizona
Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions
Aug 27, 2026Spyros Dragazis, Aldo PacchianoContextual Bandits Multi-Armed Bandits
Boston University · Broad Institute of MIT and Harvard

May 7, 2026J/K move · Enter open · S save

Constrained Contextual Bandits with Adversarial Contexts

Dhruv Sarkar, Abhishek Sinha

Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India

Contextual Bandits Adversarial Bandits

Open paper AskPDF arXiv

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

\mathsf{SquareCB}

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}\log 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.

Abstract

Contextual Bandits

Explore similar work

Constrained Contextual Bandits with Adversarial Contexts

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions