Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs

Response:

We thank the reviewer's positive comments. Our responses to your answers can be found below.

Weakness 1 and Q1. Assumption 2 and 5 means when the policy deviates from the optimal policy, then either the reward value function or the utility value function, or both should also deviate from those under the optimal policy. We believe this is a reasonable assumption and should hold for most CMDPs.

Weakness 2 and Q4. As the reviewer correctly pointed out that the results of this paper hold when we replace Triple-Q with any online, model-free CMDP algorithm with sublinear regret and constraint violation. PRI can be viewed as a ``meta-algorithm'' that builds on any model-free CMDP algorithm with sublinear regret and constraint violation to achieve $\tilde{O}(\sqrt{K})$ regret and constraint violation and to output a single stochastic policy.

Weakness 3. For the synthetic CMDP simulation result, we indeed show that the algorithm finds a policy with cumulative reward 1.57301 and cumulative utility 2.00008. The cumulative reward and cumulative utility under the optimal solution are 1.57306 and 2, respectively. This comparison is given at the beginning of page 9. We will further highlight it in the revision.

Q2. The uniqueness is needed so that after the pruning phases, all stochastic decisions of the optimal policy are correctly identified. We note that this assumption is not needed and is relaxed in Section 6. We present this special case phase first for readability. Focusing on the special case where the problem has a unique optimal solution allows us to explain the key ideas behind the algorithm and makes the analysis easier to follow.

Q3. The algorithm outputs a near-optimal solution. We will clarify this in the revision.

We have uploaded a revision that incorporates your comments. The author-reviewer discussion ends in a few days, we would like to know whether you have any additional questions/comments we can address.

Sorry for the confusion. We hope this reply can help you better understand the assumption we make. For any value function, according to the definition of occupancy measure, we have $V^{\pi} = \sum_{h,x,a} r_h(x,a) q_h(x,a) = \mathbf{r} \cdot \mathbf{q^{\pi}}$ The assumption requires there should exist such $c_v$ that $V^* - V^{\pi} = \mathbf{r} \cdot (\mathbf{q^*} - \mathbf{q^{\pi}}) \geq c_v||\mathbf{q^*} - \mathbf{q^{\pi}}||$ $V$ is a linear function of $q$ with a deviation vector $\mathbf{r}$. That means the deviation for every specific direction must be a constant. Besides, with the limitation of constraints and legal transitions, the direction is restricted, which offers a minimum deviation. We assume the lower bound as $c_v$. For example, considering a MDP problem with $H=2, S=2, A=2$. Without loss of generality we only consider MDP while CMDP is the same. Suppose the reward function is: $r_1(1,1) = 1, r_1(1,2) = 2, r_1(2,1) = 1, r_1(2,2) = 2, r_2(1,1) = 1, r_2(1,2) = 2, r_2(2,1) = 1, r_2(2,2) = 2$. No matter what the transition kernel is, the optimal policy should always choose action 2 at any state at any step. Consider an occupancy measure $q_h^{\pi}(x,a)$ of any policy $\pi$, $V^* - V^{\pi} = [\sum_{h,x} q_h^*(x,1) - q_h^{\pi}(x,1)] + [\sum_{h,x} 2(q_h^*(x,2) - q_h^{\pi}(x,2))] = -0.5 ||\mathbf{q^*} - \mathbf{q^{\pi}}|| + ||\mathbf{q^*} - \mathbf{q^{\pi}}|| = 0.5 ||\mathbf{q^*} - \mathbf{q^{\pi}}||$ For $\sum_{h,x} q_h^*(x,1) - q_h^{\pi}(x,1) + \sum_{h,x} q_h^*(x,2) - q_h^{\pi}(x,2) = 0$ and $|\sum_{h,x} q_h^*(x,1) - q_h^{\pi}(x,1)| + |\sum_{h,x} q_h^*(x,2) - q_h^{\pi}(x,2)| = ||\mathbf{q^*} - \mathbf{q^{\pi}}||.$ As long as $c_v \leq 0.5$, this MDP problem satisfies the assumption. On the other hand, actually we can relax the TV distance as $||q^* - q||_{\infty}$ and the proof will still hold. We hope this response can address your concern!

Response:

We thank the reviewer's positive comments. Our responses to your answers can be found below.

Weakness. This is a great question. There may be a trade-off between the regret and constraint violation. However, the algorithm in the paper cannot provide such a trade off by tuning the hyperparameters. This is a great problem for future research.

Q1. In Appendix B, $p_{\min}$ shows up in the lower bound on the occupancy measure (18), and determines the constant associated the probability that stochastic decisions are correctly classified (i.e., probability in (19)).

Q2. Yes, it needs to hold for any greedy policy. We later relax this assumption when we add the multi-solution pruning phase.

We have uploaded a revision that incorporates your comments. The author-reviewer discussion ends in a few days, we would like to know whether you have any additional questions/comments we can address.

Response:

We thank the reviewer's positive comments. Our responses to your answers can be found below.

Q1. Thanks for the suggestion! We will add the discussion on its connection to average reward CMDPs.

Q2. Most BPI algorithms for MDPs are model-based. Exisitng model-free BPI algorithms output a mixed policy that chooses one policy from all $K$ used policy uniformly at random instead of a single stochastic policy. We will add a discussion to the related work.

Q3. $M$ is the same as the $M_q$ defined on page 4. We will clarify this in the revision.

Q4. Sorry for the confusion. The policy initialization is the same as that of Triple-Q. We will clarify this in the revision.

Q5. Good point! We will change it to $\alpha_m$ in the revision.

Q6. The number of optimization variables is $M,$ the number of greedy policies after the pruning phase. $M$ is upper bounded by $2^N,$ where $N$ is the number of constraints. We will clarify this in the revision.

Q7. In practice, we choose small $\epsilon$ and $\epsilon'$ to use. When the assumption does not hold, the algorithm cannot provide the performance guarantees in the paper.

Q8. Can you please elaborate? It is not clear to us if the assumption automatically holds for finite state and action spaces.

Q9. $M$ is bounded by $2^N,$ where $N$ is the number of constraints. Also, $\sum_{i=1}^M a_i = 1$ so the policy identification stage includes $K$ episodes.

Q10. Sorry for the typo. It should be $O(K^{-0.1})$ in the introduction as well.

We have uploaded a revision that incorporates your comments. The author-reviewer discussion ends in a few days, we would like to know whether you have any additional questions/comments we can address.

Response:

We sincerely thank the reviewer for the great comments and questions. Please see our detailed responses below. We believe we have addressed/clarified your concerns/questions. Please let us know if you have any further comments. We would also greatly appreciate if you could reevaluate the rating based on our response. Thanks!

Weakness 1: We thank the reviewer for this comment. While the constraint violation defined in the paper allows the cancellation across episodes, we can guarantee $O(\sqrt{K}\log K)$ violation when the cancellation is not allowed by making some minor modification to the algorithm. In particular, in the policy refinement and identification phases, instead of using the $M$ greedy policy in a round-robin fashion, we can use a mixed policy that chooses policy $m$ with probability $a_m.$ With that modification, we will have

• The Pruning phase consists at most $\sqrt{K}$ episodes, so resulting in at most $O(\sqrt{K})$ violation.
• During the refinement phase, based on the result on page 16 of the supplemental material (Inequality (27)), we have with a high probability that the mixed policy used in the $t$th iteration has a regret bounded by $O(\frac{\log K}{(t-1)\sqrt{K}})$ for $t\geq 2.$ The same result holds for constraint violation, i.e., with a high probability, the constraint violation of the policy used in the $t$th iteration is bounded by $O(\frac{\log K}{(t-1)\sqrt{K}}).$ The $t$th iteration includes $\sqrt{K}$ episodes and the refinement phase includes $\sqrt{K}$ iterations. Therefore, with a high probability, the total violation without canceling across episodes is $O(\sqrt{K}\log K).$
• The mixed policy used in the policy identification phase has a constraint violation bound of $O(\frac{\log K}{\sqrt{K}}).$ The policy is used for $K$ episodes, so the violation is bounded by $O(\sqrt{K}{\log K}).$

Therefore, the total violation is bounded by $\tilde{O}(\sqrt{K})$ by using definition (5) in [Efroni et al., 2020]. We will add this in the revision.

Weakness 2. Our results hold if we replace Triple-Q with any model-free algorithm for CMDPs with sublinear regret and sublinear constraint violation. PRI can be viewed as a ``meta-algorithm'' that builds on any model-free CMDP algorithm with sublinear regret and constraint violation to achieve $\tilde{O}(\sqrt{K})$ regret and constraint violation and to output a single stochastic policy.

Weakness 3. We present the special case phase first for readability. Focusing on the special case where the problem has a unique optimal solution allows us to explain the key ideas behind the algorithm and makes the analysis easier to follow. We can directly present the general case as the reviewer suggested, but it will not save much space because the results we established for the single-solution case are used for the multi-solution case. Therefore, there is minimal repetition in the current structure.

Weakness 4. The reviewer is correct that the result holds only for large $K.$ It is common that regret bounds in bandits and reinforcement learning hold only for large $K.$ Note that order-wise results such as $O(\sqrt{K})$ means it holds when $K$ is sufficiently. Big O notation defines the limiting behavior, i.e. when $K$ goes to infinity.

Weakness 5. Assumption 4 is similar to Assumption 1. It states that if a state-action pair is visited under an optimal policy, then the visiting probability is lower bounded. We believe it is a reasonable assumption and easy to satisfy for problems with finite state and action spaces.

Weakness 6. Thanks for the suggestion! Model-free algorithms require a memory complexity of $O(HSA)$ for maintaining the Q-Table while model-based algorithms require a memory complexity of $O(HS^2A)$ for maintaining all transition probabilities. This is the main advantage of using model-free algorithms in practice. We will clarify this in the revision.

Question about Slater's condition. Yes, the reviewer is correct. We will clarify this in the revision.

