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

We appreciate your insightful comments, which allow us to provide further clarifications. Please find below our response to the weakness and the questions. We hope that our response would clarify your concerns about the paper and we are happy to provide further clarifications if needed.

$**Response to weakness 1**$: Thank you so much for the comment! Please allow us to further clarify. Please note that when deriving instance-dependent learning, it is important to define a measure to describe how difficult it is to separate the optimal policies from the sub-optimal ones. The importance of defining such a measure has been illustrated in other problems, such as multi-arm-bandit problems (e.g. Lai and Robbins (1985)) and reinforcement learning problems (e.g. Auer et al. (2008)). There are also other works studying how to characterize such a measure for instance-dependent learning on general sequential decision making problems, for example Wagenmaker and Foster (2023). This measure is usually defined as the gap (a positive constant) between the value of the optimal policies and the value of the best sub-optimal policies. However, since the optimal policies for CMDP problems are randomized policies, the sub-optimal policies can be arbitrarily close to the optimal ones. In our paper, we show that if we restrict the policies to the ones represented by the corner points, then such a gap can be characterized as the difference between the optimal corner points and the sub-optimal corner points. Suppose this gap is $\Delta$, then it requires $\tilde{O}(1/\Delta)$ number of samples to identify the optimal corner point.

In summary, (a). ``problem instance hardness'' is a measure of the number of samples needed to separate the optimal policies from the sub-optimal ones; (b). The optimal policies for CMDP are randomized policies and thus previous measures do not apply. We need to develop a new measure that can separate the optimal randomized policies from the sub-optimal randomized policies for the CMDP problems (by restricting to the policies represented by the corner points of the LP); (c). Our new algorithm is developed based on corner point characterization. To be specific, our algorithm 1 is developed to identify one optimal corner point (one optimal basis of the LP), and our algorithm 2 resolves the LP sticking to the identified corner point to learn the optimal randomization. As we can see, identifying the optimal corner point (basis) and resolving the LP sticking to this corner point (basis) are the key elements of our algorithm, which is motivated by the instance hardness characterization via corner point.

$**Response to weakness 2**$: Thank you! Lemma 2.1 is to show that for any LP, there exists an optimal basis or corner point and the LP basis or corner point can be characterized via non-zero variables and binding constraints. As discussed in our response to your previous point, this corner point representation motivates our entire approach.

$**Response to weakness 3**$: Thanks for the comment. Our work assumes that the transition probabilities are unknown and need to be estimated from the data. Our algorithm is more in the sense of model-based, and this is why we need to construct estimates of the transition probabilities, as well as rewards and costs, during the execution of our algorithm.

$**Response to weakness 4**$: Thank you for mentioning the two important papers! It is indeed true that if we are seeking for a $**worst-case**$ sample complexity bound, then $O(1/\epsilon^2)$ is the best we can hope for, just as illustrated in the two papers you mentioned. However, we would like to emphasize that we are deriving instance-dependent sample complexity in our paper. This is the key reason why we can break the $O(1/\epsilon^2)$ lower bound and obtain an improved $\tilde{O}(1/\epsilon)$ sample complexity. To be specific, for a problem instance $I$, we can denote by $S(I, \epsilon)$ the number of samples needed to construct an $\epsilon$-optimal policy. Then the worst-case lower bound implies that $\max_{I}S(I,\epsilon)=\Theta(1/\epsilon^2)$. However, if we do not consider the worst-case guarantee, i.e., if we do not maximize over the problem instance $I$, then we can characterize an instance-dependent constant $\Delta(I)$ (independent of $\epsilon$) such that $S(I,\epsilon)=\Delta(I)/\epsilon\cdot \text{polylog}(1/\epsilon)$. The main contributions of our paper are to (i). find a cornet-point characterization of the instance-dependent constant $\Delta(I)$, and ii). derive a policy that achieves the instance-dependent $\tilde{O}(1/\epsilon)$ sample complexity bound. Please note that our bound does not contradict with the worst-case lower bound $O(1/\epsilon^2)$. It is simply that we are seeking for an instance-dependent bound and when the problem instance is favorable such that the constant $\Delta(I)$ is smaller than $1/\epsilon$, our bound strictly improves upon the worst-case bound.

$**Response to the question**$: Thank you for this question! The main difference between our work and the classical RL for CMDP literature is that we are deriving an instance-dependent sample complexity bound, while the previous literature focuses on the worst-case sample complexity bound. Indeed, the instance-dependent guarantee has been considered in the previous RL literature (but without constraints). See for example [1] and [2] for the logarithmic regret which transfers into $\tilde{O}(1/\epsilon)$ sample complexity bound. However, these works do not consider the existence of the constraints.

