Option 1: c = 2, V′ = 10, γ = 0.9
total
11.
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.
This page is easier if you are comfortable with:
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.
The Bellman equation breaks a long sequence of decisions into one decision now plus the best value afterwards.
The value rises 1, 1.9, 2 and then stays at 2, the cost of moving at once.
These examples are worked by hand, step by step, so you can compare your own working.
State A: stay costs 1 and remains in A, move costs 2 and reaches the terminal state (). With , find by value iteration.
A cost of 1 is paid every step forever with . Find .
States 0, 1, 2, 3 with cost 1 for each step towards 0, and . Find .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
total
11.
total
8.6.
min
8.6.
V = c/(1 − γ)
10.
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.
c = 2, γV′ = 9.
c = 5, γV′ = 3.6.
Smaller total.
Cost 1, γ = 0.9.
c + V′ ✗
c + γV′ ✓
Discount.
greedy ✗
lowest total ✓
Look ahead.
max for cost ✗
min ✓
Cost minimised.
always ✗
γ < 1 for convergence ✓
Infinite horizon.
Try each one on paper, then open the answer. Use the solver above to see the full working.
7
4
4.5
5
30
7
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
V(x) = min_u [c(x, u) + γV(f(x, u))].
The discount factor.
By iteration, see fixed-point iteration.
c/(1 − γ).
present value of an annuity.
algebraic Riccati equation.
More in Advanced statistics and stochastic processes and the formula sheets.