Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction

Introduction

A fundamental challenge in artificial intelligence, robotics, and language processing is to reason, plan, and make a sequence of decisions to minimize accumulated cost, achieve a long-term goal, or optimize for a loss acquired only after many predictions. Reinforcement Learning (RL), especially deep RL, has dramatically advanced the state of the art in sequential decision making in high-dimensional robotics control tasks as well as in playing video and board games (Schulman et al., 2015; Silver et al., 2016). Though conventional supervised learning of deep models has been pivotal in advancing performance in sequential prediction problems, researchers are beginning to utilize deep RL methods to achieve high performance (Ranzato et al., 2015; Bahdanau et al., 2016; Li et al., 2016). Often in sequential prediction tasks, future predictions from the learner are dependent on the history of previous predictions; thus, a poor prediction early on can yield high accumulated loss (cost) for future predictions. Viewing the predictor as a policy $\pi$, deep RL algorithms are able to reason about the future accumulated cost in a sequential decision making process whether it is a traditional robotics control problem or a sequential structured prediction task.

In contrast with reinforcement learning methods, well-known imitation learning (IL) and sequential prediction algorithms such as SEARN (Daumé III et al., 2009), DaD (Venkatraman et al., 2015), AggreVaTe (Ross & Bagnell, 2014), and LOLS (Chang et al., 2015b) reduce the sequence prediction problem to supervised learning by leveraging one special property of the sequence prediction problem: at training time we usually have a (near) optimal cost-to-go oracle. At any point along the sequential prediction process (i.e. state or partially completed sequential prediction), the oracle is able to select the next (near)-best action.

Concretely, the above methods assume access to an oracleExpert, demonstrator, and oracle are used interchangeably. that provides an optimal or near-optimal action and the future accumulated loss $Q^{*}$, also called the cost-to-go. For robotics control problems, this oracle may come from a human expert guiding the robot during the training phase (Abbeel & Ng, 2004) or from an optimal MDP solver (Ross et al., 2011; Kahn et al., 2016) that either may be too slow to use at test time or leverages information unavailable at test time (e.g., ground truth). Similarly, for sequential prediction problems, an oracle can be constructed by optimization (e.g., beam search) or by a clairvoyant greedy algorithm (Daumé III et al., 2009; Ross et al., 2013; Rhinehart et al., 2015; Chang et al., 2015a) that is near-optimal on the task specific performance metric (e.g., cumulative reward, IoU, Unlabeled Attachment Score, BLEU) given the training data’s ground truth.

Such an oracle, however, is only available during training time (e.g., when there is access to ground truth). Thus, the goal of IL is to learn a policy $\hat{\pi}$, with the help of the oracle $(\pi^{*},Q^{*})$ during the training session, such that $\hat{\pi}$ achieves similar quality performance at test time when the oracle is unavailable. In contrast to IL, reinforcement learning methods often initialize with an random policy $\pi_{0}$ or cost-to-go (accumulated loss) $Q_{0}$ predictor which may be far from the optimal. The optimal policy (or cost-to-go) must be found through a tradeoff of dithering, directed exploration, and exploitation.

The existence of oracle can be exploited to alleviate blind learning by trial and error: one can imitate the oracle to speed up learning process by significantly reducing exploration. A classic IL method is to collect data from running the demonstrator or oracle and train a regressor or classifier via supervised learning. These methods (Abbeel & Ng, 2004; Syed et al., 2008; Ratliff et al., 2006; Ziebart et al., 2008; Finn et al., 2016; Ho & Ermon, 2016) learn either a policy $\hat{\pi}^{*}$ or $\hat{Q}^{*}$ from a fixed-size dataset pre-collected from the oracle. A pernicious problem with these methods is that they require the training and test data to be sampled from the same distribution. This is very difficult to enforce in practice, and, as a result, policies learned by these methods can fail spectacularly in theory and in practice (Ross & Bagnell, 2010). Interactive approaches to IL such as SEARN (Daumé III et al., 2009), DAgger (Ross et al., 2011), and AggreVaTe (Ross & Bagnell, 2014) interleave learning and testing procedures to overcome the data mismatch issue and, as a result, work well in practical applications. Furthermore, these interactive approaches can provide strong theoretical guarantees between training time loss and test time performance through a reduction to no-regret online learning.

