mlsanityData to 7 Oct 2026

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

arXiv 2102.02981 ↗First posted 5 Feb 2021cs.LG math.ST stat.MLcited by 54

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

Key facts. Cited by 54 papers in the map (data through 7 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.

Builds on

19 of 54 references.

Closest ancestors · 3

Same direction, newest first

  1. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient8 Nov
  2. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  3. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul

Other references · 16

  1. 2016Error bounds for approximations with deep ReLU networkscited by 567
  2. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  3. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  4. 2019Orthogonal Statistical Learningcited by 150
  5. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  6. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  7. 2020Minimax Estimation of Conditional Moment Modelscited by 83
  8. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  9. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  10. 2018De-Biased Machine Learning of Global and Local Parameters Using Regularized Riesz Representerscited by 34
  11. 2017Augmented Minimax Linear Estimationcited by 33
  12. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 24
4 more
  1. 2019A unifying approach for doubly-robust ℓ1 regularized estimation of causal contrastscited by 15
  2. 2020Instrumental Variable Regression via Kernel Maximum Moment Losscited by 14
  3. 2017Finite-Sample Optimal Estimation and Inference on Average Treatment Effects Under Unconfoundednesscited by 11
  4. 2020Minimax Value Interval for Off-Policy Evaluation and Policy Optimizationcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 16; 2023: 9; 2024: 7; 2025: 5; 2026: 3.

54 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  3. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  4. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  5. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  6. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  7. 2021A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processescited by 34
  8. 2022On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluationcited by 33
  9. 2021Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learningcited by 32
  10. 2022Off-Policy Confidence Interval Estimation with Confounded Markov Decision Processcited by 31
  11. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  12. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
38 more
  1. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  2. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  3. 2022Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processescited by 19
  4. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  5. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  6. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  7. 2021Projected State-action Balancing Weights for Offline Reinforcement Learningcited by 16
  8. 2024Diffusing States and Matching Scores: A New Framework for Imitation Learningcited by 16
  9. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  10. 2023Minimax Instrumental Variable Regression and L2 Convergence Guarantees without Identification or Closednesscited by 13
  11. 2022Testing Stationarity and Change Point Detection in Reinforcement Learningcited by 12
  12. 2022Inference on Strongly Identified Functionals of Weakly Identified Functionscited by 12
  13. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  14. 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Datacited by 11
  15. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
  16. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  17. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  18. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  19. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 9
  20. 2022Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributionscited by 8
  21. 2021Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networkscited by 7
  22. 2024Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimalcited by 7
  23. 2023Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Frameworkcited by 6
  24. 2024The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regretcited by 6
  25. 2023Revisiting Bellman Errors for Offline Model Selectioncited by 5
  26. 2025Inverse Reinforcement Learning with Just Classification and a Few Regressionscited by 4
  27. 2021Pessimistic Model Selection for Offline Deep Reinforcement Learningcited by 3
  28. 2022Policy evaluation from a single path: Multi-step methods, mixing and mis-specificationcited by 3
  29. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  30. 2025Optimality and Adaptivity of Deep Neural Features for Instrumental Variable Regressioncited by 3
  31. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  32. 2023A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observationscited by 2
  33. 2025Bellman Calibration for V-Learning in Offline Reinforcement Learningcited by 2
  34. 2025Fitted Q-Evaluation without Bellman Completeness via Occupancy Weightingcited by 1
  35. 2026A Covering Framework for Offline POMDPs Learning using Belief Space Metriccited by 1
  36. 2023Deep Spectral Q-learning with Application to Mobile Healthcited by 0
  37. 2023Minimax Weight Learning for Absorbing MDPscited by 0
  38. 2024Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Datacited by 0

50 most cited of 54 All 54 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  3. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  4. 2023Offline Reinforcement Learning with Additional Covering Distributions
  5. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation
  6. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps
  7. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game