- Rating
- 4(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The authors analyse an episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions. They resolve a gap in regret, to , in a niche cell (full-information feedback, weak violation, and the linear MDP structure), showing that Slater-free dual technique makes mixing unnecessary.
Critical strengths
The paper addresses successfully what seems to be a true gap in the CMDP theory.
Critical weaknesses
-
the paper is written for experts in the domain. Many notions are neither introduced nor explained. Some pedagogical devices are missing entirely (see below). It is basically written for readers who already know very well at least three specific prior works: Cassel & Rosenberg 2024, Yu et al. 2026b, and Yu et al. 2026d. Many key steps are asserted with a citation rather than explained...
-
Moreover, the paper is long and technically demanding, but its depth seems moderate. The difficulty lies in bookkeeping and making the pieces compatible, not really in a new idea (or at least I was not convinced that there was a genuinely new idea...).
-
The main limitation is full-information feedback for both losses and constraints. Yu 2026b handles constraints under bandit feedback, and Table 1 has no feedback column, so the “adversarial constraints” versus “stochastic” comparison is not fair. The claim in footnote 1 that bandit feedback for stochastic constraints works “with a few modifications” is unproven.
Questions for authors
- I would have appreciated the definition/explnations in much more details of several key notions :
- a tabular warm up would have been useful to understand the difficulties
- the central “covering number issue” is never explained,
- why mixing inflates the covering number is only asserted, Slater-free mechanism is the selling point, but its intuition is missing -forward references and notation used before definition (e.g; Y_k,...)
- the main theorem is not interpreted
- Algo 1 is full of complicated unknown constants...
-
Is the clipping (Lemma 8) actually needed, given that the normalization already makes the parameters Y-independent?
-
Can the footnote claim be proved?
-
Can Table 1 add a feedback column, so the comparison with Yu 2026b is fair?
-
Can the experiments test adversarial constraints and use the theoretical parameters, or at least report the ratio of tuned to theoretical values?
-
Is there a lower bound, or at least a discussion, of the d and H dependence specific to the constrained setting?
7 comments
Response to the Reviewer’s Comments
[W1] the paper is written for experts in the domain. Many notions are neither introduced nor explained. Some pedagogical devices are missing entirely (see below). It is basically written for readers who already know very well at least three specific prior works: Cassel & Rosenberg 2024, Yu et al. 2026b, and Yu et al. 2026d. Many key steps are asserted with a citation rather than explained.
- We agree that the paper should be more self-contained and accessible to readers unfamiliar with the cited works. We will introduce key notions—including feature contraction, covering numbers, and the Lyapunov potential—with definitions and intuition before using them. We will also add a proof roadmap explaining the main obstacle, the purpose of each algorithmic component, and how the intermediate bounds yield the final guarantees.
[W2] Moreover, the paper is long and technically demanding, but its depth seems moderate. The difficulty lies in bookkeeping and making the pieces compatible, not really in a new idea (or at least I was not convinced that there was a genuinely new idea...).
- Our paper is lengthy and technical in part because we provide complete proofs with detailed justifications in the appendix to ensure rigor. We would nevertheless like to reiterate our central technique: a mechanism that controls errors depending on the dual variables while preserving the small covering number required for uniform concentration in linear CMDPs. Yu et al. (2026b) use policy mixing to control KL divergence terms, but mixing complicates the policy class and creates a tradeoff that limits their guarantees. Our adaptive dual regularizer generates a negative contribution in the drift analysis that offsets the term proportional to in the primal regret bound. Adaptive FTRL enables this argument without the unbounded KL diameter term arising in a direct adaptive mirror descent analysis, and the dual clipping mechanism ensures a small covering number. Together, these properties eliminate the need for policy mixing while preserving uniform concentration, enabling regret and cumulative constraint violation under our full-information model without Slater’s condition.
[W3] The main limitation is full-information feedback for both losses and constraints. Yu 2026b handles constraints under bandit feedback, and Table 1 has no feedback column, so the “adversarial constraints” versus “stochastic” comparison is not fair. The claim in footnote 1 that bandit feedback for stochastic constraints works “with a few modifications” is unproven.
-
While we agree with the reviewer that the distinction between full-information and bandit feedback should be made explicit, our reason for omitting a separate treatment of stochastic bandit feedback was that estimating stationary reward or constraint functions using confidence bounds is a standard technique in RL theory; see, for example, Jaksch et al. (2010) and Jin et al. (2020).
-
In contrast, this stationary mean estimation argument does not apply to adversarial rewards or constraints, whose values may change arbitrarily across episodes. Thus, the linear structure of our constraint functions suggests a standard route to adapting our algorithm to the stochastic constraints under bandit feedback considered by Yu et al. (2026b). Extending their approach to adversarial constraints, however, does not follow from the same statistical estimation argument.
-
More technically, we explain how the stationary reward or constraint functions are estimated. Suppose the observed feedback has a fixed conditional mean and bounded or conditionally sub-Gaussian noise. In the tabular setting, standard concentration inequalities yield confidence bounds of the form
where denotes the number of observations at before episode , with the stage index suppressed. In the linear setting, where , regularized least squares instead yields confidence widths proportional to , where is the design matrix. Standard counting and elliptical potential arguments bound the cumulative confidence widths along the observed trajectories by , treating the horizon and problem dimensions as fixed. These confidence bounds underpin the principle of optimism in the face of uncertainty. See Jin et al. (2020).
[Q1] I would have appreciated the definition/explnations in much more details of several key notions.
-
(Difficulty: Tabular vs. Linear) A central difficulty in learning linear MDPs and CMDPs is estimating the unknown transition dynamics without dependence on the state space size . In the tabular setting, one can estimate separately for each . However, directly estimating the entire transition kernel introduces dependence on , which is unsuitable for large state spaces. Under the linear representation , estimating separately for every would retain this dependence on .
Jin et al. (2020) instead use least squares to estimate the transition kernel’s action on a value function, , where is a -dimensional vector. This avoids estimating the full transition kernel, but introduces a statistical dependency: the value function is itself constructed from the data used for estimation. Consequently, concentration for a fixed is insufficient; the analysis establishes concentration uniformly over the class of possible value estimates. A covering number argument controls the complexity of this class and enables such a uniform bound, explaining why keeping the value function class compact is essential.
-
(Covering number issue): We previously explained the motivation for the covering number argument in linear MDPs and CMDPs. We now provide additional intuition about the covering number. Specifically, it describes how many value functions are sufficient to cover the value function class with balls centered at those selected value functions. In the linear setting, value function estimates can be expressed in terms of vectors and matrices, allowing us to analyze their covering number. In the concentration argument, we apply a union bound over this cover, so the covering number must be small to keep the confidence bounds small.
-
(Why mixing inflates the covering number) We previously explained that the covering number can be analyzed by expressing value functions in terms of vectors and matrices. However, policy mixing increases the number of vectors and matrices needed to represent a value function estimate. This is because the additive structure introduced by mixing complicates the policy class, resulting in more complex value function estimates. That is why we must avoid policy mixing to obtain rate-optimal guarantees.
-
(Why being Slater-free is a selling point) We would like to address this from both (i) practical and (ii) theoretical aspects. (i) Practically, our algorithm does not require the Slater constant as an input, whereas the algorithm of Ghosh et al. (2022) does. This removes the need to know or estimate the strict feasibility margin, which may be difficult in an unknown environment. (ii) Theoretically, our regret and constraint violation bounds have no inverse dependence on the Slater constant. Slater-dependent guarantees can become arbitrarily large as this constant approaches zero. Our guarantees remain applicable even when no strictly feasible policy exists, provided that the feasible policy set is nonempty.
-
(Notation used before definition) Section 3 is intended to motivate our approach and explain the main technical challenges. We therefore introduce , , , , and by describing their roles, without presenting all mathematical details at that stage. We will add brief definitions and explanations at first use to make Section 3 more self-contained.
-
(Interpretation of the main theorem) The interpretation of the main theorem (Theorem 4) is that our algorithm achieves the first rate-optimal guarantees for both regret and constraint violation in the adversarial linear CMDP setting. Here, rate-optimal means achieving bounds.
-
(Constants used in Algorithm 1) The choices of all algorithmic parameters are specified in the Input line of Algorithm 1 in the original manuscript. For convenience, we restate them below: for a failure probability ,
\beta_p &= 187dH\sqrt{\log(2HK/\delta)},\\\\ \beta_\phi &= 4\beta_p\log K,\\\\ \beta_Q &= 2H,\\\\ \beta_R &= 2H^2(\log|A|+20)\sqrt{dH\log(2K)},\\\\ \gamma &= \min\left\\{\frac{1}{36H\sqrt K},\frac{1}{6\beta_R}\right\\}. \end{aligned}$$ Here, $\beta_p$ determines the confidence bonus, $\beta_\phi$ controls feature contraction, $\beta_Q$ bounds the $Q$-function estimates on the good event, $\beta_R$ scales the adaptive dual regularizer, and $\gamma$ determines the growth rate of the Lyapunov function $\Phi(z)=e^{\gamma z}-1$. The dual clipping threshold is $K^8$. We will explain these roles more explicitly in the algorithm description.
We thank the reviewer for the detailed feedback and positive evaluation of our paper. Before addressing the reviewer’s comments, we would like to introduce an extension of our algorithm. That is, motivated by Reviewer cVsJ’s comment, we have successfully extended our algorithm to provide hard constraint-violation guarantees, an important objective in the CMDP literature.
Important Additional Contribution: Hard Constraint Violation Guarantees
We have extended our algorithm to obtain hard constraint violation guarantees while preserving the same dependence on d, H, and K in both the regret and violation bounds. Here, hard constraint violation is defined below. Note that it does not allow cancellation across episodes and is therefore a stronger metric than the soft constraint violation introduced in the original submission.
ViolationHard(K)=∑k=1K[Vgk,1πk(s1)−b]+.
Given the importance of hard constraint violation guarantees in the CMDP literature, we have incorporated this extension into the revised manuscript, with changes to the main text, Table 1, and Appendix H highlighted in red.
A key modification is to use the modified dual variable Yˉk in the policy update, defined as
Yˉk=Yk⋅1V^g,1k(s1)≥b,
where Yk is the original dual variable. This modification enables us to establish the hard-constraint analogue of Eq. (5). We refer the reviewer to Appendix H of the revised manuscript for the full algorithm and analysis. We provide an updated comparison table for clarification.