mlsanityData to 14 Oct 2026

The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective

arXiv 2501.15910 ↗First posted 27 Jan 2025cs.LG cs.SY eess.SYcited by 6

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study the sample complexity of online reinforcement learning in the general hzyrevnon-episodic setting of nonlinear dynamical systems with continuous state and action spaces. Our analysis accommodates a large class of dynamical systems ranging from a finite set of nonlinear candidate models to models with bounded and Lipschitz continuous dynamics, to systems that are parametrized by a compact and real-valued set of parameters. In the most general setting, our algorithm achieves a policy regret of O(N ε2 + duln(m(ε))/ε2), where N is the time horizon, ε is a user-specified discretization width, du the input dimension, and m(ε) measures the complexity of the function class under consideration via its packing number. In the special case where the dynamics are parametrized by a compact and real-valued set of parameters (such as neural networks, transformers, etc.), we prove a policy regret of O(√duN p), where p denotes the number of parameters, recovering earlier sample-complexity results that were derived for linear time-invariant dynamical systems. While this article focuses on characterizing sample complexity, the proposed algorithms are likely to be useful in practice, due to their simplicity, their ability to incorporate prior knowledge, and their benign transient behaviors.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 56 of its 95 references that are in the map. First posted on arXiv 27 Jan 2025.

Builds on

56 of 95 references.

References · 56

  1. 2018Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Modelscited by 774
  2. 2019When to Trust Your Model: Model-Based Policy Optimizationcited by 773
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017A Tutorial on Thompson Samplingcited by 433
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  6. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  7. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  8. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 227
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  12. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
38 more
  1. 2017Deep Exploration via Randomized Value Functionscited by 156
  2. 2018A Tour of Reinforcement Learning: The View from Continuous Controlcited by 151
  3. 2016EPOpt: Learning Robust Neural Network Policies Using Model Ensemblescited by 138
  4. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  5. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  6. 2020Naive Exploration is Optimal for Online LQRcited by 116
  7. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  8. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  9. 2019Online Control with Adversarial Disturbancescited by 92
  10. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  11. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  12. 2020Improper Learning for Non-Stochastic Controlcited by 83
  13. 2019Learning Linear-Quadratic Regulators Efficiently with only √T Regretcited by 70
  14. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  15. 2018Online Linear Quadratic Controlcited by 56
  16. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  17. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 53
  18. 2019The Nonstochastic Control Problemcited by 52
  19. 2015Fast rates in statistical and online learningcited by 47
  20. 2020Black-Box Control for Linear Dynamical Systemscited by 43
  21. 2018Successor Uncertainties: Exploration and Uncertainty in Temporal Difference Learningcited by 35
  22. 2018On the optimality of the Hedge algorithm in the stochastic regimecited by 33
  23. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  24. 2023Foundations of Reinforcement Learning and Interactive Decision Makingcited by 33
  25. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
  26. 2020Online Sparse Reinforcement Learningcited by 25
  27. 2020Regret Bounds for Adaptive Nonlinear Controlcited by 25
  28. 2020Model-based Reinforcement Learning for Continuous Control with Posterior Samplingcited by 21
  29. 2020Online Optimal Control with Affine Constraintscited by 20
  30. 2020Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxationcited by 18
  31. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  32. 2017Thompson Sampling for Linear-Quadratic Control Problemscited by 14
  33. 2022Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbationscited by 14
  34. 2020A maximum-entropy approach to off-policy evaluation in average-reward MDPscited by 9
  35. 2023Online switching control with stability and regret guaranteescited by 9
  36. 2022Thompson Sampling Achieves tilde O(√T) Regret in Linear Quadratic Controlcited by 8
  37. 2024Stochastic Online Optimization for Cyber-Physical and Robotic Systemscited by 6
  38. 2022Posterior Sampling for Continuing Environmentscited by 4

50 most cited of 56 All 56 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 4.

6 papers.

  1. 2025High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systemscited by 1
  2. 2025Online Multi-Agent Control with Adversarial Disturbancescited by 0
  3. 2026Adapting Actively on the Fly: Relevance-Guided Online Meta-Learning with Latent Concepts for Geospatial Discoverycited by 0
  4. 2026Online Learning for Supervisory Switching Controlcited by 0
  5. 2026PhiBE-Q-Learning: Bridging Off-Policy Reinforcement Learning and Continuous-Time Controlcited by 0
  6. 2026Foundations of Reinforcement Learning and Control:Connections and New Perspectivescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  2. 2024Learning the Model While Learning Q: Finite-Time Sample Complexity of Online SyncMBQ
  3. 2022The Role of Coverage in Online Reinforcement Learning
  4. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  5. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  6. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  7. 2025Improving Reinforcement Learning Sample-Efficiency using Local Approximation
  8. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond