acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal Regret for Constrained MDPs with Hard Stopping

Abstract

We introduce Constrained Markov Decision Processes with Hard Stopping, which generalize Contextual Bandits with Knapsacks (CBwK) and can be viewed as a hard-constraint variant of Constrained Markov Decision Processes (CMDPs). In each of episodes, the agent interacts with the environment through an -step MDP, where at each step it takes an action based on the current state and receives stochastic reward and cost. The objective is to maximize cumulative reward until the end of episodes or the cumulative cost exceeds a budget . We propose Agressive Online Gradient Descent (AOGD) and prove an upper regret bound of , where is the average budget per episode, are the numbers of states and actions. Up to our knowledge, this is the first algorithm that can achieve sublinear regret guarantee as long as the budget . We also establish a lower bound of , matching our upper bound up to a factor of , and showing our bounds are near optimal in the key parameters and . Further, we also show that with a sliding-window design, our algorithm would also have strong performance under a non-stationary setting.

Primary area:
learning theory
Keywords:
constrained MDPs with hard stopping, contextual bandits with knapsacks, near-optimal regret

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_QXk9OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies episodic constrained MDPs under a hard-stopping protocol: the learner cannot skip episodes or use a null action, and interaction terminates after the first episode whose realized cumulative cost exceeds the budget; the reward from this crossing episode is discarded. The paper proposes Aggressive Online Gradient Descent (AOGD), which combines optimistic reward estimation, pessimistic cost estimation, and an aggressive dual-variable decrease whenever the optimistic Lagrangian score becomes negative. The paper proves high-probability stationary regret bounds against a stopping-LP benchmark and relates this benchmark to a full-information hard-stopping oracle. It also provides a lower bound that nearly matches the upper bound in the key TT, bb, HH, and AA dependencies, and extends the method to a non-stationary setting using sliding-window confidence sets.

Critical strengths
  1. Meaningful and distinct problem formulation.

The hard-stopping setting without null actions, voluntary skipping, or strict feasibility assumptions is well motivated and genuinely differs from standard CMDP formulations that permit cumulative constraint violation while running for the full horizon.

  1. The aggressive dual update is technically substantive.

The central AOGD mechanism is not merely heuristic. The negative-score test yields a certificate of the form λ≥v/b\lambda\ge v/b before each internal decrement, which is used to cancel the regret contribution of internal queue updates. This is a clean and important part of the proof.

  1. Strong stationary theory.

The stationary regret analysis appears carefully constructed, especially in its handling of stopping times, attempted versus valid episodes, and budget-sensitive Bernstein cost estimation. The lower bound supports near-optimality in the main TT, bb, HH, and AA dependencies, up to a S\sqrt S gap.

Critical weaknesses
  1. The comparison with prior CMDP/CBwK results needs more careful qualification.

The paper uses a different stopping protocol and benchmark from much of the prior literature. In particular, the learner may physically overshoot the budget by up to HH in the crossing episode, after which it stops and discards that episode’s reward. This is a meaningful hard-stopping model, but it is not the same as an always-feasible, zero-violation guarantee. Likewise, Table 1 compares results with different assumptions on null actions, skipping, feasibility, violation, and comparator classes. The claims regarding budget requirements should be framed more carefully.

  1. The computational complexity of AOGD is insufficiently discussed.

The algorithm may invoke the robust planner repeatedly within one episode due to the internal decrement loop. The proof controls the number of internal updates indirectly; for example, the queue argument suggests a total dependence on TT and H/bH/b under the budget event. However, the paper does not provide an explicit total planner-invocation bound, per-episode worst-case complexity, or an implementation/runtime analysis for the robust transition optimization. This is important, especially in the small-bb regime emphasized by the paper.

  1. The non-stationary result relies on a stronger oracle assumption and a different comparator semantics.

The non-stationary algorithm assumes that the learner knows per-time local drift envelopes djr,djc,djPd_j^r,d_j^c,d_j^P, which are used directly to construct the sliding-window confidence sets. This is substantially stronger than knowing only a global variation budget, and should be made prominent. Moreover, the dynamic comparator ∑kvk∗\sum_k v_k^* is not itself evaluated under the same realized hard-stopping protocol as the learner; it is a per-episode expected-feasible benchmark. Thus the non-stationary claim should be distinguished from regret against a dynamic hard-stopping oracle.

Questions for authors
  1. Benchmark and comparison:

Can the authors more explicitly distinguish the stopping-LP benchmark, the hard-stopping oracle, and the standard full-horizon feasible-policy benchmark used in prior CMDP/CBwK work? How should the budget-threshold comparison in Table 1 be interpreted given these differences?

  1. Efficiency:

What is the computational complexity of one call to Plank(λ)\texttt{Plan}_k(\lambda), and what is an explicit bound on the total number of planner calls, including calls caused by internal decrements? Can the authors provide a polynomial-time runtime guarantee in S,A,H,T,1/bS,A,H,T,1/b?

  1. Non-stationarity assumptions:

Is knowledge of each local drift envelope djr,djc,djPd_j^r,d_j^c,d_j^P essential? Can the result be extended to the more standard setting where only an aggregate variation budget is known, or where the variation budget is unknown? Also, can the authors relate the dynamic benchmark to a true dynamic hard-stopping oracle?

  1. Interpretation of the low-budget claim:

