Dataset Aggregation (DAgger)

Let a finite-horizon imitation-learning problem have the finite MDP, initial state distribution, positive integer horizon $T$, deterministic expert ${\pi }^{\ast }$, learner class $\{{\pi }_{\theta }:\theta \in K\}$, and expert surrogate loss $\mathrm{\ell }(s,\theta )$ defined previously. Let $N\ge 1$ and $m\ge 1$ be integers giving the number of training rounds and trajectories per round, let ${\beta }_1,\dots ,{\beta }_N\in [0,1]$ be expert-use probabilities, supply an initial parameter ${\theta }_1\in K$, and supply a deterministic selector for attained minimizers of the cumulative losses. Require that each cumulative training-loss function below attains a minimum on $K$; when the minimizer is unique the selector returns it.

Initialize the aggregated training dataset as the empty multiset ${\mathcal{D}}_0=\mathrm{\varnothing }$.

For each round $i=1,\dots ,N$:

1. Set ${\widehat{\pi }}_i={\pi }_{{\theta }_i}$. For the rollout policy, at each decision time of every trajectory, independently draw an expert-use coin with success probability ${\beta }_i$. At current state $s$, if the coin succeeds, execute ${\pi }^{\ast }(s)$; otherwise sample an action from ${\widehat{\pi }}_i(\cdot \mid s)$ and execute it. This per-decision stochastic policy is ${\pi }_i={\beta }_i{\pi }^{\ast }+(1-{\beta }_i){\widehat{\pi }}_i$.

2. Run $m$ trajectories of length $T$ from the specified initial distribution using ${\pi }_i$. At every visited state $S_{ijt}$, for $1\le j\le m$ and $0\le t<T$, query and record the expert label ${\pi }^{\ast }(S_{ijt})$. Append these labeled pairs to ${\mathcal{D}}_{i-1}$, with multiplicity, to form ${\mathcal{D}}_i$. The expert label is recorded for training and is not executed unless the mixture in step 1 selected the expert.

3. Define the empirical round loss on every candidate parameter by

   ${\widehat{L}}_i(\theta )=\frac{1}{mT}{\sum }_{j=1}^m{\sum }_{t=0}^{T-1}\mathrm{\ell }(S_{ijt},\theta )\mathrm{.}$

4. Update by Follow-the-Leader on the cumulative empirical loss: set ${\theta }_{i+1}$ to the supplied selector's choice from $\arg {\min }_{\theta \in K}{\sum }_{r=1}^i{\widehat{L}}_r(\theta )$.

The finite-sample output is the sequence ${\widehat{\pi }}_1,\dots ,{\widehat{\pi }}_N$ and the aggregated labeled multiset ${\mathcal{D}}_N$. The population-loss idealization replaces each empirical ${\widehat{L}}_i$ by $L_i(\theta )={\sum }_s{d}_{{\pi }_i}(s)\mathrm{\ell }(s,\theta )$; it is used only for the infinite-sample theorem. The procedure requires an interactive expert capable of labeling learner-visited states.

Finite-horizon imitation learning and expert-surrogate loss: specifies the finite MDP, normalized state occupancy, deterministic expert, learner class, task/surrogate losses, and DAgger round losses.

Online decision protocol: the learner selects its current policy from earlier feedback before collecting current-round trajectories and labels.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Algorithm 3.1, §3, PDF p. 3.

Bagnell, Boots, and Choudhury, Modern Adaptive Control and Reinforcement Learning, Chapter 6: PDF pp. 4–6 / printed pp. 57–59.

Duisterhof, Truong, and Agrawal, Algorithmic Foundations of Interactive Learning, Lecture 9: PDF pp. 51–53 / note pages 47–48.