Sample-Efficient Constrained Reinforcement Learning with General Parameterization

Summary

The paper studies constrained Markov decision processes. Using momentum acceleration, the paper develops a primal-dual natural policy gradient-based algorithm and shows that it achieves an \epsilon global optimality with O(\epsilon^-3) samples. The policy class considered in the paper is the generic Fisher non-degenerate policies.

Strengths

* The paper is the first in the literature that derives the O(\epsilon^-3) sample complexity for constrained MDP under more general policy parameterizations than the softmax. * The presentation of theoretical results are clear and easy to follow. I appreciate that the author presents a complete flow of proof in the main body of the paper.

Weaknesses

I mainly have the following concern, and if it can be addressed, then I am willing to adjust my rating. In literature [25], a sample complexity of O(\epsilon^-2) is derived for unconstrained MDP. To me, it seems it is not impossible to translate this result to the constrained setting by adding a primal-dual component, and if this can be done, I think the sample complexity should be O(\epsilon^-3) or so. I wonder could the author discuss the feasibility of this generalization (and perhaps the underlying challenges if it is not generalizable).

Questions

* I hope the author could discuss the concern I raised in the weakness section. * Since the paper actually studies Fisher non-degenerate policies, I think a more common (and precise) way is to directly use the name "Fisher non-degenerate policies". Using the name "general parameterization" is a little bit misleading.

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

The author has discussed the limitation of the paper briefly in the conclusion section.

Summary

The paper considers the constrained MDP setting. Given a target error of $\epsilon > 0$, the paper provides a primal-dual algorithm on that will return an epsilon optimal policy making at most epsilon constraint violations. The claim is that the algorithm solves such problem with O($\epsilon^{-3}$) sample complexity.

Strengths

The idea of incorporating momentum acceleration to a primal-dual algorithm seems interesting.

Weaknesses

The Slater's constant $c_{slater}$ is missing from the big O-notations in your $H$ and $K$ terms. The slater's constant is an unique quantity in CMDP and should be clearly stated in your sample complexity. In the relaxed-feasibility problem, where the algorithm returns a policy that is allowed to have some small constraint violation (such as epsilon constraint violation), the Slater's constant can be smaller than the target error epsilon. In this case, the Slater's constant can be set to be the $\epsilon$. Your paper is in this relaxed-feasibility setting. By writing the Slater's constant $c_{slater}$ explicitly in the big O-notations, we see that $H = \mathcal{O}((1-\gamma)^{-3} \epsilon^{-1} c_{slater}^{-1})$ and $K = \mathcal{O}((1-\gamma)^{-4} \epsilon^{-2} c_{slater}^{-2})$. If the Slater's constant = epsilon, then we see that $H \propto \epsilon^{-2}$ and $K \propto \epsilon^{-4}$ making the total sample complexity to be proportional to $\epsilon^{-6}$. Then, the result is independent of the Slater's constant.

Questions

Your result stated in Lemma 6 is based on a previous result provided by [6]. In [6], the result relies on an oracle that, when given an input, provides a noisy unbiased gradient of a function. However, your algorithm uses a sampling procedure to obtain a gradient estimate, which appears to rely on access to a generative model (Kakade (2003) On the sample complexity of reinforcement learning). Are you considering the setting of having access to a generative model, or are you assuming access to an oracle as in [6], for which your Lemma 6 is based? If you are considering the setting of having access to a generative model, the paper should address the statistical challenges associated with sampling, and the sample complexity should include the number of queries to a simulator, incorporating $T$ into the sample complexity. Therefore, the result from [6] in Lemma 6 does not immediately apply. If you are considering the setting of having access to an oracle, it is not clear why Algorithm 1 is necessary.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

By stating the Slater's constant in the sample complexity, the sample complexity is in the order of epsilon to the minus 6 instead of minus 3 so to be independent of the Slater's constant. See comments in the Weaknesses section.

Summary

