Agents that plan by searching around a human-imitation policy are strong in games. Examples are Chess, Go and Diplomacy, where every position has a meaningful score. Long household tasks work differently. The only feedback is whether the whole task succeeded, and many actions (slicing, heating, discarding) cannot be undone. There, the standard recipe breaks in two opposite ways. With a strong pull toward the human policy, search can never fix the human policy's blunders. With a weak pull, or with the exploration bonuses of ordinary tree search, the agent spends its search budget on odd, irreversible actions that have never been seen to succeed.
This note proposes making the pull toward the human policy depend on evidence of success. At each decision, the planner may move away from the imitation policy only as far as the number of successful simulated continuations it has actually observed from that state justifies. When no rollout has succeeded, the planner does exactly what the imitation policy would do. As successes accumulate, it is free to override the human prior. The claim is that this one change makes regularized search safe to run under sparse reward. The planner never does worse than imitation when search finds nothing, and it recovers from imitation's mistakes when search finds something.
Core Claim
Policy-regularized search maximizes expected reward minus a penalty on divergence from a reference policy. The divergence is the Kullback–Leibler (KL) divergence, a standard measure of how different two probability distributions are. Modeling Strong and Human-Like Gameplay with KL-Regularized Search introduced piKL-Hedge, which adds this penalty at each decision node of a regret-matching procedure. Regret matching is an online learner that shifts probability toward actions it regrets not having played. The paper also showed that tree search with a policy prior is already implicitly KL-regularized. Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning sampled the regularization strength from a fixed distribution to model players of different skill.
Both papers motivate this proposal: human-anchored search beats pure imitation, by more than 85% of Chess games won and a 1.4× higher Diplomacy score. Both also assume dense payoffs and a regularization strength that does not depend on the state.
Under sparse binary reward, a fixed strength creates a trade-off that no single value resolves:
- Everywhere the search has seen no success, every action's estimated value is zero. The regularized solution then collapses to the anchor, so the search adds nothing.
- Where the anchor blunders, a strong pull keeps the agent trapped. This is the coverage failure highlighted by KL-Regularized Reinforcement Learning is Designed to Mode Collapse.
The proposal replaces the fixed strength with a trust region whose radius grows with the observed successes. As far as the file shows, this is new relative to piKL-Hedge's fixed penalty and to the skill-dependent strength distribution in the Diplomacy paper. Neither lets the degree of anchoring depend on the reward evidence gathered at a state.
Research Program
The setting is hierarchical, following the planner/controller split used in Do As I Can, Not As I Say (SayCan) and Modular Multitask Reinforcement Learning with Policy Sketches. Planning happens over discrete subgoals, such as "go to counter," "pick up knife," or "slice apple." Low-level controllers, trained by imitation, carry out each subgoal. The anchor $\pi_h(a \mid s)$ is a behavioral-cloning model of which subgoal a human would choose next in state $s$, given the instruction.
At each high-level decision, the planner spends a fixed budget of simulated rollouts. Each rollout commits to a candidate subgoal $a$ and then continues with the anchor to the end of the episode. From these rollouts the planner estimates, for each $a$:
- $\hat{p}(s,a)$, the fraction of rollouts from $a$ that ended in task success;
- $m(s)$, the total number of successful rollouts from $s$.
It runs a Hedge-style online update over these noisy estimates. At its fixed point, the policy is
$$\pi(a \mid s) \propto \pi_h(a \mid s)\, \exp\!\big(\hat{p}(s,a)/\lambda(s)\big).$$
The update is a no-regret learner, which suits a small, noisy rollout budget; logarithmic-regret guarantees for this kind of objective appear in Logarithmic Regret for Online KL-Regularized Reinforcement Learning.
The new ingredient is how the temperature $\lambda(s)$ is set. It is chosen as the smallest value satisfying
$$D_{\text{KL}}\big(\pi(\cdot \mid s)\,\|\,\pi_h(\cdot \mid s)\big) \le \kappa \log\big(1 + m(s)\big).$$
Here $\kappa$ is a single scale parameter tuned on validation tasks. The logarithm makes the deviation budget grow slowly, so that one lucky success cannot license a large departure.
This rule has a property that can be checked directly. When $m(s) = 0$, the budget is zero and the planner reproduces the anchor exactly. The anchor's success rate is therefore a floor that holds by construction, not a hoped-for outcome.
A second, optional stage distills the planner's choices back into the anchor and repeats the process. It is reported separately so the test-time contribution is not confounded with self-training.
The work involves three parts:
- building the rollout planner on the ALFRED simulator and on a crafting environment;
- deriving the monotone-improvement property under exact success estimates, and characterizing the regret cost when the estimates come from $n$ Bernoulli rollouts;
- measuring when evidence gating helps, as a function of horizon length and of the anchor's coverage.
Baselines
Pure imitation (the naive reference point). This is the behavioral-cloning anchor $\pi_h$ run greedily with the same low-level controllers. On ALFRED, the sequence-to-sequence imitation baseline in ALFRED reports 3.7% task success in seen environments and 0.4% in unseen ones, against 91% for humans. Our hierarchical anchor will be stronger than that monolithic model, so it is retrained and reported on the same splits. Any method that falls below it in the no-success regime has failed the basic safety property.
Fixed-strength piKL search. This is the strongest direct competitor: piKL-Hedge run with the identical rollout estimator and budget.
- The single fixed $\lambda$ gets the same tuning budget as our $\kappa$: the same number of validation configurations.
- A second variant samples $\lambda$ per episode from a distribution, as in the Diplomacy work.
- Beating it means strictly higher unseen-environment success at matched rollout budget, with human-likeness no lower than the anchor's.
- No reported result was found on Lacuna for any piKL variant on ALFRED or on the crafting game, so both variants are run by us.
Tree search with the imitation prior. This is PUCT-style Monte Carlo tree search that uses $\pi_h$ as its prior, with the same simulator calls. Jacob et al. showed this search is implicitly KL-regularized, so it is the natural "you already have this" competitor.
Greedy grounded selection (SayCan). This picks the subgoal maximizing anchor probability times the controller's estimated success probability, with no lookahead. SayCan reports 84% planning success and 74% execution success on its real-robot kitchen suite. No reported result was found on Lacuna for SayCan-style selection on ALFRED, so we reimplement it.
Dense-shaping search. This replaces the binary success estimate with a shortest-path shaped step reward in the style of the SPRE method in Process vs. Outcome Reward. That paper reports 34.4% exact match versus 32.8% for outcome-supervised RL, with 18× less data. Those numbers are on retrieval-based question answering, not embodied tasks.
Key ablation. Our planner is run with the trust-region radius fixed to the value it reaches on average. This isolates whether the state-dependence of the radius, rather than its typical size, drives any gain.
All methods share:
- the same anchor and low-level controllers;
- the same per-decision simulator budget, swept over at least three levels;
- the same validation tuning budget;
- the same five seeds.
Why not just…?
Why not just run tree search with the imitation prior, as AlphaZero-style systems do? This is the most serious alternative, because PUCT also loosens its reliance on the prior as visits grow. The difference is what it loosens in response to. PUCT's exploration bonus grows for rarely visited actions whether or not anything has succeeded. With all estimated values at zero, it therefore spreads visits toward low-prior actions, which in ALFRED are often the irreversible ones. We predict that in the no-success regime PUCT falls below the anchor while our planner matches it. The no-success-regime experiment below tests this directly. If PUCT does not degrade there, most of our claimed advantage disappears, and we will say so.
Why not just use a fixed KL strength tuned on validation? A single strength trades anchor-trapping against drift. That trade-off only goes away if, on a given task distribution, the states where the anchor blunders coincide with the states where evidence is plentiful. The anchor-coverage sweep below tests this by planting blunders at controlled depths. If a tuned fixed $\lambda$ matches our planner across the sweep, the gating adds nothing.
Why not just add dense shaped rewards and keep ordinary search? Shaping removes the zero-value regime that motivates gating. Process vs. Outcome Reward shows its value in text tasks. However, the file also notes that intermediate shaping fails when early subgoals have irreversible side effects on later stages, which is exactly ALFRED's structure. We include the shaped baseline, and also shaping combined with our gate, so that complementarity is measured rather than assumed.
Why not just filter successful rollouts and fine-tune the imitation policy on them? This self-imitation strategy is a real threat for the training-time stage. It is essentially what our distillation step does. It does not, however, help at test time in an unseen environment, where no fine-tuning data exist yet. We therefore report test-time planning and distillation separately, and compare distillation against filtered behavioral cloning trained on the same number of successful trajectories.
Proposed Experiments
Controlled testbed: the crafting environment. We use the crafting environment from Policy Sketches, where modular policies reach 77% zero-shot on make bed and monolithic ones score 0%. We extend its recipes to horizons of 5, 10, and 20 subgoals and add consumable, irreversible resources. The anchor is trained on synthetic demonstrations, and in a controlled fraction of states it is made to blunder at a chosen depth. The key plots show success versus blunder rate and versus horizon, at three rollout budgets.
Main benchmark: ALFRED. We use ALFRED's seen and unseen splits and report task success and subgoal progress. Human-likeness is measured as agreement between the planner's subgoal choices and held-out human demonstrations. We also report the KL divergence to the anchor on successful and on failed episodes.
Decisive check 1: the no-success regime. We restrict the rollout budget so that most states see zero successes. The prediction is that our planner equals the anchor while PUCT and weakly regularized piKL fall below it.
Decisive check 2: the blunder-recovery regime. In the crafting sweep, as blunders move deeper and the rollout budget grows, our planner should recover most of the gap to an oracle anchor. Strongly regularized fixed-$\lambda$ search should not.
Decisive check 3: localized deviation. The measured KL divergence of our planner should concentrate in states with nonzero success counts. The fixed-radius ablation should spread its divergence evenly.
Outcome. The proposal succeeds if checks 1 and 2 both hold and ALFRED unseen success exceeds the best competitor at matched budget. It fails, and would be reported as a negative result, if tuned fixed-$\lambda$ piKL or tree search with the prior matches our planner across the sweep.
References
- Modeling Strong and Human-Like Gameplay with KL-Regularized Search
- Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning
- KL-Regularized Reinforcement Learning is Designed to Mode Collapse
- Do As I Can, Not As I Say: Grounding Language in Robotic Affordances
- Modular Multitask Reinforcement Learning with Policy Sketches
- Logarithmic Regret for Online KL-Regularized Reinforcement Learning
- ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks
- Process vs. Outcome Reward: Which is Better for Agentic RAG Reinforcement Learning