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

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!

• Surrogate loss means it's a loss which is not the true loss but is always greater than the true loss. The best example for this is the SVM hinge loss, even if the true loss should be an abrupt 0-1 loss, we use a hinge loss to make the problem of SVM a convex problem and also help in getting a maximum margin classifier. Thus, minimising on a surrogate loss gives you a simpler learning algorithms but a worse solution. – DuttaA Aug 13 '20 at 10:07

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^*$$.