A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning

Sequential prediction problems such as imitation learning, where future depend on previous predictions (actions), violate the common. i. d. assumptions made in statistical learning. This leads to poor performance theory and often in practice. Some recent approaches provide stronger in this setting, but remain somewhat unsatisfactory as they train non-stationary or stochastic policies and require a large number of. In this paper, we propose a new iterative algorithm, which trains a deterministic policy, that can be seen as a no regret algorithm in online learning setting. We show that any such no regret algorithm, combined additional reduction assumptions, must find a policy with good performance the distribution of observations it induces in such sequential settings. demonstrate that this new approach outperforms previous approaches on two imitation learning problems and a benchmark sequence labeling.