acceptodds
Under review as a conference paper at ICLR 2027

Improved Regret bounds for Stochastic Contextual Bandits with General Constraints

Abstract

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 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 guarantees on constraint violation. These results hinge on a refined analysis of the offline benchmark structure.

Primary area:
learning theory
Keywords:
Bandits, generic cost/reward functions, instance-dependent bounds

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_uLN8OpenReview ↗
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 O(min⁡{log⁡T/Δ⋆,Tlog⁡T})O(\min\{\log T/\Delta^\star, \sqrt{T \log T}\}) regret and O~(T)\tilde{O}(\sqrt{T}) violation without Slater's condition, where Δ⋆\Delta^\star is a basis-based sub-optimality gap. This paper gives further CBwK extension and synthetic experiments.

Critical strengths
  1. The Slater-free setting in constrained contextual bandits is important, and this paper achieves an instance-independent guarantee that improves upon the standard O(T)O(\sqrt T) bound.
  2. 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 O(log⁡T/Δ⋆)O(\log T/\Delta^\star) 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 00. The cost constraint would then be active at the optimal deterministic vertex, in addition to its ∣C∣(∣A∣−1)\lvert\mathcal{C}\rvert(\lvert\mathcal{A}\rvert-1) active non-negativity constraints: one active constraint too many. Example 1 is consistent with this (Δ⋆≤b\Delta^\star \le b, where bb 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 O~(T)\tilde{O}(\sqrt{T}) guarantees, which Guo et al. (2025) already achieve, so the contribution in the general case is more limited than presented.

Questions for authors
  1. 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?
  2. Is the 1/Δ⋆1/\Delta^\star dependence necessary? Can L(I)\mathcal{L}(\mathcal{I}) be bounded by natural LP quantities?
  3. 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

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(log⁡T/Δ⋆)\mathcal O(\log T/\Delta^\star) 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)\tilde{\mathcal O}(\sqrt T) rate. We have split our row of Table 1 in two, as for Guo & Liu (2024): O~(T)\tilde{\mathcal O}(\sqrt T) regret without Slater's condition, and O(log⁡T/Δ⋆)\mathcal O(\log T/\Delta^\star) 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)\tilde{\mathcal O}(\sqrt 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(log⁡T/Δ⋆)\mathcal O(\log T/\Delta^\star) regret, with the same violation. The same algorithm achieves both, with no knowledge of a Slater margin or of Δ⋆\Delta^\star.

  • 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\sqrt T, namely O~(T/ν)\tilde{\mathcal O}(\sqrt T/\nu) with a known margin ν\nu (Slivkins et al., 2024), O~(T/ν2)\tilde{\mathcal O}(\sqrt T/\nu^2) (Guo & Liu, 2024) and O~(T)\tilde{\mathcal O}(\sqrt 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), Δ⋆\Delta^\star shrinks with the Slater margin when the constraint binds; but it enters through log⁡T/Δ⋆\log T/\Delta^\star rather than as a factor of T\sqrt T, and our bound min⁡{log⁡T/Δ⋆,Tlog⁡T}\min\lbrace\log T/\Delta^\star,\sqrt{T\log T}\rbrace 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\sqrt T; and Chen et al. (2024, Thm. 2.1) show that, with knapsacks, an Ω(T)\Omega(\sqrt 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\sqrt T regret whereas OPALP gives O(log⁡T/Δ⋆)\mathcal O(\log T/\Delta^\star), with the same O~(T)\tilde{\mathcal O}(\sqrt 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\sqrt2) 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/Δ⋆1/\Delta^\star dependence necessary? Can L(I)\mathcal L(\mathcal I) be bounded?

  • Inverse-gap dependence. It cannot be removed in general: with a single context and a void constraint (ψ≡−1\psi\equiv-1), Δ⋆\Delta^\star is exactly the classical reward gap, for which Ω(log⁡T/Δ)\Omega(\log T/\Delta) is unavoidable (Lai & Robbins, 1985). We do not claim that Δ⋆\Delta^\star is the sharpest instance-dependent constant. For comparison, our dependence is 1/Δ⋆1/\Delta^\star, against 1/δ21/\delta^2 in Li, Sun & Ye (2021) and 1/D21/D^2 in Chen et al. (2024) for their respective gaps.

  • L(I)\mathcal L(\mathcal I). Yes. By Prop. C.1 (properties of L\mathcal L), L(I)\mathcal L(\mathcal I) is the right derivative, with respect to the slack, of the value of the LP restricted to I\mathcal 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\mathcal L(\mathcal I)=0; or it leaves one context cc with two free actions a,a′a,a', and then L(I)≤∣r(c,a)−r(c,a′)∣/∣ψ(c,a)−ψ(c,a′)∣\mathcal L(\mathcal I)\le|r(c,a)-r(c,a')|/|\psi(c,a)-\psi(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.

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 δ\delta in Li, Sun & Ye, the stability radius DD in Chen et al., and Δ⋆\Delta^\star 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 T\sqrt T: in its proof, the regret before budget exhaustion is still O(log⁡T/Δ⋆)\mathcal O(\log T/\Delta^\star), and the T\sqrt T 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 Ω(T)\Omega(\sqrt T) 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 Δ⋆\Delta^\star), 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.

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

