Cross-Rollout Bellman Closure for Long-Horizon Agentic Reinforcement Learning

• CRBC combines global evidence propagation with behaviour-consistent aggregation, addressing the local reach of visit averaging and frequency-blind extremum aggregation of shortest-path estimates.The method merges rollout groups into an empirical process and evaluates its behaviour-policy Bellman fixed point with one linear solve.Source: §1 · pp. 2–3
• CRBC backs state values through observed transitions to obtain action values, then combines normalized closure credit with trajectory-level group advantage without additional environment rollouts.Source: §1 · p. 3
• Shared anchors let step-level credit use downstream evidence from rollouts that never visited an anchor, weighted by observed action and transition frequencies.Source: §1 · p. 3
• 5.59 percentage points: CRBC improves over the strongest baseline on ALFWorld with Qwen2.5-1.5B-Instruct.Experiments across ALFWorld, WebShop, and Sokoban show gains over evaluated baselines; feasible policy reweighting along the closure-credit direction does not decrease discounted success value on the fixed empirical process.Source: §1 · p. 3

• Group-based methods such as RLOO and GRPO replace PPO’s learned critic with comparisons among same-prompt responses.The cited work also covers post-training with human feedback, preference optimization, and verifiable rewards.Source: §2 · p. 3
• Step-level credit methods include process reward models, LLM judges, learned action-boundary critics, and rollout-group statistics such as GiGPO, HGPO, and RTMC.Source: §2 · pp. 3–4
• GraphGPO uses shortest-path distance, G2PO uses one-step TD errors, while CRBC solves the empirical process’s exact behaviour-policy Bellman fixed point using observed frequencies.Other cited approaches calibrate limited rollout evidence, add progress signals for all-failing groups, use state potentials, or extract attribution from model reasoning.Source: §2 · p. 4

• Each task group contains G rollouts from the same initial condition, with language contexts mapped to anchors matched only within that group.Rollouts receive binary terminal success indicators and no intermediate reward; time-limit truncations are represented as failures.Source: §3 · p. 4
• Broadcasting one trajectory-level advantage to every step cannot distinguish actions within that trajectory.Source: §3 · p. 4
• Group-relative methods compare outcomes within a group rather than using a learned value function; GRPO and RLOO are examples, and the proposed method is optimizer-agnostic.Source: §3 · p. 4
• Step-level methods use shared anchors to assign signals that vary within a trajectory, while visit-local suffix-return averaging does not propagate evidence from other rollouts at shared successors back to the anchor.The realized discounted return is defined as β^(T_i−t+1)R_i, with β between zero and one.Source: §3 · p. 4

4.1 THE EMPIRICAL PROCESS

• The group-induced empirical process preserves observed action and transition frequencies, assigns zero probability to unobserved transitions, and is the object of analysis rather than unknown environment dynamics.Source: §4.1 · p. 5

4.2 THE BELLMAN CLOSURE

• Repeated Bellman backups recombine evidence across observed edges, and the unique behavior-policy fixed point is obtained by solving a linear system.On the empirical process, the resulting state value is the discounted success probability under the group behavior policy.Source: §4.2 · pp. 5–6

4.3 FINITE DEPTH AND THE REFERENCE DIRECTION

• Finite-depth backups start from visit-local suffix averages, converge to closure values, and inherit the non-decrease guarantee when sufficiently accurate.At zero depth, the family uses visit-local suffix averaging; increasing depth extends recombination while retaining empirical aggregation.Source: §4.3 · pp. 6–7

4.4 STEP CREDIT AND POLICY OPTIMIZATION

• CRBC gates and normalizes closure credit, combines it with trajectory-level group advantage, and adds neither a parametric critic nor environment rollouts.Occurrences of the same anchor and semantic-action pair share credit; the trajectory advantage covers steps without an identifiable anchor comparison.Source: §4.4 · p. 7

5.1 EXPERIMENT SETUP

• The setup spans text-based household and shopping tasks plus visual 6 × 6 Sokoban, using shared data, rollout, and optimization protocols across reproduced RL methods.Each update uses eight rollouts per group; episodes are capped at 50, 15, and 15 environment steps for ALFWorld, WebShop, and Sokoban, respectively.Source: §5.1 · pp. 7–8, §5 · p. 7

5.2 EXPERIMENTAL RESULTS