We have uploaded a revision that incorporates your comments. The author-reviewer discussion ends in a few days, we would like to know whether your concerns have been addressed and whether you have any additional questions/comments we can address. We again would appreciate if you could reconsider your rating based on our response.

Response:

We thank the reviewer's positive comments. Our responses to your answers can be found below..

Weakness. Thank you very much for the suggestion! We will add the review of Triple-Q in the revision.

Q1. It is a constant a constant for constraint $n,$ not the exponential. We will use $(n)$ in the revision to avoid this confusion. This paper the subscripts are related to time (step index, episode index, etc) so we feel it is better to superscript as the constraint index.

Q2. When $K$ is unknown, we may use the standard doubling trick, i.e., running the algorithm by increasing the assumed horizon from $T$, $2T,$ to $4T,$ $\cdots$ until the process ends.

Q3. Yes, the reviewer is correct that Triple-Q is conservative and aims at achieving zero constraint violation, so it has smaller negative constraint violation. While the conservativeness reduces under Triple-Q, the plot shows the total constraint violation so it continues to decreases. We did not count the number of episodes where the constraint is violated because the constraint violation is defined on the utility-value function, which is the expected total utility, averaged over many episodes.

We have uploaded a revision that incorporates your comments. The author-reviewer discussion ends in a few days, we would like to know whether you have any additional questions/comments we can address.

Both are great questions!

For zero constraint violation, Triple-Q achieves zero violation because the regret is $O(K^{0.8})$, which is higher than $O(K^{0.5})$ regret. The design of the algorithm reduces the constraint violation with a conservative design, which increases the regret but the increase is smaller than $O(K^{0.8})$, so it does not affect the regret in the analysis of Triple-Q. In our paper, the algorithm achieves $O(K^{0.5})$. We tried the conservative design, which, however, increases the regret and makes it higher than $O(K^{0.5})$. By now, we are not sure whether we can use a conservative constraint without increasing the order of regret but we continue working on it.

About your second question, our result is a high probability result, not with probability one. In other words, the regret and constraint violation are both $O(K^{0.5})$ with a high probability $1-O(K^{-0.1})$. This is because we used the Markov inequality to show that the probability that all stochastic decisions are correctly identified with probability $1-O(K^{-0.1})$ (Theorem 1). Conditioned on this event, the regret and constraint violation in the refinement and identification phases are $O(K^{0.5})$ with probability $1-O(K^{-0.5}).$ We would like to comment (1) while the high probability result is not as strong as the probability one result like the results in Triple-Q, this type of result is not uncommon in the literature. (2) We believe this result is not tight and is a result of the Markov inequality. We are currently working on using better concentration result to improve the result.

Dear Area Chair,

Thanks again for this very insightful question! It turns out that there is an easy fix. Instead of running Triple-Q just once at the pruning phase, we can modify the algorithm and run Triple-Q $\log K$ times, independently. We then classify each decision, greedy or stochastic, based on the majority rule. Since each decision (greedy or stochastic) is correctly classified with probability $1-\tilde{O}(K^{-0.1})$ under each run of the Triple-Q, the probability a decision is correctly classified with the majority rule is $1-\tilde{O}(e^{-(\sqrt{K}\log K)/16})$ based on the Chernoff bound, or at least $1-O(\frac{1}{K^2})$ i.e., Theorem 1 now holds with probability $1-O(\frac{1}{K^2}).$ So the large violation occurs with $O(\frac{1}{K^2})$ and its contribution to regret is $O(1/K).$ We also note that Theorem 2 holds with probability $1-O(1/\sqrt{K})$ and Theorem 3 holds with probability $1-O(1/K)$ so the large violation events under Theorem 2 and 3 also do not change the order of the regret. The same idea can be used to the multi-solution case to improve the probability from $1-O(K^{-0.02})$ to $1-O(K^{-2}).$ In that case the probability of bad events can be bounded by $\tilde{O}(K^{-0.5})$, generated from phase 2 and phase 3. With this easy fix, we now can guarantee $\tilde{O}(\sqrt{K})$ regret and constraint violation with probability one as in the Triple-Q paper.

Additionally, we found that zero constraint violation is accomplishable. With a conservative constraint $\rho + \epsilon_\rho$, where $\epsilon_\rho = \frac{2H\sqrt{K} + 4\frac{H}{\sqrt{\epsilon'}}\sqrt{2K\log K} + H^2SAK^{0.25}}{2K+\sqrt{K}logK}$, the violation will be substracted at least $(2K + \sqrt{K}logK) \epsilon_\rho$, which ensures the zero constraint violation based on cancellation. On the other hand, with Slater's condition, we can conclude that $V^* - V^{*,\epsilon_\rho} \leq \frac{H\epsilon_\rho}{\delta}$ ,where $\delta$ is defined in Slater's condition. In that case the additional terms on regret will also be of $\tilde{O}(\sqrt{K})$.

We sincerely thank the area chair for raising this great question, which helped us strengthen the paper!