Answers.Body: <p>The point of importance sampling is to use the same episode(s) to do multiple policy gradient updates. It will definitely increase sample efficiency over the strictly on-policy case, simply because in an off-policy algorithm we can use a single transition to do multiple updates, whereas we only get a single update from that same experience in the on-policy case.</p>
  <p>First of all, in the pseudocode for TRPO that you give, I see no importance sampling being done, and the pseudocode makes it seem that the algorithm is being done on-policy.</p>
  <p>Basically, an on-policy algorithm would look like:</p>
  <p><span class="math-container">\begin{align*} 
  &amp; \text{ for each iteration }: \\
  &amp; \qquad \text{ for t in range(n)}: \\
  &amp; \qquad \qquad \text{sample } a_t; \text{ get reward } r_t \text{ and next state } s_{t+1} \\
  &amp; \qquad \text{ do policy update based on } a_1, r_1, s_2, a_2, \ldots
  \end{align*}</span></p>
  <p>whereas an off-policy algorithm is like</p>
  <p><span class="math-container">\begin{align*} 
  &amp; \text{ for each iteration }: \\
  &amp; \qquad \text{ for t in range(n)}: \\
  &amp; \qquad \qquad \text{sample } a_t; \text{ get reward } r_t \text{ and next state } s_{t+1} \\
  &amp; \qquad \text{ for m epochs}: \\
  &amp; \qquad \qquad \text{ for k mini-batches}: \\
  &amp; \qquad \qquad \qquad \text{make mini batch from} \{a_1, r_1, s_2, a_2, \ldots\} \text{ and do policy gradient update }
  \end{align*}</span></p>
  <p>So, in an off-policy algorithm, you may have something like <span class="math-container">$m=10$</span> (10 epochs), meaning every transition you do gets used in 10 policy gradient updates. An on policy algorithm would only use that transition once.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-18T06:38:51.613Z
Answers.Text: This clarifies a lot. But  I still have some problems. 1) TRPO is a on-policy method for sure, for which it confuses me a lot that how is sample efficiency attained without doing multiple update like the off-policy method does (seems no essential difference bewteen VPG). 2) For best of my knowledge, is policy gradient method always on-policy because the object of both sampling and control is $\pi_{\theta}$ under the same parameter space? So if I'm not wrong, how to do mini-batches without introducing a behavior policy?
Answers.UserDisplayName: Magi Feeney
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-18T06:43:47.287Z
Answers.Text: And I also wanna stress that you've concluded at the beginning with the statement **It will definitely increase sample efficiency over the strictly on-policy case**,  however, your explanation right after mainly focuses on the off-policy case where can attain sample efficiency by runing many epoches, but not directly aids the conclusion of on-policy case.
Answers.UserDisplayName: Magi Feeney
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T23:25:04.770Z
Answers.Text: my answer explains what is meant by 'off policy' in the context of the PPO algorithm (which is mentioned in your title, and is essentially the successor to TRPO). I'm not exactly sure what purpose importance sampling serves in TRPO.
Answers.UserDisplayName: Taw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T22:57:25.150Z
Answers.LastActivityDate: 2023-01-21T17:48:31.180Z
Answers.LastEditDate: 2023-01-21T17:48:31.180Z
Answers.UserDisplayName: Taw
Body: <p>Vanilla policy gradient has a loss function:</p>
  <p><span class="math-container">$$\mathcal{L}_{\pi_{\theta}(\theta)} = E_{\tau \sim \pi_{\theta}}[\sum\limits_{t = 0}^{\infty}\gamma^{t}r_{t}]$$</span></p>
  <p>while in TRPO it is:</p>
  <p><span class="math-container">$$\mathcal{L}_{\pi_{\theta_{old}}(\theta)} = \frac{1}{1 - \gamma}E_{s, a \sim \pi_{\theta_{old}}}[\frac{\pi_{\theta}(a|s)}{\pi_{\theta_{old}(a|s)}}A^{\pi_{\theta_{old}}}(s,a)]$$</span></p>
  <p>There exists some problems of vanilla policy gradient, such that distance dismatch between parameter space and policy space and suffering poor sample efficiency.</p>
  <p>For tackling this problem, TRPO introduces importance sampling for improving this. However, when I compared the pseudocode of two algorithms, I don't see any obvious evidence that aids the point. They all firstly sampled multiple trajectories under the current policy. The former then just uses the estimated gradient of loss function to update the parameter <span class="math-container">$\theta$</span>. The latter also uses the estimated gradient but under the KL constraint to update the parameter <span class="math-container">$\theta$</span>. It looks like they are almost the same procedure but with some subtle difference of the optimization process.</p>
  <p>My question is - should it be more accurate to say that importance sampling just increases the stability of the sequential decision making process, or rather, avoid update too aggressively, but not directly improves the sample efficiency?</p>
  <p>Pseudocode of two algorithms (source from OpenAI spinning up document)</p>
  <p><a href="https://i.sstatic.net/87gBH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/87gBH.png" alt="enter image description here" /></a></p>
  <p><a href="https://i.sstatic.net/QKozg.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/QKozg.png" alt="enter image description here" /></a></p>
  
