Imitation learning and DAgger

Let $d,N\ge 1$ be integers, let $K\subseteq {\mathbb{R}}^d$ be nonempty and convex, and define $\mathrm{\parallel }x-y{\mathrm{\parallel }}_2=({\sum }_{r=1}^d(x_r-y_r{)}^2{)}^{1\mathrm{/}2}$. Let $G\ge 0$ and $\mu >0$. For each $i=1,\dots ,N$, let $L_i:K\to [0,1]$ be $G$-Lipschitz, meaning $\mathrm{\mid }{L}_i(x)-L_i(y)\mathrm{\mid }\le G\mathrm{\parallel }x-y{\mathrm{\parallel }}_2$, and $\mu$-strongly convex, meaning

$L_i((1-\lambda )x+\lambda y)\le (1-\lambda )L_i(x)+\lambda L_i(y)-\frac{\mu }{2}\lambda (1-\lambda )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2$

for all $x,y\in K$ and $\lambda \in [0,1]$. For $n=1,\dots ,N$, assume $F_n:={\sum }_{i=1}^n{L}_i$ attains a minimum on $K$. Let ${\theta }_1\in K$ and, for $n=1,\dots ,N$, let ${\theta }_{n+1}$ be the unique minimizer of $F_n$. Define $H_0=0$ and $H_n={\sum }_{j=1}^{n}1\mathrm{/}j$ for $n\ge 1$. Then

${\sum }_{i=1}^N{L}_i({\theta }_i)-{\min }_{\theta \in K}{\sum }_{i=1}^N{L}_i(\theta )\le 1+\frac{4G^2}{\mu }{H}_{N-1}\mathrm{.}$

The minimizers are unique because $F_n$ is $n\mu$-strongly convex. The first policy ${\theta }_1$ may be any supplied point of $K$.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: §4.1–4.2, PDF pp. 3–4, for the FTL/strongly-convex no-regret context.

Let a finite Markov decision process have a nonempty finite state set $S$ and finite nonempty action sets $A(s)$, with state transition probabilities $P(s^{\mathrm{\prime }}\mid s,a)$ obtained by summing its joint reward-transition law over rewards. Let $T\ge 1$ be an integer, let ${\mu }_0:S\to [0,1]$ satisfy ${\sum }_{s\in S}{\mu }_0(s)=1$, and let $\pi (a\mid s)$ be a stationary Markov policy. Define recursively

${\mu }_{t+1}(s^{\mathrm{\prime }})={\sum }_{s\in S}{\sum }_{a\in A(s)}{\mu }_t(s)\pi (a\mid s)P(s^{\mathrm{\prime }}\mid s,a),0\le t<T\mathrm{.}$

Then each ${\mu }_t$ is a probability vector on $S$, and the finite-horizon average occupancy

$d_{\pi }(s)=\frac{1}{T}{\sum }_{t=0}^{T-1}{\mu }_t(s)$

is also a probability vector. This construction uses only finite sums and does not require an infinite-path probability extension.

Finite Markov decision process with joint reward-transition law: the finite state/action sets, row-normalized joint reward-transition law, derived $P(s^{\mathrm{\prime }}\mid s,a)$, and stationary Markov policy.

The sum ${\sum }_{i\in S}{a}_i$ over a finite index set, and its product form: finite-index sums are well-defined and independent of enumeration.

Laws of finite sums and finite products: finite sums preserve nonnegativity, add termwise, and commute with scalar multiplication.

${\sum }_{i\in S}{\sum }_{j\in T}{a}_{ij}={\sum }_{(i,j)\in S\times T}{a}_{ij}={\sum }_{j\in T}{\sum }_{i\in S}{a}_{ij}$ for finite index sets $S$ and $T$: finite sums over two finite index sets may be interchanged.

The principle of mathematical induction: a property proved at $0$ and preserved by successors holds for every natural index.

Sutton and Barto, Reinforcement Learning: An Introduction: §3.6, printed pp. 67–69.

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

