skip to content

How does the Bellman optimality equation differ from the Bellman expectation equation?

level: middleimportance: must knowfreq 66%

answer

  1. same recursion, different rule over actions
  2. average versus maximum
  3. one of them stays linear
  4. the max kills linearity
  5. V-pi versus V-star

basics

~20 s

Both split a value into immediate reward plus the discounted value of the next state. The expectation equation averages over the actions a fixed policy takes and is linear in the values; the optimality equation takes the maximum over actions, which makes it nonlinear and defines the best achievable value.

solid answer

~50 s

The expectation equation is the self-consistency condition for one fixed policy: `V_pi(s) = sum over a of pi(a|s) * sum over s' of p(s'|s,a) * [r + g*V_pi(s')]`. Every action is weighted by how often the policy takes it, so the whole system is linear in the unknown values — for a finite state set it is |S| linear equations in |S| unknowns. The optimality equation replaces the policy average with a maximum: `V*(s) = max over a of sum over s' of p(s'|s,a) * [r + g*V*(s')]`, saying the value of a state under optimal behaviour is the value of its best action. The max is nonlinear, so this is not a linear system. The two also describe different objects: V_pi for the policy you have, V* for the best policy there is. And crucially, both are *conditions* a value function must satisfy, not procedures for producing one.

code

python · 15 lines
python
gamma = 0.9
# Claimed state values for one fixed policy on a customer-lifecycle MDP.
V = {'trial': 8.3643, 'active': 18.5874, 'lapsing': 6.6915, 'churned': 0.0}
# Transitions the policy induces: (probability, immediate reward, next state)
model = {
    'trial':   [(0.5, 0.0, 'active'), (0.5, 0.0, 'churned')],
    'active':  [(0.8, 5.0, 'active'), (0.2, 0.0, 'lapsing')],
    'lapsing': [(0.4, 0.0, 'active'), (0.6, 0.0, 'churned')],
    'churned': [(1.0, 0.0, 'churned')],
}
for state, transitions in model.items():
    backup = sum(p * (r + gamma * V[nxt]) for p, r, nxt in transitions)
    print(state, 'claimed', round(V[state], 2), 'backup', round(backup, 2))
# Every state's backup reproduces its claimed value, so these numbers are
# consistent with the Bellman expectation equation for this policy.

go deeper

for a junior

Be ready to say in words that a state's value is immediate reward plus the discounted value of the next state, and that one version follows a fixed policy while the other assumes the best action.

for a middle

Write both equations from memory and point at the difference: a policy-weighted average versus a max over actions. An interviewer expects you to know the expectation form is linear in the unknown values.

for a senior

Use the equations as a diagnostic — compute Bellman errors on a claimed value function, check the terminal boundary, and read a large residual as evidence the values or the assumed dynamics are wrong.

for a principal

Frame where the equations stop being usable: huge or continuous state sets, unknown dynamics, and non-Markov state encodings, and decide when approximation is worth its bias versus reshaping the problem itself.

