Timezone: »

 
Poster
Minimax Optimal Online Imitation Learning via Replay Estimation
Gokul Swamy · Nived Rajaraman · Matt Peng · Sanjiban Choudhury · J. Bagnell · Steven Wu · Jiantao Jiao · Kannan Ramchandran

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #243
in Poster Session 1 »
Online imitation learning is the problem of how best to mimic expert demonstrations, given access to the environment or an accurate simulator. Prior work has shown that in the \textit{infinite} sample regime, exact moment matching achieves value equivalence to the expert policy. However, in the \textit{finite} sample regime, even if one has no optimization error, empirical variance can lead to a performance gap that scales with $H^2 / N_{\text{exp}}$ for behavioral cloning and $H / N_{\text{exp}}$ for online moment matching, where $H$ is the horizon and $N_{\text{exp}}$ is the size of the expert dataset. We introduce the technique of ``replay estimation'' to reduce this empirical variance: by repeatedly executing cached expert actions in a stochastic simulator, we compute a smoother expert visitation distribution estimate to match. In the presence of general function approximation, we prove a meta theorem reducing the performance gap of our approach to the \textit{parameter estimation error} for offline classification (i.e. learning the expert policy). In the tabular setting or with linear function approximation, our meta theorem shows that the performance gap incurred by our approach achieves the optimal $\widetilde{O} \left( \min( H^{3/2} / N_{\text{exp}}, H / \sqrt{N_{\text{exp}}} \right)$ dependency, under significantly weaker assumptions compared to prior work. We implement multiple instantiations of our approach on several continuous control tasks and find that we are able to significantly improve policy performance across a variety of dataset sizes.
Keywords: imitation learning

Author Information

Gokul Swamy (Carnegie Mellon University)
Nived Rajaraman (University of California, Berkeley)

Hi I am Nived, a 2nd year PhD student at the University of California, Berkeley. My research interests are broadly in high dimensional statistics. More recently I have been exploring the theory of reinforcement learning

Matt Peng (University of California Berkeley)
Sanjiban Choudhury (Department of Computer Science, Cornell University)
J. Bagnell (Carnegie Mellon University)
Steven Wu (Carnegie Mellon University)
Jiantao Jiao (University of California, Berkeley)
Kannan Ramchandran (UC Berkeley)

More from the Same Authors