What does the number of required expert demonstrations in Imitation Learning depend on?

Question

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

Answer 1

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 (by Abbel and Ng, 2004, ICML). Specifically, theorem 1 (section 4, 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 provide a nice overview of the contents of this paper, so I suggest that you read them too.