Introduction

Most machine learning needs a teacher: show the model a photo, tell it "cat", repeat a million times. Reinforcement learning throws that away. There is no answer key. There is only an agent moving through a world, and once in a while a number — the reward — that says "that was good" or "that was bad."

Think of a robot in a room, a player in a game, a thermostat in a house. Each picks an action, the world changes, and a reward trickles in. The catch: the reward often comes much later than the action that earned it. Reach the goal and you score — but which of the hundred earlier moves deserves the credit?

That is the whole problem. Out of delayed, sparse rewards, the agent must work out a policy: a rule that says, in every situation, what to do next. And the way it does so turns out to be a beautifully simple idea about letting value flow backward from the future.

Watch the Agent Learn

Here is a tiny gridworld. The agent starts somewhere and wants to reach the green goal (+1) while avoiding the red traps (−1). It can move up, down, left or right. At the start it knows nothing — every square is grey, value zero.

<p class="hint">A <b>gridworld</b>: the agent wants the green goal (+1) and fears the red
traps (&minus;1). Each cell shows its learned <b>value</b>. Press <b>Step</b> to run one
sweep of value iteration &mdash; the goal's reward ripples outward, and arrows (the
<b>policy</b>) point the way home.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Sweep 0 — every value starts at 0.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run to convergence</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(5, 58px); gap: 4px; margin: .4rem 0; }
.cell { width: 58px; height: 58px; display: flex; flex-direction: column; align-items: center;
        justify-content: center; border-radius: 8px; border: 1px solid #cdd9e3;
        font: 700 13px ui-monospace, monospace; position: relative; transition: background .25s; }
.cell .arrow { font-size: 18px; line-height: 1; margin-bottom: 1px; }
.cell .val { font-size: 12px; opacity: .85; }
.cell.wall { background: #4a4a4a; border-color: #333; }
.cell.goal { background: #2a9d4a; color: #fff; border-color: #1f7d39; }
.cell.trap { background: #e63946; color: #fff; border-color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.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 5x5 gridworld (a Markov Decision Process).
// States = cells. Actions = up/down/left/right (deterministic; hitting a wall or
// edge stays put). Reward is +1 at the goal, -1 at a trap, 0 elsewhere; goal and
// traps are terminal. Bellman optimality update for a non-terminal state s:
//   V(s) = max_a [ R(s,a,s') + gamma * V(s') ].
// Repeating this sweep converges to the optimal value function and policy
// (Bellman, 1957). For a fixed discount it is a polynomial-time, solved problem.
const R = 5, C = 5, GAMMA = 0.9;
const GOAL = [0, 4], TRAPS = [[1, 4], [2, 1]], WALLS = [[1, 1], [3, 3]];
const key = (r, c) => r + ',' + c;
const isWall = (r, c) => WALLS.some(([a, b]) => a === r && b === c);
const isGoal = (r, c) => GOAL[0] === r && GOAL[1] === c;
const isTrap = (r, c) => TRAPS.some(([a, b]) => a === r && b === c);
const isTerminal = (r, c) => isGoal(r, c) || isTrap(r, c);
const reward = (r, c) => isGoal(r, c) ? 1 : (isTrap(r, c) ? -1 : 0);
const MOVES = [[-1,0,'↑'],[1,0,'↓'],[0,-1,'←'],[0,1,'→']];

let V, sweep;
function init() {
  V = {}; sweep = 0;
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++)
    if (!isWall(r, c)) V[key(r, c)] = isTerminal(r, c) ? reward(r, c) : 0;
}

// Where action (dr,dc) lands from (r,c): off-grid or into a wall -> stay put.
function next(r, c, dr, dc) {
  const nr = r + dr, nc = c + dc;
  if (nr < 0 || nr >= R || nc < 0 || nc >= C || isWall(nr, nc)) return [r, c];
  return [nr, nc];
}

// Best action value from (r,c): max over moves of discounted successor value.
function bestAction(r, c) {
  let best = -Infinity, arrow = '';
  for (const [dr, dc, g] of MOVES) {
    const [nr, nc] = next(r, c, dr, dc);
    const q = GAMMA * V[key(nr, nc)];
    if (q > best + 1e-9) { best = q; arrow = g; }
  }
  return [best, arrow];
}

// One synchronous sweep of the Bellman optimality update over all non-terminals.
function step() {
  const nV = Object.assign({}, V);
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    if (isWall(r, c) || isTerminal(r, c)) continue;
    nV[key(r, c)] = bestAction(r, c)[0];
  }
  let delta = 0;
  for (const k in V) delta = Math.max(delta, Math.abs(nV[k] - V[k]));
  V = nV; sweep++;
  return delta;
}

function render() {
  const g = document.getElementById('grid'); g.innerHTML = '';
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    const d = document.createElement('div'); d.className = 'cell';
    if (isWall(r, c)) { d.className += ' wall'; g.appendChild(d); continue; }
    const v = V[key(r, c)];
    if (isGoal(r, c)) { d.className += ' goal'; d.innerHTML = '<div class="arrow">★</div><div class="val">+1.0</div>'; }
    else if (isTrap(r, c)) { d.className += ' trap'; d.innerHTML = '<div class="arrow">✖</div><div class="val">−1.0</div>'; }
    else {
      const arrow = sweep > 0 ? bestAction(r, c)[1] : '·';
      const t = Math.max(0, Math.min(1, v));
      d.style.background = 'rgba(42,157,74,' + (0.08 + 0.6 * t).toFixed(3) + ')';
      d.innerHTML = '<div class="arrow">' + arrow + '</div><div class="val">' + v.toFixed(2) + '</div>';
    }
    g.appendChild(d);
  }
}
function setStatus(t) { document.getElementById('status').textContent = t; }

