A Best-of-Both-Worlds Algorithm for MDPs with Long-Term Constraints

Both the algorithms and results in (Castiglioni et al., 2022b) and this paper look similar and the only difference I see is that this paper extends to MDP. So I am doubtful about the technical contributions of this paper. I would suggest the author highlighting the novelty of this work. What are the main technical contributions of this paper (other than extending (Castiglioni et al., 2022b) to MDP)?

We thank the Reviewer for the opportunity to clarify these fundamental aspects. We will surely strengthen the original contribution section in the final version of the paper including the following discussion.

We believe that our work provide quite novel techniques with respect to (Castiglioni et al., 2022b). Castiglioni et al. focus on general constraints but they assume to know the feasibility parameter $\rho$. Please notice that, assuming the knowledge of $\rho$ is arguably an unreasonable assumption in real-world scenarios, since it almost never happens to know a-priori the performances, in terms of violation, of the strictly feasible solution. Castiglioni et al. were able to relax this assumption only in the stochastic setting, while in our paper we relax this assumption in both the adversarial and the stochastic setting. This is a non-trivial task and indeed this assumption is present in all subsequent works on general constraints (see, e.g., ["Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression.", 2023]).

Precisely, even if our work is related to (Castiglioni et al., 2022b), the following technical contributions of our paper are novel with respect to the contributions in (Castiglioni et al., 2022b):

i) We show how to ensure that the Lagrange multipliers are kept small without any explicit constraint and any knowledge of the value of the strictly feasibility parameter $\rho$. To do so, we are the first to employ "no-interval regret" properties for the primal and dual regret minimizers. The idea of using no-interval regret minimizers allows us to prove that the Lagrange multipliers are automatically bounded during the learning dynamic, while previous works with adversarial constraints need to bound the Lagrange multipliers a priori.

ii) We design the first adaptive regret minimizer for adversarial MDPs. State-of-the-art MDPs online learning techniques rely on OMD-like (with KL regularizer) optimization updates, which make the no-interval regret property unattainable. Resorting to OGD-like updates and changing the theoretical analysis allows us to build an algorithm which is no-regret for every interval of the learning dynamic, thus having more guarantees in terms of stability. The aforementioned achievement may push the online learning research area to develop more stable regret minimizer even in complex environments such as Markov decision processes, since the classical static regret definition might not always make sense, especially when the environment is non-stationary such that there is no single fixed action that performs well in every interval of the horizon.

To summarize, even if some results seem to be in common with (Castiglioni et al., 2022b), the theoretical analysis are quite independent. Indeed, as previously specified, the main theoretical effort of our work lies in showing the bound on the Lagrangian multiplier given the no-interval regret property of both the primal and the dual regret minimizers. These kind of analysis cannot be found in (Castiglioni et al., 2022b).

Can your results be generalized to discounted MDP or Stochastic Shortest Path easily?

Our setting without constraints is sometimes referred to as the stochastic shortest path problem in the literature. Thus, for the stochastic shortest path problem, there is no need of generalization. On the contrary, our techniques cannot be generalized to infinite horizon (thus, discounted) MDPs. Nevertheless, to the best of our knowledge, there are not works on online learning in adversarial MDPs with infinite horizon (when the transitions are not known), even in the simpler unconstrained setting.

The term 'best-of-both worlds' is somewhat misleading. In the context of bandits and RL, 'best-of-both-worlds' typically implies achieving $\sqrt{T}$ regret in the adversarial setting versus $\log(T)$ regret in the stochastic setting. This paper only demonstrates a $\sqrt{T}$ rate in a fully stochastic setting when condition 2 holds. Furthermore, the 'best-of-both-worlds' literature in CMDPs is not discussed at all. Additionally, many algorithms can achieve zero constraint violations. Therefore it's unclear if this is the best achievable result.

We agree with the Reviewer that the term 1best-of-both worlds' has a different meaning in the unconstrained online learning literature. Nevertheless, in constrained online optimization the definition of 'best of both world' is the one given in our paper (e.g, see ["The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems", 2021], Castiglioni et al. (2022a), and Castiglioni et al. (2022b)). We believe that our work is more connected with the area of constrained optimization in which our definition of best-of-both-worlds is standard. Nonetheless, we will clarify this aspect in the final version of the paper.

