# Proof of gradient of $v_{\pi}(s)$ via Kronecker Product

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. 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?

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').$$