In this work, we introduce AggreVaTeD, a differentiable version of AggreVaTe (Aggregate Values to Imitate (Ross & Bagnell, 2014)) which extends interactive IL for use in sequential prediction and challenging continuous robot control tasks. We provide two gradient update procedures: a regular gradient update developed from Online Gradient Descent (OGD) (Zinkevich, 2003) and a natural gradient update (Kakade, 2002; Bagnell & Schneider, 2003) which we show is closely related to Exponential Gradient Descent (EG), another popular no-regret algorithm that enjoys an almost dimension-free property (Bubeck et al., 2015).i.e., the regret bound depends on poly-log of the dimension of parameter space.

AggreVaTeD leverages the oracle to learn rich polices that can be represented by complicated non-linear function approximators. Our experiments with deep neural networks on various robotics control simulators and on a dependency parsing sequential prediction task show that AggreVaTeD can achieve expert-level performance and even super-expert performance when the oracle is sub-optimal, a result rarely achieved by non-interactive IL approaches. The differentiable nature of AggreVaTeD additionally allows us to employ LSTM-based policies to handle partially observable settings (e.g., observe only partial robot state). Empirical results demonstrate that by leveraging an oracle, IL can learn much faster than RL in practice.

In addition to providing a set of practical algorithms, we develop a comprehensive theoretical study of IL on discrete MDPs. We construct an MDP that demonstrates exponentially better sample efficiency for IL than any RL algorithm. For general discrete MDPs, we provide a regret upper bound for AggreVaTeD with EG, which shows IL can learn dramatically faster than RL. We provide a regret lower bound for any IL algorithm, which demonstrates that AggreVaTeD with EG is near-optimal. Our experimental and the theoretical results support the proposition:

Imitation Learning is a more effective strategy than Reinforcement Learning for sequential prediction with near optimal cost-to-go oracles.

Preliminaries

In order to develop algorithms that reason about long-term decision making, it is convenient to cast the problem into the Markov Decision Process (MDP) framework. The MDP framework consists of a set of states, actions (that come from a policy), cost (loss), and a model that transitions states given actions. For robotics control problems, the robot’s configuration is the state, the controls (e.g., joint torques) are the actions, and the cost is related to achieving a task (e.g., distance walked). Though more nuanced, most sequential predictions can be cast into the same framework (Daumé III et al., 2009). The actions are the learner’s (e.g., RNN’s) predictions. The state is then the result of all the predictions made so far (e.g., the dependency tree constructed so far or the words translated so far). The cumulative cost is the performance metric such as (negative) UAS, received at the end (horizon) after the final prediction.

We define a stochastic policy $\pi$ such that for any state $s\in\mathcal{S}$, $\pi(\cdot|s)\in\Delta(A)$, where $\Delta(A)$ is a $A$-dimension simplex, conditioned on state $s$. $\pi(a|s)\in$ outputs the probability of taking action $a$ at state $s$. The distribution of trajectories $\tau=(s_{1},a_{1},\ldots,a_{H-1},s_{H})$ is deterministically dependent on $\pi$ and the MDP, and is defined as

The distribution of the states at time step $t$, induced by running the policy $\pi$ until $t$, is defined $\forall s_{t}$:

Note that the summation above can be replaced by an integral if the state or action space is continuous. The average state distribution $\bar{d}^{\pi}(s)=\sum_{t=1}^{H}d_{t}^{\pi}(s)/H$.

The expected average cost of a policy $\pi$ can be defined with respect to $\rho_{\pi}$ or $\{d_{t}^{\pi}\}$:

We define the state-action value $Q_{t}^{\pi}(s,a)$ (i.e., cost-to-go) for policy $\pi$ at time step $t$ as:

where the expectation is taken over the randomness of the policy $\pi$ and the MDP.

We define $\pi^{*}$ as the expert policy (e.g., human demonstrators, search algorithms equipped with ground-truth) and $Q^{*}_{t}(s,a)$ as the expert’s cost-to-go oracle (note $\pi^{*}$ may not be optimal, i.e., $\pi^{*}\not\in\arg\min_{\pi}\mu(\pi)$). Throughout the paper, we assume $Q_{t}^{*}(s,a)$ is known or can be estimated without bias (e.g., by rolling out $\pi^{*}$: starting from state $s$, applying action $a$, and then following $\pi^{*}$ for $H-t$ steps).

Differentiable Imitation Learning

Policy based imitation learning aims to learn a policy $\hat{\pi}$ that approaches the performance of the expert $\pi^{*}$ in testing time when $\pi^{*}$ is not available anymore. In order to learn rich policies such as with LSTMs or deep networks (Schulman et al., 2015), we derive a policy gradient method for imitation learning and sequential prediction. To do this, we leverage the reduction of IL and sequential prediction to online learning as shown in (Ross & Bagnell, 2014) to learn policies represented by expressive differentiable function approximators.

The fundamental idea in Ross & Bagnell (2014) is to use a no-regret online learner to update policies using the following loss function at each episode $n$:

A simple implementation of AggreVaTe that aggregates the values (as the name suggests) will require an exact solution to a batch optimization procedure in each episode. When $\pi$ is represented by large, non-linear function approximators, the $\arg\min$ procedure generally takes more and more computation time as $n$ increases.

See Appendix A for the derivation of the above equation. With this reformulation, the gradient with respect to $\theta$ is

2 Policy Updates with Natural Gradient Descent

We derive a natural gradient update procedure for imitation learning inspired by the success of natural gradient descent in RL (Kakade, 2002; Bagnell & Schneider, 2003; Schulman et al., 2015). First, we show that Exponential Gradient Descent (EG) can be leveraged to speed up imitation learning in discrete MDPs. Then we extend EG to continuous MDPs, where we show that, with three steps of approximation, EG leads to a natural gradient update procedure.

where $KL(q\|p)$ is the KL-divergence between two probability distributions $q$ and $p$. This leads to the following closed-form update:

2.2 Continuous MDPs

We now consider how to update the parametrized policy $\pi_{\theta}$ for continuous MDPs. Replacing summations by integrals, Eq. 3.2.1 can be written as:

Second, we replace $KL(\pi_{\theta}||\pi_{\theta_{n}})$ by $KL(\pi_{\theta_{n}}||\pi_{\theta})$, which is a local approximation since $KL(q||p)$ and $KL(p||q)$ are equal up to the second order (Kakade & Langford, 2002; Schulman et al., 2015).

Third, we approximate $KL(\pi_{\theta_{n}}||\pi_{\theta})$ by a second-order Taylor expansion around $\theta_{n}$, such that we can approximate the penalization using the Fisher information matrix:

where $\nabla_{\theta}\log(\rho_{\pi_{\tau}}(\tau))$ is the gradient of the log likelihood of the trajectory $\tau$ which can be computed as $\sum_{t=1}^{H}\nabla_{\theta}\log(\pi_{\theta}(a_{t}|s_{t}))$. In the remainder of the paper, we use this Fisher information matrix representation, which yields much faster computation of the descent direction $\delta_{\theta}$, as we will explain in the next section.

Sample-Based Practical Algorithms

for discrete and continuous setting respectively.

When we can compute $V_{t}^{*}(s)$ (e.g., $\min_{a}Q_{t}^{*}(s,a)$), we can replace $Q_{t}^{*}(s_{t}^{i,n},a)$ in Eq. 10 and Eq. 11 by the state-action advantage function $A^{*}_{t}(s_{t}^{i,n},a)=Q^{*}_{t}(s_{t}^{i,n},a)-V_{t}^{*}(s_{t}^{i,n})$, which leads to the following two unbiased and variance-reduced gradient estimations (Greensmith et al., 2004):

where Eq. 12 is for discrete action and Eq. 13 for continuous action .

The Fisher information matrix (Eq. 9) is approximated as:

2 Differentiable Imitation Learning: AggreVaTeD

We present the differentiable imitation learning framework AggreVaTeD, in Alg. 1. At every iteration $n$, the roll-in policy $\hat{\pi}_{n}$ is a mix of the expert policy $\pi^{*}$ and the current policy $\pi_{\theta_{n}}$, with mixing rate $\alpha$ ($\alpha_{n}\to 0,n\to\infty$): at every step, with probability $\alpha$, $\hat{\pi}_{n}$ picks $\pi^{*}$ and else $\pi_{\theta_{n}}$. This mixing strategy with decay rate was first introduced in (Ross et al., 2011) for IL, and later on was used in sequence prediction (Bengio et al., 2015). In Line 6 one can choose Eq. 10 or the corresponding variance reduced estimation Eq. 12 (Eq. 11 and Eq. 13 for continuous actions) to perform regular gradient descent, and choose CG to perform natural gradient descent. Compared with previous well-known IL and sequential prediction algorithms (Ross et al., 2011; Ross & Bagnell, 2014; Chang et al., 2015b), AggreVaTeD is extremely simple: we do not need to perform any Data Aggregation (i.e., we do not need to store all $\{\tau_{i}\}_{i}$ from all previous iterations); the computational complexity of each episode scales as $O(d)$.

Quantify the Gap: An Analysis of IL vs RL

