Bellman Equations

Recursive Value Decomposition

The fundamental principle of Dynamic Programming (Richard Bellman, 1957):

                       CUMULATIVE DISCOUNTED RETURN
        G_t = R_{t+1} + γ R_{t+2} + γ² R_{t+3} + γ³ R_{t+4} + ...
            = R_{t+1} + γ ( R_{t+2} + γ R_{t+3} + ... )
            = R_{t+1} + γ G_{t+1}

Taking expectations yields the Bellman Equations!

1. Bellman Expectation Equations (Policy Evaluation)

For a fixed policy $\pi$:

State-Value Function $V^\pi(s)$:

$$V^\pi(s) = \sum_{a \in A} \pi(a \mid s) \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a, s') + \gamma V^\pi(s') \right]$$

Action-Value Function $Q^\pi(s, a)$:

$$Q^\pi(s, a) = \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a, s') + \gamma \sum_{a' \in A} \pi(a' \mid s') Q^\pi(s', a') \right]$$

2. Bellman Optimality Equations

For the optimal policy $\pi^*$:

$$V^(s) = \max_{a \in A} \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a, s') + \gamma V^(s') \right]$$

$$Q^(s, a) = \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a, s') + \gamma \max_{a' \in A} Q^(s', a') \right]$$

                        Bellman Optimality Backup Diagram
                                  (State s)
                                      │
                                 a = max_a
                                      │
                                      ▼
                               (Action-State s,a)
                                    /   \
                         P(s'|s,a) /     \
                                  ▼       ▼
                              (State s') (State s'')

Value Iteration Algorithm

Turn Bellman Optimality Equation into an iterative update rule:

$$V_{k+1}(s) \leftarrow \max_{a \in A} \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a, s') + \gamma V_k(s') \right]$$

By the Contraction Mapping Theorem, repeatedly applying this operator guarantees linear convergence to unique optimal fixed point $V^*(s)$.

Say this out loud

"Bellman Equations recursively express the value of a state V(s) or action Q(s,a) as immediate reward plus discounted expected value of successor states: V(s) = E[R + γ V(s')]. Bellman Expectation Equations evaluate a fixed policy π, while Bellman Optimality Equations incorporate the max operator over actions, forming the update rule for Value Iteration and Q-Learning."

Follow-ups to expect

• How does Q-Learning derive from the Bellman Optimality Equation? Q-Learning is a model-free sample-based approximation of the Bellman Optimality Equation, replacing transition probabilities $P(s'|s,a)$ with environment sample experiences $(s, a, r, s')$.
• What is Bellman Residual / Error? The difference between current value prediction $Q(s,a)$ and Bellman target $r + \gamma \max_{a'} Q(s',a')$. Minimizing squared Bellman residual trains Q-networks.