Tags: <reinforcement-learning><policy-gradients><importance-sampling><trust-region-policy-optimization><sample-efficiency>
Title: Does importance sampling really improve sampling efficiency of TRPO or PPO?
UserDisplayName: Magi Feeney
ThreadText: # Does importance sampling really improve sampling efficiency of TRPO or PPO?
  
  (Asked by: username_0 on 2022-02-16)
  
  Vanilla policy gradient has a loss function:
  
  $$\mathcal{L}\_{\pi\_{\theta}(\theta)} = E\_{\tau \sim \pi\_{\theta}}[\sum\limits\_{t = 0}^{\infty}\gamma^{t}r\_{t}]$$
  
  while in TRPO it is:
  
  $$\mathcal{L}\_{\pi\_{\theta\_{old}}(\theta)} = \frac{1}{1 - \gamma}E\_{s, a \sim \pi\_{\theta\_{old}}}[\frac{\pi\_{\theta}(a|s)}{\pi\_{\theta\_{old}(a|s)}}A^{\pi\_{\theta\_{old}}}(s,a)]$$
  
  There exists some problems of vanilla policy gradient, such that distance dismatch between parameter space and policy space and suffering poor sample efficiency.
  
  For tackling this problem, TRPO introduces importance sampling for improving this. However, when I compared the pseudocode of two algorithms, I don't see any obvious evidence that aids the point. They all firstly sampled multiple trajectories under the current policy. The former then just uses the estimated gradient of loss function to update the parameter $\theta$. The latter also uses the estimated gradient but under the KL constraint to update the parameter $\theta$. It looks like they are almost the same procedure but with some subtle difference of the optimization process.
  
  My question is - should it be more accurate to say that importance sampling just increases the stability of the sequential decision making process, or rather, avoid update too aggressively, but not directly improves the sample efficiency?
  
  Pseudocode of two algorithms (source from OpenAI spinning up document)
  
  [![enter image description here](https://i.sstatic.net/87gBH.png)](https://i.sstatic.net/87gBH.png)
  
  [![enter image description here](https://i.sstatic.net/QKozg.png)](https://i.sstatic.net/QKozg.png)
  
  **Tags:** reinforcement-learning, policy-gradients, importance-sampling, trust-region-policy-optimization, sample-efficiency
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-17. Score: 2
  
  The point of importance sampling is to use the same episode(s) to do multiple policy gradient updates. It will definitely increase sample efficiency over the strictly on-policy case, simply because in an off-policy algorithm we can use a single transition to do multiple updates, whereas we only get a single update from that same experience in the on-policy case.
  
  First of all, in the pseudocode for TRPO that you give, I see no importance sampling being done, and the pseudocode makes it seem that the algorithm is being done on-policy.
  
  Basically, an on-policy algorithm would look like:
  
  \begin{align\*}
  & \text{ for each iteration }: \\
  & \qquad \text{ for t in range(n)}: \\
  & \qquad \qquad \text{sample } a\_t; \text{ get reward } r\_t \text{ and next state } s\_{t+1} \\
  & \qquad \text{ do policy update based on } a\_1, r\_1, s\_2, a\_2, \ldots
  \end{align\*}
  
  whereas an off-policy algorithm is like
  
  \begin{align\*}
  & \text{ for each iteration }: \\
  & \qquad \text{ for t in range(n)}: \\
  & \qquad \qquad \text{sample } a\_t; \text{ get reward } r\_t \text{ and next state } s\_{t+1} \\
  & \qquad \text{ for m epochs}: \\
  & \qquad \qquad \text{ for k mini-batches}: \\
  & \qquad \qquad \qquad \text{make mini batch from} \{a\_1, r\_1, s\_2, a\_2, \ldots\} \text{ and do policy gradient update }
  \end{align\*}
  
  So, in an off-policy algorithm, you may have something like $m=10$ (10 epochs), meaning every transition you do gets used in 10 policy gradient updates. An on policy algorithm would only use that transition once.
  
  > **Comments:**
  > **username_0**: This clarifies a lot. But  I still have some problems. 1) TRPO is a on-policy method for sure, for which it confuses me a lot that how is sample efficiency attained without doing multiple update like the off-policy method does (seems no essential difference bewteen VPG). 2) For best of my knowledge, is policy gradient method always on-policy because the object of both sampling and control is $\pi_{\theta}$ under the same parameter space? So if I'm not wrong, how to do mini-batches without introducing a behavior policy?  
  > **username_0**: And I also wanna stress that you've concluded at the beginning with the statement **It will definitely increase sample efficiency over the strictly on-policy case**,  however, your explanation right after mainly focuses on the off-policy case where can attain sample efficiency by runing many epoches, but not directly aids the conclusion of on-policy case.  
  > **username_1**: my answer explains what is meant by 'off policy' in the context of the PPO algorithm (which is mentioned in your title, and is essentially the successor to TRPO). I'm not exactly sure what purpose importance sampling serves in TRPO.  
  
  ---
  
  