Value Functions and Bellman Equations

Policy evaluation measures the current policy. Policy improvement uses that measurement to construct a better policy. Policy iteration repeatedly alternates these two jobs.

Programming

From a Policy to Its Consequences

A policy tells an agent what to do, but the policy itself does not immediately tell us how good each state is. Value functions answer that question. They measure the consequences of following a policy from different states. Dynamic programming then uses those measurements to ask a second question: could another policy do better?

Key point

Policy evaluation measures the current policy. Policy improvement uses that measurement to construct a better policy. Policy iteration repeatedly alternates these two jobs.

The Policy Iteration Loop

Policy iteration begins with a policy, evaluates it, improves it, and then evaluates the resulting policy again. Evaluation does not change the policy. It computes the value function associated with continuing to follow that policy. Improvement uses those values to construct a candidate policy that is better informed by the evaluation. The loop ends when improvement no longer changes the policy.

What happens next as policy evaluation and policy improvement alternate until the policy stops changing?

1
Start with a policy that specifies what to do.
2
Evaluate that fixed policy by computing its value function.
3
Improve the policy using the computed values.
4
If the policy changed, evaluate the new policy and repeat.
5
Stop when improvement produces no change.

Reading a Bellman Relationship

Definition

The Bellman equation is a recursive consistency relationship for value functions. It describes how the value of a state relates to the reward and discounted value of possible successor states. The relationship is recursive because a state's value is expressed partly in terms of values of states that may follow it.

Rule

For a fixed policy, the value of a state is determined by what the policy does there and by what the environment may produce afterward. Each possible outcome contributes according to two factors: how likely that outcome is and how much reward and future value it provides. Discounting reduces the contribution of future value relative to the immediate reward. The value function vπ is the unique solution to the Bellman equation for that policy.

Part of the relationship	Role in the state value
Immediate reward	The reward received as the transition occurs
Probability of an outcome	The weight assigned to that possible outcome
Discount factor	The factor that reduces the contribution of future value
Successor-state value	The value carried forward from a possible next state

The ingredients combined by a Bellman-style backup

How do a state-action choice, immediate reward, transition probabilities, discounting, and successor-state values combine to update a state's value?

Following a Full Backup

A full backup is the local operation behind a dynamic-programming sweep. Select one state, then use the values of all possible successor states, together with the probabilities that those successors occur, to update the selected state's value. Full means that the model's possible successors are all considered, rather than using only one observed successor.

How does information move from a state through an action and possible successor states during a full backup?

Backup diagrams make the Bellman relationship visible. Open circles represent states, and solid circles represent state-action pairs. Starting at a state, follow the selected action, then inspect the environment's possible responses, rewards, probabilities, and successor states. The information from those branches is combined to update the value of the starting state.

Key point

A Bellman equation describes the relationship. A backup performs one update using that relationship. A sweep applies backups across the state set.

A Small Expected-Value Calculation

Consider a generated illustration with one current state and one action. Suppose the action gives an immediate reward of 2. After the action, there are two possible successor states. The first has probability 0.6 and value 5. The second has probability 0.4 and value 1. Use a discount factor of 0.5. This example is generated to show how the parts of a Bellman relationship combine; it is not a numerical example taken from the source.

Formula, step by step

1
Compute the expected successor-state value: (0.6 × 5) + (0.4 × 1) = 3.4.
2
Apply the discount factor to that expectation: 0.5 × 3.4 = 1.7.
3
Add the immediate reward: 2 + 1.7 = 3.7.

Worked example

Combining two possible outcomes

An action produces reward 2, then reaches a successor valued at 5 with probability 0.6 or a successor valued at 1 with probability 0.4. The discount factor is 0.5. What value does the Bellman relationship assign to the current state?

1
Weight each successor value
The first outcome contributes 0.6 × 5 = 3.0, and the second contributes 0.4 × 1 = 0.4.
2
Add the weighted outcomes
The expected successor-state value is 3.0 + 0.4 = 3.4.
3
Discount the future contribution
Multiplying 3.4 by the discount factor 0.5 gives 1.7.
4
Include the immediate reward
The current state's value is the immediate reward 2 plus the discounted future contribution 1.7.

Result

The illustrative value of the current state is 3.7.

How does a state's value depend recursively on the values of its possible successor states, and how does that relationship produce a concrete numeric result?

Two Dynamic Programming Routes