How much faster can IL learn a good policy than RL? In this section we quantify the gap on discrete MDPs when IL can (1) query for an optimal $Q^{*}$ or (2) query for a noisy but unbiased estimate of $Q^{*}$. To measure the speed of learning, we look at the cumulative regret of the entire learning process, defined as $R_{N}=\sum_{n=1}^{N}(\mu(\pi_{n})-\mu(\pi^{*}))$. A smaller regret rate indicates faster learning. Throughout this section, we assume the expert $\pi^{*}$ is optimal. We consider finite-horizon, episodic IL and RL algorithms.

We consider an MDP $\mathcal{M}$ shown in Fig. 1 which is a depth-K binary tree-structure with $S=2^{K}-1$ states and two actions ${a_{l},a_{r}}$: go-left and go-right. The transition is deterministic and the initial state $s_{0}$ (root) is fixed. The cost for each non-leaf state is zero; the cost for each leaf is i.i.d sampled from a given distribution (possibly different distributions per leaf). Below we show that for $\mathcal{M}$, IL can be exponentially more sample efficient than RL.

For $\mathcal{M}$, the regret $R_{N}$ of any finite-horizon, episodic RL algorithm is at least:

The expectation is with respect to random generation of cost and internal randomness of the algorithm. However, for the same MDP $\mathcal{M}$, with the access to $Q^{*}$, we show IL can learn exponentially faster:

For the MDP ${\mathcal{M}}$, there exists a policy class such that AggreVaTe with FTL that can achieve the following regret bound:

Fig. 1 illustrates the intuition behind the theorem. Assume during the first episode, the initial policy $\pi_{1}$ picks the rightmost trajectory (bold black) to explore and the algorithm queries from oracle that for $s_{0}$ we have $Q^{*}(s_{0},a_{l})<Q^{*}(s_{0},a_{r})$, it immediately learns that the optimal policy will go left (black arrow) at $s_{0}$. Hence the algorithm does not have to explore the right sub-tree (dotted circle).

Next we consider a more difficult setting where one can only query for a noisy but unbiased estimate of $Q^{*}$ (e.g., by rolling out $\pi^{*}$ finite number of times). The above halving argument will not apply since deterministically eliminating nodes based on noisy estimates might permanently remove good trajectories. However, IL can still achieve a poly-log regret with respect to $S$, even in the noisy setting:

With only access to unbiased estimate of $Q^{*}$, for the MDP ${\mathcal{M}}$, AggreVaTeD with EG that can achieve the following regret with probability at least $1-\delta$:

The detailed proofs of the above three theorems can be found in Appendix D,E,F respectively. In summary, for MDP ${\mathcal{M}}$, IL is is exponentially faster than RL.

2 Polynomial Gap and Near-Optimality

We next quantify the gap in general discrete MDPs and also show that AggreVaTeD is near-optimal. We consider the harder case where we can only access an unbiased estimate of $Q^{*}_{t}$, for any $t$ and state-action pair. The policy $\pi$ is represented as a set of probability vectors $\pi^{s,t}\in\Delta(A)$, for all $s\in\mathcal{S}$ and $t\in[H]$: $\pi=\{\pi^{s,t}\}_{s\in\mathcal{S},t\in[H]}$.

With access to unbiased estimates of $Q^{*}_{t}$, AggreVaTeD with EG achieves the regret upper bound:

We also provide a lower bound on $R_{N}$ for $H=1$ case which shows the dependencies on $N,A,S$ are tight:

There exists an MDP (H=1), with only access to unbiased estimate of $Q^{*}$, any finite-horizon episodic imitation learning algorithm must have:

The proofs of the above two theorems regarding general MDPs can be found at Appendix G,H. In summary for discrete MDPs, one can expect at least a polynomial gap and a possible exponential gap between IL and RL.

Experiments

We evaluate our algorithms on robotics simulations from OpenAI Gym (Brockman et al., 2016) and on Handwritten Algebra Dependency Parsing (Duyck & Gordon, 2015). We report reward instead of cost, since OpenAI Gym by default uses reward and dependency parsing aims to maximize UAS score. As our approach only promises there exists a policy among all of the learned polices that can perform as well as the expert, we report the performance of the best policy so far: $\max\{\mu(\pi_{1}),...,\mu(\pi_{i})\}$. For regular gradient descent, we use ADAM (Kingma & Ba, 2014) which is a first-order no-regret algorithm, and for natural gradient, we use CG to compute the descent direction. For RL we use REINFORCE (Williams, 1992) and Truncated Natural Policy Gradient (TNPG) (Duan et al., 2016).

