Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback

The authors introduce an algorithm for online learning in CMDP with either stochastic and adversarial constraints while only requiring bandit feedback unlike in prior work. The resulting regret and constraint violation bounds matches prior work with full-feedback and retain the property of not requiring the knowledge of the Slater's parameter. Additionally, the authors show that using a weaker-baseline that only requires a policy to satisfy a constraint at each episode, the propose algorithm achieve sub-linear regret and constraint violations.

The authors present an algorithm for adversarial CMDP. They showed that it achieves $\mathcal{O}(T^{3/4})$ regret and constraint violation both in the stochastic and adversarial setting with modified baselines.

This paper studies the problem of learning a constrained MDP under bandit feedback. The authors propose a policy-based algorithm to reach $\tilde{O}(T^{3/4})$ regret and violations. By assuming that the Lagrangian multiplier is bounded by $\Lambda$, the regret and violation bounded could be improved to $\tilde{O}(\Lambda\sqrt{T})$. In the meantime, the proposed algorithm could also achieve similar regret and violation bounds under the adversarial setting, which is referred as "best-of-both-worlds" property.

This paper proposes an algorithm for online CMDPs with bandit feedback under both stochastic and adversarial constraints settings. Applying an existing policy optimization algorithm to a primal-dual approach to policy optimization, the algorithm achieves $\sqrt{T}$ regret and constraint violation bounds for stochastic constraints under certain conditions, and a $\sqrt{T}$ condition violation under adversarial constraints.

This paper studied the constrained Markov decision process (CMDP) problem where the transition kernel is stochastic unknown, and the reward and costs could be adversarial and stochastic settings. The paper leverages the techniques from the existing literature to address the trade-off between rewards and constraint violations. The theoretical analysis is provided to justify the proposed algorithm.

Dear Reviewers,

we would like to thank you for the effort in evaluating our work. We decided to answer you with an official comment since many of the concerns are shared by most of the Reviewers.

On Condition 2. We apologize for the typo, but the condition required by our algorithm to properly work is $\rho\geq T^{-1/8}H\sqrt{112m}$. We believe that this correction answers many of the Reviewer concerns about the correctness of our results. We already updated the corrected version of the paper.

On the primal regret minimizer

1) Regret bound

It is not correct to state that our primal algorithm cannot be defined as no-regret since $\Xi_t$ can be an increasing function in $T$. Indeed, the primal regret bound depends on the maximum payoff range in the interval (namely, $\Xi_{t_1,t_2}$). Nonetheless, it is standard for online learning algorithms to scale at least linearly in the payoff range, and it is standard in the no-regret definition to consider the payoff range a constant independent of $T$.

2) Why policy optimization?

The advantage of employing policy optimization approach in the primal regret minimizer is twofold.

First of all, this kind of procedures are computationally much more efficient. Indeed, policy optimization updates are solved by employing dynamic programming techniques, namely, the MDP is simply traversed to compute the state-action value function. On the contrary, occupancy-based methods require to solve convex programs at each episode, in order to project over the occupancy-measure decision space. Notice that, while convex programs can be approximated arbitrarily well in polynomial time, they require specific methods to be solved.

Furthermore, policy-optimization approaches are more suitable for guaranteeing the no-interval regret property. Indeed, we managed to show the no-interval regret property by introducing a fixed-share update in the policy optimization primal algorithm. This kind of update cannot be performed on the occupancy measure space, since, due to the transitions estimations, the center of the estimated occupancy measure space could lie outside the decision space induced by the true transition function. That is why, (Stradi et al. 2024) primal algorithm cannot be employed to deal with bandit feedback, by just changing the estimator.

On the dependence of $\rho$ in the theoretical bound

We believe that the dependence on $\rho$ is not a drawback in [Stradi et al. 2024]. Indeed, assuming Slater's condition to hold and attaining theoretical bounds the scales as the inverse of the Slater's parameter is standard in the literature of primal-dual methods. In the following, some references.

["Exploration-Exploitation in Constrained MDPs", 2020]

["Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs", 2023]

["Provably Efficient Model-Free Algorithms for Non-stationary CMDPs", 2023]

["Truly No-Regret Learning in Constrained MDPs", 2024]

In general, it is also standard in the literature to assume the knowledge of the value of $\rho$ (see many of the references mentioned above), which is not the case in our work.

Thus, we focused on relaxing what we believe are the main disadvantages of [Stradi et al. 2024], namely, the full-feedback assumption and the per-round projection in the occupancy measure space.

On the contributions

While our primal-dual scheme follows the one of [Stradi et al. 2024], we believe that the contribution of our work is clear.

First of all, the analysis of the primal regret minimizer is completely independent from [Stradi et al. 2024]. As previosuly specified, occupancy-measure based methods are not suitable for guaranteeing the no-interval regret property. Moreover, even if our primal regret minimizer shares similarity between [Luo et al., 2021], the algorithms are not equivalent. 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 suitability modify the learning rate. Moreover, as highlighted in our work, our algorithm guarantees the no-interval regret property. Proving this result makes our analysis independent from the one of [Luo et al., 2021]. We underline that, showing the no-interval regret property in new settings (in our case, adversarial MDPs with bandit feddback) is of independent interest.

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, capture 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.

We ask the Reviewer to let us know if further discussion on any concern is needed and we hope that we have properly addressed the Reviewer's concerns.

Thanks,

the Authors

This paper considers the online constrained Markov decision problem (CMDP) with bandit feedback under both stochastic and adversarial constraints. The CMDP considered is under the finite horizon episodic setting. The authors propose a best-of-both-worlds algorithm that can handle the considered problem setting with both stochastic and adversarial constraints. Based on the value of a constant $\rho$ that captures the "degree" that Slater's condition is satisfied, $O(T^{1/2})$ or $O(T^{3/4})$ regret/violation can be achieved.

After the author-reviewer discussion, there are still several issue that has yet been cleared.

First, even as a theoretical paper, this work lacks basic numerical evaluation of the result. Second, and most importantly, even after correcting the typo in Cond. 2, it still remains not well-justified. According to the defination, $\rho$ is in fact not a constant. In stochastic setting it relies on $\bar{G}:=(G_1+\cdots+G_T)/T$. In adversarial setting it relies on all $G_t, t\leq T$ and involves a minimum over $t$. That is $\rho$ should in fact be $\rho_T$ and is changing in each step. The current Cond. 2 is misleading in that $\rho$ looks like a constant and Cond.2 "seems to hold when T is large enough". However, as $\rho_T$ is changing in each step (even monotonically decreasing for adversarial setting), there lacks justification on why Cond. 2 should eventually hold.

Overall, the AC would give a rejection to the paper.

Reject