# When Is Generalizable Reinforcement Learning Tractable?

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 61 references that are in the map.
- First posted on arXiv 1 Jan 2021.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning](https://mlsanity.com/paper/1910.10897/) (2019)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables](https://mlsanity.com/paper/1903.08254/) (2019)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [Quantifying Generalization in Reinforcement Learning](https://mlsanity.com/paper/1812.02341/) (2018)
- [Learning to Adapt in Dynamic, Real-World Environments Through Meta-Reinforcement Learning](https://mlsanity.com/paper/1803.11347/) (2018)
- [Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning](https://mlsanity.com/paper/1511.06342/) (2015)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Assessing Generalization in Deep Reinforcement Learning](https://mlsanity.com/paper/1810.12282/) (2018)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Generalization and Regularization in DQN](https://mlsanity.com/paper/1810.00123/) (2018)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Observational Overfitting in Reinforcement Learning](https://mlsanity.com/paper/1912.02975/) (2019)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [A Dissection of Overfitting and Generalization in Continuous Reinforcement Learning](https://mlsanity.com/paper/1806.07937/) (2018)
- [Composable Deep Reinforcement Learning for Robotic Manipulation](https://mlsanity.com/paper/1803.06773/) (2018)
- [Towards Generalization and Simplicity in Continuous Control](https://mlsanity.com/paper/1703.02660/) (2017)
- [Gotta Learn Fast: A New Benchmark for Generalization in RL](https://mlsanity.com/paper/1804.03720/) (2018)
- [Sample Complexity of Multi-task Reinforcement Learning](https://mlsanity.com/paper/1309.6821/) (2013)
- [Invariant Policy Optimization: Towards Stronger Generalization in Reinforcement Learning](https://mlsanity.com/paper/2006.01096/) (2020)
- [Guided Meta-Policy Search](https://mlsanity.com/paper/1904.00956/) (2019)
- [On the Generalization Gap in Reparameterizable Reinforcement Learning](https://mlsanity.com/paper/1905.12654/) (2019)
- [On the Global Optimality of Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2006.13182/) (2020)
- [Comments on the Du-Kakade-Wang-Yang Lower Bounds](https://mlsanity.com/paper/1911.07910/) (2019)
- [Instance based Generalization in Reinforcement Learning](https://mlsanity.com/paper/2011.01089/) (2020)

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

- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [Contextualize Me -- The Case for Context in Reinforcement Learning](https://mlsanity.com/paper/2202.04500/) (2022)
- [On the Importance of Exploration for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2306.05483/) (2023)
- [Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RL](https://mlsanity.com/paper/2410.20254/) (2024)
- [Generalization in Cooperative Multi-Agent Systems](https://mlsanity.com/paper/2202.00104/) (2022)
- [A Survey Analyzing Generalization in Deep Reinforcement Learning](https://mlsanity.com/paper/2401.02349/) (2024)
- [On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardness](https://mlsanity.com/paper/2210.10464/) (2022)
- [Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity](https://mlsanity.com/paper/2106.07814/) (2021)
- [Meta Learning MDPs with Linear Transition Models](https://mlsanity.com/paper/2201.08732/) (2022)
- [Deep Reinforcement Learning for Multi-Agent Interaction](https://mlsanity.com/paper/2208.01769/) (2022)
- [Provable Zero-Shot Generalization in Offline Reinforcement Learning](https://mlsanity.com/paper/2503.07988/) (2025)
- [Towards robust and domain agnostic reinforcement learning competitions](https://mlsanity.com/paper/2106.03748/) (2021)
- [Satellite Chasers: Divergent Adversarial Reinforcement Learning to Engage Intelligent Adversaries on Orbit](https://mlsanity.com/paper/2409.17443/) (2024)
- [Inductive Biases for Zero-shot Systematic Generalization in Language-informed Reinforcement Learning](https://mlsanity.com/paper/2501.15270/) (2025)
- [Active Reinforcement Learning over MDPs](https://mlsanity.com/paper/2108.02323/) (2021)
- [A Research Agenda for Usability and Generalisation in Reinforcement Learning](https://mlsanity.com/paper/2412.16970/) (2024)
- [Zero-Shot Context Generalization in Reinforcement Learning from Few Training Contexts](https://mlsanity.com/paper/2507.07348/) (2025)
- [Certificate-Guided Evaluation of Reinforcement Learning Generalization](https://mlsanity.com/paper/2606.00840/) (2026)
- [A Model-Driven Approach for Developing Families of Reinforcement Learning Environments](https://mlsanity.com/paper/2606.20324/) (2026)
- [Formalizing Task-Space Complexity for Zero-Shot Generalization](https://mlsanity.com/paper/2606.20967/) (2026)

## Abstract (arXiv)

Agents trained by reinforcement learning (RL) often fail to generalize beyond the environment they were trained in, even when presented with new scenarios that seem similar to the training environment. We study the query complexity required to train RL agents that generalize to multiple environments. Intuitively, tractable generalization is only possible when the environments are similar or close in some sense. To capture this, we introduce Weak Proximity, a natural structural condition that requires the environments to have highly similar transition and reward functions and share a policy providing optimal value. Despite such shared structure, we prove that tractable generalization is impossible in the worst case. This holds even when each individual environment can be efficiently solved to obtain an optimal linear policy, and when the agent possesses a generative model. Our lower bound applies to the more complex task of representation learning for the purpose of efficient generalization to multiple environments. On the positive side, we introduce Strong Proximity, a strengthened condition which we prove is sufficient for efficient generalization.