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

Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, Nicola GattiSubmission to ICLR 2025 · Rejected

TL;DR

A classic impossibility result states that in constrained reinforcement learning with adversarial environments, no algorithm can simultaneously achieve both sublinear regret and sublinear constraint violations. This paper eases that negative result for non-stationary environments by parameterizing the degradation of performance with an adversarial corruption metric $C$. The authors introduce algorithms achieving $\tilde{\mathcal{O}}(\sqrt{T} + C)$ regret and positive constraint violation under bandit feedback, both when $C$ is known and when it must be learned adaptively via a novel meta-algorithm.

What Problem Does This Paper Address?

In safe reinforcement learning, an agent modeled via a Constrained Markov Decision Process (CMDP) must maximize cumulative rewards while keeping certain costs (e.g., fuel spent, collisions, or policy violations) below strict thresholds.

When rewards and constraints are chosen adversarially, a celebrated impossibility result by Mannor et al. (2009) proves that an online learner cannot achieve both sublinear regret and sublinear constraint violations against an optimal benchmark policy that satisfies constraints on average. While most existing CMDP literature sidesteps this by assuming stationary or purely stochastic constraints, real-world systems (e.g., traffic conditions, auction markets) are inherently non-stationary.

The authors bridge the gap between purely stochastic and fully adversarial settings. They ask: Can an agent achieve near-optimal performance when the environment shifts over time, scaling gracefully with the degree of non-stationarity rather than failing outright?

Methods

The paper considers episodic, loop-free CMDPs under bandit feedback (the agent only observes rewards and costs for visited state-action pairs) and evaluates positive constraint violation $\sum_t [ \text{cost}_t - \alpha ]^+$ (violations cannot be cancelled out by being extra safe in other episodes).

  1. Measuring Non-Stationarity ($C$): The authors define total corruption $C = \max\{C_r, C_G\}$, measuring the cumulative $\ell_1$ distance between the true time-varying distributions' means and fixed, fictitious non-corrupted counterparts.

  2. NS-SOPS (Known $C$): When $C$ is known, the authors propose Non-Stationary Safe Optimistic Policy Search (NS-SOPS). It solves a linear program over occupancy measures using:

  3. Upper confidence bounds (UCBs) on rewards to encourage reward exploration.

  4. Lower confidence bounds (LCBs) on constraint costs to ensure optimism in constraint feasibility.
  5. Crucially, confidence widths are enlarged with an explicit additive term proportional to $C/N_t(x, a) + C/T$.
  6. Lag-FTRL (Unknown $C$): When $C$ is unknown, the authors design Lag-FTRL, a master meta-algorithm running $M = \lceil \log_2 T \rceil$ stabilized instances of NS-SOPS, each guessing $C = 2^j$. The master selects an instance each episode using Follow-The-Regularized-Leader (FTRL) with log-barrier regularization.

  7. It addresses bandit feedback at the master level using optimistic loss estimators.

  8. It penalizes constraint violations using a newly developed positive Lagrangian formulation: $\mathcal{L}(\beta, q) = r^\top q - \beta \sum_i [G_i^\top q - \alpha_i]^+$.

Datasets

Not discussed in the paper. This work is purely theoretical and does not present empirical benchmarks or simulated datasets.

Key Insights and Ideas

  • Optimism in Both Objectives: By inflating both reward UCBs and cost LCBs with the corruption parameter $C$, the linear program's feasible set contains the optimal hindsight policy with high probability, guaranteeing that optimism drives exploration safely.
  • Positive Strong Duality: Traditional Lagrangian duality fails when constraints take the form $[G^\top q - \alpha]^+ \le 0$ because strict interior points (Slater's condition) do not exist for the non-negative hinge function. The authors prove a specialized strong-duality theorem for the positive Lagrangian: setting the dual multiplier $\beta \ge L/\rho$ (where $\rho$ is the Slater margin) is sufficient to guarantee that the unconstrained positive Lagrangian supremum matches the primal constrained optimum.
  • General Meta-Procedure: The Lag-FTRL master algorithm does not depend strictly on CMDP specifics; it serves as a modular meta-framework to adaptively tune corruption-sensitive algorithms in broader non-stationary constrained online learning problems.

Key Results

  • Known Corruption ($C$ known): Algorithm 2 (NS-SOPS) achieves high-probability bounds of: $$\text{Regret } R_T = \tilde{\mathcal{O}}\left(L|X|\sqrt{|A|T} + |X||A|C\right)$$ $$\text{Violation } V_T = \tilde{\mathcal{O}}\left(L|X|\sqrt{|A|T} + |X||A|C\right)$$ When $C = \mathcal{O}(1)$, both regret and violation match the standard $\tilde{\mathcal{O}}(\sqrt{T})$ rate. When $C = \Theta(T)$, the bounds become linear, consistent with Mannor et al.'s impossibility theorem.

  • Unknown Corruption ($C$ unknown): Algorithm 3 (Lag-FTRL) achieves: $$R_T, V_T = \tilde{\mathcal{O}}\left(m^2 L^2 |X|\sqrt{|A|T} + m^2 L |X||A|C\right)$$ up to polylogarithmic factors in $T$, matching the $\tilde{\mathcal{O}}(\sqrt{T} + C)$ rate without knowing $C$ in advance.

Limitations and Future Work

  • Dependence on Slater Margin ($\rho$): The master algorithm Lag-FTRL requires knowing (or having a positive lower bound on) the Slater feasibility parameter $\rho$ to set the dual penalty bound $\Lambda = \frac{Lm+1}{\rho}$.
  • Computational Complexity: Lag-FTRL runs $\mathcal{O}(\log T)$ parallel instances of NS-SOPS, each maintaining enlarged confidence sets and solving linear programs over occupancy measure polytopes, which may be computationally demanding for large state spaces.
  • Adversarial Transitions: The current formulation considers non-stationary rewards and constraints, but transitions are assumed stationary (governed by a fixed, unknown transition probability matrix $P$). Extending this framework to concurrently handle adversarially drifting transition dynamics is an open direction.

Summary updated

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.
BibTeX
@misc{stradi2024learning,
  author = {Francesco Emanuele Stradi and Anna Lunghi and Matteo Castiglioni and Alberto Marchesi and Nicola Gatti},
  title = {{Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints}},
  year = {2024},
  eprint = {2405.14372},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.14372},
}

Loading related content...

Figure