Plan with it: search at decision time

Lesson 8 ended on a search: draw 128 random nudges from the model, keep the best, and 83 % of the launches hit a goal no policy had practised for. That was a plan one step long. Here it becomes a sequence, in the maze of task T5, where a wall of 11 posts stands between ball and goal: search the model for the best sequence of impulses, run only the first, look, and search again. Planning 12 steps ahead the ball docks in 0 of 20 episodes, planning 60 in 20 of 20. Re-planning lets the search look past what its model can be trusted for; what it cannot do is look far for cheap: the maze needs about 50 steps even from an exact model, each paid for at every decision.

The thesis, here

Planning is search at the moment of decision: score candidate action sequences by running them through the model, take the best, run its first action, and search again from where the world put the agent. Only the first action is used, so a plan's far end, where lesson 6's errors are largest, serves as a direction and not as a promise: the loop docks at horizons well past the one the model can be believed for (measured with a smooth model error). It cannot make the look-ahead cheap: how far a plan must look is set by how far the cost misleads, counted in model steps (even an exact model needs about 50 in the maze), no search effort replaces them, and each is paid for in model evaluations at every decision.

Linear position

Forced by: Practice produces a policy that is only as good as the model was where it practiced. When the goal changes, or the situation is new, the policy has nothing to say. What if the agent used the model at the moment of decision, searching over what to do next, and what does it do about a model that is trustworthy for only a few steps?
New idea: choose each action by searching the model: sample action sequences, score each by the model's predicted cost over a horizon, refit the sampler to the best, run the first action, and plan again from the real state. Re-planning corrects the model at every step, so the far end of a plan is a direction, not a promise; the horizon has to reach the first place where the cost stops misleading.
Forces next: A planner can look past the horizon its model is trustworthy for, because it re-plans and uses the far end of a plan as a direction. But the maze already needed about fifty steps of look-ahead, each paid for at every decision, and the tasks that matter, crossing a building or cooking a meal, take thousands. A better model lowers the error of each step, not the number of steps; the way to look farther at the same price is to take fewer, bigger steps. How can a model predict in jumps, and what does it lose?

The plan

Seven moves. (1) Turn lesson 8's search into a plan over many steps, and count its cost. (2) Search by random shooting. (3) Derive the cross-entropy method. (4) Run the first action and plan again. (5) Find the horizon the maze needs, and why no search effort replaces it. (6) Search a tree instead of a sample, as MuZero does. (7) Price a decision, and see where that stops.

1 · From one decision to a plan

Lesson 8's search drew, for each of 60 launches, 128 random nudges and kept the best by penalised imagined return; the world agreed on 83 % of the launches (the model had said 88 %), with no practice. That was planning with a horizon of one step: a candidate was two numbers and the model's answer was the whole ending. Here the task is a sequence of decisions.

Task T5 is a maze. A wall of 11 round posts stands across the courtyard at x = 4 m, with a gap of 1.1 m above the top post. The ball starts at rest within ±10 cm of (1, 1); the goal is a disc of radius 0.45 m at (7, 1), 6 m away. On each of 160 steps (0.1 s) the agent picks an impulse a with |a| ≤ 0.6 m/s, and friction multiplies the velocity by 0.9656 per step. An episode succeeds if at some step the ball is inside the goal and slower than 0.5 m/s: it must arrive and stop, which we call docking. The straight line is blocked, and the way round goes first up and away from the goal, 8.9 m by way of the point (4, 4.3) in the gap.

A plan is a sequence of H impulses, 2H numbers. The model rolls it forward to predicted positions ŝ₁, …, ŝ_H, and its cost is

J = 0.2 · Σ_t=1…H dist(ŝ_t) + 3 · dist(ŝ_H)

where dist is the distance to the goal: stay close all along, and end close. Planning is finding the plan of least cost; lesson 8's search is that problem at H = 1. A planner spends model steps. Scoring one plan takes H of them, so a decision that scores N plans takes NH: 18,000 for N = 300 and H = 60. The model is the Courtyard's own dynamics, so that we measure the planner and not a fit; to see what a wrong model does we mis-set its friction (×1.15, ×1.3, ×3), a smooth error that grows along a plan, as lesson 6's did.