## One recursion, two action rules Every Bellman equation is the same trick: a return is immediate reward plus a discounted return from the next state, so a value must equal immediate reward plus the discounted value of where you land. The equations differ only in how the action is chosen at the first step. **Bellman expectation equation** (for a fixed policy pi): `V_pi(s) = sum over a of pi(a|s) * sum over s',r of p(s',r|s,a) * [ r + g * V_pi(s') ]` and in action-value form: `Q_pi(s,a) = sum over s',r of p(s',r|s,a) * [ r + g * sum over a' of pi(a'|s') * Q_pi(s',a') ]` **Bellman optimality equation** (for the best achievable values): `V*(s) = max over a of sum over s',r of p(s',r|s,a) * [ r + g * V*(s') ]` `Q*(s,a) = sum over s',r of p(s',r|s,a) * [ r + g * max over a' of Q*(s',a') ]` Notice where the max sits. In `V*` it is outside, over the first action. In `Q*` the first action is already fixed by the arguments, so the max moves inside, over the *next* action. Placing the max over states instead of actions is a common and fatal slip: you never maximise over which next state occurs, because the environment picks that, and you average over it. ## Linear versus nonlinear With the policy fixed, the right-hand side of the expectation equation is a weighted sum of the unknown values plus a constant. Written across all states it is `v = r_pi + g * P_pi * v`, a linear system whose unique solution exists whenever g < 1 (or under an episodic structure that guarantees termination). "Unique" matters: a fixed policy has exactly one value function, so a claimed V either satisfies the equation everywhere or is simply wrong. The max in the optimality equation destroys linearity — the right-hand side is a maximum of linear functions, so it is piecewise linear and convex in the values, not linear. There is no matrix inverse to write down. Turning either equation into an actual computation is a separate subject from the equations themselves and belongs to the planning material; what matters here is *what the equations assert*. ## Different objects, not different notations `V_pi` is the value of the policy you actually have, however mediocre. `V*` is the value of the best policy available in the MDP. Any policy satisfies the expectation equation with its own values; only the optimum satisfies the optimality equation. A useful corollary: if for some state the best action's one-step backup exceeds `V_pi(s)`, the policy is not optimal there — the two equations disagree exactly where there is room to improve. ## Extracting behaviour From `Q*`, optimal behaviour is a lookup: `pi*(s) = argmax over a of Q*(s,a)`. From `V*` it needs one step of the model: `pi*(s) = argmax over a of E[ r + g*V*(s') | s,a ]`. This is why the optimality equation for Q is the more directly useful of the pair — it bakes the lookahead into the stored numbers. ## Terminal states and the boundary A terminal state has value zero by definition — nothing follows it — so the backup in the state before a terminal transition reduces to the expected immediate reward. Getting this boundary wrong is a frequent source of value functions that are self-consistent everywhere except at the end of an episode. ## Checking consistency by hand Because the expectation equation is a condition, it doubles as a test. Take a four-state customer-lifecycle MDP — trial, active, lapsing, churned — with a fixed policy, a discount of 0.9, and a claimed value for each state. For every state, compute the right-hand side: average `r + g * V(next)` over the transitions the policy induces. If the result reproduces the claimed value in all four states, the numbers are that policy's value function. If one state is off by 3.0, the claimed values are inconsistent with the policy; that gap is the Bellman error (also called the residual) in that state. This is exactly how you would debug a value function someone hands you, and it needs nothing but arithmetic. ## What interviewers listen for That you can write one of the equations without prompting; that you know which term is an average over the environment's randomness and which is a choice by the agent; that you say "consistency condition", not "algorithm"; and that you do not claim V_pi and V* are the same thing under different names.

  • Why is the expectation equation solvable as a linear system while the optimality equation is not?
    With the policy fixed, each value is a weighted sum of successor values plus a constant, so across states it reads `v = r_pi + g*P_pi*v` — linear, with a unique solution when g < 1. The optimality equation maximises over actions, and a maximum of linear functions is piecewise linear, not linear, so no closed-form matrix solution exists.
  • In the optimality equation for Q*, why does the max sit over the next action rather than the current one?
    Because Q*(s,a) already commits to action a at this step — that is what its arguments mean. Optimality then applies from the next state onward, so the backup is the expected reward plus the discounted value of the best action available in s'. In the V* form nothing is committed yet, so the max sits over the current action.
  • Someone hands you a value function for a fixed policy; how do you check it?
    Plug it into the expectation backup state by state: average `r + g*V(next)` over the transitions the policy induces and compare with the claimed value. Because a fixed policy has exactly one value function, any state where the two sides disagree — a non-zero Bellman error — proves the numbers are wrong.
  • What do the two equations say about a state where a non-chosen action looks better?
    That the policy is not optimal there. The expectation equation is still satisfied — it only describes the policy you have — but the optimality equation is violated, because the best action's backup exceeds the current value. That gap is exactly the room for improvement in that state.

The expectation equation asks what your current habits are worth; the optimality equation asks what the best possible play is worth.

saying these in an interview costs you the question

  • Says the Bellman equation uses only immediate reward
  • Thinks the expectation and optimality equations share a solution
  • Puts the max over next states instead of actions
  • Calls the equation an algorithm rather than a condition
  • Forgets to discount the successor state's value
  • Assigns a terminal state a non-zero value

context

resolving links…