Dependence of the bounds on $\epsilon_{\mathrm{bias}}$ and $\epsilon_{\mathrm{app}}$: Thank you for pointing this out. We will mention the dependence of the convergence rates on $\epsilon_{\mathrm{bias}}$ and $\epsilon_{\mathrm{app}}$ in the main text as well as in Table 1 in the revised manuscript.

On good feature maps: We would like to emphasize that the concept of linear function approximation is not only a common assumption for the actor-critic algorithms, but it is also central to the rich literature of linear MDPs [1]. Although there is no consensus, to the best of our knowledge, on how to build feature maps for a generic task, several task-dependent features have been reported in the literature [2], [3] that perform well in experiments. Hence, it is quite practical to assume that the learner has access to a good feature map.

On nonlinear value function approximation: The benefit of linear critic approximation is that both the NPG and the critic updates can be described as stochastic linear recursions (SLRs). This allows us to utilize Theorem B.1, which is crucial in obtaining the optimal convergence rates. Extending these results to non-linear critic approximation is extremely challenging since the convergence analysis of SLRs can no longer be applied. Very recently, [4] has provided a regret analysis with non-linear critic approximation in the unconstrained discounted reward setup. However, they introduce a data-drop technique and do not use the MLMC-based estimation, which is central to our work. Whether their approach can be extended to the constrained average reward scenario is currently an open question.

Relation to [31] and (Patel et al.): We agree that there are some similarities between our algorithm and that proposed by the cited papers. For example, MLMC-based estimation and linear critic approximation are central to all of these papers. Despite these apparent similarities, there are some crucial differences. For example, both of the cited papers analyze unconstrained setups, liberating them from the nuances of dual projection and its parameter optimization. Secondly, unlike our paper, [31] merely guarantees convergence to a first-order stationary point. Although (Patel et al.) guarantees global convergence, their established rate $\tilde{\mathcal{O}}(T^{-1/4})$ is nowhere near the theoretical lower bound $\Omega(T^{-1/2})$. Thirdly, the set of assumptions used in [31] is different than ours. For example, Assumption 4.2(3) used in [31] is not needed in our analysis. Finally, the analysis of stochastic linear recursions (SLRs), which is central in our paper (Theorem B.1), is present in neither of the cited papers. Hence, although we are not the first to remove dependence on the knowledge of $\tau_{\mathrm{mix}}$ using MLMC (though we are the first to do so in the CMDP setup), our analysis is not an adopted version of that presented in either of the cited papers. We will include a summary of the above comparison in the revised manuscript.

Typos: Thank you for pointing out the typos. We will correct those in the revised manuscript.

References:

[1] ''Provably efficient reinforcement learning with linear function approximation'', COLT 2020.

[2] ''Making Linear MDPs Practical via Contrastive Representation Learning'', ICML 2022.

[3] ''Achieving sub-linear regret in infinite horizon average reward constrained MDP with linear function approximation'', ICLR 2023.

[4] ''Order-optimal global convergence for actor-critic with general policy and neural critic parametrization'', UAI 2025.

Technical novelty: Our primary novelty lies in achieving an optimal-order convergence rate for average reward Constrained Markov Decision Processes (CMDPs) with general policy parameterization, which was previously unresolved in the literature.

We indeed leverage the natural actor-critic framework in conjunction with the MLMC-based estimation technique, which recently has obtained an order-optimal convergence rate in the unconstrained setup [1]. However, directly applying these techniques to constrained MDPs by integrating a primal-dual approach does not yield the same optimal convergence rate. The key challenge arises from introducing the dual variable, which significantly complicates the convergence analysis. Specifically, as highlighted in Eq. (79,82) in our paper, the dual learning rate $\beta$ appears in both the numerator and denominator of the convergence bounds. Therefore, merely following the unconstrained setting by choosing $\beta$ inversely proportional to $T$ fails to replicate the optimal convergence rate achieved in the unconstrained case.

This fundamental challenge has also been observed in the literature. For example, [2] addresses the unconstrained average reward RL and achieves a convergence rate of $\tilde{O}(T^{-1/4})$, while [3] deals with the constrained counterpart, achieving a slower rate of $\tilde{O}(T^{-1/5})$.

Our work addresses these critical challenges through a sharper and more refined analytical approach. We specifically modify both the primal and dual learning rate to scale inversely with the square root of $T$, a significant departure from the constant primal learning rate used in the unconstrained analyses ([1] and [2]). Additionally, we introduce a refined error bound for the Lagrangian (last expression on Page 30) and strategically set the inner-loop complexity to be nearly logarithmic in $T$. These innovative technical modifications enable us to overcome the identified challenges and achieve the first optimal-order convergence rate for the average reward constrained RL setting.

Relation to lower bound: As mentioned in Table 1 in the paper, the theoretical lower bound on the global convergence rate is $\Omega(T^{-1/2})$ where $T$ indicates the horizon length. Theorems 4.9 and 4.10 in our paper establish convergence rates of $\tilde{\mathcal{O}}(T^{-1/2})$ and $\tilde{\mathcal{O}}(T^{-1/2+\epsilon})$ for arbitrarily small $\epsilon$. Therefore, not only do our results vastly improve upon the state-of-the-art convergence rates, but they nearly match the theoretical lower bound as well.

On constraint violation: Our algorithm can achieve a small average constraint violation, provided that the horizon length $T$ is sufficiently large and the errors due to policy and critic approximations are negligible. That being said, we agree with the reviewer that in some safety-critical applications, even a small constraint violation is undesirable. To force the constraint violation to zero, we can resort to a standard ``trick'' commonly used in constrained RL literature. The main idea is to consider a stringent constraint of the form $J_c^{\pi}\geq \eta>0$ in the algorithm, instead of the formulated constraint $J_c^{\pi}\geq 0$. Now, the hyperparameter $\eta$ can be appropriately chosen so that our desired constraint violation is forced to zero. Please see section H.5 of [4] for a detailed exposition. Similar ideas are also discussed in [5]. Hence, one can extend a small constraint violation result to a zero one with some additional assumption, and we leave it as future work.

On general policies: The class of policies considered in the paper is called ``general'' because it contains various commonly used policy classes such as tabular, softmax, log-linear, neural, etc., as special cases. This terminology is common across the RL literature [6], [7]. We believe that renaming the general policy class as policies with smooth and bounded gradients would de-emphasize the generic applicability of our results. Therefore, instead of renaming it in the title, we will mention the smoothness and boundedness properties of the policy gradients in the abstract and introduction of the revised paper.

References:

[1] "A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach", ICML 2025.

[2] "Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes", AAAI 2024.

[3] "Learning general parameterized policies for infinite horizon average reward constrained MDPs via primal-dual policy gradient algorithm", NeurIPS 2024.

[4] ''Achieving sub-linear regret in infinite horizon average reward constrained MDP with linear function approximation'', ICLR 2023.

[5] ''Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach'', AAAI 2022.

[6] ''Sample-Efficient Constrained Reinforcement Learning with General Parameterization'', NeurIPS 2024.

[7] ''A novel framework for policy mirror descent with general parameterization and linear convergence'', NeurIPS 2023.

Thank you for your letting us know your concerns and for the detailed reading of the manuscript.

On lower bound: We are unaware of any theoretical lower bound that directly corresponds to our general parameterized setting and captures the dependence of various parameters, such as $G_1$. We have reported a lower bound in Table 1 that dictates the dependence on $T$. This result emerges from analyzing a tabular setup. Since tabular policies are special cases of general parameterized policies, the stated result also serves as a lower bound for our case (as far as $T$ is concerned).

On constraint violation: The intuition behind the definition of constraint violation, as stated in our paper, is as follows. Suppose that an algorithm generates a sequence of policy parameters $\\{\theta_1, \cdots, \theta_K\\}$ during the $*training phase*$. Now, if one of these policy parameters is chosen at random and deployed in the $*evaluation phase*$, what is the constraint violation one is expected to see? Note that each policy parameter has an equal chance $1/K$ of being selected. Moreover, if the parameter $\theta_i$ is chosen, then the expected constraint violation is $-\mathbf{E}[J_c(\theta_i)]$. Therefore, the expected constraint violation during the evaluation phase is:

$-\dfrac{1}{K}\sum_{k=1}^{K}\mathbf{E}[J_c(\theta_k)]$