We consider CartPole Balancing, Acrobot Swing-up, Hopper and Walker. For generating an expert, similar to previous work (Ho & Ermon, 2016), we used a Deep Q-Network (DQN) to generate $Q^{*}$ for CartPole and Acrobot (e.g., to simulate the settings where $Q^{*}$ is available), while using the publicly available TRPO implementation to generate $\pi^{*}$ for Hopper and Walker to simulate the settings where one has to estimate $Q^{*}$ by Monte-Carlo roll outs $\pi^{*}$.

We use a one-layer (16 hidden units) neural network with ReLu activation functions to represent the policy $\pi$ for the Cart-pole and Acrobot benchmarks. The value function $Q^{*}$ is obtained from the DQN (Mnih et al., 2015) and represented by a multi-layer fully connected neural network. The policy $\pi_{\theta_{1}}$ is initialized with common ReLu neural network initialization techniques. For the scheduling rate $\{\alpha_{i}\}$, we set all $\alpha_{i}=0$: namely we did not roll-in using the expert’s actions during training. We set the number of roll outs $K=50$ and horizon $H=500$ for CartPole and $H=200$ for Acrobot.

Fig. 4(a) and 4(b) shows the performance averaged over 10 random trials of AggreVaTeD with regular gradient descent and natural gradient descent. Note that AggreVaTeD outperforms the experts’ performance significantly: Natural gradient surpasses the expert by 5.8$\%$ in Acrobot and $\mathbf{25\%}$ in Cart-pole. Also, for Acrobot swing-up, at horizon $H=200$, with high probability a randomly initialized neural network policy won’t be able to collect any reward signals. Hence the improvement rates of REINFORCE and TNPG are slow. In fact, we observed that for a short horizon such as $H=200$, REINFORCE and Truncated Natural Gradient often even fail to improve the policy at all (failed 6 times among 10 trials). On the contrary, AggreVaTeD does not suffer from the delayed reward signal issue, since the expert will collect reward signals much faster than a randomly initialized policy.

Fig. 2(c) shows the performance of AggreVaTeD with an LSTM policy (32 hidden states) in a partially observed setting where the expert has access to full states but the learner has access to partial observations (link positions). RL algorithms did not achieve any improvement while AggreVaTeD still achieved 92$\%$ of expert’s performance.

We test our approaches on two robotics simulators with continuous actions: (1) the 2-d Walker and (2) the Hopper from the MuJoCo physics simulator. Following the neural network settings described in Schulman et al. (2015), the expert policy $\pi^{*}$ is obtained from TRPO with one hidden layer (64 hidden states), which is the same structure that we use to represent our policies $\pi_{\theta}$. We set $K=50$ and $H=100$. We initialize $\pi_{\theta_{1}}$ by collecting $K$ expert demonstrations and then maximize the likelihood of these demonstrations (i.e., supervised learning). We use Eq. 11 instead of the variance reduced equation here since we need to use MC roll-outs to estimate $V^{*}$ (we simply use one roll-out to estimate $Q^{*}$).

Fig. 2(d) and 2(e) show the performance averaged over 5 random trials. Note that AggreVaTeD outperforms the expert in the Walker by 5.4$\%$ while achieving 97$\%$ of the expert’s performance in the Hopper problem. After 100 iterations, we see that by leveraging the help from experts, AggreVaTeD can achieve much faster improvement rate than the corresponding RL algorithms.

2 Dependency Parsing on Handwritten Algebra

We consider a sequential prediction problem: transition-based dependency parsing for handwritten algebra with raw image data (Duyck & Gordon, 2015). The parsing task for algebra is similar to the classic dependency parsing for natural language (Chang et al., 2015a) where the problem is modelled in the IL setting and the state-of-the-art is achieved by AggreVaTe with FTRL (using Data Aggregation). The additional challenge here is that the inputs are handwritten algebra symbols in raw images. We directly learn to predict parse trees from low level image features (Histogram of Gradient features (HoG)). During training, the expert is constructed using the ground-truth dependencies in training data. The full state $s$ during parsing consists of three data structures: Stack, Buffer and Arcs, which store raw images of the algebraic symbols. Since the sizes of stack, buffer and arcs change during parsing, a common approach is to featurize the state $s$ by taking the features of the latest three symbols from stack, buffer and arcs (e.g., (Chang et al., 2015a)). Hence the problem falls into the partially observable setting, where the feature $o$ is extracted from state $s$ and only contains partial information about $s$. The dataset consists of 400 sets of handwritten algebra equations. We use 80$\%$ for training, 10$\%$ for validation, and 10$\%$ for testing. We include an example of handwritten algebra equations and its dependency tree in Appendix I. Note that different from robotics simulators where at every episode one can get fresh data from the simulators, the dataset is fixed and sample efficiency is critical.

