PaperlayerView exact revision on arXiv

Source-linked AI summary

Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction

Wen Sun, Arun Venkatraman, Geoffrey J. Gordon, Byron Boots, J. Andrew Bagnell

arXiv:1703.01030v1cs.LG

TL;DR

Sequential prediction and robotics control require learning policies for long-term decisions, but reinforcement learning may learn slowly without a strong initial cost-to-go estimate. The paper introduces AggreVaTeD, a differentiable imitation-learning method that leverages near-optimal oracles, and reports faster learning than reinforcement learning together with expert-level and sometimes super-expert performance. Its theory and experiments support imitation learning as more effective than reinforcement learning for sequential prediction when near-optimal cost-to-go oracles are available.

  • Problem

    Sequential decision problems need policies that manage accumulated future costs, while reinforcement learning may start with poor policies or cost-to-go estimates and fixed-data imitation learning faces distribution mismatch.

  • Method

    AggreVaTeD extends AggreVaTe into a differentiable policy-gradient method for training neural policies with near-optimal cost-to-go oracles.

  • Results

    Across robotics control and dependency parsing experiments, learned policies reached expert-level and sometimes super-expert performance, while theory and practice showed imitation learning learning much faster than reinforcement learning.

  • Takeaways & Limitations

    Imitation learning can be more effective than reinforcement learning for sequential prediction when near-optimal cost-to-go oracles are available.

  • Takeaways & Limitations

    For nonlinear function approximators, the original AggreVaTe analysis does not hold because the loss is nonconvex in the parameters.

Abstract

from arXiv · show

Researchers have demonstrated state-of-the-art performance in sequential decision making problems (e.g., robotics control, sequential prediction) with deep neural network models. One often has access to near-optimal oracles that achieve good performance on the task during training. We demonstrate that AggreVaTeD --- a policy gradient extension of the Imitation Learning (IL) approach of (Ross & Bagnell, 2014) --- can leverage such an oracle to achieve faster and better solutions with less training data than a less-informed Reinforcement Learning (RL) technique. Using both feedforward and recurrent neural network predictors, we present stochastic gradient procedures on a sequential prediction task, dependency-parsing from raw image data, as well as on various high dimensional robotics control problems. We also provide a comprehensive theoretical study of IL that demonstrates we can expect up to exponentially lower sample complexity for learning with AggreVaTeD than with RL algorithms, which backs our empirical findings. Our results and theory indicate that the proposed approach can achieve superior performance with respect to the oracle when the demonstrator is sub-optimal.

1. Introduction

Sequential prediction requires reasoning over long-term consequences, while imitation learning can exploit near-optimal cost-to-go oracles available during training. AggreVaTeD extends this approach with differentiable policy gradients and achieves strong empirical and theoretical results relative to reinforcement learning.

  • Motivation: Sequential decisions can accumulate high future loss because later predictions depend on earlier predictions.This motivates treating predictors as policies that reason about long-term accumulated cost.
  • Motivation: Imitation learning uses a training-time oracle that supplies near-optimal actions and future accumulated loss, unlike reinforcement learning methods that may begin with poor policies or cost-to-go estimates.The oracle is unavailable at test time, so the learned policy must approximate its performance independently.
  • Motivation: Fixed-dataset imitation learning can fail when training and test distributions differ, motivating interactive methods that collect data under learned policies.Distribution mismatch is difficult to prevent in practice.
  • Approach: AggreVaTeD is a differentiable extension of AggreVaTe that applies interactive imitation learning to sequential prediction and continuous robot control.Its differentiability supports rich nonlinear policies, including neural networks and recurrent models.
  • Results: Experiments show expert-level and sometimes super-expert performance, while imitation learning learns much faster than reinforcement learning when an oracle is available.The results include deep neural network experiments in robotics control and dependency parsing.
  • Theory: Theoretical results establish exponentially better sample efficiency for imitation learning on a constructed MDP and near-optimal regret for AggreVaTeD with exponential gradient descent.The paper also provides a regret upper bound for AggreVaTeD and a lower bound for any imitation-learning algorithm.

2. Preliminaries

