Answers.Body: <p>As you point out, they are not equivalent. I guess you could store the time index for each state visited, but there are two problems with this. </p>
  
  <p>First, if you sample states according to their time index, sampling from the replay memory will become more cumbersome and probably much slower (you'd have to sample the time index and then a specific state with that time index). This is definitely something undesirable. If you choose to add the importance sampling term, then you will make really small most of the terms if <span class="math-container">$\gamma$</span> is not so close to 1. </p>
  
  <p>Second, while the original objective is very nice to obtain theoretical results, you may ask yourself if that objective is really what you want to maximize. Do you really care more about the performance at the beginning of the trajectory than at the end? </p>
  
  <p>While I have no rigorous proofs, I like to think that a better definition for the expected discounted reward is a time average:</p>
  
  <p><span class="math-container">$$\eta(\pi) = \lim_{N\to\infty}\frac{1}{N}\sum_{k=1}^N\mathbb E_{s_k,a_k,s_{k+1},\cdots}\left[\sum_{t=k}^\infty\gamma^{t-k}r(s_t)\right].$$</span></p>
  
  <p>Since each term of the average satisfies the original proofs, the only difference with the equation 14 is that the density is <span class="math-container">$\tilde\rho_{\theta_{old}}(s) = \lim_{N\to\infty}\frac{1}{N}\sum_{k=1}^N\rho_{k,\theta_{old}}(s)$</span>, where <span class="math-container">$$\rho_{k,\theta_{old}} = P(s_k = s)+\gamma P(s_{k+1}=s) + \gamma^2 P(s_{k+2}=s) + \dots.$$</span>
  You can notice that for a large <span class="math-container">$N$</span> you basically give the same importance to all of the time-steps. So, the usual implementations actually optimize some complicated function similar to the one I defined, where you give a similar weight to all samples, irrespective of their corresponding time-step.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-01T08:04:21.403Z
Answers.LastActivityDate: 2019-12-01T08:04:21.403Z
Answers.UserDisplayName: Diego Gomez
Body: <p>In the <a href="https://arxiv.org/pdf/1502.05477.pdf" rel="nofollow noreferrer">TRPO paper</a>, the objective to maximize is (equation 14)
  <span class="math-container">$$
  \mathbb{E}_{s\sim\rho_{\theta_\text{old}},a\sim q}\left[\frac{\pi_\theta(a|s)}{q(a|s)} Q_{\theta_\text{old}}(s,a) \right]
  $$</span></p>
  
  <p>which involves an expectation over states sampled with some density <span class="math-container">$\rho$</span>, itself defined as
  <span class="math-container">$$
  \rho_\pi(s) = P(s_0 = s)+\gamma P(s_1=s) + \gamma^2 P(s_2=s) + \dots
  $$</span></p>
  
  <p>This seems to suggest that later timesteps should be sampled less often than earlier timesteps, or equivalently sampling states uniformly in trajectories but adding an importance sampling term <span class="math-container">$\gamma^t$</span>.</p>
  
  <p>However, the usual implementations simply use batches made of truncated or concatenated trajectories, without any reference to the location of the timesteps in the trajectory.</p>
  
  <p>This is similar to what can be seen in the <a href="https://arxiv.org/pdf/1707.06347.pdf" rel="nofollow noreferrer">PPO paper</a>, which transforms the above objective into (equation 3)
  <span class="math-container">$$
  \mathbb{E}_t \left[ \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_\text{old}}(a_t|s_t)} \hat A_t \right]
  $$</span></p>
  
  <p>It seems that something is missing in going from <span class="math-container">$\mathbb{E}_{s\sim \rho}$</span> to <span class="math-container">$\mathbb{E}_t$</span> in the discounted setting.
  Are they really equivalent?</p>
  
Tags: <reinforcement-learning><policy-gradients><proximal-policy-optimization><trust-region-policy-optimization>
Title: Are these two TRPO objective functions equivalent?
UserDisplayName: udscbt
ThreadText: # Are these two TRPO objective functions equivalent?
  
  (Asked by: username_0 on 2019-10-07)
  
  In the [TRPO paper](https://arxiv.org/pdf/1502.05477.pdf), the objective to maximize is (equation 14)
  $$
  \mathbb{E}\_{s\sim\rho\_{\theta\_\text{old}},a\sim q}\left[\frac{\pi\_\theta(a|s)}{q(a|s)} Q\_{\theta\_\text{old}}(s,a) \right]
  $$
  
  which involves an expectation over states sampled with some density $\rho$, itself defined as
  $$
  \rho\_\pi(s) = P(s\_0 = s)+\gamma P(s\_1=s) + \gamma^2 P(s\_2=s) + \dots
  $$
  
  This seems to suggest that later timesteps should be sampled less often than earlier timesteps, or equivalently sampling states uniformly in trajectories but adding an importance sampling term $\gamma^t$.
  
  However, the usual implementations simply use batches made of truncated or concatenated trajectories, without any reference to the location of the timesteps in the trajectory.
  
  This is similar to what can be seen in the [PPO paper](https://arxiv.org/pdf/1707.06347.pdf), which transforms the above objective into (equation 3)
  $$
  \mathbb{E}\_t \left[ \frac{\pi\_\theta(a\_t|s\_t)}{\pi\_{\theta\_\text{old}}(a\_t|s\_t)} \hat A\_t \right]
  $$
  
  It seems that something is missing in going from $\mathbb{E}\_{s\sim \rho}$ to $\mathbb{E}\_t$ in the discounted setting.
  Are they really equivalent?
  
  **Tags:** reinforcement-learning, policy-gradients, proximal-policy-optimization, trust-region-policy-optimization
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-12-01. Score: 1
  
  As you point out, they are not equivalent. I guess you could store the time index for each state visited, but there are two problems with this.
  
  First, if you sample states according to their time index, sampling from the replay memory will become more cumbersome and probably much slower (you'd have to sample the time index and then a specific state with that time index). This is definitely something undesirable. If you choose to add the importance sampling term, then you will make really small most of the terms if $\gamma$ is not so close to 1.
  
  Second, while the original objective is very nice to obtain theoretical results, you may ask yourself if that objective is really what you want to maximize. Do you really care more about the performance at the beginning of the trajectory than at the end?
  
  While I have no rigorous proofs, I like to think that a better definition for the expected discounted reward is a time average:
  
  $$\eta(\pi) = \lim\_{N\to\infty}\frac{1}{N}\sum\_{k=1}^N\mathbb E\_{s\_k,a\_k,s\_{k+1},\cdots}\left[\sum\_{t=k}^\infty\gamma^{t-k}r(s\_t)\right].$$
  
  Since each term of the average satisfies the original proofs, the only difference with the equation 14 is that the density is $\tilde\rho\_{\theta\_{old}}(s) = \lim\_{N\to\infty}\frac{1}{N}\sum\_{k=1}^N\rho\_{k,\theta\_{old}}(s)$, where $$\rho\_{k,\theta\_{old}} = P(s\_k = s)+\gamma P(s\_{k+1}=s) + \gamma^2 P(s\_{k+2}=s) + \dots.$$
  You can notice that for a large $N$ you basically give the same importance to all of the time-steps. So, the usual implementations actually optimize some complicated function similar to the one I defined, where you give a similar weight to all samples, irrespective of their corresponding time-step.
  
  
  ---
  
  