The above definition of constraint violation is also used in many prior works [1, 2]. In contrast, if one is interested in the constraint violation during the training phase itself, then the expression of expected constraint violation should be of the following form, as stated by the reviewer.

$-\dfrac{1}{K}\sum_{k=1}^K \mathbf{E}[c(s_k, a_k)]$

In summary, the two definitions of expected constraint violations have different purposes and application scenarios. In some RL applications, a reliable simulator is available for training. In such cases, the algorithm's performance during training is not of much importance, although the performance of the deployed policy during the evaluation phase is. However, if a simulator is unavailable or the available simulators are not reliable, then in-training performance guarantee takes centre stage. We hope this clarifies the confusion regarding the definition of constraint violation.

We will expand on the technical novelty, and mention the different definitions of constraint violation in the Table to clarify the difference.

References:

[1] ''Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach'', AAAI 2022.

[2] ''Sample-efficient constrained reinforcement learning with general parameterization'', NeurIPS 2024.

We are unaware of any theoretical lower bound that directly corresponds to our general parameterized setting and captures the dependence of various parameters

I am sorry for the confusion. What I wrote is that because of the loose lower bound, it is difficult to evaluate how significant the result is.

On constraint violation

I am not fully convinced by the discussion. Firstly, the argument that other papers are using this criteria does not justify its use. Secondly, the safety during the training is important, and even if one only cares the final policy, the considered objective function is inappropriate. Indeed, picking up and using a policy as suggested in the response can result in violating a constraint with probability 0.5 in the worst case.

Therefore, I keep my score of 4, which is weak accept.

We thank the reviewer for the constructive review. Please find our responses below.

Algorithmic novelty: Our primary novelty lies in achieving an optimal-order convergence rate for average reward Constrained Markov Decision Processes (CMDPs) with general policy parameterization, which was previously unresolved in the literature.

We indeed leverage the natural actor-critic framework in conjunction with the MLMC-based estimation technique, which recently has obtained an order-optimal convergence rate in the unconstrained setup [1]. However, directly applying these techniques to constrained MDPs by integrating a primal-dual approach does not yield the same optimal convergence rate. The key challenge arises from introducing the dual variable, which significantly complicates the convergence analysis. Specifically, as highlighted in Eq. (79,82) in our paper, the dual learning rate $\beta$ appears in both the numerator and denominator of the convergence bounds. Therefore, merely following the unconstrained setting by choosing $\beta$ inversely proportional to $T$ fails to replicate the optimal convergence rate achieved in the unconstrained case.

This fundamental challenge has also been observed in the literature. For example, [2] addresses the unconstrained average reward RL and achieves a convergence rate of $\tilde{O}(T^{-1/4})$, while [3] deals with the constrained counterpart, achieving a slower rate of $\tilde{O}(T^{-1/5})$.

Our work addresses these critical challenges through a sharper and more refined analytical approach. We specifically modify both the primal and dual learning rate to scale inversely with the square root of $T$, a significant departure from the constant primal learning rate used in the unconstrained analyses ([1] and [2]). Additionally, we introduce a refined error bound for the Lagrangian (last expression on Page 30) and strategically set the inner-loop complexity to be nearly logarithmic in $T$. These innovative technical modifications enable us to overcome the identified challenges and achieve the first optimal-order convergence rate for the average reward constrained RL setting.

Knowledge of Slater's constant: We would like to point out that almost all primal-dual algorithms in the literature, to the best of our knowledge, assume access to Slater's constant $\delta$ (see, e.g., [3], [4]) to define the dual projection operator. Nevertheless, we agree with the reviewer's concern that the value of $\delta$ might be unknown for most practical scenarios. In such a case, $\delta$ can be taken as a hyperparameter of the algorithm, which needs to be fine-tuned during the training period. This is in line with many RL algorithms in the literature that also require fine-tuning of several unknown hyperparameters, such as the Lipschitz constant, mixing time, or hitting time for effective implementation [2]. In other words, the issue of fine-tuning is not unique to $\delta$, but common across the RL literature. Since $\delta$ is such that $J_c^{\pi}\geq \delta$ for $*some*$ policy $\pi$, a coarse estimate of $\delta$ can be obtained by computing an estimate of $J_c^{\pi}$ for some arbitrarily chosen policy $\pi$.

