Introduction

The previous article defined the state value as

$$v_\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t=s \right].$$

It is the expected return from state $s$ when policy $\pi$ is followed.

From this definition alone, it seems that calculating a value requires expanding every future reward through the end of an episode.

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$$

If an episode lasts three steps, we can simply add the terms. If it lasts hundreds of steps or never ends, repeatedly calculating the entire future for every state becomes unwieldy.

The Bellman equation identifies a recurring structure in this long future.

The entire future can be divided into the very next reward and the remaining future beginning from the next state.

It sounds obvious in words, but this idea underlies nearly every value update in reinforcement learning.

Folding the Tail of the Return

Let us group the return into the first reward and the remainder.

$$\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\ &= R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \cdots \right). \end{aligned}$$

The expression in parentheses is precisely the return $G_{t+1}$ beginning at time $t+1$.

$$G_t = R_{t+1} + \gamma G_{t+1}$$

Taking the expectation turns the expected $G_{t+1}$ into the value of the next state.

$$v_\pi(s) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t=s \right]$$

This is the Bellman expectation equation for state values.

The equation may look strange because it contains itself: $v_\pi$ appears on both the left and right. This recursive structure is natural because it expresses the current state's value in terms of the values of next states.

It is like saying, “the team's total workload is the work that arrived today plus the work carried into tomorrow.” Tomorrow's workload follows the same rule and connects to the following day. The Bellman equation exploits this repeated structure.

Reading the Bellman Equation with Small Numbers

Suppose the next reward from state $s$ is always $2$, and the policy and environment lead to one of two states.

• With probability $0.7$, the next state is $s_1$, where $v_\pi(s_1)=5$.
• With probability $0.3$, the next state is $s_2$, where $v_\pi(s_2)=1$.
• $\gamma=0.9$

First calculate the expected value of the next state.

$$0.7 \times 5 + 0.3 \times 1 = 3.8$$

Then discount it and add the immediate reward.

$$\begin{aligned} v_\pi(s) &= 2 + 0.9 \times 3.8 \\ &= 5.42. \end{aligned}$$

The value of the current state $s$ is $5.42$. The $2$ is the next reward, and $3.42$ is the present value of the future after the next state.

If the transition probabilities and reward function are known, we can expand the Bellman equation as sums.

$$v_\pi(s) = \sum_a \pi(a \mid s) \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a v_\pi(s') \right]$$

Although the equation is longer, it contains only four steps.

1. Consider the probability that the policy selects action $a$.
2. Consider that action's immediate reward.
3. Average the values of possible next states according to their transition probabilities.
4. Average over all actions according to the policy probabilities.

A Bellman Backup Corrects the Left Side with the Right

Recalculating the current value with the rewards and next-state values on the right is called a backup.

We can initialize every value to zero.

$$V_0(s)=0$$

After one backup, information about the immediately following reward enters the value. Repeated backups propagate reward information one step farther across the states each time.

Suppose a Gridworld exit gives $+10$.

• First iteration: states immediately beside the exit become valuable.
• Second iteration: states two cells away become valuable.
• As iterations continue, information about the exit spreads throughout the grid.

This is why value iteration is often described as “calculating backward from the final reward.” Even when the real environment contains loops and stochastic transitions, repeated backups preserve the same intuition.

The Bellman Equation for Action Values

An action value can likewise be divided into one step and the remaining future.

$$q_\pi(s,a) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma q_\pi(S_{t+1},A_{t+1}) \mid S_t=s, A_t=a \right]$$

From the current $(s,a)$, the agent receives a reward and reaches the next state. Its policy then chooses the next action $A_{t+1}$. The expected future from that point is $q_\pi(S_{t+1},A_{t+1})$.

Later, the SARSA update target will have the form

$$R_{t+1} + \gamma Q(S_{t+1},A_{t+1}).$$

This formula does not appear from nowhere. It approximates the Bellman expectation equation for action values with one actual experience.

The Bellman Optimality Equation for Finding the Best Policy

The Bellman expectation equation evaluates a fixed policy $\pi$. To find an optimal policy, we select the greatest value among the actions available in the next state.

$$v_*(s) = \max_a \mathbb{E} \left[ R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t=s, A_t=a \right]$$

For action values,

$$q_*(s,a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1},a') \mid S_t=s, A_t=a \right].$$

