Learning Adversarial MDPs with Stochastic Hard Constraints

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

On the comparison with existing works and [W1]

[A1] focuses on CMDPs with stochastic rewards and constraints, showing how it is possible to achieve $\sqrt T$ regret and violation. The only technique proposed by [A1] which is of interest in our setting is the optimistic safe set estimation, which is employed by SV-OPS.

[A2] and [A3] study the stochastic version of our second scenario. Their randomization techniques cannot work in our second scenario, since in adversarial settings, it is not possible to play the safe policy for a fixed amount of rounds and then switch to an adversarial online learning algorithm on a pessimistic decision space. To see this, notice that pessimistic decision spaces increase over time and that adversarial online learning algorithms do not work on increasing decision spaces in $t$.

Moreover, notice that even if [A3] shows how to obtain constant violation, but this is done employing a weaker version of constraints violation (which allows for cancellations between episodes), thus they are not applicable to our third scenario.

Similarly to [A1], [A4] focuses on CMDPs with stochastic rewards and constraints, showing how it is possible to achieve $\sqrt T$ positive regret and violation. Their techniques cannot be generalized to adversarial settings, since they assume that there exists an underlying reward distribution in their analysis. Moreover, notice that the algorithm proposed in [A4] has an exponential worst-case running time, while our algorithm is polynomial.

To conclude, our paper's main contributions are highlighted as follows. First, we study a novel CMDP setting, encompassing both adversarial losses and hard constraints. Specifically, we focus on three scenarios, which are all novel and cannot be tackled by existing algorithms. The first one is novel in terms of results, while we agree that we combine existing techniques to get our theoretical results. The second and third scenarios are instead novel both in terms of results and in terms of algorithmic techniques. Furthermore, the third scenario has never been studied even in simpler stochastic settings. Finally, we propose a novel lower bound which can be of independent interest, since it applies to the stochastic setting, too.

We will surely include this discussion in the final version of the paper.

[W2]

We agree with the Reviewer that studying CMDPs with infinite state-action spaces is an interesting future direction. Nevertheless, since this is the first work to tackle both adversarial losses and hard constraints, providing a large set of different results, we believe it is still of interest for the community.

[Q1]

As is standard in the adversarial MDPs literature, the performance metrics are computed taking the expectation over policies and transitions. Since S-OPS plays non-Markovian policies, the expected violation is computed taking into account the randomization selected by the algorithm (please refer to Theorem 5.1. for additional details).

[Q2]

Optimistic occupancy measures can be computed in $O(|X|^3|A|^2)$ steps (please refer to Jin et al. (2020) for the associated algorithm pseudocode).

[Q3]

$\lambda_t$ is proportional to the uncertainty the algorithm has on both constraints and transitions. Thus, $\lambda_t$ is greater in the first episodes while converges to $0$ as the learning dynamic evolves.

Since these are crucial aspects of our work, please let us know if further details are necessary. We would be happy to engage in further discussion.

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

W1

We agree with the Reviewer that experiments are always beneficial; nevertheless, we underline that both in the online CMDPs literature and the adversarial MDPs one, many works do not have experimental results (see e.g., Rosenberg et al. (2019b), Jin et al. (2020), Efroni et al. (2020), Stradi et al. (2024b) and many others). Despite the lack of experimental evaluation, many of the aforementioned works (and many others) have been published in top AI conferences, such as ICML.

W2

We thank the Reviewer for the opportunity to clarify this aspect. Please notice that Eq. (2) is a convex program with linear constraints, which can be approximated arbitrarily well in polynomial time. We underline that solving this kind of projection is standard in the adversarial MDPs literature (see e.g., Rosenberg et al. (2019b), Jin et al. (2020)). Similarly, it is standard for adversarial online learning algorithms to require projections to be solved at each episode, even in easier single-state full-feedback settings (e.g., OGD and OMD algorithms).

W3

We thank the Reviewer for the opportunity to clarify these aspects.

Regarding Lagrangian methods, state-of-the-art primal-dual algorithms are not suited to handle any of our scenarios. Broadly, these algorithms can be categorized into two main families: (i) primal-dual methods designed specifically for stochastic settings (e.g., [1], [2], [3]), and (ii) algorithms that address both stochastic and adversarial CMDPs (e.g., [4], [5]). All the algorithms in the first class assume that the losses/rewards are stochastic in nature, thus, their techniques and results are not applicable to our three scenarios. For the latter, [4], [5] achieve $\sqrt T$ regret and violation when the constraints are stochastic and the losses adversarial. Nevertheless, notice that their violation definition allows per-episode violations to cancel out, thus they employ a weaker violation definition w.r.t. ours. Moreover, the aforementioned papers assume Slater’s condition to hold, which is not the case for our first scenario. Our second and third scenarios have never been tackled employing primal-dual methods even in simpler stochastic rewards settings.

