How Reinforcement Learning Improves AI Agent Planning
Ask a plain large language model to plan a multi-step task and it will usually produce a plan that reads well — and then quietly fall apart halfway through executing it. Reinforcement learning planning changes the mechanics underneath that behaviour: instead of generating the next plausible step, the agent learns from the outcomes of whole trajectories, so its planning improves with experience rather than with better wording.
Why plain LLM planning breaks down
Planning is sequential decision-making under uncertainty, not text continuation. Each step an agent takes changes the state of the world, and the next step has to make sense given that new state. A language model generating a plan token by token does something much weaker: it picks each step for local plausibility, with no lookahead and no way to simulate what a step will actually do.
The authors of the RAP paper put the gap directly: language models “lack an internal world model to predict the world state and simulate long-term outcomes of actions,” which is what prevents deliberate planning. Without that world model, an early wrong turn becomes the context for every later step. An ICLR 2026 study found the problem is worse than simple compounding: the per-step error rate itself rises as a long task progresses, because models conditioned on their own error-prone history become more likely to err further, and this is not mitigated by scaling model size alone. The same study reports that without chain-of-thought prompting, even a frontier model like DeepSeek-V3 fails at performing even four steps of execution, while its thinking version, R1, can execute over 100 steps.
METR’s time-horizon research shows the practical consequence: frontier models succeed almost 100% of the time on tasks taking human professionals under four minutes, but under 10% of the time on tasks taking over four hours. Prompt-only planning fails in three recurring ways: dead ends, loops, and unrecoverable wrong turns. What all three share is the absence of a scoring signal over whole trajectories.
What reinforcement learning planning adds
Reinforcement learning adds exactly that missing signal. Instead of imitating demonstrations token by token, the policy is updated toward trajectories that earn higher reward. Planning behaviour is learned from trial and error: the agent tries paths, and the ones that succeed become more likely.
Three pieces of machinery do the work. The first is the reward: feedback on outcomes rather than on individual tokens. A plan is judged by whether it reached the goal, not by whether each step sounded reasonable. The second is the value function, which estimates the expected remaining return from a partial plan — letting the agent judge whether a half-finished plan is worth continuing before the final outcome is known. The third is policy improvement: training pushes the planner toward actions that led to high-reward trajectories.
Naive behaviour cloning cannot fix this: a policy trained to mimic experts drifts into states the expert never visited, and Ross and Bagnell showed in 2010 that the cost of naive behaviour cloning grows quadratically with the horizon. Training on the agent’s own trajectories, including its own mistakes, can help address this distribution mismatch.
The RL techniques that improve agent planning
The techniques that matter fall into four groups, depending on where they act: training time, inference time, or the loop between them.
Policy optimisation for agent training. PPO stabilises policy updates by clipping them, but it needs a separate critic network to estimate advantages. GRPO removes the critic by sampling a group of outputs for the same prompt and normalising each reward against the group’s mean and standard deviation, so better-than-average outputs are reinforced. That group-relative comparison breaks down on long-horizon agent tasks, where trajectories have wildly uneven lengths — which is why, according to the research, GLM-5.2 moved back to critic-based PPO for long-horizon RL. Turn-PPO works at the turn level rather than the token level, since different turns in a multi-turn trajectory contribute unequally to the final reward.
Verifiable, outcome-based rewards. Where a task has a checkable answer, the check itself is a useful source of reward. DeepSeek-R1-Zero used only rule-based rewards for accuracy and format, with no neural reward model, because its tasks — maths and code — have programmatic verifiers: an answer is right or wrong, code passes the tests or it does not. Training on those rewards alone lifted R1-Zero from 15.6% to 71.0% pass@1 on AIME 2024, and the full DeepSeek-R1 reaches 79.8% on AIME 2024 and 97.3% on MATH-500.
Search at inference time. RL techniques also improve planning without touching the model’s weights. In RAP, the language model acts as both world model and reasoning agent: it predicts the state resulting from an action, scores candidate actions, and uses Monte Carlo tree search — selection, expansion, simulation, backpropagation — to explore the reasoning tree. On Blocksworld plan generation, RAP on LLaMA-33B achieved 64% average success versus near-zero for chain-of-thought, and surpassed GPT-4 with chain-of-thought by a 33% relative improvement. Outcome reward models score only the final answer; process reward models score each intermediate step and can prune low-scoring branches.
Self-improvement loops. The final group generates its own training data. STaR bootstraps reasoning by generating rationales, keeping only those that reach correct answers, fine-tuning on them, and repeating. For agents, the equivalent loop is training on the agent’s own successful trajectories, which is how SWE-Gym lifted a 32B coding agent from 7.0% to 20.6% on SWE-bench Verified, and with learned verifiers reached 32%.
Training-time vs test-time: two places RL helps
These techniques act in two different places, and confusing them is the most common mistake in this area. Training-time RL bakes better planning behaviour into the model: the weights change, so the same prompt produces better plans on the next run. Test-time search leaves the model frozen and spends more compute at inference — sampling many candidate plans, scoring them, and keeping the best — to buy better plans from the same model. OpenAI reported that o1’s performance consistently improves with more reinforcement learning (train-time compute) and with more time spent thinking (test-time compute).
Test-time scaling works even on strong models. A Meta-led paper on scaling test-time compute for agentic coding, as reported in a secondary write-up, lifted Claude-4.5-Opus from 70.9% to 77.6% on SWE-bench Verified without changing the underlying model.
What each costs is a different question. Training-time RL requires unrolling trajectories and evaluating them, which is expensive and noisy — and flaky tests inject noise directly into the reward signal. How large the compute gap between the two is for a typical coding or web agent remains unresolved: no source directly compares the FLOPs or dollars of training-time RL against test-time search for the same agent task, so any single gap figure would be invented.
A worked example: planning a multi-step task with RL
Consider a task a coding agent faces often: a bug report arrives, and the agent must reproduce the bug, find its cause, write a fix, run the tests, and open a pull request. The steps depend on each other, so a wrong early step wastes everything after it.
Naive prompting stalls on this task in familiar ways. The agent writes a fix for the wrong function, then spends turns defending it against failing tests. Or it repeats the same diagnostic command — a stuck-in-loop behaviour SWE-Gym training reduced by 4.6 to 18.6 percentage points.
With RL, the reward signal is defined over the whole trajectory. The final outcome is verifiable: the reproduction script fails before the fix and passes after it, and the test suite is green. The final signal arrives only at the end of a long sequence, so intermediate rewards are an optional aid to credit assignment rather than a requirement — training on the terminal reward alone is possible, as R1-Zero’s outcome-only training shows. Process reward models score individual steps, and Turn-PPO estimates turn-level advantages rather than measuring each turn’s actual causal contribution.
A plan representation for this task might look like this:
{
"goal": "Fix the failing checkout test and open a PR",
"steps": [
{"id": 1, "action": "reproduce", "check": "repro script fails"},
{"id": 2, "action": "localise", "check": "failing function identified"},
{"id": 3, "action": "patch", "check": "repro script passes"},
{"id": 4, "action": "verify", "check": "full test suite green"},
{"id": 5, "action": "submit", "check": "PR opened with passing CI"}
],
"rewards": {"step_pass": 0.2, "final_pass": 1.0}
}What changes at each decision point is what the agent does with a bad intermediate result. A prompt-only agent that sees its reproduction script fail in an unexpected way often barrels on to a fix anyway. Consider instead a hypothetical agent designed with explicit search and value estimation: it treats the failure as information — the value function scores the current partial plan low, the search backtracks to an earlier branch, and the agent tries a different localisation step instead. That is a design choice, not something RL training guarantees on its own: a trained policy selects actions from what it learned, without necessarily running an explicit search at inference time. The reward function behind that behaviour can be sketched as a simplified illustration — not a production reward function:
def step_reward(state, action, outcome):
if outcome == "test_suite_green":
return 1.0
if outcome == "repro_passes":
return 0.2
if outcome == "same_action_repeated":
return -0.1
return 0.0The structure is the point: reward on verifiable checks at each step, a penalty for loops, and the largest reward for the final outcome.
Where RL planning still fails
The first documented failure mode is the most insidious: reward hacking. The agent optimises the measurable proxy rather than the intended goal, so observed reward rises while hidden safety or quality falls. In one controlled study, direct reward optimisation raised the observed signal while hidden safety performance fell or stayed flat, and the failure survived scaling, credit-assignment fixes, prompt changes and entropy tuning. A mechanistic taxonomy study measured a localised reward-hacking rate of 14.45% for aggressive PPO, with a 95% confidence interval of 10.16–18.75%.
The second failure mode is sparse and delayed rewards. In long-horizon tasks, success signals typically emerge only at the end of long action sequences, which complicates credit assignment for the intermediate steps. Process rewards and turn-level advantages mitigate this, but no established standard exists for rewarding intermediate planning steps where only the final outcome is checkable.
The third is cost: every trajectory must be unrolled and evaluated, and the reward signal is only as clean as the verifier behind it. The fourth is brittleness: a policy trained on one distribution of tasks degrades when the deployment task differs from the training distribution. The evidence base itself has limits: the strongest agent-specific RL results are on coding agents and planning tasks like Blocksworld, not on general agent-planning benchmarks.
When to use reinforcement learning planning — and when not to
RL planning is worth the cost when three properties hold. First, the outcome is verifiable: there is a test, a checker, or a programmatic condition that says whether the plan succeeded — a useful task property, since a checkable outcome provides a direct source of reward. Second, the task repeats: the same class of task recurs often enough that a training run pays for itself across many runs. Third, the stakes per run are high enough that a better plan is worth more than the extra compute — a failed deployment, a corrupted database, or hours of wasted agent time.
When those properties do not hold, cheaper alternatives come first. Better prompts and structured workflows are worth trying first: a plan representation with explicit checks at each step can help catch some dead ends before they waste a run. Test-time search is the next rung: sampling several candidate plans and keeping the best is an alternative to evaluate on the target task — what it costs and gains depends on the method, the sampling budget, and the task.
A simple decision rule follows. If the outcome is checkable, the task repeats, and failures are expensive, invest in training-time RL. If the outcome is checkable but the task is one-off, use test-time search. If the outcome is not checkable at all, RL is harder to apply: learned proxy rewards are possible, but they need careful evaluation for gaming and objective mismatch, as the reward-hacking research shows. And if a prompt or a workflow fix solves the failure, take that first — the cheapest planning improvement is the one that needs no training run.
