Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization

This paper's algorithm and regret bound rely on a problem-dependent factor $\rho$, which could be small and lead to worse regret. Could the authors provide more technical reasons why $\rho$ is required in this paper? Does this factor also appear in previous papers?

We thank the Reviewer for the opportunity to clarify this fundamental aspect. The dependence on $1/\rho$ is standard in primal-dual formulations (all the works that are mainly related to our, have this kind of dependence, see e.g., [Efroni et al 2020] and [Müller et al. 2024]). Intuitively, it happens since the optimal Lagrange variable of the offline problem is of the order $1/\rho$, and, the magnitude of the Lagrangian variables appears in the theoretical bound of primal-dual procedure. To better understand this, notice that any regret minimizer scales at least linearly in its payoffs range. Thus, since the payoffs range of the primal depends on the maximum of Lagrangian variable, this dependence appears in theoretical bounds.

Nonetheless, differently from [Müller et al 2024], we avoid the $1/\rho$ dependence in the violation bound, while keeping it in the regret only. We believe that this additional result is of particular interest for the community.

Since this is a crucial aspect of our work, please let us know if further discussion is needed.

This paper does not have an empirical comparison. Although this is typically not necessary for a theoretical paper, simulation results like Muller et al. [2024] could be helpful.

We agree that experiments are always beneficial; nevertheless, we underline that in the online CMDPs literature, many works do not have experimental results (e.g., Efroni et al. (2020)).

A conclusion and discussion section is lacking.

We thank the Reviewer for the suggestion. We will surely include a conclusion in the final version of the paper.

Is there any regret lower bound in this setting that is related to the number of constraints $m$?

We are not aware on any lower-bound related to the number of constraints in our setting. Nevertheless, to the best of our knowledge, there are not works which avoid the linear dependence on it, as in our work.

The paper missed a few important related references (e.g., [1] and [2]), where the strong violation has been investigated and better results than this paper have been established. In [1], the OptPess-LP algorithm can satisfy the constraints instantaneously, which seems better than $O(\sqrt{T})$ strong violation. In [2], the paper proposed a model-free method to achieve $O(\sqrt{T})$ strong violation. It would be better to discuss these papers in detail and highlight the differences.

We thank the Reviewer for the suggestion. Indeed, we will include both the papers mentioned by the Reviewer in the final version of the paper, including the following discussion.

Specifically, while [1] studies CMDPs, their OptPess-LP algorithm assumes the knowledge of a strictly feasible solution. This assumption is non-practical in many real-world scenarios where the constraints are not known. Moreover, we remark that their approach is LP-based and not primal-dual, neither policy-optimization based.

As concerns [2], as pointed out in [Müller et al, 2024], the algorithm proposed by the authors achieves $\widetilde{O}(\sqrt{T})$ strong violation when allowed to take $\Omega(d^{L-1}T^{1.5L}\log(|A|)^L)$ computational steps in every episode. Differently, in our work, as in [Müller et al, 2024], we focus on polynomial-time algorithms that achieve a strong regret and violation guarantee.

Since these aspects are crucial, please let us know if further discussion is needed.

The algorithm requires Slater's condition and the knowledge of Slater's constant $\rho$, which is usually not practical in most critical applications. Besides, the regret is in the order of $O(1/\rho),$ it could be problematic when $\rho$ is close to zero.

As concerns the Slater's condition assumption and the knowledge of $\rho$, these requirements are standard for primal-dual methods. Indeed, both [Efroni et al. 2020] -- for the primal-dual algorithm -- and [Müller et al. 2024] make the aforementioned assumptions. Intuitively, the Slater's condition is necessary, since, otherwise, the otpimal Lagrangian variable could be unbounded, preventing any kind of regret guarantees for primal-dual methods. As concerns the knowledge of $\rho$, this can be easily replaced by any lower-bound on $\rho$, or estimated in an online fashion adding a preliminary estimation phase (see Castiglioni et al. 2022, "A Unifying Framework for Online Optimization with Long-Term Constraints").

A similar reasoning also holds for the dependence on $O(1/\rho)$. We remark that this dependence is standard for primal-dual methods (see [Efroni et al. 2020], [Müller et al 2024]). Intuitively, it happens since the optimal Lagrange variable of the offline problem is in general of the order $1/\rho$, and, the magnitude of the Lagrangian variables appears in the theoretical bound of primal-dual procedure. Nonetheless, please notice that, differently from [Müller et al 2024], we avoid the $1/\rho$ dependence in the violation bound. We believe that this additional result is of particular interest for the community.

