mlsanityData to 14 Oct 2026

Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient

arXiv 2210.00750 ↗First posted 3 Oct 2022cs.LG cs.AI stat.MLcited by 12

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

Abstract (arXiv)

Offline reinforcement learning, which aims at optimizing sequential decision-making strategies with historical data, has been extensively applied in real-life applications. State-Of-The-Art algorithms usually leverage powerful function approximators (e.g. neural networks) to alleviate the sample complexity hurdle for better empirical performances. Despite the successes, a more systematic understanding of the statistical complexity for function approximation remains lacking. Towards bridging the gap, we take a step by considering offline reinforcement learning with differentiable function class approximation (DFA). This function class naturally incorporates a wide range of models with nonlinear/nonconvex structures. Most importantly, we show offline RL with differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning (PFQL) algorithm, and our results provide the theoretical basis for understanding a variety of practical heuristics that rely on Fitted Q-Iteration style design. In addition, we further improve our guarantee with a tighter instance-dependent characterization. We hope our work could draw interest in studying reinforcement learning with differentiable function approximation beyond the scope of current research.

Key facts. Cited by 12 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 65 of its 88 references that are in the map. First posted on arXiv 3 Oct 2022.

Builds on

65 of 88 references.

Closest ancestors · 22

Same direction, newest first

  1. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward13 Jun
  2. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  4. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  5. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  6. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  7. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  8. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  9. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  10. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  11. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  12. 2021Uncertainty Weighted Actor-Critic for Offline Reinforcement Learning17 May
10 more
  1. 2021Nearly Horizon-Free Offline Reinforcement Learning25 Mar
  2. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  3. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  4. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  5. 2020Batch Value-function Approximation with Only Realizability11 Aug
  6. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  7. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
  8. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation19 Jun
  9. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  10. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar

Other references · 43

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  2. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2017A Brief Survey of Deep Reinforcement Learningcited by 483
  7. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  8. 2016Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collectioncited by 316
  9. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  10. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  11. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  12. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
31 more
  1. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  2. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  3. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  7. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  8. 2017Equivalence Between Policy Gradients and Soft Q-Learningcited by 173
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2017Deep Reinforcement Learning for De-Novo Drug Designcited by 161
  11. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  12. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  13. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 119
  14. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  15. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  16. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  17. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  18. 2017Applications of Deep Learning and Reinforcement Learning to Biological Datacited by 45
  19. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  20. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
  21. 2017Provably Optimal Algorithms for Generalized Linear Contextual Banditscited by 38
  22. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  23. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  24. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  25. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  26. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 28
  27. 2022Sample Efficient Deep Reinforcement Learning via Uncertainty Estimationcited by 27
  28. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  29. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  30. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 16
  31. 2020Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?cited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 9; 2024: 2; 2025: 0; 2026: 1.

12 papers.

  1. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  2. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 9
  3. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  4. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 6
  5. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  6. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  7. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  8. 2024Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learningcited by 2
  9. 2024NetworkGym: Reinforcement Learning Environments for Multi-Access Traffic Management in Network Simulationcited by 2
  10. 2023Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifoldscited by 1
  11. 2026Less is More: Clustered Cross-Covariance Control for Offline RLcited by 1
  12. 2023Sample Complexity of Preference-Based Nonparametric Off-Policy Evaluation with Deep Networkscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning
  2. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coverage
  3. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian
  4. 2021Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
  5. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  6. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation
  7. 2020MOReL : Model-Based Offline Reinforcement Learning
  8. 2025Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear qπ-Realizability and Concentrability