- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies stochastic contextual bandits with general constraints. The learner maximizes cumulative reward subject to non-positive cumulative cost. The result is evaluated by regret and expected cumulative violation. This paper proposes OPALP, which solves an optimistic policy LP every round. OPALP achieves regret and violation without Slater's condition, where is a basis-based sub-optimality gap. This paper gives further CBwK extension and synthetic experiments.
Critical strengths
- The Slater-free setting in constrained contextual bandits is important, and this paper achieves an instance-independent guarantee that improves upon the standard bound.
- The proposed algorithm is interesting and differs from traditional primal-dual designs; the proof seems clean and correct.
Critical weaknesses
My main concern is that the instance-dependent bound only holds when Slater's condition holds, because Assumption 3.2 already implies it. If no policy satisfied the constraint strictly, every feasible policy would have expected cost exactly . The cost constraint would then be active at the optimal deterministic vertex, in addition to its active non-negativity constraints: one active constraint too many. Example 1 is consistent with this (, where is the Slater margin). Hence the "Slater's condition free" mark in Table 1 are overstated. Without Slater's condition, the paper can at best offer guarantees, which Guo et al. (2025) already achieve, so the contribution in the general case is more limited than presented.
Questions for authors
- If the instance-dependent results hold only under Slater’s condition, the proposed algorithm appears to achieve the same guarantees as prior work while introducing additional complexity? And what's the advantage of the proposed algorithm compared with primal-dual-based methods?
- Is the dependence necessary? Can be bounded by natural LP quantities?
- How does your analysis relate to LP-based analyses in Li, Sun & Ye (2021) and Chen et al. (2024) ? Is it possible to achieve instance-dependent guarantee in CBwK setting?
4 comments
Q3 – Relation to Li, Sun & Ye (2021) and Chen et al. (2024); instance-dependent guarantees in CBwK.
-
Common principle. All three analyses exploit the stability of the optimal basis of a unique, non-degenerate LP: regret is controlled once this basis is identified. The corresponding gap is in Li, Sun & Ye, the stability radius in Chen et al., and here.
-
Differences. (a) Setting: both works address hard budgets with non-negative consumption and a null action; Li, Sun & Ye have no contexts, and Chen et al. assume known reward and consumption functions. We treat general soft constraints with signed costs, and unknown rewards and costs in general function classes. (b) Algorithm: Li, Sun & Ye first identify the basis by elimination, then re-solve an LP restricted to it; Chen et al. re-solve an estimated LP. OPALP solves one optimistic LP per round, with no identification phase: identification is implicit in the analysis (Prop. C.4: a wrong active set forces a large estimation error). (c) Guarantees: OPALP attains the logarithmic and the worst-case rate simultaneously, whereas no worst-case bound is proved in Li, Sun & Ye. (d) Budget: both works re-solve with the remaining budget; OPALP keeps a static constraint with optimistic costs, which suits soft constraints.
-
CBwK. Point (d) is what limits Corollary 6.1 (knapsack bound) to : in its proof, the regret before budget exhaustion is still , and the term comes only from early stopping, caused by cost fluctuations and optimistic overspending under a static constraint. This is consistent with Li, Sun & Ye, who argue that a static right-hand side produces an term under hard budgets. Instance-dependent guarantees are known with known cost functions (Wu et al., 2015; Chen et al., 2024) and in the linear case under best-arm-optimality with a single resource (Sankararaman & Slivkins, 2021); with unknown rewards and costs in general function classes, the question is open to our knowledge. A natural route is to combine OPALP's optimistic LP with re-solving on the remaining budget once the active set is stable, which we leave for future work. We have added this discussion (Section 6 and App. C.4) and the comparison with Li, Sun & Ye (2021) in Section 2.
We thank you for your insightful feedback and hope that these responses address your questions and concerns. The paper has been revised accordingly, and we would be grateful if you could reconsider your score in light of these responses and of the revision. We are happy to discuss further if needed.
Thanks for the clarifications and revisions. The logarithmic regret improvement under non-degeneracy is valuable, though the Slater-free guarantees remain unchanged and the overall contribution still seems modest. I will keep my score, with the overall assessment borderline between 2 and 3.
Dear reviewer, we thank you very much for your feedback and for your engagement in the discussion, which has certainly made our paper better and stronger.
We hope that the tailored constructions we introduce (the optimistic LP and the gap ), and the first problem-dependent bound in the literature for contextual bandits with general constraints (to our knowledge), will be taken into account in your final assessment and will weigh in favour of our paper.
Dear Reviewer uLN8, we thank you for your review and the effort you dedicated to it. In the following, we provide detailed answers to your questions and address the points mentioned in the weaknesses section:
W – The logarithmic rate and Slater's condition.
We agree. The reviewer is right: Assumption 3.2 (feasibility and non-degeneracy) implies Slater's condition. The O(logT/Δ⋆) rate therefore holds only on instances satisfying Slater's condition, and the "Slater-free" mark of Table 1 (comparison with related work) is correct only for our O~(T) rate. We have split our row of Table 1 in two, as for Guo & Liu (2024): O~(T) regret without Slater's condition, and O(logT/Δ⋆) under non-degeneracy.
What Theorem 5.1 (main result) establishes. (i) On every feasible instance, with neither Slater's condition nor non-degeneracy: O~(T) regret and violation, matching the Slater-free rates of Guo et al. (2025). This part uses only Lemma 5.1 (the LP solved by OPALP is feasible) and Props. C.2–C.3 (per-round expected cost and regret are bounded by the confidence widths). (ii) On every non-degenerate instance: O(logT/Δ⋆) regret, with the same violation. The same algorithm achieves both, with no knowledge of a Slater margin or of Δ⋆.
Why this is not the guarantee of prior work. Slater's condition alone does not yield a logarithmic rate: under it, existing regret bounds remain of order T, namely O~(T/ν) with a known margin ν (Slivkins et al., 2024), O~(T/ν2) (Guo & Liu, 2024) and O~(T) (Guo et al., 2025). To our knowledge, (ii) is the first instance-dependent regret bound in the general-constraint setting of Table 1, with or without Slater's condition. As the reviewer notes on Example 1 (two-arm toy example), Δ⋆ shrinks with the Slater margin when the constraint binds; but it enters through logT/Δ⋆ rather than as a factor of T, and our bound min{logT/Δ⋆,TlogT} never exceeds the Slater-free rate. Non-degeneracy holds for almost every instance (App. A, discussion of the assumptions) and is the standard condition for such rates: it is assumed by Li, Sun & Ye (2021) and Chen et al. (2024), the works cited by the reviewer; Flajolet & Jaillet (2017) impose it on all LP bases (we need it only at the optimum); the degenerate "boundary cases" of Wu et al. (2015) revert to T; and Chen et al. (2024, Thm. 2.1) show that, with knapsacks, an Ω(T) gap to the LP benchmark is unavoidable when its optimum is degenerate.
Q1 – Same guarantees as prior work? Advantage over primal–dual methods. No. On non-degenerate instances, which are generic among those satisfying Slater's condition, primal–dual analyses give T regret whereas OPALP gives O(logT/Δ⋆), with the same O~(T) violation. Fig. 1 (synthetic comparison) shows the same picture: the regret of OPALP flattens while that of the three primal–dual baselines keeps growing. On the remaining instances, including those violating Slater's condition, OPALP indeed offers the rate of Guo et al. (2025) at a higher computational cost. This cost is a trade-off stated in the paper; it is mitigated by Lazy-OPALP (which re-solves the LP only when a confidence width has shrunk by a factor 2) and by the structure of the per-round LP, which is solvable in near-linear time (see our response to Reviewer WD4m).
Q2 – Is the 1/Δ⋆ dependence necessary? Can L(I) be bounded?
Inverse-gap dependence. It cannot be removed in general: with a single context and a void constraint (ψ≡−1), Δ⋆ is exactly the classical reward gap, for which Ω(logT/Δ) is unavoidable (Lai & Robbins, 1985). We do not claim that Δ⋆ is the sharpest instance-dependent constant. For comparison, our dependence is 1/Δ⋆, against 1/δ2 in Li, Sun & Ye (2021) and 1/D2 in Chen et al. (2024) for their respective gaps.
L(I). Yes. By Prop. C.1 (properties of L), L(I) is the right derivative, with respect to the slack, of the value of the LP restricted to I: it is the shadow price of the constraint. With one constraint it is explicit. A candidate set either fixes one action per context, and then L(I)=0; or it leaves one context c with two free actions a,a′, and then L(I)≤∣r(c,a)−r(c,a′)∣/∣ψ(c,a)−ψ(c,a′)∣, the reward-to-cost exchange rate between them. We have added this bound after Definition 4.3 (performance gap), with a proof in Proposition C.6.