Sample-Efficient Constrained Reinforcement Learning with General Parameterization

On the Generalizability of [25]: The approach explored in [25] does not generalize to CMDPs. To understand the reasoning, note that one of the preliminary steps in [25] is showing a descent-like inequality. For example, Lemma 6 in [25] reads as follows.

$

\delta\_{t+1} \leq (1-\kappa \gamma_t)\delta_t +R_t, ~~R_t=\mathcal{O}\left(\gamma_t\mathbf{E}\left[\Vert e_t\Vert\right]+ \gamma_t^2 + \sqrt{\epsilon\_{\mathrm{bias}}}\gamma_t\right)  

$

where $\delta_t = J^*- J(\theta_t)$ is the optimality gap, $e_t$ is the difference between the gradient estimate and its actual value, $\gamma_t$ is a time-dependent learning rate, and $\kappa<1$ is some problem-dependent constant. Next, using recursion, and an appropriate choice of $\gamma_t$, the following result is derived (Lemma 12 in [25]).

$

\delta_T \leq \mathcal{O}\left(\frac{\delta_0}{(T+1)^2}\right)+ \dfrac{\sum_{t=0}^{T-1}R_t(t+2)^2}{(T+1)^2}

$

The authors of [25] could prove the convergence of $\delta_T$ up to a factor of $\sqrt{\epsilon_{\mathrm{bias}}}$ precisely because each term in $R_t$ is accompanied by $\gamma_t$ which is chosen to decrease sufficiently fast with $t$. Following Lemma 6 of [25], we can prove the following bound for a primal-dual algorithm.

$

\bar{\delta}^{L}\_t \leq (1-k\gamma_t)\delta_t^L + R_t^L

$

where $\gamma_t$ is the time-dependent primal rate, $\delta_t^L = J_r^* - J_{\mathrm{L}}(\theta_t, \lambda_t)$ is the Lagrange optimality gap, $R_t^L$ has a dependence on $\gamma_t$ that is similar to that of $R_t$, and $\bar{\delta}\_t^L = J_r^* - J_{\mathrm{L}}(\theta_{t+1}, \lambda_t)$. To obtain a recursion on $\delta_t^L$, one can use the following.

$

\delta_{t+1}^L - \bar{\delta}\_t^L = J_{\mathrm{L}}(\theta_{t+1}, \lambda_t) - J_{\mathrm{L}}(\theta_{t+1}, \lambda_{t+1}) = (\lambda_t - \lambda\_{t+1})J_c(\theta\_{t+1}) = \mathcal{O}(\zeta_t)

$

where $\zeta_t$ is the time-dependent dual learning rate. Combining the above two results, we have the following recursion.

$

\delta_{t+1}^{L} \leq (1-k\gamma_t)\delta_t^{L} + R_t^L + \mathcal{O}(\zeta_t)

$

Note that, unlike $R_t^L$, $\zeta_t$ has no dependence on $\gamma_t$. Thus, to establish convergence via recursion, one must choose $\zeta_t$ to decrease faster than $\mathcal{O}(t^{-1})$. On the other hand, the process of decomposing the optimality gap and constraint violation rates from the Lagrange convergence introduces a term of the form $\mathcal{O}(1/(t\zeta_t))$ (see the proof of Theorem 1 in our paper) which requires $\zeta_t$ to decrease slower than $\mathcal{O}(t^{-1})$ to obtain meaningful results. Therefore, any choice of $\zeta_t$ will either disrupt the convergence of the Lagrange function or blow up the constraint violation rates. This negates the possibility of generalizing the approach of [25] to CMDPs via primal-dual algorithms.

On Fisher Degenerate Policies: Thank you for this comment. We will modify the terminology in the revised paper accordingly.

On Slater's Constant: We would like to clarify that, for a given problem instance, Slater's constant is fixed and outside of the control of the learner. On the other hand, the target optimality error $\epsilon$ can be chosen by the learner to be arbitrarily small. Therefore, it would be inappropriate to assign $c_{\mathrm{slater}}=\mathcal{O}(\epsilon)$. Note that, in all previous works on CMDPs, $c_{\mathrm{slater}}$ is treated as a constant, rather than a function of $\epsilon$, e.g., see [1], [2].

