Value Functions and Bellman Equations

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?

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.

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

Value of current state = expected immediate reward + discounted expected value of successor state

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.

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.

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.

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.

State value = immediate reward + discount factor × expected successor-state value

Two Dynamic Programming Routes

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

• Treating policy evaluation as policy improvement

  Evaluation computes the values associated with the fixed policy. It does not change that policy.

  Fix: Look for a separate improvement stage that uses the computed values to construct a better policy.

• Using only one possible successor in a full backup

  A full backup considers all possible successors represented by the model and weights them by their probabilities.

  Fix: Include every modeled possible successor and its contribution to the expected value.

• Forgetting discounting

  The Bellman relationship includes discounted successor-state value, so future value is weighted by the discount factor.

  Fix: Apply the discount factor to the expected successor-state contribution before combining it with the immediate reward.

• Reading a backup diagram as a single deterministic path

  The diagram represents possible actions, environment responses, rewards, probabilities, and successor states that collectively contribute information.

  Fix: Read every possible branch and combine their weighted contributions.

• Assuming policy iteration and value iteration are the same procedure

  The source identifies value iteration as a separate dynamic-programming method, while policy iteration explicitly alternates two stages.

  Fix: Describe the computational route before describing the shared goal.

Check Your Understanding

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.