This paper studies the problem of contextual bandits with general constraints, with realizable reward and cost functions, known context distribution and finite context space. The authors propose an algorithm that solve the primal problem directly by using the plug-in estimates of the reward and cost functions provided by the online regression oracle, while the literature mainly focuses on the primal-dual approach, such as Slivkins et al. (2024), Guo & Liu (2024). The authors proof that the proposed algorithm achieves a regret bound of RT=O(min⁡{log⁡T/Δ⋆,Tlog⁡T})R_T=O(\min\{\log T/\Delta^\star,\sqrt{T\log T}\}) and the cumulative constraint violation of VT=O~(T)V_T=\tilde O(\sqrt T). where Δ⋆\Delta^\star is the sub-optimality gap by considering the infeasible gap from the slackness of LP problem and the performance gap from the relaxation affected performance degradation. The violation bound is also shown to match the best known bound in the literature (Guo et al., 2025). For the regret bound, this is the first work that establishes a logarithmic regret bound for the contextual bandits with general constraints problem, which is a better upper bound than the existing O~(T)\tilde O(\sqrt T) regret bound in the large suboptimality gap regime. The authors also provide a synthetic experiment to demonstrate the regret bound and the violation bound of the proposed algorithm, which shows that the proposed algorithm regret and violation bounds match the theoretical results. Overall, this paper is a solid contribution to the literature of contextual bandits with general constraints.

Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression., Slivkins et al., 2024, JMLR.

Stochastic constrained contextual bandits via lyapunov optimization based estimation to decision framework. Guo & Liu, 2024, COLT.

Triple-optimistic learning for stochastic contextual bandits with general constraints. Guo et al., 2025, ICML.

Critical strengths

The theoretical results are solid and the proofs are correct. The authors provide a detailed theoretical analysis of the regret and violation bounds of the proposed algorithm. The violation bound matches the best known bound in the literature, and the regret bound is the first logarithmic regret bound for the contextual bandits with general constraints problem (although only in the large suboptimality gap regime). The authors also provide a synthetic experiment to demonstrate the regret and violation bounds of the proposed algorithm, showing that they match the theoretical results. Overall, this paper is a solid contribution to the literature of contextual bandits with general constraints.

This paper is well written and easy to follow, with clear definitions and assumptions. For the key concepts, the suboptimality gap and the binding set, the authors provide a clear example (Example 1) that helps readers understand the problem setting and the proposed algorithm.

Critical weaknesses
  1. The context distribution is known, while other existing methods, such as Slivkins et al. (2024), Guo & Liu (2024), work in the unknown context distribution. The comparison in Table 1 seems a little bit misleading, since they are not in the same setting and Slivkins et al. (2024), Guo & Liu (2024) achieve a higher regret bound, but they are in a harder setting. The authors should clarify this point in the paper.

  2. This paper assumes a finite context space. In the Linear Programming (LP) formulation (Eq. 3), the number of constraints depends on the number of contexts. Also, the candidate set (Definition 4.1) has a size of ∥C∥(A−1)\|\mathcal{C}\| (\mathcal{A} - 1) constraints, which also depends on the number of contexts. However, in many real-world applications, the context space is continuous or large, and the finite context space assumption has not been included in previous works such as Slivkins et al. (2024), Guo & Liu (2024).

Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression., Slivkins et al., 2024, JMLR.