As concerns model-based techniques, our work is the first to tackle adversarial losses. Additionally, our work is the first one to provide constant violation bounds (employing our positive violation definition) without assuming the knowledge of a safe policy, even considering stochastic settings. Finally, existing model-based algorithms tailored for stochastic versions of our second scenario do not work in adversarial settings, and cannot be easily extended due to a different randomization approach ([6], [7]). For further details on these aspects please refer to the next answer.

We will surely include this discussion in the final version of the paper.

W4

We thank the Reviewer for the opportunity to better discuss the algorithmic components of our techniques.

SV-OPS employs the optimization approach of Jin et al. (2020) on optimistic safe decision spaces. Optimistic safe decision spaces were originally introduced by [1] in the context of stochastic CMDPs. The idea behind S-OPS and its randomization approach is novel in the CMDPs literature. We acknowledge that there exist other forms of randomization which are suitable for stochastic CMDPs (see, e.g., [6], [7]), but they fail in working in adversarial settings. To see this, notice that the algorithms presented in [7], [8] play the safe policy for a fixed amount of rounds and then resort to pessimistic decision spaces which are increasing in $t$. It is well-known that adversarial online learning algorithms do not work on increasing decision spaces. Thus, their approach cannot be easily generalized to tackle adversarial loss. BV-OPS employs techniques which are completely novel in the literature.

We hope to have properly addressed the Reviewer concerns. Please let us know if further discussion is necessary.

[1] Efroni et al (2020), “Exploration-Exploitation in Constrained MDPs”

[2] Müller et al. (2024), “Truly No-Regret Learning in Constrained MDPs”

[3] Stradi et al. (2024), “Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization”

[4] Qiu et al. (2020), “Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss.”

[5] Stradi et al. (2024), “Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints”

[6] Liu et al. (2021), “Learning policies with zero or bounded constraint violation for constrained mdps”

[7] Bura et al. (2022), “DOPE: Doubly optimistic and pessimistic exploration for safe reinforcement learning.”

We thank the Reviewer for the positive evaluation and for the interesting question. Indeed, this is an interesting future direction, nonetheless, we believe that it would be highly non-trivial to employ a primal-dual approach to solve any of the scenarios we study, due to the following reasons. For the first scenario, primal-dual methods generally require Slater’s condition to hold, which is not the case of our algorithm. Moreover, primal-dual methods generally fail to remove the $1/\rho$ dependence in the regret and violation bound, thus achieving worse regret and violation guarantee than SV-OPS. Finally, notice that primal-dual methods developed for adversarial loss settings do not guarantee sublinear positive violation, but employ a violation definition where the cancellations are allowed (see, e.g., Stradi et al. (2024b)). As concerns the second and third scenario, we believe that the randomization with the strictly feasible policy requires an optimistic safe-set estimation, which is generally not employed in primal-dual methods.

Finally we want to underline that solving this kind of projection is standard in the adversarial MDPs literature (see e.g., Rosenberg et al. (2019b), Jin et al. (2020)). Similarly, it is standard for adversarial online learning algorithms to require projections to be solved at each episode, even in easier single-state full-feedback settings (e.g., OGD and OMD algorithms).

Please let us know if further discussion is necessary.

We thank the Reviewer for the positive evaluation of the paper.

Question 1.

We thank the Reviewer for the opportunity to clarify this aspect. Indeed, there is no contradiction between [1] and our lower bound, since our lower bound holds for our second and third scenario only, namely, when we aim to guarantee a violation of order $o(\sqrt{T})$, such as $0$ or constant violation. In our first scenario, we do not assume Slater's condition and we guarantee $O(\sqrt{T})$ regret and violation, thus, there is no contradiction w.r.t. [1].

Question 2.

We agree with the Reviewer that experiments are always beneficial; nevertheless, we underline that both in the online CMDPs literature and the adversarial MDPs one, many works do not have experimental results (see e.g., Rosenberg et al. (2019b), Jin et al. (2020), Efroni et al. (2020), Stradi et al. (2024b) and many others). Despite the lack of experimental evaluation, many of the aforementioned works (and many others) have been published in top AI conferences, such as ICML.

Question 3.

We thank the Reviewer for the opportunity to clarify this aspect. Please notice that Eq. (2) is a convex program with linear constraints, which can be approximated arbitrarily well in polynomial time. We underline that solving this kind of projection is standard in the adversarial MDPs literature (see e.g., Rosenberg et al. (2019b), Jin et al. (2020)). Similarly, it is standard for adversarial online learning algorithms to require projections to be solved at each episode, even in easier single-state full-feedback settings (e.g., OGD and OMD algorithms).

We finally thank the Reviewer for the other comments and suggestions, we will surely update the final version of the paper taking them into account.