2 · Search without structure: random shooting

The simplest search is lesson 8's. Draw N plans with every number independent and normal, standard deviation 0.3 m/s (half the largest impulse), score each in the model, keep the cheapest: random shooting. Its weakness is geometric: a plan is a point in 2H dimensions, and the plans nearly as good as the best are a sliver of the draws. With only two values per number there are already 2^2H plans: 64 at H = 3, 16,777,216 at H = 12, 1.3 × 10³⁶ at H = 60.

Measure it from the start state, as the mean over six repeats of the best cost found. At H = 60 the best of 300 plans costs 56.3, of 3,000 46.6, of 30,000 38.4, of 300,000 36.2: each factor of ten in model steps buys less than the one before. Against the cheapest plan found in §3:

horizon H	3	12	25	60
cheapest found (6,000 plans, §3)	20.4	21.0	30.2	30.4
random shooting, 300 plans	20.8	25.8	33.5	56.3
shooting's excess	1.6 %	23 %	11 %	85 %

The excess does not grow smoothly with H, because what matters is how thin the set of good plans is. Of 20,000 random plans, those that cost within 10 % of the cheapest found number 19,959 at H = 3, 0 at 12 (the ball has 12 steps to cover the 2.7 m to the wall), 53 at 25 and 0 at 60 (it must also thread a gap 1.1 m wide). When only the first action of a plan will be used (§4), shooting can still serve; when the plan itself matters, more draws are a poor way to a better one.

3 · Refit the sampler: the cross-entropy method

The cheap plans of one round say where to draw the next. Let the sampler be a Gaussian q with its own mean and spread for each of the 2H numbers, and let p be the distribution of the cheapest sixth of its draws, the elite. Among Gaussians with independent coordinates, the one closest to p in cross-entropy, −E_p[ln q] (the maximum-likelihood fit to draws from p), has the mean and variance of p in every coordinate. So the update is: draw N plans, keep the best K, set each number's mean and spread to the elite's, repeat. This is the cross-entropy method of Rubinstein (1997). Ours: N = 60, K = 10, 5 rounds, from the sampler of §2 with the spread kept above 0.02 m/s, and a fresh start at every decision: 300 plans, shooting's budget. PlaNet (Hafner et al., 2019) plans with it in a learned latent space (H = 12, 10 rounds of 1,000 candidates, refit to the best 100); V-JEPA 2-AC (Assran et al., 2025) uses it to plan toward a goal image.

What it buys, at H = 60 from the start: with 300 plans the best cost is 48.0 against 56.3 for shooting; with 6,000 (600 per round, 10 rounds) it is 30.4, which 300,000 random plans (36.2) do not reach: a better plan for at least 50 times fewer evaluations.

How fast does a round narrow the search? Take the friendliest cost, a bowl J = |a − a*|², with the sampler centred on the optimum and d = 2H numbers. The elite are the draws with |z|² ≤ c, where z is the draw in units of the spread and c the point below which a sixth of the χ²_d distribution lies. By symmetry the variance left in one coordinate is

v_d = E[z₁² | |z|² ≤ c] = (1/d) E[|z|² | |z|² ≤ c] = P(χ²_d+2 ≤ c) / P(χ²_d ≤ c)

because s f_d(s) = d f_d+2(s) for chi-square densities. Each round multiplies the spread by √v_d: 0.297 for d = 2, 0.782 for 24 (H = 12), 0.903 for 120 (H = 60), 0.976 for 2,000 (H = 1,000), about 1 − 1.06/√d for large d; drawing and counting confirms the formula to 2 %. After five rounds the spread left is 0.002, 0.29, 0.60 and 0.89 of the start. The refit narrows a search in many numbers slowly: five rounds are a descent and not a solve.

4 · Run the first action, then plan again

A plan is a promise about 2H numbers. The model that made it is wrong more the farther it runs (lesson 6), and the search that chose it picked the plan the model flatters most (lesson 8). So run only the first impulse, look at where the world put the ball, and plan again from there: a receding horizon, or in control engineering model-predictive control. TD-MPC (Hansen et al., 2022) and V-JEPA 2-AC run this loop on a learned model, and LeCun (2022) calls his planning mode akin to it.

