acceptodds
Under review as a conference paper at ICLR 2027

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

12 views

Abstract

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 , the algorithm achieves regret and constraint violation, where denotes the cumulative prediction error bound of the online regression oracles. When Slater's condition also holds with an unknown feasibility margin , we derive a novel Lyapunov analysis that improves the violation bound to 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.

Primary area:
optimization
Keywords:
Contextual bandits, general constraints, online learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_JNkTOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies stochastic constrained contextual bandits under a general realizability assumption and a regression-oracle interface. The learner observes a context, chooses an action, and receives bandit feedback for both reward and cost. The goal is to compete with the best stationary feasible policy while keeping cumulative constraint violation sublinear. The paper proposes QUID, a primal-dual algorithm that combines inverse-gap exploration with two modifications: queue-dependent normalization in the primal action distribution and a discounted virtual-queue update on the dual side. The main analytical idea is to derive a regret-plus-drift inequality in which the prediction-error term is no longer multiplied by the current dual variable. This allows the regret analysis to proceed without first proving a bound on the queue. Under general feasibility and a cumulative squared prediction-error bound (U) from the regression oracles, the paper obtains a family of tradeoffs parameterized by (\theta\in[1/2,1]): [ \widetilde O(T^\theta U^{1-\theta}) ] regret and [ \widetilde O(T^{1-\theta/2}U^{\theta/2}) ] constraint violation. In particular, (\theta=1/2) gives the unconstrained-style regret rate while retaining sublinear violation, while (\theta=2/3) balances the two quantities. Under Slater's condition with unknown margin (\epsilon>0), the violation bound is further improved to [ \widetilde O!\left(\min\left{\frac{\sqrt{TU}}{\epsilon}, T^{1-\theta/2}U^{\theta/2}\right}\right) ] without changing the regret guarantee. The paper also reports experiments on a learning-to-rank task and a constrained bidding problem. Overall, the theoretical contribution is interesting and appears technically nontrivial. My main reservations concern the empirical validation and several points where the stated rates and experimental assumptions should be made more explicit.

Critical strengths
  1. The regret analysis genuinely improves the primal-dual decomposition The most interesting technical step is the queue-normalized inverse-gap rule. With the normalization (\beta_t=(1+q_t^2)^{-1}), the squared prediction error in the one-step regret bound can be controlled without an additional factor growing with the queue. The cost is an exploration term proportional to (1+q_t^2), which is then absorbed through the negative quadratic component introduced by the discounted queue update. This produces a regret-plus-drift inequality in which the only remaining explicit queue-dependent term is (q_t g(\pi)), which is nonpositive for a feasible comparison policy. As a result, the regret bound can be obtained without first controlling the queue. This is a clean improvement over the analysis pattern the paper attributes to LOE2D.

  2. The Slater-margin dependence is substantially improved under the same cumulative-error oracle model The refined queue analysis under Slater's condition is another strong point. Rather than requiring the regression error to be small in every round, the proof separates low-risk and high-risk rounds according to the predictable conditional squared error. Negative drift controls the former, while the total number of high-risk rounds is charged to the cumulative regression-error budget. The resulting (1/\epsilon) dependence in the violation bound is materially better than the (1/\epsilon^2) dependence reported for LOE2D, while QUID does not require the margin as an algorithm input. This is a meaningful theoretical improvement if the comparison assumptions in Table 1 are taken at face value.

Critical weaknesses
  1. The experimental comparison is not apples-to-apples with the theoretical assumptions The weakest part of the paper is the empirical section. All methods are implemented using XGBoost as the regression oracle. The paper then explains the poor empirical performance of OPTIMISTIC3 by noting that XGBoost does not provide the uniform confidence bounds required by that method. This makes the comparison difficult to interpret: OPTIMISTIC3 is being evaluated with an oracle that explicitly does not satisfy one of its defining assumptions. Its empirical underperformance therefore provides little evidence about the relative quality of the algorithms. There is a related issue for QUID itself. The theory assumes a high-probability cumulative squared prediction-error guarantee for the online regression oracle. The paper does not explain whether the particular online XGBoost implementation used in the experiments has such a guarantee. If it does not, the experiments are heuristic tests of the algorithmic idea rather than validation of the theoretical regime. That is acceptable, but it should be stated consistently for all methods. For a top-tier paper making a comparison between weak-oracle and strong-oracle methods, I would prefer either implementations that respect each method's required oracle interface or a separate empirical comparison that is explicitly described as heuristic.

  2. The experimental setup is too underspecified to support the claims about the Slater regime The paper states that both experimental environments have Slater margin (\epsilon=10^{-3}), but the construction is not sufficiently documented to verify this claim. The learning-to-rank experiment is especially unclear. The paper says that costs are sampled from ([-1,1]), but does not specify the action- and context-dependent mean cost function or how it is shifted so that the best strict-feasibility margin is exactly (10^{-3}). If "sampled from ([-1,1])" means a centered uniform distribution independent of the action, then the stated Slater margin would not follow. Presumably a more structured construction is intended, but it is not described. The experiments also add Gaussian noise to reward and cost observations, whereas the formal model assumes bounded reward and cost observations. If clipping or another bounded-noise construction is used in code, that should be stated. Otherwise the experimental environment does not literally satisfy the assumptions of the theorem. More generally, the paper gives no hyperparameter-selection protocol for QUID or the baselines, and no sensitivity analysis with respect to (\theta), despite (\theta) being the main regret-violation tradeoff parameter.

  3. The empirical evidence does not isolate the two proposed algorithmic mechanisms QUID's claimed algorithmic novelty has two components: quadratic queue normalization and discounted queue regularization. The experimental section only compares the full method against prior algorithms. There is no ablation that removes either normalization or discounting, and no experiment showing how each mechanism changes queue growth, prediction-error sensitivity, regret, or violation. This is particularly relevant because the theory assigns distinct roles to the two components. An ablation would substantially strengthen the claim that the empirical gains are attributable to the proposed design rather than to tuning or implementation details. The experiments also consider only the Slater setting with a fixed small margin and only (\theta=1/2). The paper's general-feasibility tradeoff is one of its main theoretical contributions, but it is not tested empirically.

