# Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Orthogonal Statistical Learning](https://mlsanity.com/paper/1901.09036/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [GenDICE: Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2002.09072/) (2020)
- [Off-Policy Evaluation via the Regularized Lagrangian](https://mlsanity.com/paper/2007.03438/) (2020)
- [Minimax Estimation of Conditional Moment Models](https://mlsanity.com/paper/2006.07201/) (2020)
- [Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning](https://mlsanity.com/paper/1909.05850/) (2019)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [De-Biased Machine Learning of Global and Local Parameters Using Regularized Riesz Representers](https://mlsanity.com/paper/1802.08667/) (2018)
- [Augmented Minimax Linear Estimation](https://mlsanity.com/paper/1712.00038/) (2017)
- [Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/2007.03760/) (2020)
- [A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting](https://mlsanity.com/paper/2011.01075/) (2020)
- [Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient](https://mlsanity.com/paper/2011.04019/) (2020)
- [A unifying approach for doubly-robust ℓ1 regularized estimation of causal contrasts](https://mlsanity.com/paper/1904.03737/) (2019)
- [Instrumental Variable Regression via Kernel Maximum Moment Loss](https://mlsanity.com/paper/2010.07684/) (2020)
- [Finite-Sample Optimal Estimation and Inference on Average Treatment Effects Under Unconfoundedness](https://mlsanity.com/paper/1712.04594/) (2017)
- [Minimax Value Interval for Off-Policy Evaluation and Policy Optimization](https://mlsanity.com/paper/2002.02081/) (2020)

## Built on by (most cited first, 30 of 56)

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning](https://mlsanity.com/paper/2103.13883/) (2021)
- [A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2111.06784/) (2021)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluation](https://mlsanity.com/paper/2201.06169/) (2022)
- [Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learning](https://mlsanity.com/paper/2110.14000/) (2021)
- [Off-Policy Confidence Interval Estimation with Confounded Markov Decision Process](https://mlsanity.com/paper/2202.10589/) (2022)
- [Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage](https://mlsanity.com/paper/2106.03207/) (2021)
- [Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2205.13589/) (2022)
- [Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization](https://mlsanity.com/paper/2111.13807/) (2021)
- [Future-Dependent Value-Based Off-Policy Evaluation in POMDPs](https://mlsanity.com/paper/2207.13081/) (2022)
- [Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processes](https://mlsanity.com/paper/2209.08666/) (2022)
- [Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theory](https://mlsanity.com/paper/2202.04970/) (2022)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [When is Realizability Sufficient for Off-Policy Reinforcement Learning?](https://mlsanity.com/paper/2211.05311/) (2022)
- [Projected State-action Balancing Weights for Offline Reinforcement Learning](https://mlsanity.com/paper/2109.04640/) (2021)
- [Diffusing States and Matching Scores: A New Framework for Imitation Learning](https://mlsanity.com/paper/2410.13855/) (2024)
- [Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings](https://mlsanity.com/paper/2105.06029/) (2021)
- [Minimax Instrumental Variable Regression and L2 Convergence Guarantees without Identification or Closedness](https://mlsanity.com/paper/2302.05404/) (2023)
- [Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems](https://mlsanity.com/paper/2307.12975/) (2023)
- [Testing Stationarity and Change Point Detection in Reinforcement Learning](https://mlsanity.com/paper/2203.01707/) (2022)
- [Inference on Strongly Identified Functionals of Weakly Identified Functions](https://mlsanity.com/paper/2208.08291/) (2022)
- [Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data](https://mlsanity.com/paper/2403.17091/) (2024)
- [Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm](https://mlsanity.com/paper/2103.09847/) (2021)
- [Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling](https://mlsanity.com/paper/2203.08248/) (2022)
- [Bellman Residual Orthogonalization for Offline Reinforcement Learning](https://mlsanity.com/paper/2203.12786/) (2022)
- [Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage](https://mlsanity.com/paper/2302.02392/) (2023)

## Abstract (arXiv)

We offer a theoretical characterization of off-policy evaluation (OPE) in reinforcement learning using function approximation for marginal importance weights and q-functions when these are estimated using recent minimax methods. Under various combinations of realizability and completeness assumptions, we show that the minimax approach enables us to achieve a fast rate of convergence for weights and quality functions, characterized by the critical inequality citepbartlett2005. Based on this result, we analyze convergence rates for OPE. In particular, we introduce novel alternative completeness conditions under which OPE is feasible and we present the first finite-sample result with first-order efficiency in non-tabular environments, i.e., having the minimal coefficient in the leading term.