Authors: Matteo Castiglioni, Alberto Marchesi, Nicola Gatti (Politecnico di Milano)
Introduction: The Safety-Performance Trade-off
In Reinforcement Learning (RL), agents are typically designed to maximize a cumulative reward signal. However, real-world deployment often requires adhering to safety constraints—modeled as Constrained Markov Decision Processes (CMDPs). For instance, an autonomous vehicle must reach its destination efficiently while strictly avoiding collisions.
The challenge intensifies in non-stationary environments where rewards and safety costs fluctuate over time. A seminal result by Mannor et al. (2009) established an "impossibility result": in a purely adversarial setting, no algorithm can simultaneously guarantee sublinear regret (performance loss relative to the optimal policy) and sublinear constraint violations. This suggests a binary choice: be safe but potentially ineffective, or be effective but potentially unsafe.
Bridging the Gap with Corruption Measures
This research seeks a middle ground between perfectly stable (stochastic) and purely adversarial environments. The authors introduce a corruption measure ($C$) to quantify the degree of non-stationarity. $C$ represents the total variation of the environment's reward and cost distributions from a hypothetical stable baseline.
By using $C$ as a continuous parameter, the authors demonstrate that the "impossibility" is not a wall but a spectrum. When $C$ is small, the environment is near-stochastic, allowing for high performance and safety. As $C$ increases toward the adversarial limit, performance naturally degrades, providing a framework for "graceful degradation."
Algorithmic Contributions
The paper proposes two primary algorithms to navigate these non-stationary CMDPs:
1. NS-SOPS (Non-Stationary Safe Optimistic Policy Search)
Designed for scenarios where the total non-stationarity $C$ is known a priori, NS-SOPS extends the "Optimism in the Face of Uncertainty" principle. It constructs confidence intervals for rewards and costs but expands these intervals based on the corruption value $C$. This ensures the agent remains sufficiently optimistic to explore the state space even as the underlying distributions shift.
2. Lag-FTRL (Lagrangified Follow-the-Regularized-Leader)
Since the degree of non-stationarity is rarely known in practice, the authors developed Lag-FTRL. This meta-algorithm manages multiple instances of NS-SOPS, each initialized with a different guess for $C$. Using a specialized online learning technique—Follow-the-Regularized-Leader with log-barrier regularization—Lag-FTRL dynamically identifies and follows the most effective instance for the current environment.
A critical design choice in both algorithms is the focus on positive constraint violation. Unlike models where "safe" actions can offset previous "unsafe" ones, this approach recognizes that a past failure (e.g., a crash) cannot be undone by future safety.
Theoretical Results
The authors provide rigorous mathematical proofs showing that their algorithms achieve:
- Regret: $\tilde{O}(\sqrt{T} + C)$
- Positive Constraint Violation: $\tilde{O}(\sqrt{T} + C)$
Where $T$ is the number of episodes. These bounds imply that if the environment's drift ($C$) grows slower than the time horizon ($T$), the agent successfully learns an optimal, safe policy. This represents a significant advancement over prior adversarial CMDP methods, which often suffered linear regret to maintain safety.
Limitations and Future Directions
While providing a robust theoretical framework, several challenges remain:
- Feasibility Parameters: The meta-algorithm relies on a "feasibility parameter" ($\rho$), representing the available "slack" in constraints, which may be difficult to estimate in unknown environments.
- Computational Complexity: Running multiple parallel instances of a base algorithm ($\log T$ instances) introduces overhead that might be significant for long-duration tasks.
- Transition Dynamics: The current work assumes non-stationarity in rewards and costs while keeping transition physics stable. Addressing environments where the very dynamics of the world are adversarial remains a primary goal for future research.
Summary updated