Toward Minimax Off-policy Value Estimation

Lihong Li, Rémi Munos, Csaba SzepesváriAISTATS 2015 · OpenReview

Abstract: This paper studies the off-policy evaluation problem, where one aims to estimate the value of a target policy based on a sample of observations collected by another policy. We first consider the multi-armed bandit case, establish a finite-time minimax risk lower bound, and analyze the risk of three standard estimators. It is shown that in a large class of settings the so-called regression estimator is minimax optimal up to a constant that depends on the number of actions, while the other two can be arbitrarily worse even in the limit of infinitely many data points, despite their empirical success and popularity. The performance of these estimators are studied in synthetic and real problems; illustrating the nontriviality of this simple task. Finally the results are extended to the problem of off-policy evaluation in contextual bandits and fixed-horizon Markov decision processes.

Introduction

In Reinforcement Learning (RL), off-policy evaluation (OPE) is a critical task: estimating the performance of a new "target" policy using historical data generated by a different "behavior" policy. This is essential in domains where deploying an untested policy is risky or expensive, such as healthcare or autonomous driving. While various estimators exist, a fundamental question remains: what is the absolute best performance possible for a given amount of data? This paper establishes the theoretical "speed limits" (minimax lower bounds) for OPE and evaluates how standard estimators measure up.

Estimators and Methodology

The study primarily focuses on the multi-armed bandit (MAB) setting, later extending to contextual bandits and Markov Decision Processes (MDPs). Three primary estimators are analyzed:

  1. Importance Sampling (IS): Re-weights rewards by the ratio of target to behavior policy probabilities. It is unbiased but often suffers from high variance.
  2. Weighted Importance Sampling (WIS): A normalized version of IS that reduces variance at the cost of introducing bias.
  3. Regression Estimator (REG): Estimates mean rewards for each action using sample means, then calculates the expected value under the target policy.
Comparison of $n \times \text{MSE}$ for IS, WIS, and REG across different reward distribution settings.

As shown in Figure 1, while IS and WIS often reach a performance plateau, the Regression Estimator (REG) demonstrates superior asymptotic behavior, eventually reaching lower error levels as the sample size $n$ increases.

Theoretical Limits: The Minimax Lower Bound

The core contribution is the derivation of a minimax lower bound for the Mean Squared Error (MSE). This bound represents a theoretical floor; no algorithm can consistently achieve a lower error rate across all possible reward distributions.

A key insight is that the Regression Estimator can be viewed as an IS estimator that uses empirical estimates of the behavior policy rather than true probabilities. This "noisy" empirical estimate actually acts as a variance reduction technique, making the estimator more robust. The authors prove that while REG is asymptotically minimax optimal, standard IS and WIS are fundamentally sub-optimal, with errors remaining higher than the theoretical limit even as data approaches infinity.

Results and the "K-Penalty"

While the Regression Estimator is asymptotically optimal, its performance in the "small data" regime is constrained by the number of actions ($K$). If the sample size $n$ is small relative to $K$, the error can be significant.

The effect of the number of actions ($K$) on the $n \times \text{MSE}$ of the Regression Estimator.

Figure 2 illustrates this "K-penalty." As $K$ increases, the peak error (normalized by $n$) grows and occurs at larger sample sizes. This highlights a critical trade-off: REG is the best choice for large datasets, but its finite-sample performance is sensitive to the complexity of the action space.

Empirical Validation

The theoretical findings were validated using both synthetic data and real-world search engine logs. In the search engine experiments, actions represented different Search Engine Result Pages (SERPs) and rewards were binary clicks. The results confirmed that REG eventually outperforms WIS as sample size increases, though WIS can be more competitive in very low-data regimes where the K-penalty is most pronounced.

Conclusion

This work establishes that the Regression Estimator is the minimax optimal choice for off-policy evaluation in the limit of large data. However, the exponential growth of risk with the horizon ($H$) in MDPs—the "curse of horizon"—remains a significant challenge. Future work may explore hybrid estimators that combine the low-data stability of WIS with the asymptotic optimality of REG, as well as extending these bounds to high-dimensional contextual spaces.

Summary updated

Abstract

This paper studies the off-policy evaluation problem, where one aims to estimate the value of a target policy based on a sample of observations collected by another policy. We first consider the multi-armed bandit case, establish a finite-time minimax risk lower bound, and analyze the risk of three standard estimators. It is shown that in a large class of settings the so-called regression estimator is minimax optimal up to a constant that depends on the number of actions, while the other two can be arbitrarily worse even in the limit of infinitely many data points, despite their empirical success and popularity. The performance of these estimators are studied in synthetic and real problems; illustrating the nontriviality of this simple task. Finally the results are extended to the problem of off-policy evaluation in contextual bandits and fixed-horizon Markov decision processes.
BibTeX
@inproceedings{li2015toward,
  author = {Lihong Li and Rémi Munos and Csaba Szepesvári},
  title = {{Toward Minimax Off-policy Value Estimation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=31rDKKNK1ne},
}
Figure