Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:38:48

Abstract: We consider the reinforcement learning problem for the constrained Markov decision process (CMDP), which plays a central role in satisfying safety or resource constraints in sequential learning and decision-making. In this problem, we are given finite resources and a MDP with unknown transition probabilities. At each stage, we take an action, collecting a reward and consuming some resources, all assumed to be unknown and need to be learned over time. In this work, we take the first step towards deriving optimal problem-dependent guarantees for the CMDP problems. We derive a logarithmic regret bound, which translates into a $O(\frac{1}{\Delta\cdot\epsilon}\cdot\log^2(1/\epsilon))$ sample complexity bound, with $\Delta$ being a problem-dependent parameter, yet independent of $\epsilon$. Our sample complexity bound improves upon the state-of-art $O(1/\epsilon^2)$ sample complexity for CMDP problems established in the previous literature, in terms of the dependency on $\epsilon$. To achieve this advance, we develop a new framework for analyzing CMDP problems. To be specific, our algorithm operates in the primal space and we resolve the primal LP for the CMDP problem at each period in an online manner, with \textit{adaptive} remaining resource capacities. The key elements of our algorithm are: i) a characterization of the instance hardness via LP basis, ii) an eliminating procedure that identifies one optimal basis of the primal LP, and; iii) a resolving procedure that is adaptive to the remaining resources and sticks to the characterized optimal basis.

Main paper: 
  
 Appendix:  


Decision: This paper derives optimal problem-dependent guarantees for CMDPs. In particular, the paper proposes a primal only algorithm and prove that the resulting algorithm has an instance-dependent $O(1/\epsilon)$ sample complexity bound. 

The reviewers agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the paper and the corresponding discussion, I tend to agree. Please incorporate the reviewers' feedback. In particular, addressing the following concerns will help strengthen the paper:
- Include the experiment done as part of the author response. An empirical comparison with an existing approach (e.g. primal-dual policy gradient) will be helpful. 
- Explain whether the proposed algorithm (without any modification) retains the $O(1/\epsilon^2)$ problem-independent sample-complexity
- Better situate the resulting algorithm and compare to the existing literature (response to Rev. w3CH)
- Add the discussion about the minimax lower-bound (response to Rev. hDFd)
- Compare to the previous bounds in terms of the dependence in $S$, $A$ (and not just $\epsilon$)
- Add a proof sketch. Including some more details about the online LP literature and better connecting it to the CMDP problem will enhance the paper's readability for the audience working on constrained RL. 
- Clearly explain the dependence on the constants in Theorem 5.2. What is tight and what can be relaxed? Conjecturing a lower bound and having a discussion section will be helpful.

Reviews: review: paper_summary: paper_summary: This paper studies reinforcement learning problem under Constrained Markov Decision Processes (CMDPs). It formulates the problem using linear programming and designs a novel algorithm to solve it. Using the newly designed algorithm, the authors prove a sample complexity of $\tilde{O}(1/\epsilon)$, albeit at the expense of having some additional factors.
strength_weakness: strength_weakness: - It has many additional dependencies such as an additional $|\mathcal{S}|^3$, $\sigma$, and etc., compared to other complexity bounds.

- Since the algorithm focuses on the corner points, it defines the separation gap $\delta_1$ between the optimal corner point and the sub-optimal corner points. They are defined to ensure the estimation errors are bounded to distinguish the optimal policy from sub-optimal policies. However, since the algorithm outputs stochastic policies, it is possible that the sub-optimal policies are very close to the optimal policy. Similarly, $\delta_2$ is the minimum gap in the dual values when some constraints are excluded. If the constraints do not change the value of the dual problem much, $\delta_2$ will also be small. Therefore, an additional $\delta = \min \{\delta_1^2, \delta_2^2 \}$ term might not be worth substituting for $\epsilon$.

- In addition, from the definitions of $\xi$ and $\sigma$, it is very likely they will be small terms. For example, for rarely visited states in $q^*$ and small eigenvalues for $A^*$.

