Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints

Unique technical challenges specific to the CMDPs setting that prevent a direct application of the techniques (Jin et al., 2024)

Both [Jin et al., 2024] and [Agarwal et al., 2017] deal with unconstrained problems, so their goal is single-objective: minimizing the regret. In our setting, minimizing the regret is not the only objective, since we want to keep the violations as small as possible. Thus, the master algorithm must be significantly modified. It is necessary to introduce a Lagrangian formulation of the problem which, in turn, requires a careful analysis of the "optimal" Lagrangian multiplier magnitude, namely, the one that guarantees that high rewards could not compensate high violations (e.g., see Section F.1). This is of paramount importance for our specific setting, since we study the positive constraints violation, not allowing for cancellation.

Finally, consider that we prove regret and positive constraints violation bounds in high probability, while both the original paper of Corral [Agarwal et al., 2017] and [Jin et al., 2024] give results only in expectation (e.g., see Section H).

Since these are crucial aspect of our work, please let us know if further discussion is necessary.

Can the authors provide the motivation for considering a static baseline algorithm? When the time horizon $L$ is large, minimizing the regret in the current episode seems to be a natural choice. Thus, the dynamic regret seems to be more meaningful under this nonstationary setup.

As concerns the choice of a static baseline, the goal of our paper was to bridge the existent gap in literature between the stochastic world and the adversarial world in CMDP. Both extremes (stochastic and adversarial) are traditionally studied through the employ of a static baseline and therefore the use of a static baseline permits the immediate interpretation of the interpolation between this two cases. In addition, for how we defined the measure of non-stationary, our works fits more closely with the field of corruption robustness (e.g. [1],[2],[3],[4]).

Nonetheless, since the difference between the reward achievable with a static optimal policy and the reward achievable through a dynamic optimal policy is strongly dependent on the corruption, in principle our algorithm should achieve also a dynamic regret of order $\sqrt{T}+C$. To give an intuition of why, we can observe that for all episodes $OPT\_{d,t}=\max\_{q \in \Delta(G^\circ)} \mathbb{E}[r_t]^\top q= \max\_{q \in \Delta(G^\circ)} (r^\circ{}^\top q + (\mathbb{E}[r_t]- r^\circ{})^\top q) \le \max\_{q \in \Delta(G^\circ)} (r^\circ{}^\top q + \|\|\mathbb{E}[r_t]-r^\circ\|\|\_1\|\|q\|\|\_\infty) \le OPT_s + C\_t^r$, where $\Delta(G^\circ)$ is the space of the feasible occupancy measures that respect the uncorrupted constraints.

Moreover, notice that, when $L$ is large enough, any regret bound for episodic MDPs become vacuous due to the existing lower-bound of order $\Omega(\sqrt{LT})$ (see e.g. [5]).

[1] ”A model selection approach for corruption robust reinforcement learning”, Wei et al. (2022)

[2]”Noregret online reinforcement learning with adversarial losses and transitions”, Jin et al. (2024)

[3], ”Corruption robust exploration in episodic reinforcement learning”, Lykouris et al. (2019)

[4], ”Improved corruption robust algorithms for episodic reinforcement learning”, Chen et al. (2021)

[5] "Minimax regret bounds for reinforcement learning", Azar et al. (2017)

Lower bound involving $C$

To find a lower bound on the minmax regret dependent on $C$, we start from the following known lower bounds: the one in case of completely stochastic rewards and constraints and the one in the worst case of adversarial rewards and constraints. In the stochastic setting (namely, when $C=0$) the instance independent lower bound for both $R_T, V_T$ is of order $\Omega(\sqrt{T})$ making the first element of our upper bound $\mathcal{O}(\sqrt{T}+C)$ tight. On the other end, suppose by absurd that a regret of type $(\sqrt{T}+C^\alpha)$ was possible, with $\alpha \in (\frac{1}{2},1)$. Then, since $C$ is at most linear by definition, we would have that the regret would be $\mathcal{O}(T^\alpha)$ for all possible choice of adversary, violating the impossibility result of [Mannor et al. 2009] in the adversarial setting.

How efficient it is to solve the optimization problem in Line 5 of Algorithm 2?

The linear optimization problem can be efficiently solved in $Poly(m,|X|^2|A|)$. This is possible through the use of ellipsoid method (see e.g., ["Introduction to linear optimization", Bertsimas and Tsitsiklis, 1997]).

Comparison with literature

• Comparison with [Efroni et al. (2020)]

The algorithm presented by [Efroni et al., 2020] works for stochastic environments: even when $C$ is a constant different from $0$, the confidence interval built by the algorithm might exclude the optimal solution and therefore lead to a linear regret.

• Comparison with [Stradi et al. (2024a)]

[Stradi et al. (2024a)] study the case where rewards are adversarial but constraints are stochastic. Therefore, the same reasoning above holds.

