When Is Generalizable Reinforcement Learning Tractable?
This work addresses the fundamental challenge of generalization in RL for researchers and practitioners, providing theoretical bounds on its tractability.
This paper investigates the query complexity of generalizable reinforcement learning (RL), demonstrating that even with shared structure (Weak Proximity) among environments, tractable generalization is impossible in the worst case. However, they introduce Strong Proximity, a more stringent condition, and prove its sufficiency for efficient generalization.
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.