Stochastic constrained contextual bandits via lyapunov optimization based estimation to decision framework. Guo & Liu, 2024, COLT.

Questions for authors
  1. Lines 189-197, Offline oracle problem. What kind of problem is solved in the offline oracle problem? Is it a planning problem? It is better to make it clearer in the paper, and why do we emphasize it is an offline oracle problem?

  2. Lines 265-267, what does the element (c,a)(c, a) in the constraint set J\mathcal{J} mean? Does it mean that π(c,a)≥0\pi(c, a) \geq 0?

  3. This paper assumes the context space is finite since the LP formulation (Eq. 3) has a number of constraints that depends on the number of contexts. Is it possible to extend the proposed algorithm to the setting with a continuous context space? If yes, what is the regret bound and violation bound in that setting? If not, what is the fundamental challenge to extend the proposed algorithm to that setting?

  4. Since the proposed algorithm is a primal method and uses the plug-in estimate provided by an online regression oracle, and there are also some works that reduce contextual bandit with general function approximation to an offline regression oracle, such as Falcon (Simchi & Xu, 2021) and OE2D (Qin & Zhang, 2026), is it possible to extend the proposed algorithm to the setting with an offline regression oracle? If yes, what is the regret bound and violation bound in that setting? If not, what is the main challenge in extending the proposed algorithm to that setting?

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability, Simchi & Xu, 2021, Mathematics of Operations Research.

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits, Qin & Zhang, 2026, COLT.

4 comments

Dear Reviewer eDhw, we are grateful for your positive feedback and your insightful comments on our work. Below, we provide detailed answers to the questions and comments raised in the Weaknesses section.


W1–W2 – Comparison with previous work. We thank the reviewer for these remarks. In the revised version, the comparison with previous work is clearer and more direct: Table 1 (comparison with related work) now reports the context space and the context distribution assumed by each method, and Section 2 points out that the settings differ.

Q1 – The offline oracle problem (lines 189–197). Problem (2) is the benchmark, not a problem solved by the learner. It is the static relaxation of the planning problem (1): the linear program of an oracle who knows the mean reward and cost functions and the context distribution ("offline": nothing is learned), with the constraint imposed in expectation rather than along the trajectory. Lemma 3.1 (benchmark) shows that its value Tv⋆T v^\star upper-bounds the value of problem (1), so regret against it is the standard choice (Guo & Liu, 2024; Guo et al., 2025). To avoid any confusion with the regression oracles of Assumption 3.3, we have renamed it "offline benchmark problem".

Q2 – The element (c,a)(c,a) of J\mathcal J (lines 265–267). Yes: the index (c,a)∈J(c,a)\in\mathcal J stands for the non-negativity constraint π(c,a)≥0\pi(c,a)\ge 0. It is active when π(c,a)=0\pi(c,a)=0, i.e., when the policy never plays action aa in context cc. A candidate set (Definition 4.1) is a set of ∣C∣(∣A∣−1)|\mathcal C|(|\mathcal A|-1) such constraints, possibly including the general constraint, that are active simultaneously. This is now stated explicitly in Section 4.