• Comparison with [Stradi et al. (2024b)]

[Stradi et al. (2024b)] study the case where both rewards and constraints can be adversarial in principle. However, the algorithm presented attains linear regret whenever both the non-stationarity of the rewards and the non-stationarity on the constraints is different from zero. Moreover, notice that in our work we consider positive constraints violation while [Stradi et al. (2024b)] allows for cancellation. Finally, [Stradi et al. (2024b)] deals with full feedback while the algorithms presented in this paper work under bandit feedback.

• Comparison with [Wei et al. (2023)]

[Wei et al. (2023)] study a similar problem to ours. Nonetheless, please notice the following fundamental differences. First, we consider the harder problem of bounding the positive constraint violation, while they allow for cancellations. As concerns the definition of regret, they employ a dynamic regret baseline, which, in general, is harder than the static regret employed in our work. However, they compare learner’s performances against a dynamic policy that satisfies the constraints at every round. Instead, we consider a policy that satisfies the constraints on average, which can perform arbitrarily better than a policy satisfying the constraints at every round. Furthermore, the dependence on $T$ in their regret bound is much worse than ours, even when the non-stationarity is small, namely, when it is a constant independent of $T$ and thus the dynamic regret definition collapse to the static one. Indeed, when the variation budget is not known the regret is of order $\widetilde{\mathcal{O}}(T^{\frac{7}{8}})$. Finally, notice that the regret guarantees presented by [Wei et al. (2023)] hold only under the assumption of large $T$ while we make no assumption on the number of episodes.

The proposed algorithm follows the UCB design with $C$ involved, thus, achieving a sublinear regret with respect to the static policy is kind of expected. It would be great if the authors can highlight the technical novelty.

We agree with the Reviewer that the techniques employed in the known $C$ setting are UCB-like; nonetheless, they are indeed properly adapted to the uncertainty of the environment. While enlarged confidence set are not novel in literature, ours present peculiar characteristic due to our choice of baseline. Moreover, we want to stress that the algorithm developed for the known $C$ setting is mostly presented as a necessary intermediate step to tackle the considerably more challenging problem of dealing with unknown $C$ setting, which makes standard techniques like UCB inapplicable.

Please let us know if further discussion is necessary.

The algorithmic definitions, especially the $\ell_{t,j}$ and $b_{t,j}$ are written in a highly technical way. For example, without any description on the $\beta$'s in the main text, it is almost impossible to understand the construction of $b_{t,j}$ -- I suggest the authors to exemplify what each $\beta$ would be like if the revised Algorithm 2 is executed on its own. The effect of $\nu_{t,j}$ is also not explained.

The role of the bonus quantity is to incentivize the exploration. In this sense, $\nu_{t,j}=\max_{\tau \le t}\frac{1}{w_{\tau,j}}$ is higher for the less explored arms, leading to a bonus quantity that push the algorithm to choose them more. The bonus quantity is also proportional to the upper bound of the regret and positive constraints violation of the arm algorithm, which is represented by the use of the $\beta$'s. Due to space constraints we had to be very concise in explaining this bonus quantity and in giving an intuitive explanation, but we will be glad to expand on these topics in the camera-ready with the additional space.

Independent interest of Lag-FTRL

As we specified in the previous answer, the problem-specific quantities employed in lag-FTRL can be easily derived observing the regret and constraints guarantees of the employed sub-routines (the ones associated with the arms), leading to a versatile meta-procedure that deals with constrained problem.

Is there any intuition why the non-stationarity metric is like this? Would other common metrics like path lengths be harder to tackle?

Our choice of measure of non-stationary is directly inspired by the corruption robustness field (e.g. [1],[2],[3],[4]). In principle, our $C$ and a path length metric are very different, as our metric is considered with respect to a possible fixed distribution equal for all episodes and the cumulative deviation from it. Our choice of $C$ is also a result of our goal of interpolating the result between the completely stochastic case and the completely adversarial one, both traditionally studied through a static prospective, more affine to corruption than to path length. Using the metric of path length would be more meaningful in relation with a dynamic regret problem, which is out of scope for this work .

Since these are crucial aspect of our work, please let us know if further discussion is necessary.

[1] "A model selection approach for corruption robust reinforcement learning", Wei et al. (2022)

[2] "Noregret online reinforcement learning with adversarial losses and transitions", Jin et al. (2024)

[3] "Corruption robust exploration in episodic reinforcement learning", Lykouris et al. (2019)

[4] "Improved corruption robust algorithms for episodic reinforcement learning", Chen et al. (2021)

On the reason behind the static baseline

We designed this setting to bridge the existent gap in literature between the stochastic world and the adversarial world in CMDP. Both extremes (stochastic and adversarial) are traditionally studied through the employ of a static baseline and therefore the use of a static baseline permits the immediate interpretation of the interpolation between this two cases. In addition, for how we defined the measure of non-stationary, our works fits more closely with the field of corruption robustness (e.g. [1],[2],[3],[4]).

