How is the state-value function expressed as a product of sums?

Question

The state-value function for a given policy $\pi$ is given by

$$\begin{align} V^{\pi}(s) &=E_{\pi}\left\{r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\cdots \mid s_{t}=s\right\} \\ &=E_{\pi}\left\{r_{t+1}+\gamma V^{\pi}\left(s_{t+1}\right) \mid s_{t}=s\right\} \tag{4.3}\label{4.3} \\ &=\sum_{a} \pi(s, a) \sum_{s^{\prime}} \mathcal{P}_{s s^{\prime}}^{a}\left[\mathcal{R}_{s s^{\prime}}^{a}+\gamma V^{\pi}\left(s^{\prime}\right)\right] \tag{4.4}\label{4.4} \end{align}$$

It is given in section 4.1 of the first edition of Sutton and Barto's book (equations 4.3 and 4.4).

I don't understand how equation \ref{4.4} derives from equation \ref{4.3}. How can I get the product in equation \ref{4.4} from the expectation in equation \ref{4.3}?

Answer 1

A quick review of resolving expectations: If you know that a discrete random variable $X$, drawn from set $\mathcal{X}$ has probability distribution $p(x) = \mathbf{Pr}\{X=x \}$, then

$$\mathbb{E}[X] = \sum_{x \in \mathcal{X}} xp(x)$$

This equation is the core of what is going on when resolving the expectation in your quoted equation.

Resolving the expectation to show how the value function of a state relates to the possible next rewards and future states means summing up all possible rewards and next states. There are two components to the distribution over the single step involved - the policy $\pi(a|s)$, and the state progression $P^a_{ss'}$. As they are both independent probabilities, they need to be multiplied to establish the combined probability of any specific trajectory.

So, looking at only a single trajectory starting from state $s$, the trajectory of selecting action $a$ and ending up in state $s'$ has a probability of:

$$p_{\pi}(a,s'|s) = \pi(a|s) P^a_{ss'}$$

Iterating over all possible trajectories to get the expected value of some function of the end of the trajectory $f(s,a,s')$ looks like this:

$$\mathbb{E}[f(S_t, A_t, S_{t+1})|S_t=s] = \sum_a \pi(a|s)\sum_{s'}P_{ss'}^a f(s,a,s')$$

It is important to note that the sums are nested here, not separately resolved then multiplied. This is standard notation, but you could add some brackets to show it:

$$\mathbb{E}[f(S_t, A_t, S_{t+1})|S_t=s] = \sum_a \pi(a|s)\left(\sum_{s'}\left(P_{ss'}^a f(s,a,s')\right)\right)$$

In the equation from the book, $f(s,a,s') = R_{ss'}^a + \gamma v_{\pi}(s')$