As concerns the 'best-of-both-worlds' literature in CMDPs (according to the definition of 'best-of-both-worlds' used in constrained online optimization or according to definition commonly used in unconstrained MDPs), it is not discussed in the paper since, to the best of our knowledge, it does not exist. If the Reviewer can provide us some references, we are glad to add them in the final version of the paper. Indeed, our work is the first to consider fully-adversarial constraints in CMDPs, and thus the first 'best-of-both-worlds' work. In order to further clarify the distinction with the literature on 'best-of-both-worlds' algorithms in unconstrained online learning, we will add a discussion on papers belonging to the latter literature in the final version of the paper.

Regarding achieving a $\mathcal{O}(\log(T))$ regret bound in the stochastic setting, it has been shown that $\mathcal{O}(\log(T))$ regret bounds are not achievable online optimization with constraints. Previous works on this topic (see, e.g., ["The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems", 2021]) show a lower bound $\Omega(\sqrt{T})$ on the regret even in simple instances. As a consequence, all the best-of-both-worlds algorithms for similar problems have a $\mathcal{O}(\sqrt{T})$ regret in the stochastic setting (see, e.g., ["The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems", 2021], ["A Unifying Framework for Online Optimization with Long-Term Constraints", 2022]). We acknowledge that there are some works that deal only with the stochastic setting (i.e., do not provide best-of-both-worlds guarantees) and provide $\mathcal{O}(\log(T))$ regret; this happens due to quite strong assumptions on the problem, such as assuming the the optimal solution is deterministic (see ["Bandits with knapsacks beyond the worst case", 2021]).