Fix a finite Markov decision process with nonempty finite state set $S$ and finite nonempty action set $A(s)$ at each state, a positive integer horizon $T$, and an initial probability vector ${\mu }_0$ on $S$. A policy is a stationary Markov policy $\pi (a\mid s)$; a deterministic expert is a function ${\pi }^{\ast }:S\to {\bigcup }_{s\in S}A(s)$ with ${\pi }^{\ast }(s)\in A(s)$. For a policy $\pi$, let ${\mu }_t^{\pi }$ and $d_{\pi }$ be the finite-horizon state and average-occupancy probability vectors defined by the finite recursion in the preceding lemma.

Let $c_t(s,a)\in [0,1]$ be the task cost at time $t$ for $0\le t<T$. Define the total expected task cost by

$J(\pi )={\sum }_{t=0}^{T-1}{\sum }_{s\in S}{\mu }_t^{\pi }(s){\sum }_{a\in A(s)}\pi (a\mid s)c_t(s,a)\mathrm{.}$

Define the expert cost-to-go recursively by $V_T^{\ast }(s)=0$ and, for $0\le t<T$,

$Q_t^{\ast }(s,a)=c_t(s,a)+{\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V_{t+1}^{\ast }(s^{\mathrm{\prime }}),V_t^{\ast }(s)=Q_t^{\ast }(s,{\pi }^{\ast }(s))\mathrm{.}$

For a learner policy ${\pi }_{\theta }$ indexed by a parameter $\theta$ in a nonempty set $K$, define its expert-action disagreement probability at $s$ by $e(s,\theta )={\sum }_{a\in A(s):a\mathrm{\ne }{\pi }^{\ast }(s)}{\pi }_{\theta }(a\mid s)$. An expert surrogate loss is a function $\mathrm{\ell }:S\times K\to [0,1]$ satisfying $\mathrm{\ell }(s,\theta )\ge e(s,\theta )$ for every $s\in S$ and $\theta \in K$. The average surrogate loss under a policy's own state occupancy is ${\mathbb{E}}_{s\sim d_{{\pi }_{\theta }}}[\mathrm{\ell }(s,\theta )]={\sum }_s{d}_{{\pi }_{\theta }}(s)\mathrm{\ell }(s,\theta )$.

Behavior cloning fits a learner policy using expert labels on states sampled from $d_{{\pi }^{\ast }}$. DAgger (Dataset Aggregation) is the interactive alternative: at iteration $i$, it rolls out a mixture ${\pi }_i={\beta }_i{\pi }^{\ast }+(1-{\beta }_i){\widehat{\pi }}_i$, where ${\widehat{\pi }}_i={\pi }_{{\theta }_i}$ is the current learner with parameter ${\theta }_i\in K$ and ${\beta }_i\in [0,1]$ is the expert-use probability at each decision, queries the expert on the visited states, aggregates those labeled states with prior data, and updates the learner. For a positive integer $N$ of iterations, in the infinite-sample analysis define $L_i(\theta )={\sum }_s{d}_{{\pi }_i}(s)\mathrm{\ell }(s,\theta )$. When the minimum is attained, define ${ϵ}_N={\min }_{\theta \in K}{N}^{-1}{\sum }_{i=1}^N{L}_i(\theta )$ and the learner's average regret ${\gamma }_N=N^{-1}{\sum }_{i=1}^N{L}_i({\theta }_i)-{ϵ}_N$. Fixed demonstrations do not in general provide expert labels for every learner-visited state; if they cover those states, their labels can be reused without new expert interaction.

Finite Markov decision process with joint reward-transition law: the finite state/action sets, joint reward-transition masses, derived state transition probabilities, and stationary Markov policies.

Finite-horizon MDP policy occupancy is a probability distribution: finite recursion gives probability vectors ${\mu }_t^{\pi }$ and their normalized average occupancy $d_{\pi }$ without an infinite-path construction.

Online decision protocol: the learner chooses from past history before receiving current-round feedback.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: §2, PDF pp. 1–2.

Bagnell, Boots, and Choudhury, Modern Adaptive Control and Reinforcement Learning, Chapter 6: PDF pp. 1–5 / printed pp. 53–58.

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

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.

Let a finite-horizon MDP have positive integer horizon $T$, and let ${\pi }^{\ast }$ and $\widehat{\pi }$ be stationary Markov policies. For a stationary policy $\pi$, define its state transition matrix by $P_{\pi }(s,s^{\mathrm{\prime }})={\sum }_{a\in A(s)}\pi (a\mid s)P(s^{\mathrm{\prime }}\mid s,a)$; for a state vector $\mu$, define $(\mu P_{\pi })(s^{\mathrm{\prime }})={\sum }_{s\in S}\mu (s)P_{\pi }(s,s^{\mathrm{\prime }})$. Fix $\beta \in [0,1]$ and let ${\pi }_{\beta }(a\mid s)=\beta {\pi }^{\ast }(a\mid s)+(1-\beta )\widehat{\pi }(a\mid s)$, which is the per-decision expert/learner mixture. For every function $g:S\to [0,1]$, its finite-horizon average occupancies satisfy

$\mid {\sum }_{s\in S}{d}_{{\pi }_{\beta }}(s)g(s)-{\sum }_{s\in S}{d}_{\widehat{\pi }}(s)g(s)\mid \le 1-(1-\beta {)}^T\le \min \{1,T\beta \}\mathrm{.}$

Here $d_{\pi }=T^{-1}{\sum }_{t=0}^{T-1}{\mu }_t^{\pi }$ is the normalized average of the state marginals from the common initial distribution.

Finite-horizon imitation learning and expert-surrogate loss: defines the finite-horizon state recursion, normalized average occupancy, and the DAgger per-decision policy mixture.

The principle of mathematical induction: finite recursion and Bernoulli inequality use natural-number induction.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Lemma 4.1 and proof, §4.2, PDF p. 4.

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

Let a finite-horizon MDP, horizon $T\ge 1$, initial distribution, deterministic expert ${\pi }^{\ast }$, learner policy ${\pi }_{\theta }$, task cost $J$, expert cost-to-go $Q_t^{\ast }$, expert value $V_t^{\ast }(s)=Q_t^{\ast }(s,{\pi }^{\ast }(s))$, occupancy $d_{{\pi }_{\theta }}$, and surrogate $\mathrm{\ell }(s,\theta )$ be as defined previously. Suppose $u\ge 0$ and

$Q_t^{\ast }(s,a)-V_t^{\ast }(s)\le u$

for every time $0\le t<T$, state $s\in S$, and admissible action $a\in A(s)$, and suppose $\mathrm{\ell }(s,\theta )\ge {\sum }_{a\mathrm{\ne }{\pi }^{\ast }(s)}{\pi }_{\theta }(a\mid s)$ for every state. Then

$J({\pi }_{\theta })-J({\pi }^{\ast })\le uT{\sum }_{s\in S}{d}_{{\pi }_{\theta }}(s)\mathrm{\ell }(s,\theta )\mathrm{.}$

The one-step cost-to-go bound is required at all states and times, including states not reached by the expert.

Finite-horizon imitation learning and expert-surrogate loss: defines finite-horizon task cost, expert cost-to-go recursion, normalized state occupancy, and the surrogate's expert-action-disagreement domination condition.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Theorem 2.2 and its complete hybrid-policy proof, §2.2, PDF pp. 2–3.

Duisterhof, Truong, and Agrawal, Algorithmic Foundations of Interactive Learning, Lecture 9: equations (9.72)–(9.74), PDF p. 54 / note page 48; used for terminology only.

Consider the finite-horizon imitation-learning setting with deterministic expert ${\pi }^{\ast }$, positive integer horizon $T$, and expert surrogate $\mathrm{\ell }(s,\theta )\in [0,1]$ defined previously. Let $d\ge 1$ be an integer and let $K\subseteq {\mathbb{R}}^d$ be nonempty and convex, with $\mathrm{\parallel }x-y{\mathrm{\parallel }}_2=({\sum }_{r=1}^d(x_r-y_r{)}^2{)}^{1\mathrm{/}2}$. Assume there are constants $\mu >0$ and $G\ge 0$ such that, uniformly in $s$, $\mathrm{\ell }(s,\cdot )$ is $G$-Lipschitz, meaning $\mathrm{\mid }\mathrm{\ell }(s,x)-\mathrm{\ell }(s,y)\mathrm{\mid }\le G\mathrm{\parallel }x-y{\mathrm{\parallel }}_2$, and is $\mu$-strongly convex on $K$; that is,

$\mathrm{\ell }(s,(1-\lambda )x+\lambda y)\le (1-\lambda )\mathrm{\ell }(s,x)+\lambda \mathrm{\ell }(s,y)-\frac{\mu }{2}\lambda (1-\lambda )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2$

for all $x,y\in K$ and $\lambda \in [0,1]$. Run the population-loss version of DAgger for a positive integer $N$ rounds with exact FTL updates, and assume each cumulative population loss attains its minimum on $K$. Let ${\beta }_i\in [0,1]$ satisfy ${\beta }_1\le 1$ and ${\beta }_i\le (1-\alpha {)}^{i-1}$ for $2\le i\le N$, where $\alpha \in (0,1]$ is fixed independently of $T$ and $N$. Suppose $u\ge 0$ satisfies $Q_t^{\ast }(s,a)-V_t^{\ast }(s)\le u$ for every time $t$, state $s$, and admissible action $a$.

Let $L_i(\theta )={\sum }_s{d}_{{\pi }_i}(s)\mathrm{\ell }(s,\theta )$ be the true round-$i$ loss under the mixed rollout policy, and let ${ϵ}_N={\min }_{\theta \in K}{N}^{-1}{\sum }_{i=1}^N{L}_i(\theta )$, with the minimum attained. Define $H_0=0$, $H_n={\sum }_{j=1}^{n}1\mathrm{/}j$, let $q_T$ be the least nonnegative integer with $T\le 2^{q_T}$, and let $k_{\alpha }$ be the least positive integer with $k_{\alpha }\alpha \ge 1$. Then some learned policy $\widehat{\pi }\in \{{\widehat{\pi }}_1,\dots ,{\widehat{\pi }}_N\}$ satisfies

$J(\widehat{\pi })\le J({\pi }^{\ast })+uT[{ϵ}_N+\frac{1+\frac{4G^2}{\mu }{H}_{N-1}+k_{\alpha }(q_T+2)}{N}]\mathrm{.}$

In particular, the additive term beyond $uT{ϵ}_N$ is at most $1$ whenever $N\ge uT(1+\frac{4G^2}{\mu }{H}_{N-1}+k_{\alpha }(q_T+2))$. For fixed $\alpha ,\mu ,G$ and a valid scale $u\ge 1$, the sufficient iteration count is $\tilde{O}(uT)$ because $H_{N-1}$ and $q_T$ grow logarithmically. If a valid one-step bound has $u<1$, it may be enlarged to $1$ for this iteration-count corollary; the exact inequality above remains valid with the original $u$. This is an infinite-sample statement: expert labels must be obtained by interaction on states visited under ${\pi }_i$.

Finite-horizon imitation learning and expert-surrogate loss: defines task cost, finite-horizon state occupancy, surrogate disagreement domination, mixed rollout losses, and ${ϵ}_N$.

Dataset Aggregation (DAgger): population-loss FTL updates, expert/learner mixture, and interactive expert labels.

Follow-the-Leader regret for bounded strongly convex losses: exact cumulative FTL regret bound $1+(4G^2\mathrm{/}\mu )H_{N-1}$.

Expert mixing changes finite-horizon state occupancy by at most the mixing mass: a bounded state loss changes by at most $\min (1,T{\beta }_i)$ between the mixed and learner occupancies.

Expert-surrogate loss bounds finite-horizon task-cost increase: task-cost increase is at most $uT$ times the learner's own-occupancy surrogate loss.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Theorems 3.1–3.2 and §4.2, PDF pp. 3–4.

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

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