# Minimax Off-Policy Evaluation for Multi-Armed Bandits

arXiv: https://arxiv.org/abs/2101.07781 · HTML: https://mlsanity.com/paper/2101.07781/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 37 references that are in the map.
- First posted on arXiv 19 Jan 2021.

## Builds on (most cited first, 7 of 7)

- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Hyperparameter Selection for Offline Reinforcement Learning](https://mlsanity.com/paper/2007.09055/) (2020)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Off-Policy Evaluation via Off-Policy Classification](https://mlsanity.com/paper/1906.01624/) (2019)

## Built on by (most cited first, 9 of 9)

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [High-probability sample complexities for policy evaluation with linear function approximation](https://mlsanity.com/paper/2305.19001/) (2023)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency](https://mlsanity.com/paper/2209.13075/) (2022)
- [Off-Policy Risk Assessment in Markov Decision Processes](https://mlsanity.com/paper/2209.10444/) (2022)
- [Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency](https://mlsanity.com/paper/2301.06240/) (2023)
- [Logarithmic Neyman Regret for Adaptive Estimation of the Average Treatment Effect](https://mlsanity.com/paper/2411.14341/) (2024)
- [Off-policy estimation with adaptively collected data: the power of online learning](https://mlsanity.com/paper/2411.12786/) (2024)
- [Optimistic Algorithms for Adaptive Estimation of the Average Treatment Effect](https://mlsanity.com/paper/2502.04673/) (2025)

## Abstract (arXiv)

We study the problem of off-policy evaluation in the multi-armed bandit model with bounded rewards, and develop minimax rate-optimal procedures under three settings. First, when the behavior policy is known, we show that the Switch estimator, a method that alternates between the plug-in and importance sampling estimators, is minimax rate-optimal for all sample sizes. Second, when the behavior policy is unknown, we analyze performance in terms of the competitive ratio, thereby revealing a fundamental gap between the settings of known and unknown behavior policies. When the behavior policy is unknown, any estimator must have mean-squared error larger -- relative to the oracle estimator equipped with the knowledge of the behavior policy -- by a multiplicative factor proportional to the support size of the target policy. Moreover, we demonstrate that the plug-in approach achieves this worst-case competitive ratio up to a logarithmic factor. Third, we initiate the study of the partial knowledge setting in which it is assumed that the minimum probability taken by the behavior policy is known. We show that the plug-in estimator is optimal for relatively large values of the minimum probability, but is sub-optimal when the minimum probability is low. In order to remedy this gap, we propose a new estimator based on approximation by Chebyshev polynomials that provably achieves the optimal estimation error. Numerical experiments on both simulated and real data corroborate our theoretical findings.