Toward the Fundamental Limits of Imitation Learning
Toward the Fundamental Limits of Imitation Learning
复制标题
DOI：
--
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Nived Rajaraman;Lin F. Yang;Jiantao Jiao;K. Ramachandran
中科院分区：
文献类型：
--
作者：
Nived Rajaraman;Lin F. Yang;Jiantao Jiao;K. Ramachandran
模仿学习（IL）的目的是模仿专家政策在顺序决策问题中的行为，只给出示范。在本文中，我们着重于理解情景马尔可夫决策过程（mdp）中IL的极大极小统计极限。我们首先考虑的设置是，学习者提前提供了$N$专家轨迹的数据集，并且不能与MDP交互。在这里，我们表明，与专家的值相比，尽可能模仿专家的策略的期望是$\lesssim \frac{|\mathcal{S}| H^2 \log (N)}{N}$次优的，即使专家遵循任意的随机策略。这里$\mathcal{S}$是状态空间，$H$是剧集的长度。此外，我们建立了$\gtrsim |\mathcal{S}| H^2 / N$的次优性下界，即使专家被约束为确定性，或者如果学习者被允许在访问状态下主动查询专家，同时与MDP交互$N$集。据我们所知，这是第一个在没有额外假设的情况下，不依赖于动作数量的次优性算法。然后，我们提出了一种基于最小距离函数的新算法，在给定转移模型和专家是确定性的情况下。该算法的次优值为$\lesssim \min \{ H \sqrt{|\mathcal{S}| / N} ,\ |\mathcal{S}| H^{3/2} / N \}$，表明对过渡的了解将极大极小率提高了至少$\sqrt{H}$个因子。
Imitation learning (IL) aims to mimic the behavior of an expert policy in a sequential decision-making problem given only demonstrations. In this paper, we focus on understanding the minimax statistical limits of IL in episodic Markov Decision Processes (MDPs). We first consider the setting where the learner is provided a dataset of $N$ expert trajectories ahead of time, and cannot interact with the MDP. Here, we show that the policy which mimics the expert whenever possible is in expectation $\lesssim \frac{|\mathcal{S}| H^2 \log (N)}{N}$ suboptimal compared to the value of the expert, even when the expert follows an arbitrary stochastic policy. Here $\mathcal{S}$ is the state space, and $H$ is the length of the episode. Furthermore, we establish a suboptimality lower bound of $\gtrsim |\mathcal{S}| H^2 / N$ which applies even if the expert is constrained to be deterministic, or if the learner is allowed to actively query the expert at visited states while interacting with the MDP for $N$ episodes. To our knowledge, this is the first algorithm with suboptimality having no dependence on the number of actions, under no additional assumptions. We then propose a novel algorithm based on minimum-distance functionals in the setting where the transition model is given and the expert is deterministic. The algorithm is suboptimal by $\lesssim \min \{ H \sqrt{|\mathcal{S}| / N} ,\ |\mathcal{S}| H^{3/2} / N \}$, showing that knowledge of transition improves the minimax rate by at least a $\sqrt{H}$ factor.