Markov Decision Process & Value Iteration

States, actions, rewards — the framework for sequential decisions — solved by rippling worth out from the goal.

A Markov Decision Process (MDP) is the standard way to frame a sequential decision problem: an agent in some state takes an action, lands in a new state, and collects a reward. The aim is a policy — a rule for which action to take in each state — that earns the most reward over time.

The pieces

1States S — the situations the agent can be in (e.g. which grid cell).
2Actions A — the choices available in a state (up/down/left/right).
3Transitions P(s' | s, a) — where an action lands you (bumping a wall leaves you put).
4Rewards R — the payoff: +1 at the goal, -1 in the pit, -0.04 per step to discourage wandering.
5Discount γ — a number in [0, 1) (say 0.9) that makes reward-soon worth slightly more than reward-later.

The Markov property

The 'Markov' in MDP means the future depends only on the current state, not the path that got you there. The present state already summarizes everything relevant — which is what makes the math tractable.

Value iteration — back worth out from the goal

Define V(s) as the best total future reward achievable from state s. The Bellman optimality equation says each state's value equals the best action's immediate reward plus the discounted value of where it leads. Value iteration just applies this update again and again until the numbers stop changing.

V(s) <- max over actions a of:
          sum over s' of  P(s' | s, a) · [ R(s, a, s') + γ · V(s') ]

# repeat for every state until V stops changing (converges to V*)

From values to a policy

Once the values settle, the optimal policy is read off greedily: in each state pick the action whose Bellman value is highest. Those arrows together are guaranteed optimal — worth has rippled outward from the goal until every cell knows which way to go.

Value iteration needs the model

This method assumes you know the transitions P and rewards R up front — it plans on a known map. When the agent must *learn* the world from trial and error instead, you reach for model-free methods like Q-learning.

OperationTimeSpace

One sweep · every state × action × next-stateO(|S|² · |A|)O(|S|)

To convergence · γ-contraction guarantees it convergesO(sweeps · |S|² · |A|)O(|S|)

Check yourself

What does value iteration require that Q-learning does not?