Imitation Learning

Let’s say we have a policy ${\pi }^{\beta }$ (known as the behavior policy). We run ${\pi }^{\beta }$ on the environment and generate $\mathcal{D}$ (a dataset of experience tuples). Now, since each tuple is of the form $\{o_t,a_t,r_t,o_{t+1},d_t\}$ corresponding to the observation, action, reward, next observation, and done respectively at time-step $t$, we can easily extract a new dataset ${\mathcal{D}}^{\prime }=\{o_t,a_t{\}}_{t=0}^{|\mathcal{D}|}$. Note that in the analogy of supervised learning, $\{o_t{\}}_t$ are the data features and $\{a_t{\}}_t$ are the targets. Since we consider the continuous state/action space, it might be helpful to think of the supervised learning task as a regression task. Note that although in this part of the notes all the expressions use observations ($o_t$), however everything can be interchanged to states ($s_t$) without much modification.

Behavior Cloning (BC)

For behavior cloning to work, we need to assume that the behavior policy ${\pi }^{\beta }$ is also the optimal (expert) policy ${\pi }^{\ast }$, since it doesn’t make sense to imitate sub-optimal policies. So, given ${\mathcal{D}}^{\prime }$ we need to learn a mapping ${\pi }_{\theta }:\mathcal{O}\to \mathcal{A}$, i.e. a policy (which can be modeled as a parametric distribution over actions conditioned on the observation) ${\pi }_{\theta }(a_t|o_t)$. This can be easily learned by using ERM (expected risk minimization), which is equivalent to maximizing the log likelihood of the data as follows:

$$\underset{\theta }{\max }{\mathbb{E}}_{(o_t,a_t)\sim {\mathcal{D}}^{\prime }}\log {\pi }_{\theta }(a_t|o_t)$$

where the symbols have their usual meanings. In the regression setting, the ERM objective becomes:

$${\theta }^{\ast }=\arg \underset{\theta }{\max }{\mathbb{E}}_{(o_t,a_t)\sim {\mathcal{D}}^{\prime }}[({\pi }_{\theta }(o_t)-a_t{)}^2]$$

---

Aside (Cost Function and RL Objective)

We can now analyze the “goodness” of the policy ${\pi }_{{\theta }^{\ast }}$ obtained after ERM by inspecting the difference from ${\pi }^{\ast }$. Recall that the any MDP can be characterized by either a reward or a cost function. Assume the following cost function:

$$c(o_t,a_t)=\{\begin{array}{ll}0& a_t={\pi }^{\ast }(o_t)\\ 1& otherwise\end{array}$$

In that case the goal of any RL agent should be to minimize the cost (rather than the ERM):

$${\theta }^{\ast }=\arg \underset{\theta }{\min }{\mathbb{E}}_{o_t\sim p_{{\pi }_{\theta }}(o_t)}[c(o_t,{\pi }_{\theta }(o_t))]$$

Note: Although in ERM we are training without rewards, since the task is sequential decision making, we shall be using the above cost function to evaluate the performance of any trained policy.

---

Analysis

Let’s assume that for any $o_t$ (under the trained BC policy trained using ERM), the probability of incurring the cost (i.e. making error), i.e.:

$${\pi }_{{\theta }^{\ast }}({\hat{a}}_t\ne a_t|o_t)\le ϵ;\forall (o_t,a_t)\in {\mathcal{D}}^{\prime }$$

where ${\hat{a}}_t\sim {\pi }_{{\theta }^{\ast }}(s_t)$ and $ϵ\ge 0$ is a small constant bound. So, the upper bound on the total error for a trajectory run by taking actions according to a BC trained policy ${\pi }_{{\theta }^{\ast }}$ is:

$$\mathbb{E}\left[\sum _{t=0}^{T}c(o_t,{\hat{a}}_t)\right]\le ϵT;\text{ only when all possible }{o}_t\in {\mathcal{D}}^{\prime }...[1]$$

However, that is not the case during execution of the policy. Assume that the agent transitions from $o_t\in {\mathcal{D}}^{\prime }$ to $o_{t+1}\notin {\mathcal{D}}^{\prime }$ after an erroneous decision. Since there is a distribution shift, all actions corresponding to time-steps $t+1$ onward until $T$ will be wrong and will incur a cost.

Let $p_{{\theta }^{\ast }}(o_t)$ be the distribution over observations at the $t^{\text{th}}$ time-step that is obtained when the trajectory is collected with the policy ${\pi }_{{\theta }^{\ast }}$:

$$p_{{\theta }^{\ast }}(o_t)=(1-ϵ{)}^t{p}_{train}(o_t)+(1-(1-ϵ{)}^t)p_{mistake}(o_t)$$

where $p_{train}(o_t)$ can be thought of as the distribution over observations when the trajectory is collected using ${\pi }^{\beta }$ (${\pi }^{\ast }$ in our case), i.e. the same distribution from which ${\mathcal{D}}^{\prime }$ was generated, and similarly $p_{mistake}$ is the distribution over observations after the first mistake is made. We are interested in finding out how far off is the distribution of observations under the current policy (trained using the dataset ${\mathcal{D}}^{\prime }$) vs. the behavior policy (that collected the training dataset). Manipulating the above expression we get:

$$\begin{array}{rl}{p}_{{\theta }^{\ast }}(o_t)& =(1-ϵ{)}^t{p}_{train}(o_t)+(1-(1-ϵ{)}^t)p_{mistake}(o_t)\\ & =(1-ϵ{)}^t{p}_{train}(o_t)-(1-ϵ{)}^t{p}_{mistake}(o_t)+p_{mistake}(o_t)\\ & =p_{mistake}(o_t)+(1-ϵ{)}^t(p_{train}(o_t)-p_{mistake}(o_t))\\ ⟹-p_{{\theta }^{\ast }}(o_t)& =-p_{mistake}(o_t)-(1-ϵ{)}^t(p_{train}(o_t)-p_{mistake}(o_t))\\ ⟹p_{train}(o_t)-p_{{\theta }^{\ast }}(o_t)& =(p_{train}(o_t)-p_{mistake}(o_t))-(1-ϵ{)}^t(p_{train}(o_t)-p_{mistake}(o_t))\\ & =(1-(1-ϵ{)}^t)(p_{train}(o_t)-p_{mistake}(o_t))\end{array}$$

However, since we are only interested in the magnitude of the difference, and not the sign, we can upper-bound the variational divergence as follows:

$$\begin{array}{rl}⟹|p_{train}(o_t)-p_{{\theta }^{\ast }}(o_t)|& =(1-(1-ϵ{)}^t)\cdot |p_{train}(o_t)-p_{mistake}(o_t)|\\ & \le (1-(1-ϵ{)}^t)\cdot 2\text{ (using the identity ∣a−b∣<∣a∣+∣b∣ \& maxP[⋅]=1)}\\ & \le 2ϵt\text{ (using the identity (1−ϵ)t≥1−ϵt)}\end{array}$$

Thus the difference between the distribution of observations at time-step $t$ obtained by learning the optimal policy and the learned policy is upper-bounded by $2ϵt$. Hence, the expected cost over the trajectory can be calculated as follows:

$$\begin{array}{rl}{\mathbb{E}}_{o_t\sim p_{{\theta }^{\ast }}(\cdot ),{\hat{a}}_t\sim {\pi }_{{\theta }^{\ast }}(\cdot |o_t)}\left[\sum _{t=0}^{T}c(o_t,{\hat{a}}_t)\right]& =\sum _{t=0}^T{\mathbb{E}}_{o_t,{\hat{a}}_t}\left[c(o_t,{\hat{a}}_t)\right]\text{ (linearity of expectations)}\\ & =\sum _{t=0}^T\sum _{o_t}{p}_{{\theta }^{\ast }}(o_t)\cdot c(o_t,{\hat{a}}_t)\\ & =\sum _{t=0}^T\sum _{o_t}(p_{train}(o_t)+p_{{\theta }^{\ast }}(o_t)-p_{train}(o_t))\cdot c(o_t,{\hat{a}}_t)\\ & =\sum _{t=0}^T\sum _{o_t}{p}_{train}(o_t)\cdot c(o_t,{\hat{a}}_t)+(p_{{\theta }^{\ast }}(o_t)-p_{train}(o_t))\cdot c(o_t,{\hat{a}}_t)\\ & =\sum _{t=0}^T\left({\mathbb{E}}_{o_t,{\hat{a}}_t}\left[c(o_t,{\hat{a}}_t)\right]+\sum _{o_t}(p_{{\theta }^{\ast }}(o_t)-p_{train}(o_t))\cdot c(o_t,{\hat{a}}_t)\right)\\ & \le \sum _{t=0}^T\left({\mathbb{E}}_{o_t,{\hat{a}}_t}\left[c(o_t,{\hat{a}}_t)\right]+\sum _{o_t}|p_{{\theta }^{\ast }}(o_t)-p_{train}(o_t)|\cdot c_{\text{max}}\right)\\ & \le \sum _{t=0}^Tϵ+2ϵt\text{ (cmax=1 as defined above)}\\ & =ϵ\sum _{t=0}^{T}1+2ϵ\sum _{t=0}^{T}t=ϵT+2ϵ\frac{T(T+1)}{2}\\ & =ϵT+ϵT(T+1)=2ϵT+ϵT^2\\ \therefore {\mathbb{E}}_{o_t\sim p_{{\theta }^{\ast }}(\cdot ),{\hat{a}}_t\sim {\pi }_{{\theta }^{\ast }}(\cdot |o_t)}\left[\sum _{t=0}^{T}c(o_t,{\hat{a}}_t)\right]& \in \mathcal{O}(T^2)\end{array}$$

here $\mathcal{O}$ is the Big-Oh Notation, not the observation space.

This problem can be addressed in a the following ways:

• Be smart about data collection (and augmentation)
• Use very powerful models that make very few mistakes
• Use multi-task learning
• Change the algorithm (DAgger)

---

DAgger (Dataset Aggregation)

GOAL: Collect data from $p_{{\pi }_{\theta }}(o_t)$ instead of $p_{{\pi }^{\ast }}(o_t)$ While ${\pi }_{\theta }\ne {\pi }^{\ast }$ for the support $o_t$ of ${\pi }^{\ast }$:

1. Train $\pi_{\theta}(\hat{a}_{t}|o_{t})$ from dataset $\mathcal{D}'=\{o_{1},a_{1},...,o_{N},a_{N}\}$
2. Run $\pi_{\theta}(\hat{a}_{t}|o_{t})$ to get dataset $\mathcal{D}_{\pi}=\{o_{1},...,o_{M}\}$
3. Use $\pi^*$ to get $a_{t}$ $\forall o_{t}\in\mathcal{D}_{\pi}$
4. Aggregate $\mathcal{D}'\gets \mathcal{D}'\cup \mathcal{D}_{\pi}$

Since the dataset will eventually get populated with the entire support of ${\pi }^{\ast }$, the error will be upper-bounded by $ϵT$ as mentioned in $[1]$, i.e. all possible $o_t$ will be in the augmented dataset.