The RNN policy follows the design from (Sutskever et al., 2014). It consists of two LSTMs. Given a sequence of algebra symbols $\tau$, the first LSTM processes one symbol at a time and at the end outputs its hidden states and memory (i.e., a summary of $\tau$). The second LSTM initializes its own hidden states and memory using the outputs of the first LSTM. At every parsing step $t$, the second LSTM takes the current partial observation $o_{t}$ ($o_{t}$ consists of features of the most recent item from stack, buffer and arcs) as input, and uses its internal hidden state and memory to compute the action distribution $\pi(\cdot|o_{1},...,o_{t},\tau)$ conditioned on history. We also tested reactive policies constructed as fully connected ReLu neural networks (NN) (one-layer with 1000 hidden states) that directly maps from observation $o_{t}$ to action $a$, where $o_{t}$ uses the most three recent items. We use variance reduced gradient estimations, which give better performance in practice. The performance is summarised in Table 1. Due to the partial observability of the problem, AggreVaTeD with a LSTM policy achieves significantly better UAS scores compared to the NN reactive policy and DAgger with a Kernelized SVM (Duyck & Gordon, 2015). Also AggreVaTeD with a LSTM policy achieves 97$\%$ of optimal expert’s performance. Fig. 3 shows the improvement rate of regular gradient and natural gradient on both validation set and test set. Overall we observe that both methods have similar performance. Natural gradient achieves a better UAS score in validation and converges slightly faster on the test set but also achieves a lower UAS score on test set.

Conclusion

We introduced AggreVaTeD, a differentiable imitation learning algorithm which trains neural network policies for sequential prediction tasks such as continuous robot control and dependency parsing on raw image data. We showed that in theory and in practice IL can learn much faster than RL with access to optimal cost-to-go oracles. The IL learned policies were able to achieve expert and sometimes super-expert levels of performance in both fully observable and partially observable settings. The theoretical and experimental results suggest that IL is significantly more effective than RL for sequential prediction with near optimal cost-to-go oracles.

References

Appendix A Derivation of Eq. 3.1

Starting from Eq. 1 with parametrized policy $\pi_{\theta}$, we have:

Appendix B Derivation of Exponential Gradient Update in Discrete MDP

We show the detailed derivation of Eq. 7 for AggreVaTeD with EG in discrete MDP. Recall that with $KL$-divergence as the penalization, one update the policy in each episode as:

Note that in the above equation, for a particular state $s$, optimizing $\pi^{s}$ is in fact independent of $\pi^{s^{\prime}},\forall s^{\prime}\neq s$. Hence the optimal sequence $\{\pi^{s}\}_{s\in\mathcal{S}}$ can be achieved by optimizing $\pi^{s}$ independently for each $s\in\mathcal{S}$. For $\pi^{s}$, we have the following update rule:

Take the derivative with respect to $\pi^{s}[j]$, and set it to zero, we get:

Since $\pi^{s}\in\Delta(A)$, after normalization, we get:

Appendix C Lemmas

Before proving the theorems, we first present the Performance Difference Lemma (Kakade & Langford, 2002; Ross & Bagnell, 2014) which will be used later:

For any two policies $\pi_{1}$ and $\pi_{2}$, we have:

We refer readers to (Ross & Bagnell, 2014) for the detailed proof of the above lemma.

The sequence of decisions $\{w_{n}\}$ computed by running Exponential Gradient descent with step size $\mu$ on the loss functions $\{w\cdot y_{n}\}$ has the following regret bound:

We refer readers to (Shalev-Shwartz et al., 2012) for detailed proof.

Appendix D Proof of Theorem 5.1

Consider a MAB with $2^{K}$ arms. To construct a MDP from a MAP, we construct a $K+1$-depth binary-tree structure MDP with $2^{K+1}-1$ nodes. We set each node in the binary tree as a state in the MDP. The number of actions of the MDP is two, which corresponds to go left or right at a node in the binary tree. We associate each leaf nodes with arms in the original MAB: the cost of the $i$’th leaf node is sampled from the cost distribution for the $i$’th arm, while the non-leaf nodes have cost always equal to zero. The initial distribution $\rho_{0}$ concentrates on the root of the binary tree. Note that there are total $2^{K}$ trajectories from the root to leafs, and we denote them as $\tau_{1},...\tau_{2^{K}}$. We consider finite horizon ($H=K+1$) episodic RL algorithms that outputs $\pi_{1},\pi_{2},...,\pi_{N}$ at $N$ episodes, where $\pi_{n}$ is any deterministic policy that maps a node to actions left or right. Any RL algorithm must have the following regret lower bound:

where the expectation is taken with respect to the possible randomness of the RL algorithms. Note that any deterministic policy $\pi$ identifies a trajectory in the binary tree when rolling in from the root. The optimal policy $\pi^{*}$ simply corresponds to the trajectory that leads to the leaf with the mininum expected cost. Note that each trajectory is associated with an arm from the original MAB, and the expected total cost of a trajectory corresponds to the expected cost of the associated arm. Hence if there exists an RL algorithm that achieves regret $O(\sqrt{SN})$, then we can solve the original MAB problem by simply running the RL algorithm on the constructed MDP. Since the lower bound for MAB is $\Omega(\sqrt{SN})$, this concludes that Eq. 28 holds. ∎

Appendix E Proof of Theorem 5.2

For notation simplicity we denote $a_{l}$ as the go-left action while $a_{r}$ is the go-right action. Without loss of generality, we assume that the leftmost trajectory has the lowest total cost (e.g., $s_{3}$ in Fig. 1 has the lowest average cost). We consider the deterministic policy class $\Pi$ that contains all policy $\pi:\mathcal{S}\to\{a_{l},a_{r}\}$. Since there are $S$ states and 2 actions, the total number of policies in the policy class is $2^{S}$. To prove the upper bound $R_{N}\leq O(\log(S))$, we claim that for any $e\leq K$, at the end of episode $e$, AggreVaTe with FTL identifies the $e$’th state on the best trajectory, i,e, the leftmost trajectory $s_{0},s_{1},s_{3},...,s_{(2^{K-1}-1)}$. We can prove the claim by induction.

At episode $e=1$, based on the initial policy, AggreVaTe picks a trajectory $\tau_{1}$ to explore. AggreVaTe with FTL collects the states $s$ at $\tau_{1}$ and their associated cost-to-go vectors $[Q^{*}(s,a_{l}),Q^{*}(s,a_{r})]$. Let us denote $D_{1}$ as the dataset that contains the state,cost-to-go pairs: $D_{1}=\{(s,[Q^{*}(s,a_{l}),Q^{*}(s,a_{l})])\}$, for $s\in\tau_{1}$. Since $s_{0}$ is visited, the state-cost pair $(s_{0},[Q^{*}(s_{0},a_{l}),Q^{*}(s_{0},a_{r})])$ must be in $D_{1}$. To update policy from $\pi_{1}$ to $\pi_{2}$, AggreVaTe with FTL runs cost-sensitive classification $D_{1}$ as:

where $s_{k}$ stands for the $k$’th data point collected at dataset $D_{1}$. Due to the construction of policy class $\Pi$, we see that $\pi_{2}$ must picks action $a_{l}$ at state $s_{0}$ since $Q(s_{0},a_{l})<Q(s_{0},a_{r})$. Hence at the end of the episode $e=1$, $\pi_{2}$ identifies $s_{1}$ (i.e., running $\pi_{2}$ from root $s_{0}$ leads to $s_{1}$), which is on the optimal trajectory.

Now assume that at the end of episode $n-1$, the newly updated policy $\pi_{n}$ identifies the state $s_{(2^{n-1}-1)}$: namely at the beginning of episode $n$, if we roll-in $\pi_{n}$, the algorithm will keep traverse along the leftmost trajectory till at least state $s_{(2^{n-1}-1)}$. At episode $n$, let $D_{n}$ as the dataset contains all data points from $D_{n-1}$ and the new collected state, cost-to-go pairs from $\tau_{n}$: $D_{n}=D_{n-1}\cup\{(s,[Q^{*}(s,a_{l}),Q^{*}(s,a_{r})])\}$, for all $s\in\tau_{n}$. Now if we compute policy $\pi_{n+1}$ using cost-sensitive classification (Eq. 29) over $D_{n}$, we must learn a policy $\pi_{n+1}$ that identifies action $a_{l}$ at state $s_{(2^{j}-1)}$, since $Q^{e}(s_{(2^{j}-1)},a_{l})<Q^{*}(s_{(2^{j}-1)},a_{r})$, and $s_{(2^{j}-1)}$ is included in $D_{n}$, for $j=1,...,n-1$. Hence at the end of episode $n$, we identify a policy $\pi_{n+1}$ such that if we roll in policy $\pi_{n+1}$ from $s_{0}$, we will traverse along the left most trajectory till we reach $s_{(2^{n}-1)}$.