Feature	Policy iteration	Value iteration
Main pattern	Alternates policy evaluation and policy improvement	Uses a distinct dynamic-programming route toward optimal policies and value functions
Policy evaluation	Explicit stage that evaluates a fixed policy	Not presented as the same separate two-stage loop
Policy improvement	Explicit stage that uses values to construct a better policy	Not presented as the same separate two-stage loop
Shared goal in the source	Compute optimal policies and value functions for finite Markov decision processes when the model is completely known	Compute optimal policies and value functions for finite Markov decision processes when the model is completely known

The source distinguishes the methods by their computational route, not by a different overall target.

What is the difference between separately evaluating and improving a policy and directly updating values while implicitly improving the policy?

Both methods are dynamic-programming methods aimed at optimal policies and value functions for finite Markov decision processes when the model is completely known. The important distinction here is procedural. Policy iteration explicitly separates evaluation of a policy from improvement of that policy. Value iteration is presented as a separate route rather than as that same alternating loop.

Mistakes in Interpreting Backups

Common mistake
Treating policy evaluation as policy improvement
What it looks like
Assuming that evaluating a policy automatically replaces its actions
Why it fails
Evaluation computes the values associated with the fixed policy. It does not change that policy.
Do this instead
Look for a separate improvement stage that uses the computed values to construct a better policy.
Common mistake
Using only one possible successor in a full backup
What it looks like
Updating a state from one observed outcome while ignoring other outcomes represented by the model
Why it fails
A full backup considers all possible successors represented by the model and weights them by their probabilities.
Do this instead
Include every modeled possible successor and its contribution to the expected value.
Common mistake
Forgetting discounting
What it looks like
Adding successor-state value directly to the immediate reward
Why it fails
The Bellman relationship includes discounted successor-state value, so future value is weighted by the discount factor.
Do this instead
Apply the discount factor to the expected successor-state contribution before combining it with the immediate reward.
Common mistake
Reading a backup diagram as a single deterministic path
What it looks like
Following one branch and treating it as the complete value update
Why it fails
The diagram represents possible actions, environment responses, rewards, probabilities, and successor states that collectively contribute information.
Do this instead
Read every possible branch and combine their weighted contributions.
Common mistake
Assuming policy iteration and value iteration are the same procedure
What it looks like
Describing value iteration as policy evaluation followed by policy improvement in a repeated loop
Why it fails
The source identifies value iteration as a separate dynamic-programming method, while policy iteration explicitly alternates two stages.
Do this instead
Describe the computational route before describing the shared goal.

Check Your Understanding

MEDIUM

A state has an immediate reward of 4. An action can lead to a successor valued at 6 with probability 0.25 or a successor valued at 2 with probability 0.75. Use a discount factor of 0.5. Calculate the illustrative Bellman-style value of the state, then identify which part of your calculation represents the expected successor-state value.

Hints

First multiply each successor value by the probability of reaching it.
Add the weighted successor contributions before applying the discount factor.
Finally, add the immediate reward.

Your attempt (not saved)

What do you think happens?

After a policy has been evaluated, what should happen next in policy iteration?

Evaluate the same policy forever without changing it
Use the value function to perform policy improvement
Discard the value function and select an action randomly
Switch automatically to value iteration

Reveal answer

Answer:

Use the value function to perform policy improvement

Policy iteration alternates policy evaluation with policy improvement. The evaluation measures the current policy, and the improvement stage uses those values to construct a better policy.

The Working Mental Model

1
A value function measures how good it is to follow a policy from each state.
2
Policy evaluation computes the value function for a fixed policy and repeats backups until the values become stable.
3
Policy improvement uses those values to construct a better policy, and policy iteration alternates evaluation and improvement until the policy stops changing.
4
A Bellman equation expresses a state's value recursively through immediate reward and discounted, probability-weighted successor-state values.
5
A full backup considers all possible successors represented by the model; a sweep applies this operation across the state set.
6
Value iteration is a separate dynamic-programming method that shares the goal of computing optimal policies and value functions but does not follow the same explicit evaluation-improvement loop.

Key Takeaways

Policy evaluation measures a fixed policy by computing its value function.
Policy improvement uses that value function to construct a better policy, and policy iteration repeats the two stages until improvement produces no change.
The Bellman equation is a recursive relationship combining immediate rewards with discounted, probability-weighted values of possible successor states.
A full backup uses every possible successor represented by the model, while repeated backups move value estimates toward values that satisfy the Bellman equation.
Policy iteration and value iteration are distinct dynamic-programming routes that target optimal policies and value functions for finite Markov decision processes when the model is completely known.

Related concepts

More concepts starting with V