Scaling of reward and cost functions: The reward function is typically assumed to be bounded, which allows us to choose $[0, 1]$ as its range without loss of generality. Note that the constraint in our optimization problem is of the form $J_c^{\pi}\geq 0$. Therefore, if the range of the cost function is chosen as either $[0, 1]$ or $[-1, 0]$, then the constraint would either be obeyed by all policies or no policies at all. Both of these cases would lead to trivial solutions. To avoid this problem, we have chosen the range of the cost function to be $[-1, 1]$.

Typos: Thank you for pointing out the typos. We will correct those in the revised manuscript.

References:

[1] "A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach." ICML 2025.

[2] "Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes." AAAI 2024.

[3] "Learning general parameterized policies for infinite horizon average reward constrained MDPs via primal-dual policy gradient algorithm." NeurIPS 2024.

[4] "Sample-efficient constrained reinforcement learning with general parameterization." NeurIPS 2024.

On prohibitive horizon length: We agree that, for small $\epsilon$ and unknown $\tau_{\mathrm{mix}}$, the length of the required horizon length $T$, as stated in Theorem 4.10, can indeed be very large. In such a scenario, one can switch to the parameter setting of Theorem 4.9, which does not impose any such restriction on $T$. However, since this setup requires the knowledge of $\tau_{\mathrm{mix}}$, one can treat $\tau_{\mathrm{mix}}$ as one of the unknown hyperparameters of the algorithm, and fine-tune it during the training phase. This is in line with other RL algorithms in the literature that also require fine-tuning of several unknown hyperparameters, such as the Lipschitz constant or hitting time [1]. Despite these practical solutions, we acknowledge that a systematic theoretical investigation is needed to improve the requirement of the horizon length, $T$ (in the absence of knowledge of $\tau_{\mathrm{mix}}$). We will include it as one of the future works in the revised paper.

On the assumption of ergodicity: The assumption of ergodicity ensures that any state of the MDP is achievable from any other state via some policy. This ensures that a well-designed algorithm can sufficiently explore the state space and obtain a near-optimal policy exploiting the convergence of the policy-induced Markov chain to a stationary distribution. Therefore, it is no surprise that ergodicity is one of the most commonly employed assumptions in the RL literature (see the discussion following Assumption 2.2 in our paper). Extending the analysis to beyond-ergodic MDPs is extremely difficult, and a few works that are available in this direction primarily target tabular policies in the unconstrained setup. Designing algorithms achieving optimal convergence rates for beyond-ergodic CMDPs with general parameterized policies is currently an open question.

On the linear critic approximation error: Bounded linear critic approximation error is one of the commonly employed assumptions in the actor-critic literature. Please refer to the discussion following Assumption 2.2 for an overview of the relevant works. Apart from being important from a theoretical perspective, such a framework also yields good numerical results in experiments, as demonstrated in [2]. Despite these successes, we acknowledge that it is important to extend the analysis to non-linear critic to widen the applicability of the algorithm. Although some recent results are available in this direction [3], they primarily target unconstrained discounted reward setups. Moreover, their algorithms and analysis techniques are vastly different from ours. Whether similar analyses can be performed for constrained average reward settings is currently an open question.

Sensitivity of PDNAC to misspecifying $H$ with unknown $\tau_{\mathrm{mix}}$: Theorem 4.10 states that if $\tau_{\mathrm{mix}}$ is unknown, then one can choose $H=T^{\epsilon}$ for some $\epsilon>0$ which results in objective convergence and constraint violation rates of $\tilde{\mathcal{O}}(T^{-1/2+\epsilon})$ for sufficiently large $T$. Hence, if $H$ is misspecified as $H=T^{\epsilon+\Delta \epsilon}$ for some small error $\Delta\epsilon$, then the convergence rates are modified by a factor of $\tilde{\mathcal{O}}(T^{\Delta\epsilon})$.

References:

[1] ``Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes'', AAAI 2024.

[2] ``Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic'', ICML 2023.

[3] ``Order-optimal global convergence for actor-critic with general policy and neural critic parametrization'', UAI 2025.