Hence by the induction hypothesis, at the end of episode $K-1$, $\pi_{K}$ will reach state $s_{(2^{K-1}-1)}$, the end of the best trajectory.

Appendix F Proof of Theorem 5.3

Since in Theorem 5.3 we assume that we only have access to the noisy, but unbiased estimate of $Q^{*}$, the problem becomes more difficult since unlike in the proof of Theorem 5.2, we cannot simply eliminate states completely since the cost-to-go of the states queried from expert is noisy and completely eliminate nodes will potentially result elimination of low cost trajectories. Hence here we consider a different policy representation. We define $2^{K}$ deterministic base policies $\pi^{1},...,\pi^{2^{K}}$, such that rolling in policy $\pi^{i}$ at state $s_{0}$ will traverse along the trajectory ending at the $i$’th leaf. We define the policy class $\Pi$ as the convex hull of the base policies $\Pi=\{\pi:\sum_{i=1}^{2^{K}}w_{i}\pi^{i},\sum_{i}^{2^{K}}w_{i}=1,w_{i}\geq 0,\forall i\}$. Namely each $\pi\in\Pi$ is a stochastic policy: when rolling in, with probability $w_{i}$, $\pi$ execute the $i$’th base policy $\pi^{i}$ from $s_{0}$. Below we prove that AggreVaTeD with Exponential Gradient Descent achieves the regret bound $O(\sqrt{\ln(S)N})$.

Note that $S=2^{K+1}-1$. The above inequality holds for any $w^{*}\in\Delta(2^{K})$, including the $w^{e}$ that corresponds to the expert (i.e., $w^{e}=1,w^{e}[i]=0,i\neq 1$ as we assumed without loss of generality the left most trajectory is the optimal trajectory).

and with probability at least $1-\delta/2$:

Combine the above inequality using union bound, we get with probability at least $1-\delta$:

Now let us apply the Performance Difference Lemma (Lemma C.1), we get with probability at least $1-\delta$:

Appendix G Proof of Theorem 5.4

The proof of theorem 5.4 is similar to the one for theorem 5.3. Hence we simply consider the infinitely many roll-ins and exact query of $Q^{*}$ case. The finite number roll-in and noisy query of $Q^{*}$ case can be handled by using the martingale difference sequence argument as shown in the proof of theorem 5.3.

where as we defined before $Q_{t}^{*}(s)$ stands for the cost-to-go vector $Q_{t}^{*}(s)[j]=Q_{t}^{*}(s,a_{j})$, for the $j$’th action in $\mathcal{A}$, and $q_{n}^{s,t}=\frac{d_{t}^{\pi_{n}}(s)}{H}Q_{t}^{*}(s)$.

Note that we can upper bound $(q_{n}^{s,t}[j])^{2}$ as:

if we set $\mu=\sqrt{(Q^{*}_{\max})^{2}NS\ln(A)/(2H^{2})}$.

Now let us apply the performance difference lemma (Lemma C.1), we get:

Appendix H Proof of Theorem 5.5

Note that for each state $s_{i}$, at the rounds from $\mathcal{N}_{i}$, we can think of the algorithm running any possible online linear regression algorithm to compute the sequence of policies $\pi_{j}^{s_{i}},\forall j\in\mathcal{N}_{i}$ for state $s_{i}$. Note that from classic online linear regression analysis, we can show that for state $s_{i}$ there exists a distribution $P_{s_{i}}$ such that for any online algorithm:

for some non-zero positive constant $c$. Substitute the above inequality into Eq. 44, we have:

Let $\epsilon=1/(2S)$, and substitute it back to the above inequality, we get:

Substitute this result back to Eq. 47 and use the fact from Eq. H, we get:

Appendix I Details of Dependency Parsing for Handwritten Algebra

In Fig. 4, we show an example of set of handwritten algebra equations and its dependency tree from a arc-hybird sequence $slssslssrrllslsslssrrslssrlssrrslssrr$. The preprocess step cropped individual symbols one by one from left to right and from the top equation to the bottom one, centered them, scaled symbols to 40 by 40 images, and finally formed them as a sequence of images.

Since in the most common dependency parsing setting, there is no immediate reward at every parsing step, the reward-to-go $Q^{*}(s,a)$ is computed by using UAS as follows: start from $s$ and apply action $a$, then use expert $\pi^{*}$ to roll out til the end of the parsing process; $Q^{*}(s,a)$ is the UAS score of the final configuration. Hence AggreVaTeD can be considered as directly maximizing the UAS score, while previous approaches such as DAgger or SMILe (Ross et al., 2011) tries to mimic expert’s actions and hence are not directly optimizing the final objective.