function doStep() {
  const delta = step(); render();
  if (delta < 1e-4) setStatus(fmt('Sweep %sweep% — converged. The policy is optimal.', { sweep: sweep }));
  else setStatus(fmt('Sweep %sweep% — value spread outward (max change  %delta%).', { sweep: sweep, delta: delta.toFixed(3) }));
  console.log('sweep', sweep, 'maxDelta', delta.toFixed(5));
  return delta;
}
function runAll() {
  let n = 0, delta;
  do { delta = doStep(); n++; } while (delta >= 1e-4 && n < 100);
}
function reset() { init(); render(); setStatus('Sweep 0 — every value starts at 0.'); }

document.getElementById('step').addEventListener('click', doStep);
document.getElementById('run').addEventListener('click', runAll);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

Press Step to run one sweep of value iteration. Each square asks its neighbours, "what is the best you can promise me?" and updates its own value to the best discounted reward it can reach. Watch the green glow of the goal seep outward, one ring per step, until even the farthest corner knows which way to walk. Then the arrows — the policy — point straight home. No one ever told the agent the route; it fell out of the reward alone.

The Real Complexity

Underneath, reinforcement learning rests on the Markov Decision Process (MDP): a set of states, the actions available in each, the probability that an action moves you from one state to another, and the reward you collect. The goal is a policy that maximises total reward over time, with future reward shrunk by a discount factor.

  • Known model, exact solution. If you know the MDP, the Bellman optimality equation pins down the value of every state, and value iteration or policy iteration (Bellman, 1957; Howard, 1960) converge to the optimal policy. For a fixed discount, policy iteration runs in polynomial time in the number of states and actions — this is a solved problem.
  • The curse of dimensionality. The catch is that the number of states explodes: a chessboard, a robot's joints, a screen of pixels. Enumerating them all is hopeless, so real systems approximate the value with neural networks instead of a table.
  • Unknown model. When the agent does not know the transition probabilities, it must learn them by acting. Now the cost is measured in samples — how much experience is needed — and the exploration-vs-exploitation tradeoff makes guarantees far subtler.

So the elegant core is genuinely tractable, much like solving a shortest path. The frontier is scale and uncertainty: huge or unknown worlds where exact solutions give way to approximation, and the hardness shifts from computing the answer to gathering enough experience to estimate it.

Where It Matters

"Act now, get rewarded later" describes an enormous range of real problems, and reinforcement learning is the toolkit for all of them:

  • Games: from Backgammon to Go and Atari, agents trained on self-play reached and then passed human champions, learning strategies no one taught them.
  • Robotics and control: walking, grasping, balancing and steering are all "pick actions that keep paying off," learned in simulation and transferred to hardware.
  • Operations: datacentre cooling, traffic-light timing, inventory and energy grids are control problems where a good policy saves real money.
  • Tuning AI: large language models are polished with reinforcement learning from human feedback, where the reward is how much a person liked the answer.

Understand value iteration and you have met the engine behind all of it — the same backward flow of value powers neural-network training wherever a system must learn to act, not just to label.

Conclusion

Reinforcement learning hides an almost magical idea behind plain arithmetic: hand an agent nothing but a number that arrives late and rarely, and let it discover, all by itself, the best thing to do in every situation. The trick is to let the value of the goal flow backward until each state knows its worth — and from those values a policy simply falls out.

For a small, known world this is a solved, polynomial-time problem. Scale it up — unknown rules, astronomically many states — and the same idea, wrapped in neural networks and clever exploration, is what taught machines to play Go, steer robots and converse. From one delayed reward, a whole way of acting. That is the quiet power of learning by reward.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/reinforcement-learning/Content licensed under CC BY-NC 4.0.