The paper casts long-term sequential prediction and robotics control as finite-horizon Markov decision processes. It defines policies, trajectory-induced state distributions, costs, and expert cost-to-go information used by imitation learning.

  • MDP formulation: An MDP represents sequential decision making through states, actions, transition dynamics, costs, an initial-state distribution, and a finite horizon.Robotics controls map naturally to actions, while sequential predictions define states through the prediction history.
  • Policies and trajectories: A stochastic policy assigns each state a probability distribution over actions, which determines the distribution of resulting trajectories.The policy and MDP jointly induce the trajectory distribution.
  • Policies and trajectories: State distributions at each time step and their average summarize where a policy visits during an episode.These distributions support definitions of expected policy cost and imitation-learning losses.
  • Expert information: The expert policy may be sub-optimal, and its cost-to-go oracle is assumed known or estimable without bias.The oracle can be estimated by taking an action and then rolling out the expert for the remaining horizon.
  • Function approximation: Policies are parameterized by θ and may use the full history of partial observations and actions, with LSTM hidden states compressing that history.This supports partially observable settings and high-dimensional parameter spaces.

3. Differentiable Imitation Learning

Differentiable imitation learning reduces online imitation losses to policy-gradient updates for expressive neural policies. The paper develops regular and natural-gradient procedures, while noting computational and nonconvexity limitations of the underlying analysis.

  • Differentiable imitation learning: Policy-based imitation learning uses online learning to train expressive differentiable policies that approach expert performance when the expert is absent at test time.This reduction enables policies represented by deep networks or LSTMs.
  • AggreVaTe: AggreVaTe updates policies by minimizing expert cost-to-go under the state distribution induced by the current learned policy.The original procedure uses Follow-the-Leader over accumulated episode losses.
  • AggreVaTe: When the expert is not locally optimal, the regret formulation permits the learned policy to outperform the expert, consistent with the reported experiments.The quantity ε_N measures the online learner’s excess loss relative to the best policy in the policy class.
  • Motivation for AggreVaTeD: Exact batch optimization at every episode becomes increasingly expensive for large nonlinear function approximators.This computational burden motivates efficient online gradient procedures.
  • Policy updates: Online Gradient Descent and Exponential Gradient Descent yield regular stochastic policy-gradient and natural policy-gradient updates, respectively.The natural-gradient procedure is derived for discrete MDPs and extended to continuous MDPs through approximations.
  • Online Gradient Descent: For discrete actions, the loss gradient is computed from policy log-probability gradients weighted by the expert cost-to-go.The resulting gradient supports an efficient online update of the policy parameters.
  • Continuous actions: For continuous actions, importance weighting reformulates the loss because evaluating the oracle cost-to-go over infinitely many actions is infeasible.The reformulated objective can then be differentiated with respect to policy parameters.
  • Natural Gradient Descent: Natural-gradient updates use local Taylor and KL-divergence approximations to obtain a Fisher-information preconditioned step.The resulting update has the form θ_n+1 = θ_n − η_n I(θ_n)^−1 ∇_θℓ_n(θ)|_θ=θ_n.

4. Sample-Based Practical Algorithms

The paper develops sample-based gradient procedures for AggreVaTeD, including variance reduction and natural-gradient estimation, and presents a simple iterative framework without data aggregation. It notes that nonlinear policies invalidate the prior convex analysis, although experiments show competitive or superior performance to the oracle.

  • Sample-based estimation: Finite samples collected during policy execution approximate the gradients and Fisher information matrices needed by AggreVaTeD.The exact-expectation derivations are replaced with practical sample-based estimators.
  • Gradient estimation: Unbiased gradient estimates can use sampled trajectories, while access to V*_t(s) enables variance-reduced advantage-based estimators.Replacing Q*_t(s,a) with the state-action advantage function yields unbiased, variance-reduced estimates.
  • Natural gradients: The Fisher information matrix is approximated as a sum of K rank-one matrices, producing a low-rank representation when K ≪ d.This representation supports solving for the descent direction with Conjugate Gradient.
  • Natural gradients: Conjugate Gradient avoids explicitly storing the d^2-sized Fisher matrix, using O(Kd) storage and O(K^2d) computational time.The method stores the sample-derived matrix instead of the full Fisher matrix.
  • AggreVaTeD framework: AggreVaTeD mixes the expert and current policy during roll-in, estimates a descent direction, updates parameters, and returns the best validation policy.The mixing rate decays toward zero across iterations, and the procedure does not require storing trajectories from previous iterations.
  • Limitation: With nonlinear policy approximators, the prior AggreVaTe analysis does not apply because the loss is non-convex in the parameters.Experiments nevertheless report policies that are competitive with, and sometimes superior to, the oracle.

