Markov Decision Processes

Imagine a small robot in a grid. It wants to reach a charging pad and avoid a pit. It can move up, down, left or right — but the floor is slippery, so a chosen move only usually lands where intended. Sometimes it slides sideways. How should the robot act, in every square, to collect the most reward over time?

That question is a Markov decision process (MDP). You give it four ingredients: a set of states (the squares), a set of actions (the moves), the transition probabilities (the odds each action lands you somewhere), and a reward for each step. The word Markov means the future depends only on where you are now, not on the path that got you there.

The answer an MDP hands back is not a single route. It is a policy: a recommended action for every possible state, so that no matter where luck drops you, you already know the best thing to do.

Below is a grid world. The green pad is the goal (+1), the red square is a pit (−1), and the dark square is a wall. Every other step costs a little, so the robot is nudged to finish quickly. Moves are noisy: 80% of the time you go where you aim, 10% you slip left, 10% you slip right.

Press Step to run one sweep of value iteration, or Solve to run until the numbers stop changing. Each cell shows its current value, and an arrow appears once the best action settles. Watch how good moves ripple outward from the goal.

<p class="hint">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: repeat(4, 74px); gap: 5px; margin: .4rem 0; }
.cell { width: 74px; height: 74px; border-radius: 8px; position: relative;
        display: flex; align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; border: 1px solid #cdd9e3; }
.normal { background: #eef3f7; color: #1d3557; }
.goal { background: #2a9d4a; color: #fff; border-color: #1f7a38; }
.pit  { background: #e63946; color: #fff; border-color: #c92f3c; }
.wall { background: #3a4654; border-color: #2c3540; }
.arrow { position: absolute; bottom: 3px; right: 6px; font-size: 18px; color: #1d3557; }
.val { position: absolute; top: 4px; left: 6px; font-size: 12px; opacity: .85; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Value iteration repeats one simple rule, the Bellman update: the value of a state is the best action's expected reward plus the (discounted) value of wherever you might land. Sweep after sweep, the estimates settle to the true optimum — and the arrows become the optimal policy.

Here is the good news: solving a finite MDP is not one of the impossible problems. Its status is solved and tractable.

• Value iteration, introduced by Richard Bellman in 1957, converges to the optimum. Each sweep shrinks the error by a factor of the discount γ, so the values approach the true answer geometrically fast.
• Policy iteration (Ronald Howard, 1960) alternates between evaluating a policy and improving it, and reaches the exact optimal policy in a finite number of steps.
• Linear programming solves an MDP exactly in polynomial time in the number of states and actions — so the core problem sits comfortably inside P.

So why does anyone struggle? Because the number of states can explode. A robot with ten sensors, each reading one of ten values, has $10^{10}$ states — Bellman himself coined the phrase "the curse of dimensionality" for exactly this. The math is easy; the bookkeeping is what grows.

That is where reinforcement learning steps in: when you cannot even write down all the states, or you do not know the transition odds, you sample experience instead. The MDP stays the underlying model — the same one that powers Bayesian inference when uncertainty is in play.

"Make a sequence of decisions, each with uncertain consequences, to maximize long-run reward" describes an enormous slice of the real world:

• Robotics and control: navigation, manipulation and self-driving stacks plan over MDPs to act despite noisy sensors and actuators.
• Game-playing AI: the reinforcement-learning systems behind game-mastering agents treat each position as a state and learn a policy by trial and error.
• Operations: inventory restocking, maintenance scheduling and queue management are textbook MDPs balancing cost now against cost later.
• Finance and healthcare: optimal trade execution and adaptive treatment plans are decision sequences under uncertainty.
• Recommendation: choosing what to show next to maximize long-term engagement is naturally a sequential decision problem.

Wherever decisions chain together and the world answers with probabilities, an MDP is lurking — often paired with the sampling tricks of reinforcement learning and probabilistic reasoning.

A Markov decision process is one of the most elegant ideas in computing: hand it states, actions, rewards and the odds, and it hands back the best move for every situation you could find yourself in. Better still, the problem is solved — value iteration, policy iteration and linear programming all reach the optimum, the last of them in polynomial time.

The remaining difficulty is never logical impossibility; it is sheer size. When the states are too many to enumerate, we stop solving the MDP exactly and start learning it from experience. But the target never changes: the same crisp question — what is the best action here? — and the same satisfying answer that ripples out, cell by cell, from the goal.