As concerns results achieving zero constraint violation, we believe that the Reviewer is referring to ["Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs'', 2021]. In this paper, the authors assume to know a strictly feasible policy to employ in the first episodes, namely, when the uncertainty about the environment is high. We can further elaborate about this point if the Reviewer prefers to. In general, there are works that provide stronger results for stochastic or adversarial CMDPs, but these works have much stronger assumptions.

In the unconstrained case, several works have discussed bandit feedback and constraint violation without cancellation. However, the authors have not provided much insight into the challenges of removing these assumptions and studying the stronger setting.

As it is usual in the online learning literature, both for single state and multi state environments, when a novel problem is proposed, it is first studied in the full-feedback setting; then, it is extended to the bandit setting, when only the realizations are observed (i.e. from Hedge to Exp3 ["A modern introduction to online learning", 2019] and, in case of MDPs, from ["Online convex optimization in adversarial Markov decision processes", 2019] to ["Online shortest path with bandit feedback and unknown transition function", 2019] ).

Nevertheless, to extend our result to bandit settings, it is sufficient to develop a regret minimizer for MDPs with bandit feedback which guarantees no-interval regret. Then, the result will follow immediately from our analysis. Nevertheless, to develop no-interval regret minimizer for adversarial MDPs with bandit feedback is a non-trivial challenge. We believe that future work can build on this paper and design algorithms with less informative feedback.

As concerns the constraints without the cancellation, primal-dual methods fails in achieving sublinear violation without cancellations (we can further discuss about the technical challenge). The algorithms which achieves sublinear violation without cancellation generally resort to confidence bound, which cannot work in the adversarial setting.

The regret bounds depend on condition 2. How is this related to the Slater condition, and which one is stronger? If they are not closely related, what happens if condition 2 doesn't hold but the Slater condition does? In such a case, your algorithm cannot achieve results of the same order as an algorithm using the Slater condition. How can we even say if it is the best of both worlds?

Formally, Condition 2 is slightly stronger than the Slater's condition. However, all the previous works assume that $\rho$ is a constant and simply hide the dependence on $\rho$ in the regret bound. For instance, if the slackness parameter $\rho$ is really small, e.g., $1/T$, the regret bound is superlinear in $T$! (see, e.g., the regret bound without big O notation in ["Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss", 2021]). We extend this result and provide an analysis that holds even in degenerate cases in which $\rho$ is arbitrary small. If the Reviewer desires a classical (and weaker) regret bound, it is sufficient to consider only the proof of the case in which Condition 2 holds (even if the condition does not hold). In this way, we have a bound that depends on $\rho$ and $\sqrt{T}$, and assuming that $\rho$ is constant (since it can be hidden in the big-O notation as in previous works), a $\mathcal{O}(\sqrt{T})$ regret bound. To conclude, our results are actually stronger than the one in previous works when slackness parameter $\rho$ is very small and comparable otherwise.

All the theoretical results are standard, and the use of projection to bound the dual variable for boundedness is not surprising.

Most of the works on constrained MDPs (and constrained online optimization) exhibit quite similar approaches, and the difference in the algorithm and analysis are always a bit subtle. For example, comparing ["Exploration-Exploitation in Constrained MDPs", 2020] and ["Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss", 2020], it easy to see that both the papers employ primal-dual techniques. Similar reasoning holds for the constrained online learning literature, where ["Online Learning with Knapsacks: the Best of Both Worlds", 2022], ["Adversarial bandits with knapsacks", 2022] and ["A unifying framework for online optimization with long-term constraints", 2023] employ almost the same algorithm. Nevertheless, these works appear in top venues. The reason why all these works might look similar at a first glance is that they usually present a generic primal dual template that is then instantiated with different subroutines. However, the specific subroutines and the analysis are where the real contribution of these works lies.

We strongly believe that compared to the homogeneity of the algorithms and proof techniques of previous works, we can claim that our algorithms and analysis is quite different from previous works. For instance, we are the first to use regret minimizers with the interval regret property in MDP problems, and, thus, to automatically prove a bound on the Lagrange multipliers when the constraints are adversarial, while the projection on the restricted Lagrangian space is used only in extreme scenarios, namely $\rho$ is particularly small. We believe that this cannot be consider a trivial extension. In the following, we describe more in detail the contributions of our paper.

We developed the first best-of-both-worlds algorithm for CMDPs which works without knowledge of the feasibility parameter $\rho$. We introduce a complexity condition (namely, Condition 2), which indicates how hard the underlying constrained optimization problem is. Related works, such as ("Exploration-Exploitation in Constrained MDPs", 2020), implicitly assumes the aforementioned condition, inserting the feasibility parameter $\rho$ directly in the regret bound.

When the condition holds, we automatically prove a bound on the Lagrangian multiplier learning dynamic thanks to the no-interval regret properties guaranteed by both the primal and the dual regret minimizers. Related works in simpler single-state constrained optimization do not bound the multiplier employing the no-interval regret property, since they assume knowledge of the feasibility parameter $\rho$, which is not reasonable in practice. Given the bound, we show $\tilde{\mathcal{O}}(\sqrt{T})$ violation in both the stochastic and the adversarial setting, $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound in the stochastic setting and fraction of the optimal rewards guarantee in the adversarial one.

Differently from the state-of-the-art, we extended the analysis to cases where Condition 2 is not satisfied. Precisely, our algorithm guarantees sublinear regret and violation in the stochastic setting even in the hardest scenario. This result follows from the choice of instantiating the dual regret minimizer in a restricted decision space, namely $\mathcal{D}=[0,T^{1/4}]^m$, which guarantees the optimal trade-off between regret bound and violation (both of order $\tilde{\mathcal{O}}(T^{3/4})$).

From an algorithmic perspective, our algorithm is the first in the CMDP research area to explicit instantiate two black-box regret minimizers in order to solve the underlying Lagrangian game. This makes our work more general, since both no-regret algorithms could be substituted with algorithms with the same properties. Currently, our primal algorithm is the only one for Online MDPs to achieve the weak no-interval regret property, but in future it could be updated with a more efficient version.

Moreover, our algorithm is the first one to employ OGD on a decision space which is the occupancy measure space, while in the literature Multiplicative Weights is standard. This key modification helped us to achieve the weak no-interval regret property. The primal regret minimizer employs an adaptive learning rate, which depends on the maximum loss encountered in the learning dynamic, that is not standard in the Online MDP literature. This trick helped us to achieve better regret guarantees.

Finally, our algorithm does not employ policy mixing techniques, nor exploration bonus ("Exploration-Exploitation in Constrained MDPs", 2020), which leads to a more understandable learning dynamics.

The technical contributions appear somewhat limited, as the algorithm follows a standard framework in CMDPs, and its dependence on $\rho$ is highly motivated by prior work [1].

We believe that the Reviewer is missing some crucial aspects of our technical contributions. Let us remark that our paper is the first one in the literature to address the problem with adversarial constraints in CMDPs, which is the hardest possible setting. Moreover, our paper does so by proposing a novel best-of-both-world algorithm that is able to seamlessly handle adversarial/stochastic rewards and constraints, and this algorithm is the first of its kind in CMDPs. Our algorithm is based on a primal-dual framework that is fundamentally different from the techniques usually employed in the literature on CMDPs, as having to deal with adversarial constraints prevents us from using any kind of confidence bounds, which are instead generally used in the literature. Moreover, even when primal-dual techniques are employed in place of techniques based on confidence bounds, the analysis has never been extended to adversarial constraints.

As concerns the differences of our work with respect to [1], in the following we detail the several aspects in which the two works depart. Crucially, [1] focuses on general constraints but they assume to know the feasibility parameter $\rho$. Then, it is possible to upper bound the Lagrange multipliers with $\frac{1}{\rho}$. Please notice that, assuming the knowledge of $\rho$ is arguably an unreasonable assumption in real-world scenarios, since it almost never happens to know a priori the performances, in terms of violation, of the strictly feasible solution. Castiglioni et al. were able to relax this assumption only in the stochastic setting, while in our paper we relax this assumption in both the adversarial and the stochastic setting.

Precisely, the following technical contributions of our paper are novel with respect to the contributions in [1]:

i) We show how to ensure that the Lagrange multipliers are kept small without any explicit constraint and any knowledge of the value of the strict feasibility parameter $\rho$. To do so, we are the first to employ no-interval regret properties for the primal and dual regret minimizers. The idea of using no-interval regret minimizers allows us to prove that the Lagrange multipliers are automatically bounded during the learning dynamic, while previous works with adversarial constraints need to bound the Lagrange multipliers a priori.

