Trajectory Sampling in RL

Plan only where you will actually go. Simulate rollouts from the start state under your current policy and spend every planning update there.

Forty planning updates spread over ten states leave the start value at 0.46, while the same forty updates along one four-state rollout bring it to 6.04 against a true 7.29

Why Does This Exist?

Planning with a model means using simulated experience to improve values before acting. The default way is uniform sweeping: back up every state in round robin, each getting an equal share of compute. On a toy grid that converges everywhere, eventually. On anything realistic it drowns: with a million states and a thousand that matter, $99.9$ percent of backups polish states the agent will never visit, while the bottleneck states on the actual path starve.

Trajectory sampling spends the budget where the agent goes. Start from the start state, simulate a rollout under the current policy with the learned model, and update along that trajectory. Update frequencies then match the on-policy visit distribution: busy states get refined constantly, unreachable states cost nothing. The tradeoff is real and worth stating up front: with a small budget, trajectory sampling wins by a mile; with an infinite budget, uniform sweeps converge everywhere including irrelevant corners. Since compute is never infinite, this page teaches the rollout version. Its closest relatives are prioritized sweeping, which orders backups by error size, real-time dynamic programming, which interleaves planning with acting, and Monte Carlo tree search, which grows a search tree from the current state.

The one idea you need first.

A Bellman backup refreshes one state's value from its successors: $V(S) \leftarrow V(S) + \alpha[R + \gamma V(S') - V(S)]$ , where $R$ is the simulated reward, $\gamma$ discounts the future, and $\alpha$ is the step size. Planning is just choosing which states get this backup and in what order. Uniform sweeping chooses round robin. Trajectory sampling chooses "wherever the rollout goes."

Think of It Like This

Routing Seattle to San Francisco

Your GPS must route you from Seattle to San Francisco. A uniform sweeping router loads every intersection on the continent, from Anchorage to Key West, and recomputes all of them in turn. Your fan spins for hours calculating left turns in Ohio that cannot possibly be on your route.

A trajectory sampling router starts at your position, projects corridors south along the plausible highways, and refines junctions along those corridors only. Every cycle of compute lands on roads you might drive. You get a near-optimal itinerary in milliseconds because $100$ percent of the budget went to the reachable corridor.

Where it stops: highways do not move, while an RL policy changes what is reachable as it learns. A router that only ever refines its first guess can miss a better corridor entirely, which is why rollout policies must keep exploring, the subject of the first pitfall below.

How It Actually Works

Rollouts distribute updates by visit frequency

Start at $S_0$ , pick actions from a rollout policy (usually $\epsilon$ -greedy in the current values so new corridors stay visible), query the model for $S'$ and $R$ , apply the backup above, step forward, and repeat to the horizon. Do this many times. A state visited on half the rollouts gets roughly half the updates. Formally the frequencies approximate the discounted on-policy distribution $d^\pi(s)$ , proportional to how often the policy lands in $s$ weighted by $\gamma^t$ . Nothing ever samples the unreachable remainder, which is the entire savings.

Under a tight budget this focuses effort exactly where value accuracy changes decisions. Under an infinite budget it converges the reachable region and ignores the rest, while uniform sweeping converges everything slowly. For real tasks only the reachable region matters, so the tradeoff favors rollouts wherever models are cheap to query.

Worked comparison

Ten states, task chain $S_0 \to S_1 \to S_2 \to S_3 \to$ terminal, six more states unreachable. Reward $0$ until exiting $S_3$ for $+10$ . Discount $\gamma = 0.9$ , step $\alpha = 0.5$ , budget exactly $40$ backups, all values start at $0$ . True values working backward: $V(S_3) = 10.00$ , $V(S_2) = 9.00$ , $V(S_1) = 8.10$ , $V(S_0) = 7.29$ .