What it repairs, for a model whose error is smooth. Give the planner a model with 15 % too much friction, plan once at the start with a larger search (8 rounds of 300, the best 30 kept: eight times a decision's) and run the plan blind. At H = 80 the model says the ball docks in 7 of 20 episodes and the world delivers 3; at H = 100 it promises 16 and delivers 3. With the exact model the promise is kept (17 of 20 at H = 100). The same wrong model in the receding loop docks 20 of 20 at H = 80 and 20 at 100, and with 30 % too much friction 20 of 20 at H = 60: the wrong friction cost the one-shot plan most of its docks and, from H = 60 on, the loop none.

Why? Measure the plan's promise as lesson 6 measured a rollout's: roll each plan the loop makes with the 15 % model in the model and in the world, and take the median distance between the two positions after k steps: 0.055 m at 12, 0.45 at 40, 0.70 at 60. The trustworthy horizon, the first step at which that median crosses a tolerance, is 12 steps at 5 cm and 40 at the goal's radius (9 and 31 with 30 % too much friction). Yet the loop docks 20 of 20 at H = 60, beyond both. The far end of the plan is not used as a promise but as a direction (head for the gap), and the next decision, with a fresh look at the world, corrects what was wrong. That suffices while a direction is all the far future has to supply (§7). The loop forgives a poor search in the same way: random shooting with the same 300 plans also docks 20 of 20 at H = 60, in a mean of 74 steps against 66, though its best plan costs 56.3 against 48.0.

5 · How far must it look? The maze decides

Run the receding loop on the exact model, 20 episodes per horizon. Docks of 20: 0, 0 and 0 at H = 5, 12 and 25; 1 at 35, 5 at 40, 14 at 45, 18 at 50, 20 at 60, and 20 at 80 and at 100. A step between 35 and 50, then flat: up to 100 a longer horizon never docked fewer episodes. The model is exact, so the step is the task's and not the model's: no better model moves it.

To see why, look at the first decision alone. From the start, search the model for the cheapest plan (12 searches of 2,400 plans) and ask whether it goes round the wall. Up to H = 30 none of the 12 does (0); at 35, 1; at 40, 5; at 45, 9; from 50 all 12 do: the same sigmoid as the docks, in the same place. A short plan that runs at the wall ends 3.3 m from the goal. The way round is farther than that for most of its length (4.5 m at the middle of the gap) and wins only if enough steps remain after the gap to bring the distance down. The model knows the wall; the cost knows only the distance. A short horizon is not a noisy plan but a confident wrong one, and the loop runs it at every step.

The horizon needed is counted in the model's own steps. With friction ×3 in the model (its ball loses speed three times as fast) the loop docks 0 of 20 at H = 60, 3 at 80, 16 at 100 and 20 at 130; 15 % too much friction moves it only a little (14 of 20 at 50, against 18).

Road not taken · a bigger search at H = 12

PlaNet's planner scored 1,000 candidates for 10 rounds at H = 12. Here that is 120,000 model steps a decision, against 3,600 for ours, and still 0 of 12 such searches ends in a plan that goes round the wall. Search effort improves the plan the cost asks for; it cannot change what the cost asks for.

Road not taken · shape the cost

Measure distance round the wall, by way of (4, 4.3), instead of straight. A plan of 5 steps then docks 20 of 20 episodes in 30 steps on average, and 12 steps dock 20 of 20. The horizon was needed only to see past the wall to where the cost falls, and this works only because we told the cost where the gap is. TD-MPC learns such a cost-to-go instead, a terminal value with a horizon of 5; a value is an estimate like any other, and lesson 8's optimiser will look for its mistakes.

The widget

Plan with the model: horizon, search and a wrong model

Top left: the maze, the ball (cyan), this decision's plan in the model (purple) and in the world (red dashed), and its candidates. Top right: best cost against plans tried. Bottom right: model minus world along the plan. Bottom left: does the cheapest plan go round the wall, by horizon, and your 20-episode runs.

horizon H = 60 decision 0 episode 0 the planner's model search execute cost

this episode docked at

—

closest to the goal

—

plan goes round the wall

—

best cost: CEM / shooting

—

promise holds to 5 cm / 0.45 m

—

model steps per decision

—

model steps this episode

—

cheapest plan goes round, of 12

—

20 episodes

—

Show the core JS

      for (j = 0; j < d; j++) plans[i][j] = mu[j] + sd[j] * gauss();
      cost[i] = cf(step, s0, plans[i], H);
...
    order.sort(function (a, b) { return cost[a] - cost[b] || a - b; });
...
      m = 0; for (k = 0; k < el; k++) m += plans[order[k]][j] / el;
      s2 = 0; for (k = 0; k < el; k++) { e = plans[order[k]][j] - m; s2 += e * e / el; }
      mu[j] = m; sd[j] = max(sqrt(s2), SIGMIN);
...
      r = L9.decide(c, s, t); msteps += r.evals * c.H;
      a = L9.clip(r.v[0], r.v[1]); o = real(s[0], s[1], s[2], s[3], a[0], a[1]); s = [o[0], o[1], o[2], o[3]]; states.push(s);

What to try. The default is H = 60, the exact model, episode 0: the ball docks at step 58, and the purple plan at decision 0 goes through the gap. Drag the horizon to 12: the ball parks 3.25 m from the goal, and the bottom-left panel shows why: cheapest plans that go round rise from 0 of 12 at H = 30 to 9 at 45 and 12 at 50. Press run 20 episodes at 12, 45 and 60: 0, 14 and 20 docks. At decision 0 the best-cost readout is 56.4 for the cross-entropy method and 59.6 for shooting (single searches; §2 averages six), yet with random shooting H = 60 still docks 20 of 20, in 74 steps against 66. Set the model to ×1.15 and the execution to plan once, H = 80, and run 20: 3 dock where the model promised 7; the bottom-right panel shows the plan's error crossing the goal radius at step 30. Re-plan at H = 100: 20 dock; with friction ×3 the loop needs H = 130 (20). Last, distance round the wall at H = 5: 20.

6 · A tree instead of a sample

With a few discrete actions, say 8 directions, the plans are the leaves of a tree: 8⁵ = 32,768 at depth 5, 1,073,741,824 at depth 10, 1.3 × 10³⁶ at 40 (§2's 2¹²⁰ plans, since 8⁴⁰ = 2¹²⁰). MuZero (Schrittwieser et al., 2020) searches such a tree by Monte Carlo tree search, 800 simulations a move in board games and 50 in Atari. Each simulation walks down from the root steered by a learned policy and value, expands one leaf with a learned model and backs the leaf's value up its path. The model is trained over 5 unrolled steps to predict reward, policy and value, not to reconstruct the observation. 800 simulations reach at most 2.4 % of the leaves at depth 5 and 7.5 × 10⁻⁷ of those at depth 10: most of the tree is never seen, and the search works because the value at a leaf stands for everything below it. TD-MPC's bargain: a learned value buys the depth.

7 · What a decision costs, and where it stops

The bill is paid at every decision. The loop at H = 60 spends 18,000 model steps a decision, and episode 0 (58 decisions) 1,044,000: practice (lesson 8) pays once, planning pays again for every step and every new goal. Learned models make a step dear: V-JEPA 2-AC scores 800 samples for 10 refinements (8,000 candidates) in 16 seconds per action, where a baseline with 80 samples and a horizon of 1 took 4 minutes; 1,000 actions at 16 seconds take 4.4 hours.

Now stretch the task. The maze needs about 50 steps and its model's promise holds to 5 cm for 12 of them; a direction was enough. Tasks that matter, crossing a building or cooking a meal, take thousands of steps, and where the far future matters in detail there is no such luxury (arithmetic here, not a measurement). At H = 1,000 the plan is 2,000 numbers, a refit that on a bowl leaves 89 % of the spread after five rounds and needs about 96 rounds to shrink it tenfold, 300,000 model steps a decision for 300 plans, and a promise that covers 1.2 % of the plan.

What this lesson did not do

The model was the Courtyard's own dynamics with a friction we mis-set, not a network: a learned model's errors are not smooth, and at a contact it has never seen the loop can be led into the wall; lesson 8's penalty was not used inside the planner. The planner starts fresh at every decision, costs were deterministic, so planning over a distribution of futures (lesson 5) is not here, and the tree search is counted, not built. A longer horizon never cost docks (§5), only the bill and some speed (76 steps at 100 against 66 at 60); a model with rough errors might, and we did not look. A rate of 14 of 20 has a standard error of 0.10, so the step's position is good to a few steps of horizon, not one.

Common mistakes / failure modes

"plan only as far as the model is accurate"

The promise holds to the goal's radius for 40 steps (15 % too much friction), yet the loop docks 20 of 20 at H = 60; a blind plan at H = 100 docks 3 where the model promised 16 (§4).

"a better search replaces a longer horizon"

Of 12 PlaNet-sized searches at H = 12, 0 end in a plan round the wall; of 12 of ours at H = 50, all 12 do (§5).

"random shooting is hopeless"

In the loop it docks 20 of 20 at H = 60, though its plans cost more: 36.2 for the best of 300,000 against 30.4 for 6,000 refitted (§2, §4).

"re-planning fixes a wrong model"

It fixed 15 % and 30 % too much friction (20 of 20 at H = 60 for both). With ×3 it docks 0 at 60 and needs 130 (§5).

Checkpoint exercise

Try it

On a quadratic bowl one round of the cross-entropy method multiplies the spread by √v_d, with the values of §3. (a) How many rounds bring the spread from 0.3 to 0.03 m/s for H = 12 (d = 24) and for H = 60 (d = 120)? (b) Our planner stops after 5 rounds: how much of the spread is left at H = 60? Answer: (a) The spread must fall by 0.3/0.03 = 10, so the rounds are ln 10 / (−ln √v_d) = 9.4 for H = 12 and 22.5 for H = 60 (from the unrounded factors): 10 and 23 whole rounds. (b) 0.903⁵ = 0.60, about 60 %: a five-round search is stopped well short of converged.

Where this points next

A model can now be searched at the moment of decision, and re-planning makes the search tolerant of its smooth errors: with 30 % too much friction the loop still docks 20 of 20 at H = 60. But the maze needed about 50 steps of look-ahead even from an exact model, against a promise of 12 steps to 5 cm from a wrong one, and the loop got away with that because a direction was enough. Where a task takes thousands of steps (§7), the promise covers 1.2 % of the plan and every step is paid for at every decision. A better model lowers the error of each step, not their number; fewer, bigger steps would lower the number. How can a model predict in jumps, and what does it lose?

Takeaway

Planning is search at the decision: score action sequences with the model, run the first action of the best, search again. Random shooting thins out as plans lengthen; refitting a Gaussian to the elite is the cross-entropy-optimal update, and on a bowl it narrows the search by √v_d a round, slowly. Re-planning repairs smooth model error: with 15 % too much friction at H = 100 a blind plan docks 3 of 20 where the model promised 16, the loop 20. The look-ahead needed is how far the cost misleads, counted in the model's steps: about 50 here even for an exact model, 5 for a cost that knows the way round, 130 for a model whose ball loses speed three times as fast. Each step is paid at every decision, and past the model's trustworthy horizon a plan is a direction, not a promise.

Interview prompts

Why does a planner re-plan after every action? (§4 — the model's error grows along a plan and the search picked the plan the model flatters; only the first action is committed.)
Derive the cross-entropy update. (§3 — the Gaussian nearest the elite in cross-entropy has the elite's mean and variance.)
Why can random shooting serve in a closed loop and still be a poor planner? (§2, §4 — only the first action is used, but the plan's quality falls as 2H grows.)
What sets the horizon a planner needs? (§5 — how far the cost misleads, counted in the model's steps; a cost that knows the way round needs almost none.)
What does MuZero's search add to sampling plans, and what does it need? (§6 — a tree over discrete moves steered by a learned policy and value; the value stands in for the depth.)
How does a decision's cost scale, and where does it break? (§7 — N·H model steps; the refit slows in 2H dimensions; the promise covers a shrinking share.)

Companion reads: Reinforcement Learning · 04 Model and planning (dynamic programming to MCTS) and Lesson 25 · Horizon, memory, and the quadratic bill (the cost of a long horizon).