Questions for authors
  1. Can the authors make the full dependence of Theorem 4.1 on (K), (F), and (G) explicit? The proof contains factors involving (K+1), while the theorem and Table 1 display only (T,U,\epsilon) and state that (\widetilde O) suppresses logarithmic factors in (T). Is (K) treated as a fixed constant throughout? How does the resulting dependence compare with the standard (\sqrt{KTU})-type dependence of regression-oracle contextual bandit reductions?

  2. How exactly is the learning-to-rank cost process constructed, and how is the claimed Slater margin (\epsilon=10^{-3}) verified? Please specify the conditional mean cost (g(x,a)), the constraint threshold, and the strictly feasible policy attaining the margin. The current statement that costs are sampled from ([-1,1]) is not enough to reconstruct the environment.

  3. How is OPTIMISTIC3 implemented when the common XGBoost oracle does not provide its required anytime confidence bounds or the required knowledge of the context distribution? I do not think its empirical performance is a meaningful baseline unless these requirements are implemented faithfully. If the experiment intentionally uses a misspecified version, it should be labeled as such and not used as evidence against the method.

  4. Can the authors provide ablations for queue normalization and queue discounting, and a tradeoff curve over (\theta)? These would directly test the two claimed design contributions and the main theoretical tradeoff.

2 comments

We thank reviewer for the positive assessment and recognizing the contribution of our work. We respond to your questions as follows.

Dependence on KK, FF and GG. Yes, Theorem 4.1 treats them as constants. Tracking them in (37), (54) and (79) gives

RegT=O(K TθU1−θ+G2 TθU−θ+K(F2+G2)),\mathrm{Reg}_T=O\big(K\ T^{\theta}U^{1-\theta}+G^2\ T^{\theta}U^{-\theta}+K(F^2+G^2)\big),

ViolT=O~(1+F T1−θ/2Uθ/2+KTU)(general),\mathrm{Viol}_T=\tilde O\big(\sqrt{1+F}\ T^{1-\theta/2}U^{\theta/2}+\sqrt{KTU}\big)\quad\text{(general)},

ViolT=O~((1+F)TU/ϵ+KG TU/ϵ)(Slater).\mathrm{Viol}_T=\tilde O\big((1+F)\sqrt{TU}/\epsilon+\sqrt{KG\ TU/\epsilon}\big)\quad\text{(Slater)}.

Thus KK enters the regret linearly but only lower-order terms of the violation. Rescaling γ→γ/K+1\gamma\to\gamma/\sqrt{K+1} and V→K+1 VV\to\sqrt{K+1}\ V keeps ρ\rho unchanged and improves the guarantee to O(K TθU1−θ)O(\sqrt{K}\ T^{\theta}U^{1-\theta}) and O~(K T1−θ/2Uθ/2)\tilde O(\sqrt{K}\ T^{1-\theta/2}U^{\theta/2}) for regret and violation respectively, which is the optimal dependence on KK.

Experiments. We reran all experiments with T=50,000T=50{,}000 and report the average reward and cost per round over the last 1,000 rounds (for clarity, the rewards and costs reported in the tables below are multiplied by 10310^{3}).

(a) Oracle assumptions and Optimistic$^3$. In ranking and bidding, its confidence bounds and context distribution are unavailable, so it uses XGBoost point prediction. Since Optimistic$^3$ requires confidence bounds, and the context distribution must be known, it is difficult to find a real-world dataset satisfying these requirements. We therefore add a synthetic environment (Toy: four contexts and actions, affine rewards and signed costs with bounded noise), where the environment satisfies the assumptions of Optimistic$^3$.

(b) Construction and Slater margin. We clip observed rewards and costs to [0,F][0,F] and [−G,G][-G,G]. The Slater margin is set by rescaling negative costs so that the lowest achievable expected cost is exactly −ϵ-\epsilon, and ϵ=0\epsilon=0 gives a feasible instance without Slater's condition.

(c) Hyperparameters. In each environment, we first run the oracle for a full horizon with random actions and random seeds, select the XGBoost configuration with the best prediction accuracy, and set U0U_0 to the largest cumulative prediction error observed. Table I shows that QUID is robust to overestimating UU, whereas underestimating UU leads to insufficient exploration and degraded reward. The asymmetry is expected: Assumption 2.2 only requires UU to upper bound the cumulative prediction error. A conservative estimate therefore preserves the guarantees up to constant factors, while an underestimate may violate the assumption.

Table I: Sensitivity of QUID to the oracle error bound UU

