Bellman equation derivation

Bellman equation for $v_{\pi }$.

We want to show $v_{\pi }(s)=\sum _{a}\pi (a\mid s)\sum _{s',r}p(s',r\mid s,a)[r+\gamma v_{\pi }(s')]$ 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},\ldots ,C_{n}$ are a partition of the sample space, then $\Pr(B)=\sum _{j=1}^{n}\Pr(B\mid C_{j})\Pr(C_{j})$.