I understand it is a theory paper; however, including numerical experiments to validate the proposed algorithm would be beneficial. For example, the baselines could be Efroni et al. (2020), [1] and [2].

We agree that experiments are always beneficial; nevertheless, we underline that in the online CMDPs literature, many works do not have experimental results (e.g., Efroni et al. (2020)).

The authors focus on the basic tabular case of constrained MDPs. This method needs further generalization to extend beyond the tabular case.

We agree with the Reviewer that extending our results to non-tabular MDPs is an interesting future work. Nevertheless, we underline that, since the problem tackled by this work has been originally raised by [Efroni et al. (2020)], no better results than $\widetilde{\mathcal{O}}(T^{0.93})$ regret and violation have be shown even in the tabular setting. Thus, we believe that our result (which improves the bounds to $\widetilde{\mathcal{O}}(\sqrt{T})$) is still of fundamental importance for the community.

It would be helpful if the authors could clarify the motivation behind the techniques used in the proposed algorithm. Notably, the standard primal-dual policy optimization suffers the oscillation issues, potentially causing linear strong regret and constraint violation.

We thank the Reviewer for the precious observation and for the opportunity to clarify this aspect of our work. The main advantage of our algorithm compared to existing primal-dual methods is that we somehow fix the Lagrangian variable depending on the policy chosen by the primal algorithm. To better understand this aspect, imagine a Markov decision process where the reward, the constraints and the transitions are fixed and known to the learner. Thus, we run a primal-dual procedure which does not employ any upper/lower confidence bound on the unknown variables (since all of them are known). In such a setting, standard primal-dual methods work by iteratively playing a Lagrangian game between the primal variable (the policy) and the dual ones: This leads to instability since no-regret adversarial procedures (employed for both the primal and the dual) would cycle around the equilibrium (namely, the optimal solution), as known from many results in equilibrium computation theory (see, e.g., "Prediction, learning, and games", Cesa-Bianchi and Lugosi 2006). On the contrary, our primal-dual scheme does not allow the Lagrangian variable to move at a rate of $1/\sqrt{T}$ (as for any primal-dual method which employ an adversarial regret minimizer for the dual), but it simply chooses between the maximum reasonable Lagrangian variable and the minimum one.

We will surely include this discussion in the final version of the paper. Since it is a crucial aspect of our work, please let us know if further explanation is necessary.

The proposed algorithm employs an existing adversarial policy optimization oracle to update the policy. The policy optimization oracle is designed in the adversarial setting, while the constrained MDP problem assumes stochastic rewards, costs, and fixed transitions. It would be helpful if the authors could explain the rationale behind this choice.

In primal-dual methods, it is standard to employ adversarial regret minimizers since the Lagrangian loss is adversarial for both the primal and the dual. To understand this, notice that, even if the rewards, the constraints and the transitions were deterministic, the Lagrangian function encompasses both the policy and the Lagrangian variables, which are selected by the algorithm and thus adversarial by construction.

Please let us know if further discussion is necessary.

The adversarial policy optimization oracle minimizes the average type regret. It would be helpful if the extra technique to obtain a tighter regret bound can be highlighted.

We thank the Reviewer for the insightful comment and for the opportunity to clarify this aspect. It is important to underline that the average type of regret is computed w.r.t. the loss given to the primal algorithm. Notice that, this loss is built as the Lagrangian function employing upper bound on the rewards and lower bound on the constraints. Thus, we can see the loss as somehow deterministic, up to confidence bounds term (which shrinks sublinearly) and up to the Lagrangian variables, which are properly selected to make the primal avoid violations. Then, notice that average type of regret on deterministic functions coincides with the positive one, since it is not possible to perform better than the offline optimum.

Since this is a crucial aspect, please let us know if further discussion is necessary.

What is the role of the probability distributions in line 129 in algorithm?

We are not sure to have properly understood the question. The reward and constraint distributions in line 129 are the ones that generate the feedback for our algorithm, that is, at each episode the learner observes a sample from those distributions for the path traversed in the CMDP.

How large the margin $\rho$ is? What is the practical implication when it is infinitely small?

$\rho\in[0,L]$. When $\rho$ is arbitrary it may worsen the regret bound of our algorithm. Nonetheless, it is fundamental to take into account two crucial aspects. First, the dependence on $\rho$ for both regret and violation is standard in primal-dual formulations (all the works that are mainly related to our have this kind of dependence, see, e.g., [Efroni et al 2020] and [Müller et al. 2024]). Intuitively, it happens since the optimal Lagrange variable of the offline problem is in general of the order $1/\rho$, and, the magnitude of the Lagrangian variables appears in the theoretical bound of primal dual-procedure. Second, differently from [Müller et al 2024], we avoid the $1/\rho$ dependence in the violation bound. We believe that this additional result is of particular interest for the community.

