Bellman equation derivation

Bellman equation for $v_{π}$ .

We want to show $v_{π} (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{π} (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}, \dots, C_{n}$ are events that partition the sample space, then $Pr (B) = \sum_{j = 1}^{n} Pr (B ∣ C_{j}) Pr (C_{j})$ .

For fixed event $A$ with non-zero probability, the mapping $B \mapsto Pr (B ∣ A)$ is another valid probability measure. In other words, define ${Pr}_{A}$ by ${Pr}_{A} (B) : = Pr (B ∣ A)$ for all events $B$ . Now the law of total probability for $P_{A}$ states that ${Pr}_{A} (B) = \sum_{j = 1}^{n} {Pr}_{A} (B ∣ C_{j}) {Pr}_{A} (C_{j})$ . We also have

{Pr}_{A} (B ∣ C_{j}) = \frac{{Pr}_{A} (B \cap C_{j})}{{Pr}_{A} (C_{j})} = \frac{Pr (B \cap C_{j} ∣ A)}{Pr (C_{j} ∣ 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 ∣ C_{j}, A)

So the law of total probability states that $Pr (B ∣ A) = \sum_{j = 1}^{n} Pr (B ∣ C_{j}, A) Pr (C_{j} ∣ A)$ .