Reinforcement learning (RL) agents are notoriously brittle. An agent trained to achieve superhuman performance in one specific simulator often fails catastrophically when deployed in a slightly modified environment—even if the changes appear trivial to a human observer. This phenomenon, known as the "generalization gap," remains a central hurdle in deploying RL to real-world systems.
While researchers have proposed numerous empirical methods to improve generalization, the formal mathematical foundations of this problem remain underexplored. Specifically, what structural conditions make generalization mathematically tractable (i.e., solvable in polynomial time and queries)? This paper investigates the fundamental limits of generalization in RL, revealing a surprising "impossibility" result alongside a strict condition that finally enables efficient generalization.
The Theoretical Framework
To rigorously analyze generalization, the authors focus on query complexity—the number of interactions an agent requires with its environments to discover a robust policy. The study evaluates two popular settings:
- Average Performance: The objective is to maximize the expected reward across a distribution of different environments.
- Meta-RL: The agent learns from a set of training environments to quickly adapt to a new, unseen test environment.
To test the limits of tractability, the authors assume Strong Individual Optimization (SIO), meaning any single environment in the set is "easy" to solve on its own (for instance, it possesses an optimal linear policy). From this baseline, they introduce two key structural conditions to model how environments might be related:
- Weak Proximity: The environments have highly similar transition and reward functions, and they share a single policy that is optimal when starting from the initial state.
- Strong Proximity: A stricter condition where a single shared policy is near-optimal for every possible state across all environments, not just the starting state.
The Impossibility Result: The "Weak Proximity" Trap
A natural intuition—often formalized in classical approaches like the Simulation Lemma—is that if environments are "close" in their transition and reward dynamics, and if they share an optimal path from the start, generalization should be straightforward.
The authors prove this intuition mathematically false. Under Weak Proximity, even if environments are nearly identical, finding the generalizing policy can require an exponential number of queries. Because the agent does not know which specific path is the shared optimal one, it can be forced to explore an exponential number of trajectories.
The paper establishes a rigorous lower bound, proving that any algorithm requires $\Omega(\min\{|A|^H, 2^d\})$ queries to find a generalizing policy (where $|A|$ is the number of actions, $H$ is the horizon, and $d$ is the dimension). This exponential "curse of dimensionality" demonstrates that mere similarity is insufficient for modern RL generalization.
Furthermore, the authors show that this worst-case inefficiency applies even to representation learning. Even if a perfect shared state representation exists across the environments, learning it can still require exponential queries, challenging the common belief that finding the "right features" automatically solves the generalization problem.
The Path to Tractability: Strong Proximity
If Weak Proximity is a trap, what makes generalization tractable? The answer lies in global optimality.
Generalization becomes tractable only when the shared structure is robust enough to allow information from one environment to prune the search space in others. The authors prove that under Strong Proximity—where a single policy is optimal from any state—an agent can efficiently learn to generalize.
They introduce an iterative algorithm that builds a policy by averaging value estimates across sampled environments. The authors prove a Tractability Theorem: under Strong Proximity and deterministic transitions, this algorithm successfully finds a generalizing policy with a query complexity that is strictly polynomial in all relevant parameters ($|A|$, $H$, and $d$).
Limitations and Future Directions
While this paper provides a crucial theoretical foundation for RL generalization, it also highlights several open challenges:
- Deterministic Transitions: The positive tractability result (the upper bound) currently relies on environments having deterministic transitions. Extending this polynomial-time guarantee to stochastic environments remains a major open question.
- Verifiability: In practical applications, it is exceedingly difficult to verify whether a set of environments satisfies the strict "Strong Proximity" condition before training begins.
- Bridging Theory and Practice: Strong Proximity is a highly restrictive condition. Future research must explore "Medium Proximity" conditions—structural assumptions that are more representative of real-world environment variations but still allow for faster-than-exponential learning.
Ultimately, this research clarifies that empirical tricks alone cannot overcome the fundamental limits of RL generalization. By mapping the boundaries between the tractable and the impossible, it provides a vital roadmap for designing RL systems that can genuinely adapt to the unknown.
Summary updated