Imitation learning and DAgger — Examples

Let the states be $g$ (good) and $b$ (bad), with initial state $S_0=g$. At $g$ the actions are $c$ and $e$; action $c$ stays at $g$ with task cost $0$, while action $e$ moves to $b$ with cost $1$. At $b$ the actions are $r$ and $e$; action $r$ moves to $g$ with cost $0$, while action $e$ stays at $b$ with cost $1$. The transition is deterministic for every state/action pair. The deterministic expert chooses $c$ at $g$ and $r$ at $b$. For a parameter $ϵ$ with $0<ϵ\le 1\mathrm{/}T$, the learner chooses $e$ at $g$ with probability $ϵ$ and $c$ otherwise, and always chooses $e$ at $b$. Use the statewise 0–1 expert-action disagreement as surrogate loss.

The diagram labels each deterministic transition by action/task-cost; the text specifies the two stochastic action probabilities of the learner. The expert occupancy is concentrated at $g$, so the behavior-cloning disagreement loss on expert states is $ϵ$. Under the learner, the expected total task cost is

${\sum }_{k=1}^T(1-(1-ϵ{)}^k),$

which lies between $ϵT^2\mathrm{/}8$ and $ϵT^2$. Thus an $ϵ$ disagreement rate on expert states can correspond to quadratic-in-$T$ learner cost when a mistake moves the learner to states absent from expert demonstrations.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[draw,circle] (g) at (0,0) {$g$};
  \node[draw,circle] (b) at (4,0) {$b$};
  \draw[->] (g) edge[loop above] node[above] {$c/0$} (g);
  \draw[->] (g) to[bend left=18] node[above] {$e/1$} (b);
  \draw[->] (b) edge[loop above] node[above] {$e/1$} (b);
  \draw[->] (b) to[bend left=18] node[below] {$r/0$} (g);
\end{tikzpicture}

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

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

Use states $g,b$, initial state $g$, actions $A(g)=\{c,e\}$ and $A(b)=\{r,e\}$, and deterministic transitions/costs: at $g$, $c$ returns to $g$ with cost $0$ and $e$ moves to $b$ with cost $1$; at $b$, $r$ moves to $g$ with cost $0$ and $e$ returns to $b$ with cost $1$. The expert chooses $c$ at $g$ and $r$ at $b$. The learner class contains two deterministic policies: ${\pi }^{\mathrm{b}\mathrm{a}\mathrm{d}}$ chooses $e$ at both states, and ${\pi }^{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ chooses $c$ at $g$ and $r$ at $b$. Run two DAgger rounds with horizon $T=2$, one trajectory per round, expert-use probabilities ${\beta }_1={\beta }_2=0$, initial policy ${\pi }^{\mathrm{b}\mathrm{a}\mathrm{d}}$, and statewise 0–1 disagreement loss. The round-1 rollout visits $g$ and then $b$; DAgger queries the expert at both states, aggregates the labels $(g,c)$ and $(b,r)$, and fits ${\pi }^{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ as the unique minimum-loss policy. The second rollout then remains at $g$. The label $(b,r)$ could not be obtained from expert-only demonstrations because the expert stays at $g$.

The diagram labels each deterministic transition by action/task-cost and marks the initial state; the expert and the two learner policies are specified in the text.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[draw,circle] (g) at (0,0) {$g$};
  \node[draw,circle] (b) at (4,0) {$b$};
  \draw[->] (-1.5,0) -- (g) node[midway,above] {start};
  \draw[->] (g) edge[loop above] node[above] {$c/0$} (g);
  \draw[->] (g) to[bend left=18] node[above] {$e/1$} (b);
  \draw[->] (b) edge[loop above] node[above] {$e/1$} (b);
  \draw[->] (b) to[bend left=18] node[below] {$r/0$} (g);
\end{tikzpicture}

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.

Let $S=\{s\}$, $A(s)=\{a^{\ast },b\}$, and let both actions return deterministically to $s$ at every decision. For every time, set task costs $c_t(s,a^{\ast })=0$ and $c_t(s,b)=1$. Let the expert always choose $a^{\ast }$, let the learner class contain both the expert and a learner that always chooses $b$, and define a candidate loss score by $\mathrm{\ell }(s,\theta )=0$ for every class policy. Then the learner's score is zero under every state distribution, while its total task cost over horizon $T\ge 1$ is $T$ and the expert's task cost is zero. This score fails the required disagreement-domination condition $\mathrm{\ell }(s,\theta )\ge {\sum }_{a\mathrm{\ne }{\pi }^{\ast }(s)}{\pi }_{\theta }(a\mid s)$, so the example does not contradict the DAgger task-cost lemma; it shows why that premise is necessary.

The diagram labels each deterministic self-transition by action/task-cost. The two actions have the same next state but different task costs.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[draw,circle] (s) at (0,0) {$s$};
  \draw[->] (s) edge[loop above] node[above] {$a^*/0$} (s);
  \draw[->] (s) edge[loop below] node[below] {$b/1$} (s);
\end{tikzpicture}

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