This paper studied the sample complexity of learning a discounted-reward MDP with a discounted cost constraint under a general policy parameterization. It proposes a policy-gradient-type of algorithm that combines natural policy gradient and an accelerating stochastic gradient descent algorithm proposed in [6]. Then the paper proves that with $O(1/\epsilon^3)$ samples, the policy learned by this algorithm violates the constraint by at most $\epsilon$, and is optimal up to $\epsilon_{bias} + \epsilon$ error, where $\epsilon_{bias}$ is a constant coming from policy parameterization. The sample complexity of this policy improves upon the prior SOTA, which was $O(1/\epsilon^4)$.

Strengths

The paper is well-written. The main contribution, the algorithm, the key idea of the proof and the proof structure are clearly presented. The improvement of sample complexity from $O(1/\epsilon^4)$ to $O(1/\epsilon^3)$ is non-trivial, following from a clever observation given in lemma 3. The analysis looks solid, though I do have questions about a few minor details, see the questions 1 and 2 below.

Weaknesses

1 The “sample efficient” in the title seems to overclaim the contribution of the paper, since there is still an order gap between the sample complexity of the algorithm in this paper, $O(\epsilon^{-3})$, and the lower bound, $O(\epsilon^{-2})$. 2 It is not entirely accurate to say that the algorithm achieves “$\epsilon$ global optimality gap” and “$\epsilon$ constraint violation”, as the actual bounds in Theorem 1 contain constant terms involving $\epsilon_{bias}$. Although $\epsilon_{bias}$ is common in the analysis of RL algorithms with general parameterizations, it is crucial to discuss whether they are tight and optimal, how they compare to the prior work, and whether they are truly negligible when the policy is parameterized by a neural net of a reasonable scale. At the very least, the sense in which your policy is epsilon-optimal should be clarified in a prominent part of the paper.

Questions

1 I believe the definition of L in (9) has a typo: the square should be inside the expectation, rather than outside the expectation, so that its gradient with respect to w is given by (10). Does this typo affect the proof? 2 The logic from (75) to (76) is not very clear. How did you get rid of the first term on LHS of (76), and where does $\lambda^*$ comes from?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

There is no negative social impact. A discussion of limitation is included in the submission.

Summary

The paper studies the sample complexity of the constrained Markov Decision Process (CMDP), and derives an algorithm that attains the $O(\epsilon^{-3})$ that improves the SOTA sample complexity bound for CMDP by a factor of $O(\epsilon^{-1})$.

Strengths

CMDP with general parameterization is a very challenging problem, and thus there have not been many papers making progress in this challenging setting compared to the tabular CMDP setting. The authors modify the classic primal-dual natural policy gradient (NPG) framework by leveraging an accelerated stochastic gradient descent (ASGD) method to improve the SOTA sample complexity bound by a factor of $O(\epsilon^{-1})$.

Weaknesses

Even though the authors claim they have improved the SOTA sample complexity bound for CMDP with general parameterization, I still think it is hard to say the authors have "beat" the previous results. $\epsilon$ is not the only factor that matters for the sample complexity bound for discounted infinite-horizon MDPs, since $\gamma$ is also another significant factor. Unfortunately, it seems that the authors' bound has a dependency of $O(1/(1-\gamma)^{-8})$, so that makes the sample complexity bound read $O(1/(1-\gamma)^8\epsilon^3)$. Compared to a prior work [1] which has a sample complexity bound of $O(1/(1-\gamma)^6\epsilon^4)$, it is clear the two bounds are not necessarily comparable due to one bound is superior in terms of the order of $\epsilon$ and the other superior in terms of the order of $\gamma$. Also, [1]'s algorithm has zero constraint violation while the authors' algorithm permits $O(\epsilon)$ constraint violation, which is a worse result. Hence, unless the authors can clarify their result has improvement in $\epsilon$ and $\gamma$ and constraint violations (or at least provide stronger justifications that their algorithm requires a smaller number of samples to achieve near-optimality), it is hard to evaluate the value of the authors' result. [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.

Questions

As mentioned, the major weakness of the paper is that you have overlooked the sample complexity bound's dependency in $\gamma$ and it seems you have a worse constraint violation result. Can you update Table 1 with sample complexity bounds having dependency in $\gamma$ and with constraint violations? More importantly, can you justify why your result has seemingly worse dependency in $\gamma$ and constraint violations?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The major limitation of the paper is the lack of proper comparison of the sample complexity bounds with prior works.