- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper provides computational efficentl algorithm for solving infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption, with provable reward regret and cumulative constraint violation, while I have concerns about its proof and also its need for the strong assumption.
Critical strengths
-
Building on the state augmentation proposed in (Sootla et al., 2022b), this paper uses the augmented state space to encode information about constraint violations, which helps for efficient algorithm design. Unlike prior work, it uses the tracked cumulative constraint violation with a new reshaped reward based on a Huber potential. Such a potential function is a new technique, and could be useful for other works.
-
Compared with other works of CMDPs under the weakly communicating assumption, this paper is more computationally efficient than Ghosh et al. (2023) while achieving the same regret rate. Compared with Yu et al. (2026), which is also computationally efficient, this work achieves an improved regret rate.
Critical weaknesses
-
The success of theoretical results for weakening the ergodicity assumption to weakly communicating CMDPs largely depends on an assumption called Existence of an optimal stationary policy, while the statement of this assumption is more than the existence of an optimal stationary policy, it further requires that the reward and constraint values are independent of the initial state. This is hard to ensure in the constrained setting, it excludes optimal stationary policies whose feasibility depends on averaging across recurrent classes with different reward–constraint tradeoffs. Moreover, the algorithm requires the span of bias functions associated with the optimal policies, mentioned only at the beginning of the algorithm.
-
In the proof of Lemma 9, inequality near line 947, it is not true that . Just take (lying on the boundary) and , then . This invalidates your proof and further affects the correctness of your theorem.
Questions for authors
-
In the theorem statement, the constraint violation bound should also include the constant factors multiplying , as is teh case for the reward regret bound. Otherwise, the constraint violation may be at a constant level.
-
The computational cost of the algorithm also depends polynomially on the number of iterations. As the authors point out, it is approximately . Even in the simple gridworld experiment with 8 states and 2 actions from the paper, running the algorithm for steps implies a substantial computational cost of level . How does this cost compare with that reported in other papers, such as Yu et al. (2026)? The authors should also include computational costs in the comparison table in Appendix A and report running times alongside the regret plots in the experiment section.
-
Can the algorithm handle larger problems or harder instances of weakly communicating MDPs? The current experimental instance is ergodic under every stationary policy.
-
Minor comment: Line 18 of the algorithm, the if condition should be on .
10 comments
[W2] In the proof of Lemma 9, inequality near line 947, it is not true that . Just take (lying on the boundary) and , then . This invalidates your proof and further affects the correctness of your theorem.
-
As the reviewer pointed out, the projection error could be larger than expected near the boundaries and . However, the safety state can never reach at the boundaries. Therefore, the raised issue does not indicate a fundamental flaw in our algorithm or analysis and can be addressed by a minor modification to the lemma statements
-
We provide further details on this modification below. Our analysis only requires the supporting lemmas (e.g., Lemmas 3, 9, 10, and 13) to hold for , rather than for all . Consequently, the only necessary modification is to restrict the statements of these lemmas from to , while keeping the original algorithm unchanged. Roughly speaking, must (i) contain and (ii) remain sufficiently far from the boundary of . Our choice is For comparison,
-
We thank the reviewer for pointing out this subtle oversight. Although the issue can be readily addressed, we acknowledge that it could cause confusion. We have therefore updated the manuscript to clarify this point, with the corresponding changes highlighted in red.
[Q1] In the theorem statement, the constraint violation bound should also include the constant factors multiplying , as is teh case for the reward regret bound. Otherwise, the constraint violation may be at a constant level.
- We thank the reviewer for pointing out this typo. Specifically, was omitted from the statement.
[Q2] The computational cost of the algorithm also depends polynomially on the number of iterations. As the authors point out, it is approximately . Even in the simple gridworld experiment with 8 states and 2 actions from the paper, running the algorithm for steps implies a substantial computational cost of level . How does this cost compare with that reported in other papers, such as Yu et al. (2026)? The authors should also include computational costs in the comparison table in Appendix A and report running times alongside the regret plots in the experiment section.
- We provide separate tables below comparing the time complexity of algorithms for weakly communicating CMDPs. We emphasize that our algorithm is the first polynomial-time algorithm to achieve bounds. Compared with the algorithm of Yu et al. (2026), our algorithm requires time, whereas theirs requires time. Here, the additional multiplicative factor of arises from the discretization of . However, the algorithm of Yu et al. (2026) fails to attain optimal guarantees, whereas ours achieves optimal bounds.
| Algorithm | Bounds | Time complexity |
|---|---|---|
| Chen et al. (2022), Algorithm 3 | ||
| Chen et al. (2022), Algorithm 4 | No known poly-time implementation | |
| Ghosh et al. (2023), Algorithm 1 | No known poly-time implementation | |
| Ghosh et al. (2023), Algorithm 2 | ||
| Yu et al. (2026), PD-LSCVI-UCB | ||
| SA-CVI-UCB, Algorithm 1 | ||
| SA-CVI-UCB, Algorithm S1 (efficient) |
denotes the cost of forming and solving an LP whose numbers of variables and constraints are . Here, denotes the feature dimension of a linear CMDP. A tabular CMDP can be represented as a linear CMDP using one-hot features with .
- Our experiments use an efficient version of Algorithm 1 (Algorithm S1). It computes only for reachable values of and discards after use. Its general memory complexity is . For the original Chain CMDP and the new Non-ergodic CMDP, there are only and reachable values of at stage , respectively. Since these counts are rather than the general bound , the time and memory complexities reduce to and , respectively.
- We also directly measure the computation cost. The table averages results over 10 runs of rounds. We sample resident set size (RSS), the physical RAM used by the process, approximately every seconds during learning and report it in mebibytes (MiB).
| CMDP | Method | Regret | Violation | Time (s) | RAM: peak/mean |
|---|---|---|---|---|---|
| Chain CMDP | SA-CVI-UCB | 359.8 | 8.0 | 27.87 | 91.83 / 91.20 |
| Chain CMDP | PD-LSCVI-UCB | 1584.0 | 88.7 | 3.20 | 82.37 / 81.63 |
| Non-ergodic CMDP | SA-CVI-UCB | 7065.4 | 63.0 | 90.00 | 116.07 / 113.45 |
| Non-ergodic CMDP | PD-LSCVI-UCB | 7379.8 | 347.0 | 4.13 | 79.44 / 78.72 |
SA-CVI-UCB achieves lower regret and violation than PD-LSCVI-UCB with additional computation and at most MiB of additional average peak RAM. Further reducing the dependence on is future work. The implementation and complexity analysis are provided in Supplement Section 1.2 and Algorithm S1, and the full measurements are provided in Supplement Sections 1.3 and 1.6, Tables S2--S3.
We thank the reviewer for the valuable comments and questions. While our paper primarily focuses on theoretical guarantees in reinforcement learning, we have conducted additional numerical experiments to address the reviewer’s empirical concerns. The supplementary material is available as additional.pdf (referred to below as the “Supplement”) in our anonymous GitHub repository: https://anonymous.4open.science/r/additional-0788/. We address the reviewer’s comments and questions below.
As the reviewer pointed out, we assume the existence of an optimal stationary policy whose gains are independent of s. However, our theoretical success does not merely rely on this assumption, as supported by the fact that prior works also adopt the same assumption. In particular, while this assumption was adopted in all prior works on weakly communicating CMDPs—Chen et al. (2022), Ghosh et al. (2023), and Yu et al. (2026)—their algorithms are either (i) suboptimal or (ii) computationally inefficient. Hence, our main contribution, namely the first computationally efficient algorithm that achieves optimal guarantees, arises from the novel design of our algorithm and its analysis.
Nevertheless, we outline an alternative result with a relaxed version of the assumption. Roughly speaking, even when the gains Jr∗(s),Jg∗(s) depend on s, if sups,s′∣Jr∗(s)−Jr∗(s′)∣,sups,s′∣Jg∗(s)−Jg∗(s′)∣≤1/T hold, then the main rates are preserved up to constant factors. The key observation is that to obtain Lemma 3 from Lemma 9, the above condition is sufficient. More technically, under this relaxed assumption, we may derive a modified statement for Lemma 9: (H−h+1)Jr∗(s)+ΦW(z)−ΦW(z−(H−h+1)Jg∗(s))−Vr~,hπ∗(s,z)≤C. Given this, the additional terms for Lemma 3 are just constant, as we have ∣HJr∗(s)−HJr∗(s′)∣=O(1),∣ΦW(z−HJg∗(s))−ΦW(z−HJg∗(s′))∣=O(Λ). This does not introduce additional dependence on T in the final guarantees. We will include further discussion of this direction in the camera-ready version.