Derivation of Monte Carlo Policy Gradient for REINFORCE

Question

On page 270 of this draft of Intro to Reinforcement Learning by Sutton and Burton, the authors simplify the policy gradient as follows:

Since the action-value function equals the conditional expectation of the cumulative reward, the intermediate step in moving from line 2 to 3 is presumably:

Why can you just drop the inner expectation to arrive at line 3?

Answer 1

In my proof I use related random variables as the subscript of expectations rather than the policy $\pi$. It may make the expressions look more complicated but it makes the notion more clear.

---

The proof is based on two facts:

Fact 1.

$$ y\mathbb{E}_{X|Y=y}[X|Y=y]=\mathbb{E}_{X|Y=y}[Xy|Y=y] $$

The left part is actually a function of $y$ so in $\mathbb{E}_{X|Y=y}[\cdot]$'s view $y$ is a constant. Thus it can be put into the expectation by linearity. You can also prove it easily as below: $$ \begin{align} y\mathbb{E}[X|Y=y]&=y\sum_xp_{X|Y=y}(x|y)x\\ &=\sum_xp_{X|Y=y}(x|y)xy\\ &=\mathbb{E}[Xy|Y=y]\\ \end{align} $$

Fact 2.

$$ \mathbb{E}_X[\mathbb{E}_{Y|X}[g(X,Y)|X]]=\mathbb{E}_{X,Y}[g(X,Y)] $$

It is a generalization of the Law of Total Expectation. You can also easily prove it as below: $$ \begin{align} \mathbb{E}_X[\mathbb{E}_{Y|X}[g(X,Y)|X]]&=\sum_xp_X(x)\mathbb{E}_{Y|X=x}[g(x,Y)|X=x]\\ &=\sum_xp_X(x)\sum_yp_{Y|X=x}(y|x)g(x,y)\\ &=\sum_x\sum_yp_X(x)p_{Y|X=x}(y|x)g(x,y)\\ &=\sum_x\sum_yp_{X,Y}(x,y)g(x,y)\\ &=\mathbb{E}_{X,Y}[g(X,Y)] \end{align} $$

The final proof.

$$ \begin{align} \nabla J(\theta)&=\mathbb{E}_{S_t,A_t}\left[q_\pi(S_t,A_t)\nabla\ln\pi_\theta(A_t|S_t)\right]\\ &=\mathbb{E}_{S_t,A_t}\Big[\mathbb{E}_{G_t|S_t,A_t}[G_t|S_t,A_t]\nabla\ln\pi_\theta(A_t|S_t)\Big]\tag{Definition of $q$}\\ &=\mathbb{E}_{S_t,A_t}\Big[\mathbb{E}_{G_t|S_t,A_t}\big[G_t\nabla\ln\pi_\theta(A_t|S_t)|S_t,A_t\big]\Big]\tag{Fact 1.}\\ &=\mathbb{E}_{G_t,S_t,A_t}\big[G_t\nabla\ln\pi_\theta(A_t|S_t)\big]\tag{Fact 2.} \end{align} $$

(Note: for applying fact 2, here $(S_t,A_t)$ is the $X$, and $G_t$ is the $Y$.)

Answer 2

The expectation of an expectation of a random variable (using the same assumptions, such as following the policy as here) is the same as the expectation of the random variable.

$$\mathbb{E}[\mathbb{E}[X|Y]] = \mathbb{E}[X]$$

(provided $X$ and $Y$ are drawn from same probability space)

This rule appears with various names, but Wikipedia has it as the law of total expectation.