mlsanityData to 7 Oct 2026

Batch Value-function Approximation with Only Realizability

arXiv 2008.04990 ↗First posted 11 Aug 2020cs.LG stat.MLcited by 103

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

Abstract (arXiv)

We make progress in a long-standing problem of batch reinforcement learning (RL): learning Q^star from an exploratory and polynomial-sized dataset, using a realizable and otherwise arbitrary function class. In fact, all existing algorithms demand function-approximation assumptions stronger than realizability, and the mounting negative evidence has led to a conjecture that sample-efficient learning is impossible in this setting (Chen and Jiang, 2019). Our algorithm, BVFT, breaks the hardness conjecture (albeit under a stronger notion of exploratory data) via a tournament procedure that reduces the learning problem to pairwise comparison, and solves the latter with the help of a state-action partition constructed from the compared functions. We also discuss how BVFT can be applied to model selection among other extensions and open problems.

Key facts. Cited by 103 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. First posted on arXiv 11 Aug 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 2; 2021: 20; 2022: 26; 2023: 22; 2024: 14; 2025: 10; 2026: 9.

103 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  2. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  3. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  7. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  8. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  9. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  10. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  11. 2022Sparse Mixture-of-Experts are Domain Generalizable Learnerscited by 85
  12. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
38 more
  1. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  2. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  3. 2021Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settingscited by 68
  4. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  5. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  6. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  7. 2023Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcarecited by 41
  8. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  9. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  10. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  11. 2021Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learningcited by 32
  12. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  13. 2023Adversarial Model for Offline Reinforcement Learningcited by 31
  14. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  15. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  16. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  17. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  18. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  19. 2022Performative Reinforcement Learningcited by 25
  20. 2022Transfer Learning for Contextual Multi-armed Banditscited by 24
  21. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  22. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  23. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  24. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  25. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  26. 2022Federated Offline Reinforcement Learningcited by 13
  27. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  28. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  29. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  30. 2023Towards Assessing and Benchmarking Risk-Return Tradeoff of Off-Policy Evaluationcited by 13
  31. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
  32. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  33. 2022Data-Efficient Pipeline for Offline Reinforcement Learning with Limited Datacited by 12
  34. 2023Efficient Policy Evaluation with Offline Data Informed Behavior Policy Designcited by 12
  35. 2021Model Selection in Batch Policy Optimizationcited by 11
  36. 2022Max-Min Off-Policy Actor-Critic Method Focusing on Worst-Case Robustness to Model Misspecificationcited by 11
  37. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  38. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10

50 most cited of 103 All 103 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2020Provably Good Batch Reinforcement Learning Without Great Exploration
  2. 2021Continuous Doubly Constrained Batch Reinforcement Learning
  3. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
  4. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation
  5. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity
  6. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
  7. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting
  8. 2019On Value Functions and the Agent-Environment Boundary