Value iteration

From evaluation to control

Policy evaluation answers a fixed question: how good is this policy? Control asks a harder one: what is the best policy? The change is small on paper. Instead of averaging over the actions the policy might take, you take the best action at every state. Evaluation is a scoring function; control is a search. The first is a prediction problem, the second is an optimisation problem, and the difference in language matters.

That maximum is what makes the equation nonlinear, and it is also what makes it useful. The optimal value function is the fixed point of the Bellman optimality equation: the value of a state is the best immediate reward plus discounted value of the best successor, over all actions. The max is over actions, not states, and it applies to each action’s expected one-step return. It is also what makes the policy greedy with respect to its own values.

The backup is the algorithm

Value iteration starts with every value at zero and repeatedly applies that equation to every state. Each sweep takes the values from the previous sweep, computes the best action’s one-step lookahead, and writes the result down. The values move toward the fixed point from below. Starting from zero is a choice; any finite start converges, but zero keeps the first sweeps interpretable. Information propagates one transition per sweep, which is why a long corridor needs many sweeps.

The loop stops when the largest change in a sweep falls below a tolerance. The result is an approximation, not an exact answer, and the tolerance is a promise about how wrong it can be: with a discount of gamma, the remaining error is at most the change times gamma divided by one minus gamma. That bound is worth remembering when a value looks slightly off. It assumes the values are updated simultaneously, not in place.

The same algorithm in a library

import mdptoolbox.example
import mdptoolbox.mdp

P, R = mdptoolbox.example.forest()
planner = mdptoolbox.mdp.ValueIteration(P, R, 0.9)
planner.run()

print(planner.policy)
print([round(value, 3) for value in planner.V])

The policy falls out of the values

Once the values have settled, the policy is one more pass: at each state, try every action, score it with the reward plus discounted value of the next state, and keep the action with the highest score. No extra training is needed, because the values already encode the consequences. The policy is read off the value function, not stored alongside it. For a small grid you can do this by hand and check the arrows against intuition.

Ties are common in symmetric worlds, and any of the tied actions is optimal. A deterministic tie-break is still worth writing down, because otherwise two runs of the same planner can produce different-looking policies and look like a bug. In a grid world, a consistent order also makes the printed arrows stable enough to compare across runs. Any tie-break is fine as long as it is the same one every time.

What the discount buys

The discount sets the planner’s horizon. A reward k steps away is worth gamma raised to k, so with gamma at 0.9 half the value survives about seven steps, and with 0.99 about seventy. The effective horizon is roughly one over one minus gamma. A reward beyond that horizon is, for planning purposes, invisible. At 0.99 the agent is nearly patient; at 0.5 it barely looks two steps ahead.

That number is also the cost of planning. Smaller discounts converge in fewer sweeps because distant rewards stop mattering; larger ones need more sweeps to propagate value across the world. Choosing gamma is choosing both how far the agent looks and how long you are willing to wait for the answer. The two are not separable: the horizon you want sets the compute you must pay. A planner that needs a thousand sweeps is telling you the discount is doing real work.