Bellman equation derivation

Bellman equation for $v_{\pi }$.

We want to show $v_{\pi }(s)={\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$ for all states $s$.

The core idea of the proof is to use the law of total probability to go from marginal to conditional probabilities, and then invoke the Markov assumption.

Law of total probability

The law of total probability states that if $B$ is an event, and $C_1,\dots ,C_n$ are events that partition the sample space, then $Pr(B)=\sum _{j=1}^{n}Pr(B\cap C_j)=\sum _{j=1}^{n}Pr(B\mid C_j)Pr(C_j)$.

For fixed event $A$ with non-zero probability, the mapping $B\mapsto Pr(B\mid A)$ is another valid probability measure, so the law of total probability also applies to it. Define ${Pr}_A$ by ${Pr}_A(B):=Pr(B\mid A)$ for all events $B$. Now the law of total probability for ${Pr}_A$ states that ${Pr}_A(B)=\sum _{j=1}^n{Pr}_A(B\mid C_j){Pr}_A(C_j)$. We also have

${Pr}_A(B\mid C_j)=\frac{{Pr}_A(B\cap C_j)}{{Pr}_A(C_j)}=\frac{Pr(B\cap C_j\mid A)}{Pr(C_j\mid A)}=\frac{Pr(B\cap C_j\cap A)/Pr(A)}{Pr(C_j\cap A)/Pr(A)}=\frac{Pr(B\cap (C_j\cap A))}{Pr(C_j\cap A)}=Pr(B\mid C_j,A)$

So the law of total probability states that $Pr(B\mid A)=\sum _{j=1}^{n}Pr(B\mid C_j,A)Pr(C_j\mid A)$.

Now we see how the law of total probability interacts with conditional expectation. Let $X$ be a random variable. Then

$\mathbb{E}[X\mid A]={\sum }_{x}x\cdot Pr(X=x\mid A)={\sum }_{x}x{\sum }_{j}Pr(X=x\mid C_j,A)Pr(C_j\mid A)$

Here the event $X=x$ is playing the role of $B$ in the statement of the conditional law of total probability.

This is the basic trick of the proof; we keep conditioning on different things (actions, next states, rewards) and using the law of total probability.

Start of proof

By definition, $v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$. Now rewrite $G_t=R_{t+1}+\gamma G_{t+1}$ and use the linearity of expectation to get ${\mathbb{E}}_{\pi }[R_{t+1}\mid S_t=s]+\gamma {\mathbb{E}}_{\pi }[G_{t+1}\mid S_t=s]$. From here, we can work separately with ${\mathbb{E}}_{\pi }[R_{t+1}\mid S_t=s]$ and ${\mathbb{E}}_{\pi }[G_{t+1}\mid S_t=s]$ for a while.

Simplifying expectation for reward term

Using the law of total probability while conditioning over actions, we have

${\mathbb{E}}_{\pi }[R_{t+1}\mid S_t=s]={\sum }_{r}r\cdot Pr(R_{t+1}=r\mid S_t=s)={\sum }_{r}r{\sum }_{a}Pr(R_{t+1}=r\mid A_t=a,S_t=s)Pr(A_t=a\mid S_t=s)$

Using the convention that $Pr(A_t=a\mid S_t=s)=\pi (a\mid s)$, this becomes

${\mathbb{E}}_{\pi }[R_{t+1}\mid S_t=s]={\sum }_{r}r{\sum }_{a}Pr(R_{t+1}=r\mid A_t=a,S_t=s)\pi (a\mid s)$

Now we can reorder the sums to get

${\sum }_a\pi (a\mid s){\sum }_{r}rPr(R_{t+1}=r\mid A_t=a,S_t=s)$

Again, using the law of total probability (in its conjunction form) while conditioning this time over states, we have

${\sum }_a\pi (a\mid s){\sum }_{r}r{\sum }_{s^{\prime }}Pr(R_{t+1}=r,S_{t+1}=s^{\prime }\mid A_t=a,S_t=s)$

Reordering the sums, this becomes

${\sum }_a\pi (a\mid s){\sum }_{s^{\prime }}{\sum }_{r}Pr(R_{t+1}=r,S_{t+1}=s^{\prime }\mid A_t=a,S_t=s)r$

Sutton and Barto abbreviate $Pr(R_{t+1}=r,S_{t+1}=s^{\prime }\mid A_t=a,S_t=s)$ as $p(s^{\prime },r\mid s,a)$ (strictly speaking, we should track the timestep parameter $t$, but we will omit this detail here). We can also combine the nested sums ${\sum }_{s^{\prime }}{\sum }_r$ into a single sum that iterates over pairs $(s^{\prime },r)$. So we obtain

${\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)r$

This completes the part for ${\mathbb{E}}_{\pi }[R_{t+1}\mid S_t=s]$. In other words, we have shown that

${\mathbb{E}}_{\pi }[R_{t+1}\mid S_t=s]={\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)r$

Simplifying expression for return term

Now we do a similar series of steps for ${\mathbb{E}}_{\pi }[G_{t+1}\mid S_t=s]$. Conditioning over actions,

${\mathbb{E}}_{\pi }[G_{t+1}\mid S_t=s]={\sum }_{g}g\cdot Pr(G_{t+1}=g\mid S_t=s)={\sum }_{g}g{\sum }_{a}Pr(G_{t+1}=g\mid A_t=a,S_t=s)\pi (a\mid s)$

Rearranging sums, this is

${\sum }_a\pi (a\mid s){\sum }_{g}gPr(G_{t+1}=g\mid A_t=a,S_t=s)$

Conditioning over states and rewards, we have

${\sum }_a\pi (a\mid s){\sum }_{g}g{\sum }_{s^{\prime },r}Pr(G_{t+1}=g,S_{t+1}=s^{\prime },R_{t+1}=r\mid A_t=a,S_t=s)$

Now write $Pr(G_{t+1}=g,S_{t+1}=s^{\prime },R_{t+1}=r\mid A_t=a,S_t=s)$ as $Pr(G_{t+1}=g\mid S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)Pr(S_{t+1}=s^{\prime },R_{t+1}=r\mid A_t=a,S_t=s)$. Since $Pr(S_{t+1}=s^{\prime },R_{t+1}=r\mid A_t=a,S_t=s)=p(s^{\prime },r\mid s,a)$ we have $Pr(G_{t+1}=g,S_{t+1}=s^{\prime },R_{t+1}=r\mid A_t=a,S_t=s)=Pr(G_{t+1}=g\mid S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)p(s^{\prime },r\mid s,a)$. Thus, substituting this expression and rearranging sums, we have

${\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a){\sum }_{g}gPr(G_{t+1}=g\mid S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)$

This is basically what we want, except we want to say that ${\sum }_{g}gPr(G_{t+1}=g\mid S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)={\mathbb{E}}_{\pi }[G_{t+1}\mid S_{t+1}=s^{\prime }]$, since the latter expression equals $v_{\pi }(s^{\prime })$. Thankfully, we can say this, because of the Markov assumption. Actually proving this is a little complicated; see the section at the end of this page.

So we end up with

${\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)v_{\pi }(s^{\prime })$

Finishing the proof

So now we have

$\begin{array}{rr}{v}_{\pi }(s)& ={\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s\text{'},r\mid s,a)r+\gamma {\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s\text{'},r\mid s,a)v_{\pi }(s\text{'})\\ & ={\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s\text{'},r\mid s,a)[r+\gamma v_{\pi }(s\text{'})]\end{array}$

This completes the proof. I'm pretty confused why Sutton and Barto seem to think abbreviating all these steps without comment is a good idea.

Using the Markov assumption

I think the following works: It suffices to show $Pr(G_{t+1}=g\mid S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)=Pr(G_{t+1}=g\mid S_{t+1}=s^{\prime })$. Conditioning over actions in the $t+1$ timestep, we have ${\sum }_{a^{\prime }}Pr(G_{t+1}=g\mid A_{t+1}=a^{\prime },S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)Pr(A_{t+1}=a^{\prime }\mid S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)$. But the action is chosen by the policy, which depends only on the state, so $Pr(A_{t+1}=a^{\prime }\mid S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)=\pi (a^{\prime }\mid s^{\prime })$. As for $Pr(G_{t+1}=g\mid A_{t+1}=a^{\prime },S_{t+1}=s^{\prime },R_{t+1}=r,A_t=a,S_t=s)$, recall that $G_{t+1}=R_{t+2}+R_{t+3}+\cdots$ so has only rewards starting on timestep $t+2$. Since we are working with an MDP, the environment's dynamics are completely determined by the state and action on timestep $t+1$, i.e. on $s^{\prime }$ and $a^{\prime }$ (NOTE: Sutton and Barto's text seems to have a small error here, where they describe the Markovian property as "That is, the probability of each possible value for $S_t$ and $R_t$ depends only on the immediately preceding state and action, $S_{t-1}$ and $A_{t-1}$, and, given them, not at all on earlier states and actions." -- the last part should probably say "not at all on earlier states, actions, and rewards". Otherwise I'm not sure how to prove that we can ignore the conditioning on $R_{t+1}=r$). So this is equal to $Pr(G_{t+1}=g\mid A_{t+1}=a^{\prime },S_{t+1}=s^{\prime })$. Thus we have ${\sum }_{a^{\prime }}Pr(G_{t+1}=g\mid A_{t+1}=a^{\prime },S_{t+1}=s^{\prime })\pi (a^{\prime }\mid s^{\prime })$. Now we can reverse the conditionalization, i.e. we marginalize to obtain $Pr(G_{t+1}=g\mid S_{t+1}=s^{\prime })$.

See this question for a similar manipulation.