Answers.Body: <p>The answer is: <span class="math-container">$\sum_{s} \eta(s)$</span> is <strong>not a constant</strong> with regards to <span class="math-container">$\theta$</span>. As you already mentioned
  <span class="math-container">\begin{equation}
  \sum_{k=0}^{\infty} \text{Pr}(s_{0}\rightarrow s, k, \pi) = \eta(s).
  \end{equation}</span>
  But then the question arises: Why is the derivation you showed correct? It's not the point that <span class="math-container">$\sum_{s} \eta(s)$</span> is constant in regards to <span class="math-container">$\theta$</span> and is therefore not affected by the <span class="math-container">$\nabla$</span> operator but quite the contrary: That it is the result of applying the <span class="math-container">$\nabla$</span> operator to the state value function. If you just look at the <em>Proof of the Policy Gradient Theorem (episodic case)</em> in Sutton-Barto at the simplification of <span class="math-container">$\nabla v_{\pi}(s)$</span> you will find that (not showing all steps here):
  <span class="math-container">\begin{align}
  \nabla v_{\pi}(s) &amp;= \nabla \left[ \sum_{a} \pi(a|s)q_{\pi}(s, a) \right] &amp;\text{for all s} \in S \\
  &amp;=~... \\
  &amp;= \sum_{a}\left[\nabla \pi(a|s) q_{\pi}(s, a) + \pi(a|s) \sum_{s'}p(s'|s,a)\nabla v_{\pi}(s')\right] &amp; (\text{using recursivity}) \\
  &amp;=\sum_{a}\left[\nabla \pi(a|s) q_{\pi}(s, a) + \pi(a|s) \sum_{s'}p(s'|s,a) \\ \sum_{a'}[\nabla \pi(a'|s')q_{\pi}(s', a') + \pi(a'|s')\sum_{s''}p(s''|s',a')\nabla v_{\pi}(s'')]\right] &amp; (\text{further unrolling}) \\
  &amp;= \sum_{x \in S}\sum_{k=0}^{\infty} \text{Pr}(s\rightarrow x, k, \pi)\sum_{a}\nabla \pi(a|x)q_{\pi}(x,a).
  \end{align}</span>
  Where <span class="math-container">$\text{Pr}(s\rightarrow x, k, \pi)$</span> is the probability of moving from state <span class="math-container">$s$</span> to state <span class="math-container">$x$</span> accounting for all intermediate states <span class="math-container">$s_{1}, s_{2}, ..., s_{k}$</span> by following policy <span class="math-container">$\pi$</span>.
  So we see, that this equation from which you start is the result NOT the target of a derivative.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-13T19:39:51.017Z
Answers.LastActivityDate: 2023-02-14T12:54:53.053Z
Answers.LastEditDate: 2023-02-14T12:54:53.053Z
Answers.UserDisplayName: pythonic833
Answers.Body: <p>Spitballing some ideas here -</p>
  <p>as <span class="math-container">$\pi_\theta$</span> is updated using some gradient optimization process with <em>small</em> steps in the direction of the gradient, the changes to state visits are generally small as well. If so, maybe we can assume that the state-visitation frequency <span class="math-container">$\eta(s)$</span> will not change significantly. To be precise, while <span class="math-container">$\eta(s)$</span> is in fact <span class="math-container">$\eta(s,\theta)$</span>, is it a valid assumption that when the step size is small enough, <span class="math-container">$\eta(s,\theta_t)\approx\eta(s,\theta_{t+1})$</span> for all <span class="math-container">$t$</span>.</p>
  <p>This may bring to mind a <em><a href="https://en.wikipedia.org/wiki/Quasistatic_process" rel="nofollow noreferrer">Quasistatic process</a></em>, which is a thermodynamic process that happens slowly enough for the system to remain in equilibrium, but hey thats just my intuition</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-12T09:25:48.287Z
Answers.Text: Thanks for your answer! Hmm, maybe that argument applies better to $\sum_s\eta(s)$. I read that $\eta(s)$ can be interpreted as the average time you spend in a state in one episode, which makes sense to me. Therefore, $\sum_s\eta(s)$ can be interpreted as the average time you spend in the episode. Maybe that doesn't change much in the sum, but the single $\eta(s)$ change more strongly. I am just wondering whether there is a strict mathematical argument for this. The book gives me the impression there is, but I didn't it in there nor by looking up other posts.
Answers.UserDisplayName: jwl17
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-12T08:11:36.250Z
Answers.LastActivityDate: 2023-01-12T08:11:36.250Z
Answers.UserDisplayName: Hadar Sharvit
Body: <p>In Sutton and Barto's book (<a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf" rel="nofollow noreferrer">http://incompleteideas.net/book/bookdraft2017nov5.pdf</a>), a proof  of the policy gradient theorem is provided on pg. 269 for an episodic case and a start state policy objective function (see picture below, last 3 equations).</p>
  <p><a href="https://i.sstatic.net/qWCuP.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qWCuP.png" alt="enter image description here" /></a></p>
  <p>Why can we assume that the sum <span class="math-container">$\sum_s\eta(s)$</span> is a constant of proportionality? Doesn't it also depend on <span class="math-container">$\theta$</span>, since it depends on the policy <span class="math-container">$\pi$</span>?</p>
  <p>What could make sense, would be to say that <span class="math-container">$\nabla J(\theta)  = \mathbb{E}_{s\sim \eta(s), a \sim \pi}\left[\nabla_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q_{\pi}(s,a)\right]\propto  \mathbb{E}_{s\sim d(s), a \sim \pi}\left[\nabla_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q_{\pi}(s,a)\right]$</span>.</p>
  <p>Since the proportionality constant is always <span class="math-container">$\ge 0$</span> (average time spent in an episode), any update direction suggested by <span class="math-container">$\mathbb{E}_{s\sim d(s), a \sim \pi}\left[\nabla_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q_{\pi}(s,a)\right]$</span> is the same as <span class="math-container">$\mathbb{E}_{s\sim \eta(s), a \sim \pi}\left[\nabla_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q_{\pi}(s,a)\right]$</span>, but with different amplitude. This, however, wouldn't impact the learning process too much, since we multiply the update term with a low learning rate anyway.</p>
  <p>Hence, as it is more easy to sample states from <span class="math-container">$d(s)$</span>, we just set <span class="math-container">$\nabla_{\theta} J = \mathbb{E}_{s\sim d(s), a \sim \pi}\left[\nabla_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q_{\pi}(s,a)\right]$</span>.</p>
  <p>Could that serve as plausible explanation?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-04-01T21:12:46.480Z
Comments.Text: The derivation answering your question is just above the expression on your screenshot.
Comments.UserDisplayName: Kostya
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-12T18:05:42.290Z
Comments.Text: Thanks for linking this post! I think what you say in your answer there in the second paragraph ("Moreover, ...") goes in the same direction as what I tried to explain in my own answer suggestion above. So, it doesn't matter if we take samples from $d$ or $\eta$ (or $\rho$ in the linked post), as they represent the same distribution, just scaled by a factor, right? I guess, that taking samples from $d$ is just more intuitive, as sampling from a probability distribution is more intuitive than sampling from something that is not, i.e., $\eta$.
Comments.UserDisplayName: jwl17
Tags: <reinforcement-learning><policy-gradients><proofs><sutton-barto><policy-gradient-theorem>
Title: Why is $\sum_{s} \eta(s)$ a constant of proportionality in the proof of the policy gradient theorem?
UserDisplayName: jwl17
ThreadText: # Why is $\sum_{s} \eta(s)$ a constant of proportionality in the proof of the policy gradient theorem?
  
  (Asked by: username_0 on 2023-01-11)
  
  In Sutton and Barto's book (<http://incompleteideas.net/book/bookdraft2017nov5.pdf>), a proof of the policy gradient theorem is provided on pg. 269 for an episodic case and a start state policy objective function (see picture below, last 3 equations).
  
  [![enter image description here](https://i.sstatic.net/qWCuP.png)](https://i.sstatic.net/qWCuP.png)
  
  Why can we assume that the sum $\sum\_s\eta(s)$ is a constant of proportionality? Doesn't it also depend on $\theta$, since it depends on the policy $\pi$?
  
  What could make sense, would be to say that $\nabla J(\theta) = \mathbb{E}\_{s\sim \eta(s), a \sim \pi}\left[\nabla\_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q\_{\pi}(s,a)\right]\propto \mathbb{E}\_{s\sim d(s), a \sim \pi}\left[\nabla\_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q\_{\pi}(s,a)\right]$.
  
  Since the proportionality constant is always $\ge 0$ (average time spent in an episode), any update direction suggested by $\mathbb{E}\_{s\sim d(s), a \sim \pi}\left[\nabla\_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q\_{\pi}(s,a)\right]$ is the same as $\mathbb{E}\_{s\sim \eta(s), a \sim \pi}\left[\nabla\_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q\_{\pi}(s,a)\right]$, but with different amplitude. This, however, wouldn't impact the learning process too much, since we multiply the update term with a low learning rate anyway.
  
  Hence, as it is more easy to sample states from $d(s)$, we just set $\nabla\_{\theta} J = \mathbb{E}\_{s\sim d(s), a \sim \pi}\left[\nabla\_{\theta}\mathrm{log}\left(\pi(s,a,\theta)\right)\,q\_{\pi}(s,a)\right]$.
  
  Could that serve as plausible explanation?
  
  **Tags:** reinforcement-learning, policy-gradients, proofs, sutton-barto, policy-gradient-theorem
  
  > **Comments:**
  > **username_0**: Thanks for linking this post! I think what you say in your answer there in the second paragraph ("Moreover, ...") goes in the same direction as what I tried to explain in my own answer suggestion above. So, it doesn't matter if we take samples from $d$ or $\eta$ (or $\rho$ in the linked post), as they represent the same distribution, just scaled by a factor, right? I guess, that taking samples from $d$ is just more intuitive, as sampling from a probability distribution is more intuitive than sampling from something that is not, i.e., $\eta$.  
  > **username_1**: The derivation answering your question is just above the expression on your screenshot.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-02-13. Score: 1
  
  The answer is: $\sum\_{s} \eta(s)$ is **not a constant** with regards to $\theta$. As you already mentioned
  \begin{equation}
  \sum\_{k=0}^{\infty} \text{Pr}(s\_{0}\rightarrow s, k, \pi) = \eta(s).
  \end{equation}
  But then the question arises: Why is the derivation you showed correct? It's not the point that $\sum\_{s} \eta(s)$ is constant in regards to $\theta$ and is therefore not affected by the $\nabla$ operator but quite the contrary: That it is the result of applying the $\nabla$ operator to the state value function. If you just look at the *Proof of the Policy Gradient Theorem (episodic case)* in Sutton-Barto at the simplification of $\nabla v\_{\pi}(s)$ you will find that (not showing all steps here):
  \begin{align}
  \nabla v\_{\pi}(s) &= \nabla \left[ \sum\_{a} \pi(a|s)q\_{\pi}(s, a) \right] &\text{for all s} \in S \\
  &=~... \\
  &= \sum\_{a}\left[\nabla \pi(a|s) q\_{\pi}(s, a) + \pi(a|s) \sum\_{s'}p(s'|s,a)\nabla v\_{\pi}(s')\right] & (\text{using recursivity}) \\
  &=\sum\_{a}\left[\nabla \pi(a|s) q\_{\pi}(s, a) + \pi(a|s) \sum\_{s'}p(s'|s,a) \\ \sum\_{a'}[\nabla \pi(a'|s')q\_{\pi}(s', a') + \pi(a'|s')\sum\_{s''}p(s''|s',a')\nabla v\_{\pi}(s'')]\right] & (\text{further unrolling}) \\
  &= \sum\_{x \in S}\sum\_{k=0}^{\infty} \text{Pr}(s\rightarrow x, k, \pi)\sum\_{a}\nabla \pi(a|x)q\_{\pi}(x,a).
  \end{align}
  Where $\text{Pr}(s\rightarrow x, k, \pi)$ is the probability of moving from state $s$ to state $x$ accounting for all intermediate states $s\_{1}, s\_{2}, ..., s\_{k}$ by following policy $\pi$.
  So we see, that this equation from which you start is the result NOT the target of a derivative.
  
  
  ---
  
  ### Answer by username_3 on 2023-01-12. Score: 0
  
  Spitballing some ideas here -
  
  as $\pi\_\theta$ is updated using some gradient optimization process with *small* steps in the direction of the gradient, the changes to state visits are generally small as well. If so, maybe we can assume that the state-visitation frequency $\eta(s)$ will not change significantly. To be precise, while $\eta(s)$ is in fact $\eta(s,\theta)$, is it a valid assumption that when the step size is small enough, $\eta(s,\theta\_t)\approx\eta(s,\theta\_{t+1})$ for all $t$.
  
  This may bring to mind a *[Quasistatic process](https://en.wikipedia.org/wiki/Quasistatic_process)*, which is a thermodynamic process that happens slowly enough for the system to remain in equilibrium, but hey thats just my intuition
  
  > **Comments:**
  > **username_0**: Thanks for your answer! Hmm, maybe that argument applies better to $\sum_s\eta(s)$. I read that $\eta(s)$ can be interpreted as the average time you spend in a state in one episode, which makes sense to me. Therefore, $\sum_s\eta(s)$ can be interpreted as the average time you spend in the episode. Maybe that doesn't change much in the sum, but the single $\eta(s)$ change more strongly. I am just wondering whether there is a strict mathematical argument for this. The book gives me the impression there is, but I didn't it in there nor by looking up other posts.  
  
  ---
  
  