Bellman Equations

The previous sections gave us the pieces: an MDP gives states, actions, transitions, rewards, and $\gamma$; a policy $\pi(a\mid s)$ chooses actions; $V^\pi(s)$ and $Q^\pi(s,a)$ estimate expected return. Bellman equations connect those pieces into one recursive statement.

The core idea is simple: value now equals immediate reward plus discounted future value. Think of value like a one-step receipt. The first line on the receipt is what happens immediately after the next action. The second line is the estimated value of wherever you end up next, discounted because it is future value.

For a delivery robot, a state $s$ might be "at the lobby, carrying a package." An action $a$ might be "go to the elevator." The next state $s'$ might be "inside the elevator" or "waiting because the elevator is full." The transition probability $P(s'\mid s,a)$ says how likely each next state is. The reward $R(s,a,s')$ might charge a small time cost or give progress credit. The term $\gamma V^\pi(s')$ asks how useful the new situation is for the rest of the delivery.

For a fixed policy, the Bellman expectation equation for $V$ is:

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

The left side, $V^\pi(s)$, asks: if the robot starts in state $s$ and follows policy $\pi$, what return should we expect? The right side answers by looking one step ahead, then reusing the value estimate for the state that comes next.

The first sum, $\sum_a\pi(a\mid s)$, averages over the actions the policy might take. If the policy goes to the elevator 70% of the time and takes the stairs 30% of the time, both possibilities contribute to the state value in those proportions. The second sum, $\sum_{s'}P(s'\mid s,a)$, averages over next states the environment might produce after action $a$. If the elevator is available most of the time and full some of the time, both outcomes matter.

Inside the brackets, $R(s,a,s')$ is the immediate payoff for that one transition, and $\gamma V^\pi(s')$ is the continuation value. In the delivery example, the robot might pay a small step cost now, then gain access to a much better future state once it reaches the elevator.

The Bellman expectation equation for $Q$ fixes the first action and then averages over what happens next:

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

Read it as: if the robot commits to action $a$ first, what return should we expect? After that first action, the policy takes over again. That is why the expression contains $a'$: after landing in $s'$, the policy chooses among possible next actions.

The distinction between $V$ and $Q$ is practical. $V^\pi(s)$ evaluates a situation under the policy's usual behavior. $Q^\pi(s,a)$ evaluates a particular first move. If the robot is deciding between the elevator and the stairs right now, $Q$ is the more direct comparison.

When we find the best possible policy $\pi^*$, policy averaging is replaced by choosing the best action. The optimal value equations are $$V^*(s)=\max_a Q^*(s,a)$$ and $$Q^*(s,a)=\sum_{s'}P(s'\mid s,a)\left[R(s,a,s')+\gamma\max_{a'}Q^*(s',a')\right]$$ These equations define the fixed point for optimal behavior and are the backbone for dynamic programming, value iteration, and Q-learning.