Does value iteration require a transition model?

Its basic dynamic-programming form uses transition probabilities and rewards.

Does it produce actions or values?

It directly updates values; actions are obtained through a greedy policy extraction step.

Will it converge for every possible decision problem?

No. The standard finite discounted guarantee has stated assumptions, and other settings need separate analysis.

AI Glossary / Mathematics and optimization / Intermediate

Value iteration

Definition

Value iteration is a dynamic-programming method for finding optimal state values in a Markov decision process. It repeatedly updates each state's value using the best available action, combining immediate expected reward with discounted values of possible next states. In a finite discounted problem with bounded rewards and a known model, these updates converge to the optimal value function. A policy can then be selected from the action comparisons.

What it means

A state value summarizes the expected future return available from a state. Value iteration improves an estimate of that quantity by looking one step ahead, while using the previous estimates to represent everything after that step.
The method evaluates consequences under a model of rewards and transitions. It is therefore a planning method in its basic form, rather than a procedure that automatically learns unknown dynamics by interacting with the world.
Optimal means best for the specified reward, transition model, discount factor, and allowable actions. A computed policy can be optimal for an inaccurate model or poorly chosen reward while remaining unsuitable for the real task.

How it works

Initialize a value V0(s) for each state. In a synchronous update, compute Vnext(s) as the maximum over actions of R(s,a) + gamma times the sum over next states s-prime of P(s-prime|s,a)Vold(s-prime).
The transition probabilities weight possible outcomes; the maximum selects an action before knowing which outcome occurs. Use the old value table throughout a synchronous sweep. In-place variants need their own clearly specified update convention.
For a finite MDP with bounded rewards and 0≤gamma<1, the Bellman optimality update contracts differences in the maximum norm by at most gamma. Repeated exact updates therefore converge to a unique optimal value function. A greedy policy chooses an action maximizing the same one-step expression using the final values. Undiscounted settings require additional conditions and are not covered by this simple guarantee.

Three practical examples

A small maintenance-planning model can compare immediate repair costs with the modeled consequences of delaying repair.
A game or navigation exercise can compute actions that trade an immediate reward against better future positions.
An analyst can use a fully specified small MDP as a reference solution when checking an approximate planning or learning method.

Think of it this way

Think of repeatedly updating a map of how promising each location is. A location becomes attractive when it offers a good immediate outcome or leads to another promising location. The analogy captures information flowing backward through possible moves, but real transition probabilities and rewards need to be specified; the map does not discover them merely by being updated.

Worked example

Consider two nonterminal states, S and B, plus a terminal state T whose future value is zero. At S, action exit gives reward 3 and moves to T. Action continue gives reward 0 and moves to B. At B, the only action gives reward 5 and moves to T. All transitions are deterministic, and gamma=0.9.
Initialize V0(S)=V0(B)=V0(T)=0. The first synchronous sweep gives V1(S)=max(3,0)=3 and V1(B)=5.
The second sweep gives V2(S)=max(3,0+0.9×5)=4.5 and V2(B)=5. A further sweep changes nothing. The optimal choice at S is continue: it earns the later reward 5, discounted to 4.5, rather than the immediate reward 3.
This example also shows why immediate-reward greediness can fail. It would select exit before accounting for B's value.
Now change only gamma to 0.5. Continuing is worth 0.5×5=2.5, so exit becomes optimal at value 3. Neither answer is an arithmetic contradiction: changing the discount changes the modeled objective. The example uses exact table calculations, not observed business returns.

Illustrative case study

In a fictional warehouse simulation, a planner uses value iteration to choose between completing a nearby task and moving toward a later opportunity. The initial policy looks strong under assumed travel times but performs poorly when congestion delays are introduced.
The team checks whether the state description and transition model capture the relevant traffic conditions. It compares simulated outcomes under several plausible models before deciding which policy deserves a controlled trial.
The lesson is that convergence of the planning calculation does not validate the model of the warehouse. Numerical correctness and operational relevance require separate evidence.

Common misconceptions and mistakes

Do not replace the expected value over next states with the value of whichever next state is most attractive. The decision maker chooses an action, not the random outcome.
Do not confuse value iteration with policy evaluation, which computes values for a fixed policy, or with policy iteration, which alternates evaluation and policy improvement.
A small update is not automatically a small policy-performance error without the appropriate bound. For discounted exact updates, the Bellman residual can support a value-error bound, but its interpretation depends on gamma.
Finally, the finite-table guarantee does not automatically transfer to arbitrary function approximation, inaccurate updates, or an undiscounted problem with indefinite cycles.

Business use

Value iteration is useful when a manageable decision model exposes the consequences of acting now versus later. Its practical limits include the number of states and actions, model accuracy, and the suitability of the reward.
Keep the discount factor and reward timing explicit in reports. Test sensitivity to uncertain transition assumptions, and explain what constraints are represented by allowed actions. A converged value table is a solution to a mathematical planning model, not by itself authorization or evidence for live operational deployment.

Check your understanding

An action gives immediate reward 1 and deterministically reaches a state valued at 8. With gamma=0.5, what is its one-step action value? Is it better than terminating immediately for reward 6?

Answer: Its value is 1+0.5×8=5, so terminating for 6 is better under these values and assumptions.

Related terms

Learn next

Reproduce the two sweeps in the worked example using separate old and new tables. Then add a probabilistic transition and compute the weighted expectation. Study the Bellman contraction argument before interpreting a stopping tolerance or extending the method to function approximation.

Sources

Aalto Dictionary of Machine Learning, value iteration and Bellman operator entries. https://aaltodictionaryofml.github.io/ADictML_Main.pdf Emma Brunskill, Stanford CS234 Lecture 2, Spring 2024: value iteration, policy extraction, and discounted contraction discussion. https://web.stanford.edu/class/cs234/CS234Spr2024/slides/lecture2pre.pdf

Previous: Value imputation Next: Value of perfect information