Bellman Equation Explained with Worked Examples

The Bellman equation says that the best total cost from a state is the best choice of immediate cost plus the discounted best cost from the next state.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

What Bellman equation means

It expresses the principle of optimality: after the first decision, the remaining decisions must be optimal for the state you reach. The unknown is the function , found by solving the equations for all states, or by repeating the update (value iteration) from . A discount factor weights the future less, as in the present value of an annuity: a constant cost of 1 per step has when , the sum of a geometric series.

Example: state A with two actions: stay (cost 1, remain in A) or move (cost 2, reach the terminal state B with ). Then . Value iteration gives , so : moving immediately is optimal, since staying forever would cost 10. On a chain of states 0 to 3 with cost 1 per step towards 0 and , .

The Bellman equation is the basis of reinforcement learning and of optimal control; for linear systems with quadratic cost it leads to the algebraic Riccati equation. The repeated update converges by the Banach fixed-point theorem, and is a fixed-point iteration. Shortest routes are found in the same way, as in route problems and critical paths.

What is it used for?

The Bellman equation breaks a long sequence of decisions into one decision now plus the best value afterwards.

How to use bellman equation

  1. List the states, actions, costs and transitions .
  2. Start with (or a guess).
  3. Update for every state.
  4. Repeat until the values stop changing; the minimising actions form the optimal policy.

Graph

Value iteration for the stay-or-move problem converges to V = 2V(A) = 200.511.522.533.544.5500.511.52Value iteration for the stay-or-move problem converges to V = 2sweepV(A)Graph with x from 0 to 5 and y from 0 to 2.4. Shows V after each sweep (4); point V(A) = 2 at (3, 2).

The value rises 1, 1.9, 2 and then stays at 2, the cost of moving at once.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: stay or move

State A: stay costs 1 and remains in A, move costs 2 and reaches the terminal state (). With , find by value iteration.

Worked example
Answer
V(A)=2V(A)=2
  1. V₁
  2. V₂
  3. V₃

Example 2: a constant cost

A cost of 1 is paid every step forever with . Find .

Worked example
Answer
1010
  1. Equation
  2. Solve

Example 3: a chain

States 0, 1, 2, 3 with cost 1 for each step towards 0, and . Find .

Worked example
Answer
33
  1. V(0)
  2. V(k)
  3. V(3)

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Option 1: c = 2, V′ = 10, γ = 0.9

total

11.

Option 2: c = 5, V′ = 4

total

8.6.

Best

min

8.6.

Constant cost 1 forever

V = c/(1 − γ)

10.

Word problems

V(x) = min over u of [c(x, u) + γ V(next)]. The best cost-to-go is the best immediate cost plus the discounted cost-to-go.

Option 1

c = 2, γV′ = 9.

  1. 2 + 9
  2. Check: ✓11

Option 2

c = 5, γV′ = 3.6.

  1. 5 + 3.6
  2. Check: ✓8.6

Choose Higher

Smaller total.

  1. min(11, 8.6)
  2. Check: ✓8.6

Infinite horizon Higher

Cost 1, γ = 0.9.

  1. 1/0.1
  2. Check: ✓10

Common mistakes

Ignoring the discount

c + V′ ✗

c + γV′ ✓

Discount.

Choosing the lowest immediate cost

greedy ✗

lowest total ✓

Look ahead.

Wrong sign of min and max

max for cost ✗

min ✓

Cost minimised.

γ = 1 always

always ✗

γ < 1 for convergence ✓

Infinite horizon.

Exam tips

  1. V = min[c + γV′].
  2. Compare totals.
  3. γ < 1.
  4. Work backwards from the end.
  5. Iterate to solve.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. c + γV′: c = 3, γ = 0.5, V′ = 8 Foundation

7

2. V for c = 2, γ = 0.5 forever Foundation

4

3. min(6, 4.5) Foundation

4.5

4. c + γV′: c = 1, γ = 0.8, V′ = 5 Higher

5

5. V for c = 3, γ = 0.9 forever Higher

30

6. c + γV′: c = 4, γ = 0.25, V′ = 12 Higher

7

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Bellman equation
Optimality condition.
Cost-to-go
V(x).
Discount factor (γ)
0 < γ < 1.
Policy
Choice of u.
Dynamic programming
Recursive optimisation.
Value function
Best total cost.

Frequently asked questions

What is the Bellman equation?

V(x) = min_u [c(x, u) + γV(f(x, u))].

What is γ?

The discount factor.

How do I solve it?

By iteration, see fixed-point iteration.

What is the value for constant cost c forever?

c/(1 − γ).

Which page covers annuities?

present value of an annuity.

Which page covers the Riccati equation?

algebraic Riccati equation.

More in Advanced statistics and stochastic processes and the formula sheets.