mlsanityData to 7 Oct 2026

A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning

arXiv 2209.15634 ↗First posted 30 Sep 2022cs.LG cs.AI stat.MLcited by 31

Not on the map. Why?

Abstract (arXiv)

With the increasing need for handling large state and action spaces, general function approximation has become a key technique in reinforcement learning (RL). In this paper, we propose a general framework that unifies model-based and model-free RL, and an Admissible Bellman Characterization (ABC) class that subsumes nearly all Markov Decision Process (MDP) models in the literature for tractable RL. We propose a novel estimation function with decomposable structural properties for optimization-based exploration and the functional eluder dimension as a complexity measure of the ABC class. Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed, achieving regret bounds that match or improve over the best-known results for a variety of MDP models. In particular, for MDPs with low Witness rank, under a slightly stronger assumption, OPERA improves the state-of-the-art sample complexity results by a factor of dH. Our framework provides a generic interface to design and analyze new RL models and algorithms.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Builds on 38 of its 68 references that are in the map. First posted on arXiv 30 Sep 2022.

Builds on

38 of 68 references.

References · 38

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  5. 2018Is Q-learning Provably Efficient?cited by 485
  6. 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 373
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  8. 2013Learning to Optimize Via Posterior Samplingcited by 253
  9. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  10. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  11. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  12. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
26 more
  1. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  2. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  7. 2017A Rewriting System for Convex Optimization Problemscited by 178
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2015Model Predictive Path Integral Control using Covariance Variable Importance Samplingcited by 122
  13. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  14. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  15. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  16. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  17. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  18. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  19. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  20. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  21. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 78
  22. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  23. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  24. 2019An Online Learning Approach to Model Predictive Controlcited by 29
  25. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  26. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 18; 2024: 8; 2025: 3; 2026: 1.

31 papers.

Sort:

By area:

  1. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  2. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  3. 2023Optimal Exploration for Model-Based RL in Nonlinear Systemscited by 17
  4. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  5. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  6. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  7. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  8. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  9. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
  10. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  11. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  12. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
19 more
  1. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  2. 2023Low-Switching Policy Gradient with Exploration via Online Sensitivity Samplingcited by 6
  3. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  4. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  5. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  6. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  7. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?cited by 4
  8. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  9. 2023Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimensioncited by 3
  10. 2023The Effective Horizon Explains Deep RL Performance in Stochastic Environmentscited by 3
  11. 2024Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximationcited by 3
  12. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  13. 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexitycited by 2
  14. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  15. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  16. 2025Episodic Contextual Bandits with Knapsacks under Conversion Modelscited by 1
  17. 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Errorcited by 0
  18. 2025The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportabilitycited by 0
  19. 2026Provably Efficient Offline-to-Online Value Adaptation with General Function Approximationcited by 0