Answers.Body: <p>The answer to your question can be found in the original paper that introduced the <strong>max-margin</strong> and <strong>projection</strong> imitation learning (IL) algorithms: <a href="https://ai.stanford.edu/%7Eang/papers/icml04-apprentice.pdf" rel="nofollow noreferrer">Apprenticeship Learning via Inverse Reinforcement Learning</a> (by Abbel and Ng, 2004, ICML). Specifically, <a href="https://ai.stanford.edu/%7Eang/papers/icml04-apprentice.pdf#page=4" rel="nofollow noreferrer">theorem 1 (section 4, page 4)</a> states</p>
  <blockquote>
  <p>Let an <span class="math-container">$\text{MDP} \setminus R$</span>, features <span class="math-container">$ \phi : S \rightarrow [0, 1]^k$</span>, and any <span class="math-container">$\epsilon &gt; 0$</span> be given. Then the apprenticeship learning algorithm (both max-margin and projection versions) will terminate with <span class="math-container">$t^{(i)} \leq \epsilon$</span> after at most</p>
  <p><span class="math-container">$$n=O\left(\frac{k}{(1-\gamma)^{2} \epsilon^{2}} \log \frac{k}{(1-\gamma) \epsilon}\right)$$</span>
  iterations.</p>
  </blockquote>
  <p>Here <span class="math-container">$k$</span> is the dimension of the feature vectors, so it's clear that the number of iterations needed for these algorithms to terminate scales with <span class="math-container">$k$</span>. The proof of this theorem can be found in appendix A of the same paper (and all other terms are defined in the paper, which you should read to understand all the details). Of course, this result holds (only) for these specific IL algorithms (which are the algorithms the author of your slides, Abbel, is referring to). See also theorem 2 and the experiments section (in particular, figure 4, which shows the performance as a function of the number of trajectories) of the same paper.
  <a href="https://github.com/rhklite/apprenticeship_inverse_RL/blob/master/Apprenticeship%20Learning%20via%20Inverse%20Reinforcement%20Learning.pdf" rel="nofollow noreferrer">These slides</a> provide a nice overview of the contents of this paper, so I suggest that you read them too.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-09T22:23:10.237Z
