  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.
