mlsanityData to 7 Oct 2026

When Is Generalizable Reinforcement Learning Tractable?

arXiv 2101.00300 ↗First posted 1 Jan 2021cs.LG cs.AI stat.MLcited by 19

Not on the map. Why?

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.

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

Builds on

31 of 61 references.

References · 31

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2019Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learningcited by 1,168
  3. 2017Deep Reinforcement Learning that Matterscited by 727
  4. 2019Leveraging Procedural Generation to Benchmark Reinforcement Learningcited by 478
  5. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 424
  6. 2019Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variablescited by 372
  7. 2018Quantifying Generalization in Reinforcement Learningcited by 345
  8. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
  9. 2018Learning to Adapt in Dynamic, Real-World Environments Through Meta-Reinforcement Learningcited by 270
  10. 2015Actor-Mimic: Deep Multitask and Transfer Reinforcement Learningcited by 176
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2019Scalable methods for computing state similarity in deterministic Markov Decision Processescited by 133
19 more
  1. 2018Assessing Generalization in Deep Reinforcement Learningcited by 132
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  3. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  4. 2018Generalization and Regularization in DQNcited by 117
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  6. 2019Observational Overfitting in Reinforcement Learningcited by 90
  7. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  8. 2018A Dissection of Overfitting and Generalization in Continuous Reinforcement Learningcited by 86
  9. 2018Composable Deep Reinforcement Learning for Robotic Manipulationcited by 70
  10. 2017Towards Generalization and Simplicity in Continuous Controlcited by 65
  11. 2018Gotta Learn Fast: A New Benchmark for Generalization in RLcited by 59
  12. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  13. 2020Invariant Policy Optimization: Towards Stronger Generalization in Reinforcement Learningcited by 37
  14. 2019Guided Meta-Policy Searchcited by 26
  15. 2019On the Generalization Gap in Reparameterizable Reinforcement Learningcited by 21
  16. 2020On the Global Optimality of Model-Agnostic Meta-Learningcited by 21
  17. 2020Instance based Generalization in Reinforcement Learningcited by 17
  18. 2019Comments on the Du-Kakade-Wang-Yang Lower Boundscited by 16
  19. 2019How Does an Approximate Model Help in Reinforcement Learning?cited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 5; 2023: 1; 2024: 3; 2025: 3; 2026: 3.

19 papers.

Sort:

By area:

  1. 2021A Survey of Zero-shot Generalisation in Deep Reinforcement Learningcited by 164
  2. 2022Contextualize Me -- The Case for Context in Reinforcement Learningcited by 41
  3. 2023On the Importance of Exploration for Generalization in Reinforcement Learningcited by 30
  4. 2022Generalization in Cooperative Multi-Agent Systemscited by 18
  5. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  6. 2024A Survey Analyzing Generalization in Deep Reinforcement Learningcited by 8
  7. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  8. 2021Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycited by 6
  9. 2022Meta Learning MDPs with Linear Transition Modelscited by 4
  10. 2022Deep Reinforcement Learning for Multi-Agent Interactioncited by 3
  11. 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
  12. 2021Towards robust and domain agnostic reinforcement learning competitionscited by 2
7 more
  1. 2021Active Reinforcement Learning over MDPscited by 0
  2. 2024A Research Agenda for Usability and Generalisation in Reinforcement Learningcited by 0
  3. 2025Inductive Biases for Zero-shot Systematic Generalization in Language-informed Reinforcement Learningcited by 0
  4. 2025Zero-Shot Context Generalization in Reinforcement Learning from Few Training Contextscited by 0
  5. 2026Certificate-Guided Evaluation of Reinforcement Learning Generalizationcited by 0
  6. 2026A Model-Driven Approach for Developing Families of Reinforcement Learning Environmentscited by 0
  7. 2026Formalizing Task-Space Complexity for Zero-Shot Generalizationcited by 0