Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm

Response to Question 1: Note that a constrained MDP can be considered as an unconstrained MDP where the (equivalent) reward function is $r+\lambda c$ and the optimization is performed over all policies $\pi\in \Pi$ and $\lambda\geq 0$. In other words, the original constrained optimization is equivalent to the following primal formulation: $\max\_{\pi\in\Pi}\min\_{\lambda\geq 0} J^{\pi}\_{r+\lambda c}$. Note that the solution to this max-min problem, $\pi^*$ is precisely the solution to the original CMDP. Therefore, it is natural that $\epsilon_{\mathrm{bias}}$, in this case, is defined via $\pi^*$ and $A_{\mathrm{L}, \lambda}$ where $A_{\mathrm{L}, \lambda}=A_r+\lambda A_c$ denotes the advantage function corresponding to $r+\lambda c$. A similar definition of $\epsilon_{\mathrm{bias}}$ can also be found in earlier works (e.g., see Assumption 4 in ref. [4])

Response to Questions 2 and 3: The remark that the primal-dual approach performs worse than the unconstrained setup was mainly targeted for general parameterization. Table 1 in the paper shows that a similar conclusion does not hold for either tabular or linear MDPs. The paper by Hong and Tewari cited by the reviewer assumes a linear MDP setup and thus is not a focus of this discussion. To understand why a gap arises between a constrained and an unconstrained case in general parameterization, one can take a look at Lemma 6. An extra $\beta$ term (dual learning rate) appears in the convergence of the first-order stationary result which is accompanied by an $\mathcal{O}(\beta^{-1})$ term during the segregation of objective optimality gap and constraint violation rate (Theorem 1). Note that the second $\mathcal{O}(\beta^{-1})$ term is absent in unconstrained case which allows us to choose $\beta = 0$ and obtain a convergence rate of $\tilde{\mathcal{O}}(T^{-1/4})$ as in [13]. However, such a choice is infeasible for the constrained case, leading to a worsening of the final result.

Response to Question 4: For Assumption 5: Assumption 5 is also common (Liu et al., 2020) in the policy gradient analysis. This is not a very restrictive assumption. We corroborate this claim by quoting (Liu et al., 2020) (where this assumption is Assumption 2.1):

``This is a common (and minimal) requirement for the convergence of preconditioned algorithms in both convex and nonconvex settings in the optimization realm, for example, the quasi-Newton algorithms [40, 41, 42, 43], and their stochastic variants [44, 45, 46, 47, 36]. In the RL realm, one common example of policy parametrizations that can satisfy this assumption is the Gaussian policy [2, 48, 19, 21], where $\pi_\theta(\cdot| s) = N(\mu_\theta(s), \Sigma)$ with mean parametrized linearly as $\mu_\theta(s) = \phi(s)^T\theta$, where $\phi(s)$ denotes some feature matrix of proper dimensions, $\theta$ is the coefficient vector, and $\Sigma >0$ is some fixed covariance matrix. In this case, the Fisher information matrix at each $s$ becomes $\phi(s)\Sigma^{-1}\phi(s)^T$, independent of $\theta$, and is uniformly lower bounded (positive definite sense) if $\phi(s)$ is full-row-rank, namely, the features expanded by $\theta$ are linearly independent, which is a common requirement for linear function approximation settings [49, 50, 51].

For $\mu_\theta(s)$ being nonlinear functions of $\theta$, e.g., neural networks, the positive definiteness can still be satisfied, if the Jacobian of $\mu_\theta(s)$ at all $\theta$ uniformly satisfies the aforementioned conditions of $\phi(s)$ (the Jacobian in the linear case). In addition, beyond Gaussian policies, with the same conditions mentioned above on the feature $\phi(s)$ or the Jacobian of $\mu_\theta(s)$, Assumption 2.1 also holds more generally for any full-rank exponential family parametrization with mean parametrized by $\mu_\theta(s)$, as the Fisher information matrix, in this case, is also positive definite, in replace of the covariance matrix $\phi(s)\Sigma^{-1}\phi(s)^T$ in the Gaussian case [11].

Indeed, the Fisher information matrix is positive definite for any regular statistical model [28]. In the pioneering NPG work [24], $F(\theta)$ is directly assumed to be positive definite. So is in the follow-up works on natural actor-critic algorithms [39, 7]. In fact, this way, $F_\rho(\theta)$ will define a valid Riemannian metric on the parameter space, which has been used for interpreting the desired convergence properties of natural gradient methods [3, 32]. In sum, the positive definiteness on the Fisher preconditioning matrix is common and not restrictive. "

We will expand on this in the revision to explain Assumption 5.

Response to Weakness 1: Thank you for suggesting the paper by Patel et. al. where the algorithm works without the knowledge of $t_{\mathrm{mix}}$. We would like to point out that such a feat is achieved by introducing an additional assumption and weakening the convergence result. In particular, the paper solves the average (unconstrained) MDP problem via an actor-critic approach where the value function of the critic is taken to be a linear function of a feature vector. No such assumption is needed in our paper. Secondly, their approach introduces an additional critic error $T\sqrt{\epsilon_{\mathrm{critic}}}$ in the final regret, in addition to the usual approximation error $T\sqrt{\epsilon_{\mathrm{bias}}}$. Despite these drawbacks, we agree that their approach is worth exploring in the future. However, we believe that if the linear critic assumption in this paper is relaxed, the regret bounds will become even worse (a similar effect has been recently shown in the sample complexity result of discounted MDPs). We are currently not sure about the applicability of this technique to our CMDP problem.

