mlsanityData to 14 Oct 2026

Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation

arXiv 2002.09516 ↗First posted 21 Feb 2020cs.LG math.ST stat.MLcited by 120

Not on the map. Why?

Cited by 59 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history generated by unknown behavioral policies. We study a regression-based fitted Q iteration method, and show that it is equivalent to a model-based method that estimates a conditional mean embedding of the transition operator. We prove that this method is information-theoretically optimal and has nearly minimal estimation error. In particular, by leveraging contraction property of Markov processes and martingale concentration, we establish a finite-sample instance-dependent error upper bound and a nearly-matching minimax lower bound. The policy evaluation error depends sharply on a restricted chi2-divergence over the function class between the long-term distribution of the target policy and the distribution of past data. This restricted chi2-divergence is both instance-dependent and function-class-dependent. It characterizes the statistical limit of off-policy evaluation. Further, we provide an easily computable confidence bound for the policy evaluator, which may be useful for optimistic planning and safe policy improvement.

Key facts. Cited by 120 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 3; 2021: 29; 2022: 32; 2023: 18; 2024: 21; 2025: 11; 2026: 6.

120 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  5. 2021Offline RL Without Off-Policy Evaluationcited by 151
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  7. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 95
  8. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  9. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  10. 2021DR3: Value-Based Deep Reinforcement Learning Requires Explicit Regularizationcited by 66
  11. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  12. 2025WorldGym: World Model as An Environment for Policy Evaluationcited by 64
38 more
  1. 2022How to Leverage Unlabeled Data in Offline Reinforcement Learningcited by 62
  2. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  3. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  4. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  5. 2021Bootstrapping Fitted Q-Evaluation for Off-Policy Inferencecited by 40
  6. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  7. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  8. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  9. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  10. 2022On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluationcited by 33
  11. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  12. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  13. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  14. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  15. 2022Proximal Point Imitation Learningcited by 26
  16. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  17. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  18. 2024Diffusion Model for Data-Driven Black-Box Optimizationcited by 24
  19. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  20. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 21
  21. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  22. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 18
  23. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  24. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  25. 2023Pseudo-Labeling for Kernel Ridge Regression under Covariate Shiftcited by 17
  26. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  27. 2024From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systemscited by 17
  28. 2021Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approachcited by 16
  29. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  30. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  31. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  32. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  33. 2021PowerGym: A Reinforcement Learning Environment for Volt-Var Control in Power Distribution Systemscited by 14
  34. 2022Offline Reinforcement Learning with Closed-Form Policy Improvement Operatorscited by 14
  35. 2022Federated Offline Reinforcement Learningcited by 13
  36. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  37. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  38. 2022Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networkscited by 12

50 most cited of 120 All 120 (JSON)