Eluder-Dimension-Free Regret for Stage-Wise Constrained Contextual Bandits via Offline Regression
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.
