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 data collection. While value aggregation has been shown to be successful in many applications, its theoretical convergence is not well understood. In this paper, we analyze the convergence of the policy sequence generated by value aggregation. We show that the sequence converges to a neighborhood of the expert policy if the problem is stable, and we provide a tight bound on the size of the neighborhood. We also show that the sequence can diverge if the problem is unstable, and we provide a simple example to illustrate this. Finally, we propose a new value aggregation algorithm that is guaranteed to converge even for unstable problems.
Introduction
In Imitation Learning (IL), a learner attempts to mimic an expert's behavior by observing demonstrations. Modern iterative methods, such as DAgger (Dataset Aggregation) and AggreVaTe (Aggregate Value to Imitate), have become the standard for addressing the distribution shift problem—where the learner’s errors lead it into states not covered by the expert's initial demonstrations.
These methods work by iteratively collecting data using the current policy, querying an expert for the optimal actions or values in those states, and updating the policy. However, a significant gap has existed between theory and practice: while existing proofs guaranteed that the average policy in a sequence would perform well, practitioners almost universally deploy the last policy ($\pi_N$). This paper by Ching-An Cheng and Byron Boots provides the first rigorous theoretical foundation for this "last-policy" assumption, identifying the specific conditions under which value aggregation converges or diverges.
The Stability Constant: $\theta$
The authors analyze value aggregation through the lens of online convex optimization. The core of their contribution is the identification of a stability constant, defined as $\theta = \beta / \alpha$. This constant captures the interplay between two fundamental properties of the learning problem:
- $\alpha$ (Strong Convexity): This represents the curvature of the cost function. A higher $\alpha$ means it is easier for the optimization process to identify the unique best action in a given state.
- $\beta$ (Lipschitz Continuity of State Distribution): This represents how much the distribution of states visited changes when the policy is slightly modified. A high $\beta$ indicates an environment where small changes in behavior lead to drastically different outcomes.
The Myth of Automatic Convergence
A common assumption in reinforcement learning is that more data and more iterations lead to better performance. This paper "debunks" that belief for value aggregation. The authors prove that the value $\theta = 1$ acts as a critical tipping point:
- Stable Regime ($\theta < 1$): The sequence of policies is guaranteed to converge to a neighborhood of the expert's performance. The performance of the last policy $F(x_N, x_N)$ is bounded by the approximation error of the policy class plus a term that decays at a rate of $O(N^{2(\theta-1)})$.
- Unstable Regime ($\theta > 1$): The algorithm can enter a destructive feedback loop. Small errors in the policy lead to new state distributions that the current policy is even less prepared for, causing the performance of the last policy to spiral and eventually diverge from the expert.
Stabilization Strategies
To address environments where $\theta > 1$, the authors propose two mathematically grounded "fixes" that are often used as heuristics in practice:
- Policy Mixing: By blending the learner's current policy with the expert's policy during data collection (a technique used in the original DAgger algorithm), the learner effectively reduces the distribution shift (lowering $\beta$).
- Weighted Regularization: By adding a penalty term that keeps the learner's policy close to the expert's or to the policy from the previous iteration, the learner increases the effective stability of the optimization (increasing $\alpha$).
Experimental Validation: A Motivating Example
As a theoretical work, the paper utilizes a two-stage deterministic optimal control problem to validate these findings. This toy environment is designed to be analytically solvable while remaining complex enough to exhibit divergence. The researchers demonstrated that when the environment's sensitivity was tuned such that $\theta > 1$, AggreVaTe produced a sequence of policies with strictly degrading performance, confirming that the last policy is not always the best.
Stochastic Robustness
The paper extends these insights to stochastic settings, which are more representative of real-world robotics. They show that even with finite samples and noisy observations, the performance of the last policy can be bounded if the sample size growth is managed correctly relative to the problem's stability. In the stochastic case, the last policy $x_N$ converges at a rate of nearly $\tilde{O}(1/N)$, matching the best known results for Empirical Risk Minimization (ERM) but extending them to the non-i.i.d. setting of reinforcement learning.
Conclusion and Future Work
This research provides a vital bridge between the empirical success of imitation learning and its theoretical underpinnings. It explains why algorithms like AggreVaTe often work—likely because the implicit regularization of optimizers like SGD or the inherent structure of the task keeps the system in a stable regime.
While the stability constant $\theta$ is difficult to calculate for complex deep neural networks, this framework allows researchers to reason about why their models might be failing to converge. Future work may involve developing adaptive methods to estimate these stability constants during training, allowing for the automatic tuning of regularization parameters to ensure convergence in any environment.
Summary updated