High-Confidence Off-Policy (or Counterfactual) Variance Estimation

Yash Chandak, Shiv Shankar, Philip S. Thomas

TL;DR

This paper introduces the first model-free, unbiased, and consistent estimator for the variance of returns in off-policy reinforcement learning. By combining a clever double-sampling trick with a new "coupled-decision" importance sampling technique, the authors provide high-confidence bounds that allow practitioners to assess the risk of a new policy before it is ever deployed.

What Problem Does This Paper Address?

In reinforcement learning (RL), we often want to evaluate a new policy ($\pi$) using data collected from an old one ($\beta$). While estimating the expected (mean) return is well-studied, knowing the mean isn't enough for high-stakes applications like medical treatments or autonomous driving. In these fields, the variance—a proxy for risk and reliability—is just as critical.

The challenge is that standard Importance Sampling (IS), the workhorse of off-policy evaluation, is designed to correct for the mean. As shown in Figure 1, the distribution of importance-weighted returns ($\rho$) has the correct mean $\mu(\pi)$, but its variance is generally not equal to the true variance $\sigma^2(\pi)$ of the evaluation policy. Naive attempts to estimate variance off-policy often result in biased or inconsistent estimates because they inadvertently "square" the importance weights, leading to unstable and incorrect results.

Figure 1: Illustrative example of the distributions of returns from a behavior policy β, and evaluation policy π, along with the importance weighted returns ρ, discussed later. Given trajectories from the behavior policy β, we aim to estimate and bound the variance, σ2(π), of returns under an evaluation policy π, with high confidence. Note that the distribution of importance-weighted returns ρ has the mean value µ(π), but might have variance not equal to σ2(π).

Methods

The authors propose a suite of techniques to tackle off-policy variance estimation (OVE) and its high-confidence counterpart (HCOVE):

  1. Double-Sampling Trick: To get an unbiased estimate of the squared mean term in the variance formula ($V[X] = E[X^2] - E[X]^2$), the authors split the off-policy data into two independent sets. They estimate the mean return from each set separately and multiply them together. This prevents the "self-coupling" of importance weights that causes bias in naive estimators.
  2. Coupled-Decision Importance Sampling (CDIS): Standard Per-Decision IS (PDIS) reduces variance by recognizing that a reward at time $t$ only depends on actions taken up to time $t$. The authors extend this to squared returns, which involve cross-terms of rewards at different times ($R_i \cdot R_j$). CDIS uses importance ratios only up to the maximum of the two time steps ($\max(i, j)$), significantly reducing the estimator's variance.
  3. High-Confidence Bounds: The paper provides two ways to get confidence intervals:
  4. Concentration Inequalities: They use interval propagation (mapping bounds on $X$ to bounds on $X^2$, as seen in Figure 2) and a control-variate $\xi$ to handle the "long-tail" behavior typical of importance sampling.
  5. Statistical Bootstrapping: A more practical, though approximately correct, method that often yields tighter intervals.
Figure 2: Two separate examples that show how interval propagation can be used to map confidence intervals for X (in red) to confidence intervals for Y = X2 (in blue).

Datasets

The methods were evaluated on three simulated domains:

  • Recommender System: Simulates online recommendations where customer experience variability directly impacts financial risk.
  • Diabetes Treatment: Uses the FDA-approved T1DMS simulator for Type-1 Diabetes. Here, high variance in blood-glucose control could indicate potential harm to a patient.
  • Gridworld: A standard $4 \times 4$ stochastic environment used to demonstrate the variance-reduction benefits of CDIS over longer horizons.

Key Insights and Ideas

  • The Bias of Squaring: The "aha" moment is realizing that $E[\rho^2 G^2]$ is not $E_\pi[G^2]$. Standard IS fails for variance because the second moment of the importance-weighted return involves $\rho^2$, which doesn't integrate to 1.
  • Independence is Key: The double-sampling trick works because trajectories are independent. By ensuring the two mean estimates use different data, the expectation of their product correctly factors into the product of their expectations.
  • Structure Matters: Just as PDIS is essential for mean estimation in MDPs, CDIS is essential for variance. It leverages the temporal structure of rewards to discard irrelevant future importance ratios.
  • Taming Long Tails: Importance sampling estimators often have extreme outliers (long tails). The authors' use of a control-variate $\xi$ allows them to "flip" the distribution, making it possible to use robust lower-bound techniques to find valid upper bounds.

Key Results

The experiments (summarized in Figure 3) validate the theoretical claims:

  • Unbiasedness: The proposed estimator $\hat{\sigma}^2_n$ (green line) accurately tracks the true variance $\sigma^2(\pi)$ (black dashed line) across all domains as the number of trajectories increases.
  • Guaranteed Coverage: Bounds derived from concentration inequalities (red/orange dashed lines) always contained the true variance within the specified failure rate $\delta = 0.05$.
  • Efficiency: Bootstrap bounds (blue/cyan dashed lines) were significantly tighter than concentration inequalities, though they occasionally exceeded the failure rate at small sample sizes, as expected for an approximate method.
Figure 3: Experimental results showing the estimator's convergence (bottom) and the reliability of the confidence intervals (top) across three domains.

Limitations and Future Work

  • IS Curse: Like all IS-based methods, the variance of the estimator can still scale exponentially with the trajectory horizon.
  • Support Assumption: The behavior policy must cover all trajectories possible under the evaluation policy.
  • Knowledge of $\beta$: The method requires knowing the action probabilities of the behavior policy. If these are estimated from data, the variance estimator might become biased.
  • Future Directions: The authors suggest integrating these variance estimates into risk-sensitive policy optimization and exploring "doubly robust" versions that incorporate environment models to further reduce variance.

Summary updated

Abstract

Many sequential decision-making systems leverage data collected using prior policies to propose a new policy. For critical applications, it is important that high-confidence guarantees on the new policy's behavior are provided before deployment, to ensure that the policy will behave as desired. Prior works have studied high-confidence off-policy estimation of the expected return, however, high-confidence off-policy estimation of the variance of returns can be equally critical for high-risk applications. In this paper, we tackle the previously open problem of estimating and bounding, with high confidence, the variance of returns from off-policy data
BibTeX
@inproceedings{chandak2021high,
  author = {Yash Chandak and Shiv Shankar and Philip S. Thomas},
  title = {{High-Confidence Off-Policy (or Counterfactual) Variance Estimation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=1VruPCac4k},
}
Figure