12
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

An algorithm is sample efficient if it can get the most out of every sample. Imagine learning trying to learn how to play 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. (Thanks Dennis Soemers for correcting me (see his answer below))

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. Here is a good paper covering the topic.

$\endgroup$
  • 2
    $\begingroup$ Thanks again. Basic question: ..finding a ratio of how likely a sample is to be generated by the target policy How do we decide this, given that we know only the behaviour policy? Isn't target policy something we have to find? $\endgroup$ – Gokul NC Feb 7 '18 at 16:59
  • 1
    $\begingroup$ We can get an estimate of this readily by finding the ratio of the target policy, pi, taking that action verses the behaviour policy, mu. Thus the ratio is P= pi(s,a)/mu(s,a) where a and s are the action chosen by mu and the state, respectively. $\endgroup$ – Jaden Travnik Feb 7 '18 at 19:06
  • 1
    $\begingroup$ My question was, where do we obtain pi(s,a) from, while we only have mu(s,a) ? That is, where do we get the target policy from, while it's our goal to find it? $\endgroup$ – Gokul NC Feb 8 '18 at 5:19
  • 1
    $\begingroup$ Your target policy is initialized to random, it’s just a matter of updating it. $\endgroup$ – Jaden Travnik Feb 8 '18 at 11:40
  • 1
    $\begingroup$ @JadenTravnik I dont think your definition of sample efficiency is correct. Sample efficiency means making the best use of every sample of experience we get, whereas you seem to imply pretty much the opposite (only using some and throwing the rest away, which is far from efficiently using all samples we get). See the new answer I added. $\endgroup$ – Dennis Soemers Feb 13 '18 at 11:45
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.