ILeNA: ${ϵ}^{-2}$ Sample Complexity for Value-Based Imitation Learning

Value-based imitation learning is a new approach to eliminate assumptions about the policy class. We study offline imitation learning where expert realizability is replaced by $Q^{\pi }$-realizability. The objective is to find a policy with a return at least as good as the expert's. Our proposed algorithm, ILeNA, obtains a sample complexity in $O(\frac{\log \mathcal{N}(\mathcal{Q})}{(1-\gamma {)}^4{ϵ}^2})$ under general $Q^{\pi }$-realizability, and $\tilde{O}(\frac{d}{(1-\gamma {)}^4{ϵ}^2})$ under linear $Q^{\pi }$-realizability. This solves the open problem of obtaining sample complexity in the order of ${ϵ}^{-2}$ under non-convex action-value functions sets. The best previous sample complexity in the general non-convex case was in $O({ϵ}^{-4})$, which is improved by a factor of $O(\frac{1}{(1-\gamma {)}^4{ϵ}^2})$ in this work. We reduce the problem to a two-player repeated game between an actor ($\pi$-player) and a critic ($Q$-player), and translate any no-regret dynamic between the players into a guarantee for the value of the output policy. The generality of this result enables us to use an appropriate pair of no-regret algorithms for the two players, which gives us the aforementioned sample complexity. We also support our theoretical result with numerical experiments.