mlsanityData to 7 Oct 2026

Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison

arXiv 2003.03924 ↗First posted 9 Mar 2020cs.LG cs.AI stat.MLcited by 22

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

Abstract (arXiv)

We prove performance guarantees of two algorithms for approximating Q^star in batch reinforcement learning. Compared to classical iterative methods such as Fitted Q-Iteration---whose performance loss incurs quadratic dependence on horizon---these methods estimate (some forms of) the Bellman error and enjoy linear-in-horizon error propagation, a property established for the first time for algorithms that rely solely on batch data and output stationary policies. One of the algorithms uses a novel and explicit importance-weighting correction to overcome the infamous "double sampling" difficulty in Bellman error estimation, and does not use any squared losses. Our analyses reveal its distinct characteristics and potential advantages compared to classical algorithms.

Key facts. Cited by 22 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 9 of its 33 references that are in the map. First posted on arXiv 9 Mar 2020.

Builds on

9 of 33 references.

References · 9

  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  4. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  5. 2019Doubly robust off-policy evaluation with shrinkagecited by 87
  6. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  7. 2016Generalized Optimal Matching Methods for Causal Inferencecited by 39
  8. 2019A Kernel Loss for Solving the Bellman Equationcited by 37
  9. 2017Augmented Minimax Linear Estimationcited by 33

Built on by

Cited by year

Citing papers per year: 2020: 2; 2021: 6; 2022: 8; 2023: 6.

22 papers.

Sort:

By area:

  1. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  2. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  4. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  5. 2022When Should We Prefer Offline Reinforcement Learning Over Behavioral Cloning?cited by 86
  6. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  7. 2020Provably Good Batch Reinforcement Learning Without Great Explorationcited by 77
  8. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  9. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  10. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  11. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  12. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
10 more
  1. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  2. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  3. 2022Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networkscited by 12
  4. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  5. 2021Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Boundscited by 11
  6. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  7. 2023Quasi-optimal Reinforcement Learning with Continuous Actionscited by 7
  8. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?cited by 4
  9. 2023Statistical Learning under Heterogeneous Distribution Shiftcited by 1
  10. 2022Statistical Estimation of Confounded Linear MDPs: An Instrumental Variable Approachcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning
  2. 2021Approximated Multi-Agent Fitted Q Iteration
  3. 2020Batch Value-function Approximation with Only Realizability
  4. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
  5. 2021Continuous Doubly Constrained Batch Reinforcement Learning
  6. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
  7. 2024Fitted Q-Iteration via Max-Plus-Linear Approximation
  8. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity