- 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
-
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.
-
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
-
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.
-
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.
-
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
-
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?
-
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.
-
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.
-
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
Thanks for your reply, your explaination has addressed my concerns.
We thank reviewer for the positive assessment and recognizing the contribution of our work. We respond to your questions as follows.
Dependence on K, F and G. 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)),
ViolT=O~(1+F T1−θ/2Uθ/2+KTU)(general),
ViolT=O~((1+F)TU/ϵ+KG TU/ϵ)(Slater).
Thus K enters the regret linearly but only lower-order terms of the violation. Rescaling γ→γ/K+1 and V→K+1 V keeps ρ unchanged and improves the guarantee to O(K TθU1−θ) and O~(K T1−θ/2Uθ/2) for regret and violation respectively, which is the optimal dependence on K.
Experiments. We reran all experiments with T=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 103).
(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] and [−G,G]. The Slater margin is set by rescaling negative costs so that the lowest achievable expected cost is exactly −ϵ, and ϵ=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 U0 to the largest cumulative prediction error observed. Table I shows that QUID is robust to overestimating U, whereas underestimating U leads to insufficient exploration and degraded reward. The asymmetry is expected: Assumption 2.2 only requires U 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
(d) Ablation and θ. We remove the queue normalization(βt=1) or the discount (ρ=0), and set θ 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 θ
(e) Slater margins. Due to space limits, Table III reports Toy. Across all margins, including ϵ=0. The results generally align with the theoretical trend regarding changes in the Slater margin.
Table III: Toy environment under different Slater margins
We have submitted a revised version of our manuscript to address the reviewers’ comments. Thank you again for your time.