On the Value of Interaction and Function Approximation in Imitation Learning
On the Value of Interaction and Function Approximation in Imitation Learning
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Nived Rajaraman;Yanjun Han;L. Yang;Jingbo Liu;Jiantao Jiao;K. Ramchandran
中科院分区：
文献类型：
--
作者：
Nived Rajaraman;Yanjun Han;L. Yang;Jingbo Liu;Jiantao Jiao;K. Ramchandran
我们研究情景 MDP 中模仿学习 (IL) 问题的统计保证。拉贾拉曼等人。 [22] 显示了一个信息论下界，在最坏的情况下，甚至可以主动查询专家策略的学习器也会遭受在时间范围 H 的长度上呈二次方增长的次优性。我们在[27]的μ可恢复性假设下研究模仿学习，该假设假设在一个状态下不同行动的专家策略下Q值的差异不会偏离最大值超过μ。我们证明[25]提出的减少在统计上是最佳的：与 N 个情节的 MDP 交互时产生的算法导致 (cid:101) O ( µ |S| H/N ) 的次优界限，我们证明它在对数因子下是最优的。相比之下，我们表明任何不与 MDP 交互并使用 N 个专家轨迹的离线数据集的算法都必须导致次优性增长为 (cid:38) |S|即使在μ-可恢复性假设下，H 2 /N 也是如此。这在活动设置和无交互设置之间建立了最小最大速率的清晰且可证明的分离。我们还用线性函数近似来研究IL。当专家根据已知状态动作特征的线性分类器执行动作时，我们使用多类分类的简化来表明，在给定 N 次从最优状态推出的情况下，行为克隆的次优性为 (cid:101) O ( dH 2 /N )
We study the statistical guarantees for the Imitation Learning (IL) problem in episodic MDPs. Rajaraman et al. [22] show an information theoretic lower bound that in the worst case, a learner which can even actively query the expert policy suffers from a suboptimality growing quadratically in the length of the horizon, H . We study imitation learning under the µ -recoverability assumption of [27] which assumes that the difference in the Q -value under the expert policy across different actions in a state do not deviate beyond µ from the maximum. We show that the reduction proposed by [25] is statistically optimal: the resulting algorithm upon interacting with the MDP for N episodes results in a suboptimality bound of (cid:101) O ( µ |S| H/N ) which we show is optimal up to log-factors. In contrast, we show that any algorithm which does not interact with the MDP and uses an offline dataset of N expert trajectories must incur suboptimality growing as (cid:38) |S| H 2 /N even under the µ -recoverability assumption. This establishes a clear and provable separation of the minimax rates between the active setting and the no-interaction setting. We also study IL with linear function approximation . When the expert plays actions according to a linear classifier of known state-action features, we use the reduction to multi-class classification to show that with high probability, the suboptimality of behavior cloning is (cid:101) O ( dH 2 /N ) given N rollouts from the optimal