We would also like to mention that the suggested paper became public on arXiv on March 18th for the first time, which is within two months of the NeurIPS 2024 abstract submission deadline, and thus could be considered as concurrent research. We will cite this work in the final version, and suggest extending its approaches to CMDPs as a future work.

Response to Weakness 2: We agree that empirical evaluations will be a nice corroboration of our established results. However, considering this is a theory-oriented paper, our goal is to propose a policy gradient-type algorithm in an infinite horizon average reward setting and establish its theoretical guarantees. A detailed evaluation will be the subject of future work.

Response to Weakness 1: Note that the framework of UCRL that works for Weakly Communicating (WC) MDPs is a model-based method that cannot be extended to large state space. Designing model-free algorithms, especially for Constrained MDPs (CMDPs), is an extremely difficult problem. This is evident from the fact that no model-free algorithms are available in the literature that yield provable guarantees for WC CMDPs. Only a single paper in the literature (ref. [8] in the paper) provides a model-free algorithm that works for ergodic CMDPs. Unfortunately, this paper has a worse $\tilde{\mathcal{O}}(T^{5/6})$ regret compared to our result and adopts the tabular setup. In contrast, our paper provides the first regret bound for ergodic CMDPs with general parameterization (that subsumes the tabular case) and improves the regret to $\tilde{\mathcal{O}}(T^{4/5})$. Extension of our result to the WC case will be considered in the future.

Response to Weakness 2: Thanks for providing the suggestion. We will add an extra column in the table that states the model assumptions used in the associated works for a fairer comparison between the algorithms.

Response to Weakness 3: Intuitively, $t_{\mathrm{mix}}$ indicates how fast the $t-$step transition probability converges to the stationary distribution. To the best of our knowledge, there is no known lower bound of $t_{\mathrm{mix}}$ in terms of $S$ and $A$. Therefore, it is theoretically possible that, even in an MDP with infinite states, $t_{\mathrm{mix}}$ could be finite.

Response to Question 1: Please refer to weakness 3.

Response to Question 2: We agree that empirical evaluations will help characterize the impact of $t_{\mathrm{mix}}$ estimation on the performance of the algorithm. However, since ours is a theory-oriented paper, our main goal is to establish provable guarantees for the proposed algorithm. A detailed evaluation will be the subject of future work.

Response to Weakness 1: Unfortunately, the proposed algorithm may not be extended to the weakly communicating (WC) setting. In general, it is difficult to propose a model-free algorithm with provable guarantees for Constrained MDPs (CMDPs) without considering the ergodic model. WC CMDPs impose extra challenges in learning compared to the ergodic case. For example, there is no uniform bound for the span of the value function for all stationary policies. It is also unclear how to estimate a policy’s bias function accurately without the estimated model, which is an important step for estimating the policy gradient. The above-stated difficulty is evident from the fact that no model-free algorithm is available in the literature that works for WC CMDPs with provable guarantees. Moreover, only a single model-free algorithm (ref. [8] in the paper) is available for ergodic CMDPs. In other words, all existing algorithms that work for WC CMDPs are model-based in nature. These approaches cannot be extended to the large state space scenario which is the premise of our paper.

Response to Weakness 2: Thanks for providing the suggestion. We will modify the table to point out the dependence on the linear term $T\sqrt{\epsilon_{\mathrm{bias}}}$. The transferred compatible function approximation error is a common assumption in policy-based algorithms (see ref. [10], [11] in the paper). From the sample complexity result (Theorem 1), we can see that the proposed algorithm converges to the neighborhood of the global optima within a distance of $\sqrt{\epsilon_{\mathrm{bias}}}$, which is the same result as in the literature.

Response to Weakness 1: We would like to clarify that we do not assume access to an accurate knowledge of the optimal policy since that would contradict our learning objective. We merely assume that the policy belongs to a class where each member is indexed by a parameter $\theta$. The goal is to find the parameter $\theta^*$ that corresponds to the optimal policy. In reality, such a parameterized class can be modeled via a neural network where its weights can act as the index parameter. We start with an arbitrary $\theta_0$ (which can be far away from $\theta^*$) and slowly move towards the optimality using our proposed primal-dual steps.

Response to Weakness 2: We agree with the reviewer that the policy evaluation part is inspired by [17]. However, we would like to point out some major differences.

(1) The value estimation (Algorithm 2) is not tabular in the sense that it need not be evaluated for all state-action pairs. This routine only needs to be invoked for the pairs that are encountered by Algorithm 1 on the go.

(2) The parameter $H$ in Algorithm 2 differs from that in [17]. With the same parameter choice, our proposed policy gradient algorithm would diverge.

Additionally, the overall approach in our paper differs significantly from that of [17].

(3) In particular, our paper considers a constrained setting, which includes a primal-dual approach that is not included in [17].

(4) Finally, [17] considers a tabular setting which enjoys the strong duality. However, the general parameterization setting considered in our paper does not have the same benefit. The convergence result for the dual problem, therefore, does not automatically translate to that for the primal problem. Our novel introduction of Theorem 1 allows us to separate the objective and constraint violation rates.

Response to Weakness 3: We agree that empirical evaluations will be a nice corroboration of our established results. However, considering this is a theory-oriented paper, our goal is to propose a policy gradient-type algorithm in an infinite horizon average reward setting and establish its theoretical guarantees. A detailed evaluation will be the subject of future work.