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

Authors: Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti
Primary area: learning theory
Keywords: CMDPs, Non-stationary, Online learning

Abstract:
In constrained Markov decision processes (CMDPs) with adversarial rewards and constraints, a well-known impossibility result prevents any algorithm from attaining both sublinear regret and sublinear constraint violation, when competing against a best-in-hindsight policy that satisfies constraints on average. In this paper, we show that this negative result can be eased in CMDPs with non-stationary rewards and constraints, by providing algorithms whose performances smoothly degrade as non-stationarity increases.
Specifically, we propose algorithms attaining $\tilde{\mathcal{O}} (\sqrt{T} + C)$ regret and positive constraint violation under bandit feedback, where $C$ is a corruption value measuring the environment non-stationarity. This can be $\Theta(T)$ in the worst case, coherently with the impossibility result for adversarial~CMDPs. First, we design an algorithm with the desired guarantees when $C$ is known. Then, in the case $C$ is unknown, we show how to obtain the same results by embedding such an algorithm in a general meta-procedure. This is of independent interest, as it can be applied to any non-stationary constrained online learning setting.

Decision: reject
Reviewer scores: 5, 6, 5, 5

Reviews and discussion:
<thread>
creation date:
1730078411642

thread_type:
official_review

<thread_object>
creator: reviewer_ba5a

<content>
summary:
This paper studies the constrained Markov decision processes (CMDPs) with adversarial rewards and constraints. Given the negative result of Mannor et al., 2009, the authors propose algorithms whose regret bounds depend on the non-stationarity of rewards and constraints. The proposed algorithm works for unknown $C$ by using a Corral-based technique.

strengths:
+ To my knowledge, This is the first work considering the CMDPs problem with adversarial rewards and constraints.

+ Authors provide theoretical guarantees for the proposed algorithms and achieve a linearly additive dependence on C.

+ The paper is generally well-written and easy to follow.

weaknesses:
My primary concern is the limited novelty of the technical contribution, as the approach in this paper appears to be a direct application of techniques from (Jin et al., 2024) for the CMDPs setting. In particular, the core technique and main theoretical analysis to deal with unknown $C$ are largely based on that of (Jin et al., 2024). Given that the corral (Agarwal et al., 2017) with different guesses for $C$ has been used in prior work (e.g., Jin et al., 2024), I believe a more direct comparison to (Jin et al., 2024) is necessary to clarify the technical contributions of this paper.

questions:
If there are unique technical challenges specific to the CMDPs setting that prevent a direct application of the techniques in (Jin et al., 2024), I would be happy to reconsider and adjust my evaluation accordingly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730179546574

thread_type:
official_review

<thread_object>
creator: reviewer_573v

<content>
summary:
This paper considers constrained MDP under non-stationary rewards and constraints, where the reward, cost functions and the transition kernel are unknown, the level of non-stationarity is measured by $C$ and the constraints is in terms of the expected number of violations. It solves the problem with the knowledge of $C$, followed by an extension to the unknown $C$ case with the help of Corralling method by Agarwal et al. (2017).

strengths:
- The paper is easy to follow and the intuition of the algorithms is natural.
- This paper adopts $C$ to quantify the level of non-stationarity, bridging the stationary setup and the adversarial setup.
- A meta algorithm is used to deal with the case where the knowledge of $C$ is not provided.

weaknesses:
- Given the previous literature (Efroni et al. (2020), Stradi et al. (2024a), Stradi et al. (2024b), Wei et al. (2023)), the proposed problem formulation lacks novelty and motivations. While considering a positive violation seems to be practical, it is more proper to consider a dynamic baseline. Therefore, it is encouraged to provide a more detailed comparison between this work and the literatures in terms of the setups, motivations, and results.
- 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.
- Simulations are not provided to illustrate the efficacy of the proposed algorithms, as well as comparisons with other baseline algorithms in the literature.

questions:
- 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.
- The paper suggests it can ease the negative result of Mannor et al. (2019) by introducing the nonstationary parameter $C$. Is there any lower bound that involves $C$ for the proposed problem under the proposed regret formulation?
- How efficient it is to solve the optimization problem in Line 5 of Algorithm 2?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730226648815

thread_type:
official_review

<thread_object>
creator: reviewer_o4qz

<content>
summary:
This paper considers CMDPs with both non-stationary rewards and constraints. As the fully adversarial CMDP problem is shown to be statistically intractable, the authors propose to consider the case where the per-round reward $r_t$ / constraint $g_t$ are sampled from some time-dependent distributions whose means do not vary from a "reference" reward / constraint vector significantly.

When $C$ is known, to tackle with the extra uncertainty in rewards and constraints, the confidence intervals are enlarged by an additive factor of $C/N_t(s,a)$. Utilizing policy search over the (estimated) occupancy measures, the algorithm guarantees $\mathcal O(\sqrt T + C)$ regret and constraint violations where $C$ is the level of non-stationarity.

Moreover, when $C$ is unknown, an algorithm-selection meta-algorithm that performs log-barrier FTRL on many base-algorithms with doubling $C$'s is developed.

strengths:
1. The constraint-violation metric is pretty strong: Albeit the static hindsight optimal policy is allowed to violate the constraints in some rounds and make it up in the remaining, the algorithm is not because of the $[\cdot]^+$ notion.
2. The known $C$ algorithm is pretty intuitive and well-motivated, especially regarding the enlargement of confidence radii.
3. The algorithm also works well when $C$ is unknown, with almost no performance degeneration -- though its quite hard to get the idea and applicability of the framework from the current writing; see the Weaknesses section.

