mathematics//decision theory//Markov decision process//value iteration

Value iteration is an algorithm that solves a Markov decision process by starting from any guess of the value function, usually zero everywhere, and applying the right-hand side of the Bellman equation to every state again and again until the values stop changing; it is the brute-force way to find an optimal policy when the model is known and the states are few enough to list. Maintenance planning, inventory control and grid-world robot navigation are its natural ground.

Value iteration is an algorithm that solves a Markov decision process by starting from any guess of the value function, usually zero everywhere, and applying the right-hand side of the Bellman equation to every state again and again until the values stop changing; it is the brute-force way to find an optimal policy when the model is known and the states are few enough to list. Maintenance planning, inventory control and grid-world robot navigation are its natural ground.

Each sweep computes, for every state, the best immediate reward plus the discounted value of where each action leads, using the values of the previous sweep. Information travels outward from the rewarding states: after one sweep only the cells next to the goal know it exists, after two their neighbours do, and so on.

sweeps to converge25 V(S), value of the start0.281 route from Sover the bridge With γ = 0.95, a slip probability of 0.10 and a cost of 0.020 per step, value iteration settles in 25 sweeps; the start is worth 0.281 and its route goes over the bridge.

Press one sweep a few times and watch the value spread from the goal one cell per sweep; raise the slip above 0.2 and the route abandons the bridge between the two traps for a longer, safer way; tap cells to add walls and solve again.

Each sweep shrinks the error by at least a factor γ\gammaγ. The Bellman operator is a contraction mapping, which guarantees a unique fixed point and convergence from any start; with γ=0.9\gamma=0.9γ=0.9, about 44 sweeps divide the error by a hundred, since 0.944≈0.010.9^{44}\approx0.010.944≈0.01.

Its cost is the cost of the state space. One sweep costs about states times actions times successors, which is nothing for the five wear levels of a machine (a two-by-five table, settled in well under a second on the policy of repairing at level 3, before it breaks) and impossible for a robot described by 10 variables of 100 values each, 102010^{20}1020 states (curse of dimensionality).

The discount sets both speed and character. A low γ\gammaγ converges quickly and makes the agent myopic, its values for distant rewards fading toward zero; a γ\gammaγ near 1 sees far and converges slowly.

The model it needs is the weak point. Value iteration exploits the transition probabilities wherever they are wrong; without a model, Q-learning replaces the expectation by experienced samples, and with continuous states LQR or MPC solve the same equation in closed form or online.