- 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 , , , and dependencies, and extends the method to a non-stationary setting using sliding-window confidence sets.
Critical strengths
- 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.
- 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 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.
- 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 , , , and dependencies, up to a gap.
Critical weaknesses
- 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 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.
- 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 and 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- regime emphasized by the paper.
- 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 , 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 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
- 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?
- Efficiency:
What is the computational complexity of one call to , 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 ?
- Non-stationarity assumptions:
Is knowledge of each local drift envelope 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?
- Interpretation of the low-budget claim:
The statement that sublinear regret is possible for is asymptotic and appears to require fixed . Could the authors clarify this explicitly, especially in light of additive terms such as
After rebuttal
Many thanks to the authors for their detailed response. After examining all the reviews, I maintain my original score.