Is it efficient to run the adversarial policy optimization oracle?

We thank the Reviewer for the opportunity to clarify this aspect. The efficiency is one of the key advantages of our adversarial policy optimization procedure. Indeed, the update can be performed by employing dynamic programming techniques. Being a policy optimization approach allows to avoid the employment of occupancy-measure based methods which require projections to be performed at each episode (which, on the contrary, are highly inefficient). We refer to [Luo et al., 2021. "Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses"] for further details.

Can the authors point out the new analysis that avoids the oscillation issue in typical primal-dual methods or compare their key analysis ideas?

Please refer to the second answer.

Thank you for the response. Since the response addresses my concerns, I am inclined to raise my score.

This paper only deals with finite-horizon episodic MDPs with bandit feedback, which is a more restrictive setting than Efroni et al. (2020) and Müller et al. (2024). It seems a little unfair to directly compare against those algorithms that do not require bandit feedback.

We believe there is a possible misunderstanding. Both [Efroni et al. 2020] and [Müller et al. 2024] work under bandit feedback as our paper, namely, observing the rewards and constraints along the path traversed during the episode. Notice that bandit feedback should not be seen as a strong requirement; indeed, it is standard in the online learning (and online RL) literature. To summarize, our work closes the open problem raised by [Efroni et al. (2020)] and left open by [Müller et al. (2024)], for the setting studied by those specific works. Since this is a crucial aspect of our work, please let us know if further discussion is necessary.

The algorithmic contribution is limited since $`CPD-PO`$ largely builds upon $`PO-DB`$, only adding a simple binary dual update scheme.

We believe that this is indeed a point in favor of our algorithm. Indeed, any primal-dual algorithm employs an adversarial-kind of update for the primal (while dual methods employ UCB for the primal). This also holds for [Efroni et al. 2020] and [Müller et al. 2024], where the authors simply explicited the multiplicative-weight update. We decided to make our primal-dual scheme more general, namely, to rely on an existing algorithm for the primal regret minimizer, so that, in future, our primal-dual scheme could be instantiated with a different policy-optimization primal algorithm, in order to attain better regret and violations guarantees. Additionally, we believe this choice should improve the readability of our work.

Nonetheless, we remark that the novelty of a primal-dual method generally relies on the specific Lagrangian formulation of the problem and on the primal-dual scheme employed. We believe that, since our primal-dual scheme is novel (e.g., employing UCB on the Lagrangian variable is a novel technique), the algorithmic novelty should be evaluated positively.

The algorithm seems intractable since it requires the exact value of $\rho$, which is generally unavailable in practice. It would be much better if it can work with only an upper/lower bound of $\rho$, which does not seem to be the case here.

We thank the Reviewer for the opportunity to clarify this aspect. We first underline that the requirement on $\rho$ is standard in the literature of primal-dual methods (e.g., [Efroni et al. 2020] and [Müller et al. 2024]). Nonetheless, our algorithm works for any lower-bound on $\rho$. Indeed, it is possible to substitute $\rho$ with its lower-bound $\widehat{\rho}$, in Line 7 of Algorithm 2 (in the choice of $\lambda_t$) and all the results still hold, since, a greater Lagrangian variable does not preclude the possibility to achieve small violations. Nevertheless, please notice that, in such a case, the regret would scale as $1/\widehat{\rho}$. To conclude, we underline that there exist works which show how to introduce a preliminary estimation phase to estimate $\rho$ in an online fashion (see [Castiglioni et al. 2022, ``A Unifying Framework for Online Optimization with Long-Term Constraints"]).

Suggestions on writing and typos

We thank the Reviewer for the suggestions. We will surely include them in the final version of the paper.

Is $\tilde{\mathcal{O}}(L^5)$ the optimal dependency we can expect here (where $L$ is the horizon length)?

We thank the Reviewer for the questions. We do not believe that the dependence on $L$ is tight. We leave as interesting open problem to develop an algorithm which attains tight regret and violation in any constant. Nevertheless, we believe that an improvement from $\widetilde{\mathcal{O}}(T^{0.93})$ to $\widetilde{\mathcal{O}}(\sqrt{T})$ should be evaluated positively.