Improved Regret and Violation Guarantees for Constrained Contextual Bandits with General Realizability

This paper studies stochastic constrained contextual bandits under a general realizability condition. In each round, a learner observes a context, selects an action, and receives the reward and cost of the selected action. The objective is to maximize cumulative reward while ensuring that the cumulative cost remains below a prescribed threshold. In prior works, regret and violation analyses are tightly coupled, leading to regret bounds that inherit difficulty of violation control. We propose a primal-dual learning algorithm that combines queue-normalized inverse-gap exploration with a discounted regulator. The key to this design is a regret analysis that does not require a prior bound on the dual process. Under general feasibility, for every $\theta \in [1/2,1]$, the algorithm achieves $\tilde{O}(T^{\theta }{U}^{1-\theta })$ regret and $\tilde{O}(T^{1-\theta /2}{U}^{\theta /2})$ constraint violation, where $U$ denotes the cumulative prediction error bound of the online regression oracles. When Slater's condition also holds with an unknown feasibility margin $ϵ>0$, we derive a novel Lyapunov analysis that improves the violation bound to $\tilde{O}(\min \{\sqrt{TU}/ϵ,T^{1-\theta /2}{U}^{\theta /2}\})$ while preserving regret guarantee. These results improve upon state-of-the-art guarantees under the same regression oracle assumption in both feasibility regimes. Experiments on learning-to-rank and constrained bidding tasks further demonstrate the effectiveness of our method.