5. Quantify the Gap: An Analysis of IL vs RL

The paper analyzes how access to an optimal or noisy cost-to-go oracle changes imitation-learning regret relative to reinforcement learning. On a binary-tree MDP, imitation learning can be exponentially faster, while general discrete MDPs yield at least polynomial and potentially exponential gaps; AggreVaTeD is near-optimal under noisy oracle access.

  • Setup: The analysis measures learning speed using cumulative regret over finite-horizon episodic imitation-learning and reinforcement-learning algorithms.A smaller regret rate indicates faster learning, and the expert is assumed optimal throughout this analysis.
  • Exponential gap: A depth-K deterministic binary-tree MDP has zero non-leaf costs and independently sampled leaf costs, allowing imitation learning to outperform reinforcement learning exponentially.The tree contains S = 2^K − 1 states and two actions corresponding to going left or right.
  • Exponential gap: With access to Q*, AggreVaTe with FTL achieves exponentially faster learning on the binary-tree MDP than reinforcement learning.Oracle comparisons can eliminate an unexplored subtree after identifying the better root action.
  • Noisy oracle: With only unbiased noisy estimates of Q*, AggreVaTeD with EG still achieves poly-logarithmic regret in S on the binary-tree MDP.The noisy setting prevents deterministic elimination based on individual estimates, but imitation learning retains a strong regret advantage.
  • General discrete MDPs: For general discrete MDPs, the analysis establishes a regret upper bound for AggreVaTeD with EG and a lower bound showing near-optimality.The results compare imitation learning with efficient exploration methods such as UCB-based reinforcement learning.
  • General discrete MDPs: For discrete MDPs, imitation learning can have at least a polynomial gap and possibly an exponential gap over reinforcement learning, while the H = 1 lower bound makes key dependencies tight.The lower-bound result concerns dependence on N, A, and S with unbiased Q* estimates.

6. Experiments

Experiments evaluate AggreVaTeD with neural policies on robotics control and handwritten algebra dependency parsing. Across settings, it often matches or exceeds expert performance and improves faster than RL, including partial observability.

  • Experimental setup: AggreVaTeD is evaluated on OpenAI Gym robotics simulations and handwritten algebra dependency parsing, using reward and UAS as performance measures.Robotics experiments include CartPole, Acrobot, Hopper, and Walker; parsing uses raw image inputs.
  • Method: AggreVaTeD uses expert-policy mixing during roll-in and supports regular or natural gradient updates, with variance-reduced estimates available.The mixing rate decays toward zero across iterations.
  • Robotics simulations: 5.8% and 25%: natural-gradient AggreVaTeD surpasses expert performance on Acrobot and CartPole, respectively.Results are averaged over 10 random trials.
  • Robotics simulations: 92%: an LSTM AggreVaTeD policy reaches this fraction of expert performance under partial observations, while RL algorithms show no improvement.The expert observes full states, whereas the learner observes only link positions.
  • Robotics simulations: 5.4%: AggreVaTeD outperforms the expert on Walker while achieving 97% of the expert’s performance on Hopper.The Walker and Hopper results are averaged over 5 random trials.
  • Dependency parsing: 97%: the LSTM policy achieves this fraction of optimal expert UAS on handwritten algebra dependency parsing.It significantly outperforms the reactive neural-network policy and DAgger with a Kernelized SVM.

7. Conclusion

The paper concludes that AggreVaTeD trains neural policies for robotics control and dependency parsing in fully and partially observable settings. Its theoretical and experimental results suggest faster and more effective learning than RL when near-optimal cost-to-go oracles are available.

  • AggreVaTeD trains neural-network policies for continuous robot control and dependency parsing from raw image data.
  • The learned policies reach expert-level and sometimes super-expert performance in fully and partially observable settings.
  • Table 1 compares UAS for supervised learning, RL initialized with supervised learning, random policies, DAgger, and AggreVaTeD approaches.The table caption defines SL, SL-RL, Random, and the DAgger comparison.
  • Theoretical and experimental results suggest imitation learning is significantly more effective than RL when near-optimal cost-to-go oracles are available.

