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

This paper analyzes the sample complexity of online reinforcement learning for general nonlinear dynamical systems with continuous state and action spaces, proposing algorithms that achieve specific policy regret bounds ranging from $\mathcal{O}(N \epsilon^2 + d_\mathrm{u}\ln(m(\epsilon))/\epsilon^2)$ in the general case to $\mathcal{O}(\sqrt{d_\mathrm{u}N p})$ for parameterized models, while emphasizing the practical utility of these simple, prior-knowledge-incorporating methods.

The Gist

Imagine you are the captain of a ship navigating through a thick, uncharted fog. You have a destination (optimizing performance), but you don't know the map (the dynamics of the ocean). You can only steer by turning the wheel (taking actions) and seeing how the ship reacts.

This paper is about how to learn the map quickly and safely while steering, without crashing the ship or getting lost for too long. The authors, Michael Muehlebach, Zhiyu He, and Michael I. Jordan, propose a new way to teach computers (specifically Reinforcement Learning algorithms) how to do this in complex, real-world situations where the rules aren't simple straight lines.

Here is the breakdown of their idea using everyday analogies:

1. The Core Problem: The "Exploration vs. Exploitation" Dilemma

In Reinforcement Learning, you face a classic catch-22:

• Exploitation: You steer the ship the way you think is best right now to get to the destination fast.
• Exploration: You steer the ship in a weird, random direction just to see what happens, hoping to learn something new about the ocean.

If you only exploit, you might get stuck in a bad spot because you never learned the whole map. If you only explore, you'll circle the ocean forever and never arrive. Most existing methods struggle to balance this, especially when the "ocean" is complex and non-linear (like a stormy sea rather than a calm lake).

2. The Solution: The "Gambler's Menu" Approach

The authors propose a clever strategy that combines guessing with learning. Imagine you have a menu of 100 different maps (models) of the ocean. You don't know which one is the real map, but you know the real map is somewhere in that list.

Their algorithm works like this:

1. The Menu: You have a list of candidate maps (models).
2. The Scorecard: Every time you steer the ship, you check: "Which map predicted this movement correctly?"
   • If Map A predicted the turn perfectly, its score goes up.
   • If Map B predicted the ship would go left but it went right, its score goes down.
3. The Gamble (Posterior Sampling): Instead of just picking the single "best" map and sticking with it, the algorithm randomly picks a map from the menu.
   • Maps with high scores (good predictions) have a higher chance of being picked.
   • Maps with low scores have a tiny chance, but they aren't completely eliminated yet.
4. The "Nudge" (Excitation): Here is the secret sauce. Even when you are following a map, you add a tiny, random "nudge" to the steering wheel. This is like shaking the ship slightly to make sure the water reacts. This ensures that if your current map is wrong, the ship will react in a way that exposes the error, allowing you to learn faster.

3. The Three Scenarios

The paper tests this idea in three different levels of complexity:

• Scenario A: The Finite Menu (Discrete Models)
  • Analogy: You have a physical stack of 50 printed maps.
  • Result: The algorithm quickly realizes which 1 or 2 maps are the best and stops wasting time on the bad ones. It learns very fast.
• Scenario B: The Infinite Library (Continuous Models)
  • Analogy: You don't have a stack of maps; you have a library with infinite variations of maps (every possible curve and angle).
  • Result: The algorithm creates a "net" (a mathematical concept called a packing number) to catch the best map. It proves that even with infinite possibilities, you can still find the right path efficiently.
• Scenario C: The Neural Network (Parametric Models)
  • Analogy: The map isn't a picture; it's a recipe with thousands of ingredients (parameters). You can tweak the amount of salt, sugar, or spice to change the map.
  • Result: This is the most practical scenario (like modern AI). The paper shows that even with thousands of "ingredients" to tune, the algorithm can find the perfect recipe and steer the ship safely.

4. Why This is a Big Deal

Previous methods had two main problems:

1. They were too theoretical: They worked well in simple, linear worlds (like a straight road) but broke down in complex, non-linear worlds (like a winding mountain road).
2. They were "Bayesian": They relied on "belief" and probability in a way that was hard to guarantee in the real world.

This paper's breakthrough:

