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.

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\mid C_j)Pr(C_j)$.

For fixed event $A$, the mapping $B\mapsto Pr(B\mid A)$ is another valid probability measure. 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)$.