U/U0U/U_0Ranking RewardRanking CostBidding RewardBidding CostToy RewardToy Cost
0.1×0.1\times221.60±4.333.96±6.0411.22±0.620.98±0.63410.81±0.870.27±0.11
1×1\times254.32±1.561.44±0.1712.82±0.571.32±0.67411.67±0.850.79±0.11
10×10\times256.44±1.573.67±0.1312.60±0.801.44±0.50414.37±0.912.43±0.12

(d) Ablation and θ\theta. We remove the queue normalization(βt=1\beta_t=1) or the discount (ρ=0\rho=0), and set θ\theta to different values to validate the tradeoff of regret and violation. Removing normalization substantially reduces reward, while removing discount yields a smaller reduction.

Table II: Ablation of the two design components and the tradeoff parameter θ\theta

VariantRanking RewardRanking CostBidding RewardBidding CostToy RewardToy Cost
\textit{(a) Design ablation, θ=1/2\theta=1/2}
QUID (full)254.32±1.561.44±0.1712.82±0.571.32±0.67411.67±0.850.79±0.11
βt=1\beta_t=1 (no normalization)227.93±1.661.51±0.3111.40±0.741.27±0.90396.88±0.870.78±0.05
ρ=0\rho=0 (no discount)253.97±1.441.32±0.2212.14±0.761.33±0.90403.76±0.270.50±0.12
\textit{(b) Tradeoff parameter θ\theta}
θ=1/2\theta=1/2254.32±1.561.44±0.1712.82±0.571.32±0.67411.67±0.850.79±0.11
θ=2/3\theta=2/3253.82±1.310.89±0.2710.72±1.061.07±0.89410.77±0.870.25±0.10
θ=1\theta=1253.48±1.640.42±0.1911.17±1.130.99±0.52409.94±0.790.06±0.11

(e) Slater margins. Due to space limits, Table III reports Toy. Across all margins, including ϵ=0\epsilon=0. The results generally align with the theoretical trend regarding changes in the Slater margin.

Table III: Toy environment under different Slater margins

MethodMetricϵ=0\epsilon=010−310^{-3}10−210^{-2}10−110^{-1}
QUIDReward409.54±0.77411.67±0.85432.54±0.90579.22±0.39
Cost0.88±0.140.79±0.110.74±0.120.44±0.07
LOE2DReward410.92±0.62412.87±0.94433.69±0.98579.69±0.43
Cost1.69±0.151.53±0.111.49±0.140.87±0.07
Optimistic$^3$Reward410.06±0.08412.36±0.17433.22±0.28579.36±0.21
Cost1.28±0.421.27±0.441.24±0.470.58±0.41

We have submitted a revised version of our manuscript to address the reviewers’ comments. Thank you again for your time.

Thanks for your reply, your explaination has addressed my concerns.

Reviewer_5ctuOpenReview ↗
Rating
3
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies stochastic constrained contextual bandits under a general realizability condition, using regression oracles with a cumulative prediction error bound UU. It proposes QUID, a primal-dual algorithm that combines quadratic queue-normalized inverse-gap exploration with a discounted virtual queue update.

Under general feasibility, for every θ∈[1/2,1]\theta\in[1/2,1], the stated guarantees are O~(TθU1−θ)\widetilde{O}(T^\theta U^{1-\theta}) regret and O~(T1−θ/2Uθ/2)\widetilde{O}(T^{1-\theta/2}U^{\theta/2}) constraint violation. When Slater’s condition holds with an unknown margin ϵ>0\epsilon>0, the violation bound improves while preserving the regret guarantee. The paper also reports experiments on learning-to-rank and constrained bidding tasks.

Critical strengths
  • The interaction between quadratic queue normalization and dual regularization provides an interesting way to control regret without first bounding the dual process. This specific interaction is the relevant algorithmic contribution, since combining IGW with primal-dual or virtual-queue methods already appears in prior work.

  • The main text outlines the analysis and explains the complementary roles of normalization and regularization, as well as the separation of low- and high-prediction-error rounds under Slater’s condition.

  • Experiments are included on two tasks, with comparisons against several existing methods.

Critical weaknesses
  • The lower-bound and optimality discussion needs clarification. The paper does not establish a matching lower bound. Moreover, the conjecture quoted in Remark 4.2 appears inconsistent with the paper’s own balanced guarantee.

  • The dependence on the number of actions is omitted from the main guarantees.

  • The experiments do not directly test the main design choices or the tunable tradeoff. Section 5 evaluates only θ=1/2\theta=1/2 and states that both environments have Slater margin ϵ=10−3\epsilon=10^{-3}. No reported ablations isolate quadratic queue normalization and discounted queue updates. The experiments also do not evaluate the balanced setting θ=2/3\theta=2/3, vary the Slater margin, or include an instance that is feasible without satisfying Slater’s condition. Consequently, the empirical evidence for the proposed components and the broader regret–violation tradeoff is limited.

  • The connection between the violation criterion and the motivating applications needs clarification. Equation (4) defines signed expected cumulative violation: $ \mathrm{Viol}T= \mathbb{E}\left[\sum{t=1}^{T}g(x_t,a_t)\right]. $ This criterion permits positive and negative costs to offset one another, including across different realizations. The introduction motivates the problem through resource budgets and related operational constraints, but it would help to explain which applications permit this interpretation and which require a hard budget or stronger control of transient violations. The high-probability queue bounds and Equation (17) also suggest that a stronger realized cumulative-cost guarantee could be stated more explicitly.

  • The experimental construction leaves some assumptions unclear. The experiments use Gaussian noise and Gaussian auction variables, whereas the model assumes bounded rewards and costs. The description does not specify whether observations are clipped or truncated. It also states that both environments have Slater margin ϵ=10−3\epsilon=10^{-3} without explaining how this margin is established.

  • Some presentation and reporting details could be improved. Table 1 is difficult to interpret before the formal setup and oracle assumptions are introduced, although its caption defines several symbols. In addition, Figure 1 reports averages over 50 seeds without uncertainty bands or error bars, making it harder to assess the reliability of the empirical differences.