On Query Complexity of the Simulator: Our algorithm does not assume access to a gradient oracle. Rather, we assume access to a generative model that yields a sample of the next state $s'$ given the current state-action pair $(s, a)$ following $s'\sim P(s, a)$. We use this generator to obtain an unbiased sample of the gradient via Algorithm 1. It is easy to check that the expected number of queries to the generator to generate one gradient sample is $T=\mathcal{O}((1-\gamma)^{-1})$. We do account for this factor in computing the overall sample complexity of our algorithm. In particular, note that the lengths of inner and outer loops in Algorithm 2 are $H = \mathcal{O}((1-\gamma)^{-3}\epsilon^{-1})$ and $K=\mathcal{O}((1-\gamma)^{-4}\epsilon^{-2})$ respectively, which leads to an overall sample complexity of $\mathcal{O}(THK) = \mathcal{O}((1-\gamma)^{-8}\epsilon^{-3})$. We shall elaborate on the impact of $T$ on the sample complexity in the revised manuscript.

References:

[1] Bai, Qinbo, Amrit Singh Bedi, and Vaneet Aggarwal. "Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 6. 2023.

[2] Ding, D., Zhang, K., Basar, T. and Jovanovic, M., 2020. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33, pp.8378-8390.

Thank you for the comment. We would like to clarify the following points.

P1: Theorem 1 says that the expected objective optimality gap and the constraint violation are of the following form. $\mathrm{Optimality Gap}\leq \sqrt{\epsilon_{\mathrm{bias}}} + \epsilon,$ $\mathrm{ConstraintViolation} \leq (1-\gamma)c_{\mathrm{slater}} \sqrt{\epsilon_{\mathrm{bias}}} + \epsilon \overset{(a)}{\leq} \sqrt{\epsilon_{\mathrm{bias}}} + \epsilon$ where inequality (a) follows from the fact that $c_{\mathrm{slater}}\in (0, \frac{1}{1-\gamma}]$ (see Assumption 1). Note that both $\epsilon_{\mathrm{bias}}$ and $c_{\mathrm{slater}}$ are problem-dependent constants and have no functional dependence on $\epsilon$. We believe that our current phrasing "our algorithm achieves $\epsilon$ optimality gap and $\epsilon$ constraint violation" is the source of this confusion. Instead, if we modify it to "our algorithm achieves $\epsilon$ optimality gap and $\epsilon$ constraint violation up to a factor of $\sqrt{\epsilon_{\mathrm{bias}}}$", the impact of both the problem-dependent constants and $\epsilon$ are separately acknowledged, and one need not force them to be of the same order. It also emphasizes the fact that due to incompleteness of the parameterized policy class i.e., $\epsilon_{\mathrm{bias}}>0$, it is impossible to reach arbitrarily close to the optimal point, no matter how small $\epsilon$ is chosen. Unlike complete policy classes such as direct tabular parameterization (where $\epsilon_{\mathrm{bias}}=0$), it is one of the well-known disadvantages of general parameterization.

P2: We also acknowledge the fact that the choice of $H$, $K$, and the overall sample complexity is dependent on $c_{\mathrm{slater}}$. Currently, such dependence is shown only in the appendix. We can explicitly state this dependence in the main text (Theorem 1) and make it visible to the readers.

P3: To make a fair comparison, we will modify Table 1 to show the impact of $c_{\mathrm{slater}}$ on the sample complexities provided by other existing works (if such explicit dependence is available in the paper).

The problem that you are solving is relaxed feasibility, where the returned policy parameterized by $\theta_0,...,\theta_{K-1}$ is allowed to make some constraint violation, i.e. $E [ 1/K \sum_{k=0}^{K-1} J^{\pi^*}\_{c,rho} - J\_{c,\rho} (\theta_k) ] \leq O(c_{slater}) + \epsilon$ (this is stated in your Theorem 1). In this case, the target error $\epsilon$ can be chosen to be large and because you are allowing for some constraint violation, it is appropriate to assign $c_{slater}$ to $\epsilon$. In doing so, then the bound will be independent of the slater's constant, but it will inflate the bound to $\epsilon^{-6}$. The effect of the slater's constant should be reflected in the bound, and not be treated as a constant. If other papers treat the slater's constant as a constant, it doesn't mean it is appropriate to do so. Your H and K are missing the slater's constant and ignoring its effect. Having slater's constant also differentiates CMDP from MDP, for more details, please see Vaswani, S., Yang, L., and Szepesvári, C. (2022). Near-optimal sample complexity bounds for constrained mdps. I ask the authors to state these distinctions more clearly.