We will meet the target in the second equation again, unchanged, in Q-Learning.

$$R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a')$$

The expectation equation averages over the next actions that the current policy will actually select. The optimality equation chooses the largest possible next action. This small difference eventually leads to the distinction between on-policy SARSA and off-policy Q-Learning.

What Does Dynamic Programming Know in Advance?

Dynamic programming, or DP, divides a complex problem into overlapping smaller problems and reuses their results.

To use DP in reinforcement learning, we must know the model of the MDP.

• Transition probabilities $\mathcal{P}_{ss'}^a$
• Reward function $\mathcal{R}_s^a$

In other words, we assume that we already know where an action $a$ in state $s$ might lead and what its average reward is.

With this information, a Bellman backup can sum over every possible next state without repeatedly running the actual environment.

Knowing the model is a strong assumption, but DP provides a reference point for later algorithms. To understand what Monte Carlo and TD approximate with a single experience, it helps to first see how DP calculates the result when the entire model is available.

Policy Evaluation: How Good Is This Policy?

Policy evaluation calculates the value $v_\pi$ of a fixed policy $\pi$.

Beginning from an initial estimate $V_0(s)$, it repeatedly updates every state.

$$V_{k+1}(s) = \sum_a \pi(a \mid s) \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a V_k(s') \right]$$

$V_k$ is the estimate at iteration $k$. The right side uses the previous iteration's values $V_k$, and the newly calculated values are stored in $V_{k+1}$.

When the changes become sufficiently small, we stop and regard $V_k$ as close to $v_\pi$.

Policy Improvement: Switch to a Better Action

Once we know a policy's values, we can look one step ahead in each state and choose a better action.

$$\pi'(s) = \arg\max_a \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a v_\pi(s') \right]$$

This is a greedy improvement: choose the action that looks best under the current policy's values.

Alternating policy evaluation and policy improvement gives policy iteration.

The flow is

$$\pi_1 \xrightarrow{\text{evaluate}} v_{\pi_1} \xrightarrow{\text{improve}} \pi_2 \xrightarrow{\text{evaluate}} v_{\pi_2} \xrightarrow{\text{improve}} \cdots$$

When the policy no longer changes, its current action is already greedy in every state, and it has reached an optimal policy.

Value Iteration: Evaluate Once and Improve Immediately

Must policy evaluation converge completely before we improve the policy?

David Silver's lecture explains that the extreme case—performing only one evaluation update before immediately improving—is equivalent to value iteration.

$$V_{k+1}(s) = \max_a \left[ \mathcal{R}_s^a + \gamma \sum_{s'} \mathcal{P}_{ss'}^a V_k(s') \right]$$

Instead of explicitly storing and evaluating a policy, value iteration repeatedly applies the Bellman optimality backup to the values.

Both are DP methods for finding an optimal policy in an MDP whose model is known. They differ in how long evaluation runs before improvement is reflected.

The Limits of DP, Which Calculates Everything

DP is conceptually clear, but it has requirements.

1. The transition and reward models must be known.
2. It must be possible to sweep repeatedly over every state.
3. The numbers of states and actions cannot be too large.

In the real world, we may not know the exact probability that a robot will slip, and the set of possible image states may be effectively infinite. Then we cannot use a backup that sums over every $s'$.

The next step is to use samples that were actually experienced instead of calculating every possible outcome.

• Monte Carlo: use the actual return after an episode ends as the target
• TD: use one reward and the next-state estimate as the target

Both methods learn values even when the environment model is unknown.

What to Remember

The central idea of this article is

The Bellman equation divides a long future into the immediate reward and the discounted value of the next state.

More specifically:

1. $G_t=R_{t+1}+\gamma G_{t+1}$ reveals the recursive structure of the return.
2. The Bellman expectation equation represents the value of a fixed policy.
3. The Bellman optimality equation uses a $\max$ over the next action.
4. Policy iteration alternates evaluation and improvement.
5. Value iteration repeatedly applies the Bellman optimality backup.
6. DP requires the transition and reward models to be known.

The next article moves to a setting where the environment's transition matrix is unknown. Instead of calculating every possible future, Monte Carlo prediction experiences complete episodes and learns values from the average of actual returns.

References

• David Silver, Lecture 2: Markov Decision Processes
• David Silver, Lecture 3: Planning by Dynamic Programming
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition