When Is Generalizable Reinforcement Learning Tractable?
arXiv:2101.00300
Abstract
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.
arXiv commentNeurips 2021, v3 fixes minor typos
References in corpus (16)
- Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
- Deep Reinforcement Learning that Matters
- Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning
- Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables
- Assessing Generalization in Deep Reinforcement Learning
- Generalization and Regularization in DQN
- A Dissection of Overfitting and Generalization in Continuous Reinforcement Learning
- Gotta Learn Fast: A New Benchmark for Generalization in RL
- Sample Complexity of Multi-task Reinforcement Learning
- On the Sample Complexity of Reinforcement Learning with a Generative Model
- On Reward-Free Reinforcement Learning with Linear Function Approximation
- Comments on the Du-Kakade-Wang-Yang Lower Bounds
- On the Generalization Gap in Reparameterizable Reinforcement Learning
- Invariant Policy Optimization: Towards Stronger Generalization in Reinforcement Learning
- On the Global Optimality of Model-Agnostic Meta-Learning
- On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function