mlsanityData to 7 Oct 2026

When is Agnostic Reinforcement Learning Statistically Tractable?

arXiv 2310.06113 ↗First posted 9 Oct 2023cs.LG cs.AI math.STcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the problem of agnostic PAC reinforcement learning (RL): given a policy class Pi, how many rounds of interaction with an unknown MDP (with a potentially large state and action space) are required to learn an ε-suboptimal policy with respect to Pi? Towards that end, we introduce a new complexity measure, called the spanning capacity, that depends solely on the set Pi and is independent of the MDP dynamics. With a generative model, we show that for any policy class Pi, bounded spanning capacity characterizes PAC learnability. However, for online RL, the situation is more subtle. We show there exists a policy class Pi with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for agnostic learnability between generative access and online access models (as well as between deterministic/stochastic MDPs under online access). On the positive side, we identify an additional sunflower structure, which in conjunction with bounded spanning capacity enables statistically efficient online RL via a new algorithm called POPLER, which takes inspiration from classical importance sampling methods as well as techniques for reachable-state identification and policy evaluation in reward-free exploration.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 73 of its 125 references that are in the map. First posted on arXiv 9 Oct 2023.

Builds on

73 of 125 references.

References · 73

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2015Continuous control with deep reinforcement learningcited by 3,279
  4. 2015Trust Region Policy Optimizationcited by 2,503
  5. 2019Solving Rubik's Cube with a Robot Handcited by 699
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2018Behavioral Cloning from Observationcited by 482
  9. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  10. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  11. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  12. 2016Deep Reinforcement Learning for Dialogue Generationcited by 286
38 more
  1. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  4. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  7. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  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. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  13. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  14. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  15. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  16. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  17. 2014Reinforcement and Imitation Learning via Interactive No-Regret Learningcited by 116
  18. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  19. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  20. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  21. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  22. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  23. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  24. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  25. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  26. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  27. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  28. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  29. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  30. 2018Private PAC learning implies finite Littlestone dimensioncited by 73
  31. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  32. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  33. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  34. 2022A Characterization of Multiclass Learnabilitycited by 66
  35. 2014Optimal Learners for Multiclass Problemscited by 65
  36. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  37. 2014Minimax Analysis of Active Learningcited by 61
  38. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60

50 most cited of 73 All 73 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

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

8 papers.

  1. 2024Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHFcited by 29
  2. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6
  3. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  4. 2025Efficient Imitation under Misspecificationcited by 4
  5. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learningcited by 1
  6. 2023Agnostic Interactive Imitation Learning: New Theory and Practical Algorithmscited by 0
  7. 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizabilitycited by 0
  8. 2026The Sample Complexity of Policy Learning with Mu-Resetscited by 0