Answers.Body: <p>For the question mark,</p>
  <p><span class="math-container">\begin{align}
  \sum_{a\in A}\pi(a\mid s,\theta)\sum_{s'\in S}p(s'\mid s,a)\nabla_{\theta}v_{\pi}(s'))&amp;=\sum_{s'\in S}\left(\sum_{a\in A} p(s'\mid s,a)\pi(a\mid s,\theta)\right)\nabla_{\theta}v_{\pi}(s')) \\
  &amp;=\sum_{s'\in S}p(s'\mid s,\theta)\nabla_{\theta}v_{\pi}(s')),
  \end{align}</span></p>
  <p>For the second part, I don't think it is particularly instructive to think in terms of matrices, as that proof only works for discrete state spaces, but here is the idea.</p>
  <p>For each <span class="math-container">$s\in S$</span> fixed, the gradient is an <span class="math-container">$m$</span>-dimensional vector <span class="math-container">$$\nabla_{\theta}v_{\pi_{\theta}}(s)=(\frac{\partial }{\partial \theta_1}v_{\pi_{\theta}}(s),\cdots, \frac{\partial }{\partial \theta_m}v_{\pi_{\theta}}(s))^\top. $$</span></p>
  <p>Now, we do this for each of the points, which gives a collection of vectors  <span class="math-container">$$\nabla_{\theta} v_{\pi_{\theta}}=\left(\nabla_{\theta} v_{\pi_{\theta}}(s_1), \cdots, \nabla_{\theta} v_{\pi_{\theta}}(s_n)\right).$$</span></p>
  <p>So, they essentially stack <span class="math-container">$v_{\pi_{\theta}}$</span> in a vertical vector of dimension <span class="math-container">$mn$</span>, so that</p>
  <p><span class="math-container">$$ \nabla_{\theta}v_{\pi_{\theta}} = \left(\frac{\partial }{\partial \theta_1}v_{\pi_{\theta}}(s_1), \cdots, \frac{\partial }{\partial \theta_m}v_{\pi_{\theta}}(s_1), \cdots, \frac{\partial }{\partial \theta_1}v_{\pi_{\theta}}(s_n), \cdots, \frac{\partial }{\partial \theta_m}v_{\pi_{\theta}}(s_n)\right)^\top. $$</span></p>
  <p>However, the matrix <span class="math-container">$P_{\pi}$</span> is an <span class="math-container">$n\times n$</span> matrix, corresponding to</p>
  <p><span class="math-container">\begin{pmatrix} p(s'_1\mid s_1, \theta) &amp;\cdots &amp; p(s'_n\mid s_1,\theta) \\ \vdots&amp; &amp; \vdots\\ p(s_1'\mid s_n,\theta) &amp; \cdots &amp;p(s_n'\mid s_n,\theta)\end{pmatrix}</span></p>
  <p>As you see the dimensions don't add up if we want to multiply it by an <span class="math-container">$nm$</span>-vector. The idea of the Kronecker product is to ensure that the dimensions add up, so we get a <span class="math-container">$nm\times nm$</span> matrix. In this case, we get a matrix with lots of zeroes as you wrote. The idea is that for each <span class="math-container">$i$</span> and <span class="math-container">$s$</span>
  <span class="math-container">$$ \frac{\partial}{\partial \theta_i}v_{\pi_{\theta}}(s)=\sum_{s'\in S}p(s'\mid s, \theta)\frac{\partial}{\partial \theta_i}v_{\pi_{\theta}}(s').$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-05T16:01:33.627Z
Answers.LastActivityDate: 2024-07-05T16:25:18.643Z
Answers.LastEditDate: 2024-07-05T16:25:18.643Z
Answers.UserDisplayName: matorbi
Body: <p>Hi I am reading Mathematical Foundation of Reinforcement Learning by Shiyu Zhao and I try to understand a proof regarding policy gradients. The part is on page 209/210 in <a href="https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning/blob/main/3%20-%20Chapter%209%20Policy%20Gradient%20Methods.pdf" rel="nofollow noreferrer">Policy Gradient Methods</a>. First I don't understand the equation I marked with the question mark. Next I also don't understand the matrix vector form. I am a bit confused in the order of the entries in the <span class="math-container">$\nabla_{\theta}v_{\pi}$</span> vector. I made an example to understand the calculation with two states <span class="math-container">$s_1$</span> and <span class="math-container">$s_2$</span> and two parameters/weights <span class="math-container">$\theta_1$</span> and <span class="math-container">$\theta_2$</span>.</p>
  <p><span class="math-container">$$
  (\begin{bmatrix}
  p_{11} &amp; p_{12}\\
  p_{21} &amp; p_{22}
  \end{bmatrix} \otimes
  \begin{bmatrix}
  1 &amp; 0\\
  0 &amp; 1
  \end{bmatrix})
  \begin{bmatrix}
  \nabla_{\theta_{1}}v_{\pi}(s_{1})\\
  \nabla_{\theta_{1}}v_{\pi}(s_{2})\\
  \nabla_{\theta_{2}}v_{\pi}(s_{1})\\
  \nabla_{\theta_{2}}v_{\pi}(s_{2})
  \end{bmatrix} =
  \begin{bmatrix}
  p_{11} &amp; 0 &amp; p_{12} &amp; 0\\
  0 &amp; p_{11} &amp; 0 &amp; p_{12}\\
  p_{21} &amp; 0 &amp; p_{22} &amp; 0\\
  0 &amp; p_{21} &amp; 0 &amp; p_{22}
  \end{bmatrix}
  \begin{bmatrix}
  \nabla_{\theta_{1}}v_{\pi}(s_{1})\\
  \nabla_{\theta_{1}}v_{\pi}(s_{2})\\
  \nabla_{\theta_{2}}v_{\pi}(s_{1})\\
  \nabla_{\theta_{2}}v_{\pi}(s_{2})
  \end{bmatrix}
  $$</span></p>
  <p>Would my calculation be correct here?</p>
  <p><a href="https://i.sstatic.net/oLG4cbA4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oLG4cbA4.png" alt="enter image description here" /></a>
  <a href="https://i.sstatic.net/z1wzCdC5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/z1wzCdC5.png" alt="enter image description here" /></a></p>
  
Tags: <reinforcement-learning><policy-gradients><proofs>
Title: Proof of gradient of $v_{\pi}(s)$ via Kronecker Product
UserDisplayName: craaaft
ThreadText: # Proof of gradient of $v_{\pi}(s)$ via Kronecker Product
  
  (Asked by: username_0 on 2024-05-27)
  
  Hi I am reading Mathematical Foundation of Reinforcement Learning by Shiyu Zhao and I try to understand a proof regarding policy gradients. The part is on page 209/210 in [Policy Gradient Methods](https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning/blob/main/3%20-%20Chapter%209%20Policy%20Gradient%20Methods.pdf). First I don't understand the equation I marked with the question mark. Next I also don't understand the matrix vector form. I am a bit confused in the order of the entries in the $\nabla\_{\theta}v\_{\pi}$ vector. I made an example to understand the calculation with two states $s\_1$ and $s\_2$ and two parameters/weights $\theta\_1$ and $\theta\_2$.
  
  $$
  (\begin{bmatrix}
  p\_{11} & p\_{12}\\
  p\_{21} & p\_{22}
  \end{bmatrix} \otimes
  \begin{bmatrix}
  1 & 0\\
  0 & 1
  \end{bmatrix})
  \begin{bmatrix}
  \nabla\_{\theta\_{1}}v\_{\pi}(s\_{1})\\
  \nabla\_{\theta\_{1}}v\_{\pi}(s\_{2})\\
  \nabla\_{\theta\_{2}}v\_{\pi}(s\_{1})\\
  \nabla\_{\theta\_{2}}v\_{\pi}(s\_{2})
  \end{bmatrix} =
  \begin{bmatrix}
  p\_{11} & 0 & p\_{12} & 0\\
  0 & p\_{11} & 0 & p\_{12}\\
  p\_{21} & 0 & p\_{22} & 0\\
  0 & p\_{21} & 0 & p\_{22}
  \end{bmatrix}
  \begin{bmatrix}
  \nabla\_{\theta\_{1}}v\_{\pi}(s\_{1})\\
  \nabla\_{\theta\_{1}}v\_{\pi}(s\_{2})\\
  \nabla\_{\theta\_{2}}v\_{\pi}(s\_{1})\\
  \nabla\_{\theta\_{2}}v\_{\pi}(s\_{2})
  \end{bmatrix}
  $$
  
  Would my calculation be correct here?
  
  [![enter image description here](https://i.sstatic.net/oLG4cbA4.png)](https://i.sstatic.net/oLG4cbA4.png)
  [![enter image description here](https://i.sstatic.net/z1wzCdC5.png)](https://i.sstatic.net/z1wzCdC5.png)
  
  **Tags:** reinforcement-learning, policy-gradients, proofs
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-07-05. Score: 1 | Accepted answer
  
  For the question mark,
  
  \begin{align}
  \sum\_{a\in A}\pi(a\mid s,\theta)\sum\_{s'\in S}p(s'\mid s,a)\nabla\_{\theta}v\_{\pi}(s'))&=\sum\_{s'\in S}\left(\sum\_{a\in A} p(s'\mid s,a)\pi(a\mid s,\theta)\right)\nabla\_{\theta}v\_{\pi}(s')) \\
  &=\sum\_{s'\in S}p(s'\mid s,\theta)\nabla\_{\theta}v\_{\pi}(s')),
  \end{align}
  
  For the second part, I don't think it is particularly instructive to think in terms of matrices, as that proof only works for discrete state spaces, but here is the idea.
  
  For each $s\in S$ fixed, the gradient is an $m$-dimensional vector $$\nabla\_{\theta}v\_{\pi\_{\theta}}(s)=(\frac{\partial }{\partial \theta\_1}v\_{\pi\_{\theta}}(s),\cdots, \frac{\partial }{\partial \theta\_m}v\_{\pi\_{\theta}}(s))^\top. $$
  
  Now, we do this for each of the points, which gives a collection of vectors $$\nabla\_{\theta} v\_{\pi\_{\theta}}=\left(\nabla\_{\theta} v\_{\pi\_{\theta}}(s\_1), \cdots, \nabla\_{\theta} v\_{\pi\_{\theta}}(s\_n)\right).$$
  
  So, they essentially stack $v\_{\pi\_{\theta}}$ in a vertical vector of dimension $mn$, so that
  
  $$ \nabla\_{\theta}v\_{\pi\_{\theta}} = \left(\frac{\partial }{\partial \theta\_1}v\_{\pi\_{\theta}}(s\_1), \cdots, \frac{\partial }{\partial \theta\_m}v\_{\pi\_{\theta}}(s\_1), \cdots, \frac{\partial }{\partial \theta\_1}v\_{\pi\_{\theta}}(s\_n), \cdots, \frac{\partial }{\partial \theta\_m}v\_{\pi\_{\theta}}(s\_n)\right)^\top. $$
  
  However, the matrix $P\_{\pi}$ is an $n\times n$ matrix, corresponding to
  
  \begin{pmatrix} p(s'\_1\mid s\_1, \theta) &\cdots & p(s'\_n\mid s\_1,\theta) \\ \vdots& & \vdots\\ p(s\_1'\mid s\_n,\theta) & \cdots &p(s\_n'\mid s\_n,\theta)\end{pmatrix}
  
  As you see the dimensions don't add up if we want to multiply it by an $nm$-vector. The idea of the Kronecker product is to ensure that the dimensions add up, so we get a $nm\times nm$ matrix. In this case, we get a matrix with lots of zeroes as you wrote. The idea is that for each $i$ and $s$
  $$ \frac{\partial}{\partial \theta\_i}v\_{\pi\_{\theta}}(s)=\sum\_{s'\in S}p(s'\mid s, \theta)\frac{\partial}{\partial \theta\_i}v\_{\pi\_{\theta}}(s').$$
  
  
  ---
  
  