mlsanityData to 7 Oct 2026

Bilinear Classes: A Structural Framework for Provable Generalization in RL

arXiv 2103.10897 ↗First posted 19 Mar 2021cs.LG cs.AI math.OCcited by 176

Not on the map. Why?

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

Abstract (arXiv)

This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function approximation. The framework incorporates nearly all existing models in which a polynomial sample complexity is achievable, and, notably, also includes new models, such as the Linear Q^*/V^* model in which both the optimal Q-function and the optimal V-function are linear in some known feature space. Our main result provides an RL algorithm which has polynomial sample complexity for Bilinear Classes; notably, this sample complexity is stated in terms of a reduction to the generalization error of an underlying supervised learning sub-problem. These bounds nearly match the best known sample complexity bounds for existing models. Furthermore, this framework also extends to the infinite dimensional (RKHS) setting: for the the Linear Q^*/V^* model, linear MDPs, and linear mixture MDPs, we provide sample complexities that have no explicit dependence on the explicit feature dimension (which could be infinite), but instead depends only on information theoretic quantities.

Key facts. Cited by 176 papers in the map (data through 7 Oct 2026). Builds on 22 of its 52 references that are in the map. First posted on arXiv 19 Mar 2021.

Builds on

22 of 52 references.

References · 22

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2013Learning to Optimize Via Posterior Samplingcited by 253
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  8. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  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. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
10 more
  1. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  2. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  3. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  4. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  5. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  6. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  7. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  8. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  9. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  10. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 47; 2023: 49; 2024: 32; 2025: 14; 2026: 13.

176 papers.

Sort:

By area:

  1. 2023Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuningcited by 230
  2. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  3. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  4. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  5. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  7. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  8. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  9. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  10. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  11. 2025Outcome-based Exploration for LLM Reasoningcited by 79
  12. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
38 more
  1. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  2. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  3. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  4. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  5. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  6. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  7. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  8. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  9. 2024Dataset Reset Policy Optimization for RLHFcited by 41
  10. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  11. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  12. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  13. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  14. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  15. 2022Learning with little mixingcited by 33
  16. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  17. 2022On the Complexity of Adversarial Decision Makingcited by 32
  18. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  19. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  20. 2024Hybrid Inverse Reinforcement Learningcited by 31
  21. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  22. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  23. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 29
  24. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  25. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  26. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  27. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  28. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  29. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  30. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  31. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  32. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  33. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  34. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  35. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  36. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  37. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  38. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20

50 most cited of 176 All 176 (JSON)