Branch-and-Commit for Frozen RL Agents: When and Where to Spend Test-Time Compute
Organizations: Technion, Israel Institute of Technology Haifa, Israel · Nvidia Research Israel
Abstract
Reinforcement learning agents are often deployed with policies that cannot be retrained or modified. In digital environments whose states can be copied and resumed, an operator has another option: sample several continuations from the current state, evaluate them, and continue from the endpoint of the selected branch. We call this procedure branch-and-commit. We study when it improves return, what produces the improvement, and where its computational budget should be spent. Across four environments, two frozen policies, five continuation verifiers, and a model-free selection rule, we find that the benefit of branching depends on dispersion: the difference between the best candidate return and the mean candidate return. Branching provides no benefit in low-dispersion settings, while increasing return by 12.8% in our main Craftax-Medium setting. Most of this gain comes not from selecting better actions, but from selecting among different stochastic realizations of the same action. Several competent verifiers achieve similar episode returns, suggesting that verifier quality is not the main constraint at our operating budget. Instead, computation is better allocated to states where useful dispersion is likely. On held-out seeds, gating branching using predicted dispersion retains 69% of the improvement from uniform branching while using 48% as many branching calls. These results characterize when branch-and-commit is useful and clarify what its gains represent.
Figures & tables
| Measure | Independent | Shared RNG |
|---|---|---|
| Same initial action | 84.9% | — |
| Between-action variance | 3.1% | — |
| Mean dispersion | 0.455 | 0.142 |
| Zero-dispersion decisions | 58.5% | 84.8% |
| Selection method | Episode return |
|---|---|
| No branching | |
| Uniform selection | |
| Realized-return rule | |
| GPT-4o | |
| Value head |
| Method | Return | Calls/ep. | Lift retained |
|---|---|---|---|
| Uniform | (100%) | 100% | |
| Dispersion-gated | (48%) | 69% |
Appendix figures & tables30 assets
Supplementary material from the paper’s appendix.
Appendix
| Pool | Runs | Ep./run | Mean | Read by |
|---|---|---|---|---|
| No branching, matched checkpoints | or | Every Craftax-Medium percentage (Section 3 ) | ||
| Fifty-episode verifier pool | VF, GPT-4o | , | Verifier comparison and the bound (Section 6.1 ) | |
| Periodic- , historical aggregate | mixed | mixed | Uniform reference row of Table 23 | |
| Periodic- , clean rerun | Reconciles the row above; fires at – calls per episode | |||
| Proposer sweep | Stochastic reference of Table 22 | |||
| Held-out gating, seeds – | , | The -of-lift-at- -of-calls result (Section 6.3 ) |
| Environment | Policy | decisions | Observed lift | ||
|---|---|---|---|---|---|
| XLand-MiniGrid R9-19x19 | PPO-MLP | ||||
| XLand-MiniGrid DoorKey-8x8 | PPO-MLP | ||||
| Craftax-Easy | GTrXL | ||||
| Craftax-Hard | GTrXL | ||||
| Asterix-MinAtar | PPO-MLP | ||||
| Craftax-Medium ( ID) | GTrXL |
| Verifier | Episode Return | Lift over no-branching |
|---|---|---|
| No branching | — | |
| Value head | ||
| Qwen-14B-AWQ |
| Verifier | ( CI) | |
|---|---|---|
| Value head | ||
| GPT-4o-mini | ||
| GPT-4o | ||
| Qwen-2.5-14B | ||
| Qwen-2.5-72B |
| Verifier | Verifier | Verdict | |
| Value head | GPT-4o | differ | |
| Value head | GPT-4o-mini | tie | |
| Value head | Qwen-2.5-14B | differ | |
| Value head | Qwen-2.5-72B | differ | |
| GPT-4o-mini | GPT-4o | tie | |
| GPT-4o-mini | Qwen-2.5-14B | tie |
| Grouping factor | Groups | ICC (outcome) | ICC (residual) | |
|---|---|---|---|---|
| Verifier | ||||
| Policy | ||||
| Seed | ||||
| Run | ||||
| Mixed-effects slope, verifier as random intercept: , CI | ||||
| Refit | Cells | Slope | ||
| Subset | cells | Joint Pearson | ||
|---|---|---|---|---|
| All cells (headline) | ||||
| Verifier | Full | Positive | Full | Positive | Full | Positive | |
|---|---|---|---|---|---|---|---|
| Value head | |||||||
| GPT-4o | |||||||
| GPT-4o-mini | |||||||
| Qwen-2.5-14B-AWQ | |||||||
| Qwen-2.5-72B-AWQ | |||||||
| sel. gain | per-dec | |||||
| Environment | Policy | Decisions | All-same | Between-action share | |
|---|---|---|---|---|---|
| Craftax-Medium | (GTrXL) | – | – | – | |
| Craftax-Medium | (PPO-MLP) | ||||
| Asterix-MinAtar | (PPO-MLP) | ||||
| DoorKey-8x8 | (PPO-MLP) |
| Oracle | Sparse | all | informative | |
|---|---|---|---|---|
| Craftax-Symbolic-Medium: | ||||
| Value head | 66 | |||
| Qwen-72B-AWQ | 58 | |||
| Craftax-Easy: | ||||
| Qwen-14B-AWQ (seed 42) | 503 | |||
| Qwen-14B-AWQ (seed 43) | 976 | |||
| Independent dice | Shared dice (CRN) | |||
| Seed | Decisions | Mean | Decisions | Mean |
| Pooled | ||||
| Pooled contrast: difference , SE , CI , | ||||
| Environment | Policy | Degenerate | Between-action | Ratio | CI | Ratio (live) | |
|---|---|---|---|---|---|---|---|
| Craftax-Medium | |||||||
| Craftax-Medium | |||||||
| Craftax-Medium | |||||||
| Craftax-Medium | |||||||
| Asterix-MinAtar | |||||||
| DoorKey-8x8 † |
| Arm | Runs | Episodes | Mean | SD | |||
|---|---|---|---|---|---|---|---|
| No branching | |||||||
| Periodic-50 (VF) |
| Verifier | Episode return |
|---|---|
| Value head | |
| GPT-4o-mini | |
| GPT-4o | |
| Qwen-2.5-14B-AWQ | |
| Qwen-2.5-72B-AWQ | |
| No branching (paired eval) |
| Achievement | Base | VF | LLM | VF Base | LLM Base | LLM VF |
| Where LLM wins (long-horizon / rare): | ||||||
| collect_diamond | ||||||
| make_iron_sword | ||||||
| make_iron_pickaxe | ||||||
| make_stone_sword | ||||||
| collect_iron | ||||||
| LLM verifier | runs | |||
|---|---|---|---|---|
| GPT-4o | ||||
| Qwen-2.5-14B-AWQ | ||||
| Qwen-2.5-72B-AWQ |
| LLM verifier | low | mid | high | all |
|---|---|---|---|---|
| Raw : | ||||
| GPT-4o | ||||
| GPT-4o-mini | ||||
| Qwen-2.5-14B-AWQ | ||||
| Qwen-2.5-72B-AWQ | ||||
| Pooled | ||||
| Proposal mechanism | Episode return | Lift | Rank fidelity | Return stoch | |
|---|---|---|---|---|---|
| No branching | — | — | — | — | |
| Stochastic ( ) | (ref) | — | |||
| B1 Top- distinct | ( ) | ||||
| B1 Tempered ( ) | ( ) | ||||
| B1 Counterfactual † | ( ) | ||||
| B2 LLM-prefix | ( ) |
| Policy | Method | Calls/ep | Episode return | Lift | Lift/call |
|---|---|---|---|---|---|
| GTrXL ( ) | No branching | — | — | ||
| Periodic-50 (uniform) | |||||
| Disp-target | |||||
| Disp-target | |||||
| PPO-MLP | No branching | — | — | ||
| Periodic-50 (uniform) |
| Method | Calls/ep | Episode return | Lift | Per-call efficiency |
|---|---|---|---|---|
| No branching | — | — | ||
| Disp-target | /call | |||
| Disp-target (headline) | /call | |||
| Disp-target | /call | |||
| Periodic-50 (uniform) | /call | |||
| Disp-target | /call |
| Trigger Strategy | Episode Return | Calls/Ep. | Lift vs. baseline |
|---|---|---|---|
| No branching | — | ||
| Periodic (period , historical) | |||
| Periodic (period ) | |||
| Anti-targeting baseline: | |||
| Value only ( ) | |||
| Budget | Random | Entropy | Predicted | Oracle | ||
|---|---|---|---|---|---|---|
| Craftax-Symbolic-Medium ( , GTrXL): , , | ||||||
| 10% | 977 | |||||
| 33% | 977 | |||||
| 50% | 977 | |||||
| Asterix-MinAtar ( ): , , | ||||||
| 10% | 454 | |||||
| Actual gate | Permuted (within-ep) | Random | Concentration (actual/random) | |
| as gating signal: | ||||
| Environment | Recipe CV | -proxy | |
|---|---|---|---|
| Craftax-Medium (MLP) | |||
| Craftax-Hard | |||
| Asterix-MinAtar |
| Method | Calls/ep | Episode return | Lift | Lift/call |
|---|---|---|---|---|
| No branching (paired eval) | — | — | ||
| Periodic-15 (uniform) | ||||
| -gated | ||||
| -gated | ||||
| -gated | ||||
| Predictor-gated |
Reinforcement Learning
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
See all 1,852 papers