acceptodds
Under review as a conference paper at ICLR 2027

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

Abstract

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions . We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves regret and cumulative constraint violation with high probability in the tabular setting. The dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in .

Primary area:
reinforcement learning
Keywords:
regret, violation, CMDPs

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_Kez5OpenReview ↗
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 O(T)\mathcal O(\sqrt T) reward regret and cumulative constraint violation, while I have concerns about its proof and also its need for the strong assumption.

Critical strengths
  1. 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.

  2. 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
  1. 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.

  2. In the proof of Lemma 9, inequality near line 947, it is not true that ∣ΠZ(z′−g)−(z′−g)∣≤δ/2|\Pi_{\mathcal{Z}}(z' - g) - (z' - g)|\le \delta/2. Just take z′=2Tz' = 2T (lying on the boundary) and g=−1g=-1, then ∣ΠZ(z′−g)−(z′−g)∣=1>δ/2|\Pi_{\mathcal{Z}}(z' - g) - (z' - g)| = 1> \delta/2. This invalidates your proof and further affects the correctness of your theorem.

Questions for authors
  1. In the theorem statement, the constraint violation bound should also include the constant factors multiplying T\sqrt{T}, as is teh case for the reward regret bound. Otherwise, the constraint violation may be at a constant level.

  2. The computational cost of the algorithm also depends polynomially on the number of iterations. As the authors point out, it is approximately S2AT2.5S^2AT^{2.5}. Even in the simple gridworld experiment with 8 states and 2 actions from the paper, running the algorithm for 3×1043 \times 10^4 steps implies a substantial computational cost of level 101010^{10}. 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.

  3. Can the algorithm handle larger problems or harder instances of weakly communicating MDPs? The current experimental instance is ergodic under every stationary policy.

  4. Minor comment: Line 18 of the algorithm, the if condition should be on Nk+1N_{k+1}.

10 comments

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.

[W1-1] 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.

  • As the reviewer pointed out, we assume the existence of an optimal stationary policy whose gains are independent of ss. 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)J_r^*(s), J_g^*(s) depend on ss, if sup⁡s,s′∣Jr∗(s)−Jr∗(s′)∣,sup⁡s,s′∣Jg∗(s)−Jg∗(s′)∣≤1/T\sup_{s,s'}|J_r^*(s) - J_r^*(s')|, \sup_{s,s'}|J_g^*(s) - J_g^*(s')|\leq 1/\sqrt{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.\left|(H-h+1)J_r^*(s) + \Phi_W(z) - \Phi_W\left(z-(H-h+1)J_g^*(s)\right) - V_{\tilde r,h}^{\pi^*}(s,z)\right| \leq 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(Λ).|HJ_r^*(s) - HJ_r^*(s')|=O(1), |\Phi_W(z-HJ_g^*(s)) - \Phi_W(z-HJ_g^*(s'))| = O(\Lambda). This does not introduce additional dependence on TT in the final guarantees. We will include further discussion of this direction in the camera-ready version.

[W1-2] ... Moreover, the algorithm requires the span of bias functions associated with the optimal policies, mentioned only at the beginning of the algorithm.

  • We believe that it is possible to remove the requirement of prior knowledge of the bias spans by adapting techniques from Boone and Zhang (2024), who study regret minimization in unconstrained weakly communicating tabular average-reward MDPs without requiring the optimal bias span as an input. Intuitively, their approach constructs confidence regions for differences between state biases from observed trajectories and incorporates these regions into optimistic value iteration. This allows the algorithm to use bias information learned during interaction. Adapting this idea to our state-augmented CMDP formulation is a promising direction, although additional analysis would be needed to preserve both regret and cumulative constraint-violation guarantees. We will include further discussion of this direction in the camera-ready version.

[W2] In the proof of Lemma 9, inequality near line 947, it is not true that ∣ΠZ(z′−g)−(z′−g)∣≤δ/2|\Pi_{\mathcal Z}(z'-g) - (z'-g)|\leq \delta/2. Just take z′=2Tz'=2T (lying on the boundary) and g=−1g=-1, then ∣ΠZ(z′−g)−(z′−g)∣=1>δ/2|\Pi_{\mathcal Z}(z'-g) - (z'-g)|=1 > \delta/2. 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 2T2T and −2T-2T. However, the safety state zz 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 zhkz_h^k, rather than for all z∈Zz\in\mathcal Z. Consequently, the only necessary modification is to restrict the statements of these lemmas from ∀z∈Z\forall z\in\mathcal Z to ∀z∈Zh\forall z\in\mathcal Z_h, while keeping the original algorithm unchanged. Roughly speaking, Zh⊆Z\mathcal Z_h \subseteq \mathcal Z must (i) contain zhkz_h^k and (ii) remain sufficiently far from the boundary of Z\mathcal Z. Our choice is Zh=Δn:n∈Z,∣Δn∣≤(1+Δ/2)(T−H+h−1).\mathcal Z_h = \\{\Delta n: n\in\mathbb Z, |\Delta n| \leq (1+\Delta/2)(T-H+h-1)\\}. For comparison, z∈Z̸  ⟹  ∣ΠZ(z−g)−(z−g)∣≤Δ/2,z \in \mathcal Z \not\implies |\Pi_{\mathcal Z}(z-g)-(z-g)| \leq \Delta/2, z∈Zh  ⟹  ∣ΠZ(z−g)−(z−g)∣≤Δ/2.z \in \mathcal Z_h \implies |\Pi_{\mathcal Z}(z-g)-(z-g)| \leq \Delta/2.

  • 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 T\sqrt{T}, 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, +1+1 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 S2AT2.5S^2AT^{2.5}. Even in the simple gridworld experiment with 8 states and 2 actions from the paper, running the algorithm for 3×1043\times 10^4 steps implies a substantial computational cost of level 101010^{10}. 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 O~(T)\widetilde O(\sqrt{T}) bounds. Compared with the algorithm of Yu et al. (2026), our algorithm requires O(T2.5)O(T^{2.5}) time, whereas theirs requires O(T2)O(T^2) time. Here, the additional multiplicative factor of T\sqrt{T} arises from the discretization of zz. However, the algorithm of Yu et al. (2026) fails to attain optimal guarantees, whereas ours achieves optimal bounds.
AlgorithmBoundsTime complexity
Chen et al. (2022), Algorithm 3O~(T2/3)\widetilde O(T^{2/3})O!((S2A)1/3T2/3)×LPtime!((S2A)2/3T1/3)O\\!((S^2A)^{1/3}T^{2/3}) \times \mathrm{LP}_{time}\\!((S^2A)^{2/3}T^{1/3})
Chen et al. (2022), Algorithm 4O~(T)\widetilde O(\sqrt T)No known poly-time implementation
Ghosh et al. (2023), Algorithm 1O~(T)\widetilde O(\sqrt T)No known poly-time implementation
Ghosh et al. (2023), Algorithm 2O~(T3/4)\widetilde O(T^{3/4})O(Ad2T2)O(Ad^2T^2)
Yu et al. (2026), PD-LSCVI-UCBO~(T2/3)\widetilde O(T^{2/3})O(d2SAT2)O(d^2SAT^2)
SA-CVI-UCB, Algorithm 1O~(T)\widetilde O(\sqrt T)O(S2AT5/2)O(S^2AT^{5/2})
SA-CVI-UCB, Algorithm S1 (efficient)O~(T)\color{black}\widetilde O(\sqrt T)O~(S2AT2)\color{black}\widetilde O(S^2AT^2)

LPtime(N)\mathrm{LP}_{time}(N) denotes the cost of forming and solving an LP whose numbers of variables and constraints are O(N)O(N). Here, dd denotes the feature dimension of a linear CMDP. A tabular CMDP can be represented as a linear CMDP using one-hot features with d=SAd=SA.

  • Our experiments use an efficient version of Algorithm 1 (Algorithm S1). It computes Q,VQ,V only for reachable values of zz and discards VV after use. Its general memory complexity is O(SAT3/2+S2AT)O(SAT^{3/2}+S^2AT). For the original Chain CMDP and the new Non-ergodic CMDP, there are only hh and 2h−12h-1 reachable values of zz at stage hh, respectively. Since these counts are O(h)O(h) rather than the general bound O(h/Δ)O(h/\Delta), the time and memory complexities reduce to O~(S2AT3/2)\widetilde O(S^2AT^{3/2}) and O(SAT+S2AT)O(SAT+S^2A\sqrt T), respectively.
  • We also directly measure the computation cost. The table averages results over 10 runs of T=64,000T=64{,}000 rounds. We sample resident set size (RSS), the physical RAM used by the process, approximately every 0.010.01 seconds during learning and report it in mebibytes (MiB).
CMDPMethodRegretViolationTime (s)RAM: peak/mean
Chain CMDPSA-CVI-UCB359.88.027.8791.83 / 91.20
Chain CMDPPD-LSCVI-UCB1584.088.73.2082.37 / 81.63
Non-ergodic CMDPSA-CVI-UCB7065.463.090.00116.07 / 113.45
Non-ergodic CMDPPD-LSCVI-UCB7379.8347.04.1379.44 / 78.72

SA-CVI-UCB achieves lower regret and violation than PD-LSCVI-UCB with additional computation and at most 3737 MiB of additional average peak RAM. Further reducing the dependence on TT 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.

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

The paper concerns tabular infinite-horizon average-reward CMDPs under weakly communicating assumption. The authors propose the first "computationally efficient" method with nearly optimal bound on the regret and cumulative constraint violation in terms of the number of iterations, namely, O~(T)\tilde{O}(\sqrt{T}). By computationally efficient they apparently mean that the algorithm has arithmetic complexity polynomial in S,A,TS,A,T. The approach is based on augmenting the state with an auxiliary variable that tracks cumulative constraint violation and adjusting the reward using Huber potential difference. The authors then conduct a three step analysis of the algorithm to prove the desired bounds. Afterwards, they present empirical results on a synthetic problem and comparison with existing algorithms.

Critical strengths

Nearly optimal dependence on T under fairly weak assumptions is an important theoretical contribution. The paper is clearly written and well-organized.

Critical weaknesses

The experiments don't illustrate the theory well. First, the generality of the weakly communicating assumption is one of the key features of the theory, yet the chosen environment doesn't demonstrate this generality. If I understand correctly, the considered MDP is ergodic under every stationary randomized policy. Second, computational efficiency is presented as one of the main strengths of the proposed approach, but the experimental results don't illustrate this point as they only plot the regret and violation as functions of the number of interactions. Third, experiments consider only one environment and a single value of TT. Finally, the experiments use hyperparameters different from those suggested by the theory. I suggest including both a theoretical and a practical version of the algorithm in the experiments, or at least adding a short justification of the current choice of hyperparameters.

Questions for authors
  1. Is the Huber potential essential or just one convenient choice? Could you please characterize the properties of a potential sufficient for your analysis?
  2. I suggest defining the term "computationally efficient" in the beginning of the paper to avoid ambiguity.
  3. Please consider adding the following works to the literature review: Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs (2026) by Wei et al., Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs (2026) by Naskar and Aggarwal.
  4. The expression "added state" in the abstract might be a little bit misleading. Consider replacing it with, e.g., "auxiliary state variable".
  5. I am concerned about the projection error bound in line 947. While it indeed holds for an unbounded grid, doesn't restricting it to [−2T,2T][-2T,2T] invalidate the inequality? How does this issue affect the statements that rely on Lemma 9?

If the authors properly address the remarks regarding the experiments (see Weaknesses section) and Question #5, I am open to increasing my rating.

4 comments

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.

[W1] First, the generality of the weakly communicating assumption is one of the key features of the theory, yet the chosen environment doesn't demonstrate this generality. If I understand correctly, the considered MDP is ergodic under every stationary randomized policy.

  • We defined a Non-ergodic CMDP and conducted additional experiments on it and the original Chain CMDP. The new CMDP is weakly communicating but neither communicating nor ergodic. We evaluated both CMDPs at 4 values of TT, from 8,0008{,}000 to 64,00064{,}000 rounds. The table shows final regret / violation, averaged over 10 runs at T=64,000T=64{,}000.
CMDPSA-CVI-UCBPD-LSCVI-UCB
Chain CMDP359.8 / 8.01584.0 / 88.7
Non-ergodic CMDP7065.4 / 63.07379.8 / 347.0

SA-CVI-UCB has lower regret and violation than PD-LSCVI-UCB in both CMDPs at T=64,000T=64{,}000. The environment description is provided in Supplement Section 1.1 and Figure S1, and the comparisons across TT are provided in Supplement Section 1.6, Figure S4 and Tables S2--S3.

[W2] Second, computational efficiency is presented as one of the main strengths of the proposed approach, but the experimental results don't illustrate this point as they only plot the regret and violation as functions of the number of interactions.

  • We agree with the reviewer that the additional computation time and memory required by state augmentation are important practical concerns. We first point out that by “computationally efficient,” we mean polynomial time and memory in S,A,TS,A,T. For weakly communicating CMDPs, Chen et al. (2022) obtain O~(T2/3)\widetilde O(T^{2/3}) bounds with a polynomial-time algorithm, while their algorithm with O~(T)\widetilde O(\sqrt T) bounds has no known polynomial-time implementation. Our contribution is to achieve O~(T)\widetilde O(\sqrt T) regret and violation in polynomial time. We will clarify this definition at the beginning of the paper.
  • For comparison, we measured wall-clock time and memory usage for every algorithm. We sample resident set size (RSS), the physical RAM used by the process, approximately every 0.010.01 seconds during learning and report it in mebibytes (MiB). The table shows results at T=64,000T=64{,}000, averaged over 10 runs.
CMDPMethodRegretViolationTime (s)RAM: peak/mean
Chain CMDPSA-CVI-UCB359.88.027.8791.83 / 91.20
Chain CMDPPD-LSCVI-UCB1584.088.73.2082.37 / 81.63
Chain CMDPChen (2022), Alg. 3-2623.16729.9780.5492.11 / 90.94
Non-ergodic CMDPSA-CVI-UCB7065.463.090.00116.07 / 113.45
Non-ergodic CMDPPD-LSCVI-UCB7379.8347.04.1379.44 / 78.72
Non-ergodic CMDPChen (2022), Alg. 3-14635.458605.02764.07109.37 / 102.49

SA-CVI-UCB is approximately 2828--3131 times faster than Algorithm 3 of Chen et al. (2022), with lower constraint violation in both CMDPs. Compared with PD-LSCVI-UCB, it has lower regret and violation but higher runtime and at most 3737 MiB of additional average peak RAM. The measurement protocol is provided in Supplement Section 1.3, and the full results are provided in Supplement Section 1.6 and Tables S2--S3.

  • We also developed an efficient implementation of SA-CVI-UCB (Algorithm S1). It computes Q,VQ,V only for reachable values of zz and discards VV after use. With H=Θ(T)H=\Theta(\sqrt T) and Δ=Θ(T−1/2)\Delta=\Theta(T^{-1/2}), it reduces the general time bound from O(S2AT5/2)O(S^2AT^{5/2}) to O~(S2AT2)\widetilde O(S^2AT^2). The memory bound changes from O(SAT2+S2A)O(SAT^2+S^2A) to O(SAT3/2+S2AT)O(SAT^{3/2}+S^2AT). Its description and complexity analysis are provided in Supplement Section 1.2. The memory and time complexity tables are provided in Reviewer 1, Q3 and Reviewer 4, Q2, respectively.

[W3] Third, experiments consider only one environment and a single value of TT.

  • We defined a Non-ergodic CMDP and conducted additional experiments on it and the original Chain CMDP. The new CMDP is weakly communicating but neither communicating nor ergodic. Its description is provided in Supplement Section 1.1 and Figure S1. We also evaluated both CMDPs for T=8,000T=8{,}000, 16,00016{,}000, 32,00032{,}000, and 64,00064{,}000 rounds. Each experiment is repeated 10 times. The table gives SA-CVI-UCB's average final regret / violation.
TTChain CMDPNon-ergodic CMDP
8,000189.6 / 4.2967.9 / 21.2
16,000243.3 / 5.01880.6 / 30.8
32,000302.5 / 6.13627.3 / 44.2
64,000359.8 / 8.07065.4 / 63.0

These results and comparisons with all baselines, together with time and RAM measurements, are provided in Supplement Section 1.6, Figure S4 and Tables S2--S3.

[W4] Finally, the experiments use hyperparameters different from those suggested by the theory. I suggest including both a theoretical and a practical version of the algorithm in the experiments, or at least adding a short justification of the current choice of hyperparameters.

  • As the reviewer noted, the original experiments used a practical adaptive choice of CkC_k. We compared SA-CVI-UCB's theoretical and practical parameter settings in Supplement Section 1.7, Figure S5 and Table S4. The table shows SA-CVI-UCB's final regret / violation, averaged over 10 runs at T=32,000T=32{,}000.
CMDPTheoretical settingPractical setting
Chain CMDP1525.5 / 8060.4302.5 / 6.1
Non-ergodic CMDP4109.6 / 67.23627.3 / 44.2

The practical setting gives lower regret and violation in both CMDPs. The theoretical setting keeps the clipping constant CC and bonus coefficient β\beta fixed, while the practical setting updates CkC_k and βk\beta_k at each episode. To examine whether the large theoretical CC explains the performance gap, we also reduced it to C/10C/10 and C/100C/100 and recomputed the corresponding β\beta. Reducing CC to C/100C/100 lowers Chain CMDP violation by approximately 9999\\%. This experiment is provided in Supplement Section 1.7, Figure S6 and Table S5.

  • We further note that the hyperparameter choices specified in Algorithm 1 are primarily motivated by the theoretical analysis and are not necessarily optimal from an empirical standpoint. Accordingly, consistent with the experimental practices in prior studies of both unconstrained and constrained RL (Zhou et al., 2021; Ghosh et al., 2024), we adopt empirically tuned hyperparameters in our numerical evaluations while leaving the core algorithmic framework unchanged.

[Q1] Is the Huber potential essential or just one convenient choice? Could you please characterize the properties of a potential sufficient for your analysis?

  • Our Huber potential is a sufficient choice rather than an essential one. We believe that other (nonnegative, nondecreasing) potential functions satisfying properties similar to those stated in Lemma 1 may also lead to rate-optimal guarantees. In particular, the key to potential design is to balance the regularity conditions: the potential must satisfy sufficiently strong regularity conditions for the first two statements of Lemma 1, while retaining sufficient growth to satisfy the third statement. Indeed, those three statements are used throughout the analysis.

  • We provide further details on this point. The required properties of potential functions are (i) global Lipschitzness and (ii) global smoothness. In contrast, exponential potentials satisfy neither (i) nor (ii), while quadratic potentials do not satisfy (i). The Huber potential satisfies both regularity conditions, leading to the first and second statements of Lemma 1. However, these regularity conditions alone are insufficient; the potential must also satisfy the linear lower bound in the third statement of Lemma 1.

[Q2] I suggest defining the term "computationally efficient" in the beginning of the paper to avoid ambiguity.

  • We thank the reviewer for this suggestion and will clarify the meaning of "computationally efficient" at the beginning of our paper. Specifically, by "computationally efficient," we mean that the time and memory complexities are polynomial in S,A,TS, A, T, and that the algorithm does not involve intractable optimization steps. For comparison, previous state-of-the-art algorithms in our setting are either (i) statistically suboptimal or (ii) computationally inefficient, as they require solving nonconvex optimization problems, for which no efficient solution method is known (Chen et al., 2022).

[Q3] Please consider adding the following works to the literature review: Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs (2026) by Wei et al., Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs (2026) by Naskar and Aggarwal.

  • We thank the reviewer for pointing out these missing references and will include them in our literature review.

[Q4] The expression "added state" in the abstract might be a little bit misleading. Consider replacing it with, e.g., "auxiliary state variable".

  • We thank the reviewer for this suggestion and will replace "added state" with "auxiliary state variable" in the abstract.

[Q5] I am concerned about the projection error bound in line 947. While it indeed holds for an unbounded grid, doesn't restricting it to [−2T,2T][-2T,2T] invalidate the inequality? How does this issue affect the statements that rely on Lemma 9?

  • As the reviewer pointed out, the projection error could be larger than expected near the boundaries 2T2T and −2T-2T. However, the safety state zz 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 zhkz_h^k, rather than for all z∈Zz\in\mathcal Z. Consequently, the only necessary modification is to restrict the statements of these lemmas from ∀z∈Z\forall z\in\mathcal Z to ∀z∈Zh\forall z\in\mathcal Z_h, while keeping the original algorithm unchanged. Roughly speaking, Zh⊆Z\mathcal Z_h \subseteq \mathcal Z must (i) contain zhkz_h^k and (ii) remain sufficiently far from the boundary of Z\mathcal Z. Our choice is Zh=Δn:n∈Z,∣Δn∣≤(1+Δ/2)(T−H+h−1).\mathcal Z_h = \\{\Delta n: n\in\mathbb Z, |\Delta n| \leq (1+\Delta/2)(T-H+h-1)\\}. For comparison, z∈Z̸  ⟹  ∣ΠZ(z−g)−(z−g)∣≤Δ/2,z \in \mathcal Z \not\implies |\Pi_{\mathcal Z}(z-g)-(z-g)| \leq \Delta/2, z∈Zh  ⟹  ∣ΠZ(z−g)−(z−g)∣≤Δ/2.z \in \mathcal Z_h \implies |\Pi_{\mathcal Z}(z-g)-(z-g)| \leq \Delta/2.

  • 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.

[References]

  • Chen et al. (2022), Learning infinite-horizon average-reward markov decision process with constraints.

I thank the authors for the response. The projection error issue was resolved. Regarding the experiments, the authors addressed my requests for a non-ergodic example, several values of TT, and the comparison of theoretical and practical parameters. The extension in Appendix G is also interesting.

Since my main concerns were resolved, I'm planning to raise the score by one point, although the experiments are still limited.

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

The paper studies learning in weakly communicating average reward constrained Markov decision processes. Its central idea is to augment the state with cumulative constraint violation and reshape rewards using differences of a Huber potential. Because the added coordinate evolves deterministically, the learner only estimates the original transition kernel. Combining this construction with optimistic value iteration, clipping, and strong duality gives claimed regret and constraint violation bounds of order O~(T)\widetilde O(\sqrt T), with polynomial computation. The algorithm requires known reward and constraint functions, a known Slater constant, and bias span information. Experiments compare a practical variant against existing methods on a small tabular environment.

Critical strengths
  1. The paper addresses a meaningful computational gap. Chen et al. (2022) obtain efficient bounds of order T2/3T^{2/3}, while their square root guarantees require computationally inefficient planning. The proposed augmentation provides a different route around this obstacle: the Huber potential keeps reward adjustments bounded, and the known dynamics of the added coordinate prevent the statistical estimation problem from growing with the augmented state space.

  2. The proof strategy connects several useful ingredients. The comparator value span bound motivates clipping, the potential differences telescope across episode boundaries, and strong duality provides a lower bound on regret that allows constraint violation to be controlled even when regret is negative. This combination explains how the method handles the constrained problem while retaining the desired dependence on TT.

Critical weaknesses
  1. The violation bound in Theorem 2 omits a necessary contribution independent of the bias spans. Appendix C.5 retains a 1/γ1/\gamma contribution in its bound on CC, together with the term γΛW/2=T\gamma\Lambda W/2=\sqrt T, but these contributions disappear from the final expression.

    Consider a single state with two actions satisfying $ (r(a_0),g(a_0))=(0,1), (r(a_1),g(a_1))=(1,-1). $ The optimal feasible stationary policy selects each action with probability 1/21/2. Both its reward and constraint bias spans are zero. We also have γ=1\gamma=1 and λ∗=1/2\lambda^*=1/2. The composite reward is constant, so its optimal bias span is zero as well. Consequently, the displayed violation bound has a zero right hand side.

    However, applying Algorithm 1 with T=9T=9, H=K=W=3H=K=W=3, and δ=0.05\delta=0.05 gives respectively two, zero, and three selections of a1a_1 across the three episodes, resulting in violation 11. The stated guarantee therefore fails in an admissible case. Retaining an additive 11 alongside the bias span terms appears to repair the bound while preserving the main O~(T)\widetilde O(\sqrt T) rate.

  2. The experiments provide limited evidence about the procedure covered by the theorem and its practical computational cost. Appendix E uses the adaptive clipping parameter Ck=sp⁡(vr∗)+ΦW′(z1k)sp⁡(vg∗)C_k=\operatorname{sp}(v_r^{\ast})+\Phi_W'(z_1^k)\operatorname{sp}(v_g^{\ast}), which omits the remainder terms required by the theoretical comparator span bound. The analysis does not establish the same guarantee for this variant. Evaluation also uses only one environment with eight states and two actions. Since the prescribed augmented grid contains approximately 23 million safety values at the experimental interaction budget, implementation details and computation measurements are particularly important for assessing practical efficiency.

Questions for authors
  1. Can the authors retain the constant contributions in Appendix C.5 and state a corrected violation bound that also covers cases where all relevant bias spans vanish? This correction appears sufficient to resolve the identified concern without changing the main rate.

  2. How does the empirical adaptive clipping parameter compare with the parameter prescribed by the theorem in terms of regret, violation, and computation? Please also explain how the augmented grid is represented and report computation time and memory usage.

1 comment

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.

[W1, Q1] The violation bound in Theorem 2 omits a necessary contribution independent of the bias spans. ... Can the authors retain the constant contributions in Appendix C.5 and state a corrected violation bound that also covers cases where all relevant bias spans vanish? This correction appears sufficient to resolve the identified concern without changing the main rate.

  • We thank the reviewer for pointing out this typo. Specifically, +1+1 was omitted from the statement.

[W2] The experiments provide limited evidence about the procedure covered by the theorem and its practical computational cost.

  • As the reviewer noted, the original experiments used a practical adaptive choice of CkC_k. We compared SA-CVI-UCB's theoretical and practical parameter settings in Supplement Section 1.7, Figure S5 and Table S4. To examine whether the large theoretical clipping constant CC explains the performance gap, we also reduced it to C/10C/10 and C/100C/100 and recomputed the corresponding bonus coefficient β\beta. These results are provided in Supplement Section 1.7, Figure S6 and Table S5.
  • We also defined a Non-ergodic CMDP and conducted additional experiments on it and the original Chain CMDP. The new CMDP is weakly communicating but neither communicating nor ergodic. Its description is provided in Supplement Section 1.1 and Figure S1.
  • Finally, we measured each algorithm's runtime and memory usage and described an efficient implementation to reduce the cost of state augmentation. These measurements are provided in Supplement Section 1.6 and Tables S2--S3, and the implementation is provided in Supplement Section 1.2 and Algorithm S1. We explain the augmented grid and memory usage under Q2 below.

[Q2] How does the empirical adaptive clipping parameter compare with the parameter prescribed by the theorem in terms of regret, violation, and computation? Please also explain how the augmented grid is represented and report computation time and memory usage.

  • For the parameter comparison, the practical setting gives lower regret and violation on both CMDPs. The theoretical setting keeps the clipping constant CC and bonus coefficient β\beta fixed. The practical setting updates CkC_k and βk\beta_k at each episode. The table compares the complete theoretical and practical parameter settings at T=32,000T=32{,}000, averaged over 10 runs. We sample resident set size (RSS), the physical RAM used by the process, approximately every 0.010.01 seconds during learning and report it in mebibytes (MiB).
CMDPSettingRegretViolationTime (s)RAM: peak/mean
Chain CMDPPractical302.56.110.9486.79 / 86.35
Chain CMDPTheoretical1525.58060.410.6686.91 / 86.47
Non-ergodic CMDPPractical3627.344.230.9698.22 / 96.57
Non-ergodic CMDPTheoretical4109.667.231.1598.46 / 96.88

Average runtime differs by less than 33\\% and average peak RSS by less than 11\\% between the settings on each CMDP. Thus, the practical setting improves regret and violation with similar computation costs. This comparison is provided in Supplement Section 1.7, Figure S5 and Table S4.

Reducing the theoretical clipping constant CC to C/100C/100, with β\beta recomputed, also reduces Chain CMDP violation by approximately 9999\\%. This experiment is provided in Supplement Section 1.7, Figure S6 and Table S5.

  • For the augmented grid, both settings use the efficient version of SA-CVI-UCB (Algorithm S1). At each stage, we store only grid points reachable from the episode's initial zz, using the integer z/Δz/\Delta to represent each point. We keep Qk,hQ_{k,h} for every stage hh to select actions and discard Vk,h+1V_{k,h+1} after computing Vk,hV_{k,h}. Thus, we do not store Q,VQ,V for every point of the augmented grid. The implementation details are provided in Supplement Section 1.2 and Algorithm S1. The measurement protocol is in Supplement Section 1.3, and results for every algorithm are in Supplement Section 1.6 and Tables S2--S3.
Reviewer_sjhBOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

∙\bullet The paper studies infinite-horizon average-reward CMDPs under the weakly communicating assumption.

∙\bullet The authors propose SA-CVI-UCB, a state-augmented optimistic value-iteration algorithm. The main idea is to add cumulative constraint violation as an extra state variable.

∙\bullet Instead of using a primal-dual multiplier that changes over episodes, the paper defines a fixed reshaped reward using differences of a Huber potential.

∙\bullet This reward shaping gives a telescoping relation between the augmented reward, the original reward, and the terminal potential, which is then used to control both regret and constraint violation.

∙\bullet The algorithm combines this augmentation with finite-horizon approximation, UCB optimism, and value clipping.

∙\bullet The main theoretical result is a high-probability O~(sqrt(T)) bound for both regret and cumulative constraint violation in tabular weakly communicating average-reward CMDPs.

∙\bullet The validation is mainly theoretical. The experiments evaluate the method on one modified chain CMDP and compare it with several prior baselines. The proposed method appears to have lower regret and violation in this environment, with an additional small sensitivity study on the bonus scale.

Critical strengths

∙\bullet The main technical idea of tracking cumulative constraint violation in the state and using a Huber-potential reward shaping is clean and useful. It avoids the changing-reward issue of primal-dual methods, while preserving a telescoping structure that connects the augmented problem back to the original CMDP.

∙\bullet The claimed O~(sqrt(T)) high-probability bounds for both regret and constraint violation are important in this setting. Prior efficient algorithms for weakly communicating CMDPs seem to have worse dependence on T, so this is a meaningful theoretical improvement.

Critical weaknesses

∙\bullet The role of weak communication is not very transparent. The algorithm itself does not seem specifically tailored to weakly communicating MDPs. From my reading, weak communication mainly enters the analysis through strong duality, bounded bias/span quantities, and the conversion between finite-horizon augmented values and average-reward benchmarks. I think the paper should make this much clearer and explain why weaker or different assumptions would not be enough.

∙\bullet Experimental evidence is limited. The experiments are based mostly on a single modified chain CMDP. This feels too limited to support the empirical claims, especially since the paper is motivated by weakly communicating CMDPs. I also do not see an experiment that clearly isolates the weakly communicating but non-ergodic/non-communicating case.

∙\bullet Although the paper compares with PD-LSCVI-UCB, I would like to see a clearer and more detailed experimental comparison against primal-dual methods, since avoiding changing dual multipliers is one of the main motivations of the paper. In particular, it would be useful to isolate whether the empirical gains come from the state augmentation-Huber potential design or from other implementation choices such as clipping, bonus scaling, or hyperparameter tuning.

Questions for authors

∙\bullet I would suggest the authors clearly identify the exact lemmas or proof steps where the weakly communicating assumption is essential? Is it correct that the assumption is used mainly for strong duality, bias/span control, and finite-horizon-to-average-reward conversion?

∙\bullet Does the practical implementation require knowing gamma, sp(vr∗)sp(v_r^*), and sp(vg∗)sp(v_g^*)? In the experiments, these quantities seem to be computed using LPs. Am I correct to understand this? If so, how should the algorithm be run when they are unknown?

∙\bullet The augmented state space can be quite large, roughly scaling with the discretization grid over cumulative violation. Can the authors provide memory usage for the experiments?

∙\bullet I would encourage to include experiments on CMDPs that are explicitly weakly communicating but not communicating or ergodic, for example with transient states or multiple recurrent classes under different policies.

∙\bullet Please add ablations for the main components: the Huber potential, value clipping, state augmentation, and the discretization choice. My suggestions are to compare the full method with variants using a quadratic/linear potential, no clipping, different values of WW and Δ\Delta, or a primal-dual multiplier in place of the augmented safety state. These experiments would make it clearer which design choices are responsible for the improvement in regret and violation, and whether the Huber potential and clipping are practically important rather than only proof devices.

3 comments

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.

[W1, Q1] The role of weak communication is not very transparent. The algorithm itself does not seem specifically tailored to weakly communicating MDPs. From my reading, weak communication mainly enters the analysis through strong duality, bounded bias/span quantities, and the conversion between finite-horizon augmented values and average-reward benchmarks. I think the paper should make this much clearer and explain why weaker or different assumptions would not be enough. ... I would suggest the authors clearly identify the exact lemmas or proof steps where the weakly communicating assumption is essential? Is it correct that the assumption is used mainly for strong duality, bias/span control, and finite-horizon-to-average-reward conversion?

  • Specifically, weak communication is used to establish strong duality (Lemma 5) and bias/span control for the unconstrained MDP with reward r+λ∗gr+\lambda^*g (Appendix B). Together with Slater’s condition, these results establish the regret lower bound (Lemma 7) used to derive the violation guarantee. Separately, Assumption 2 supports bias/span control for the optimal policy π∗\pi^* in the original CMDP. This underpins both the span bound used for clipping and optimism and the finite-horizon-to-average-reward conversion in Lemma 3.

[W2, Q4] Experimental evidence is limited. The experiments are based mostly on a single modified chain CMDP. This feels too limited to support the empirical claims, especially since the paper is motivated by weakly communicating CMDPs. I also do not see an experiment that clearly isolates the weakly communicating but non-ergodic/non-communicating case. ... I would encourage to include experiments on CMDPs that are explicitly weakly communicating but not communicating or ergodic, for example with transient states or multiple recurrent classes under different policies.

  • We defined a Non-ergodic CMDP and conducted additional experiments on it and the original Chain CMDP. The new CMDP is weakly communicating but neither communicating nor ergodic. We evaluated both CMDPs at 4 values of TT, from 8,0008{,}000 to 64,00064{,}000 rounds. The table shows final regret / violation, averaged over 10 runs at T=64,000T=64{,}000.
CMDPSA-CVI-UCBPD-LSCVI-UCB
Chain CMDP359.8 / 8.01584.0 / 88.7
Non-ergodic CMDP7065.4 / 63.07379.8 / 347.0
  • SA-CVI-UCB has lower regret and violation than PD-LSCVI-UCB in both CMDPs at T=64,000T=64{,}000. The environment description is provided in Supplement Section 1.1 and Figure S1, and the comparisons across TT are provided in Supplement Section 1.6, Figure S4 and Tables S2--S3.

[W3, Q5] Although the paper compares with PD-LSCVI-UCB, I would like to see a clearer and more detailed experimental comparison against primal-dual methods, since avoiding changing dual multipliers is one of the main motivations of the paper. In particular, it would be useful to isolate whether the empirical gains come from the state augmentation-Huber potential design or from other implementation choices such as clipping, bonus scaling, or hyperparameter tuning. ... Please add ablations for the main components: the Huber potential, value clipping, state augmentation, and the discretization choice. My suggestions are to compare the full method with variants using a quadratic/linear potential, no clipping, different values of WW and Δ\Delta, or a primal-dual multiplier in place of the augmented safety state. These experiments would make it clearer which design choices are responsible for the improvement in regret and violation, and whether the Huber potential and clipping are practically important rather than only proof devices.

  • We implemented the primal-dual version in Algorithm S2 (Supplement Section 1.8.1) by replacing the reward with r~k(s,a)=r(s,a)+z1k(g(s,a)−b)\tilde r_k(s,a)=r(s,a)+z_1^k(g(s,a)-b) and the safety-state update with z←Π[0,2/γ](z−(g(s,a)−b))z\leftarrow\Pi_{[0,2/\gamma]}(z-(g(s,a)-b)). It removes the zz coordinate from Q,VQ,V and uses the same horizon and clipping/bonus rules. The table shows final regret / violation, averaged over 10 runs at T=32,000T=32{,}000.
CMDPSA-CVI-UCBPrimal-dual variant
Chain CMDP302.5 / 6.11165.3 / 6759.7
Non-ergodic CMDP3627.3 / 44.28622.8 / 0.0

SA-CVI-UCB gives lower regret in both CMDPs and lower violation in the Chain CMDP. In the Non-ergodic CMDP, the primal-dual variant trades lower violation for higher regret. This suggests the effectiveness of our method over primal-dual approaches. This comparison is provided in Supplement Section 1.8.1 and Figure S7.

  • We also conducted ablation studies of the potential (Huber, quadratic, and linear), value clipping, WW, and Δ\Delta. Huber and quadratic potentials perform similarly, and removing clipping has little effect in these examples. These results are provided in Supplement Sections 1.8.2--1.8.4 and Figures S8--S11.

[Q2] Does the practical implementation require knowing gamma, sp(vr⋆)sp(v_r^\star), and sp(vg⋆)sp(v_g^\star)? In the experiments, these quantities seem to be computed using LPs. Am I correct to understand this? If so, how should the algorithm be run when they are unknown?

  • As the reviewer noted, our current theoretical guarantees require a known positive Slater margin and known bias-span bounds. In our experiments, we use LPs to obtain the optimal policy and Slater margin, then compute the bias spans of the optimal policy.

  • For unknown bias spans, a promising approach is to adapt the techniques of Boone and Zhang (2024), who study unconstrained weakly communicating tabular average-reward MDPs without requiring the optimal bias span as an input. Their approach constructs confidence regions for bias differences from observed trajectories and incorporates them into optimistic value iteration. Extending this approach to our state-augmented CMDP formulation would require additional analysis to preserve both regret and cumulative constraint-violation guarantees.

  • Regarding γ\gamma, the exact maximal Slater margin is unnecessary: any known positive lower bound γ‾\underline{\gamma} suffices, with Λ=2/γ‾\Lambda=2/\underline{\gamma} and the corresponding clipping parameter CC and exploration bonus β\beta. If no such bound is available, a practical heuristic is to tune Λ\Lambda over a geometric grid using validation runs, recomputing CC and β\beta for each candidate and fixing the selected value throughout the subsequent learning run. However, empirical tuning does not certify the required condition Λ>λ∗\Lambda > \lambda^*, so our current theoretical guarantees do not cover this procedure.

[Q3] The augmented state space can be quite large, roughly scaling with the discretization grid over cumulative violation. Can the authors provide memory usage for the experiments?

  • We measure memory usage as resident set size (RSS), the physical RAM used by the process, in mebibytes (MiB). The table shows each run's peak / time-averaged RSS, averaged over 10 runs at T=64,000T=64{,}000.
MethodChain CMDP: peak/meanNon-ergodic CMDP: peak/mean
SA-CVI-UCB91.83 / 91.20116.07 / 113.45
PD-LSCVI-UCB82.37 / 81.6379.44 / 78.72
Chen (2022)92.11 / 90.94109.37 / 102.49
Ghosh (2023)82.33 / 81.4079.38 / 78.48
Random82.24 / 81.2279.36 / 78.23

The increase in average peak RAM over PD-LSCVI-UCB is 9.59.5 MiB in the Chain CMDP and 36.636.6 MiB in the Non-ergodic CMDP. The measurement protocol is provided in Supplement Section 1.3, and results for all 4 values of TT are provided in Supplement Section 1.6, Tables S2--S3.

  • Additionally, we provide a table comparing the memory complexities of recent algorithms. Since Algorithm 3 of Chen et al. (2022) solves an LP in every episode, it requires memory for solving an LP with N=(S2A)2/3T1/3+S2AN=(S^2A)^{2/3}T^{1/3}+S^2A constraints and variables, denoted by LPmem(N)\mathrm{LP}_{\mathrm{mem}}(N). The general linear implementations of Ghosh et al. (2023) and Yu et al. (2026) require storing previous information t′=1,…,tt'=1,\ldots,t. Here, dd denotes the feature dimension of a linear CMDP. A tabular CMDP can be represented as a linear CMDP using one-hot features with d=SAd=SA.
AlgorithmMemory complexity
Chen et al. (2022), Algorithm 3LPmem(N)+O(S2A+T)\mathrm{LP}_{\mathrm{mem}}(N)+O(S^2A+T)
Ghosh et al. (2023), Algorithm 2O(dT+d2)O(dT+d^2)
Yu et al. (2026), PD-LSCVI-UCBO(dT+d2)O(dT+d^2)
Ours, Algorithm 1O(SAT2+S2A)O(SAT^2+S^2A)
Ours, Algorithm S1 (efficient)O(SAT3/2+S2AT)O(SAT^{3/2}+S^2AT)

Algorithm 1 stores Qk,h(s,a,z)Q_{k,h}(s,a,z) for every z∈Zz\in\mathcal Z and stage hh. Our experiments use its efficient version (Algorithm S1), which stores QQ only for reachable values of zz and discards VV after use. In the two CMDPs, its memory complexity is O(SAT+S2AT)O(SAT+S^2A\sqrt T). This implementation and its complexity analysis are provided in Supplement Section 1.2 and Algorithm S1.

Comments on the paper

1 comment

General comment

We thank all the reviewers for their valuable comments. We summarize the substantial revisions made during the discussion period below and welcome further questions and comments.

Extensions

Based on the reviewers' suggestions, we have added Appendix G with rigorous proofs of two extensions. Theorem 23 removes Assumption 2 while retaining known bounds on the bias spans, and Theorem 24 additionally removes that prior knowledge. Both extensions retain weak communication and Slater's condition (Assumption 1), with a known Slater constant γ\gamma.

ResultsT\sqrt{T} dependenceComputationally efficientw/o Assumption 2w/o known spans
Theorem 2OOXX
Theorem 23 (new)OOOX
Theorem 24 (new)OOOO

The T\sqrt{T} dependence is up to logarithmic factors. Theorem 23 requires known bounds on the bias spans of two stationary unichain comparator policies. These policies and the required bounds are specified in Appendix G. Theorem 24 includes an additive term exponential in the unknown bias spans, which is independent of TT for a fixed CMDP. Thus, this extension retains the optimal dependence in TT, but does not claim optimal dependence on the spans. We leave reducing the dependence on the spans as future work. Here, computational efficiency means polynomial time and memory in S,A,TS,A,T.

Corrected proofs regarding the projection error

The projection error due to ΠZ\Pi_{\mathcal Z} can exceed Δ/2\Delta/2 near the grid boundary, which was not accounted for in the original lemma statements. However, the safety states encountered by the algorithm remain sufficiently far from the boundary, so this situation does not occur along its trajectories. We therefore replace ∀z∈Z\forall z\in\mathcal Z with ∀z∈Zh\forall z\in\mathcal Z_h in the relevant lemma statements, where Zh⊆Z\mathcal Z_h\subseteq\mathcal Z contains the safety states at stage hh and ensures that the projection error is at most Δ/2\Delta/2. The algorithm remains unchanged.

Additional numerical simulations

We have conducted additional numerical experiments covering:

  • The original 8-state Chain CMDP and a new, larger 15-state Non-ergodic CMDP that is weakly communicating but neither communicating nor ergodic.
  • Four values of TT: 8,0008{,}000, 16,00016{,}000, 32,00032{,}000, and 64,00064{,}000.
  • Comparisons of actual running time and memory usage.
  • Comparisons of potentials: Huber, quadratic, and exponential.
  • State augmentation compared with a primal-dual variant.
  • Theoretical and practical parameter settings for SA-CVI-UCB, including sensitivity to the clipping parameter and the corresponding optimism parameter.
  • Ablations of value clipping and sensitivity to the parameter WW of the Huber potential and discretization gap Δ\Delta.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.