What is sample efficiency, and how can importance sampling be used to achieve it?

Question

For instance, the title of this paper reads: "Sample Efficient Actor-Critic with Experience Replay".

What is sample efficiency, and how can importance sampling be used to achieve it?

Answer 1

An algorithm is sample efficient if it can get the most out of every sample. Imagine yourself playing PONG for the first time. As a human, it would take you within seconds to learn how to play the game based on very few samples. This makes you very "sample efficient". Modern RL algorithms would have to see $100$ thousand times more data than you so they are, relatively, sample inefficient.

In the case of off-policy learning, not all samples are useful in that they are not part of the distribution that we are interested in. Importance sampling is a technique to filter these samples. Its original use was to understand one distribution while only being able to take samples from a different but related distribution. In RL, this often comes up when trying to learn off-policy. Namely, that your samples are produced by some behaviour policy but you want to learn a target policy. Thus one needs to measure how important/similar the samples generated are to samples that the target policy may have made. Thus, one is sampling from a weighted distribution which favours these "important" samples. There are many methods, however, for characterizing what is important, and their effectiveness may differ depending on the application.

The most common approach to this off-policy style of importance sampling is finding a ratio of how likely a sample is to be generated by the target policy. The paper On a Connection between Importance Sampling and the Likelihood Ratio Policy Gradient (2010) by Tang and Abbeel covers this topic.

Answer 2

Sample Efficiency denotes the amount of experience that an agent/algorithm needs to generate in an environment (e.g. the number of actions it takes and number of resulting states + rewards it observes) during training in order to reach a certain level of performance. Intuitively, you could say an algorithm is sample efficient if it can make good use of every single piece of experience it happens to generate and rapidly improve its policy. An algorithm has poor sample efficiency if it fails to learn anything useful from many samples of experience and doesn't improve rapidly.

The explanation of importance sampling in Jaden's answer seems mostly correct.

In the paper in your question, importance sampling is one of the ingredients that enables a correct combination of 1) learning from multi-step trajectories, and 2) experience replay buffers. Those two things were not easy to combine before (because multi-step returns without importance sampling are only correct in on-policy learning, and old samples in a replay buffer were generated by an old policy which means that learning from them is off-policy). Both of those things individually improve sample efficiency though, which implies that it's also beneficial for sample efficiency if they can still be combined somehow.