acceptodds
Under review as a conference paper at ICLR 2027

Rate-Optimal Algorithm for Learning Adversarial Linear CMDPs

Abstract

We study adversarial linear constrained Markov decision processes (CMDPs), where both the loss and constraint functions may change adversarially over episodes. The previous state-of-the-art algorithm achieves regret and constraint violation guarantees, leaving a gap from the rate-optimal dependence on the number of episodes . Motivated by this gap, we propose a new primal-dual algorithm that achieves rate-optimal regret and constraint violation guarantees. Closing this gap is challenging because learning linear CMDPs requires controlling the covering number of the value function class, which conflicts with standard techniques used in constrained online learning, such as policy mixing. Our key idea is to develop a new drift analysis for adversarial linear CMDPs that avoids policy mixing, thereby maintaining a sufficiently simple policy structure for controlling the covering number. Moreover, our algorithm does not require Slater's condition and accommodates adversarial constraints.

Primary area:
reinforcement learning
Keywords:
constrained MDPs, adversarial CMDPs, linear function approximation, regret analysis

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_4W2cOpenReview ↗
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, K3/4K^{3/4} to K\sqrt K, 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
  1. 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...
  1. Is the clipping (Lemma 8) actually needed, given that the normalization already makes the parameters Y-independent?

  2. Can the footnote claim be proved?

  3. Can Table 1 add a feedback column, so the comparison with Yu 2026b is fair?

  4. Can the experiments test adversarial constraints and use the theoretical parameters, or at least report the ratio of tuned to theoretical values?

  5. Is there a lower bound, or at least a discussion, of the d and H dependence specific to the constrained setting?

