Bellman Equations

A Bellman equation is a recursive consistency relationship for value functions. It describes a value in terms of related value information, usually involving immediate rewards and possible future states.

Programming

Why Values Look Ahead

The value of a state is not necessarily determined only by what happens immediately. An agent may receive a reward, move to a successor state, and then obtain additional value from that successor. The Bellman equation makes this dependency explicit: a state's value is connected to the rewards and discounted values of what may happen next.

Key point

How does the value of the current state depend on rewards and the values of all possible next states?

Two Kinds of Optimal Value

Definition

The optimal state-value function v*(s) is the maximum expected return from a particular state when decisions are made according to an optimal policy. Its input is a state by itself.

Definition

The optimal action-value function q*(s,a) is the maximum expected return after taking a particular action in a state and following an optimal policy thereafter. Its input includes both the state and the selected action.

Function	Input	Question it answers
v*(s)	State s	What is the maximum expected return from this state under an optimal policy?
q*(s,a)	State s and action a	What is the maximum expected return after taking this action and then following an optimal policy?

The distinction is whether the value is indexed by a state alone or by a state-action pair.

What does each function take as input, and how does the state value differ from the value of a particular action?

Reading a Backup

A backup diagram shows the relationships used when value information is carried back toward a state. In the diagrams described by the source, open circles represent states and solid circles represent state-action pairs. Starting from a state, follow the available actions, the environment's possible responses, the resulting rewards, and the successor states. These connected outcomes provide the information used to update or express the value of the starting state.

How do a state, an action, possible outcomes, rewards, and successor states connect during a value backup?

The backup is an organizing picture, not a replacement for the equation. It helps you identify which rewards, transition probabilities, and successor-state values belong in the expected value calculation.

Building the Recursive Expression

To construct a Bellman expression, begin with the state whose value is being evaluated. List the possible outcomes after the relevant action or policy decision. For each outcome, identify its reward and the value of the successor state. Discount the future value, weight each outcome according to its probability, and combine the contributions. The result expresses the current value through the values of related future states.

How are rewards, discounting, and transition probabilities combined to determine a state's value?

Rule

Key point

The word recursive matters: the expression for the current state refers to value information for successor states. The value function for a policy is described in the source as the unique solution to its Bellman equation.

A Small Symbolic Calculation

Worked example

Combining Two Possible Outcomes

Suppose a state has one selected action. Outcome A occurs with probability 0.6, gives reward 4, and leads to a successor state with value 10. Outcome B occurs with probability 0.4, gives reward 1, and leads to a successor state with value 5. Use a discount factor of 0.5 to form and evaluate an illustrative expected backup.

1
Write one contribution per outcome
For each outcome, combine its probability with its reward and its discounted successor-state value.
2
Substitute the values
The illustrative expression is 0.6 × (4 + 0.5 × 10) + 0.4 × (1 + 0.5 × 5).
3
Evaluate the first outcome
The first outcome contributes 0.6 × 9, because its immediate reward is 4 and its discounted successor value is 0.5 × 10.
4
Evaluate the second outcome
The second outcome contributes 0.4 × 3.5, because its immediate reward is 1 and its discounted successor value is 0.5 × 5.
5
Combine the contributions
Add the two probability-weighted contributions to obtain the current state's illustrative value.

Result

The illustrative value is 6.8.

Using an Optimal Policy

1
Identify whether the requested quantity is v*(s) or q*(s,a).
2
Locate the state, action, and successor outcomes named by the exercise.
3
Use the stated optimal policy to determine which action or continuation is relevant.
4
Write the symbolic expression before inserting numerical values.
5
Include the immediate rewards, the probabilities of possible outcomes, the discounting of future values, and the successor-state values supplied by the problem.
6
Evaluate the expression only after the symbolic structure is clear.

This procedure is especially important for gridworld-style questions. The source describes a gridworld exercise that requires the optimal policy, equation (3.2), and a separate numerical evaluation step. The exercise asks for a symbolic expression first and then a computation to three decimal places; it states that the optimal value of the best state is 24.4 to one decimal place.

What sequence of substitutions and calculations turns an optimal policy and a provided equation into the value of a state?

Common Interpretation Errors

Common mistake
Treating v*(s) and q*(s,a) as the same quantity.
What it looks like
Writing an action into v*(s) or omitting the action from q*(s,a).
Why it fails
The state-value function takes a state as its input, while the action-value function evaluates a particular action in a state.
Do this instead
Check whether the exercise asks about a state alone or about a state-action pair.
Common mistake
Ignoring successor states.
What it looks like
Using only the immediate reward when forming a value expression.
Why it fails
The Bellman relationship connects a state's value to the discounted values of possible successor states as well as to rewards.
Do this instead
Trace every possible outcome to its successor state and include the corresponding future value.
Common mistake
Forgetting outcome probabilities.
What it looks like
Adding the values of all possible outcomes without weighting them.
Why it fails
A state's value is based on an expected return, so possible outcomes contribute according to their probabilities.
Do this instead
Assign each outcome its probability before combining the contributions.
Common mistake
Calculating before writing the symbolic expression.
What it looks like
Jumping directly to decimal arithmetic in a gridworld exercise.
Why it fails
The source distinguishes expressing the optimal value symbolically from carrying out the numerical evaluation.
Do this instead
Write the equation with the optimal policy and known quantities first; evaluate it second.
Common mistake
Assuming the recursive equation is only a one-step description.
What it looks like
Treating successor-state values as unrelated numbers.
Why it fails
The recursive relationship defines current value through related value information for future states.
Do this instead
Read the equation as a consistency relationship across the current state and possible successor states.

Practice Check

MEDIUM

A problem names a state s, gives an optimal policy, lists several possible successor states with rewards and probabilities, and asks for the optimal value. Before doing arithmetic, decide whether the quantity is v*(s) or q*(s,a), draw the backup relationships in words, and write the symbolic expected-return expression.

Hints

A state alone points toward v*(s); a named action points toward q*(s,a).
For each possible outcome, identify its probability, reward, and successor-state value.
Keep the symbolic expression separate from the numerical evaluation.

Your attempt (not saved)

For the source's named practice settings, use the same reading strategy. The golf and recycling robot examples help frame value-function questions, while the gridworld exercise emphasizes using an optimal policy and a provided equation to express and compute an optimal value. In every case, first identify the requested viewpoint: state value, action value, or recursive value computation.

Key Takeaways

1
v*(s) is the maximum expected return from a state under an optimal policy.
2
q*(s,a) evaluates the return after taking a particular action and then following an optimal policy.
3
A Bellman equation is recursive because current value is expressed using rewards and values of possible successor states.
4
Probabilities weight possible outcomes, discounting adjusts future values, and rewards contribute directly to the expected return.
5
For symbolic exercises, identify the requested value function, apply the optimal policy, write the expression, and only then perform the numerical calculation.

At a glance

The optimal state-value function v*(s) describes the maximum expected return from a state under an optimal policy.
The optimal action-value function q*(s,a) describes the maximum expected return after a specified action and optimal continuation.
Bellman equations connect current value to immediate rewards and discounted values of possible successor states.
Backup diagrams organize the state, action, outcome, reward, probability, and successor-state relationships.
Solve symbolic value problems before evaluating numbers, especially in gridworld exercises.

Related concepts

More concepts starting with B