Bellman Equations

We may not know the state values $v[s_t]$ or action values $q[s_t,a_t]$ for any policy. However, we know that they must be consistent with one another, and it’s easy to write relations between these quantities. The state values $v[s_t]$ can be found by taking a weighted sum of the action values $q[s_t,a_t]$, where the weights depend on the probability under the policy $\pi [a_t|s_t]$ of taking that action:

$$v[s_t]=\sum _{a_t}\pi [a_t|s_t]q[s_t,a_t]$$

Similarly, the value of an action is the intermediate reward $r_{t+1}=r[s_t,a_t]$ generated by taking the action, plus the value $v[s_{t+1}]$ of being in the subsequent state $s_{t+1}$ discounted by $\gamma$. Since the assignment $s_{t+1}$ is not deterministic, we weight the values $v[s_{t+1}]$ according to the transition $Pr(s_{t+1}|s_t,a_t)$:

$$q[s_t,a_t]=r[s_t,a_t]+\gamma \cdot \sum _{s_{t+1}}Pr(s_{t+1}|s_t,a_t)v[s_{t+1}]$$

Substituting this equation into the state value equation above gives a relation between the state value at time $t$ and $t+1$:

$$v[s_t]=\sum _{a_t}\pi [a_t|s_t]\left(r[s_t,a_t]+\gamma \cdot \sum _{s_{t+1}}Pr(s_{t+1}|s_t,a_t)v[s_{t+1}]\right)$$

Substituting the $v[s_t]$ equation into the $q[s_t,a_t]$ equation gives a relation between the action value at time $t$ and $t+1$:

$$q[s_t,a_t]=r[s_t,a_t]+\gamma \cdot \sum _{s_{t+1}}Pr(s_{t+1}|s_t,a_t)\left(\sum _{a_{t+1}}\pi [a_{t+1}|s_{t+1}]q[s_{t+1},a_{t+1}]\right)$$

These two relations are the Bellman equations and are the backbone of many RL methods. In short, they say that the state (action) values have to be self-consistent. Consequently, when we update an estimate of one state (action) value, this will have a ripple effect that causes modifications to all the others.