[1]. Velegkas, Grigoris, Zhuoran Yang, and Amin Karbasi. "Reinforcement learning with logarithmic regret and policy switches." Advances in Neural Information Processing Systems 35 (2022).

[2]. He, Jiafan, Dongruo Zhou, and Quanquan Gu. "Logarithmic regret for reinforcement learning with linear function approximation." International Conference on Machine Learning. PMLR, 2021.

We would like to thank you for your insight review! Please find below our response to the weakness and your questions!

$**Response to weakness 1**$: Thank you for mentioning the important references to us! We will refine our literature review part to incorporate a better comparison with existing works and approaches, including the important work you pointed out. Briefly speaking, our work presents a new algorithm. We adopt an occupancy measure representation of the optimal and obtain an LP to work with, which is similar to the previous work. However, our algorithm resolves an LP and operates in the primal space, which is fundamentally different from the previous work that adopts a primal-dual update (e.g. Stooke et al., 2020, Ding et al., 2022, Zeng et al., 2022, Bai et al., 2023, Moskovitz et al., 2023, ). There is also work developing primal-based algorithms, for example (Liu et al., 2019; Chow et al., 2018; 2019; Dalal et al., 2018, Xu et al. 2021). Our algorithm is completely different from the previous work and we obtain new results. The result is that we are able to obtain an instance-dependent $\tilde{O}(1/\epsilon)$ sample complexity the first time in the literature, which improves upon the $O(1/\epsilon^2)$ worst-case sample complexity established in the previous work. Though the constrained optimization approach and the Lyapunov approach have also been developed for CMDP problems, they do not enjoy a theoretical guarantee. In comparison to the literature, we develop a new primal-based algorithm and achieve the first instance-dependent sample complexity for CMDP problems.

We will add a more comprehensive literature review. We would be appreciative if you could point out the papers that we haven't discussed and we will add discussions of those.

$**Response to weakness 2**$: Thank you for the comment! We have conducted basic numerical experiments to illustrate the empirical performance of our algorithms. Please refer to the ``global response'' for more details.

$**Response to question 1**$: Yeah, sure! Please find in our response to the first weakness part the refined literature review on the comparison with existing works. Also, we provide the following discussion on the dependency on other problem parameters.

``We discuss the dependency of our sample complexity bound on problem parameters other than $\epsilon$. We restrict to the MDP context without resource constraints. Denote by $\mathcal{S}$ the state set and $\mathcal{A}$ the action set. We show a sample complexity bound of $O\left( \frac{|\mathcal{S}|^4\cdot|\mathcal{A}|}{(1-\gamma)^4\cdot\Delta}\cdot\frac{\log^2(1/\epsilon)}{\epsilon}\right)$, where $\Delta$ is the constant that represents the hardness of the underlying problem instance. Compared to the optimal worst-case sample complexity $O\left( \frac{|\mathcal{S}|\cdot|\mathcal{A}|}{(1-\gamma)^3\cdot\epsilon^2} \right)$ that is achieved in a series of work (e.g. Sidford et al. 2018, Wainwright 2019, Wang 2020, Agarwal et al. 2020, He et al. 2021), our bound has a worse dependency over $|\mathcal{S}|$ and $1-\gamma$. This is due to our algorithm being LP-based and the dimension of the LP ($|\mathcal{S}|$ and $1-\gamma$) will influence our final bounds. However, our bound enjoys a better dependency in terms of $\epsilon$. For the general CMDP problem, our bound will depend additionally on the conditional number of the constraint matrix in the LP formulation, which is a byproduct of the resolving LP heuristics (e.g. Vera and Banerjee 2021, Li et al. 2021). However, our $\tilde{O}(1/\epsilon)$ sample complexity bound depends polynomially on other parameters including $|\mathcal{S}|$, $|\mathcal{A}|$, $1-\gamma$, and the number of constraints.''

Please note that even though our bound has some additional dependencies on other parameters, our bound can still improve upon the worst-case bound for any problem instance as long as $\epsilon$ is set to be small. To be specific, for an instance $I$, denote by $C_1(I)/\epsilon$ our bound (logarithmic term neglected) and denote by $C_2/\epsilon^2$ the worst-case bound. Then, as long as we set $\epsilon\leq C_2/C_1(I)$, our bound will be smaller. Therefore, our bound is favorable when the instance is good such that $C_1(I)$ is small, or when we are seeking for a highly accurate near-optimal solution such that $\epsilon$ is small.

