[Imitation Learning Notes] Behavior Cloning

I. The Concept of Behavior Cloning

Behavior cloning is an imitation learning method, not a reinforcement learning method.

Reinforcement learning: supervision comes from rewards provided by the environment; Imitation learning: supervision comes from experience of human actions. The main distinction is that imitation learning has no reward return and knowledge-imitates expert actions.

II. The Behavior Cloning Process

1. Observe the current state $s_t$
2. The policy network makes a prediction $p_t$
3. The expert’s action is $a_t^*$; vectorize it to obtain $y_t$
4. Compute the loss CrossEntropy($y_t,p_t$)
5. Use gradient descent to update the policy network

III. Advantages and Limitations of Behavior Cloning

If the current state appears in the training data, the policy network trained through behavior cloning can execute actions similar to those of a human expert.

However, if the current state does not appear in the training data, the actions output by the policy network may not be very good, and the errors will accumulate. This is especially likely when the state is extremely complex.

I. Introduction to Imitation Learning

Imitation learning enables an agent to learn from expert examples so that it can make intelligent decisions like a human expert.

• Unlike traditional supervised learning algorithms, supervised learning requires considering a large number of constraints and designing specific supervision methods based on those constraints to guide the agent;
• Imitation learning, by contrast, aims to let humans for-it-kindness be able to ti-provide a large number of example behaviors and use these expert examples to teach the agent to make decisions.

Imitation learning is currently divided mainly into two categories:

• Behavior cloning: attempts to minimize the difference between the actions of the agent’s policy and the expert policy, treating imitation learning as a regression or classification task;
• Adversarial imitation learning: constructs an adversarial reward function through inverse reinforcement learning and maximizes this reward function to imitate expert behavior.

II. Mathematical Foundations (Markov Decision Processes)

Consider a finite-state Markov chain with state space $S=\{1,2,3,\cdots,|S|\}$. Because of the Markov property, state transitions are independent of historical states. Therefore, the state transition matrix $P$ for a finite-state Markov chain is as follows:

$$P=\begin{bmatrix}{} p_{1,1} & p_{1,2} & \cdots & p_{1,|S|}\\ p_{2,1} & p_{2,2} & \cdots & p_{2,|S|}\\ \cdots & \cdots & \cdots & \cdots\\ p_{|S|,1} & p_{|S|,2} & \cdots & p_{|S|,|S|} \end{bmatrix}$$

Each element $p_{i,j}$ represents the probability of transitioning from state $i$ to state $j$ and satisfies:

$$\sum^{|S|}_{i=1}P_{i,j}=1, \sum^{|S|}_{j=1}P_{i,j}=1$$

To fully represent the state transition process, the initial state distribution $\rho$ must be specified. This allows the probability that a given state $i$ occurs at time $t$ to be calculated recursively (the probability of being in state $j$ at the previous time step $\times$ the state transition probability from state $j$ to state $i$):

$$\mathbb{P}(s_t=i)=\sum_{j\in S}\mathbb{P}(s_{t-1}=j)p_{j,i}$$

For a Markov decision process, the state transition is influenced not only by the up-shift-moment state but also by the current action. Therefore, in addition to the state, the action and reward must also be considered. A Markov decision process can thus be represented as $M=(S,A,\rho,P,r)$ and mathematically expressed as $P(s_{t+1}|s_t, a_t)$.

To represent the process that generates actions, a policy $\pi(a|s)$ is introduced. In state $s$, it represents the probability of selecting action $a$. Because there are at most $|S|$ states and $|A|$ actions, $\pi$ can also be represented by an $|S| \times |A|$ matrix.

According to the interaction rules of a Markov decision process and the calculation of cumulative return, return discounting must be considered. Define a discount factor $\gamma \in(0,1)$; the Markov decision process then becomes a 6-tuple $M=(S, A, \rho, P, r, \gamma)$, and the cumulative return under $M$ is:

$$V(\pi)=\mathbb{E}\left[\sum^\infty_{t=0}\gamma^t r(s_t, a_t)\right]$$

Here, $V(\pi)$ represents the expected cumulative reward that policy $\pi$ can obtain. The reward at each step is multiplied by the coefficient $\gamma^t$ to ensure that the infinite sum is correct.

When policy $\pi$ is fixed, its state-value function can be defined for any initial state $s$:

$$V^{\pi}(s)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\bigg|s_{0}=s,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim P(s_{t+1}|s_{t},a_{t})\right].$$

The state-action value function can likewise be defined:

$$Q^{\pi}(s,a)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\bigg|s_{0}=s,a_0=a,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim P(s_{t+1}|s_{t},a_{t})\right].$$

III. Imitation Learning Algorithms

3.1 Behavior Cloning Algorithm

The idea behind behavior cloning is to estimate the expert policy $\pi^E$ from data. For a specific state $s$, $\pi(\cdot|s)$ is a probability distribution over the action space $A$. A classic estimation method is maximum likelihood estimation.

$$\max_{\theta}\sum_{(s,a)\in\mathcal{D}}\log(\hat \pi_{\theta}(a|s))$$

It can be proved that the problem corresponding to this maximum likelihood model is a convex optimization problem.

• If the action space is discrete, an $A$-dimensional vector can be used to define the softmax function. The problem then becomes the familiar cross-entropy optimization problem in classification.
• If the oh-treated-as space is continuous, a Gaussian distribution can be used to represent a policy, $\hat \pi_\theta(\cdot|s)=N(\mu_\theta(s),\sigma^2_\theta(s))$. The problem is therefore converted into a regression problem based on mean squared error.

The behavior cloning algorithm can estimate a policy $\pi$ directly from expert data, but it also introduces a problem: the training dataset

References:

1. Tian Xu, Ziniu Li, and Yang Yu. A Concise Tutorial on Imitation Learning. 2021