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
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.
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
-
2021 : What Would the Expert do()?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods »
Terrance Liu · Giuseppe Vietri · Steven Wu -
2021 : What Would the Expert do()?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Sik Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Information Discrepancy in Strategic Learning »
Yahav Bechavod · Chara Podimata · Steven Wu · Juba Ziani -
2021 : Gaming Helps! Learning from Strategic Interactions in Natural Dynamics »
Yahav Bechavod · Katrina Ligett · Steven Wu · Juba Ziani -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet S Talwalkar · Hoda Heidari · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Information Discrepancy in Strategic Learning »
Yahav Bechavod · Chara Podimata · Steven Wu · Juba Ziani -
2021 : Gaming Helps! Learning from Strategic Interactions in Natural Dynamics »
Yahav Bechavod · Katrina Ligett · Steven Wu · Juba Ziani -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet S Talwalkar · Hoda Heidari · Steven Wu -
2022 : Strategy-Aware Contextual Bandits »
Keegan Harris · Chara Podimata · Steven Wu -
2022 : Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance »
Xin Gu · Gautam Kamath · Steven Wu -
2022 : Strategy-Aware Contextual Bandits »
Keegan Harris · Chara Podimata · Steven Wu -
2022 : Hybrid RL: Using both offline and online data can make RL efficient »
Yuda Song · Yifei Zhou · Ayush Sekhari · J. Bagnell · Akshay Krishnamurthy · Wen Sun -
2022 : Strategy-Aware Contextual Bandits »
Keegan Harris · Chara Podimata · Steven Wu -
2022 : Differentially Private Gradient Boosting on Linear Learners for Tabular Data »
Saeyoung Rho · Shuai Tang · Sergul Aydore · Michael Kearns · Aaron Roth · Yu-Xiang Wang · Steven Wu · Cedric Archambeau -
2022 : Counterfactual Decision Support Under Treatment-Conditional Outcome Measurement Error »
Luke Guerdan · Amanda Coston · Kenneth Holstein · Steven Wu -
2022 Poster: On Privacy and Personalization in Cross-Silo Federated Learning »
Ken Liu · Shengyuan Hu · Steven Wu · Virginia Smith -
2022 Poster: Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints »
Justin Whitehouse · Aaditya Ramdas · Steven Wu · Ryan Rogers -
2022 Poster: Incentivizing Combinatorial Bandit Exploration »
Xinyan Hu · Dung Ngo · Aleksandrs Slivkins · Steven Wu -
2022 Poster: Semi-supervised Active Linear Regression »
Nived Rajaraman · Fnu Devvrit · Pranjal Awasthi -
2022 Poster: Sequence Model Imitation Learning with Unobserved Contexts »
Gokul Swamy · Sanjiban Choudhury · J. Bagnell · Steven Wu -
2022 Poster: Beyond the Best: Distribution Functional Estimation in Infinite-Armed Bandits »
Yifei Wang · Tavor Baharav · Yanjun Han · Jiantao Jiao · David Tse -
2022 Poster: Private Synthetic Data for Multitask Learning and Marginal Queries »
Giuseppe Vietri · Cedric Archambeau · Sergul Aydore · William Brown · Michael Kearns · Aaron Roth · Ankit Siva · Shuai Tang · Steven Wu -
2022 Poster: Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning (Gokul Swamy) »
Gokul Swamy -
2021 : Leveraging strategic interactions for causal discovery »
Steven Wu -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Sik Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2021 : Contributed Talk 2: What Would the Expert do?: Causal Imitation Learning »
Gokul Swamy -
2021 : What Would the Expert do()?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 Poster: Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods »
Terrance Liu · Giuseppe Vietri · Steven Wu -
2021 Poster: Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism »
Paria Rashidinejad · Banghua Zhu · Cong Ma · Jiantao Jiao · Stuart Russell -
2021 Poster: On the Value of Interaction and Function Approximation in Imitation Learning »
Nived Rajaraman · Yanjun Han · Lin Yang · Jingbo Liu · Jiantao Jiao · Kannan Ramchandran -
2021 Poster: MADE: Exploration via Maximizing Deviation from Explored Regions »
Tianjun Zhang · Paria Rashidinejad · Jiantao Jiao · Yuandong Tian · Joseph Gonzalez · Stuart Russell -
2021 Poster: Stateful Strategic Regression »
Keegan Harris · Hoda Heidari · Steven Wu -
2021 Poster: Taxonomizing local versus global structure in neural network loss landscapes »
Yaoqing Yang · Liam Hodgkinson · Ryan Theisen · Joe Zou · Joseph Gonzalez · Kannan Ramchandran · Michael Mahoney -
2020 Poster: Boundary thickness and robustness in learning models »
Yaoqing Yang · Rajiv Khanna · Yaodong Yu · Amir Gholami · Kurt Keutzer · Joseph Gonzalez · Kannan Ramchandran · Michael Mahoney -
2020 Poster: Metric-Free Individual Fairness in Online Learning »
Yahav Bechavod · Christopher Jung · Steven Wu -
2020 Poster: Understanding Gradient Clipping in Private SGD: A Geometric Perspective »
Xiangyi Chen · Steven Wu · Mingyi Hong -
2020 Poster: Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms »
Xiangyi Chen · Tiancong Chen · Haoran Sun · Steven Wu · Mingyi Hong -
2020 Spotlight: Understanding Gradient Clipping in Private SGD: A Geometric Perspective »
Xiangyi Chen · Steven Wu · Mingyi Hong -
2020 Oral: Metric-Free Individual Fairness in Online Learning »
Yahav Bechavod · Christopher Jung · Steven Wu -
2020 Session: Orals & Spotlights Track 20: Social/Adversarial Learning »
Steven Wu · Miro Dudik -
2020 Poster: Toward the Fundamental Limits of Imitation Learning »
Nived Rajaraman · Lin Yang · Jiantao Jiao · Kannan Ramchandran -
2020 Poster: An Efficient Framework for Clustered Federated Learning »
Avishek Ghosh · Jichan Chung · Dong Yin · Kannan Ramchandran -
2020 Poster: SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory »
Paria Rashidinejad · Jiantao Jiao · Stuart Russell -
2020 Oral: SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory »
Paria Rashidinejad · Jiantao Jiao · Stuart Russell -
2019 Workshop: Information Theory and Machine Learning »
Shengjia Zhao · Jiaming Song · Yanjun Han · Kristy Choi · Pratyusha Kalluri · Ben Poole · Alex Dimakis · Jiantao Jiao · Tsachy Weissman · Stefano Ermon -
2019 Poster: Equal Opportunity in Online Classification with Partial Feedback »
Yahav Bechavod · Katrina Ligett · Aaron Roth · Bo Waggoner · Steven Wu -
2019 Poster: Random Quadratic Forms with Dependence: Applications to Restricted Isometry and Beyond »
Arindam Banerjee · Qilong Gu · Vidyashankar Sivakumar · Steven Wu -
2019 Poster: Private Hypothesis Selection »
Mark Bun · Gautam Kamath · Thomas Steinke · Steven Wu -
2019 Poster: Locally Private Gaussian Estimation »
Matthew Joseph · Janardhan Kulkarni · Jieming Mao · Steven Wu -
2018 Poster: Dual Policy Iteration »
Wen Sun · Geoffrey Gordon · Byron Boots · J. Bagnell -
2017 : Posters and Coffee »
Jean-Baptiste Tristan · Yunseong Lee · Anna Veronika Dorogush · Shohei Hido · Michael Terry · Mennatullah Siam · Hidemoto Nakada · Cody Coleman · Jung-Woo Ha · Hao Zhang · Adam Stooke · Chen Meng · Christopher Kappler · Lane Schwartz · Christopher Olston · Sebastian Schelter · Minmin Sun · Daniel Kang · Waldemar Hummer · Jichan Chung · Tim Kraska · Kannan Ramchandran · Nick Hynes · Christoph Boden · Donghyun Kwak -
2017 : Spotlights »
Antti Kangasrääsiö · Richard Everett · Yitao Liang · Yang Cai · Steven Wu · Vidya Muthukumar · Sven Schmit -
2017 Poster: Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM »
Katrina Ligett · Seth Neel · Aaron Roth · Bo Waggoner · Steven Wu -
2017 Poster: Predictive-State Decoders: Encoding the Future into Recurrent Networks »
Arun Venkatraman · Nicholas Rhinehart · Wen Sun · Lerrel Pinto · Martial Hebert · Byron Boots · Kris Kitani · J. Bagnell -
2016 Poster: Cyclades: Conflict-free Asynchronous Machine Learning »
Xinghao Pan · Maximilian Lam · Stephen Tu · Dimitris Papailiopoulos · Ce Zhang · Michael Jordan · Kannan Ramchandran · Christopher Ré · Benjamin Recht -
2016 Poster: Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs »
Shahin Jabbari · Ryan Rogers · Aaron Roth · Steven Wu -
2015 Poster: Parallel Correlation Clustering on Big Graphs »
Xinghao Pan · Dimitris Papailiopoulos · Samet Oymak · Benjamin Recht · Kannan Ramchandran · Michael Jordan