Minimax Off-Policy Evaluation for Multi-Armed Bandits

Cong Ma, Banghua Zhu, Jiantao Jiao, Martin J. Wainwright

Introduction

Off-Policy Evaluation (OPE) is a critical component of data-driven decision-making, particularly in domains where online experimentation is unethical, dangerous, or prohibitively expensive, such as clinical trials and autonomous driving. OPE allows researchers to estimate the performance of a new "target" policy using historical data collected by a different "behavior" policy.

The primary challenge in OPE is the distribution shift between the behavior and target policies. While asymptotic theory suggests that simple estimators perform well as the data size $n$ approaches infinity, these theories often fail in finite-sample regimes where the number of actions $k$ is large relative to $n$. This paper provides a comprehensive minimax analysis of OPE for multi-armed bandits, establishing the absolute statistical limits and designing algorithms that achieve them across three distinct knowledge regimes.

Methodology and Knowledge Regimes

The authors analyze OPE performance based on the level of information available regarding the behavior policy:

1. Known Behavior Policy

When the behavior policy is fully known, the authors advocate for the Switch Estimator. This approach adaptively chooses between a "plug-in" method (estimating rewards directly) and "importance sampling" (weighting rewards by likelihood ratios). The paper proves that the Switch estimator is minimax rate-optimal for all sample sizes. To implement this, the authors provide a convex program to determine the optimal threshold for switching between the two methods for any given sample size.

2. Unknown Behavior Policy

In scenarios where the behavior policy is unknown, a global minimax risk is impossible because an adversary could select a particularly difficult unknown policy. To address this, the authors introduce the Minimax Competitive Ratio, which compares an estimator's performance against an "oracle" that knows the behavior policy. They demonstrate that the simple Plug-in Estimator is near-optimal in this setting, as it automatically adapts to the support size of the target policy.

3. Partial Knowledge

In cases where only the minimum exploration probability (the "floor" of the behavior policy, $\nu$) is known, the authors develop a novel Chebyshev Estimator. This method uses Chebyshev polynomials to approximate the inverse of the behavior policy. This functional approximation effectively reduces the bias that typically plagues standard estimators when certain actions are rarely observed in the historical data.

Experimental Validation

The theoretical findings were validated using both simulated and real-world datasets:

  • Simulations: Using Bernoulli reward distributions, the authors designed "unfriendly" behavior policies with low probabilities on specific actions. The results showed that the Switch estimator consistently achieves lower Mean Squared Error (MSE) than pure Importance Sampling or pure Plug-in estimators across all sample sizes.
  • MovieLens 25M: Using this real-world dataset of movie ratings, the authors treated movies as "arms" and ratings as "rewards." By subsampling the data, they created a synthetic OPE environment where user movie-watching habits (behavior policy) differed from a uniform target policy. The experiments confirmed that while the Switch estimator performs best with oracle knowledge, the Chebyshev estimator significantly outperforms the standard plug-in estimator in small-sample regimes by reducing bias.

Key Insights

  • Optimality of the Switch: The paper moves beyond heuristics to prove that the Switch estimator is minimax rate-optimal for finite samples, not just in the limit.
  • The Knowledge Gap: There is a fundamental statistical penalty for not knowing the behavior policy, proportional to the support size of the target policy.
  • Plug-in Adaptivity: The plug-in estimator is a powerful tool when the behavior policy is unknown because of its inherent ability to adapt to the target policy's support.
  • Polynomial Bias Reduction: The Chebyshev estimator provides a "rescue" mechanism for low-exploration scenarios, maintaining a $1/\sqrt{n}$ error decay where other estimators might plateau due to bias.

Conclusion and Future Work

This research establishes the statistical boundaries of OPE in multi-armed bandits. While it provides optimal estimators for various knowledge regimes, several avenues for future work remain. These include extending minimax-optimal guarantees to Contextual Bandits and full Markov Decision Processes (MDPs), handling unbounded reward distributions, and developing versions of the Chebyshev estimator that can adapt to exploration levels without prior knowledge of the minimum probability $\nu$.

Summary updated

BibTeX
@article{ma2022minimax,
  author = {Cong Ma and Banghua Zhu and Jiantao Jiao and Martin J. Wainwright},
  title = {{Minimax Off-Policy Evaluation for Multi-Armed Bandits}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=65mj5Ij34Ls},
}
Figure