Value Iteration

Imagine you have a complete map of a small world: every location, every action available there, where each action can lead, and what reward it gives. Value iteration uses that map to work backward from desirable outcomes, repeatedly refining how valuable each state is until the best action becomes clear.

How the updates work
Value iteration maintains a table of state values, written V(s). A value means “how much total discounted reward can I expect from here if I act optimally?” For each state, it considers every possible action, the possible next states, their probabilities, and immediate rewards. It then replaces the old estimate with the best predicted return:

V(s) ← maxₐ Σₛ′ P(s′ | s, a) [R(s, a, s′) + γV(s′)]

Here, γ is the discount factor: it controls how much future reward counts relative to reward now. Repeating this update spreads the value of a distant goal backward through the state space. Once values stop changing meaningfully, the policy is simple: in each state, choose the action with the highest one-step reward plus the value of its likely next state.

What it requires and why it matters

• It requires a known environment model: transition probabilities and rewards. It plans rather than learns that model from trial data.
• It works cleanly for finite, manageable state and action spaces, such as a gridworld or a small inventory-control problem.
• Its updates use estimates to improve other estimates—a key RL idea called bootstrapping.

For example, in a gridworld with a reward at the exit and a penalty for lava, value iteration first values states next to the exit, then states leading to those states, eventually revealing the safest short route. Unlike labelled learning, no dataset says which action is correct in each state; the algorithm derives choices from predicted long-term reward. With a finite discounted model, these updates converge to the optimal value function. In a huge or unknown environment, storing every state or knowing exact dynamics breaks down, which is why methods such as DQN or PPO use sampled experience and function approximation instead.