Dynamic Programming / Value Iteration¶
Formal optimization method — instantiates Sequential Policy Optimization
Solves for the optimal policy by sweeping a value array with discounted one-step-lookahead backups until the values stop changing, then reading the greedy action off each state.
Value Iteration solves a known model by working entirely in value space. It keeps a number for every state — the best long-run value obtainable from there — and repeatedly overwrites each with a Bellman-optimality backup: the best-over-actions sum of immediate reward plus the discounted value of wherever that action lands you. Sweep the whole state array, then sweep again, and again, until no value changes by more than a tolerance. Its defining move is that no policy is ever stored during the computation — only the value array is iterated; the policy is read off at the very end by taking, in each state, the action that is greedy with respect to the converged values. The discount factor is not a detail here: it is what makes each backup a contraction and therefore guaranteed to converge to a unique optimum.[n1]
Example¶
A warehouse-floor robot must find its way back to a charging dock across a grid of aisles. Some cells are cheap to cross, some are congested and costly, a few are risky and best avoided. Value Iteration initializes every cell's value to zero, then sweeps: each cell's value becomes the smallest cost of stepping to a neighbor plus the discounted value already sitting on that neighbor. On the first sweep only cells next to the dock get meaningful values; on the second, their neighbors do; the information ripples outward sweep by sweep, like a flood filling the grid from the dock.
With a discount of, say, 0.95, a path that reaches the dock in three steps is worth noticeably more than one that takes ten, so the values naturally prefer short, safe routes. After the array stops changing, the robot needs no stored map of routes — its policy is simply "from wherever I am, step to the lowest-value neighbor," and that local rule reconstructs the globally optimal path from every starting cell at once. The route was never written down until the values converged.
How it works¶
- Initialize a value for every state (usually zero).
- Back up every state. Replace each state's value with the best, over actions, of immediate reward plus the discounted value of the resulting states — a single interleaved improvement folded into each sweep.
- Repeat full sweeps until the largest change across all states falls below a tolerance.
- Extract the policy. In each state choose the action that is greedy with respect to the converged values.
What distinguishes it from its policy-space twin is exactly this: one improvement step is baked into every evaluation sweep, and no explicit policy is maintained in between. The discount guarantees the sweeps contract toward a single fixed point.
Tuning parameters¶
- Discount factor — near 1 makes the robot farsighted but slows convergence and stiffens the contraction; near 0 makes it myopic but fast.
- Convergence tolerance — the change threshold at which sweeps stop; tighter means a more precise value array at the cost of more sweeps.
- Sweep style — in-place (Gauss–Seidel) updates propagate information within a sweep and converge faster than synchronous (Jacobi) updates, at the cost of order-dependence.
- Prioritized / asynchronous updates — focusing sweeps on the states whose values are still moving spends compute where it matters, trading simplicity for speed.
When it helps, and when it misleads¶
Its strength is simplicity and a convergence guarantee: given a fully known, tabular model, it needs no explicit policy bookkeeping and no linear-system solve — just repeated arithmetic that provably homes in on the optimum. It is the natural first tool when the state space is small enough to enumerate.
Its failure modes trace to those same assumptions. Every sweep costs on the order of states × states × actions, so a large state space is fatal — the curse of dimensionality bites hard. It also requires the transition model to be known and correct; the classic misuse is running it on a shakily estimated model as though it were exact, producing a confidently optimal policy for a fiction. And as the discount approaches 1 the contraction weakens and convergence crawls. The guarding discipline is to cross-check the model before trusting the values, keep the state space tractable, and treat the tolerance as a real precision knob rather than a formality.
How it implements the components¶
Value Iteration is a pure solver — it consumes a model and produces the optimal action map:
policy_rule— its output: the greedy policy read off the converged value array, a complete state-to-action map.discounting_or_temporal_weight— the discount inside every backup; the contraction that both weights the future and guarantees convergence.decision_horizon— the depth over which value propagates; with discounting, the effective horizon is set by how far the ripples still carry weight.
It does not maintain and exactly evaluate an explicit current policy — there is no policy_evaluation_rule here — because Value Iteration works in value space and never stores a policy until the end. That evaluate-then-improve alternation over a held policy is Policy Iteration, the near-twin from which it is separated by the absence of any named policy during the computation.
Related¶
- Instantiates: Sequential Policy Optimization — the value-space solver that turns a model into an optimal policy.
- Consumes: Markov Decision Process Model supplies the states, actions, transitions, and rewards it sweeps over.
- Sibling mechanisms: Markov Decision Process Model · Policy Iteration · Simulation Rollout Evaluation · Reinforcement Learning Policy Learning · Threshold Policy Rule · Adaptive Policy Review Cycle · Off-Policy or Historical Replay Evaluation
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Dynamic Programming / Value Iteration operates as a computation, comparison, model, or analytic representation used to infer, estimate, or choose because it solves for the optimal policy by sweeping a value array with discounted one-step-lookahead backups until the values stop changing, then reading the greedy action off each state.
Independent corroboration: The frozen evidence defines Dynamic Programming / Value Iteration as 'Solves for the optimal policy by sweeping a value array with discounted one-step-lookahead backups until the values stop changing, then reading the greedy action off each state', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Markov decision-process research cohered value iteration as repeated Bellman optimality backups to a fixed point followed by greedy policy extraction.
Related originating lineages:
- Computer Science & Software Engineering — Reinforcement-learning and algorithmic practice standardized array sweeps, convergence tolerances, and greedy policy extraction from computed values.
- Mathematics — Contraction-mapping theory supplied convergence to a unique discounted fixed point.
Review resolution: Operations research is primary because Bellman backups and policy optimization established value iteration; mathematics and computer science materially shape convergence theory and implementation.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] The Bellman-optimality backup is a contraction mapping under discounting: each sweep shrinks the distance to the true optimal value function by a factor equal to the discount, guaranteeing convergence to a unique fixed point. Push the discount to exactly 1 and the contraction — and the guarantee — weakens. ↩