• CRBC outperforms every baseline across both model sizes and all three environments, including 96.09% ALFWorld success and 82.81% Sokoban success.On ALFWorld with Qwen2.5-1.5B-Instruct, it exceeds HGPO by 5.59 points; on Sokoban, it exceeds GraphGPO by 5.21 points.Source: §5.2 · p. 8, Table 1 · p. 8, Table 3 · p. 9
• CRBC rises fastest early and mid-training and reaches the highest final reward; on ALFWorld, it matches GraphGPO’s final reward in roughly half the updates.Validation trends also show stronger held-out success, supporting the reported learning-efficiency benefit.Source: §5.2 · p. 9, Figure 3 · p. 10

5.3 ABLATION STUDY

• Full closure reaches 96.09% final success, versus 92.97% at K = 0, 1 and 93.75% at K = 2, 3, a 3.12-point gain over visit-local estimation.Validation score rises from 7.00 at K = 0 to 8.01 under full closure.Source: §5.3 · p. 9, Table 2 · p. 9
• With trajectory-level weight wG = 1, success rises from 93.75% at wS = 1 to 96.09% at wS = 5, then falls to 94.79% at wS = 10.Trajectory-only credit reaches 76.56%, step-only closure credit reaches 95.31%, and the default (1, 5) exceeds step-only credit by 0.78 points.Source: §5.3 · p. 9, Table 4 · p. 9

6 CONCLUSION

• CRBC combines normalized closure credit with trajectory-level advantages and improves performance and learning efficiency on ALFWorld, WebShop, and Sokoban without additional rollouts.Feasible policy reweighting along the closure-credit direction does not decrease discounted success value on the fixed empirical process.Source: §6 · p. 10

A ALGORITHM

• Each training iteration builds a rollout-group empirical process, solves its behavior-policy Bellman fixed point, and combines normalized step credit with group-relative trajectory advantages.The resulting advantages are held fixed while the policy is updated.Source: A ALGORITHM · p. 15

B.1 PROOF OF PROPOSITION 1

• The Bellman iteration converges to a unique fixed point, with error bounded by β^K times the initial error after K iterations.The proof uses contraction and the bound ∥βMg∥∞ ≤ β < 1.Source: §B.1 · p. 16

B.2 PROOF OF PROPOSITION 2

• For a feasible reweighting, the value difference is nonnegative, and it is strict where a positive-weight, nonzero-variance anchor is reachable under the perturbed policy.Feasibility requires nonnegative reweighted action probabilities; the proof bounds the step size using the original action frequencies and negative credit entries.Source: §B.2 · p. 16

B.3 RESIDUAL DECOMPOSITION AND FINITE-DEPTH TRANSPORT

• The residual vanishes when each observed nonterminal successor has no initial occurrences and receives transitions only from the given state-action pair, or when weighted discrepancies cancel.Acyclicity alone is insufficient because distinct state-action pairs can share a successor.Source: §B.3 · p. 17
• Finite-depth state values remain constant across depths only under the stated zero-residual condition; otherwise the residual may remain nonzero.The recurrence expresses the depth-K gap using repeated Bellman propagation of the initial residual.Source: §B.3 · p. 17

B.4 PROOF OF COROLLARY 3

• The depth-bound argument is restricted to K ≥ 1 because it includes an additional action-level residual.Source: §B.4 · p. 17
• When E_K ≤ σ_g(s) at every anchor with positive w(s) and σ_g(s), feasible reweighting does not decrease discounted success value.If there are no such anchors, the sufficient condition holds vacuously.Source: §B.4 · p. 17
• Because E_K → 0 and the relevant anchor set is finite, the sufficient condition holds for all sufficiently large finite K.Failure to satisfy the condition does not establish misalignment.Source: §B.4 · p. 17
• Decay of E_K improves the certified lower bound but does not imply monotone alignment, preserved action rankings, or a particular training-curve shape.Source: §B.4 · p. 17

C.1 COMPARING METHODS

• GPT-4o and Gemini-2.5-Pro serve as closed-source, general-purpose LLM reference points.Source: §C.1 · p. 18
• ReAct interleaves reasoning and acting, while Reflexion uses verbal reflection and iterative self-improvement without parameter updates.Source: §C.1 · p. 18
• RLOO is a critic-free trajectory-level leave-one-out baseline; PPO uses a learned value critic and generalized advantage estimation.Source: §C.1 · p. 18
• GiGPO compares occurrences at repeated anchor states, while GRPO normalizes one task-outcome advantage over that task’s rollouts.Source: §C.1 · p. 18
• GraphGPO uses a shortest-path/extremal graph readout, while HGPO refines step comparisons using historical-context consistency.Source: §C.1 · p. 18
• CRBC is evaluated in its predictor-free, full-closure setting.Source: §C.1 · p. 18

