Answers.Body: <p>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.</p>
  
  <p>The explanation of importance sampling in Jaden's answer seems mostly correct.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-13T11:42:50.290Z
Answers.LastActivityDate: 2018-02-13T11:42:50.290Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>An algorithm is <strong>sample efficient</strong> 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 &quot;sample efficient&quot;. Modern RL algorithms would have to see <span class="math-container">$100$</span> thousand times more data than you so they are, relatively, sample inefficient.</p>
  <p>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. <strong><a href="https://en.wikipedia.org/wiki/Importance_sampling" rel="noreferrer">Importance sampling</a></strong> 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 &quot;important&quot; samples. There are many methods, however, for characterizing what is important, and their effectiveness may differ depending on the application.</p>
  <p>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 <a href="http://rll.berkeley.edu/%7Ejietang/pubs/nips10_Tang.pdf" rel="noreferrer">On a Connection between Importance Sampling and
  the Likelihood Ratio Policy Gradient</a> (2010) by Tang and Abbeel covers this topic.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-07T16:59:57.593Z
Answers.Text: Thanks again. I have another question. You say "_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 the target policy something we have to find?
Answers.UserDisplayName: Gokul NC
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-07T19:06:17.150Z
Answers.Text: 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.
Answers.UserDisplayName: Jaden Travnik
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-08T05:19:44.373Z
Answers.Text: 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?
Answers.UserDisplayName: Gokul NC
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-08T11:40:50.573Z
Answers.Text: Your target policy is initialized to random, it’s just a matter of updating it.
Answers.UserDisplayName: Jaden Travnik
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-02-07T13:25:25.893Z
Answers.LastActivityDate: 2022-07-07T15:10:42.643Z
Answers.LastEditDate: 2022-07-07T15:10:42.643Z
Answers.UserDisplayName: Jaden Travnik
Body: <p>For instance, the title of <a href="https://arxiv.org/abs/1611.01224" rel="noreferrer">this paper</a> reads: "Sample Efficient Actor-Critic with Experience Replay".</p>
  
  <p>What is <em>sample efficiency</em>, and how can <em>importance sampling</em> be used to achieve it?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-01-22T18:59:40.550Z
Comments.Text: Do you mean https://en.m.wikipedia.org/wiki/Sample_complexity ? Not sure if it is the same
Comments.UserDisplayName: Ggjj11
Tags: <reinforcement-learning><papers><importance-sampling><sample-efficiency>
Title: What is sample efficiency, and how can importance sampling be used to achieve it?
UserDisplayName: Gokul NC
ThreadText: # What is sample efficiency, and how can importance sampling be used to achieve it?
  
  (Asked by: username_0 on 2018-02-07)
  
  For instance, the title of [this paper](https://arxiv.org/abs/1611.01224) reads: "Sample Efficient Actor-Critic with Experience Replay".
  
  What is *sample efficiency*, and how can *importance sampling* be used to achieve it?
  
  **Tags:** reinforcement-learning, papers, importance-sampling, sample-efficiency
  
  > **Comments:**
  > **username_1**: Do you mean https://en.m.wikipedia.org/wiki/Sample_complexity ? Not sure if it is the same  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2018-02-07. Score: 30 | Accepted answer
  
  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](https://en.wikipedia.org/wiki/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](http://rll.berkeley.edu/%7Ejietang/pubs/nips10_Tang.pdf) (2010) by Tang and Abbeel covers this topic.
  
  > **Comments:**
  > **username_0**: Thanks again. I have another question. You say "_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 the target policy something we have to find?  
  > **username_3**: 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.  
  > **username_0**: 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?  
  > **username_3**: Your target policy is initialized to random, it’s just a matter of updating it.  
  
  ---
  
  ### Answer by username_2 on 2018-02-13. Score: 7
  
  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 username_3'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.
  
  
  ---
  
  