7 comments

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 dd, HH, and KK 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]+.\text{Violation}_{\text{Hard}}(K) = \sum_{k=1}^K [V_{g^k,1}^{\pi^k}(s_1) - 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\bar Y_k in the policy update, defined as

    Yˉk=Yk⋅1V^g,1k(s1)≥b,\bar Y_k = Y_k \cdot \mathbf{1}\\{\hat V_{g,1}^k(s_1) \geq b\\},

    where YkY_k 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.

    AlgorithmMDPLossConstr.Rate∣S∣\lvert S\rvert-freeSlater-freeHard
    Roy & Das (2026)TabularAdv.Adv.K\sqrt KXOO
    Peng et al. (2026)LinearSto.Sto.K\sqrt KOXO
    Peng et al. (2026)LinearSto.Sto.K3/4K^{3/4}OOO
    Yu et al. (2026a)Lin. MixtureAdv.Sto.K\sqrt KXXX
    Yu et al. (2026b)LinearAdv.Sto.K3/4K^{3/4}OXX
    Algorithm 1LinearAdv.Adv.K\sqrt KOOX
    Algorithm 3 (new)LinearAdv.Adv.K\sqrt KOOO

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 −∑k=1KYkRk-\sum_{k=1}^{K}Y_kR_k in the drift analysis that offsets the term proportional to ∑k=1KYk2\sqrt{\sum_{k=1}^{K}Y_k^2} 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 O~(K)\widetilde O(\sqrt K) 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 g(s,a)g(s,a) and bounded or conditionally sub-Gaussian noise. In the tabular setting, standard concentration inequalities yield confidence bounds of the form

    ∣g^k(s,a)−g(s,a)∣≤O~!(1Nk(s,a)∨1),|\widehat g_k(s,a)-g(s,a)|\leq \widetilde O\\!\left(\frac{1}{\sqrt{N_k(s,a)\vee 1}}\right),

    where Nk(s,a)N_k(s,a) denotes the number of observations at (s,a)(s,a) before episode kk, with the stage index suppressed. In the linear setting, where g(s,a)=⟨ϕ(s,a),θ⟩g(s,a)=\langle\phi(s,a),\theta\rangle, regularized least squares instead yields confidence widths proportional to ∣∣ϕ(s,a)∣∣Λk−1||\phi(s,a)||_{\Lambda_k^{-1}}, where Λk\Lambda_k is the design matrix. Standard counting and elliptical potential arguments bound the cumulative confidence widths along the observed trajectories by O~(K)\widetilde O(\sqrt K), 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 ∣S∣|\mathcal S|. In the tabular setting, one can estimate Ph(s′∣s,a)P_h(s'|s,a) separately for each (s,a,s′)(s,a,s'). However, directly estimating the entire transition kernel introduces dependence on ∣S∣|\mathcal S|, which is unsuitable for large state spaces. Under the linear representation Ph(s′∣s,a)=⟨ϕ(s,a),μh(s′)⟩P_h(s'|s,a)=\langle\phi(s,a),\mu_h(s')\rangle, estimating μh(s′)\mu_h(s') separately for every s′s' would retain this dependence on ∣S∣|\mathcal S|.

    Jin et al. (2020) instead use least squares to estimate the transition kernel’s action on a value function, (PhV)(s,a)=⟨ϕ(s,a),μh(V)⟩(P_hV)(s,a)=\langle\phi(s,a),\mu_h(V)\rangle, where μh(V)=∑s′μh(s′)V(s′)\mu_h(V)=\sum_{s'}\mu_h(s')V(s') is a dd-dimensional vector. This avoids estimating the full transition kernel, but introduces a statistical dependency: the value function VV is itself constructed from the data used for estimation. Consequently, concentration for a fixed VV 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 YkY_k, ξ\xi, πˉ\bar\pi, Φ\Phi, and V^g,1k(s1)\hat V_{g,1}^k(s_1) 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 O~(K)\widetilde O(\sqrt{K}) 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 δ∈(0,1)\delta\in(0,1),

    \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.
Reviewer_BSLJOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper investigates adversarial linear CMDPs with time-varying losses and constraints under a full-information feedback model. Losses, constraints, and transition dynamics share a known feature map, and the complete loss and constraint functions are revealed after each episode. The proposed approach uses established optimization techniques, including FTRL, and claims rate-optimal guarantees.

Critical strengths
  1. The paper is well written and clearly organized.

  2. The claimed rate-optimal guarantees, if supported by a matching lower bound under the same assumptions, characterize the statistical difficulty of the full-information setting.

Critical weaknesses
  1. The full-information feedback assumption is stronger than the bandit feedback considered in prior work. It remains unclear whether the improved rates result from algorithmic and analytical advances or the stronger feedback assumption.

  2. The algorithm relies on standard techniques, including FTRL, and the proof appears to follow standard arguments. The paper should clarify its technical novelty and explain why existing approaches cannot directly achieve the stated guarantees.

Questions for authors

See Weaknesses

6 comments

We thank the reviewer for the detailed feedback. 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 dd, HH, and KK 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]+.\text{Violation}_{\text{Hard}}(K) = \sum_{k=1}^K [V_{g^k,1}^{\pi^k}(s_1) - 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, Algorithm 3, and Appendix H highlighted in red.

  • A key modification is to use the modified dual variable Yˉk\bar Y_k in the policy update, defined as

    Yˉk=Yk⋅1V^g,1k(s1)≥b,\bar Y_k = Y_k \cdot \mathbf{1}\\{\hat V_{g,1}^k(s_1) \geq b\\},

    where YkY_k 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.

    AlgorithmMDPLossConstr.Rate∣S∣\lvert S\rvert-freeSlater-freeHard
    Roy & Das (2026)TabularAdv.Adv.K\sqrt KXOO
    Peng et al. (2026)LinearSto.Sto.K\sqrt KOXO
    Peng et al. (2026)LinearSto.Sto.K3/4K^{3/4}OOO
    Yu et al. (2026a)Lin. MixtureAdv.Sto.K\sqrt KXXX
    Yu et al. (2026b)LinearAdv.Sto.K3/4K^{3/4}OXX
    Algorithm 1LinearAdv.Adv.K\sqrt KOOX
    Algorithm 3 (new)LinearAdv.Adv.K\sqrt KOOO

Response to the Reviewer’s Comments

[W1] The full-information feedback assumption is stronger than the bandit feedback considered in prior work. It remains unclear whether the improved rates result from algorithmic and analytical advances or the stronger feedback assumption.

  • We respectfully disagree with the reviewer’s assessment because it treats full-information feedback as a weakness without accounting for whether stochasticity is assumed. Our algorithm focuses on (i) adversarial constraints under full-information feedback and can be readily adapted to (ii) stochastic constraints under bandit feedback. We emphasize that (ii) is a standard setting in RL theory.

  • For clarification, it is false that our setting with adversarial constraints under full-information feedback is stronger than the Yu et al. (2026b)'s setting with stochastic constraints under bandit feedback. The key distinction is whether stochasticity is assumed. Therefore, we cannot conclude that either setting implies the other in this case.

  • Next, we explain the standard technique to handle stochastic constraints under bandit feedback. That is, estimating the mean constraint function and incorporating this estimate into the algorithm. More technically, the stochastic constraint functions can be estimated as follows. Suppose the observed feedback has a fixed conditional mean g(s,a)g(s,a) and bounded or conditionally sub-Gaussian noise. In the tabular setting, standard concentration inequalities yield confidence bounds of the form

    ∣g^k(s,a)−g(s,a)∣≤O~!(1Nk(s,a)∨1),|\widehat g_k(s,a)-g(s,a)|\leq \widetilde O\\!\left(\frac{1}{\sqrt{N_k(s,a)\vee 1}}\right),

    where Nk(s,a)N_k(s,a) denotes the number of observations at (s,a)(s,a) before episode kk, with the stage index suppressed. In the linear setting, where g(s,a)=⟨ϕ(s,a),θ⟩g(s,a)=\langle\phi(s,a),\theta\rangle, regularized least squares instead yields confidence widths proportional to ∣∣ϕ(s,a∣∣Λk−1||\phi(s,a||_{\Lambda_k^{-1}}, where Λk\Lambda_k is the design matrix. Standard counting and elliptical potential arguments bound the cumulative confidence widths along the observed trajectories by O~(K)\widetilde O(\sqrt K), 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. (2020b).

  • Moreover, we would like to compare our algorithm with that of Roy & Das (2026). Roy & Das (2026) handle adversarial constraints under bandit feedback, but their algorithm is limited to the tabular setting with a finite state space S\mathcal S. In the tabular setting, adversarial learning under bandit feedback is well studied; see, for example, Jin et al. (2020a). In contrast, we consider the more challenging linear function approximation setting. Among peer-reviewed publications, the best known computationally efficient algorithm for adversarial linear MDPs under bandit feedback achieves only a O~(K3/4)\widetilde{O}(K^{3/4}) regret bound (Liu et al., 2024).

[W2] The algorithm relies on standard techniques, including FTRL, and the proof appears to follow standard arguments. The paper should clarify its technical novelty and explain why existing approaches cannot directly achieve the stated guarantees.

Why existing approaches cannot achieve the guarantee.

  • We respectfully disagree that our guarantees follow directly from standard techniques. Although FTRL and feature contraction are established tools, our contribution is to make dual stability compatible with the uniform concentration required in linear CMDPs. Specifically, Yu et al. (2026b) use the form Yk+12−Yk2≲−ξYk+DKL(πˉ∣πk)Y_{k+1}^2-Y_k^2\lesssim-\xi Y_k+D_{\mathrm{KL}}(\bar\pi\\|\pi^k) (Eq. (1)). Without mixing, the KL term is unbounded and the violation bound becomes linear. With mixing, the policy is no longer a single softmax policy, the covering number of the value function class grows with the number of mixing steps (their Lemmas 11 and 12; ours are the special case of zero mixing steps, Appendix E), and balancing the two effects gives K3/4K^{3/4}. Appendix C shows that the natural repair, telescoping the KL terms, also fails: their analysis still needs a uniform bound on YkY_k, and the bound available without mixing, Yk=O~(K)Y_k=\widetilde O(\sqrt K), makes their mirror descent regret term O~(K)\widetilde O(K). Their analysis also requires Slater's condition.

  • A direct transfer of Yu et al. (2026d). Their analysis assumes a primal domain of bounded ℓ2\ell_2-diameter. On the policy space the corresponding quantity is the KL diameter of the simplex, which is infinite, so the natural extension (adaptive mirror descent) has a vacuous regret bound (Eq. (12) in Appendix D.2).

  • An exponential Lyapunov function under function approximation. With Φ(z)=eγz−1\Phi(z)=e^{\gamma z}-1, the a priori bound on the dual variable is exponential in KK. This bound enters the covering number, giving log⁡Nϵ≲d2log⁡CY≲d2K\log\mathcal N_\epsilon\lesssim d^2\log C_Y\lesssim d^2K (Eq. (3)) and hence vacuous concentration. This obstacle does not exist in online convex optimization or in tabular CMDPs, where no covering argument is needed.

What is new in our algorithm.

  • (i) FTRL on the policy space that adapts to the dual variables (Line 16 of Algorithm 1; Lemma 6; Appendix D.2). The regularization coefficient αk∝∑τ(1+Yτ)2\alpha_k\propto\sqrt{\sum_\tau(1+Y_\tau)^2} gives a primal regret of order log⁡∣A∣∑k(1+Yk)2\log|\mathcal A|\sqrt{\sum_k(1+Y_k)^2}, with no diameter term and no a priori bound on the dual variables. We prove this inside the epoch-based contracted value estimation, where the losses Q^fk+YkQ^gk\hat Q_f^k+Y_k\hat Q_g^k are themselves estimated.

  • (ii) A cancellation between the primal regret and the dual drift (Line 17). With Rk=108γH2+βRYk/∑τ≤kYτ2R_k=108\gamma H^2+\beta_R Y_k/\sqrt{\sum_{\tau\le k}Y_\tau^2}, the drift bound Eq. (6) contributes −∑kYkRk≈−∑kYk2-\sum_kY_kR_k\approx-\sqrt{\sum_kY_k^2}, which cancels the term ∑kYk2\sqrt{\sum_kY_k^2} on the right-hand side of Eq. (5). This yields Eq. (4), Regret(K)+Φ(ZK+1)≲K\text{Regret}(K)+\Phi(Z_{K+1})\lesssim\sqrt K, with no KL term, no Slater constant, and no mixing.

  • (iii) Breaking the circular dependence between concentration and dual stability (Line 19; Lemma 8). Uniform concentration needs a small value function class, which needs a bounded dual variable, while the bound on the dual variable is proved using concentration. We resolve this by clipping YkY_k at K8K^8, which fixes the class in advance with log⁡Nϵ≲d2log⁡K\log\mathcal N_\epsilon\lesssim d^2\log K, and then proving that on the good event the clipping is never active, Φ′(Zk)=Yk\Phi'(Z_k)=Y_k for all kk. The violation analysis therefore proceeds with the unclipped dynamics. This step has no counterpart in Yu et al. (2026b), Yu et al. (2026d), or Cassel & Rosenberg (2024).

[References]

  • Jin et al. (2020a), Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition.

  • Jin et al. (2020b), Provably efficient reinforcement learning with linear function approximation.

  • Roy & Das (2026), Optimal Regret and Hard Violation for Constrained Markov Decision Processes with Adversarial Losses and Constraints

  • Liu et al. (2024), Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback

  • Yu et al. (2026a), Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards

  • Yu et al. (2026b), Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses.

  • Yu et al. (2026d), Constrained Online Convex Optimization without Slater’s Condition.

  • Cassel & Rosenberg (2024), Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes.

  • Peng et al. (2026), Towards achieving optimal strong regret and constraint violation via computationally efficient model-free RL.

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

The authors developed a novel algorithm for adversarial linear CMDPs without Slater condition and with possibility to handle adversarial constraints. Drawing inspiration from the work of Yu et al. (2026d), which addressed the same question in the setting of online learning, the authors applied the same principle but faced multiple difficulties, which required them to apply multiple adaptations and clipping techniques. As a result, the final algorithm is the first algorithm which achieves O(K)O(\sqrt{K})-order regret bound for adversarial CMDP under soft constraint violation: hard constraint violation is left as a future work.

Critical strengths

The most critical strength of this paper is the presentation: the authors present their result in a very clean manner. Overall, the presentation flow is very smooth and it never made me wonder why it is not a trivial application of the already existing online learning paper of Yu et al. (2026d). The second critical strength is, of course, the new result, which closes an existing problem in adversarial linear CMDPs.

Critical weaknesses

The main weakness is a lack of hard-constraint satisfaction result, which make the story unfinished, especially given that the online learning paper of Yu et al. (2026d) already covers it (as well as many related linear MDP works). Although the authors have discussed the difficulty of achieving the hard satisfaction result and left it as a future work, I strongly believe it should be doable by small algorithm modification akin to Algorithm 2 in Yu et al. (2026d), or the authors should provide stronger impossibility argument.

Questions for authors
  1. What prevents an algorithm to be any-time by taking γt∝1/t\gamma_t \propto 1/\sqrt{t} instead of a fixed constant?

  2. What exactly prevents generations of prior works on tabular adversarial CMDPs (Zhu et al. (2025), Roy & Das (2026)) to the linear setting given the sigmoid argument of Cassel & Rosenberg (2024)?

4 comments

We thank the reviewer for the positive feedback on our paper and sincerely appreciate the suggestion regarding the hard constraint violation, which led to a new result. The following is our response. All the updates have been included in the revision, and highlighted in red.

Response to the Reviewer’s Comments

[W1] The main weakness is a lack of hard-constraint satisfaction result.

  • We thank the reviewer for this suggestion. As we mentioned in the original manuscript, a hard constraint violation guarantee is challenging and open in the CMDP literature; after thinking about the problem thoughtfully and carefully, we have successfully extended our algorithm to obtain hard constraint violation guarantees while preserving the same dependence on dd, HH, and KK in both the regret and violation bounds. The details can be found in Appendix H. More specifically, our new algorithm (Algorithm 3) and Theorem 28 give, with probability at least 1−δ1-\delta,

    Regret(K),ViolationHard(K)=O~(d3H4K+dH5K+d3H4)\text{Regret}(K),\\ \text{Violation}_{\text{Hard}}(K)=\widetilde O\big(\sqrt{d^3H^4K}+\sqrt{dH^5K}+d^3H^4\big)

    ViolationHard(K)=∑k=1K[Vgk,1πk(s1)−b]+.\text{Violation}_{\text{Hard}}(K)=\sum_{k=1}^K\big[V_{g^k,1}^{\pi^k}(s_1)-b\big]_+.

    This is the same bound as Theorem 4, still without Slater's condition. Since any bound on hard violation is also a bound on the cumulative violation of the original submission, the guarantee is strictly stronger.

  • How the revision resolves it. A key modification is to use the modified dual variable YkY_k by Yˉk=Yk⋅1V^g,1k(s1)≥b\bar Y_k=Y_k\cdot\mathbf 1\\{\hat V_{g,1}^k(s_1)\ge b\\} (Line 16 of Algorithm 3). Three properties make this work. First, Yk[V^g,1k(s1)−b]+=Yˉk(V^g,1k(s1)−b)Y_k[\hat V_{g,1}^k(s_1) -b]_{+} =\bar Y_k(\hat V_{g,1}^k(s_1)-b) (Eq. (32)), so the weighted positive part is recovered exactly. Second, Yˉk\bar Y_k is a nonnegative scalar that is fixed once the estimates of episode kk are computed, so the loss Q^fk+YˉkQ^gk\hat Q_f^k+\bar Y_k\hat Q_g^k passed to FTRL remains linear in the policy and the value difference lemma applies as before; this gives Eq. (30) (Lemma 30). Third, Yˉk≤Yk≤K8\bar Y_k\le Y_k\le K^8, so the value function class and the covering number bound are unchanged (Lemma 29), and ∑kYˉk2≤∑kYk2\sqrt{\sum_k\bar Y_k^2}\le\sqrt{\sum_kY_k^2}, so the cancellation against the adaptive regularizer RkR_k is preserved. The proxy dual variable accumulates only positive estimated violations, Zk+1=Zk+[V^g,1k(s1)−b]+−RkZ_{k+1}=Z_k+[\hat V_{g,1}^k(s_1)-b]_+-R_k (Line 19), which gives the drift bound Eq. (31); Lemma 32 shows that the dual clipping is again never active.

    AlgorithmMDPLossConstr.Rate∣S∣\lvert S\rvert-freeSlater-freeHard
    Roy & Das (2026)TabularAdv.Adv.K\sqrt KXOO
    Peng et al. (2026)LinearSto.Sto.K\sqrt KOXO
    Peng et al. (2026)LinearSto.Sto.K3/4K^{3/4}OOO
    Yu et al. (2026a)Lin. MixtureAdv.Sto.K\sqrt KXXX
    Yu et al. (2026b)LinearAdv.Sto.K3/4K^{3/4}OXX
    Algorithm 1LinearAdv.Adv.K\sqrt KOOX
    Algorithm 3 (new)LinearAdv.Adv.K\sqrt KOOO

[Q1] What prevents an algorithm to be any-time by taking γt∝1/t\gamma_t \propto 1/\sqrt{t} instead of a fixed constant?

  • To the best of our knowledge, we believe that it is possible to extend our algorithm to obtain anytime guarantees without relying on the doubling trick. The key modifications are (i) adopting a nonincreasing schedule γt∝1/t\gamma_t\propto 1/\sqrt{t} with suitable caps and (ii) adjusting the adaptive regularizer RtR_t, following Yu et al. (2026d). We emphasize that this extension does not rely on the doubling trick (Lattimore & Szepesv́ari (2020)). In addition, we must update confidence parameters, feature contraction parameters, and dual clipping parameters to make them independent of KK.

[Q2] What exactly prevents generations of prior works on tabular adversarial CMDPs (Zhu et al. (2025), Roy & Das (2026)) to the linear setting given the sigmoid argument of Cassel & Rosenberg (2024)?

  • The main obstruction is that the occupancy measure formulations used by Zhu et al. (2025) and Roy & Das (2026) retain dependence on ∣S∣|S|. Both works reformulate CMDPs as linear programs over occupancy measures and then apply techniques from constrained online convex optimization. However, the resulting optimization problems scale with ∣S∣|S|, and the linear MDP assumption does not automatically replace this dependence with dependence on the feature dimension dd.

  • The sigmoid technique of Cassel & Rosenberg (2024), feature contraction, addresses a different problem. It keeps the value function estimates bounded without explicit truncation, which keeps the value function class simple. It does not act on occupancy measures. Adding it to the tabular algorithms therefore leaves their dependence on ∣S∣|\mathcal S| unchanged.

  • For this reason our algorithm works in policy space. It needs only Q^\hat Q estimates, which are dd-dimensional, and the difficulty moves to controlling the covering number of the induced value function class in the presence of dual variables. That is the problem the paper solves.

[References]

  • Yu et al. (2026d), Constrained Online Convex Optimization without Slater's Condition

  • Lattimore & Szepesv́ari (2020), Bandit algorithms.

  • Peng et al. (2026), Towards achieving optimal strong regret and constraint violation via computationally efficient model-free RL.

  • Cassel & Rosenberg (2024), Warm-up free policy optimization: Improved regret in linear Markov decision processes

  • Roy & Das (2026), Optimal Regret and Hard Violation for Constrained Markov Decision Processes with Adversarial Losses and Constraints

  • Yu et al. (2026a), Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards

  • Yu et al. (2026b), Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses.

  • Zhu et al. (2025), An optimistic algorithm for online CMDPS with anytime adversarial constraints.

Reviewer_cVsJOpenReview ↗

Response to rebuttal

I would like to thank the authors for their rebuttal and for their additional contribution with the hard constraint violation, which, in my view, is very important for the coherent story in the paper. As a result, I am happy to increase my score!

Dear Reviewer cVsJ,

We sincerely thank you again for your valuable comments and positive evaluation of our work!

Thanks, Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.