• It works in the real world: It handles complex, non-linear systems (like a drone flying in a storm or a robot arm moving heavy objects).
• It provides a "Frequentist" guarantee: Instead of saying "We think we are good," it says "We guarantee that after $N$ steps, we will be this close to the optimal path." It's a mathematical promise of performance.
• It's simple: The math behind it is surprisingly straightforward (using a "Hedge" update, which is like a smart way of betting), making it easier to implement in real engineering.

5. The "Benign Transient" Promise

In control theory, a "transient" is the messy, chaotic period at the beginning of a journey before things settle down.

• Old methods: Might crash the ship or spin out of control while learning.
• This paper: Guarantees that even while learning, the ship stays stable. The "nudge" is controlled, and the ship won't go off a cliff while trying to learn the map.

Summary

Think of this paper as a new navigation system for self-driving cars or robots. It says: "Don't just guess the map. Keep a list of possible maps, bet on the ones that look right, but occasionally wiggle the steering wheel to test your theories. This way, you will learn the true map faster than anyone else, and you won't crash while doing it."

The authors prove mathematically that this approach works for everything from simple linear systems to complex neural networks, offering a reliable path forward for AI in the real, messy world.

Technical Summary

1. Problem Formulation

The paper addresses the sample complexity of online reinforcement learning (RL) in a non-episodic setting involving nonlinear dynamical systems with continuous state ($x \in \mathbb{R}^{d_x}$) and action ($u \in \mathbb{R}^{d_u}$) spaces.

• System Dynamics: The system evolves as $x_{k+1} = f(x_k, u_k) + n_k$, where $f$ is an unknown nonlinear function and $n_k$ is process noise (Gaussian or sub-Gaussian).
• Objective: The decision-maker aims to minimize the expected cumulative stage cost $\mathbb{E}[\sum_{k=1}^N l(x_k, u_k)]$ by learning a feedback policy $u_k = \mu_k(x_k)$.
• Key Challenges:
  • Non-episodic: The system cannot be reset; states are correlated over time, preventing the direct application of standard i.i.d. statistical tools.
  • Exploration-Exploitation Dilemma: Actions must simultaneously optimize performance and reveal information about the unknown dynamics.
  • Nonlinearity & Continuity: The dynamics are general nonlinear functions, and the spaces are continuous, making traditional tabular or linear methods insufficient.
  • Stability: Ensuring bounded state trajectories and benign transients during the learning phase.

The paper considers three specific settings for the candidate model class $\mathcal{F}$:

1. S1 (Finite Models): A finite set of $m$ nonlinear candidate models.
2. S2 (Infinite/Non-parametric): A bounded set of functions in a normed vector space (e.g., bounded Lipschitz functions).
3. S3 (Parametric): Models parameterized by a compact real-valued vector $\theta \in \Omega \subset \mathbb{R}^p$ (e.g., neural networks, transformers, or linear systems).

2. Methodology

The authors propose a suite of algorithms based on Posterior Sampling Reinforcement Learning (PSRL) combined with Hedge-type updates and Certainty-Equivalent Control.

Core Algorithmic Strategy

The algorithm operates in discrete time steps, updating the model selection every $M$ steps to ensure sufficient excitation:

1. Model Scoring: At each update step, the algorithm computes a prediction error score $s_k^i$ for each candidate model $f^i$:
   $$s_k^i = \sum_{j=1}^{k-1} \frac{|x_{j+1} - f^i(x_j, u_j)|^2}{1 + |(x_j, u_j)|^2/b^2}$$
   This score acts as a negative log-likelihood (assuming Gaussian noise). The normalization term ensures boundedness even for large states.
2. Posterior Sampling (Hedge Update): The algorithm samples an index $i_k$ (or parameter $\theta_k$) from a distribution proportional to $\exp(-\eta s_k^i)$, where $\eta$ is a learning rate. This is analogous to the Hedge algorithm in online learning but adapted for dependent dynamical systems.
3. Certainty-Equivalent Control: Once a model is sampled, a control policy $\mu_{i_k}$ is computed for that specific model (e.g., via Dynamic Programming, MPC, or PPO).
4. Excitation: The actual control input is $u_k = \mu_{i_k}(x_k) + n_{u_k}$, where $n_{u_k}$ is additive Gaussian noise. This persistence of excitation is crucial to ensure the posterior distribution converges rapidly to the true model.

