What is the surrogate loss function in imitation learning, and how is it different from the true cost?

Question

I've been reading A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning lately, and I can't understand what they mean by the surrogate loss function.

Some relevant notation from the paper -

• $d_\pi$ = average distribution of states if we follow policy $\pi$ for $T$ timesteps
• $C(s,a)$ = the expected immediate cost of performing action a in state s for the task we are considering (assume $C$ is bounded in [0,1]
• $C_\pi(s) = \mathbb{E}_{a\sim\pi(s)}[C(s,a)]$ is the expected immediate cost of $π$ in $s$.
• $J(π) = T\mathbb{E}_{s\sim d_\pi}[C_\pi(s)]$ is the total cost of executing policy $\pi$ for $T$ timesteps

In imitation learning, we may not necessarily know or observe true costs $C(s,a)$ for the particular task. Instead, we observe expert demonstrations and seek to bound $J(π)$ for any cost function $C$ based on how well $π$ mimics the expert’s policy $π^{*}$. Denote $l$ the observed surrogate loss function we minimize instead of $C$. For instance, $l(s,π)$ may be the expected 0-1 loss of $π$ with respect to $π^{*}$ in state $s$, or a squared/hinge loss of $π$ with respect to $π^{*}$ in $s$. Importantly, in many instances, $C$ and $l$ may be the same function – for instance, if we are interested in optimizing the learner’s ability to predict the actions chosen by an expert.

I don't understand how exactly the surrogate loss is different from the true costs, and what are the possible cases in which both are the same. It'd be great if someone could throw some light on this. Thank you!

Answer 1

A surrogate loss is a loss than you use "instead of", "in place of", "as a proxy for" or "as a substitute for" another loss, which is typically the "true" loss.

Surrogate losses are actually common in machine learning (although almost nobody realizes that they are surrogate losses). For example, the empirical risk (which the mean squared error is an instance of) is a surrogate for the expected risk, which is incomputable in almost all cases, given that you do not know the underlying probability distribution. See An Overview of Statistical Learning Theory by V. N. Vapnik for more details. In fact, discussions on generalization arise because of this issue, i.e. you use surrogate losses rather than true losses.

The term "surrogate" is also used in conjunction with the term "model", i.e. "surrogate model", for example, in the context of Bayesian optimization, where a Gaussian process is the surrogate model for the unknown model/function that you want to know about, i.e. you use the Gaussian process to approximate the unknown function/model.

Regarding the excerpt you are quoting and your specific concerns, although I didn't read the paper and I am not an expert in imitation learning, let me try to explain what I understand from this excerpt. Essentially, in imitation learning, you use the expert's policy $\pi^*$ to train the agent, rather than letting him just explore and exploit the environment. So, what you know is $\pi^*$ and you can calculate the "loss" between $\pi^*$ and $\pi$ (the current agent's policy), denoted by $l$. However, this loss $l$ that you calculate is not necessarily the "true" loss (i.e. it is a surrogate loss), given that our goal is not really to imitate the "expert" but to learn an optimal policy to behave in the environment. If the goal was to just imitate the "expert", then $C$ and $l$ would coincide, because, in that case, $l$ would represent the "discrepancy" or "loss" between $\pi$ and the expert's policy $\pi^*$.