Improved Regret bounds for Stochastic Contextual Bandits with General Constraints

We consider the contextual bandit problem with general constraints, in which the learner sequentially observes contexts and seeks to maximize cumulative reward subject to a broad class of feasibility requirements. We operate under a general realizability assumption, positing that the expected reward and cost functions belong to rich function classes. Prevailing approaches predominantly employ primal–dual methods, which generally yield $\tilde{\mathcal{O}}(\sqrt{T})$ bounds on both regret and cumulative constraint violation. By contrast, we develop a purely primal framework that exploits online regression oracles to estimate the reward and cost functions, and proceeds by sequentially solving approximations of the offline benchmark problem. We establish that the proposed algorithm attains logarithmic instance-dependent regret while simultaneously preserving $\tilde{\mathcal{O}}(\sqrt{T})$ guarantees on constraint violation. These results hinge on a refined analysis of the offline benchmark structure.