Theoretical Framework

• Separation Principle: The approach decouples model identification (via posterior sampling) from control synthesis (certainty-equivalent policy).
• Lyapunov Analysis: The authors use a cost-to-go function $V(x)$ as a Lyapunov function to prove stability and boundedness of state trajectories.
• Assumptions:
  • Realizability: The true dynamics $f$ are contained within the candidate set $\mathcal{F}$ (relaxed in Appendix G).
  • Persistence of Excitation (PE): A condition ensuring that the system trajectory provides enough information to distinguish between models.
  • Smoothness/Dissipation: Lipschitz continuity of dynamics and policies, and a Bellman-type inequality characterizing system dissipation.

3. Key Contributions

1. Non-Asymptotic Frequentist Regret Guarantees: Unlike previous PSRL works that often provide Bayesian regret bounds or rely on mixing assumptions, this paper provides frequentist policy regret bounds that hold for any specific environment realization, applicable even near stability boundaries.
2. Multi-Model Perspective for Nonlinear Systems: The work generalizes sample complexity analysis from linear systems to broad classes of nonlinear systems, including those with infinite model classes and parametric neural networks.
3. Novel Regret Bounds:
   • Finite Models (S1): Regret scales as $O(\frac{d_u \ln(N) + d_u \ln(m)}{\Delta})$, where $\Delta$ is the model separation.
   • Non-parametric (S2): Regret scales as $O(N\epsilon^2 + \frac{d_u \ln(N) + d_u \ln(m(\epsilon))}{\epsilon^2})$, where $m(\epsilon)$ is the packing number.
   • Parametric (S3): Regret scales as $O(\sqrt{d_u N p})$, where $p$ is the number of parameters. This recovers known results for Linear Quadratic Regulators (LQR) while extending to nonlinear parametric models.
4. Stability and Boundedness: The paper proves that state trajectories remain bounded (sub-Gaussian) and converge in finite time almost surely, addressing a primary concern in adaptive control.
5. Practicality: The algorithms avoid the computation of optimistic policies or complex confidence regions (unlike "Optimism in the Face of Uncertainty" methods), making them easier to implement and integrate with existing control techniques like MPC.

4. Key Results

• Theorem 2.1 (S1): For a finite set of models, the policy regret is bounded by terms logarithmic in the horizon $N$ and the number of models $m$.
• Theorem 2.2 (S2): For infinite function classes, the regret depends on the packing number $m(\epsilon)$. For bounded Lipschitz functions, the regret is sublinear ($o(N)$).
• Theorem 2.3 (S3): For parametric models (e.g., neural networks), the regret is $O(\sqrt{d_u N p})$. This matches the optimal rate for linear systems but applies to general parametric nonlinear dynamics.
• Numerical Experiments:
  • Linear Systems: Demonstrated rapid convergence to near-optimal steady-state performance (within ~20 steps) even with 10,000 candidate models.
  • Nonlinear Pendulum: Successfully controlled a swing-up task for a cart-pole system where the true dynamics were not in the candidate set (misspecification), converging to a stable balance in ~100 steps.
  • Scalability: The algorithms ran efficiently on a standard laptop, with the bottleneck being policy evaluation (MPC) rather than model sampling.

5. Significance

This paper bridges the gap between statistical learning theory, online optimization, and control theory.

• Theoretical Impact: It establishes that posterior sampling, when combined with explicit excitation and Lyapunov analysis, yields strong frequentist guarantees for continuous, nonlinear, non-episodic systems. It moves beyond the restrictive assumptions of linear dynamics or episodic resets common in prior RL literature.
• Practical Impact: The proposed algorithms are computationally tractable and simple to implement. By separating identification and control, they allow practitioners to use powerful simulators or MPC for policy evaluation while relying on simple statistical updates for model selection.
• Future Directions: The work opens avenues for handling partial observability, non-additive noise, and developing hierarchical coverage strategies for complex function classes.

In summary, the paper provides a rigorous, unified framework for online RL in complex dynamical systems, offering provable performance guarantees that scale favorably with dimension and model complexity, while ensuring system stability.