A. Derivation of Eq. 4

This passage introduces the derivation by starting from the policy objective with a parameterized policy πθ.

  • The derivation begins with Eq. 1 after replacing the policy by its parameterized form πθ.

B. Derivation of Exponential Gradient Update in Discrete MDP

The appendix derives AggreVaTeD’s exponential-gradient update for discrete MDPs and situates it within performance-difference and online-learning analyses.

  • With KL-divergence penalization, the policy is updated once per episode using the exponential-gradient formulation.
  • The optimization separates across states, so each state-specific policy component can be optimized independently.
  • The state-specific update follows by differentiating with respect to πs[j] and setting the derivative to zero.
  • The Performance Difference Lemma is introduced as a tool for the subsequent theoretical analysis.
  • The appendix also invokes Exponential Gradient descent’s regret bound for linear losses over a probability simplex.

D. Proof of Theorem 5.1

The proof reduces a bandit problem to a binary-tree MDP, showing that reinforcement learning inherits a square-root dependence on the number of states through the bandit lower bound.

  • A stochastic multi-arm bandit with S arms is used as the source problem for the reduction.The bandit regret lower bound applies to distributions over arm costs.
  • Each deterministic policy selects one root-to-leaf trajectory, and the optimal policy selects the trajectory with minimum expected leaf cost.Thus, trajectory costs correspond directly to the expected costs of the associated bandit arms.
  • Running an RL algorithm on the constructed MDP solves the original bandit problem, transferring the bandit regret lower bound to RL.The reduction establishes the claimed lower bound through the equivalence between trajectories and arms.

E. Proof of Theorem 5.2

The proof analyzes AggreVaTe on a binary-tree MDP, where exact cost-to-go queries let successive policies move toward the best trajectory and achieve logarithmic state dependence.

  • For a deterministic policy class with two actions at each of S states, the number of policies is 2^S.The proof assumes the leftmost trajectory has the lowest total cost.
  • After the first episode, cost-sensitive classification forces the updated policy to choose the lower-cost root action and enter the optimal trajectory.The dataset contains visited states paired with both actions’ exact optimal cost-to-go values.
  • By induction, each episode extends the prefix of the optimal trajectory reached by the current policy until the best leaf is identified.At the end of episode K−1, policy πK reaches the end of the best trajectory.
  • AggreVaTe with FTL identifies the best trajectory within K−1 episodes and has cumulative regret O(K)=O(log(S)).This bound assumes the average cost at each leaf is a bounded constant.
  • With noisy unbiased cost-to-go estimates, the analysis uses a convex hull of deterministic base policies and exponential gradient descent.Each stochastic policy selects a base trajectory with probability wi, while the noisy loss remains linear in the mixture weights.
  • The noisy loss is an unbiased estimate of the exact loss, and bounded martingale differences support high-probability control through concentration.The exact loss corresponds to infinitely many roll-ins followed by exact cost-to-go queries on visited states.

G. Proof of Theorem 5.4

The proof extends the noisy-query analysis to general finite-horizon MDPs by updating state-time policies independently and controlling sampling variability across states.

  • The general policy consists of action-probability vectors πs,t for every state and time step.Exponential gradient descent optimizes the corresponding policy components independently.
  • The loss uses the optimal cost-to-go vector Q* for each action, and the proof applies the performance difference lemma after bounding the update regret.The argument substitutes the resulting bound into the performance comparison.
  • In the one-step construction, each episode samples one of S states uniformly and updates only that state’s policy using a noisy unbiased estimate of Q*.Policies for unvisited states remain unchanged because no feedback is received for them.
  • The number of visits to each state is binomial, and Hoeffding bounds control the visit frequencies used in the regret analysis.The proof represents each state’s visit indicator as a Bernoulli variable with parameter 1/S.
  • The proof completes the theorem by taking N to infinity, substituting the concentration result, and concluding the stated bound.The final step is explicitly identified as the theorem’s conclusion.
  • For handwritten algebra parsing, Q*(s,a) is computed as the final UAS after taking action a and rolling out the expert to completion.This makes AggreVaTeD directly maximize UAS rather than merely imitate expert actions.
Loading 1703.01030v1…