Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints

We thank the Reviewer for the positive evaluation.

[1]

While in classical RL literature, the only goal is to maximize a given reward function, in the constrained RL literature the problem becomes two-fold. Specifically, the agent has to additionally fulfill $m$ possible constraints while maximizing the reward function. This double objective strongly limits the possibility to explore the decision space.

[2]

As “episode-dependent learning rate” we mean a learning rate which changes over episodes. This is required to attain a linear dependence on the payoffs’ range in the primal algorithm regret bound. Notice that, while attaining a linear dependence on the payoffs’ range is trivial when the payoffs’ range is known, this is not the case when the aforementioned quantity is unknown.

[3]

Algorithm 1 does not have any input/output since it simply shows the interaction between the learner and the environment.

[4]

Condition 2.5 is a condition on the Slater’s parameter of the offline problem $\rho$. Αs is standard for primal-dual methods, when $\rho$ is large enough, it is possible to achieve better regret guarantees, since the Lagrangian space can be bounded by a quantity which is “almost” independent of T.

[5]

We apologize with the Reviewer since Equation (2) contains a typo. The corrected version is $\ell_t(x_h,a_h)=\Gamma_t+ \sum_{i=1}^m \lambda_{t,i}g_{t,i}(x_h,a_h)-r_t(x_h,a_h)$, which is the definition of the lagrangian losses fed to the primal algorithm.

[6]

Algorithm 3 outputs a policy $\pi_{t+1}$ , which is the policy that the primal algorithm suggests to play at the next episode based on the previous observed losses.

[7]

One of the main challenges of our work is to build an algorithm which does not require the Slater’s parameter $\rho$ in input. Notice that, when $\rho$ is known, it is sufficient to optimally bound the Lagrange multipliers decision space to $H/\rho$ in order to have best-of-both-worlds guarantee. Differently, when $\rho$ is not known, it is necessary to resort to different techniques to show that the Lagrange multipliers are bounded during the learning dynamic. We tackle this aspect employing the no-interval regret property of the primal and the dual regret minimizers.

[8]

$OPT^\mathcal{w}$ is an alternative baseline for the setting with adversarial constraints. This baseline is computed considering the optimal fixed policy which satisfies the constraints at each episode (and not only on average). The introduction of this weaker baseline is motivated by the fact that, when competing against $OPT^\mathcal{w}$, it is possible to guarantee sublinear regret and constraints violation simultaneously.

We thank the Reviewer for the effort in evaluating our work.

On the novelty.

We thank the Reviewer for the opportunity to clarify this aspect. In the following, we better highlight the contribution of our work. Indeed, while our primal-dual scheme follows the one of [Stradi et al. 2024] and the primal regret minimizer builds on [Luo et al. 2021], we believe that the contribution of our work is valuable.

Specifically, our analysis and the one in [Luo et al., 2021] are substantially different in two fundamental aspects. First, we show that our algorithm works with a dynamic payoff range, paying a linear dependence only in the maximum range. While this dependence is standard in online algorithms, this happens since the payoff range is known a priori. This is not the case in our setting. To avoid a quadratic dependence on the payoff range, we had to suitably modify the learning rate. Moreover, our algorithm guarantees the no-interval regret property employing the fixed share update. While we agree that the fixed-share update has been shown to work in online convex optimization, we believe that extending this result to MDPs with bandit feedback is valuable.

As a second aspect, notice that all the primal-dual analysis in [Stradi et al. 2024] is designed to work under full-feedback. Indeed, the Lagrangian function given to both the primal and the dual in our work, captures less information that the one in [Stradi et al. 2024], namely, the Lagrangian is built for the path traversed only.

Finally, notice that, differently from any prior work on CMDPs, we complement our analysis studying the regret w.r.t. an optimal solution which satisfies the constraints at each episode. While this baseline is weaker than the first one we propose, it has been largely studied in different settings w.r.t. ours, since it is the only one which allows to be no-regret when the constraints are adversarial. Specifically, this baseline has been studied in online convex optimization with constraints, thus, in single state environments with full-feedback (see, e.g., “Tight Bounds for Online Convex Optimization with Adversarial Constraints”, 2024]). Our results match theirs, showing that $\sqrt{T}$ regret and violations are attainable when only bandit feedback is available and for an MDP structure of the environment. This analysis is novel and independent from prior works.

On the Slater's condition.

The Reviewer is correct, Condition 2.5 implies the Slater’s condition; however the focus of this work is the lack of knowledge of the Slater’s parameter $\rho$ and not achieving theoretical guarantees when Slater does not hold –however, we provide sublinear bounds for this case, too, namely, when Condition 2.5 does not hold–. The motivation for this is that previous works in the literature with bandit feedback require the knowledge of $\rho$ in advance and they assume $\rho$ to be a constant, ignoring the case where $\rho$ is very small (e.g. [1]).

On policy optimization.

The point raised by the Reviewer is surely interesting. While a more rigorous analysis is required to precisely answer the question, our perspective is that technical challenges may arise when dealing with the biased loss estimator. Finally, notice the policy optimization approaches are generally preferred to occupancy measure ones, since occupancy measure based algorithms require convex programs to be solved at each episode. We believe that the aforementioned one is the main justification for policy optimization.

Finally, we want to thank the Reviewer for the additional comments and suggestions. We will surely take them into account in the final version of the paper.

[1] Castiglioni et al. 2022, “A Unifying Framework for Online Optimization with Long-Term Constraints”.

We thank the Reviewer for the positive evaluation.

On Ghosh et al., 2024.

We thank the Reviewer for the interesting point. First, we underline that we use the term best-of-both-worlds referring to the constraints definition. Thus, our algorithm achieves optimal regret guarantees when the constraints are stochastic (and the loss may be adversarial) and when the constraints are adversarial. Notice that our definition of best-of-both-worlds in constrained settings is standard in the literature (e.g., see [1]). (Ghosh et al. 2024) deals with the stochastic reward and constraints setting only, thus their algorithm does not admit adversarial loss as our stochastic setting. Finally, notice that sublinear results employing the positive regret and violation definition does not imply that a better rate can be obtained employing our metrics, thus, our dependence on the number of episodes is still optimal.

On the contribution.

We thank the Reviewer for the opportunity to clarify this aspect. In this work, we design a primal-dual algorithm that does not require the Slater parameter $\rho$ as input, and in addition, it does not need any assumption on $\rho$. Indeed, in the analysis, we study both the case where the Slater condition is verified (Condition 2.5 holds) and the case where the Slater condition is not verified (namely, either $\rho=0$ or too small compared to the horizon). Nonetheless, while the lack of the Slater condition leads to weaker guarantees, most of the difficulties in our analysis arise from the lack of knowledge of the Slater’s parameter $\rho$, which is considerably harder to tackle when the feedback is bandit. In particular the bandit feedback affects the design of the primal algorithm and requires some forms of additional regularization in the learning dynamic like the fixed-share update.

We will surely include a comparison table in the final version of the paper to clarify these aspects.

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

We finally thank the Reviewer for the suggestions and we will surely implement them in the final version of the paper.

[1] Castiglioni et al. 2022, “A Unifying Framework for Online Optimization with Long-Term Constraints”.

We thank the Reviewer for the positive evaluation.

On W1 and Q1.

As shown in [1], computing the maximum state-action occupancy measure among the possible transition probability sets (Line 5 in Algorithm 3) can be solved efficiently via a greedy algorithm. The same reasoning holds for the corresponding minimum and for the bonus quantity (see Luo et al.'21). We finally remark that performing the OMD update over the occupancy measure space (as in occupancy-based methods) would require solving a convex program at each episode, which is considerably heavier than computing upper occupancy bound or bonus terms.

On W2 and Q2.

The algorithm from [Luo et al. ‘21] cannot be employed as our primal regret minimizer, as it is. In particular, our primal regret minimizer must guarantee the no-interval regret property – in order to show that the Lagrangian multipliers are bounded during the learning dynamic –, which requires the introduction of a fixed-share update. To the best of our knowledge, our primal regret minimizer is the first to show no-interval regret property for adversarial MDPs with bandit feedback. Furthermore, we had to improve the dependence of the regret bound on the loss range, introducing a dynamic learning rate. This learning rate is used to improve the dependence on the payoff’s range from a quadratic dependence to a linear one. Indeed part of the complexity of designing the primal algorithm is that the range of the losses cannot be known a priori, as it is a lagrangian loss and therefore proportional to the problem-specific lagrangian multipliers.

On W3.

We agree with the Reviewer that extending the guarantees presented in this paper to model-free approaches scalable beyond tabular CMDPs setting would be of great interest. However, the results presented in this paper are novel even for the simplest tabular case, and we believe this work might be a good starting point for extending the results to more challenging scenarios in future works.

On W4.

Guaranteeing positive violation requires the primal and the dual regret minimizers to attain convergence to the constrained optimum, namely, to have last-iterate convergence to the equilibrium of the Lagrangian game. To the best of our knowledge, no algorithm can guarantee convergence in last-iterate in the setting faced by the primal regret minimizer. Finally, notice that, if future works may find no-regret algorithms with last-iterate convergence on the settings faced by the primal and dual regret minimizers, sublinear positive violation (in the stochastic setting) would directly follow by the analysis of our primal-dual procedure. We underline that the papers provided by the Reviewer focus on stochastic settings only, where it is possible to exploit confidence intervals to estimate both rewards and constraints. Indeed, it cannot be done in our setting, since it would prevent any algorithm to deal with adversarial settings.

[1] Jin et al. 2020, "Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition".