Answers.Body: <p>A surrogate loss is a loss than you use &quot;instead of&quot;, &quot;in place of&quot;, &quot;as a proxy for&quot; or &quot;as a substitute for&quot; another loss, which is typically the &quot;true&quot; loss.</p>
  <p>Surrogate losses are actually common in machine learning (although almost nobody realizes that they are surrogate losses). For example, the <strong>empirical risk</strong> (which the <em>mean squared error</em> is an instance of) is a surrogate for the <strong>expected risk</strong>, which is <strong>incomputable</strong> in almost all cases, given that you do not know the underlying probability distribution. See <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.332.356&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">An Overview of Statistical Learning Theory</a> by V. N. Vapnik for more details. In fact, discussions on <em>generalization</em> arise because of this issue, i.e. you use surrogate losses rather than true losses.</p>
  <p>The term &quot;surrogate&quot; is also used in conjunction with the term &quot;model&quot;, i.e. &quot;surrogate model&quot;, for example, in the context of <a href="https://distill.pub/2020/bayesian-optimization/" rel="nofollow noreferrer">Bayesian optimization</a>, 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.</p>
  <p>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 <span class="math-container">$\pi^*$</span> to train the agent, rather than letting him just explore and exploit the environment. So, what you know is <span class="math-container">$\pi^*$</span> and you can calculate the &quot;loss&quot; between <span class="math-container">$\pi^*$</span> and <span class="math-container">$\pi$</span> (the current agent's policy), denoted by <span class="math-container">$l$</span>. However, this loss <span class="math-container">$l$</span> that you calculate is <strong>not necessarily</strong> the &quot;true&quot; loss (i.e. it is a surrogate loss), given that our goal is not really to imitate the &quot;expert&quot; but to learn an optimal policy to behave in the environment. If the goal was to just imitate the &quot;expert&quot;, then <span class="math-container">$C$</span> and <span class="math-container">$l$</span> would coincide, because, in that case, <span class="math-container">$l$</span> would represent the &quot;discrepancy&quot; or &quot;loss&quot; between <span class="math-container">$\pi$</span> and the expert's policy <span class="math-container">$\pi^*$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T11:18:25.173Z
Answers.LastActivityDate: 2020-08-13T14:08:51.650Z
Answers.LastEditDate: 2020-08-13T14:08:51.650Z
Answers.UserDisplayName: nbro
Body: <p>I've been reading <a href="https://arxiv.org/abs/1011.0686" rel="nofollow noreferrer"><em>A Reduction of Imitation Learning and Structured Prediction
  to No-Regret Online Learning</em></a> lately, and I can't understand what they mean by the <strong>surrogate loss function.</strong></p>
  <p>Some relevant notation from the paper -</p>
  <ul>
  <li><span class="math-container">$d_\pi$</span> = average distribution of states if we follow policy <span class="math-container">$\pi$</span> for <span class="math-container">$T$</span> timesteps</li>
  <li><span class="math-container">$C(s,a)$</span> = the expected immediate cost of performing action a in state s for the task we are considering (assume <span class="math-container">$C$</span> is bounded in [0,1]</li>
  <li><span class="math-container">$C_\pi(s) = \mathbb{E}_{a\sim\pi(s)}[C(s,a)]$</span> is the expected immediate cost of <span class="math-container">$π$</span> in <span class="math-container">$s$</span>.</li>
  <li><span class="math-container">$J(π) = T\mathbb{E}_{s\sim d_\pi}[C_\pi(s)]$</span> is the total cost of executing policy <span class="math-container">$\pi$</span> for <span class="math-container">$T$</span> timesteps</li>
  </ul>
  <blockquote>
  <p>In imitation learning, we may not necessarily know or observe true costs <span class="math-container">$C(s,a)$</span> for the particular task. Instead, we observe expert demonstrations and seek to bound <span class="math-container">$J(π)$</span>
  for any cost function <span class="math-container">$C$</span> based on how well <span class="math-container">$π$</span> mimics the expert’s policy <span class="math-container">$π^{*}$</span>. Denote <span class="math-container">$l$</span> the <strong>observed surrogate loss function</strong> we minimize <strong>instead</strong> of <span class="math-container">$C$</span>. For instance, <span class="math-container">$l(s,π)$</span> may be the expected 0-1 loss of <span class="math-container">$π$</span> with respect to <span class="math-container">$π^{*}$</span> in state <span class="math-container">$s$</span>, or a squared/hinge loss of <span class="math-container">$π$</span> with respect to <span class="math-container">$π^{*}$</span> in <span class="math-container">$s$</span>. Importantly, in many instances, <strong><span class="math-container">$C$</span> and <span class="math-container">$l$</span> may be the same function</strong> – for instance, if we are interested in <strong>optimizing the learner’s ability to predict the actions chosen by an expert</strong>.</p>
  </blockquote>
  <p>I don't understand <em>how exactly</em> the surrogate loss is <strong>different</strong> from the true costs, and <em>what are the possible cases</em> in which both are the <strong>same</strong>. It'd be great if someone could throw some light on this. Thank you!</p>
  
Tags: <reinforcement-learning><papers><imitation-learning>
Title: What is the surrogate loss function in imitation learning, and how is it different from the true cost?
UserDisplayName: stoic-santiago
ThreadText: # What is the surrogate loss function in imitation learning, and how is it different from the true cost?
  
  (Asked by: username_0 on 2020-08-13)
  
  I've been reading [*A Reduction of Imitation Learning and Structured Prediction
  to No-Regret Online Learning*](https://arxiv.org/abs/1011.0686) 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!
  
  **Tags:** reinforcement-learning, papers, imitation-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-13. Score: 2 | Accepted answer
  
  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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.332.356&rep=rep1&type=pdf) 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](https://distill.pub/2020/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^\*$.
  
  
  ---
  
  