C.2 ENVIRONMENT DETAILS

• ALFWorld requires household-task completion through admissible commands, uses six task families, and truncates trajectories after at most 50 steps.Validation uses 128 in-distribution trajectories.Source: §C.2 · p. 18
• WebShop tests searching, navigating, and selecting a matching item; trajectories are limited to 15 steps and evaluation reports raw task score and binary success rate.Source: §C.2 · pp. 18–19
• Figure 5 describes reachable-rollout counts by closure depth and paired coverage at K = 0 versus full closure, colored by the share of eligible visits.Source: Figure 5 · p. 19
• Sokoban tests transfer to a visual setting with 6 × 6 one-box boards, four pushing actions, and a 15-step trajectory limit.Reported measures are raw task score and solved-board success rate.Source: §C.2 · p. 19
• Anchors are matched by exact equality of environment-specific observations; recent interaction records in policy prompts are excluded from the matching key.Source: §C.2 · p. 19

C.3 DETAILS OF TRAINING

• Each text update samples 16 task groups with eight rollouts each; Sokoban samples 32 groups, and all settings train for 150 updates with 128 validation trajectories.Successful ALFWorld and WebShop trajectories receive reward 10 and failures 0; invalid actions incur a 0.1 penalty before advantage computation.Source: §C.3 · p. 19
• Batching is adjusted to hardware needs but held identical across methods within each comparison; reproduced experiments use one node with eight 80 GB NVIDIA A100 GPUs.Source: §C.3 · p. 19
• Table 7 reports six subtask and overall success rates, plus task score, for rollout-group sizes on ALFWorld at step 150.Source: Table 7 · p. 20
• Unless stated otherwise, CRBC uses full closure with K = ∞, β = 0.98, w_G = 1, w_S = 5, and normalization floor σ_min = 0.1.Its normalized per-anchor Q − V signal is combined with the trajectory-level advantage.Source: §C.3 · p. 20

D.1 BELLMAN DISCOUNT

• β = 0.98 achieves 96.09% overall success on ALFWorld with Qwen2.5-1.5B-Instruct, while β = 1.00 yields 93.36%, 2.73 percentage points lower.Across β = 0.95, 0.98, and 0.99, overall success ranges from 95.31% to 96.09%.Source: §D.1 · p. 20, Table 6 · p. 20
• The preferred discount varies by subtask: β = 0.95 is best on Clean and Cool, β = 0.99 on Look, and β = 0.98 on Heat.The tested discounted settings show limited overall sensitivity, supporting β = 0.98 as a practical default.Source: §D.1 · p. 20

D.2 CLOSURE DEPTH AND EVIDENCE COVERAGE

• Under full closure, 61.5% of eligible visits access all eight rollouts, up from 12.9% at K = 0; coverage increases for 63.0% of eligible visits overall.Coverage counts structurally accessible distinct rollouts within each eight-rollout group, without weighting their contributions.Source: §D.2 · p. 21

D.3 VALIDATION SUCCESS

• CRBC generally reaches high validation success earlier and achieves stronger final performance than the compared baselines across ALFWorld, WebShop, and Sokoban.Validation measurements are recorded every five training updates; Figure 6 uses Qwen2.5-1.5B-Instruct for ALFWorld and WebShop and Qwen2.5-VL-3B-Instruct for Sokoban.Source: §D.3 · p. 21, Figure 6 · p. 21

D.4 ROLLOUT GROUP SIZE

• At rollout-group sizes G = 4 and G = 16, CRBC improves over the strongest ALFWorld baseline by 13.28 and 3.91 percentage points, respectively.CRBC achieves 92.97% success at G = 4 and 96.88% at G = 16.Source: §D.4 · pp. 21–22

E PROMPT TEMPLATES

• Text-environment prompts retain at most two recent observation–action records, while Sokoban uses the current RGB image without textual interaction history.Across environments, prompts share a reasoning/action format, and reproduced RL methods use the same prompt templates and memory protocol within each environment.Source: E PROMPT TEMPLATES · p. 22, Figure 8 · p. 23