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.
翻译:通过强化学习(RL)培训的代理人员往往无法超越他们所培训的环境,即使他们展示了与培训环境相似的新情景,也往往无法超越他们所培训的环境,我们研究培训RL代理人员向多个环境推广所需的询问复杂性。直观地说,只有在环境相似或某种意义上接近时,才有可能进行可移植的概括化。我们为此引入了弱相近性这一自然结构条件,要求环境具有非常相似的过渡和奖励功能,并共享提供最佳价值的政策。尽管存在这种共同结构,但我们证明,在最坏的情况下,不可能实现可移植的普及。即使每个环境都能够有效解决,以获得最佳的线性政策,而且当代理人员拥有一种基因模型时,这也存在这种复杂性。我们较低的约束适用于更复杂的代表性学习任务,以便有效地向多个环境普及。在积极的一面,我们引入了强相近的优越性,一个我们证明足以有效普及的强化条件。