Q3 – Continuous context spaces.

  • Algorithm. Yes. With a single constraint, the optimistic LP has a threshold structure: in context cc, its solution plays an action maximizing r^t(c,a)−λtψˇt(c,a)\hat r_t(c,a)-\lambda_t\check\psi_t(c,a), up to randomization on ties, where the scalar λt\lambda_t solves a one-dimensional convex problem (the dual of the LP). No enumeration of contexts is needed, only expectations over the context distribution. This is the structure that also makes the per-round LP solvable in near-linear time (see our response to Reviewer WD4m).

  • Worst-case bounds. The O~(T)\tilde{\mathcal O}(\sqrt T) bounds on regret and violation carry over under the same assumptions, with a known distribution as in Guo et al. (2025): the proofs of these bounds (Lemma 5.1, the LP solved by OPALP is feasible; Props. C.2–C.3, per-round expected cost and regret are bounded by the confidence widths) only take expectations over contexts.

  • Logarithmic rate: the fundamental challenge. The gap Δ⋆\Delta^\star is a minimum over the finitely many bases of the LP. With a continuum of contexts, some contexts are typically arbitrarily close to indifference between two actions, and the gap vanishes. This is not specific to constraints: with general function classes, instance-dependent rates in contextual bandits require additional complexity measures, such as disagreement coefficients, even under a uniform gap (Foster, Rakhlin, Simchi-Levi & Xu, 2020). A continuous analogue of Δ⋆\Delta^\star is an open question.

Q4 – Offline regression oracles (FALCON, OE2D).

  • What OPALP needs. Not plug-in estimates, but one-sided estimates with confidence widths (Assumption 3.3: optimistic reward and cost estimates). They come from least-squares confidence sets and can be computed with an offline weighted least-squares oracle by binary search (Foster et al., 2018; App. A, discussion of the assumptions). In this sense OPALP already runs on an offline oracle, with the guarantees of Theorem 5.1 (main result) whenever these estimates satisfy Assumption 3.3. "Online" in our text only means that the estimates are updated as data arrive; we have clarified the terminology (Section 3 and App. A).

  • Plug-in offline oracles. FALCON (Simchi-Levi & Xu, 2021) and OE2D (Qin & Zhang, 2026) assume only a bound on the expected squared error of the fitted function and build no confidence bounds: they explore through a randomized action distribution computed from the plug-in estimate (inverse-gap weighting in FALCON, an exploitative F-design in OE2D). Our analysis uses optimism in three places: feasibility of the LP (Lemma 5.1), the per-round regret bound (Prop. C.3), and the absence of regret on the optimal active set (Prop. C.5). Without widths, optimism would have to be replaced by such explicit exploration around the plug-in LP solution, in epochs. We would expect T\sqrt T-type guarantees, as for these methods, but we have not analyzed this variant.

  • Main challenge for the logarithmic rate. These exploration schemes are calibrated for the minimax rate, and both works give worst-case bounds only. For unconstrained contextual bandits, instance-dependent rates with a regression oracle are obtained by combining such exploration with confidence sets (AdaCB; Foster, Rakhlin, Simchi-Levi & Xu, 2020), i.e., with the kind of widths we assume. Extending this to the constrained setting is open to our knowledge.

We thank you once again for your valuable feedback. We hope we have adequately addressed all of your points and questions, and we are pleased to inform you that the paper has been updated accordingly. We are happy to discuss further if needed.

Thansk for author's feedbacks. These responses have resolved my questions clearly. Although, from author's revised manuscript, the computation complexity depends on the context space size ∥C∥\|\mathcal{C}\|, which might be a concern in the practice deployment when context space is large. I wish the author could point this out in the final version. Overal, I will keep my score.

Dear reviewer, thank you very much for your feedback and for supporting our paper. All the points raised in our discussion will be incorporated in the final version.

Reviewer_WD4mOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes OPALP for stochastic contextual bandits with general soft constraints, using optimistic reward and cost estimates from regression oracles to repeatedly solve a policy-level linear program. Its main theoretical insight is an instance-dependent gap Δ⋆\Delta^\star that characterizes the optimal set of active constraints. Under realizability, nondegeneracy, and oracle assumptions, OPALP achieves O(log⁡T/Δ⋆)O(\log T/\Delta^\star) instance-dependent regret while retaining worst-case O~(T)\widetilde O(\sqrt T) regret and expected cumulative constraint violation, without requiring Slater’s condition. Synthetic and semi-synthetic ranking experiments support its performance, while a Lazy-OPALP variant reduces the computational burden of repeated linear-program solves.

