Towards Safe Policy Improvement for Non-Stationary MDPs

Yash Chandak, Emma Jordan, Georgios Theocharous, Martha White, Philip S. Thomas

Most reinforcement learning (RL) safety guarantees break the moment the environment starts to change. In high-stakes fields like medicine (e.g., sepsis treatment) or finance, we cannot afford to deploy an RL policy that performs worse than the current "safe" baseline. While "Safe RL" exists, it almost universally relies on the stationarity assumption: the idea that the rules of the environment (transitions and rewards) never change.

In reality, the world is non-stationary. A patient’s insulin sensitivity drifts over time; market trends shift seasonally. If an algorithm assumes the world is static when it is actually drifting, its safety guarantees become meaningless. How can we safely improve a policy when the underlying environment is constantly, albeit smoothly, changing?

To address this, researchers introduce SPIN (Safe Policy Improvement for Non-Stationary settings), an algorithm that provides high-confidence safety guarantees for policy updates in non-stationary environments.

The SPIN Algorithm

SPIN adapts the "Seldonian" framework—a class of algorithms designed to satisfy user-defined safety constraints with high probability. Rather than attempting the mathematically daunting task of modeling a full Non-Stationary Markov Decision Process (MDP), SPIN treats policy performance as a time-series forecasting problem.

Key technical components include:

  • Counterfactual Estimation: SPIN uses importance sampling to estimate how a new candidate policy would have performed on historical data.
  • Performance Forecasting: It models the scalar performance of a policy over time as a univariate time-series, using linear regression with non-linear basis functions (like the Fourier basis) to capture trends.
  • Wild Bootstrap: Standard confidence intervals assume data is independent and identically distributed (i.i.d.). Because time-series data is neither, SPIN uses the wild bootstrap—a resampling technique that handles varying noise levels and time-dependence—to generate robust confidence intervals for future performance.
Forecasting and safety test logic in SPIN. The algorithm predicts future performance bounds and only deploys a candidate policy if its lower bound exceeds the safe policy's upper bound.

The core of the algorithm is its Safety Test. A new candidate policy is only deployed if the lower bound of its predicted future performance is strictly higher than the upper bound of the current policy’s predicted performance. Safety acts as a tunable "knob": users can set a specific confidence level (e.g., 95%), and the algorithm ensures the probability of deploying a worse policy stays below that 5% failure threshold, even as the environment drifts.

Experimental Validation

The researchers evaluated SPIN on two simulated domains designed to mimic high-stakes real-world problems:

  1. Non-Stationary Recommender System (RecoSys): A synthetic environment where user interests in products fluctuate in a seasonal cycle.
  2. Non-Stationary Diabetes Treatment: Based on an FDA-approved Type-1 Diabetes simulator, where non-stationarity is introduced by varying the patient’s insulin sensitivity over time.
Experimental results on RecoSys and Diabetes domains. SPIN consistently maintains unsafe policy usage below the 5% threshold (dashed line), whereas baselines fail dramatically.

Key Findings

  • Safety Adherence: In both domains, SPIN successfully maintained a failure rate near or below the target 5% threshold. In stark contrast, baseline safe algorithms (which assume stationarity) saw failure rates soar as high as 40% when the environment drifted.
  • The Deception of Slow Change: A striking insight from the experiments is that slow environmental changes are often more dangerous than fast ones. In fast-changing environments, high variance makes algorithms naturally cautious. In slow-changing environments, algorithms mistakenly believe the world is stationary, leading to overconfidence and catastrophic safety violations.
  • Performance Gains: While SPIN is inherently conservative, it successfully identified and deployed improved policies. In the Diabetes domain, it was the only tested algorithm capable of providing performance improvements while strictly remaining safe. Ablation studies confirmed that removing the Safety Test led to immediate and significant performance drops.

Limitations and Future Directions

While SPIN represents a significant step forward, it has limitations. It assumes that environmental changes are exogenous (changing on their own, not due to the agent's actions) and requires performance to change smoothly over time, meaning it cannot handle sudden shocks or discontinuities. Additionally, reliance on importance sampling can introduce high variance, sometimes making the algorithm too conservative to update even when a better policy exists.

Future work may explore more complex time-series models, such as ARIMA, to better capture local structures and correlated noise, further refining the balance between safety and performance in non-stationary worlds.

Summary updated

Abstract

Many real-world sequential decision-making problems involve critical systems with financial risks and human-life risks. While several works in the past have proposed methods that are safe for deployment, they assume that the underlying problem is stationary. However, many real-world problems of interest exhibit non-stationarity, and when stakes are high, the cost associated with a false stationarity assumption may be unacceptable. We take the first steps towards ensuring safety, with high confidence, for smoothly-varying non-stationary decision problems. Our proposed method extends a type of safe algorithm, called a Seldonian algorithm, through a synthesis of model-free reinforcement learning with time-series analysis. Safety is ensured using sequential hypothesis testing of a policy’s forecasted performance, and confidence intervals are obtained using wild bootstrap.
BibTeX
@inproceedings{chandak2020towards,
  author = {Yash Chandak and Emma Jordan and Georgios Theocharous and Martha White and Philip S. Thomas},
  title = {{Towards Safe Policy Improvement for Non-Stationary MDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=w21o7AXrwgq},
}
Figure