Answers.LastActivityDate: 2020-11-10T13:44:05.670Z
Answers.LastEditDate: 2020-11-10T13:44:05.670Z
Answers.UserDisplayName: nbro
Body: <p>I just read the following points about the number of required expert demonstrations in imitation learning, and I'd like some clarifications. For the purpose of context, I'll be using a linear reward function throughout this post (i.e. the reward can be expressed as a weighted sum of the components of a state's feature vector)</p>
  <blockquote>
  <p>The number of expert demonstrations required <strong>scales with the number of features in the reward function</strong>.</p>
  </blockquote>
  <p>I don't think this is obvious at all - why is it true? Intuitively, I think that as the number of features rises, the complexity of the problem does too, so we may need more data to make a better estimate of the expert's reward function. Is there more to it?</p>
  <blockquote>
  <p>The number of expert demonstration required does not depend on -</p>
  <ul>
  <li>Complexity of the expert’s optimal policy <span class="math-container">$\pi^{*}$</span></li>
  <li>Size of the state space</li>
  </ul>
  </blockquote>
  <p>I don't see how the complexity of the expert's optimal policy plays a role here - which is probably why it doesn't affect the number of expert demonstrations we need; but how do we <strong>quantify the complexity of a policy</strong> in the first place?</p>
  <p>Also, I think that the number of expert demonstrations <strong>should depend on the size of the state space</strong>. For example, if the train and test distributions don't match, we can't do behavioral cloning without falling into problems, in which case we use the <em>DAGGER algorithm</em> to repeatedly query the expert and make better decisions (take better actions). I feel that a larger state space means that we'll have to query the expert more frequently, i.e. to figure out the expert's optimal action in several states.</p>
  <p>I'd love to know everyone's thoughts on this - <strong>the dependence of the number of expert demonstrations on the above, and if any, other factors</strong>. Thank you!</p>
  <hr />
  <p>Source: <a href="https://people.eecs.berkeley.edu/%7Epabbeel/cs287-fa12/slides/inverseRL.pdf" rel="nofollow noreferrer">Slide 20/75</a></p>
  
Tags: <reinforcement-learning><apprenticeship-learning><inverse-rl><imitation-learning>
Title: What does the number of required expert demonstrations in Imitation Learning depend on?
UserDisplayName: stoic-santiago
ThreadText: # What does the number of required expert demonstrations in Imitation Learning depend on?
  
  (Asked by: username_0 on 2020-08-13)
  
  I just read the following points about the number of required expert demonstrations in imitation learning, and I'd like some clarifications. For the purpose of context, I'll be using a linear reward function throughout this post (i.e. the reward can be expressed as a weighted sum of the components of a state's feature vector)
  
  > The number of expert demonstrations required **scales with the number of features in the reward function**.
  
  I don't think this is obvious at all - why is it true? Intuitively, I think that as the number of features rises, the complexity of the problem does too, so we may need more data to make a better estimate of the expert's reward function. Is there more to it?
  
  > The number of expert demonstration required does not depend on -
  >
  > * Complexity of the expert’s optimal policy $\pi^{\*}$
  > * Size of the state space
  
  I don't see how the complexity of the expert's optimal policy plays a role here - which is probably why it doesn't affect the number of expert demonstrations we need; but how do we **quantify the complexity of a policy** in the first place?
  
  Also, I think that the number of expert demonstrations **should depend on the size of the state space**. For example, if the train and test distributions don't match, we can't do behavioral cloning without falling into problems, in which case we use the *DAGGER algorithm* to repeatedly query the expert and make better decisions (take better actions). I feel that a larger state space means that we'll have to query the expert more frequently, i.e. to figure out the expert's optimal action in several states.
  
  I'd love to know everyone's thoughts on this - **the dependence of the number of expert demonstrations on the above, and if any, other factors**. Thank you!
  
  ---
  
  Source: [Slide 20/75](https://people.eecs.berkeley.edu/%7Epabbeel/cs287-fa12/slides/inverseRL.pdf)
  
  **Tags:** reinforcement-learning, apprenticeship-learning, inverse-rl, imitation-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-11-09. Score: 1 | Accepted answer
  
  The answer to your question can be found in the original paper that introduced the **max-margin** and **projection** imitation learning (IL) algorithms: [Apprenticeship Learning via Inverse Reinforcement Learning](https://ai.stanford.edu/%7Eang/papers/icml04-apprentice.pdf) (by Abbel and Ng, 2004, ICML). Specifically, [theorem 1 (section 4, page 4)](https://ai.stanford.edu/%7Eang/papers/icml04-apprentice.pdf#page=4) states
  
  > Let an $\text{MDP} \setminus R$, features $ \phi : S \rightarrow [0, 1]^k$, and any $\epsilon > 0$ be given. Then the apprenticeship learning algorithm (both max-margin and projection versions) will terminate with $t^{(i)} \leq \epsilon$ after at most
  >
  > $$n=O\left(\frac{k}{(1-\gamma)^{2} \epsilon^{2}} \log \frac{k}{(1-\gamma) \epsilon}\right)$$
  > iterations.
  
  Here $k$ is the dimension of the feature vectors, so it's clear that the number of iterations needed for these algorithms to terminate scales with $k$. The proof of this theorem can be found in appendix A of the same paper (and all other terms are defined in the paper, which you should read to understand all the details). Of course, this result holds (only) for these specific IL algorithms (which are the algorithms the author of your slides, Abbel, is referring to). See also theorem 2 and the experiments section (in particular, figure 4, which shows the performance as a function of the number of trajectories) of the same paper.
  [These slides](https://github.com/rhklite/apprenticeship_inverse_RL/blob/master/Apprenticeship%20Learning%20via%20Inverse%20Reinforcement%20Learning.pdf) provide a nice overview of the contents of this paper, so I suggest that you read them too.
  
  
  ---
  
  