Uniform sweeping runs $4$ round-robin passes over all $10$ states, so each chain state gets $4$ updates while $24$ of the $40$ backups ( $60$ percent) go to unreachable states. Result: $[0.4556, 2.5312, 6.1875, 9.3750]$ against truths $[7.29, 8.10, 9.00, 10.00]$ , mean squared error $\mathbf{21.5051}$ . The start state barely knows a goal exists.

Trajectory sampling runs $10$ simulated rollouts of $4$ states, so each chain state gets $10$ updates and zero budget leaks elsewhere. Result: $[6.0370, 7.6570, 8.9033, 9.9902]$ , mean squared error $\mathbf{0.4439}$ . Same $40$ updates, about a 48-fold error reduction ( $21.5051 / 0.4439 \approx 48.4$ ), and the start value $6.04$ already smells the goal at $7.29$ .

Code

The comparison as a script: uniform round robin versus on-policy rollouts on the same budget.

1from typing import Dict, List2
3
4def run_uniform(chain: List[int], total: int, gamma: float, alpha: float, reward: float) -> Dict[int, float]:5    """Round-robin backups over all states; unreachable states self-loop."""6    values = {s: 0.0 for s in range(total)}7    for _ in range(40 // total):8        for s in range(total):9            if s in chain:10                i = chain.index(s)11                target = reward if i == len(chain) - 1 else gamma * values[chain[i + 1]]12            else:13                target = gamma * values[s]14            values[s] += alpha * (target - values[s])15    return values16
17
18def run_rollouts(chain: List[int], gamma: float, alpha: float, reward: float) -> Dict[int, float]:19    """Simulated on-policy rollouts from the chain start; 4 backups each."""20    values = {s: 0.0 for s in range(10)}21    for _ in range(40 // len(chain)):22        for i, s in enumerate(chain):23            target = reward if i == len(chain) - 1 else gamma * values[chain[i + 1]]24            values[s] += alpha * (target - values[s])25    return values26
27
28chain = [0, 1, 2, 3]29vu, vt = run_uniform(chain, 10, 0.9, 0.5, 10.0), run_rollouts(chain, 0.9, 0.5, 10.0)30print(f"{vu[0]:.4f}")  # -> 0.455631print(f"{vt[0]:.4f}")  # -> 6.0370

The start values match the hand computation: $0.4556$ swept thin against $6.0370$ focused.

Watch Out For

Greedy rollouts lock onto the first decent path

With a purely greedy rollout policy ( $\epsilon = 0$ ), the planner simulates the same trajectory every time once values lean anywhere. Symptom: values along one corridor converge beautifully while a neighboring branch holding a big reward stays at initialization forever, and the agent defends its mediocre policy with straight-faced confidence.

Roll out with exploration: $\epsilon$ -greedy with $\epsilon$ around $0.1$ to $0.2$ during simulation, so trajectories branch into unvisited states. If a branch then reveals a large error, pair the rollouts with prioritized sweeping so the surprise propagates backward instead of waiting for a lucky rollout to revisit.

Planning on a stale model compounds the error

Trajectory sampling trusts the model every step of every rollout, so model bias accumulates with rollout length. Symptom: planning curves improve while real performance stalls or drops, and longer simulated horizons make it worse rather than better.

Keep rollouts short when the model is fresh, re-fit the model on real transitions often, and distrust any plan that only works at horizons far beyond what the model was validated on. If real returns disagree with simulated ones, the model is guilty until proven otherwise, not the backup order.

The Quick Version

Uniform sweeping backs up every state equally, spending most of its budget on states the agent will never visit.
Trajectory sampling simulates rollouts from the start under the current policy, so update frequencies match the on-policy visit distribution.
On a 4-state chain with a 40-backup budget, rollouts reach error 0.44 while uniform sweeps sit at 21.51, a 48-fold gap.
Rollout policies must explore with epsilon around 0.1 to 0.2, or planning locks onto the first decent path and goes blind.
Short rollouts and a freshly fit model keep compounding model error from eating the planning gains.
With unbounded compute, uniform sweeps converge everywhere; with any real budget, rollouts win where it counts.