Sample Complexity of Policy Search with Known Dynamics

Peter L. Bartlett, Ambuj TewariNeurIPS 2006 · OpenReview

In the realm of Reinforcement Learning (RL), Markov Decision Processes (MDPs) in the real world are often too complex to solve exactly. To make practical progress, researchers frequently rely on policy search. Instead of searching for a perfect strategy across all theoretical possibilities, we restrict our search to a specific class of strategies (such as neural networks with a defined architecture) and use a simulator to find the best performing policy within that class.

However, this approach raises a critical question: How many simulations are actually required to guarantee that a policy performing well in a simulator will also perform well in reality?

In their paper, "Sample complexity of policy search with known dynamics," Peter L. Bartlett and Ambuj Tewari explore the theoretical foundations of this problem. They reveal that standard tools from machine learning theory may be insufficient for RL, and they propose new bounds based on computational complexity.

The Problem: Why Standard Complexity Measures Fail in RL

In standard supervised learning, we know that if a model class is not overly "complex"—often measured using tools like the Vapnik-Chervonenkis (VC) dimension or pseudodimension—we do not need infinite data to learn effectively.

RL, however, is fundamentally different. Instead of making isolated predictions, RL involves a sequence of decisions. Each decision alters the state, which in turn affects the subsequent decision. This iterative composition means that even if a single policy appears "simple" in isolation, the result of executing that policy for 100 steps in a simulator can yield incredibly complex behavior. The authors sought to identify the true conditions that ensure "uniform convergence"—the guarantee that empirical estimates of a policy's value will closely match its true value across the entire policy class.

Methodology: A Shift to Computational Limits

To address the shortcomings of purely geometric complexity measures, the authors pivot toward computational limits:

  1. The BSS Model: They employ a variant of the Blum-Shub-Smale (BSS) model of computation. This assumes that the policy, state transitions, and rewards can all be calculated using a finite sequence of basic arithmetic operations ($+, -, \times, /$) and logical branches.
  2. Counting Operations: By tallying these operations, the authors can bound the "pseudodimension" of the entire multi-step reward process, rather than just the single-step policy.
  3. Minimax Lower Bounds: To demonstrate the inadequacy of standard measures, they construct mathematical counter-examples—pathological policy classes with low combinatorial complexity that still fail to converge in simulation.

Key Insights: Composition and The Lipschitz Trap

The most significant insight of the paper is that RL is inherently harder than supervised learning due to function composition. Applying a simple function to itself repeatedly can generate a fractal-like complexity that standard learning theory fails to capture.

Furthermore, the paper highlights the Lipschitz Trap. Previous research often relied on "Lipschitz continuity" (the principle that small changes in input yield small changes in output). Bartlett and Tewari demonstrate that even if a function is Lipschitz almost everywhere, a single "spiky" or discontinuous point can derail the entire learning process when iterated over multiple steps.

Pathological function example illustrating how a seemingly simple policy can exhibit complex, non-converging behavior when iterated.

As seen in the mathematical counter-examples constructed by the authors, functions can be designed to have a small "fat-shattering dimension" while still making it impossible for any amount of simulation to reliably identify the optimal policy.

Main Results

The authors formalize their findings into concrete upper and lower bounds:

  • The Upper Bound (Theorem 1): The paper provides a concrete formula for sample complexity based on computation. The number of required samples $n$ scales linearly with the number of parameters $d$ and the computation time $\tau$. Crucially, this bound is independent of the dimension of the state space, offering a pathway to tractability in high-dimensional environments.
  • The Lower Bound (Theorems 2 & 3): Using their pathological examples, they prove that for certain "simple" policy classes (e.g., with a pseudodimension of 1), the expected regret remains high regardless of the sample size. This establishes that bounded combinatorial dimension is a necessary but insufficient condition for successful RL policy search.

Limitations and Future Directions

While theoretically robust, the paper operates under specific assumptions:

  • Known Dynamics: The research assumes access to a perfect simulator. In many real-world scenarios, dynamics must be learned concurrently with the policy.
  • Theoretical Abstraction: The BSS computational model is an abstraction. Real-world hardware relies on floating-point arithmetic, introducing precision issues that could impact these theoretical bounds.

The authors suggest future work should explore whether these computational bounds can be relaxed, or if specific "structural" properties of certain MDPs make them inherently easier to learn than the worst-case scenarios presented.

Conclusion

This research serves as a vital reminder for RL practitioners: a "simple" neural network architecture does not guarantee efficient policy search. The computational complexity of the environment's dynamics and the length of the planning horizon are just as critical to learning success as the number of weights in the model.

Summary updated

Abstract

We consider methods that try to find a good policy for a Markov decision process by choosing one from a given class. The policy is chosen based on its empirical performance in simulations. We are interested in conditions on the complexity of the policy class that ensure the success of such simulation based policy search methods. We show that under bounds on the amount of computation involved in computing policies, transition dynamics and rewards, uniform convergence of empirical estimates to true value functions occurs. Previously, such results were derived by assuming boundedness of pseudodimension and Lipschitz continuity. These assumptions and ours are both stronger than the usual combinatorial complexity measures. We show, via minimax inequalities, that this is essential: boundedness of pseudodimension or fat-shattering dimension alone is not sufficient.
BibTeX
@inproceedings{bartlett2006sample,
  author = {Peter L. Bartlett and Ambuj Tewari},
  title = {{Sample Complexity of Policy Search with Known Dynamics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=ryZylYb_ZH},
}
Figure