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)$ .

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

E [X ∣ A] = \sum_{x} x \cdot Pr (X = x ∣ A) = \sum_{x} x \cdot \sum_{j} Pr (X = x ∣ C_{j}, A) Pr (C_{j} ∣ 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.