Questions for authors
  1. How should Remark 4.2 be reconciled with the θ=2/3\theta=2/3 guarantee in Theorem 4.1? Does your result refute the quoted conjecture for sufficiently small Slater margins? Please clarify the parameter range or additional restrictions under which a matching lower bound remains plausible, such as a restriction to algorithms achieving O~(TU)\widetilde{O}(\sqrt{TU}) regret.

  2. Can you state the dependence on KK explicitly in the main guarantees and comparisons? Does the optimality claim concern only the T,UT,U dependence for fixed KK, and can the parameters be tuned to improve the dependence on the number of actions?

  3. Can you include ablations that isolate quadratic queue normalization and dual discounting, as well as experiments varying θ\theta and ϵ\epsilon? In particular, evaluating θ=2/3\theta=2/3 and a setting without Slater’s condition would help assess the main theoretical tradeoff empirically.

  4. How is UU selected for XGBoost, and how sensitive is QUID to its misspecification? Can the algorithm adapt when a useful bound is unavailable? Please also specify how the regression oracles are updated and how oracle and algorithm hyperparameters are selected.

  5. How were the confidence bounds and context-distribution information required by Optimistic3\mathrm{Optimistic}^3 handled? Can you include a comparison in an environment where these requirements can be satisfied, or qualify the conclusions drawn from this baseline?

  6. Which motivating applications allow violations to be offset by later negative costs or across different realizations? What is the strongest guarantee on realized cumulative cost, including intermediate prefixes, that follows from Equation (17) and the high-probability queue bounds? Stating this explicitly would help clarify the practical meaning of the result.

  7. Were the Gaussian observations clipped or truncated to meet the boundedness assumptions? How were the environments constructed or calibrated to obtain the stated Slater margin? Can you also report uncertainty estimates for the 50-seed comparisons?

  8. Which parts of the normalization-and-regularization argument depend essentially on stochastic i.i.d. contexts, and which could extend to other constrained online-learning settings? Can you identify a concrete setting in which either the cancellation argument or the separation of low- and high-prediction-error rounds could improve existing guarantees?

4 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

We thank reviewer for the positive assessment and recognizing the contribution of our work. We respond to your questions as follows.

Lower bound. We thank the reviewer for raising this point. In Remark 4.2, the conjecture of Guo and Liu [R1] serves as a benchmark representing the best rate previously expected for this problem, and the remark explicitly leaves the existence of a matching lower bound as an open problem. Measured against this benchmark, QUID matches the conjectured rate with θ=1/2\theta = 1/2 and surpasses it with the balanced choice θ=2/3\theta = 2/3. This indicates that the conjecture is overly pessimistic and that the problem admits better performance than previously believed. Since unconstrained contextual bandits form a special case of our problem, the regret attained with θ=1/2\theta = 1/2 also matches the known lower bound for regression oracle based contextual bandits, up to factors in KK and logarithmic terms. Deriving lower bound in this setting is a challenging problem, which we leave to future work.

Generalization. We would like to clarify that our method is general: neither the normalization nor the regularization relies on stochastic i.i.d. contexts. For the more challenging adversarial context setting, assuming that Slater's condition holds for every context, our result can be directly extended to constrained bandits with adversarial contexts. The normalization idea applies whenever estimation errors enter the analysis multiplied by the dual variable, which is a common structure in primal-dual methods for constrained learning under bandit feedback. For example, the regret and violation of the CMDP algorithm of Stradi et al. [R2] scale with the largest Lagrange multiplier, yielding O~(min⁡{T/ϵ2,T3/4})\tilde O(\min\lbrace \sqrt{T}/\epsilon^2, T^{3/4}\rbrace ), the same structure as LOE2D. Our preliminary derivation indicates that queue normalization and the discounted update extend directly to this setting without additional assumptions or computation. More broadly, we believe the approach benefit other constrained bandit and model-based CMDP problems, which will be explored in the next work.

Dependence on KK. The regret scales as O(K TθU1−θ)O(K\ T^{\theta}U^{1-\theta}), while KK enters the violation bounds only through lower-order terms. Rescaling γ→γ/K+1\gamma \to \gamma/\sqrt{K+1} and V→K+1 VV \to \sqrt{K+1}\ V keeps ρ\rho unchanged and improves the guarantee to O(K TθU1−θ)O(\sqrt{K}\ T^{\theta}U^{1-\theta}) and O~(K T1−θ/2Uθ/2)\tilde O(\sqrt{K}\ T^{1-\theta/2}U^{\theta/2}) for regret and violation respectively, which is the optimal dependence on KK.

Violation criterion. We thank the reviewer for the suggestions. Our criterion follows the standard long term constraint formulation and suits applications where the constraint is imposed on an aggregate quantity over the horizon. The formulation can be applied to average power in wireless scheduling [R3], minimum selection rate fairness [R4, R5], and budget-limited crowdsourcing [R6]. While applications such as safe controller tuning in robotics [R7] and power grid operation [R8] do not permit offsetting and are better captured by hard violation metrics [R9, R10]. Moreover, (17) and the high-probability queue bounds imply that the realized cumulative cost satisfies the same bounds with high probability, simultaneously for all prefixes, which also controls transient violations. We will state this explicitly.

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

