Off-Policy Risk Assessment in Markov Decision Processes

Audrey Huang, Liu Leqi, Zachary Chase Lipton, Kamyar AzizzadenesheliarXiv 2022 · OpenReview

Abstract

Addressing such diverse ends as safety alignment with human preferences, and the efficiency of learning, a growing line of reinforcement learning research focuses on risk functionals that depend on the entire distribution of returns. Recent work on off-policy risk assessment (OPRA) for contextual bandits introduced consistent estimators for the target policy's CDF of returns along with finite sample guarantees that extend to (and hold simultaneously over) all risk. In this paper, we lift OPRA to Markov decision processes (MDPs), where importance sampling (IS) CDF estimators suffer high variance on longer trajectories due to small effective sample size. To mitigate these problems, we incorporate model-based estimation to develop the first doubly robust (DR) estimator for the CDF of returns in MDPs. This estimator enjoys significantly less variance and, when the model is well specified, achieves the Cramer-Rao variance lower bound. Moreover, for many risk functionals, the downstream estimates enjoy both lower bias and lower variance. Additionally, we derive the first minimax lower bounds for off-policy CDF and risk estimation, which match our error bounds up to a constant factor. Finally, we demonstrate the precision of our DR CDF estimates experimentally on several different environments.

Introduction

In Reinforcement Learning (RL), Off-Policy Evaluation (OPE) is the task of estimating the performance of a target policy using data collected by a different behavior policy. While traditional OPE focuses on the expected return (the mean), many real-world applications—such as healthcare, finance, and autonomous driving—require a deeper understanding of risk. In these safety-critical domains, the average outcome is often less important than the probability of catastrophic failure or the "worst-case" scenario.

To assess risk accurately, one must estimate the entire Cumulative Distribution Function (CDF) of returns. However, extending OPE from mean estimation to CDF estimation in Markov Decision Processes (MDPs) introduces significant technical hurdles, most notably the "curse of horizon," where the variance of importance sampling estimators grows exponentially with the length of the trajectory.

Methodology

This research introduces a framework for Off-Policy Risk Assessment (OPRA) in MDPs, centered on the development of a Doubly Robust (DR) estimator for the return distribution.

The CDF Bellman Equation

The foundation of this approach is a recursive formulation for the CDF of returns. Similar to how the standard Bellman equation decomposes the expected value into immediate reward and future value, the CDF Bellman equation decomposes the return distribution. It expresses the CDF as a convolution of the current reward distribution and the future return distribution, allowing for step-by-step estimation across a trajectory.

Doubly Robust (DR) Estimation

The core contribution is the first DR estimator for the CDF of returns in MDPs. This method combines two primary approaches:

  1. Model-Based Estimation: Uses a learned model of the environment to predict the distribution. While stable, this can be biased if the model is misspecified.
  2. Importance Sampling (IS): Uses actual trajectory data to provide an unbiased estimate, though it often suffers from extreme variance.

By using the model-based estimate as a baseline and applying importance sampling to the residuals (the errors in the model), the DR estimator remains unbiased while significantly reducing variance. The authors further refine this into a Weighted Doubly Robust (WDR) version for improved empirical stability.

Tail-Specific Estimation (F vs. S)

A key insight of the paper is that the variance of CDF estimators is not uniform. Estimating the CDF ($F$) is generally low-variance for small returns but high-variance for large returns. Conversely, estimating the Survival Function ($S = 1 - F$) is low-variance for large returns. The authors propose a "Combined IS" strategy that adaptively selects the more stable estimator across different segments of the return distribution.

Theoretical Contributions

The paper provides rigorous theoretical grounding for these estimators:

  • Minimax Lower Bounds: The authors derive the first minimax lower bounds for off-policy CDF and risk estimation, establishing the fundamental limits of how accurately these values can be estimated.
  • Cramer-Rao Efficiency: They prove that when the environment model is well-specified, the DR estimator achieves the Cramer-Rao variance lower bound, meaning it is asymptotically the most efficient unbiased estimator possible.
  • Simultaneous Guarantees: Because the CDF estimate is consistent across the entire range of returns, it provides simultaneous statistical guarantees for any downstream risk functional (such as Value-at-Risk or CVaR) derived from it.

Experimental Results

The estimators were evaluated in two environments designed to test risk sensitivity:

  1. Cliffwalk: A grid-world environment where the agent must navigate near a high-cost "cliff." This environment tests the estimator's ability to handle discrete, high-stakes failures.
  2. Simglucose: A continuous simulator for Type-1 diabetes management. The goal is to maintain blood glucose levels within a safe range, where the "risk" involves life-threatening hypoglycemia or hyperglycemia.

In both settings, the DR and WDR estimators demonstrated superior stability and precision compared to standard Importance Sampling. Specifically, when calculating the Conditional Value-at-Risk (CVaR), the DR-based approach showed significantly lower Mean Squared Error (MSE) and bias, particularly as trajectory lengths increased.

Conclusion

This work advances the field of safe reinforcement learning by providing a robust, theoretically sound method for assessing risk in complex MDPs. By lifting OPRA from bandits to MDPs and introducing the DR CDF estimator, the authors provide a path toward more reliable policy evaluation in domains where the cost of failure is high. Future work may explore marginalized importance sampling to further mitigate the curse of horizon and investigate adaptive selection methods for specific risk functionals.

Summary updated

Abstract

Addressing such diverse ends as safety alignment with human preferences, and the efficiency of learning, a growing line of reinforcement learning research focuses on risk functionals that depend on the entire distribution of returns. Recent work on \emph{off-policy risk assessment} (OPRA) for contextual bandits introduced consistent estimators for the target policy's CDF of returns along with finite sample guarantees that extend to (and hold simultaneously over) all risk. In this paper, we lift OPRA to Markov decision processes (MDPs), where importance sampling (IS) CDF estimators suffer high variance on longer trajectories due to small effective sample size. To mitigate these problems, we incorporate model-based estimation to develop the first doubly robust (DR) estimator for the CDF of returns in MDPs. This estimator enjoys significantly less variance and, when the model is well specified, achieves the Cramer-Rao variance lower bound. Moreover, for many risk functionals, the downstream estimates enjoy both lower bias and lower variance. Additionally, we derive the first minimax lower bounds for off-policy CDF and risk estimation, which match our error bounds up to a constant factor. Finally, we demonstrate the precision of our DR CDF estimates experimentally on several different environments.
BibTeX
@misc{huang2022off,
  author = {Audrey Huang and Liu Leqi and Zachary Chase Lipton and Kamyar Azizzadenesheli},
  title = {{Off-Policy Risk Assessment in Markov Decision Processes}},
  year = {2022},
  eprint = {2209.10444},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.10444},
}
Figure