[1] "A model selection approach for corruption robust reinforcement learning", Wei et al. (2022)

[2]"Noregret online reinforcement learning with adversarial losses and transitions", Jin et al. (2024)

[3] "Corruption robust exploration in episodic reinforcement learning", Lykouris et al. (2019)

[4] "Improved corruption robust algorithms for episodic reinforcement learning", Chen et al. (2021)

Can the results be extended to dynamic regret?

The difference between the reward achievable with a static optimal policy and the reward achievable through a dynamic optimal policy is strongly dependent on the corruption, therefore in principle our algorithm should achieve also a dynamic regret of order $\sqrt{T}+C$. To give an intuition of why, we can observe that for all episodes $OPT_{d,t}=\max_{q \in \Delta(G^\circ)} \mathbb{E}[r_t]^\top q= \max_{q \in \Delta(G^\circ)} (r^\circ{}^\top q + (\mathbb{E}[r_t]- r^\circ{})^\top q) \le \max\_{q \in \Delta(G^\circ)} (r^\circ{}^\top q + \|\|\mathbb{E}[r_t]-r^\circ\|\|\_1\|\|q\|\|\_\infty) \le OPT_s + C_t^r$, where $\Delta(G^\circ)$ is the space of the feasible occupancy measures that respect the uncorrupted constraints.

Nevertheless we want to stress the fact that our goal was to weaken the linear lower bound for the adversarial rewards and constraints setting (see answer above). The problem of learning dynamic regret is in principle very different and for the goal of this paper out of scope.

Can you comment on the technical challenges of deriving the results for static regret?

We thank the Reviewer for the opportunity to clarify this aspect. In the following, we highlight why standard FTRL techniques cannot work in our setting when only bandit feedback is available. Specifically, notice that a FTRL meta-algorithm guarantees that the performances of the master algorithm are "near" the one of the optimal arm, namely, the optimal subroutine. Nevertheless, the optimal subroutine cannot trivially attain the same theoretical guarantees than when applied in the known C scenario, since, when employed as an arm, the subroutine receives the feedback with a certain probability. Indeed, each arm (including the optimal one) receives feedback only in the subsets of episodes in which that specific arm is chosen, thus, its guarantees are in principle arbitrarily worse than the one attained when playing at each round.

Finally, we remark that it exists an extensive literature devoted to the sole scope of designing master algorithms to choose between no-regret minimizer subroutines, as it is not a trivial task under bandit feedback (see e.g., the following references). All these works study static regret.

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

[1] "Regret Balancing for Bandit and RL Model Selection", Abbasi-Yadkori et al. (2020)

[2] "Corralling a band of bandit algorithms", Agarwal et al. (2016)

Comparison with Corral

The online model selection research line, originally proposed by the seminal work of Agarwal et al. (2017) (which first proposed the Corral algorithm) and recently employed for unconstrained MDPs with adversarial transitions (see, [Jin et al., 2024]) focuses on the design of meta-procedures to choose between different instances of algorithms. However, these meta-procedures are specifically designed to deal with unconstrained problems, namely, their goal is single-objective: minimizing the regret. In our setting, minimizing the regret is not the only objective, since we want to additionally keep the violations as small as possible. Thus, it is not possible to blindly apply Corrall-like techniques, as it would lead to arbitrarily big violations.

In our work, we propose a Lagrangian approach to the online model selection problem, which we believe is of independent interest since it can be easily generalized to the employment of different kind of sub-routines compared to the ones employed in our work, adapting the learning rate and the bonus function. Please notice that using a Langrangified loss is not sufficient to guarantee bounded positive constraints violation. First, we build the meta-algorithm's loss employing a positive Lagrangian function, which to the best of our knowledge is a novel tool in the online CMDPs literature. Furthermore, properly balancing the regret and the positive constraints violation requires a careful calibration of the Lagrangian multiplier. On the one hand the Lagrangian multipliers must be large enough to guarantee that it is not possible to compensate large constraints violation with a regret sufficiently negative; on the other hand, since the FTRL regret bound depends on the Lagrangian loss range of values, the Lagrangian multiplier must be small enough not to prevent FTRL from being no-regret (see Section F.1 for additional details on these aspects). Moreover, the rest of the analysis presents various challenges derived from the constrained nature of the problem and the definition of positive constraints violation (e.g., Section F.3). Thus, we believe that, while inspired by Corral for what concerns the stability results, our analysis is novel and independent from existing works in online model selection.

Finally notice that our work presents results which hold in high probability, while both [Agarwal et al., 2017] and [Jin et al., 2024] attains results which hold in expectation only. To do so, we rely on an high probability definition of stability and we prove that from a corruption-robust algorithm in high probability it is possible to build a stable algorithm given our definition of stability (see Section H).