Experiments. We reran all experiments with T=50,000T=50{,}000 and report the average reward and cost per round over the last 1,000 rounds (mean ±\pm std over 50 seeds; for clarity, the rewards and costs reported in the tables below are multiplied by 10310^{3}; θ=1/2\theta=1/2 and ϵ=10−3\epsilon=10^{-3} unless stated).

(a) Optimistic$^3$. In ranking and bidding, its confidence bounds and context distribution are unavailable, so it uses XGBoost point prediction. Since Optimistic$^3$ requires confidence bounds for every action and context in each round, and the context distribution must be known, it is difficult to find a real-world dataset satisfying these requirements. We therefore add a synthetic environment (Toy: four uniform contexts, four actions, affine rewards and signed costs with bounded noise), where UCB/LCB oracles and the known context distribution satisfy the assumptions of Optimistic$^3$.

(b) Hyperparameters. In each environment, we first run the oracle for a full horizon with random actions and random seeds, select the XGBoost configuration with the best prediction accuracy (100 trees of depth 5), and set U0U_0 to the largest cumulative prediction error observed. Table I shows that QUID is robust to overestimating UU, whereas underestimating UU leads to insufficient exploration and degraded reward. The asymmetry is expected: Assumption 2.2 only requires UU to upper bound the cumulative prediction error. A conservative estimate therefore preserves the guarantees up to constant factors, while an underestimate may violate the assumption.

Table I: Sensitivity of QUID to the oracle error bound

U/U0U/U_0Ranking RewardRanking CostBidding RewardBidding CostToy RewardToy Cost
0.1×0.1\times221.60±4.333.96±6.0411.22±0.620.98±0.63410.81±0.870.27±0.11
1×1\times254.32±1.561.44±0.1712.82±0.571.32±0.67411.67±0.850.79±0.11
10×10\times256.44±1.573.67±0.1312.60±0.801.44±0.50414.37±0.912.43±0.12

(c) Environment construction. We clip observed rewards and costs to [0,F][0,F] and [−G,G][-G,G]. The Slater margin is set by rescaling negative costs so that the lowest achievable expected cost is exactly −ϵ-\epsilon, and ϵ=0\epsilon=0 gives a feasible instance without Slater's condition.

(d) Ablation and θ\theta. We remove the queue normalization (βt=1\beta_t=1) or the discount (ρ=0\rho=0), and set θ\theta to different values to validate the tradeoff of regret and violation. Removing normalization substantially reduces reward, while removing discount yields a smaller reduction. Removing either component has little effect on cost, since the cost is already close to zero (recall that the values in the table have been scaled up by a factor of 10310^3). Increasing θ\theta lowers the cost monotonically, matching the predicted tradeoff.

Table II: Ablation of the two design components and the tradeoff parameter θ\theta

VariantRanking RewardRanking CostBidding RewardBidding CostToy RewardToy Cost
\textit{(a) Design ablation, θ=1/2\theta=1/2}
QUID (full)254.32±1.561.44±0.1712.82±0.571.32±0.67411.67±0.850.79±0.11
βt=1\beta_t=1 (no normalization)227.93±1.661.51±0.3111.40±0.741.27±0.90396.88±0.870.78±0.05
ρ=0\rho=0 (no discount)253.97±1.441.32±0.2212.14±0.761.33±0.90403.76±0.270.50±0.12
\textit{(b) Tradeoff parameter θ\theta}
θ=1/2\theta=1/2254.32±1.561.44±0.1712.82±0.571.32±0.67411.67±0.850.79±0.11
θ=2/3\theta=2/3253.82±1.310.89±0.2710.72±1.061.07±0.89410.77±0.870.25±0.10
θ=1\theta=1253.48±1.640.42±0.1911.17±1.130.99±0.52409.94±0.790.06±0.11

(e) Slater margins. Due to space limits, Table III reports Toy. Across all margins, including ϵ=0\epsilon=0 without Slater's condition. The cost of QUID decreases as the margin grows, in line with the theory, and stays below that of LOE2D and Optimistic$^3$ at a comparable reward.

Table III: Toy environment under different Slater margins

MethodMetricϵ=0\epsilon=010−310^{-3}10−210^{-2}10−110^{-1}
QUIDReward409.54±0.77411.67±0.85432.54±0.90579.22±0.39
Cost0.88±0.140.79±0.110.74±0.120.44±0.07
LOE2DReward410.92±0.62412.87±0.94433.69±0.98579.69±0.43
Cost1.69±0.151.53±0.111.49±0.140.87±0.07
Optimistic$^3$Reward410.06±0.08412.36±0.17433.22±0.28579.36±0.21
Cost1.28±0.421.27±0.441.24±0.470.58±0.41

We have submitted a revised version of our manuscript to address the reviewers’ comments. Thank you again for your time.