weaknesses:
1. 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.
2. The authors mentioned that the meta-algorithm Lag-FTRL can be of independent interest. Would it be possible to isolate the framework from the base algorithm -- say, what conditions of $\ell_t$ and $b_t$ are required for the framework to work, or it has to be constructed so meticulously as in Eqs. (6) and (7)?

Minor: Line 155 -- the definition of $C$ should be $\max(C_{G^\circ},C_{r^\circ})$?

questions:
See Weaknesses. These two questions concern the technical hardness and applicability of the Lag-FTRL framework. I am happy to adjust my rating if the answers turn out to be pretty positive.

And also:

3. Is there any intuition why the non-stationarity metric is like this? Would other common metrics like path lengths be harder to tackle?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730555923434

thread_type:
official_review

<thread_object>
creator: reviewer_ixay

<content>
summary:
The paper studied CMDP with non stationary rewards and transitions. A \sqrt{T} + C style regret bound is shown with LAG-FTRL, which is a combination of FTRL and UCB. The algorithm will maintain several instances of the UCB algorithm and pick one according to FTRL.

strengths:
The paper is well-written and the proof is sound. To the best of my knowledge, this is the first result on CMDP with nonstationary rewards, transitions, and bandit feedback.

weaknesses:
My main concern is about the static baseline employed. To my knowledge, dynamic regret is usually used as a benchmark in learning in nonstationary environments. The paper has only highlighted the importance of considering static regret when the nonstationary is small (as a constant), which is unlikely to be the case in most environments. When we consider static regret, it is not so surprising that adding a layer of FTRL that "guesses" the corruption level can work, as FTRL already guarantees the static regret.

questions:
1. Can you elaborate on the comparison of dynamic and static regret when the nonstationary is large? 
2. Can the results be extended to dynamic regret?
3. Can you comment on the technical challenges of deriving the results for static regret?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732699447617

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

thank you again for the effort in reviewing our paper. We take the liberty to ask if our rebuttal has adequately addressed your concerns. We are happy to provide further clarification and engage in any discussion.

Thank you!

The Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1733304867179

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Part 1

comment:
We want to thank again the Reviewers for their time and for the effort in evaluating our work. Based on the comments and questions posed by the Reviewers (for more specific discussion we answered each comment singularly), we kindly ask the Reviewers to consider the following recap considerations that we believe should help in solving their possible concerns.

>On the static baseline
    
Some Reviewers expressed concerns about the choice of a static baseline in the regret definition. We would like to readdress this point here, since it is a crucial point.

First, please consider the objective of this paper. Indeed, this paper's goal is to weaken the impossibility result for CMDPs with adversarial constraints and rewards to achieve both sublinear regret and sublinear constraints violation. Thus, we propose an algorithm with theoretical guarantees that are in between the purely stochastic case ($\mathcal{O}(\sqrt{T})$) and the worst case adversarial one ($\Omega(T)$). **To address this challenge we believe the static baseline is the more meaningful, as it is the one used by both extremes and the only one that allows the immediate interpretation of the result**.

In addition, please consider that our work's most natural related literature is the corruption robust online learning literature, which is still mostly unexplored for CMDPs but it is long established in other settings, as the unconstrained MDPs with corrupted transition probabilities and other online learning problems (e.g., [1],[2],[3],[4],[5],[6],[7],[8],[9],[10]). **Corruption-robust literature traditionally uses a static regret baseline, which is perfectly coherent with the definition of corruption itself**.

In that sense, **if the Reviewer think it might be of help to future readers, we would be happy to change the title of the paper to make a direct reference to corruption robustness instead of non-stationary to delimit and frame our work for what it is, and for what it is meant to do, solving the ambiguity with the stochastic non-stationary research line traditionally approached with dynamic regret**.

Finally, we want to remark that the task of attaining the desired guarantees with static regret when corruption is not known in advance is highly non-trivial, and a classic FTRL approach when only bandit feedback is available fails in such a task. 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, namely, the probability that arm is selected. To tackle the aforementioned problem, 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. [11] ). Consider in addition that even this literature use a static regret.

[1] Lykouris et al. "Corruption robust exploration in episodic reinforcement learning" (2021)
        
[2] Chen et al. "Improved Corruption Robust Algorithms for Episodic Reinforcement Learning" (2021)
        
[3] Wei et al. "A Model Selection Approach for Corruption Robust Reinforcement Learning" (2022)
        
[4] Jin et al. "Noregret online reinforcement learning with adversarial losses and transitions" (2024) 
    
[5] Lykouris et al.,"Stochastic bandits robust to adversarial corruption" (2018)
        
[6] Yang et al., "Adversarial Bandits with Corruptions:
        Regret Lower Bound and No-regret Algorithm", (2020)
        
[7] Zhao et al. "Linear Contextual Bandits with Adversarial Corruptions", (2021)
        
[8] Bogunovic at al, "Stochastic linear bandits robust to adversarial attacks", 2021
        
[9] Lee et al., "Achieving near instance optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously", (2021)
    
[10] He et al. "Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions", (2022)

[11] Agarwal et al. "Corralling a Band of Bandit Algorithms", (2017)
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies CMDPs with non-stationary rewards and constraints, and propose an algorithm whose performance smoothly degrades as non-stationarity increases. More specifically, the algorithm achieves $O(\sqrt{T} + c)$ regret and positive constraint violation under bandit feedback, where $C$ is a corruption value measuring the environment non-stationarity. 

The main weakness of the paper is the lack of technical novelty. For instance, the authors failed to demonstrate why lag-FTRL could be a versatile meta-procedure that deals with constrained problems. 

Given the high standards of ICLR and the weakness mentioned above, I would recommend rejecting this paper.