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

arXiv: https://arxiv.org/abs/2501.15910 · HTML: https://mlsanity.com/paper/2501.15910/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 56)

- [Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models](https://mlsanity.com/paper/1805.12114/) (2018)
- [When to Trust Your Model: Model-Based Policy Optimization](https://mlsanity.com/paper/1906.08253/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [A Tour of Reinforcement Learning: The View from Continuous Control](https://mlsanity.com/paper/1806.09460/) (2018)
- [EPOpt: Learning Robust Neural Network Policies Using Model Ensembles](https://mlsanity.com/paper/1610.01283/) (2016)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019)

## Built on by (most cited first, 6 of 6)

- [High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems](https://mlsanity.com/paper/2509.11907/) (2025)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)
- [Adapting Actively on the Fly: Relevance-Guided Online Meta-Learning with Latent Concepts for Geospatial Discovery](https://mlsanity.com/paper/2602.17605/) (2026)
- [Online Learning for Supervisory Switching Control](https://mlsanity.com/paper/2603.14762/) (2026)
- [PhiBE-Q-Learning: Bridging Off-Policy Reinforcement Learning and Continuous-Time Control](https://mlsanity.com/paper/2606.21925/) (2026)
- [Foundations of Reinforcement Learning and Control:Connections and New Perspectives](https://mlsanity.com/paper/2608.02433/) (2026)

## 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.