Reference

  • [R1] “Stochastic Constrained Contextual Bandits via Lyapunov Optimization Based Estimation to Decision Framework”, COLT 2024.
  • [R2] “Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints”, ICML 2025.
  • [R3] “Stochastic Network Optimization with Application to Communication and Queueing Systems”, Morgan and Claypool 2010.
  • [R4] “Combinatorial Sleeping Bandits with Fairness Constraints”, IEEE Transactions on Network Science and Engineering 2020.
  • [R5] “Achieving Fairness in the Stochastic Multi-Armed Bandit Problem”, JMLR 2021.
  • [R6] “Efficient Crowdsourcing of Unknown Experts Using Bounded Multi-Armed Bandits”, Artificial Intelligence 2014.
  • [R7] “Safe Controller Optimization for Quadrotors with Gaussian Processes”, ICRA 2016.
  • [R8] “Linear Stochastic Bandits Under Safety Constraints”, NeurIPS 2019.
  • [R9] “Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints”, ICML 2021.
  • [R10] “Online Convex Optimization with Hard Constraints: Towards the Best of Two Worlds and Beyond”, NeurIPS 2022.
  • [R11] “Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints”, ICML 2025.

I thank the authors for their answers and will keep my score.

Reviewer_SaGzOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies stochastic contextual bandits with a long-term cost constraint, under general realizability and online regression oracles that only give a cumulative squared-error bound. The algorithm, QUID, is a primal-dual method: it runs inverse-gap weighting on an estimated Lagrangian score, with the exploration rate normalized by the square of the dual variable (the virtual queue), and updates the queue with a small discount factor. The main result is a tunable tradeoff between regret and constraint violation that improves the balanced rate of previous methods, and under Slater's condition the violation bound has a better dependence on the Slater margin, without knowing the margin in advance. The key step in the analysis is a regret-plus-drift inequality that bounds the regret without first bounding the queue length. Experiments are on a learning-to-rank task and a constrained bidding task with XGBoost as the regression oracle.

Critical strengths

The two modifications work together: queue normalization controls the amplification of prediction error by the dual variable, while the dual discounting compensates for the additional exploration penalty, so regret and violation can be analyzed separately. The improvement over LOE2D is not just a constant: the regret no longer depends on the Slater margin, the balanced rate improves from T^(3/4) to T^(2/3), and the margin dependence of the violation improves from 1/ε^2 to 1/ε. These are obtained under the same weak oracle assumption and without the prior knowledge that LagrangeCBwLC or Optimistic^3 need. The Slater analysis, which separates rounds by prediction risk and compensates the queue for the high-risk rounds, is a nice way to handle an oracle guarantee that is only cumulative.

Critical weaknesses

First, the novelty is limited. The setting, the oracle assumption, the inverse-gap weighting and the virtual queue are all from Slivkins et al. 2024 and Guo and Liu 2024. The paper presents the decoupling of the regret analysis from the queue as its main contribution, but in the Lyapunov drift-plus-penalty framework (Neely 2010; Yu, Neely and Wei 2017) the regret bound is always obtained by summing the drift-plus-penalty inequality and telescoping, without bounding the queue first; Lemma 4.5 is this standard inequality. LOE2D needed a queue bound only because its prediction error term is multiplied by q_t. So what QUID really adds is the normalization β_t=1/(1+q_t^2 ), which removes q_t from that coefficient. This is a useful trick, but it is one trick, and the main gain is a rate improvement inside a known framework. There is also no lower bound: the optimality claim in Remark 4.2 rests on a conjectured lower bound from Guo and Liu, and the real open question, whether the T^(3/4) violation without Slater's condition is intrinsic to cumulative oracle guarantees (Optimistic^3 gets sqrt(T) for both with stronger oracles), is not addressed. It would also help if the authors could say whether the normalization idea applies to other constrained learning problems, for example constrained MDPs with a virtual queue.

Second, the discount has only a small effect on the algorithm. With ρ=1/(T+1), the discounted queue differs from the standard queue by at most Q_t/(T+1) per round, and its role in the proof is to supply the negative term -ρQ_t^2 in Lemma 4.4 that cancels the q_t^2 exploration cost introduced by the normalization. It would be good to state this clearly. An ablation with ρ=0 and with β_t=1 would show how much each of the two changes matters empirically.

Third, the experiments are weak. There are only two tasks, both with Slater margin ε=10^(-3), which is the regime where the 1/ε improvement is largest. T=5000 is short for rates that differ by small powers of T. Optimistic^3 is run with XGBoost, which does not provide the confidence bounds it assumes, so that comparison does not say much. In the ranking task the cost is still above the threshold at the end for all methods. More realistic applications or at least longer horizons would make the empirical part more convincing. Also, the algorithm needs U to set γ and V, and the paper does not say how U was chosen for XGBoost.

Questions for authors
  1. Can ρ be set to zero with a modified analysis? If the discount is only needed for the -ρ(Q_t)^2 term, is there another way to absorb the (q_t)^2 exploration cost?

  2. How is U chosen for the XGBoost oracle in the experiments, and how sensitive are the results to this choice? Please also report an ablation with β_t=1 and with ρ=0.

4 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

We thank the reviewer’s comments and recognizing the contribution of our work. We respond to your questions as follows.

Novelty. We thank the reviewer for this great comment to clarify our contribution. We believe QUID goes well beyond a single normalization trick. It introduces a modular framework that jointly designs queue-normalized exploration and a discounted regulator to achieve improved regret and constraint violation guarantees under general realizability. Let us expand the discussion as follows.

We agree with the reviewer that classical Lyapunov drift-plus-penalty analysis can establish regret bounds without first bounding the queue, provided that the learning error terms can be controlled independently of the queue. This is possible in several constrained online learning settings, such as constrained online convex optimization [R1] and constrained contextual bandits with valid UCB/LCB estimates [R2, R3]. However, under general realizability, regression oracles provide only cumulative prediction error guarantees rather than uniform confidence bounds. Consequently, prediction errors in the drift analysis are amplified by the queue, preventing a direct application of classical drift-plus-penalty analysis. This is precisely why LagrangeCBwLC [R4] requires prior knowledge of the Slater margin to control the dual variable, while LOE2D [R5] relies on a separate queue bound and multi-step Lyapunov analysis to amortize prediction errors, leading to weaker regret and violation guarantees.

QUID overcomes this challenge through two complementary and tightly coupled designs. First, quadratic queue normalization βt=1/(1+qt2)\beta_t=1/(1+q_t^2) removes the queue dependence from the prediction error term, but introduces an additional exploration penalty proportional to qt2q_t^2. Second, the discounted queue update introduces a negative quadratic term in the Lyapunov drift that precisely compensates for this additional exploration penalty. Note that both designs are essential and must be carefully calibrated to establish the desired regret guarantee. The joint design enables the one-step regret-plus-drift inequality in Lemma 4.5 under general realizability. Although the inequality takes a classical form, achieving it requires both complementary designs rather than a direct application of existing Lyapunov techniques. Thus, QUID offers a modular framework beyond a single normalization trick, with potential applications to broader constrained online learning problems.

Lower bound. We thank the reviewer for raising this important question. To the best of our knowledge, no matching lower bound has been established for stochastic contextual bandits with general constraints under general realizability to date. Establishing such a lower bound is challenging, as it requires characterizing the Pareto-optimal tradeoff between regret and constraint violation under weak oracle assumptions. We will clarify this limitation in the revised paper and leave a rigorous proof for future work.

Generalization. We thank the reviewer for this insightful suggestion. We believe QUID can be naturally extended to broader constrained learning problems, including constrained MDPs (CMDPs). Specifically, for episodic CMDPs with suitable regression oracles for policy-specific Q-value functions, one can construct Lagrangian Q-value estimates by combining reward and cost-to-go estimates with a virtual queue. The joint design of queue normalization and discounted regulation can then be applied directly under appropriate oracle guarantees. However, for continuing CMDPs with streaming, single-trajectory feedback, the extension is less straightforward. Both the policy and Q-value estimates evolve at each step, making it challenging to control the resulting prediction errors under QUID. Establishing regret and violation guarantees in this setting requires careful analysis.

The discount factor. We thank the reviewer for this suggestion and will state the role of discount factor explicitly for a better understanding. If we set ρ=0\rho = 0, we have not found an analysis that can preserve the current results without changing the algorithm’s design. To remove the discount from the virtual update, one can instead use Vt:=V(1+t/T)V_t:=V(1+t/T), qt:=Qt/Vtq_t:=Q_t/V_t, and Qt+1=[Qt+ct(at)]+Q_{t+1}=[Q_t+c_t(a_t)]_+. The potential function then becomes Ψt:=Qt2/(2Vt−1)\Psi_t:=Q_t^2/(2V_{t-1}), which yields a cancelling term −K+12γqt2-\frac{K+1}{2\gamma}q_t^2. However, the discount is in fact implicitly transferred to the multiplier update, since qt+1=[(1−ρt)qt+ct/Vt+1]+q_{t+1}=[(1-\rho_t)q_t+c_t/V_{t+1}]_+ with ρt=K+1γVt+K+1\rho_t=\frac{K+1}{\gamma V_t+K+1}. Thus, the discount factor still exists implicitly.

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

Experiments. Following the reviewers’ suggestion, we reran all experiments with T=50,000T = 50{,}000. Since Optimistic$^3$ requires confidence bounds for every action and context in each round, and the context distribution must be known, it is difficult to find a real-world dataset satisfying these requirements. We therefore add a synthetic environment (Toy: four uniform contexts, four actions, affine rewards and signed costs with bounded noise), where UCB/LCB oracles and the known context distribution satisfy the assumptions of Optimistic$^3$ [R6]. We report the average reward and cost per round over the last 1,000 rounds (mean ±\pm std over 50 seeds; for clarity, the rewards and costs reported in the tables below are multiplied by 10310^{3}; θ=1/2\theta = 1/2 and ϵ=10−3\epsilon = 10^{-3} unless stated).

(a) Choice of UU. In each environment, we first run the oracle for a full horizon with random actions and random seeds, select the XGBoost configuration with the best prediction accuracy (100 trees of depth 5), and set U0U_0 to the largest cumulative prediction error observed. Table I shows that QUID is robust to overestimating UU, whereas underestimating UU leads to insufficient exploration and degraded reward. The asymmetry is expected: Assumption 2.2 only requires UU to upper bound the cumulative prediction error. A conservative estimate therefore preserves the guarantees up to constant factors, while an underestimate may violate the assumption.

Table I: Sensitivity of QUID to the oracle error bound UU

