Introduction

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.

Try It: Solve the Grid World

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">A slippery grid world. <b>Green</b> = goal (+1), <b>red</b> = pit (&minus;1), <b>dark</b> = wall. Each step costs &minus;0.04. Moves are noisy: 80% forward, 10% slip left, 10% slip right. Run value iteration and watch the optimal action (the arrow) emerge in every cell, rippling outward from the goal.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Sweep 0 — press Step or Solve.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="solve" type="button">Solve</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Value iteration on a 3x4 grid world (Russell & Norvig's classic).
// States are cells; actions = N,E,S,W. Movement is noisy: 0.8 intended, 0.1 to each perpendicular side. Goal=+1, pit=-1 are terminal absorbing
// states. Living reward (step cost) = -0.04. Discount gamma = 1.
// Bellman update: V(s) = max_a sum_s' P(s'|s,a) [ R + gamma*V(s') ].
// Value iteration converges to the unique optimal V*, and the argmax gives the optimal policy (Bellman, 1957). The known optimum here is a policy that steers the agent up and around the pit to the +1 goal.
const ROWS = 3, COLS = 4, GAMMA = 1, STEP = -0.04;
// layout: row 0 top. (0,3)=+1 goal, (1,3)=-1 pit, (1,1)=wall.
const GOAL = '0,3', PIT = '1,3', WALL = '1,1';
const key = (r,c) => r+','+c;
const isTerminal = k => k===GOAL || k===PIT;
const isWall = k => k===WALL;
const reward = k => k===GOAL ? 1 : k===PIT ? -1 : STEP;

// actions and their (dr,dc); slips are the two perpendicular directions.
const ACT = { '↑':[-1,0], '→':[0,1], '↓':[1,0], '←':[0,-1] };
const PERP = { '↑':['←','→'], '↓':['←','→'], '→':['↑','↓'], '←':['↑','↓'] };

function move(r,c,a){
  const [dr,dc] = ACT[a]; let nr=r+dr, nc=c+dc;
  if(nr<0||nr>=ROWS||nc<0||nc>=COLS||isWall(key(nr,nc))) return key(r,c); // bounce
  return key(nr,nc);
}
// expected value of taking action a from state (r,c) given value map V
function qValue(r,c,a,V){
  let q=0;
  const dirs=[[a,0.8],[PERP[a][0],0.1],[PERP[a][1],0.1]];
  for(const [d,p] of dirs){ const ns=move(r,c,d); q += p*(reward(key(r,c)) + GAMMA*V[ns]); }
  return q;
}

let V, sweep, policy;
function init(){
  V={}; policy={}; sweep=0;
  for(let r=0;r<ROWS;r++)for(let c=0;c<COLS;c++){ const k=key(r,c);
    V[k] = isTerminal(k) ? reward(k) : 0; }
}
// one synchronous Bellman sweep; returns max change.
function bellmanSweep(){
  const NV = Object.assign({}, V); let delta=0;
  for(let r=0;r<ROWS;r++)for(let c=0;c<COLS;c++){ const k=key(r,c);
    if(isWall(k)||isTerminal(k)) continue;
    let best=-Infinity, bestA=null;
    for(const a in ACT){ const q=qValue(r,c,a,V); if(q>best){best=q;bestA=a;} }
    NV[k]=best; policy[k]=bestA; delta=Math.max(delta, Math.abs(best-V[k]));
  }
  V=NV; sweep++; return delta;
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }
function render(){
  const g=document.getElementById('grid'); g.innerHTML='';
  for(let r=0;r<ROWS;r++)for(let c=0;c<COLS;c++){ const k=key(r,c);
    const d=document.createElement('div');
    let cls='cell '+(k===GOAL?'goal':k===PIT?'pit':isWall(k)?'wall':'normal');
    d.className=cls;
    if(!isWall(k)){
      const v=document.createElement('span'); v.className='val';
      v.textContent=(V[k]>=0?'+':'')+V[k].toFixed(2); d.appendChild(v);
    }
    if(k===GOAL) d.appendChild(document.createTextNode('GOAL'));
    else if(k===PIT) d.appendChild(document.createTextNode('PIT'));
    else if(!isWall(k) && policy[k]){ const ar=document.createElement('span'); ar.className='arrow'; ar.textContent=policy[k]; d.appendChild(ar); }
    g.appendChild(d);
  }
}
function step(){ const dlt=bellmanSweep(); render();
  if(dlt<1e-4) setStatus(fmt('Sweep %sweep% — converged. Arrows = optimal policy.', { sweep: sweep }),'ok');
  else setStatus(fmt('Sweep %sweep% — max change %dlt%.', { sweep: sweep, dlt: dlt.toFixed(4) }),''); }
function solve(){ let dlt=Infinity, guard=0;
  while(dlt>=1e-4 && guard<1000){ dlt=bellmanSweep(); guard++; }
  render(); setStatus(fmt('Converged after %sweep% sweeps. Arrows = optimal policy.', { sweep: sweep }),'ok');
  console.log('Optimal V:', V); console.log('Optimal policy:', policy); }
document.getElementById('step').addEventListener('click',step);
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ init(); render(); setStatus('Sweep 0 — press Step or Solve.',''); });
init(); render();
Result
Console

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.

The Real Complexity

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 101010^{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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/markov-decision-processes/Content licensed under CC BY-NC 4.0.