Finite-horizon imitation learning and expert-surrogate loss

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.