The statement that sublinear regret is possible for B=ω~(1)B=\widetilde\omega(1) is asymptotic and appears to require fixed H,S,AH,S,A. Could the authors clarify this explicitly, especially in light of additive terms such as vH3S2A/b?vH^3S^2A/b?

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

This paper proposes Aggressive Online Gradient Descent (AOGD) as a framework for constrained MDPs with a hard stopping rule, where the MDP ends immediately after T episodes or when the cumulative cost exceeds budget B, discarding the exceeding episode’s reward. Unlike several CMDP and CBwK formulations, the model does not assume a null action, voluntary skipping, or an ordinary policy with expected per-episode cost at most b=B/T. AOGD solves this problem via optimistic Lagrange multiplier optimization, exploiting the fact that if the Lagrangian value J is negative for all options, we can lower the price and replan.

Critical strengths
  • The problem formulation is convincing. The authors make a strong case that, in many realistic scenarios, a null action or skipping is not feasible, for example, in scarce medical care distribution. The budget definition and hard cutoff rule are reasonable and natural.

  • The theoretical analysis for the central stationary regret upper bound is convincing. The algorithm uses the fact that a negative optimistic score certifies that lambda is at least v/b, allowing the analysis to charge internal multiplier decrements against the stopping-related loss. The stationary upper-bound argument follows nicely.

  • The matching lower bound (up to sqrt(S)) strengthens the regret bound of AOGD. It matches the upper bound of AOGD in T and b, establishing near-optimality.

Critical weaknesses
  • Novelty claims and related work deserve more attention. Although Brantley et al. are cited, their hard-knapsack setting and guarantees deserve explicit comparison. In particular, the paper’s blanket characterization of prior CMDP results as permitting only bounded constraint violations overlooks this part of their work. Classical Bandits with Knapsacks (Badanidiyuru et al.) already gives a regret bound of ~O(sqrt(mOPT) + OPTsqrt(m/B)) and explains how to remove null actions in stationary settings.

  • The claim for sublinear regret as long as B = ~omega(1) should be clarified. This regime concerns o(T), which could be vacuous depending on the cost settings.

  • The non-stationarity setting reintroduces strong assumptions that the stationary setting strives to remove. It requires known local drift envelopes and an ordinary feasible comparator in every episode, and replaces the stationary sign test with a queue cap. These are reasonable restrictions but should be more explicitly communicated when discussing headline results.

Questions for authors

Suggestions / Questions:

  1. There are typos: “Agressive,” “high probablity,” “Wei et al. Wei et al.”
  2. “Future work” is used in the place where “Prior work” is contextually correct.
  3. Is it possible to analyze the computational cost of the repeated planning loop?
  4. What is the exact novelty claim after comparing with Brantley et al. and Badanidiyuru et al.?
  5. Can you provide even a small-scale experiment that clearly shows AOGD's efficacy? Since this is a theoretical paper, experiments may not be expected, but even a small-scale experiment would significantly strengthen the algorithm's practicality.
1 comment
Reviewer_XessOpenReview ↗

After rebuttal

Many thanks to the authors for their detailed response. After examining all the reviews, I maintain my original score.

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

This paper addresses online learning in CMDPs and CBwK under hard stopping, where null actions are disallowed and no globally feasible policy is assumed, and proposes the AOGD algorithm. Its key technique is a nonnegative-score test with aggressive multiplier decrements: before executing a policy, it repeatedly lowers the Lagrange multiplier and replans until the optimistic reward minus priced cost becomes nonnegative, which makes the internal update cost cancel exactly against the queue potential. This weakens the budget required for sublinear regret from growing at least as fast as the square root of the episode count to growing faster than any logarithmic factor.

Critical strengths

[S1] Under hard stopping with no null action and no globally feasible policy assumption, the paper weakens the budget required for sublinear regret from growing at least as fast as the square root of the episode count to growing faster than any logarithmic factor.

Critical weaknesses

[W1] Missing computational feasibility analysis: My understanding is that, unlike Lyapunov-drift-based updates of ZZ, the proposed method needs to search for a suitable ZZ at every episode (or decision round), and this search requires NintN_\text{int} calls to Plan. This may cause the overall time complexity to be superlinear in TT. The authors should justify this trade-off through experiments in appropriate settings, showing that the computational overhead is reasonable in the regime where the method claims its advantage.

[W2] Table 1 mixes different problem paradigms, reducing the transparency of the comparison: The problem formulations of several CMDP baselines in Table 1 appear inconsistent with the CMDP formulation adopted in this paper. Triple-Q, OptPess-LP, and OptDual-CMDP aim to learn a policy whose roll-out is optimal and feasible, rather than operating under the total-budget constraint BB over the learning process considered here. These baselines are primarily concerned with constraint violation or Slater-type feasibility conditions, and they do not discuss the “Requirement for Budget BB to get sublinear regret” reported in Table 1. Moreover, the paper does not explain how these budget requirements were derived.

Questions for authors

See Weaknesses

1 comment

Thank you to the authors for the detailed rebuttal. The amortized complexity analysis and large-scale experiments have resolved my concern regarding computational feasibility ([W1]), and the math derivations have clarified the baseline comparisons ([W2]). The authors have addressed my main concerns, and I have updated my score 3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.