$**Response to question 2**$: Thanks for the comment. Due to the space limit, the discussions on the proof idea have not been added. We will for sure have the discussion. Please find below for a preliminary one.

``Our algorithm is motivated by the resolving LP heuristics in online LP/resource allocation literature (e.g. Vera and Banerjee (2021), Li and Ye (2021)). We can naturally interpret the right-hand-side constraints of the LP as the resource capacities and at each round $n$, the variables $\alpha^n$ and $\mu^n$ can be interpreted as the remaining capacities. Then, a key step in the proof is to establish that the average remaining capacities, $\alpha^n/(N-n+1)$ and $\mu^n/(N-n+1)$ behave as (sub-)martingales. As a result, we can apply concentration properties to show that the remaining capacities will diminish when we arrive at the end of the horizon, i.e., the resources have been utilized well. Moreover, since we have already identified the optimal basis in Algorithm 1 and we resolve the LP sticking to the optimal basis, we can show that when the resources are well utilized, the total reward we collect is very close to the optimal reward. In this way, we obtain a bound over the total reward collected by our policy and that of the optimal policy, which then transfers into the sample complexity bound.''

$**Response to question 3**$: Thanks for the question! We are happy to add the numerical results. We have conducted basic experiments. Please refer to the ``global response'' for more details.

We would like to thank you for your positive review and insightful comments! Please find below our response to your comments and questions!

$**Response to weakness**$: Thank you so much for the comment! Indeed, the method developed in this paper is mainly for the tabular setting. However, the method can also be extended to handle the setting with possibly large state/action space. To be specific, we can utilize a linear function approximation and similarly write a LP with the coefficients in the linear approximation as the decision variables of the LP. We are currently working on this extension. Combining our method with more general function approximations will be a future topic for us to explore.

$**Response to limitation 1**$: Thank you for pointing it out! We will correct it.

$**Response to limitation 2**$: Thank you! $N$ refers to the number of episodes.

$**Response to limitation 3**$: Thank you for the suggestion! Indeed, $\nu$ or $d$ is a better notation for the occupancy measure.

$**Response to limitation 4**$: You are right! Thanks for the correction!

We would like to thank you for your insightful comments! Please find below our response to each of the weakness points and the questions you posted. We hope that our response would clarify your concerns about the paper.

$**Response to weakness**$: Thank you for the comment! We will for sure provide a better literature review and comparison with previous methods. Briefly speaking, our work presents a new algorithm. We adopt an occupancy measure representation of the optimal and obtain an LP to work with, which is similar to the previous work. However, our algorithm resolves an LP and operates in the primal space, which is fundamentally different from the previous work that adopts a primal-dual update (e.g. Stooke et al., 2020, Ding et al., 2022, Zeng et al., 2022, Bai et al., 2023, Moskovitz et al., 2023, ). There is also work developing primal-based algorithms, for example (Liu et al., 2019; Chow et al., 2018; 2019; Dalal et al., 2018, Xu et al. 2021). Our algorithm is completely different from the previous work and we obtain new results. The result is that we are able to obtain an instance-dependent $\tilde{O}(1/\epsilon)$ sample complexity the first time in the literature, which improves upon the $O(1/\epsilon^2)$ worst-case sample complexity established in the previous work. Though the constrained optimization approach and the Lyapunov approach have also been developed for CMDP problems, they do not enjoy a theoretical guarantee. In comparison to the literature, we develop a new primal-based algorithm and achieve the first instance-dependent sample complexity for CMDP problems.

We will add a more comprehensive literature review. We would be appreciative if you could point out the papers that we haven't discussed and we will add discussions of those.

$**Response to question 1**$: Thanks. The definition is $[K]=\{1,\dots, K\}$.

$**Response to question 2**$: Thanks for the comment! Indeed, there are other formulations of the constraints in CMDP, for example,

$

V_k(\pi, \mu_1)=\mathbb{E}\left[ \sum_{t=0}^{\infty}\gamma^t\cdot c_k(s_t, a_t)\mid \mu_1 \right] \geq \lambda_k, ~~\forall k\in[K].

$

in a series of work that studies safe reinforcement learning. However, the above formulation can be transferred from our formulation in constraint $(2)$. One can set $\alpha_k=\frac{1}{1-\gamma}-\lambda_k$ for each $k\in[K]$, and it is easy to see that the two inequalities are equivalent to each other,

$

\mathbb{E}\left[ \sum_{t=0}^{\infty}\gamma^t\cdot c_k(s_t, a_t)\mid \mu_1 \right] \geq \lambda_k \Leftrightarrow \mathbb{E}\left[ \sum_{t=0}^{\infty}\gamma^t\cdot (1-c_k(s_t, a_t))\mid \mu_1 \right] \leq \alpha_k.

$

Therefore, we can equivalently use the formulation in constraint $(2)$ with the cost function defined as $1-c_k$ for each $k\in[K]$.

$**Response to question 3**$: Thank you! Please note that when deriving instance-dependent learning, it is important to define a measure to describe how difficult it is to separate the optimal policies from the sub-optimal ones. The importance of defining such a measure has been illustrated in other problems, such as multi-arm-bandit problems (e.g. Lai and Robbins (1985)) and reinforcement learning problems (e.g. Auer et al. (2008)). There are also other works studying how to characterize such a measure for instance-dependent learning on general sequential decision-making problems, for example Wagenmaker and Foster (2023). This measure is usually defined as the gap (a positive constant) between the value of the optimal policies and the value of the best sub-optimal policies. However, since the optimal policies for CMDP problems are randomized policies, the sub-optimal policies can be arbitrarily close to the optimal ones. In our paper, we show that if we restrict the policies to the ones represented by the corner points, then such a gap can be characterized as the difference between the optimal corner points and the sub-optimal corner points. Suppose this gap is $\Delta$, then it requires $\tilde{O}(1/\Delta)$ number of samples to identify the optimal corner point. In summary, ``problem instance hardness'' is a measure of the number of samples needed to separate the optimal policies from the sub-optimal ones. Our corner point characterization motivates our entire approach.

$**Response to question 4**$: Thank you! We will provide a better comparison with existing methods. Please refer to our response to the weakness part.

We would like to thank you for your positive review and insightful comments! Please find below our response to the weakness and your question. We hope that our response would clarify your concerns regarding our work.

$**Response to weakness 1**$: Thank you for the comment! You are right that our bound has additional dependencies on the model parameters, however, this seems to be common for instance-dependent learning and has shown up in other works. It is easy to understand that when we obtain a better dependency on $\epsilon$, we would suffer from a worse dependency on other parameters. However, it is important to note that the additional dependency on the model parameters is fixed and is independent of $\epsilon$. Therefore, when we are seeking a highly accurate near-optimal policy and set $\epsilon$ to be small, our bound will be a better one. Please further refer to our response to your question for a more detailed explanation.

$**Response to weakness 2**$: Thanks and you are right that for some instances, the parameter $\delta$ can be small, making it difficult to separate the optimal policy from the sub-optimal ones and leading to a large bound. However, please note that no matter how small $\delta$ can be, the parameter $\delta$ is independent of $\epsilon$. Therefore, even if $\delta$ is very small, as long as we are seeking a solution with high accuracy, i.e., the error term $\epsilon$ is also very small, it could still be desirable to use $\delta$ to substitute $\epsilon$.

$**Response to weakness 3**$: Thanks for the comments! You are right that for some bad instances, the dependencies on other problem parameters can be large. However, these parameters are always independent of $\epsilon$. Therefore, when we want to find a near-optimal policy with a small $\epsilon$, the $\tilde{O}(1/\epsilon)$ bound is desirable even if the dependencies on other parameters are large. Please refer to our response to your question below for more detailed explanations.

$**Response to weakness 4**$: You are right that it is better to conduct some numerical experiments to support our results. Due to the time limit, we conduct basic experiments. Please refer to the ``global response'' for more details on our numerical experiments.

$**Response to the question**$: Thank you so much for the question which allows us to provide further clarifications! Please note that though our bound has some additional dependencies on the problem parameters, they are independent of the accuracy level $\epsilon$. To be specific, for a problem instance $I$, denote by $C_1(I)$ the constant term in our bound. Then, our sample complexity bound is $C_1(I)\cdot\log^2(1/\epsilon)/\epsilon$ on the instance $I$. The worst-case sample complexity bound established in the previous literature is $C_2/\epsilon^2$. Please note that $\epsilon$ is the accuracy level that we can decide. Therefore, for any problem instance $I$, as long as we set $\epsilon$ small enough such that $\epsilon\leq O(C_2/C_1(I))$, our instance-dependent bound $C_1(I)\cdot\log^2(1/\epsilon)/\epsilon$ will be better than the worst-case bound $C_2/\epsilon^2$. That being said, for any problem instance, even if the problem instance is not that favorable such that the constant term in our bound is large, our bound can always be better than the worst-case $O(1/\epsilon^2)$ as long as we set $\epsilon$ small enough, i.e., we are seeking for a policy with low error.