- Due to the above concerns, it would be better to conduct experiments showing that the samples needed under such a framework are indeed fewer than those needed for other algorithms achieving $O(1/\epsilon^2)$. However, there are no numerical experiments done in this work. Thus, it is hard to tell whether the newly proposed algorithm is more efficient or not in reality.
questions: questions: Could you theoretically provide some cases to illustrate when those additional dependencies do not make the bound worse? Besides, it will better if the cases provided are not edge cases.
limitations: limitations: There are no potential negative societal impact concerns for this theoretical work.
paper_summary: paper_summary: The strength of this paper is that it provides strong sample complexity results for the constrained MDP, enhancing the existing analysis in the literature by developing a new algorithm. However, despite presenting a promising method, it lacks thorough comparisons with existing methods in the literature.
strength_weakness: strength_weakness: Although the paper presents a promising method, it does not present more through comparisons with existing methods in the literature.
questions: questions: 1) Please define the notation [K] in page 2
2) I wonder if the constraint (2) is commontly used in the literature. 
Please add some discussions on the constraint (2) and if they are used in other papers.
3) The term "problem instance hardness" is frequently used in the introdcution part, but it is not familier with the most readers in my opinion. Therefore, it is necessary to clearly define what is the problem instance hardness.
4) Although the authros develop some promising algorithms, it seems that comparison with other approaches is still weak. Therefore, it would be better if some thorough discussions with existing works is added.
limitations: limitations: The authors properly addressed the limitations of the paper in the document.
paper_summary: paper_summary: This paper addresses the reinforcement learning problem for CMDPs.  The authors derived a problem-dependent sample complexity bound that is $\tilde O(1/\epsilon)$, improving upon the state-of-the-art.  They introduce a novel way to characterize the hardness of CMDP instances using the LP basis, enabling problem-dependent guarantees. The proposed algorithm involves an elimination procedure to identify an optimal basis and a resolving procedure that adapts to remaining resources, ensuring the policy remains near-optimal with fewer samples.
strength_weakness: strength_weakness: While this point may seem minor since the problem setting assumes a tabular formulation with finite and fully observable state and action spaces, it is important to note that the methodology becomes challenging to apply when dealing with large or infinite state spaces where function approximation is required.
questions: questions: N/A
limitations: limitations: Suggestions:
1) A typo in 1.1 Preliminaries line 53: "stochaastic reward" -> stochastic reward
2) Define N in line 120
3) In RL, the notation $q_\pi$ is usually reserved for action-value function according to policy $\pi$.  Thus, it may be a bit disorientating for people from the RL community to see $q_\pi$ as a notation for occupancy measure. Perhaps use a different notation?  I've seen paper using $\nu$ or $d$ for defining occupancy measures. 
4) On line 244, I believe "...satisfy the condition in Theorem 2.1" should be "...Lemma 2.1".
paper_summary: paper_summary: The paper proposes a new algorithm that solves the CMDP problem in $O(1/\epsilon)$ sample complexity, which improves the best-known $O(1/\epsilon^2)$ sample complexity in the literature. To achieve this, this paper made three contributions: (1) New characterizations of the problem instance hardness for CMDP problems. (2) A new algorithm based on LP literature instead of the traditional RL literature. (3) Extended results adopted to online LP literature.
strength_weakness: strength_weakness: 1. The presentation of this work is relatively poor. The author listed three contributions but I feel hard to understand how these contributions have contributed to this work. For example, in the Contribution 1, the author should tell (a) what is the problem instance hardness for CMDP problem, (b) what is the motivation of proposing new characterizations of the problem instance hardness for CMDP problems, (c) why the new characterization is helpful in developing the new algorithm or achieving better complexity.  
2. There is no sufficient discussions on Lemma 2.1. How is it connected to the whole section Characterization of Instance Hardness?
3. The reward, cost, and transitions are all estimated during training. I cannot agree that this algorithm work with unknown transition probabilities since it requires to estimate that.
4. I doubt if the theoretical analysis is correct since it has been known that the sample complexity lower bound is $O(1/\epsilon^2)$. See [R1] and [R2].

[R1] Azar, Mohammad Gheshlaghi, et al. "Reinforcement learning with a near optimal rate of convergence." (2011).
[R2] Vaswani, Sharan, Lin Yang, and Csaba Szepesvári. "Near-optimal sample complexity bounds for constrained MDPs." Advances in Neural Information Processing Systems 35 (2022): 3110-3122.
questions: questions: I am mainly concerned about the $O(1/\epsilon)$ complexity. Can the author clarify the difference between this work and classical RL literature?
limitations: limitations: This is a theoretical work so there is no any negative impact.
paper_summary: paper_summary: The paper studies the linear program formulation of constrained MDPs. The paper first characterizes the instance hardness of the underlying LP. Then, by proposing an algorithm that operates in the primal space and resolves the primal LP in an online manner, the paper derives an overall sample complexity of O(1/\epsilon) up to logarithm terms.
strength_weakness: strength_weakness: * The introduction and related work parts of the paper are not comprehensive enough (especially the related work). In the beginning of Section 1.2, the paper compares itself with [25, 29, 44, 14]. Yet, all of these works focus on policy-based methods, and I think it is not directly comparable with the proposed method in this paper. For example, the dependency of the sample complexity in this work is |S|^4, and this is usually lower for policy-based methods. Moreover, I think the paper might miss several related literature also studies occupancy-measure based approaches, for example,  "Achieving Zero Constraint Violation for Concave Utility Constrained Reinforcement Learning via Primal-Dual Approach" by Bai et al. 
* The paper does not provide numerical simulations. If there is some simulation, I think it helps the reader to have a better sense of how the convergence rate of the algorithm depends on the problem size.
questions: questions: * Can the author provide a more comprehensive literature review and problem introduction? And I think it is also important to consider the dependency of the sample complexity on the problem-related parameters (i.e., |S| and |A|) in the comparison.
* It would be better to briefly discuss the proof idea/implications of theoretical results around the theories. Currently, the ending of the paper seems too abrupt?
* If it is possible, can the author provides some preliminary numerical experiments (not mandatory)?
limitations: limitations: I did not find the place where the paper explicitly discuss the limitation (yet, the author claims "Yes" in the checklist question 2). BTW, it seems the author also forgot to provide justifications for other questions in the checklist as well.

Comments: title: Thank you.
comment: Thank you for acknowledging our response!
Thank you for the clarification and my questions are mostly addressed. I will keep my score the same.
Thank you so much for acknowledging our response!
Thanks the authors for the clarification and answering my questions. I am happy to maintain my current score.
Thank you so much!
Thanks for the clarification! I did misunderstand the contribution of this paper. It has been much more clear. Now I increase my score from 3 to 5.