Fairer Comparison of Sample Complexities: We would like to point out that the sample complexity of $\tilde{\mathcal{O}}((1-\gamma)^{-6}\epsilon^{-4})$ reported by [1] in their AAAI version is erroneous. The authors have subsequently corrected their result and the sample complexity has been modified to $\tilde{\mathcal{O}}((1-\gamma)^{-8}\epsilon^{-4})$ in the arXiv version (updated May 2024). Please see Table 1 in [2] to verify our claim. Therefore, in comparison to the state-of-the-art (SOTA), we improve the sample complexity in terms of the optimality gap $\epsilon$ without sacrificing the powers of $(1-\gamma)$. We also note from Table 1 in [2] that other existing results on general parameterized CMDPs are worse than our result both in terms of $\epsilon$ and $(1-\gamma)$. Following the reviewer's suggestion, we will revise the comparison table in our manuscript to exhibit the dependence of the sample complexity on both $\epsilon$ and $(1-\gamma)$. The updated table is provided below for a quick reference.

The dependence of the sample complexities of PMD-PD and PD-NAC on $\gamma$ is not depicted in the papers.

Zero Constraint Violation: Transforming an $\epsilon$ constraint violation (CV) result to a zero CV result is a relatively straightforward exercise that is routinely employed in the literature. The main idea is to choose a slightly modified cost function $c'=c-(1-\gamma)\delta$ and demonstrate an $\epsilon$ CV result for $c'$. This can be done by following the same procedure stated in our paper that is used for producing a similar result for $c$. Observe that $J^{\pi}_{c'}=J^{\pi}_c-\delta$ for any policy $\pi$. Therefore, choosing an appropriate value of $\delta$, one can prove that the obtained $\epsilon$ CV result for $c'$ implies a zero CV result for $c$. Application of this "conservative constraint" technique is abundant in the CMDP literature, e.g., see [1], [3]. In the revised manuscript, we will provide an outline explaining how to derive the zero CV result.

References:

[1] Bai, Qinbo, Amrit Singh Bedi, and Vaneet Aggarwal. "Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 6. 2023.

[2] https://arxiv.org/pdf/2206.05850

[3] Ding, D., Wei, C.Y., Zhang, K. and Ribeiro, A., 2024. Last-iterate convergent policy gradient primal-dual methods for constrained MDPs. Advances in Neural Information Processing Systems, 36.

[4] Xu, T., Liang, Y. and Lan, G., 2021, July. CRPO: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning (pp. 11480-11491). PMLR.

[5] Ding, D., Zhang, K., Basar, T. and Jovanovic, M., 2020. Natural policy gradient primal-dual method for constrained Markov decision processes. Advances in Neural Information Processing Systems, 33, pp.8378-8390.

[6] Liu, T., Zhou, R., Kalathil, D., Kumar, P.R. and Tian, C., 2021. Policy optimization for constrained MDPs with provable fast global convergence. arXiv preprint arXiv:2111.00552.

[7] Zeng, S., Doan, T.T. and Romberg, J., 2022, December. Finite-time complexity of online primal-dual natural actor-critic algorithm for constrained Markov decision processes. In 2022 IEEE 61st Conference on Decision and Control (CDC) (pp. 4028-4033). IEEE.

[8] Vaswani, S., Yang, L. and Szepesvári, C., 2022. Near-optimal sample complexity bounds for constrained MDPs. Advances in Neural Information Processing Systems, 35, pp.3110-3122.

Response to Weakness 1: The term "sample-efficient" simply acknowledges the fact that the sample complexity of our algorithm is better than that of all existing algorithms in the general parameterized CMDP setup. Note that we refrain from using the term "sample optimal" since there is still a gap between our bound $\mathcal{O}(\epsilon^{-3})$ and the theoretical lower bound of $\Omega(\epsilon^{-2})$.

Response to Weakness 2: Thank you for mentioning the inappropriate use of the phrases "$\epsilon$ optimality gap" and "$\epsilon$ constraint violation". In the revised paper, we will change these phrases to emphasize the presence of the $\epsilon_{\mathrm{bias}}$ term. Moreover, we will also discuss the precise meaning of optimality in the introduction of our paper.

Response to Question 1: We apologize for the confusion. The notation $\mathbf{E}[\cdot]^2$ in (9) was intended to denote $\mathbf{E}[(\cdot)^2]$. We will add additional parentheses in the revised manuscript to make the notation unambiguous.

Response to Question 2: The equations $(75)-(76)$ use the fact that the average of the occupancy measures is still an occupancy measure. Therefore, the average of the occupancy measures corresponding to the policies $\\{\pi_{\theta_k}\\}\_{k=1}^K$ would be an occupancy measure corresponding to some policy, say $\bar{\pi}$. Since the value function $J_g^{\pi}$ can be written as a linear function of the occupancy measure corresponding to the policy $\pi$, the transition from $(75)$ to $(76)$ is immediate. Moreover, the optimal dual variable $\lambda^*$ comes into the picture due to the use of Lemma 10. We shall expand these arguments in the revised manuscript.