When Is Generalizable Reinforcement Learning Tractable?

Dhruv Malik, Yuanzhi Li, Pradeep Ravikumar

Introduction

Reinforcement Learning (RL) agents are notoriously brittle. An agent trained to excel in a specific simulator often fails catastrophically when introduced to a slightly modified environment—such as one with altered friction, lighting, or reward scales. While the intuition suggests that "similar" environments should be easy to generalize across, the RL community has historically lacked a formal, mathematical definition of what "similarity" implies for computational tractability.

This paper investigates the fundamental limits of generalization in RL, seeking to identify the structural conditions on a distribution of environments that allow an agent to learn a generalizable policy with a polynomial number of queries. The authors focus on two primary settings: Average Performance (performing well across a task distribution) and Meta-RL (adapting rapidly to unseen test tasks).

The Limits of Similarity: Weak Proximity

To analyze the problem, the authors define two key structural conditions. The first, Weak Proximity, describes a scenario where environments have highly similar transition and reward functions and share at least one path from the initial state that is optimal for all tasks in the distribution.

Conventionally, RL theory relies on the "Simulation Lemma," which posits that if two Markov Decision Processes (MDPs) have similar transitions and rewards, they are functionally "close." However, this research proves that the Simulation Lemma is insufficient for generalization. Even under Weak Proximity, finding a shared solution can be an exponential "needle in a haystack" problem.

The Exponential Lower Bound

Using a hard-instance construction involving a complex $|A|$-ary tree MDP, the authors prove a "no-free-lunch" result. They show that even if an agent has access to a Strong Individual Optimization (SIO) oracle—meaning it can solve any single task perfectly—finding a policy that generalizes across multiple tasks requires an exponential number of queries:

$$\Omega(\min\{|A|^H, 2^d\})$$

where $|A|$ is the number of actions, $H$ is the horizon, and $d$ is the feature dimension. This result holds even if the agent has a generative model and the tasks are linear, implying that representation learning alone cannot bypass this fundamental complexity.

Achieving Tractability: Strong Proximity

The research identifies a critical pivot point for tractability: the transition from initial-state optimality to all-state optimality. This leads to the definition of Strong Proximity, a stricter condition where a single policy is near-optimal for every environment starting from any state in the state space, not just the initial one.

Under Strong Proximity, the problem of generalization becomes computationally tractable. The authors introduce Algorithm 1 (GenRL), which utilizes a value-estimation oracle to greedily construct a generalizable policy level-by-level. For deterministic environments, GenRL can find a near-optimal generalizable policy with a query cost that scales polynomially with the number of actions, the horizon, and the state dimension.

Key Insights and Implications

  1. The Generalization Gap: There is a massive complexity gap between knowing tasks share a solution from the start (Weak Proximity) versus sharing a solution from everywhere (Strong Proximity). Tractability is only guaranteed in the latter.
  2. Representation Learning Constraints: The lower bounds suggest that even if a perfect shared state representation exists, the process of identifying it remains worst-case sample inefficient without strong structural alignment across the entire state space.
  3. Theoretical Foundations for Meta-RL: This work provides a rigorous framework for understanding why Meta-RL often requires significant amounts of data to find transferable features or policies.

Limitations and Future Directions

While this paper establishes a foundational understanding of RL generalization, several avenues for future research remain:

  • Stochasticity: The current polynomial upper bound for GenRL applies specifically to deterministic transitions. Extending these guarantees to stochastic environments is a significant open challenge.
  • Intermediate Conditions: The gap between Weak and Strong Proximity is vast. Future work may identify intermediate conditions that are more realistic than Strong Proximity but still avoid the exponential complexity of Weak Proximity.
  • Practical Implementation: As a theoretical study, the paper focuses on query complexity and existence proofs. Translating these insights into practical deep RL architectures for learning shared features remains a vital next step.

Summary updated

BibTeX
@inproceedings{malik2021when,
  author = {Dhruv Malik and Yuanzhi Li and Pradeep Ravikumar},
  title = {{When Is Generalizable Reinforcement Learning Tractable?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=lHvy0DLYWm},
}
Figure