Critical strengths
  1. Sharper regret guarantees: Under the stated assumptions, achieves O(log⁡T/Δ⋆)O(\log T/\Delta^\star) instance-dependent regret without Slater’s condition, while retaining worst-case O~(T)\widetilde O(\sqrt T) regret and constraint-violation bounds.

  2. Insightful geometric analysis: Defines a gap combining infeasibility and reward suboptimality through the LP’s active constraints, explaining when logarithmic regret is achievable.

  3. Attention to practical trade-offs: Introduces Lazy-OPALP to reduce optimization overhead and evaluates performance against primal–dual baselines on synthetic and semi-synthetic ranking tasks.

Critical weaknesses
  1. Restrictive assumptions: The logarithmic regret guarantee relies on a nondegenerate LP, a positive instance gap, and strong regression-oracle guarantees, leaving robustness to model misspecification unclear.

  2. Scope of the logarithmic guarantee: The paper establishes logarithmic instance-dependent regret for soft constraints while retaining a O~(T)\widetilde O(\sqrt T) bound on expected net constraint violation. Its knapsack extension provides a O~((1+v⋆/b)T)\widetilde O((1+v^\star/b)\sqrt T) regret bound, so the analysis does not establish that the logarithmic improvement extends to hard budget constraints.

  3. Computational scalability: Repeated LP solves become substantially more expensive as the context–action space grows. Although Lazy-OPALP reduces this burden, its empirical evaluation is limited to a small synthetic instance.

Questions for authors

See weaknesses.

2 comments

Dear Reviewer WD4m, we sincerely appreciate your feedback and the time you dedicated to reviewing our work. Below, we provide detailed answers to your questions.


W1 – Assumptions.

  • Non-degeneracy and gap. The positive instance gap is not an additional assumption: Lemma 4.1 shows that Δ⋆>0\Delta^\star>0 under Assumption 3.2 (feasibility and non-degeneracy). Non-degeneracy is used only for the logarithmic rate. The O~(T)\tilde{\mathcal O}(\sqrt T) bounds on regret and violation need only feasibility, Assumption 3.1 (realizability) and Assumption 3.3 (regression oracles): they follow from Lemma 5.1 (the LP solved by OPALP is feasible) and Props. C.2–C.3 (per-round expected cost and regret are at most ξt\xi_t, the average confidence width of the played policy). Since OPALP never uses Δ⋆\Delta^\star, it achieves O(log⁡T/Δ⋆)\mathcal O(\log T/\Delta^\star) on non-degenerate instances and O~(T)\tilde{\mathcal O}(\sqrt T) otherwise.

    Non-degeneracy holds for almost every instance (App. A, discussion of the assumptions) and is the standard condition for such rates: 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\sqrt T, and Chen et al. (2024, Thm. 2.1) show that, with knapsacks, an Ω(T)\Omega(\sqrt T) gap to the LP benchmark is unavoidable when its optimum is degenerate.

  • Oracle. Assumption 3.3 (regression oracles with confidence widths) is common in the literature on general reward and cost function classes, since it is what makes learning possible in these settings. It appears in the same form for our closest baseline, Optimistic$^3$ (Guo et al., 2025), and in closely related forms elsewhere (Chzhen et al., 2023; Guo & Liu, 2025). The improvement from T\sqrt T to log⁡T\log T is thus not obtained by strengthening the oracle.

  • Misspecification. Assumption 3.1 (realizability: the true mean reward and cost functions belong to the considered classes) is imposed throughout this literature (Slivkins et al., 2024; Han et al., 2023; Guo & Liu, 2024; Chzhen et al., 2023; Guo et al., 2025), because it is what allows these functions to be estimated efficiently with high probability. It is therefore a standard assumption, not one specific to our paper. As in these works, the misspecified case is left for future work.