U/U0U/U_0Ranking RewardRanking CostBidding RewardBidding CostToy RewardToy Cost
0.1×0.1\times221.60 ± 4.333.96 ± 6.0411.22 ± 0.620.98 ± 0.63410.81 ± 0.870.27 ± 0.11
0.3×0.3\times223.04 ± 2.785.02 ± 7.4911.45 ± 0.590.76 ± 0.62411.12 ± 0.880.45 ± 0.12
1×1\times254.32 ± 1.561.44 ± 0.1712.82 ± 0.571.32 ± 0.67411.67 ± 0.850.79 ± 0.11
3×3\times255.53 ± 1.832.25 ± 0.1711.99 ± 0.520.94 ± 0.15412.59 ± 0.871.35 ± 0.11
10×10\times256.44 ± 1.573.67 ± 0.1312.60 ± 0.801.44 ± 0.50414.37 ± 0.912.43 ± 0.12

(b) Ablation. Table II removes the queue normalization (βt=1\beta_t = 1) or the discount (ρ=0\rho = 0). Result shows that removing normalization substantially reduces reward, while removing discount yields a smaller reduction. Removing either component has little effect on cost, since the cost is already close to zero (recall that the values in the table have been scaled up by a factor of 10310^3).

Table II: Ablation of the two design components

VariantRanking RewardRanking CostBidding RewardBidding CostToy RewardToy Cost
QUID (full)254.32 ± 1.561.44 ± 0.1712.82 ± 0.571.32 ± 0.67411.67 ± 0.850.79 ± 0.11
βt=1\beta_t=1 (no normalization)227.93 ± 1.661.51 ± 0.3111.40 ± 0.741.27 ± 0.90396.88 ± 0.870.78 ± 0.05
ρ=0\rho=0 (no discount)253.97 ± 1.441.32 ± 0.2212.14 ± 0.761.33 ± 0.90403.76 ± 0.270.50 ± 0.12

(c) Slater margins. Due to space limits, Table III reports Toy, where the assumptions of Optimistic$^3$ hold. Across all margins, including ϵ=0\epsilon = 0 without Slater's condition. The cost of QUID decreases as the margin grows, in line with the theory, and stays below that of LOE2D and Optimistic$^3$ at a comparable reward.

Table III: Toy environment under different Slater margins

MethodMetricϵ=0\epsilon=010−310^{-3}10−210^{-2}10−110^{-1}
QUIDReward409.54 ± 0.77411.67 ± 0.85432.54 ± 0.90579.22 ± 0.39
Cost0.88 ± 0.140.79 ± 0.110.74 ± 0.120.44 ± 0.07
LOE2DReward410.92 ± 0.62412.87 ± 0.94433.69 ± 0.98579.69 ± 0.43
Cost1.69 ± 0.151.53 ± 0.111.49 ± 0.140.87 ± 0.07
Optimistic$^3$Reward410.06 ± 0.08412.36 ± 0.17433.22 ± 0.28579.36 ± 0.21
Cost1.28 ± 0.421.27 ± 0.441.24 ± 0.470.58 ± 0.41

We have uploaded a revised version of our manuscript. We hope that our responses address the reviewer's concern and that the reviewer can re-evaluate our work. Please let us know if you have any further questions, and we will do our best to address them.

Reference

  • [R1] “Online Convex Optimization with Stochastic Constraints”, NeurIPS 2017.
  • [R2] “An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints”, NeurIPS 2021.
  • [R3] “On Kernelized Multi-Armed Bandits with Constraints”, NeurIPS 2022.
  • [R4] “Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression”, JMLR 2024.
  • [R5] “Stochastic Constrained Contextual Bandits via Lyapunov Optimization Based Estimation to Decision Framework”, COLT 2024.
  • [R6] “Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints”, ICML 2025.

Dear Reviewer SaGz,

As the discussion period is coming to an end, we would like to summarize that we have revised the manuscript and added new experiments, including a longer horizon, ablations for βt\beta_t=1 and ρ\rho=0, sensitivity to UU, and a setting where Optimistic$^{3}$ satisfies its assumptions. Please let us know if any questions remain, and we would be happy to respond before the discussion ends.

Best regards,

Authors of submission 32355

Dear Reviewer SaGz,

As the discussion approaches is coming to an end, we would like to follow up on our response to your concern.

We have clarified that classical Lyapunov drift-plus-penalty analysis breaks down for contextual bandits under general realizability, while QUID overcomes this challenge through two complementary and tightly coupled designs, queue normalization removes the dual dependence from the error term, and the discounted update absorbs the exploration cost that normalization introduces. We also appreciate that you highlighted the novel Lyapunov drift analysis under Slater’s condition. We view the algorithm design and analysis as a modular framework that may carry over to other constrained online learning problems.

Thank you again for your time. We would be happy to discuss any remaining concerns before the discussion period ends.

Best regards,

Authors of submission 32355

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

Dear Area Chair and Reviewers,

We sincerely thank all reviewers for their time and constructive feedback. We are especially grateful that the reviewers recognized our presentation, improved theoretical results, and the novel Lyapunov analysis under Slater’s condition.

During the rebuttal, we addressed the main concerns as follows:

  1. Role of the two design components. We explained why queue normalization and the discounted update must be designed jointly.
  2. Stronger experiments. We reran all experiments with T = 50,000 and added ablations, a tradeoff study over θ\theta, a Slater-margin study (including ϵ\epsilon = 0), a sensitivity study over UU, and a synthetic environment where Optimistic$^{3}$ satisfies its assumptions.
  3. Lower bound and generalization. We clarified the discussion of lower bound and the extensions to adversarial contexts and constrained MDPs.

We have uploaded a revised manuscript reflecting these changes. Finally, we thank all the reviewers and the Area Chair for their time and effort in handling our submission.

Best regards,
Authors of submission 32355

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.