Convergence of Value Aggregation for Imitation Learning

Ching-An Cheng, Byron Boots

Abstract

Value aggregation is a general framework for solving imitation learning problems. Based on the idea of data aggregation, it generates a policy sequence by iteratively interleaving policy optimization and evaluation in an online learning setting. While the existence of a good policy in the policy sequence can be guaranteed non-asymptotically, little is known about the convergence of the sequence or the performance of the last policy. In this paper, we debunk the common belief that value aggregation always produces a convergent policy sequence with improving performance. Moreover, we identify a critical stability condition for convergence and provide a tight non-asymptotic bound on the performance of the last policy. These new theoretical insights let us stabilize problems with regularization, which removes the inconvenient process of identifying the best policy in the policy sequence in stochastic problems.

Introduction

In Imitation Learning (IL), a learner attempts to mimic an expert's behavior, such as a human driver or an optimal controller. A fundamental challenge in this domain is covariate shift: as the learner makes minor errors, it drifts into states that the expert never visited. This leads to compounding errors that the learner does not know how to correct.

Algorithms like AggreVaTe (Aggregate Value to Imitate) address this by iteratively collecting new data using the learner's current policy and retraining. While existing theory guarantees that at least one policy in the resulting sequence will perform well, practitioners typically use the last policy produced by the algorithm. This paper investigates a critical gap in IL theory: Does the policy sequence actually converge, and is the final policy reliable?

The Stability Condition: $\alpha$ and $\beta$

To analyze the convergence of AggreVaTe, the authors frame the algorithm as an online convex optimization problem. They identify two primary parameters that dictate the behavior of the learning process:

  1. Strong Convexity ($\alpha$): This represents the "sharpness" of the cost function. A higher $\alpha$ indicates that the optimization landscape clearly points toward the optimal action, making the problem better-behaved.
  2. Distribution Sensitivity ($\beta$): This measures how much the distribution of states changes when the policy is modified. If a minor change in the policy leads to a drastically different set of visited states, $\beta$ is high.

The interaction between these two factors is captured by the stability constant $\theta = \beta / \alpha$. This ratio represents the tug-of-war between the environment's sensitivity to change and the learner's ability to optimize.

Convergence vs. Divergence

The paper proves that the common assumption of universal convergence in value aggregation is a myth. The behavior of the algorithm is strictly governed by the stability constant:

  • The Stable Regime ($\theta < 1$): When the cost function is sufficiently sharp relative to the environment's sensitivity, the algorithm is stable. The performance error of the last policy vanishes at a rate of $O(N^{2(\theta-1)})$, where $N$ is the number of iterations.
  • The Unstable Regime ($\theta > 1$): If the environment is too sensitive, the algorithm can actually diverge. The authors provide a lower bound showing that in certain problems, the performance error grows at a rate of $\Omega(N^{2(\theta-1)})$, meaning the policies get progressively worse despite more data.

This finding is significant because it suggests that the common heuristic of returning the last policy is only theoretically sound under specific conditions. Without these conditions, the "best" policy might have occurred early in training and been subsequently lost.

Regularization as a Stabilizer

One of the paper's most practical contributions is the theoretical justification for regularization. Techniques such as "Mixing Policies" (where the expert and learner share control, similar to DAgger) or "Weighted Regularization" (penalizing deviations from the expert) are often used as empirical tricks.

The authors show that these methods are mathematically essential for stability. By adding regularization, practitioners effectively lower the stability constant $\theta$, forcing the system into a convergent state. This ensures that the last policy is high-performing, removing the need for the computationally expensive process of identifying the "best" policy from a large sequence in stochastic environments.

Conclusion

By identifying the stability ratio $\theta$, this research provides a rigorous framework for understanding value aggregation in imitation learning. While the theory currently relies on convexity assumptions, it offers a clear explanation for why certain IL problems diverge and how regularization can be used to guarantee the quality of the final learned policy. This work bridges the gap between theoretical guarantees and the practical needs of roboticists and AI researchers.

Summary updated

Abstract

Value aggregation is a general framework for solving imitation learning problems. Based on the idea of data aggregation, it generates a policy sequence by iteratively interleaving policy optimization and evaluation in an online learning setting. While the existence of a good policy in the policy sequence can be guaranteed non-asymptotically, little is known about the convergence of the sequence or the performance of the last policy. In this paper, we debunk the common belief that value aggregation always produces a convergent policy sequence with improving performance. Moreover, we identify a critical stability condition for convergence and provide a tight non-asymptotic bound on the performance of the last policy. These new theoretical insights let us stabilize problems with regularization, which removes the inconvenient process of identifying the best policy in the policy sequence in stochastic problems.
BibTeX
@inproceedings{cheng2018convergence,
  author = {Ching-An Cheng and Byron Boots},
  title = {{Convergence of Value Aggregation for Imitation Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=igvpkjMog6r},
}
Figure