W2 – Scope of the logarithmic guarantee. We agree: the logarithmic rate is claimed for soft constraints only, where prior results are at best O~(T)\tilde{\mathcal O}(\sqrt T) for both metrics. Section 6 (knapsack instantiation, Corollary 6.1) shows that OPALP still recovers the rate of Agrawal & Devanur (2016) under hard budgets.

  • Why the rate does not transfer. On rounds where OPALP's solution has the optimal active set (It=I⋆\mathcal I_t=\mathcal I^\star, the constraints tight at the optimal policy), Prop. C.5 gives zero regret because a binding constraint is saturated in its optimistic form; the true expected cost of the played policy may then exceed the constraint by up to ξt\xi_t. Under a soft constraint this is the O~(T)\tilde{\mathcal O}(\sqrt T) violation; under a hard budget it becomes early stopping. App. C.4 (proof of Corollary 6.1) makes this explicit: the regret before the stopping time τ\tau (budget exhaustion) remains O(log⁡T/Δ⋆)\mathcal O(\log T/\Delta^\star), while the regret after it is v⋆E[T−τ]≤v⋆bE[(∑s≤τψs(cs,as))+]v^\star\mathbb E[T-\tau]\le\frac{v^\star}{b}\mathbb E\big[(\sum_{s\le\tau}\psi_s(c_s,a_s))_+\big]: the cumulative overspending, converted at rate v⋆/bv^\star/b (v⋆v^\star: optimal LP value; bb: per-round budget).

  • Positioning. Existing logarithmic (or better) guarantees under hard budgets rely on additional structure, e.g., a single resource with best-arm-optimality (Sankararaman & Slivkins, 2021) or known cost functions with re-solving on the remaining budget (Wu et al., 2015; Chen et al., 2024). Our target is contextual bandits with general soft constraints (e.g., the fairness constraint (i) of Section 3, with signed costs and no budget to exhaust), for which, to our knowledge, no rate beyond T\sqrt T was known.

  • Violation metric. VT\mathcal V_T (Definition 3.1: expected cumulative cost) is the metric of Guo et al. (2025), and our bound does not rely on cancellations across rounds: Prop. C.2 bounds each round's expected cost by ξt≥0\xi_t\ge 0, and the martingale bound (16) (App. C.4) gives E[(∑tψt(ct,at))+]≤E∑tξt+2T+1/T=O~(T)\mathbb E\big[(\sum_t\psi_t(c_t,a_t))_+\big]\le\mathbb E\sum_t\xi_t+2\sqrt T+1/T=\tilde{\mathcal O}(\sqrt T).

W3 – Computation. We agree: computation is the price of the sharper rate, and this trade-off is stated explicitly in the paper (Section 2, contributions; Section 5, algorithm; Conclusion). The instance-dependent bound was missing from the literature, and it comes at a computational cost. As the reviewer notes, Lazy-OPALP (which re-solves the LP only when a confidence width has shrunk by a factor 2\sqrt2) mitigates it: over the horizon it performs a number of LP solves that is logarithmic in TT, instead of TT, with the same rates (App. D, analysis of Lazy-OPALP), whereas primal–dual methods perform a lighter update at every round. Each solve can also be made cheap: with a single global constraint of any type (budget, fairness, etc.), the LP solved at each round (Eq. (4)) has only one linear constraint coupling otherwise independent per-context simplices. This structure is known in optimization as the linear multiple-choice knapsack problem (the name describes the form of the LP, not a budget setting; signed costs are handled by a per-context shift). It is solved exactly by a greedy pass in near-linear time, and in O(∣C∣∣A∣)\mathcal O(|\mathcal C||\mathcal A|) time by the algorithms of Dyer (1984) and Zemel (1984), so no generic LP solver is needed. We have added this remark (App. D). The trade-off between computational burden and performance guarantees remains real, and the choice is left to the practitioner depending on their priorities.


We thank you once again for your valuable feedback. We hope these points address your concerns and would be grateful if the score could be reconsidered in their light. We are pleased to inform you that the paper has been updated accordingly and are happy to discuss further if needed.

Comments on the paper

2 comments

Dear Reviewer WD4m, thank you very much for your feedback. We are grateful that you recognise the theoretical contribution of our work, and in particular the instance-dependent bound.

Regarding the computational cost and its impact on practical use, we would like to stress that repeatedly re-solving a linear program is common practice, for instance in network revenue management (Chen et al., 2022a; Balseiro et al., 2024). The theoretical improvement therefore does not come at a computational cost that is unusual in this literature.


To quantify this cost, we ran new experiments (new App. F.6 of the revised PDF).

Setting. All algorithms receive the same data and use the same estimators. The per-round LP (Eq. (4)) is solved by the sorting-based greedy procedure of App. D, which is about 70 to 400 times faster than a general-purpose LP solver for 10310^3 to 10410^4 contexts (Table 4).

1. Real data. MSLR-WEB30k with the protocol of App. F.1 (real-world dataset): 85 queries with 20 candidate documents each, gradient-boosted trees for the reward, empirical means for the cost, T=105T = 10^5, 10 trials.

LP solvesTotal LP time (s)Model refits (s)Total time (s)Average rewardAverage cost
OPALP100,00046.244.893.40.523 ± 0.0170.005 ± 0.008
Lazy-OPALP443 ± 300.2143.745.00.520 ± 0.0170.005 ± 0.010

Lazy-OPALP matches the reward and cost of OPALP up to 0.003 (paired differences: 0.003 ± 0.004 and 0.000 ± 0.001) with 0.4% of its LP solves; one solve takes about 0.5 ms for both. The LP is half of the running time of OPALP, the other half being the refits of the regression model, which any method using this oracle pays. Lazy-OPALP therefore halves the total running time.

2. Larger synthetic instances. Setting of App. F.1 (synthetic data) with ∣A∣=10\lvert\mathcal A\rvert = 10 and cost means in [−0.5,1][-0.5, 1], so that the constraint binds at every size; T=2⋅105T = 2\cdot 10^5, 3 runs; cells read OPALP / Lazy-OPALP.

Contexts × actionsLP solvesTotal LP time (s)Average rewardAverage cost
20 × 10200,000 / 25361 / 0.070.897 / 0.8920.063 / 0.071
200 × 10200,000 / 39087 / 0.150.792 / 0.7830.081 / 0.082
1000 × 10200,000 / 265143 / 0.190.610 / 0.604−0.015 / −0.008

Lazy-OPALP solves the LP in fewer than 0.2% of the rounds, with an average reward about 1% below that of OPALP and an average cost within 0.01 of it (ratio of the average regrets: 1.02 to 1.5, a constant factor as allowed by App. D). At this horizon both algorithms are still learning on the larger instances, hence the lower rewards.

3. Comparison with Optimistic$^3$. Table 7 completes Table 2 with Lazy-OPALP. Optimistic$^3$ solves no LP but updates its policy and its dual variable at every round; the policy of Lazy-OPALP changes only when the LP is re-solved. As specified, each also goes through all context–action pairs at every round: Optimistic$^3$ for the expectation over contexts in its dual update (Guo et al., 2025, Section 4), Lazy-OPALP for the test of its update rule. With count-based estimates, neither needs this pass. We ran both versions of both algorithms in the same simulator, on the synthetic instances above and a larger one; cells read Optimistic$^3$ / Lazy-OPALP.

InstancePolicy updatesTotal time (s), no passTotal time (s), one pass per round
20 × 10200,000 / 2532.9 / 1.12.5 / 1.6
200 × 10200,000 / 3903.0 / 1.22.8 / 1.9
1000 × 10200,000 / 2652.9 / 1.33.9 / 2.7
10000 × 10200,000 / 743.0 / 1.426.9 / 22.4

Lazy-OPALP is the faster of the two in both versions, by a factor of at least 2 without the pass. On the largest instance (100,000 context–action pairs), it solves the LP 74 times, 0.2 s in total. On MSLR (T=105T = 10^5), Optimistic$^3$ spends 0.7 s in its updates and Lazy-OPALP 0.2 s in LP solves, both negligible next to the model refits (44 s). This comparison concerns computation only; the statistical comparison, with tuned baselines, is in App. F.1 (Figs. 1 and 2).

4. In practice. Lazy-OPALP is the version we recommend. Its policy is a stored table that changes only when the LP is re-solved: in between, a round is a table lookup, and the LP can be re-solved offline, e.g. together with the periodic retraining of the regression model. It has no step size or dual parameter to tune and needs neither a Slater constant nor Δ⋆\Delta^\star.


We hope these experiments close the gap you identified. The paper has been revised accordingly, and we would be grateful if you could reconsider your assessment in this light. If another question remains open, please point us to it.

Dear reviewer, we would be grateful if you could consider our answer to your last concern. Please let us know if any gap remains.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.