ii) We design the first adaptive regret minimizer for adversarial MDPs. State-of-the-art MDPs online learning techniques rely on OMD-like (with KL regularizer) optimization updates, which make the no-interval regret property unattainable. Resorting to OGD-like updates and changing the theoretical analysis allows us to build an algorithm which is no-regret for every interval of the learning dynamic, thus having more guarantees in terms of stability. The aforementioned achievement may push the online learning research area to develop more stable regret minimizers even in complex environments such as Markov decision processes, since the classical static regret definition might not always make sense, especially when the environment is non-stationary such that there is no single fixed action that performs well in every interval of the horizon.

To summarize, even if some results seem to be in common with [1], the theoretical analysis are quite independent. Indeed, as previously specified, the main theoretical effort of our work lies in showing the bound on the Lagrangian multiplier given the no-interval regret property of both the primal and the dual regret minimizers. This kind of analysis cannot be found in [1].

For additional details on the other technical challenges faced in our paper and its novelty over prior works, we invite the Reviewer to read our answer to the third question.

Is it possible to achieve the best of both worlds guarantee for bandit feedback? Any conjecture?

We conjecture that it is possible to achieve the best of both worlds guarantee for bandit feedback. Precisely, to extend our result to bandit settings, it is sufficient to find a regret minimizer for adversarial MDPs with bandit feedback which guarantees no-interval regret. Then, the result will follow immediately from our analysis. Nevertheless, developing a no-interval regret minimizer for adversarial MDPs with bandit feedback is a non-trivial challenge. We believe that future work can build on this paper and design algorithms with less informative feedback.

Is it possible to achieve the best of both worlds guarantee with logarithmic stochastic regret bound?

We thank the Reviewer for the opportunity to clarify this fundamental aspect. In the setting we propose, it is not possible to achieve $\mathcal{O}(\log(T))$ regret and violation in the stochastic setting. Indeed, previous works (see, e.g., ["The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems", 2021]) show a lower bound $\Omega(\sqrt{T})$ on the regret even in simple instances. As a consequence, all the best of both worlds algorithms for similar problems have a $\mathcal{O}(\sqrt{T})$ regret in the stochastic setting (see, e.g., ["The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems", 2021], ["A Unifying Framework for Online Optimization with Long-Term Constraints", 2022]). We will better highlight the difference with this other best of both worlds definition in the final version of the paper. We acknowledge that there are some works that deal only with the stochastic setting (i.e., do not provide best of both worlds guarantees) and provide $\mathcal{O}(\log(T))$ regret; this happens due to quite strong assumptions on the problem, such as assuming that the the optimal solution is deterministic (see ["Bandits with knapsacks beyond the worst case.", 2021]).

The primal-dual framework is widely used to solve CDMP or constrained online optimizations. The sublinear regret and constraint violation can be proved in many adversarial settings of constrained online optimization [1]. Can the authors discuss more on the challenges to achieve provable regret and constraint violation bound in the considered setting?

The fundamental difference of our paper with respect to [1] (and similar works) is that our baseline for the computation of the cumulative regret is stronger. Indeed, our algorithm compares itself with the best strategy that is safe in hindsight (see, definition of the regret $R_T$ in Section 2.4 in our paper). On the contrary, [1] uses as baseline a strategy that is safe at every round, thus being possibly extremely loose in terms of performances (precisely, in the 'Formulation' section, [1] states: "The above goal compares against fixed-decision vectors $x\in A$ that make all constraint functions nonpositive for all slots $t$"). As proved by Mannor et al. (2009), it is not possible to achieve both sublinear regret and sublinear violation in the adversarial setting, when one considers our baseline. Thus, the best achievable result is to guarantee sublinear violation and a fraction of the optimal rewards. Furthermore, let us remark that if we adopt the weaker baseline of [1], it is possible to show that even our algorithm achieves sublinear regret and violation in the adversarial setting (we can provide additional technical details if the Reviewer needs them).

The paper only considers the tabular MDP which is simple. Can the authors discuss the possible generalization to continuous actions and/or continuous states?

Our algorithm (as it is standard in the online learning in Adversarial MDPs literature, see, e.g., ["Online convex optimization in adversarial Markov decision processes", 2019], ["Online Stochastic Shortest Path with Bandit Feedback and Unknown Transition Function", 2019], ["Learning adversarial MDPs with bandit feedback and unknown transition", 2019]) resorts to a Linear Program (LP) formulation of (constrained) Markov decision processes. Indeed, the generalization to continuous actions and/or continuous states would lead to LPs with an infinite number of constraints, thus not solvable in polynomial time. Nevertheless, notice that (constrained) MDPs with continuous state/action set are generally studied from an experimental point of view, since their theoretical analysis is highly non-trivial without making strong assumptions as in linear Markov decision processes or similar settings.

Although this paper has a theory taste, it would be better to have empirical results to evaluate the proposed algorithms.

We agree with the Reviewer that numerical experiments are always beneficial. Nevertheless, in the research area this work lies, namely online decision-making with long-term constraints, experiments are almost never included, see, e.g., ["Online convex optimization with stochastic constraints", 2017], ["A Unifying Framework for Online Optimization with Long-Term Constraints", 2022]. This is also true for the online learning in adversarial Markov decision process research area, see, e.g., ["Online convex optimization in adversarial Markov decision processes", 2019], ["Online Stochastic Shortest Path with Bandit Feedback and Unknown Transition Function", 2019], ["Learning adversarial MDPs with bandit feedback and unknown transition", 2019]. Please notice that, despite the lack of experiments, all the aforementioned works were published in top AI conferences, namely, venues similar to ICLR.

The adversarial setting is about the adversarial reward and constraint matrices, but would it be possible to design an algorithm for adversarial transition kernel?

In general, there exists many negative results related to MDPs with adversarial rewards and adversarial transitions. For example, in such a setting, it is well-known that it is not possible to achieve sublinear regret (see, ["Online learning in unknown markov games", 2021]), without making strong assumptions on the total variation of the transitions, thus not being fully adversarial. We conjecture that, without similar (strong) assumptions, no positive results (in terms of both regret and violations) are achievable in the same setting, with the additional complexity of dealing with constraints.