TSBPO: Tree-Structured Branching for Policy Optimization in Interactive Language Agents

TSBPO: Tree-Structured Branching for Policy Optimization in Interactive Language Agents Rui Yu, Chong Mu, Jinchuan Zhang* University of Electronic Science and Technology of China Rui Yu: 202522081031@std.uestc.edu.cn | Jinchuan Zhang: jc.zhang@uestc.edu.cn *Corresponding author: Jinchuan Zhang

replaying a physical occurrence differs from merely matching its current text [25, 26]. TSBPO connects these decisions in one training process. Supervised protocol alignment initializes executable behavior; a Root/Branch curriculum acquires outcome alternatives; realized physical siblings and exact observation groups supply separate credit terms; complete-turn aggregation transfers that credit to token updates. Both evaluated runs use the likelihood-fitted Root/Branch allocator and local state-group contrast objective, with benchmark-specific rollout budgets. Their task results measure the integrated training process rather than the isolated effect of a single component. We evaluate fixed Qwen2.5-1.5B checkpoints on complete ALFWorld validation sets and all 500 WebShop test goals. Training diagnostics characterize acquired comparisons and prediction reliability; configuration comparisons describe specific optimization choices. The derivations, full protocols, and additional studies appear after the references.

Abstract Training interactive language agents from terminal outcomes poses three coupled problems: which task and state continuations to sample, how to assign delayed feedback to decisions, and how to aggregate token losses for multi-token actions. We present TSBPO, a tree-structured sampling-toupdate paradigm that addresses these problems within one training loop. A likelihood-fitted Root/Branch allocator uses retained task and state evidence to target continuations likely to produce contrasting terminal outcomes under fixed rollout budgets. On the resulting replayed physical trees, trajectory advantages compare immediate sibling segments, while observation-group step advantages compare outcomes at matched task/observation states. The actor then sums clipped token surrogates over each complete response and normalizes across active turns, avoiding responselength averaging in the policy-gradient term. With a Qwen2.5-1.5B actor, fixed checkpoints obtain 97.79% seen and 96.64% unseen stochastic success on ALFWorld and an 81.07% per-episode success rate over six stochastic episodes for each of the 500 WebShop test goals. A WebShop step-term ablation yields 75.93% at the same update-100 evaluation; an ALFWorld aggregation comparison shows higher observed command validity with complete-turn weighting. These results support the evaluated training configuration on two interactive benchmarks.

2. Related Work 2.1 Interactive policies and terminal feedback Interactive language agents choose natural-language responses that also act on an environment. ReAct interleaves reasoning and actions with observations [13], while Reflexion uses textual feedback to revise subsequent behavior [14]. Both illustrate the importance of a closedloop interaction history. Policy training adds a different problem: a completed trajectory provides an outcome, but that outcome does not identify which earlier commands or sampled continuations were most useful. ArCHer studies hierarchical multi-turn reinforcement learning [20], longhorizon interactive RL addresses sustained environment interaction [21], and RAGEN examines multi-turn training dynamics [11]. In ALFWorld and WebShop, task completion is measured after a sequence of agent actions [1, 12]; the terminal result therefore summarizes a variablelength interaction rather than an individual response. Partial observability makes the agent's history, rather than the latest observation alone, relevant to action selection [25]. Temporal abstraction separates decisions made at the environment timescale from the lower-level operations used to realize them [26]. For a language-model actor, one environment action may contain many autoregressive tokens,

Keywords: interactive language agents; terminal feedback; training paradigm; dynamic curriculum; physical rollout trees; credit assignment.

1. Introduction Interactive language agents act through generated commands and receive terminal task feedback after partially observed, variable-length interactions. ALFWorld and WebShop make completion verifiable [1, 12], but a terminal label alone does not identify where additional rollouts should be spent, which turns deserve credit, or how a multitoken response should enter an actor update. The prompt is a bounded account of observations and earlier commands, so

1

dynamics model [9]. Sparse revisits motivate retaining direct task evidence and borrowing capped evidence from similar instructions. Branch acquisition uses likelihoodfitted state evidence at the original remaining deadline to allocate continuations toward terminal-label contrasts in factual-homogeneous observation groups. Hindsight Credit Assignment relates outcome-conditioned occurrence probabilities and forward outcome probabilities through Bayes’ rule [23]. This connection informs the use of completed outcomes for continuation prediction. In TSBPO, predictive evidence determines sampling before the actor’s advantages exist; fresh observed outcomes determine credit afterward. This separation keeps the acquisition model from becoming an additional reward or advantage multiplier.

whereas the environment transition occurs after the response is submitted. This separation creates three distinct training decisions: sampling determines which future outcomes are observed, credit assignment compares realized actions and continuations, and policy-gradient aggregation determines how those comparisons weight token updates. TSBPO retains a physical replay structure for the first two decisions and treats the complete response as the unit of actor optimization.

2.2 Curriculum and rollout allocation Curriculum learning adapts the experience distribution to the learner [29, 30]. DPS predicts fully unsolved, mixed, and fully solved prompt groups through a three-state task-

Figure 1. TSBPO training paradigm. Successful teacher interactions initialize executable behavior; online RL connects Root/Branch allocation, physical-tree credit, and complete-turn actor updates. Rollout icons are schematic.

multiple environment trajectories at different stages and optimize different interaction interfaces. TreePO aggregates relative rewards across nested ancestor subgroups [5], whereas our segment credit ends at the next physical split and restarts there. AT²PO couples entropy-guided expansion of turn-level rollout trees with descendant-based value propagation and turn-level importance weighting [6]. AT²PO and TSBPO both acquire tree-structured continuations, but our branch selection estimates deadline-conditioned terminal-label contrast; trajectory credit compares immediate physical siblings alongside a separate observation-group step term. BiPACE refines groups through behavioral state neighborhoods and action-conditioned peers [8]. RUDDER learns return redistribution for delayed feedback [22]; here, terminal leaves supply segment outcomes directly. REINFORCE and baseline analyses establish how sampled outcomes enter score gradients [27, 28]. Leaveone-out estimators distinguish an independent baseline from a sample mean containing the scored action [18, 19]. PPO and value-based estimators offer established update and credit mechanisms [2, 16, 17]. Dr. GRPO identifies

2.3 Local credit and relative optimization GiGPO combines episode-relative and observation-group step advantages [4, Section 4]. HGPO refines equal-currentobservation groups by shared historical context and combines their advantages with depth-dependent weights; K denotes the maximum historical context depth [33]. SALT refines outcome-derived advantages on a trajectory graph [31], while GraphGPO credits transitions using estimated progress toward a goal [32]. These methods construct comparisons from existing rollouts. TSBPO additionally acquires alternatives by replaying physical occurrences; its trajectory comparison uses immediate siblings sharing the realized history, alongside the retained observation-group step term. DPEPO [34] trains an agent to issue actions across multiple environments during inference, using a trajectorylevel success reward together with action- and statetransition-diversity rewards. TSBPO trains a sequential interaction policy: replayable physical occurrences organize training continuations, and observed terminal outcomes determine local sibling credit. The methods therefore use

2

deeper split starts another comparison rather than accumulating ancestor advantages. Figure 2 also distinguishes optional actor-side coefficient weighting from the raw trajectory and observation-group credit terms.

response-length and reward-normalization factors as changes in optimization weighting [7], and DAPO revises token aggregation [10]. We adopt a shared active-turn denominator while summing token surrogates within each response. The resulting local score identity explains the interface between tree credit and the language policy; Appendix B treats its conditions and adaptive-sampling limits.

3. Interaction Setting and Training Paradigm 3.1 Complete turns and observed state groups Let μ be the evaluation distribution over tasks. For task x, the actor receives context Hi , generates response yi containing reasoning and an environment command, observes the resulting transition, and continues until termination or the action limit. A trajectory τ includes generated responses and environment transitions; the verifier supplies R(τ)∈{0,10}. The task objective is Jμ (θ)=Ex∼μ Eτ∼Pπ (·|x) [R(τ)]. (1)

Figure 2. Physical rollout tree and local trajectory credit. Terminal leaves back up as descendant-leaf means; immediate sibling scores are centered at each split. At h, the child scores 4 against four zeroscore siblings, yielding +3.2 and -0.8. Optional weighting changes actor coefficients only.

θ

The curriculum changes the training task distribution and selects physical turns for an empirical actor surrogate. Terminal outcomes define task success; local invalid-action costs and fixed-reference regularization serve separate training roles. Adaptive sampling makes this surrogate distinct from the evaluation objective. At the language-policy level, each response factorizes autoregressively:

Each round freezes a behavior policy πold for factual trajectories and new suffixes. Replay reconstructs a visited physical occurrence; shared prefixes are stored once, and replay itself creates no new training row. Every newly generated physical turn supplies one active actor row. After sampling finishes, observed returns determine detached advantages, which enter the complete-turn actor update. Prediction chooses what to sample and never scales the resulting credit.

L

i logπθ (yi |Hi )=∑j=1 logπθ (yi,j |Hi ,yi,<j ). (2)

The prompt Hi contains the current observation and bounded interaction history; generated EOS tokens are included, while generation-limit termination adds no EOS. Exact task/observation keys define statistical state groups. Replay additionally retains a physical occurrence’s environment snapshot and realized history.

4. Dynamic Curriculum for Acquiring Outcome Comparisons Root assigns factual episodes to tasks; Branch assigns new suffixes at replayed physical occurrences before advantages are computed. Both seek terminal-label contrasts under fixed rollout budgets. A mean success rate near one half can conceal nearly deterministic tasks, so separate likelihood-fitted Root and Branch models integrate uncertainty in task or state success probabilities. They weigh aged direct evidence and bounded semantic evidence; Branch also conditions on current factual labels and the original remaining deadline. Both evaluated runs use this path. Likelihood fitting alone does not guarantee calibration.

3.2 Supervised protocol alignment Successful trajectories collected with GPT-5.6-sol provide environment-specific user–assistant pairs. Starting directly from Qwen2.5-1.5B-Instruct, two epochs of causal cross-entropy on assistant tokens align the initial policy with the interaction protocol: LSFT (θ)=−E(H,y)∼DT [∑j logπθ (yj |H,y<j )]. (3) The supervised model initializes both the trainable actor and its fixed RL reference. The teacher supplies no online RL feedback; the environment supplies terminal labels. Figure 1 summarizes the two-stage process, and Appendix A describes collection, prompts, and supervised settings.

4.1 Root selection and fitted factual quotas For task i, let hi s,hi f be age-decayed direct success/failure counts (factor 0.95 per round), and mi s,mi f be capped counts retrieved from similar task instructions. Each parameter component θ=( aθ , bθ , ηθ , ρθ ) defines pi |θ,D∼ Beta(A(i,θ),B(i,θ)), where A(i,θ)=aθ +ηθ hi s+ρθ mi s and B(i,θ)=bθ +ηθ hi f+ρθ mi f. The weights ηθ and ρθ lie in [0,1], so historical and semantic evidence can be discounted separately. Root decisions have no current factual counts.

3.3 Frozen behavior policy and the physical rollout tree A replayed factual prefix is stored once. Each physical split retains one factual continuation and adds new sibling suffixes. A child segment runs until the next split or a terminal leaf, so its turns receive one local comparison. A

3

The Root mixture weights wi (θ) fit complete physical Root-group counts by beta-binomial predictive likelihood. Each past group receives age weight 0.95age divided by its task's group count that round; fitting excludes the queried task. Unidentified semantic or historical reliability uses ρθ =0 or ηθ =1, respectively; scant population evidence uses Beta(1/2,1/2). Retrieved counts inform the query without entering direct outcome memory. A candidate pool combines fresh task instances with a bounded set of previously evidenced instances, allowing useful tasks to reappear despite sparse natural revisits; historical candidates occupy at most half the pool. Let gi =Uroot (i,nref ), where nref is the factual group size. Tasks are drawn without replacement using weights proportional to

4.2 Deadline-conditioned Branch prediction Completed factual trajectories form exact task/observation groups. A group is eligible when its factual labels are homogeneous, a physical occurrence is replayable, and its predicted opposite-outcome probability is positive; the task may already be mixed overall. The earliest eligible occurrence is its representative. At depth d, suffixes retain the original deadline H=L−d. For a state/depth pool a, let ha s,ha f denote historical direct counts after age decay (factor 0.90 per round), ca s, ca f the completed current bare counts, and ma s, ma f capped semantic-neighbor counts gated by task goal, state similarity, and deadline. Each physical trajectory contributes at most once to a pool. For concise notation, the component-level success/failure mass summaries are A(a,θ)=aθ +ηθ hsa +csa +ρθ msa , (6) B(a,θ)=bθ +ηθ hfa +cfa +ρθ mfa . Branch fits a separate mixture to complete historical Branch groups by an age- and task-balanced beta-binomial likelihood, holding out the queried task. When Branch history is sparse, factual Root groups from other tasks initialize only the base success-rate distribution; Root reliability coefficients are not transferred. Current bare counts enter (6) once; learned ηθ and ρθ scale historical and borrowed evidence only. Joint acquisition uses correlated samples rather than independent Beta marginals.

P(i)=ε/M+(1−ε)exp(gi /Tc )/∑u exp(gu /Tc ). (4) We use ε=0.30 and Tc =0.25. For n≥1 outcomes that are conditionally independent given a task success probability, the event probability within a Beta component is u(n;A,B)=1−B(A+n,B)/B(A,B)−B(A,B+n)/B(A,B). Averaging this event probability over the fitted taskspecific components gives the Root acquisition curve: Uroot (i,n)=∑θ wi (θ)u(n;A(i,θ),B(i,θ)). (5) Here B is the beta function and Uroot (i,0)=0. Integrating each component before averaging avoids treating an uncertain mean success rate as a known task probability. Each selected task receives at least two factual rollouts; the remaining Root budget follows marginal gains in (5). The same fitted mixture determines the curriculum score and the quota curve. Appendix B.1 derives the component event probability, and Appendix C.4 specifies semantic retrieval.

4.3 State-group contrast utility and branch quotas Let �ℎ�� contain the factual-homogeneous candidate state groups. For group a, �� is the modeled probability that one new suffix ends with the label opposite to its observed factual label: �� =�� after factual failure and �� =1−�� after factual success. Let �� be the number of new suffixes assigned to a. The expected probability of creating a mixed terminal-label group is �� (�� ) = �[1 − (1 − �� )�� | �]. (7) Given evidence D, �� (�� ) averages the event probability over 512 aligned posterior particles. Each eligible observation group counts once, including distinct groups within one task. Suffix labels are conditionally independent within a particle, while shared task and trajectory-cluster draws retain modeled dependence. Groups already mixed at their own observation are ineligible. For a block of m additional suffixes at group a after its current quota �� , the local gain is ��,� (�� ) = �[(1 − �� )�� 1 − (1 − �� )� | �]. (8) Additional suffixes reduce only that group's residual nocontrast mass. Across eligible groups, the budget problem is maximize ∑�∈�ℎ�� �� (�� ) subject to ∑� �� ≤ ������ℎ , (9) �� ∈ 0 ∪ 4, …, �� . An opened group receives at least four new suffixes; its factual child costs no new rollout. �� respects worker capacity and budget. An exact global integer dynamic program selects feasible quotas using the particle estimate

Figure 3. Likelihood-fitted Root/Branch allocator used in ALFWorld and WebShop. Root assigns factual quotas from decayed direct and capped semantic evidence. Branch scores eligible exact observation groups under original deadlines and solves a global suffix budget with at least four new continuations per opened group.

4

within each turn and use one active-turn count N for the optimizer minibatch:

of (7). Appendix B.2 derives the event probability and diminishing gains. Actor credit uses realized outcomes after sampling.

L

i JPG (θ)=(1/N)∑Ni=1 ∑j=1 Sc (ρi,j ,Ai ),

5. From Physical Comparisons to Actor Updates

ρi,j =

πθ(yi,j |Hi ,yi,<j ) πold(yi,j |Hi ,yi,<j )

.

(15)

Sc is the tokenwise clipped PPO surrogate with a negative-advantage dual cap. At the behavior policy, for a fixed batch and detached advantages, its PG gradient equals N−1 ∑i Ai ∇θ log πθ (yi |Hi ). This local identity explains the turn-to-token interface; its proof, length-weighting analysis, and limits away from the behavior policy are in Appendix B.3. PG, reference, and entropy terms share the minibatch's global active-turn count across ranks and partial minibatches; padding is excluded. The actor adds fixed-reference regularization with a tangent linear tail and a local invalid-syntax cost. Costs enter returns before centering (Appendix D; Appendix B.5). Unit segment coefficients define the core model. The optional bounded plugin redistributes trajectory coefficient mass across unequal-length sibling segments without changing raw returns, sibling baselines, or step credit (Appendix D). Section 7.2 evaluates this choice. Algorithm 1 (Appendix D) details a training round. The frozen policy collects Root factual episodes, then Branch suffixes from replayable factual-homogeneous exact task/observation groups under their original deadlines. Completed groups update predictor memory. Immediate physical siblings determine trajectory credit and exact observation groups determine step credit; only turns without assignable splits use the factual-root fallback. The actor sums token surrogates per complete response under the global active-turn denominator. ALFWorld and WebShop share this sequence with benchmark-specific budgets, horizons, and initializations.

5.1 Physical segments and terminal backup Each physical edge is one sampled turn. A child segment E(h,c) starts at split h and ends at the next split or terminal leaf z. Immediate siblings are compared locally (Figure 2). For a terminal leaf, Vterm equals its verifier reward. For an internal endpoint, it is the mean reward of all descendant leaves L(z): Vterm (z)=∑ℓ∈L(z) R(ℓ)/|L(z)|. (10) This is an observed-tree credit statistic. Endpoint backup weights descendant leaves, while the sibling baseline below weights immediate alternatives equally. Each segment turn receives the endpoint outcome minus its own invalid-action cost Pi ; the segment score is S(h,c)=(1/|E(h,c)|)∑i∈E(h,c) [Vterm (z)−Pi ]. (11) For K immediate child segments, trajectory credit is centered across their scores: μh =(1/K)∑c∈C(h) S(h,c), (12) Atraj (h,c)=S(h,c)−μh . The baseline weights immediate children equally, regardless of segment length. Credit stops at the next split; ancestor advantages are not accumulated, and an assigned zero remains zero. Turns without an assignable split use the factual-root fallback in Appendix C.3.

5.2 Observation-group step credit The supporting step term follows GiGPO’s observation grouping [4]. Its backup averages immediate outgoing outcomes: Vγ (h)=(1/|C(h)|)∑c∈C(h) Tγ (c), if c is terminal (13) R(c) . Tγ (c)= γVγ (c) otherwise

6. Experimental Design The actor is Qwen2.5-1.5B-Instruct after environmentspecific supervised alignment. Complete ALFWorld evaluation covers 140 seen and 134 unseen tasks, ten stochastic episodes and one greedy episode per task. WebShop covers all 500 test goals in the 1,000-product catalog with six stochastic episodes per goal. The reported ALFWorld and WebShop checkpoints are fixed at updates 175 and 100, respectively, rather than selected as onlinemonitoring maxima. Each configuration has one training history; task-bootstrap intervals resample evaluation tasks, not training seeds. WebShop online monitoring uses the same goal pool as complete assessment. Appendix A gives decoding and training settings.

We use γ=0.95 for the step backup in both benchmarks. With Qi =Tγ (c)−Pi , exact task/observation groups G(s) center observed turn occurrences, including repeated actions: Astep,i =Qi −(1/|G(s)|)∑u∈G(s) Qu , (14) Ai =Atraj (h,c)+Astep,i . Both raw credit terms have coefficient one. Immediatechild backup and descendant-leaf averaging can differ in unbalanced trees; they define distinct step and segment comparisons.

7. Results

5.3 Complete-turn policy optimization

7.1 Complete-Task Performance

A response is a complete autoregressive language action. Its score is the sum of its token scores (2). Dividing by its own sampled length introduces the response-dependent factor identified by Dr. GRPO [7]; we retain token sums

At the fixed checkpoints, ALFWorld achieves 97.79% seen and 96.64% unseen stochastic success (2,664/2,740 episodes overall).

5

WebShop achieves 81.07% (2,432/3,000). Table 1 places these complete-task measurements beside published scores, whose initialization and evaluation protocols differ. The two rows report the same allocation method within benchmarkspecific training and evaluation configurations. Table 1. Task-family and overall success (%) for selected RL comparisons. PPO, GRPO, and GiGPO follow [4, Table 1], BiPACE-Q follows [8, Table 4], and HGPO follows [33, Table 1]. Published ALFWorld scores use valid-seen tasks; initializations and evaluation protocols differ. Our ALFWorld rows use ten stochastic episodes per task. The WebShop dagger marks 500 goals, six episodes each, in the 1,000-product catalog. Type

Method

RL RL RL RL RL RL RL RL RL

PPO [4] GRPO [4] GiGPO, std [4] GiGPO, no std [4] HGPO, K=2 [33] HGPO, K=4 [33] BiPACE-Q [8] TSBPO (seen) TSBPO (unseen)

ALFWorld Pick

Look

Clean

Heat

Cool

Pick2

All

WebShop Succ.

64.8±3.5 85.3±1.5 94.4±5.9 96.0±1.4

40.5±6.9 53.7±8.0 67.5±4.6 76.5±3.9

57.1±4.9 84.5±6.8 94.8±3.8 91.8±5.5

60.6±6.6 78.2±7.9 94.4±7.8 91.3±6.3

46.4±4.0 59.7±5.0 79.8±4.7 71.7±8.4

47.4±1.9 53.5±5.6 76.4±5.4 79.5±7.7

100.0 97.43 87.92

97.4±3.8 98.46 100.00

100.0 98.52 99.68

100.0 96.25 97.39

96.5±3.6 100.00 97.62

92.0±7.9 95.83 97.65

54.4±3.1 72.8±3.6 86.7±1.7 86.1±4.7 92.8±1.1 94.85±0.92 93.5±1.2 97.79 96.64

51.5±2.9 56.8±3.8 65.0±3.2 67.4±4.5 71.5±4.0 78.12±2.06 71.9±2.1 81.07† —

Figures 4(a) and 4(b) show the full ALFWorld and WebShop training histories. Online monitoring and allocation diagnostics describe one history per benchmark;

Table 1 reports fixed-checkpoint complete-task evaluations. Both runs use the same fitted allocator with benchmarkspecific rollout budgets and horizons.

Figure 4(a). Complete ALFWorld training and online-monitoring history through 175 updates. Panels show bare/branch success and action validity, trajectory length, online success, task-group coverage, and new suffix outcomes. Online success samples 120 valid-seen episodes every five updates; complete-task success is reported in Table 1.

6

Figure 4(b). Complete WebShop training and online-monitoring history across 156 updates, with the same six panels as Figure 4(a). The dashed line marks the evaluated update-100 checkpoint. Online monitoring samples 128 goals from the pool also used in complete evaluation; updates 101-156 are later training diagnostics.

Table 2. Interaction-quality means over the first 100 updates of each aggregation condition (100 records). Percentages average training updates; the response-limit monitor is distinct from backend truncation in complete-task evaluation.

7.2 Actor-update and segment-coefficient comparisons This ALFWorld comparison changes only policy-gradient aggregation: the default uses loss_agg_mode=seq-meantoken-sum, and the reference uses seq-mean-token-mean. For N active responses of lengths Lᵢ, the reference averages the token surrogates within each response before averaging responses:

Aggregation reference Valid actions (%) 92.60 Branch valid actions (%) 91.60 Valid format (%) 96.80 Responses at token limit (%) 2.40 Mean response tokens 162.18

Diagnostic

L

i −1 −1 N Jnorm PG (θ)=N ∑i=1 [Li ∑j=1 Sc (ρi,j ,Ai )].

The default removes the response-specific factor 1/Li from the PG term. Appendix B.3 proves that this eliminates the associated length-normalization term under a fixedcontext score calculation; it does not prove that adaptive tree advantages are unbiased. Both conditions keep the fixedreference penalty summed over tokens with the same global active-turn denominator N; entropy regularization remains disabled. Initialization, the Section 4 allocator, rollout budgets, advantages, segment coefficients, optimizer, learning rate, and clipping remain at Table A1 defaults. No learning-rate or regularization compensation accompanies the PG switch. Tables 2-3 summarize the first 100 actor updates (100 records per condition).

TSBPO 96.59 94.59 99.55 0.01 141.80

Table 3. Temporal variability and PPO clipping over the same 100 records per condition. SD describes temporal variation rather than variation across independent training seeds. Diagnostic Valid-action SD (pp) Token-limit SD (pp) PPO clipped tokens (%)

Aggregation reference 5.83 6.03 1.81

TSBPO 1.92 0.03 1.31

Complete-turn aggregation yields higher observed command validity (96.59% versus 92.60%), fewer responses at the token limit (0.01% versus 2.40%), and shorter mean outputs (141.80 versus 162.18 tokens). With the remaining settings fixed, the aggregation switch changes both the weighting of responses and the magnitude of the PG contribution relative to regularization. These are the measured effects of the specified optimization configuration.

7

budgets, PG aggregation, segment weighting, optimization, and regularization. The coefficient is one in the full model. Both update-100 checkpoints are evaluated on the same 500 WebShop goals, with six stochastic episodes per goal, temperature 0.4, evaluation seed 0, and a 15-step horizon. Table 5 reports 81.07% success for TSBPO (2,432/3,000) and 75.93% without step advantage (2,278/3,000). Removing the step term reduces success by 5.13 percentage points; the paired 95% interval for ablation minus full is [−7.80, −2.53] points. Intervals use 20,000 percentile bootstrap resamples of whole goals, preserving all six trials per goal. The full model records more successful trials on 89 goals, the ablation on 49, and both tie on 362. Table 5. WebShop step-advantage ablation at update 100. Credit magnitudes average the per-update training diagnostics over updates 1–100; success intervals resample evaluation goals.

Figure 5. Full ALFWorld PG-aggregation comparison over the first 100 updates. Panels show command validity, response format, actor entropy, and response length. The other actor settings remain fixed; points are measurements and solid lines are centered fiverecord means.

Metric Step coefficient Mean absolute step credit Successful episodes Success (%) [95% interval]

Relative to Table A1, this ALFWorld comparison changes only the optional segment plugin: unit coefficients versus enabled weighting with cap C=6. Initialization, the Section 4 allocator, rollout budgets, complete-turn aggregation, optimizer, and regularization are identical. Both models receive complete-task evaluation after 175 actor updates. Table 4 reports these outcomes.

Without segment balance With segment balance (C=6)

Seen success (%) 97.79

96.64

97.23

96.71

94.93

95.84

w/o step 0 0.000 2,278/3,000 75.93 [72.33, 79.47]

Figures 6 and 7 trace the corresponding first 100 actor updates. The disabled step term gives zero local step credit by construction; mixed-outcome rates describe the sampled groups, while online validation tracks the training histories separately from the complete update-100 evaluation in Table 5.

Table 4. Complete-task stochastic evaluation of both segment configurations at an equal final training budget. Every model uses the same 140 seen and 134 unseen tasks, ten episodes per task, and the decoding protocol in Appendix A. Overall success weights all 2,740 episodes equally. Configuration

TSBPO 1 1.197 2,432/3,000 81.07 [77.97, 84.13]

Unseen Overall success (%) success (%)

Figure 6. WebShop training diagnostics for TSBPO and the nostep-advantage ablation over updates 1–100. The panels show mean absolute local step credit and observed mixed-outcome rate. Pale points and traces are per-update records; bold curves are centered seven-update means. The outcome rate is a realized sampling diagnostic, not a probability-calibration result.

Paired measurements on the enabled run’s trees show the intended scalar-mass change: the mean worst-sibling relative gap falls from 2.917 before weighting to 1.031 afterward. Bounds are active for 6.47% of child segments. This measures coefficient redistribution, not gradient equality. Appendix Table A5 gives additional bare/branch credit and tree-structure diagnostics. Unit coefficients achieve higher final stochastic success overall: 97.23% versus 95.84%, a 1.39-point difference with paired task-bootstrap interval −0.26 to 2.96 points. Greedy success also favors unit coefficients, whereas completeevaluation truncation is lower with the plugin (0.07% versus 0.20%). These single-run comparisons support optional configuration rather than a required performance contribution; their intervals describe evaluation-task variation, not training-seed uncertainty.

7.3 WebShop step-advantage ablation We set the step-advantage coefficient to zero in the actor update, retaining physical-sibling trajectory credit and the Table A2 settings for initialization, allocation, rollout

8

[2] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal Policy Optimization Algorithms. arXiv:1707.06347, 2017. https://arxiv.org/abs/1707.06347 [3] Shao, Z., Wang, P., Zhu, Q., et al. DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. arXiv:2402.03300, 2024. https://arxiv.org/abs/2402.03300 [4] Feng, L., Xue, Z., Liu, T., and An, B. Group-in-Group Policy Optimization for LLM Agent Training. Advances in Neural Information Processing Systems, 38, 2025. https://proceedings.neurips.cc/paper_files/paper/2025/hash/42 0c9f777c0b4f78d515e53cf74d58b2-Abstract-Conference.html [5] Li, Y., Gu, Q., Wen, Z., et al. TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling. arXiv:2508.17445, 2025. https://arxiv.org/abs/2508.17445 [6] Zong, Z., Chen, D., Li, Y., et al. AT²PO: Agentic Turn-based Policy Optimization via Tree Search. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 24120–24143, 2026. https://doi.org/10.18653/v1/2026.acl-long.1106 [7] Liu, Z., Chen, C., Li, W., et al. Understanding R1-Zero-Like Training: A Critical Perspective. arXiv:2503.20783, 2025. https://arxiv.org/abs/2503.20783 [8] Wang, H., Ren, W., Zhang, Y., et al. BiPACE: BisimulationGuided Policy Optimization with Action Counterfactual Estimation for LLM Agents. arXiv:2606.25556, 2026. https://arxiv.org/abs/2606.25556 [9] Mao, Y., Qu, Y., Wang, Q., Zou, H., and Ji, X. DynamicsPredictive Sampling for Active RL Finetuning of Large Reasoning Models. arXiv:2603.10887, 2026. https://arxiv.org/abs/2603.10887 [10] Yu, Q., Zhang, Z., Zhu, R., et al. DAPO: An Open-Source LLM Reinforcement Learning System at Scale. arXiv:2503.14476, 2025. https://arxiv.org/abs/2503.14476 [11] Wang, Z., Wang, K., Wang, Q., et al. RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning. arXiv:2504.20073, 2025. https://arxiv.org/abs/2504.20073 [12] Yao, S., Chen, H., Yang, J., and Narasimhan, K. WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents. arXiv:2207.01206, 2022. https://arxiv.org/abs/2207.01206 [13] Yao, S., Zhao, J., Yu, D., et al. ReAct: Synergizing Reasoning and Acting in Language Models. ICLR, 2023. https://arxiv.org/abs/2210.03629 [14] Shinn, N., Cassano, F., Berman, E., et al. Reflexion: Language Agents with Verbal Reinforcement Learning. arXiv:2303.11366, 2023. https://arxiv.org/abs/2303.11366 [15] Yang, A., Yang, B., Zhang, B., et al. Qwen2.5 Technical Report. arXiv:2412.15115, 2024. https://arxiv.org/abs/2412.15115 [16] Schulman, J., Levine, S., Moritz, P., et al. Trust Region Policy Optimization. arXiv:1502.05477, 2015. https://arxiv.org/abs/1502.05477 [17] Schulman, J., Moritz, P., Levine, S., et al. High-Dimensional Continuous Control Using Generalized Advantage Estimation. arXiv:1506.02438, 2015. https://arxiv.org/abs/1506.02438 [18] Kool, W., van Hoof, H., and Welling, M. Buy 4 REINFORCE Samples, Get a Baseline for Free! ICLR Workshop, 2019. https://wouterkool.github.io/publication/buy-4-samples-freebaseline/ [19] Ahmadian, A., Cremer, C., Gallé, M., et al. Back to Basics: Revisiting REINFORCE-Style Optimization for Learning from Human Feedback in LLMs. ACL, 2024. https://aclanthology.org/2024.acl-long.662/ [20] Zhou, Y., Zanette, A., Pan, J., et al. ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL. arXiv:2402.19446, 2024. https://arxiv.org/abs/2402.19446

Figure 7. WebShop online-validation success through update 100. Points show recorded validation updates and bold curves are centered three-record means. Each condition has one training run; Table 5 reports the separate complete evaluation of the update-100 checkpoints.

8. Discussion The task evaluations establish performance of the two stated training configurations; suffix outcomes show the alternatives they acquired. The allocator chooses samples before credit is computed, while observed sibling and observation-group outcomes determine the subsequent advantages. Online prediction reliability is a separate property from preferentially sampling high-scored groups, and the WebShop diagnostics show measurable overprediction. The WebShop step-term comparison favors the full update at the evaluated checkpoint.

9. Limitations Each configuration has one training run. Task-bootstrap intervals do not measure training-seed variation. WebShop monitoring and complete evaluation share the same goal pool. Adaptive tree means are observed-tree credit proxies, without a general unbiasedness, monotonic-improvement, or convergence result. The two benchmarks and one actor scale do not establish broader generality.

10. Conclusion TSBPO connects outcome-contrast sampling, physicalsibling and observation-group credit, and complete-turn updates for interactive language agents. The evaluated configurations achieve 97.79% seen and 96.64% unseen ALFWorld success and 81.07% WebShop success; WebShop's likelihood-fitted predictions also show online overprediction. AI assistance disclosure. A large language model assisted with drafting and editing this manuscript; the authors are responsible for the final text, analyses, and references.

References [1] Shridhar, M., Yuan, X., Côté, M.-A., Bisk, Y., Trischler, A., and Hausknecht, M. ALFWorld: Aligning Text and Embodied Environments for Interactive Learning. arXiv:2010.03768, 2020. https://arxiv.org/abs/2010.03768

9

[21] Chen, K., Cusumano-Towner, M., Huval, B., et al. Reinforcement Learning for Long-Horizon Interactive LLM Agents. arXiv:2502.01600, 2025. https://arxiv.org/abs/2502.01600 [22] Arjona-Medina, J. A., Gillhofer, M., Widrich, M., et al. RUDDER: Return Decomposition for Delayed Rewards. arXiv:1806.07857, 2018. https://arxiv.org/abs/1806.07857 [23] Harutyunyan, A., Dabney, W., Mesnard, T., et al. Hindsight Credit Assignment. arXiv:1912.02503, 2019. https://arxiv.org/abs/1912.02503 [24] Guo, D., Yang, D., Zhang, H., et al. DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning. Nature, 645:633–638, 2025. https://doi.org/10.1038/s41586-025-09422-z [25] Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1–2):99–134, 1998. https://doi.org/10.1016/S0004-3702(98)00023-X [26] Sutton, R. S., Precup, D., and Singh, S. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1–2):181– 211, 1999. https://doi.org/10.1016/S0004-3702(99)00052-1 [27] Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8:229–256, 1992. https://doi.org/10.1007/BF00992696 [28] Greensmith, E., Bartlett, P. L., and Baxter, J. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 5:1471–1530, 2004. https://jmlr.org/papers/v5/greensmith04a.html [29] Narvekar, S., Peng, B., Leonetti, M., Sinapov, J., Taylor, M. E., and Stone, P. Curriculum learning for reinforcement learning domains: A framework and survey. Journal of Machine Learning Research, 21(181):1–50, 2020. https://jmlr.org/papers/v21/20-212.html [30] Klink, P., Abdulsamad, H., Belousov, B., D'Eramo, C., Peters, J., and Pajarinen, J. A probabilistic interpretation of self-paced learning with applications to reinforcement learning. Journal of Machine Learning Research, 22(182):1–52, 2021. https://jmlr.org/papers/v22/21-0112.html [31] Li, J., Wang, Y., Yan, Q., Tian, Y., Xu, Z., Song, H., Xu, P., and Cheong, L. L. SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph. Findings of the Association for Computational Linguistics: EACL 2026, 4709–4725, 2026. https://doi.org/10.18653/v1/2026.findingseacl.247 [32] Cheng, X., He, S., Feng, L., Xu, H., Yan, M., Feng, L., and An, B. Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning. Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:18861–18886, 2026. https://proceedings.mlr.press/v306/cheng26e.html [33] He, S., Feng, L., Wei, Q., Cheng, X., Feng, L., and An, B. Hierarchy-of-Groups Policy Optimization for Long-Horizon Agentic Tasks. arXiv:2602.22817, 2026. https://arxiv.org/abs/2602.22817 [34] Zhang, J., Huang, C., Guo, F., et al. DPEPO: Diverse Parallel Exploration Policy Optimization for LLM-based Agents. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 46367– 46389, 2026. https://doi.org/10.18653/v1/2026.acl-long.2151

Appendix A. Models, Configuration, and Evaluation Details Model, Training, and Evaluation Configuration For ALFWorld and WebShop, Qwen2.5-1.5B experiments are run on 6×RTX 4090 GPUs. Tables A1 and A2 give the configurations of the evaluated ALFWorld and WebShop models. Both start from environment-specific SFT of Qwen2.5-1.5B-Instruct [15] and use that initialization as the fixed RL reference. Both evaluated models use the likelihood-fitted Root and Branch path with bounded semantic evidence, original remaining deadlines, and local-state-contrast Branch utility (Section 4). Table A1. Default ALFWorld configuration for all experiments unless a comparison explicitly specifies a change. Root direct evidence decays by 0.95 per round; Branch-state evidence decays by 0.90. Parameter

Setting Environment-specific Qwen2.5Actor / fixed reference 1.5B SFT Likelihood-fitted Root/Branch; Allocator local-state contrast Selected tasks / candidate pool 15 / 120 Root / additional suffix budgets 90 / 120 Minimum roots / new suffixes 2/4 per opening Rollout temperature / top_p / 1.0 / 1.0 / −1 top_k loss_agg_mode=seq-mean-tokenPG aggregation sum Actor learning rate 2×10⁻⁶ PPO minibatch / per-rank 240 / 4 microbatch Reference / entropy 0.05 / 0 coefficients Root direct evidence decay 0.95 Branch-state evidence decay 0.90 Episode action limit / history 50 / 3 turns Prompt / generated-token limits 2,048 / 512 Optional segment plugin Disabled (unit coefficients) Nominal root group / 6/6 prediction group Task-specific root quota cap None (full root budget) Branch worker / per-anchor 64 / 64 new suffixes capacity Optimizer / PPO epochs per AdamW / 1 rollout batch Environment / generation / 0/0/1 data-sampler seeds Allocation / actor-row 17 / 17 + 1,000,003 × update permutation seeds

The complete ALFWorld assessment starts from every seen and unseen validation task. Each task has ten stochastic episodes at temperature 0.4, top_p=1, top_k=−1, and repetition penalty one, plus one greedy episode. Episodes have at most 50 environment steps, 512 generated tokens per turn, three turns of history, and a 2,048-token prompt limit. Stochastic success is the fraction of successful episodes; the task-bootstrap interval resamples whole tasks

10

with their ten outcomes. Action validity requires format compliance and command admissibility, and backend truncation follows the generation termination record. ALFWorld online monitoring runs 120 stochastic episodes sampled from the valid-seen split every five actor updates; the denominator is episodes, and task identities need not be distinct. Decoding uses temperature 0.4, top_p=1, top_k=−1, and repetition penalty one, with the same 50-action limit, three history turns, 2,048-token prompt limit, and 512-token response limit as complete-task assessment. The approximately 68% initial anchor uses this smaller monitoring sample, whereas the approximately 66% independent SFT result covers all seen tasks with repeated episodes.

episode per goal and the same decoding and interaction limits; training samples goals outside that pool. These online scores track training but do not rank saved checkpoints for the reported complete assessment. The assessment evaluates the update-100 model on the same goal pool with additional episodes, rather than on a disjoint task set. Table A3. Additional complete WebShop evaluation diagnostics for the update-100 model. The 20,104 evaluated turns include invalid outputs but exclude padding; turn rates use this denominator. Horizon termination counts episodes. Diagnostic

Count or value

Evaluated interaction 20104 turns 99.99% Format-valid outputs Executable actions 99.88% Mean generated response 113.19 568 Unsuccessful episodes Failed episodes at horizon 256 All episodes at horizon 260 3 Truncated outputs Mean successful / failed 5.84 / 10.41 length

Table A2. Evaluated WebShop likelihood-fitted configuration through update 100. Parameter

Setting Environment-specific Qwen2.51.5B SFT Likelihood-fitted Root/Branch; Allocator local-state contrast Selected tasks / candidate pool 16 / 128 Root / additional suffix budgets 96 / 128 Minimum roots / new suffixes 2/4 per opening Rollout temperature / top_p / 1.0 / 1.0 / −1 top_k loss_agg_mode=seq-mean-tokenPG aggregation sum Actor learning rate 2×10⁻⁶ PPO minibatch / 240 / 5120 ppo_max_token_len_per_gpu Reference / entropy 0.05 / 0 coefficients 0.95 Root direct evidence decay Branch-state evidence decay 0.90 Episode action limit / history 15 / 3 turns Prompt / generated-token limits 4,608 / 512 Optional segment plugin Enabled, cap C=6 Nominal root group / 6/6 prediction group None (full root budget) Task-specific root quota cap Branch worker / per-anchor 64 / 64 new suffixes capacity Optimizer / PPO epochs per AdamW / 1 rollout batch Environment / generation / 0/0/1 data-sampler seeds Allocation / actor-row 17 / 17 + 1,000,003 × update permutation seeds Actor / fixed reference

Denominator / unit Turns Evaluated turns Evaluated turns Tokens / turn 3000 episodes 3000 episodes 3000 episodes Turns Actions / episode

External protocols. HGPO’s K=2 and K=4 settings denote historical context depth, not rollout count; both start from Qwen2.5-1.5B-Instruct and allow 30 WebShop actions [33, Sections 4.2 and C.3]. BiPACE reports maximum aggregate validation success over training; its ALFWorld family entries can select different checkpoints [8, Table 4 and Appendix N]. Our rows evaluate one model per benchmark at the checkpoint specified in Section 7.1. These protocols determine the contextual role of the published scores in Table 1.

SFT Cold-Start Data Collection and Configuration Before online RL, successful interactions generated by the GPT-5.6-sol teacher align the actor with the environment’s observation, reasoning, and action syntax. Both benchmarks use the same collection procedure: the teacher interacts with training environments, successful complete trajectories are retained, and each retained turn becomes a user–assistant pair in ShareGPT format. The user message contains the environment prompt; the assistant message contains the generated response, with a <think>...</think> block followed by an <action>...</action> block. Supervised training applies causal next-token likelihood to assistant tokens. The resulting environment-specific model initializes both the RL actor and its fixed reference. Table A4 gives the supervised cold-start settings. For both benchmarks, the student starts directly from Qwen2.5-1.5BInstruct and undergoes two epochs of full-parameter SFT on the corresponding successful-trajectory dataset. Both use the Qwen chat template, DeepSpeed ZeRO-2, BF16, FlashAttention 2, gradient checkpointing, and cosine learning-rate decay. The five-percent held-out split comes from each training dataset and monitors supervised loss; it is separate from environment validation tasks.

Complete WebShop assessment uses the 1,000-product catalog and all 500 synthetic test goals, indexed 0-499 under goal-order seed zero. Each receives six stochastic episodes at temperature 0.4, top_p=1, top_k=-1, with at most 15 actions, three history turns, 4,608 prompt tokens, and 512 generated tokens per turn. The environment's won flag determines success. Task-bootstrap intervals use 10,000 whole-task resamples, preserving six attempts per goal. Online monitoring samples 128 distinct goals from the same 500-goal test pool every five updates, with one stochastic

11

Figures A1 and A2 give the history-conditioned turn prompts. Braced fields are filled at runtime; colors distinguish semantic slots and response tags.

Table A4. Supervised cold-start settings. Both students start directly from Qwen2.5-1.5B-Instruct and train for two epochs; demonstrations are collected with GPT-5.6-sol.

Prompt Template for ALFWorld

Setting

ALFWorld User–assistant Example format pairs Training examples 3,040 Prompt cutoff (tokens) 2,048 Training batch per device 4 Gradient accumulation 2 Learning rate 5×10−6 Training epochs 2 Warmup ratio 0.10 Supervised validation split 0.05 Evaluation batch per 4 device Evaluation interval 200 (updates) Logging interval (updates) 10

You are an expert agent operating in the ALFRED Embodied Environment. Your task is to: {task_description} Prior to this step, you have already taken {step_count} step(s). Below are the most recent {history_length} observations and the corresponding actions you took: {action_history} You are now at step {current_step} and your current observation is: {current_observation} Your admissible actions of the current situation are: [{admissible_actions}]. Now it's your turn to take an action. You should first reason step-by-step about the current situation. This reasoning process MUST be enclosed within <think> </think> tags. Once you've finished your reasoning, you should choose an admissible action for current step and present it within <action> </action> tags. Figure A1. ALFWorld turn prompt. Braced fields denote runtime inputs; the response uses the displayed reasoning/action tags.

WebShop User–assistant pairs 4,605 5,120 2 4 5×10−6 2 0.05 0.05 2 200 10

Each shopping attempt allows fifteen actions. A failed attempt can supply private reflection to a subsequent attempt of the same query, with at most three attempts. Only trajectories whose terminal environment flag indicates success enter the exported dataset. Their original user prompts and final valid assistant responses are saved as one pair per turn; private reflection and repair messages are excluded. The WebShop supervised dataset contains 4,605 user–assistant pairs from successful training trajectories. The environment-specific BF16 supervised models initialize both the RL actor and fixed reference. Historical SFT assessments retain an earlier assessment protocol: two episodes on each ALFWorld seen task with Q8_0 inference (185/280 successes), and 512 WebShop episodes (266 successes). It supplies initialization context; differences from the RL rows are not reported as matched SFT-to-RL gains.

Prompt Template for WebShop You are an expert autonomous agent operating in the WebShop e-commerce environment. Your task is to: {task_description}. Prior to this step, you have already taken {step_count} step(s). Below are the most recent {history_length} observations and the corresponding actions you took: {action_history} You are now at step {current_step} and your current observation is: {current_observation}. Your admissible actions of the current situation are: [ {available_actions} ]. Now it's your turn to take one action for the current step. You should first reason step-by-step about the current situation, then think carefully which admissible action best advances the shopping goal. This reasoning process MUST be enclosed within <think> </think> tags. Once you've finished your reasoning, you should choose an admissible action for current step and present it within <action> </action> tags. Figure A2. WebShop turn prompt. Braced fields denote runtime inputs; the response uses the displayed reasoning/action tags.

Tree Structure and Credit-Composition Diagnostics

The WebShop collection pipeline uses the 1,000-product training catalog, excluding sessions 0–499 and their associated validation queries. Queries with insufficient successful demonstrations receive priority. Up to eight environment sessions and sixteen teacher requests run concurrently. The prompt includes the goal, current page, admissible commands, and at most five recent observation– action pairs. Teacher requests allow 2,048 completion tokens and 512 tokens for reflection, use high reasoning effort, and leave temperature and top_p at the service defaults. The collector checks the two tagged blocks and command admissibility, allowing two repairs before execution.

Table A5 reports tree-structure and sampling diagnostics used in Section 7.2. For a sibling group with child masses mc , its relative gap is (maxc mc −minc mc )/meanc mc ; each training update reports the maximum across groups. Coefficient quantiles are computed over active turn rows, whereas cap frequency counts child segments. Absolute combined advantage averages the magnitude of the composed row advantage separately for bare and branch rows. A sign conflict means the product of the trajectory and state-step components is negative. These are distinct measures of tree weighting and credit composition, rather than independent-trajectory counts or direct gradientvariance estimates.

12

E[pn ]=B(A+n,B)/B(A,B), (B.1) E[(1−p)n ]=B(A,B+n)/B(A,B). Subtracting the two all-equal events gives the component utility u(n;A,B). Averaging u over the task-specific weights wi (θ) yields the Root mixture utility (5). Because these weights do not depend on the proposed n, its one-rollout gain is

Table A5. Tree coefficient masses and credit composition. ALFWorld columns average 175 updates per run; the evaluated WebShop column averages updates 1-100 of the likelihood-fitted run. Each diagnostic contributes one record per update. Before/after values within an enabled run use the same tree batch; cross-run differences also include policy and sampled-tree variation. WebShop provides weighting context rather than an on/off control. Diagnostic Worst sibling mass gap before weighting Worst sibling mass gap after weighting Child segments at coefficient bounds (%) Median active-row coefficient 95th-percentile activerow coefficient Branch fraction of active rows (%) Absolute combined advantage, bare Absolute combined advantage, branch Trajectory/state sign conflict, bare (%) Trajectory/state sign conflict, branch (%)

ALFWorld plugin off

ALFWorld plugin on

WebShop plugin on

2.851

2.917

2.575

2.851

1.031

0.360

0.00

6.47

1.61

1.000

0.878

0.935

U(n+1)−U(n)=E[pn (1−p)+(1−p)n p]≥0. (B.2) Both terms in the integrand decrease as n increases, so each component and their weighted mixture have diminishing gains after the first rollout. The zero-to-one gain is zero; Root allocation therefore starts each selected task with two factual rollouts. This is a conditional predictive calculation. Age-weighted evidence and policy drift do not establish that the resulting mixture is a calibrated probability of future success.

1.000

1.864

1.589

B.2 State-group contrast and its marginal gains

64.15

65.61

55.99

1.935

2.126

2.488

4.290

4.127

3.415

18.12

14.68

9.59

13.87

11.92

7.77

Condition on evidence D and the modeled oppositeoutcome probability �� for a factual-homogeneous state group a. If new suffix labels are conditionally independent given �� , the chance that all �� new suffixes retain the factual label is (1 − �� )�� . Subtracting this chance from one and integrating over the predictive law proves (7). Linearity of expectation makes the sum in (9) the expected number of newly mixed factual-homogeneous groups, even when the predictive particles are correlated across groups. Subtracting the local no-contrast probabilities before and after m additional suffixes proves (8). For the same state group, let l≥k be two suffix quotas. Since 0≤1− �� ≤1, the residual no-contrast factor at l is no larger than at k in every particle. Thus the same added block has

Task-Group Sampling-Ratio Definition Panel (e) of Figure 4(a) and Figure 4(b) reports the taskgroup effective sampling ratio using the update-level definition below. er =|Tr |−1 ∑t∈Tr 1[0<∑b∈Bt,r Yb <|Bt,r |].

0≤Δa,m (l)≤Δa,m (k). (B.3)

Here Tᵣ is the set of sampled task identities, Bₜ,ᵣ contains distinct completed terminal trajectories after branching, and Yᵦ is binary success; duplicate turn rows do not create new trajectories. An empty task set has ratio zero. Suffix-contrast rates divide the number of qualifying new suffixes by max(1, number of completed new suffixes); selected-group conversion rates use the same max(1, denominator) convention for eligible groups with completed evidence. Thus a zero-denominator update contributes zero to the unweighted update mean. Candidate and selected probability means summarize representatives before branching.

For fixed �� , the gain per added suffix is nonincreasing in the block size. These statements hold for a fixed predictive law supported on [0,1] and for its finite particle average. They do not prove that the particle law is calibrated to future actor outcomes. The minimum opening quota rules out an unrestricted greedy claim, but the integer dynamic program exactly maximizes the finite-particle objective over the implemented feasible quotas. The counted event is a new terminal-label contrast at a factual-homogeneous state group. One task can contribute several eligible groups, including when its factual trajectories are already mixed across other observations. A newly mixed observation group need not create a mixed group at every physical sibling split, and local costs can create score differences even when labels agree. Acquisition therefore directs sampling; it does not guarantee a nonzero actor gradient.

Appendix B. Conditional Predictor and Optimizer Derivations B.1 Predictive mixed-group probability For a fixed success probability p and n≥1 conditionally independent outcomes from one task, the probability of observing both labels is 1−pn−(1−p)n. Within a fitted mixture component p∼ Beta(A,B), with A,B>0, the beta integral gives

B.3 Complete-turn aggregation and length normalization For the local score identity in Section 5.3, condition on a fixed batch with contexts, generated tokens, N>0 active

13

turns, and detached advantages. Sampled tokens have positive behavior probability and differentiable policy probabilities near θold . For ε>0, each ratio equals one strictly within its clipping interval. For negative A and dual cap c>1, A>cA, so the cap is locally inactive. Zero advantages contribute zero. At the behavior policy,

F(λ)=T,λ∈[0,C/minc ac ]. (B.7) Bisection moves its lower bound upward when F<T and its upper bound downward otherwise. Sixty iterations give the projection used by the actor, up to numerical precision. For C=1 every coefficient is one. If no bound is active, F(λ)=λKm̄ =λT , hence λ=1 and every effective child mass equals m̄ . Active bounds preserve total mass while permitting unequal child masses. Zero-weight rows and empty responses do not enter active policy groups, so their segments have no positive policy mass to balance. For a formal zero-mass segment its coefficient may be set to one and its contribution is zero; an all-zero group can be omitted. Equalization concerns positive masses only. Neither mass conservation nor equality determines parameter-gradient norms, which also depend on token score vectors and advantages.

∇θ Sc (ρi,j ,Ai )=Ai ∇θ logπθ (yi,j |Hi ,yi,<j ). (B.4) Summing over tokens and differentiating autoregressive factorization (2) yields

the

∇θ JPG (θold )=(1/N)∑i Ai ∇θ logπθ (yi |Hi )|θ=θold . (B.5) Equation (B.5) is an exact fixed-batch gradient identity; it does not assert that the sampled advantages equal unbiased policy advantages. EOS is included only when generated, and padding contributes nothing. Deterministic detached row weights enter the sum in the same way. The denominator is the sampled active-turn count, not an inverse episode-inclusion probability; episodes with more retained turns contribute more terms before optional reweighting. For the response-length result, fix a context H and suppose the response law has differentiable probabilities with common support and positive finite lengths L(y). Let R(y) have no direct dependence on θ and let b=b(H) be a finite baseline independent of the sampled response. Interchanging differentiation and expectation, the score identity gives E[(R-b)∇θ log πθ(y|H)]=∇θ E[R]. Dividing each response score by its sampled length instead gives E[((R-b)/L(y))∇θ log πθ(y|H)]=∇θ E[R/L(y)]-b∇θ E[1/L(y)]. In particular,

B.5 Reference penalty For δ≤δ*=log(1+M), the derivative of (D.2) is exp(δ)−1; above the join it is M. Both the value M−δ* and derivative M agree at the join. The derivative is nondecreasing, and δ=0 is a global minimum with value zero. Thus kM is nonnegative, convex, and continuously differentiable. Its tangent continuation retains a correcting derivative without exponential growth. The modified tail defines a regularizer rather than an exact KL identity.

Appendix C. Predictive and Fallback Definitions

E[(b/L(y))∇θ logπθ (y|H)]=b∇θ E[1/L(y)]. (B.6) The undivided baseline term vanishes because E[∇θ log πθ(y|H)]=∇θ1=0; the length-divided term in (B.6) need not vanish. For a concrete example, suppose the only responses have lengths one and two, the second has probability q(θ), R(y)=0 for both, and b>0. The expected undivided, baseline-subtracted PG score is zero, while the lengthdivided, baseline-subtracted score is (b/2)∇θ q(θ), nonzero wherever q varies. Thus removing 1/L(y) exactly removes this normalization-induced mechanism, as in Dr. GRPO [7]. It does not establish unbiasedness for TSBPO's empirical sibling baselines or outcome-dependent tree selection. Away from θold , the complete-response likelihood ratio is ∏j ρi,j ; a sum of tokenwise clipped terms generally differs from a surrogate based on that product. The local score identity applies to the PG component before reference regularization, not to exact sequence importance sampling across multiple PPO updates.

C.1 Likelihood fitting from complete terminal counts Root and Branch fit separate finite mixtures over θ=(a,b,η,ρ). The base success probability has Beta(a,b) shape; η and ρ scale historical direct and capped semantic evidence, respectively. For a query with historical counts ( hs , hf ), current bare counts ( cs , cf ), and semantic masses (ms ,mf ), the component shapes are Aθ =a+ηhs +cs +ρms and Bθ =b+ ηhf + cf + ρmf . Root has cs = cf =0; Branch conditions once on completed current bare outcomes. The grid combines 25 base means from 0.025 to 0.975, 31 logarithmically spaced base concentrations from 0.001 to 100, and η,ρ∈{0,0.03125,0.125,0.5,1}, for 19,375 equally weighted initial components. An audited physical group g with sg successes and fg failures contributes the betabinomial count likelihood Lg (θ)=

B.4 Bounded scalar-mass projection

sg +fg B(Ag (θ)+sg ,Bg (θ)+fg ) sg

B(Ag (θ),Bg (θ))

. (C.1)

For query task t, population fitting excludes that task and uses complete groups available before allocation. A group collected at round rg receives fitting weight cg =��−rg /Mtg,rg , where Mtg,rg counts groups from its task in that round; λ is 0.95 for Root and 0.90 for Branch. Its preallocation evidence snapshot determines Ag and Bg in (C.1). Semantic masses are covariates, not additional terminal labels.

Consider K positive segment masses mc , total T=∑c mc >0, mean m̄ =T/K, and C≥1. Define ac =m̄ /mc and F(λ)=∑c mc clip(λac ,1/C,C) . For C>1, F is continuous and nondecreasing, F(0)=T/C≤T , and at λhi =C/minc ac all factors reach C, giving F(λhi )=CT≥T . Here every ac is positive, so the denominator is positive. The intermediate value theorem establishes a solution to

14

With a uniform prior over the finite grid, the normalized, task-excluded component weights satisfy

completed physical suffixes update state memory without crediting replayed ancestors. The particle law approximates shared task and trajectory-cluster dependence and does not establish calibrated future success probabilities by itself.

wt (θ)∝exp[∑g:tg≠t cg logLg (θ)]. (C.2) At least two other tasks are required to fit population weights; otherwise the prediction uses Beta(1/2,1/2). Without identifiable historical evidence η remains one, and without identifiable semantic evidence ρ is zero. When Branch groups are sparse, complete factual Root groups from other tasks can initialize its base distribution, but Root reliability coefficients are not transferred. Only a group whose complete physical outcome count equals its assigned quota enters likelihood fitting. The age-weighted conditional likelihood is a drift-aware predictive approximation, not an exact stationary hierarchical posterior.

C.3 Factual-root compatibility credit Let Bx be the distinct factual root trajectories for task x and Fb the active turns belonging to factual root b. Conditional branch suffixes are not additional members of Bx . With terminal return Rb and local cost Pi , define Sroot b =(1/|Fb |)∑i∈Fb (Rb −Pi ), (C.4) root root Ab =Sroot b −(1/|Bx |)∑b'∈Bx Sb' . An active turn without an assignable physical sibling from its factual root. Assigned local segment inherits Aroot b credit takes precedence, including when zero; the fallback is not added. The observation-group step term is composed as in (14). With the optional plugin, fallback turns of the same root form a child segment of a task-root group and use the same scalar-mass rule.

C.2 Shared Branch prediction particles For each task t with eligible state groups and particle index ℓ, sample one θt ℓ from its task-excluded Branch mixture and share that component across all candidate anchors of t. Draw task-shared base masses Gt,+ ℓ∼ Gamma(aθ ,1) and Gt,− ℓ∼ Gamma(bθ ,1). A physical sampling cluster b contains nb paths; in state/depth pool a, its compressed counts sab and fab record the successful and failed paths visiting a once, while uab =nb −sab −fab counts the other paths. Equal visiting-subset fingerprints reuse the same within-cluster draw. For particle ℓ, the pool/cluster scale is zab ℓ=0.90age ηθℓt for historical direct evidence, one for current bare evidence, and the bounded semantic donor factor times ρθℓt for borrowed evidence. Draw a cluster total with Gamma(nb zab ℓ,1) shape and visiting-category gamma masses with shapes ( sab zab ℓ,fab zab ℓ,uab zab ℓ); zero-count categories have zero mass. Normalize category masses to the shared total. The total is reused for the same cluster and scale vector, preserving dependence between matching compressed subsets.

C.4 Semantic evidence and allocation settings

A frozen Qwen3-Embedding-0.6B encoder maps each task instruction to an L2-normalized vector ei ; observations, prompt templates, and interaction histories do not enter this Root feature. Among other tasks with direct outcomes, at most eight neighbors with cosine similarity at least 0.95 receive kernel weight [max(0,(cos(ei ,ej )−0.95)/0.05)]2. Each source success/failure pair is first capped at total mass six; the weighted donor sum is capped at total mass four. The resulting semantic masses ( mi s, mi f) enter each Root component with its learned ρθ as in Section 4.2. They remain query-only covariates, never physical terminal observations or recursively borrowed evidence. Branch state pools query bounded semantic counts from similar historical states. The same frozen encoder produces normalized features for the task goal and for the goal together with the current observation. Encoded text preserves numbers, negations, prices, and object attributes. A donor must have the same depth and episode horizon, state cosine similarity above 0.95, and goal cosine similarity above 0.90. At most eight eligible historical pools are inspected in descending state similarity. For state and goal and cg , the donor kernel is similarities cs κ=[(cs −0.95)/0.05]2[(cg −0.90)/0.10]2. Only physical terminal counts from earlier rounds can be borrowed. A sampling cluster already present in the exact query pool is excluded; each remaining cluster contributes at most one visiting subset from its highest-ranked eligible donor. That subset is rescaled to mass at most one, weighted by κ and its original 0.90 age decay, and included in a globally capped semantic mass. The configured raw borrowed-mass cap is four for ALFWorld. The particlespecific ρθ scales this mass during prediction. Borrowed masses are not committed as direct outcomes, and physical state groups remain exact task/observation groups. The Root curriculum scores the integrated mixture event (5) at nref =max(1, nrollout ), with nrollout =6 in both benchmarks; a selected task receives at least two factual

Xℓa,± =Gℓt,± +∑b Wℓab,± ,pℓa =Xℓa,+ /(Xℓa,+ +Xℓa,− ). (C.3) Here Wab,± ℓ is the scaled successful or failed category mass from cluster b. Historical scale includes original collection age and the particle’s η; current bare uses unit scale, while semantic donor scale includes retrieval similarity, age, caps, and the particle’s ρ. An exact-query cluster cannot also be a semantic donor, and each donor cluster supplies at most one visiting subset. Shared fingerprints capture equal subsets; partial overlaps between distinct compressed subsets remain an approximation. Equation (C.3) gives one success-probability draw for the original deadline H=L−d of pool a. The 512 aligned indices form a joint vector across anchors of a task. For factual-homogeneous state groups, each qa ℓ is pa ℓ after factual failure or 1− pa ℓ after factual success, and the particle average evaluates (7). A task already mixed across its factual trajectories can still have eligible homogeneous state groups. Moment-matched scalar Beta parameters are diagnostics rather than independent laws used by the budget solver. Only complete audited suffix groups fit the Branch prediction model; valid

15

rollouts. The remaining Root budget follows the same curve’s marginal gains, and no task-specific upper cap is supplied in the default configurations. Branch opening requires four new suffixes per anchor, capped by the available budget and worker capacity; its factual child is

retained separately. Historical state memory is bounded at 100,000 entries. Branch uses 512 aligned particles and an exact global budget dynamic program. Tie breaking derives from seed 17, the round, and stable pool identity; 17 is not the global training seed.

Appendix D. Actor Configuration and Training Procedure Algorithm 1 Dynamic curriculum learning and TSBPO 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33:

Require: actor πθ , fixed reference πref , memory M, budgets Broot ,Bbranch , optional balance flag and cap C. for each training iteration do Set πold ←πθ ; advance the round and decay historical evidence in M. // Dynamic curriculum and complete multi-turn rollout Assemble fresh and revisited task candidates; score each by integrated Root mixed-outcome probability and sample with exploration (4)–(5). Reserve two factual rollouts per selected task; allocate the remaining Root budget by predicted marginal gains (5). for each selected task x and its root quota nx do Sample nx complete factual trajectories using πold ; retain replayable occurrences. end for Retain factual-homogeneous state groups; group eligible occurrences by exact task/observation, choose one physical representative, and retain its original remaining deadline. Fit task-excluded Branch prediction model; condition once on current bare labels, scale historical and semantic evidence by learned reliability, and draw aligned task/cluster particles (6), (C.3). Solve state-group contrast budget (7)–(9); publish staged factual evidence to memory once. for each allocated occurrence h with kh ≥4 do Replay the physical prefix; retain the factual child and sample kh suffixes within H=L−dh . end for Audit physical suffix groups; use only complete allocated groups for likelihood fitting, and commit valid terminal labels once per visited state/depth pool, excluding replayed ancestors. // Physical tree credit and observation-state grouping Back up descendant-leaf terminal means Vterm (10) and step returns Vγ (13). Build sibling segments; center their scores to obtain Atraj (11)–(12). Assign deeper groups locally; use factual-root fallback only where no split is assignable. Group active turn occurrences by task/observation; compute Astep using (14). Set all segment coefficients wi ←1. If the optional plugin is enabled, project wi by (D.1), conserving parent-group mass. Compose Ai =wi Atraj,i +Astep,i ; keep both raw credits and the step coefficient unchanged. // Complete-turn policy update for each PPO optimizer minibatch do Count global active turns N across ranks; clear accumulated gradients. for each distributed microbatch do Sum token surrogates within turns (15); backpropagate with shared N and reference penalty (D.2), as specified by the total actor loss in Appendix D.2. end for Clip accumulated gradients and take one optimizer step on πθ . end for end for

Appendix B.4 proves existence of the bounded projection, gives a bisection bracket and the zero-mass convention, and confines the guarantee to scalar mass conservation. The plugin balances positive turn masses, not token counts. It changes only the trajectory coefficient in Abal i =wh,c Atraj (h,c)+Astep,i . The step term is unchanged. Equal scalar mass does not imply equal parameter-gradient norms. Appendix B.4 proves the bounded projection’s mass conservation.

D.1 Optional segment-mass weighting The core estimator uses unit segment coefficients. An optional segment-balance plugin changes how alreadycomputed trajectory credit is accumulated over unequallength siblings, without changing the return backup, sibling baseline, or raw advantages. Let mh,c = ∑i∈E(h,c) vi be a segment's effective turn mass, where vi is the existing active-sample weight and only positive-mass segments enter an active policy group. When enabled, the plugin targets the sibling mean m̄ h and computes:

D.2 Clipping, reference regularization, and local costs

m̄ h =(1/K)∑c mh,c ,wh,c =clip(λh m̄ h /mh,c ,1/C,C). (D.1) The positive scale λh is chosen by bounded projection so that ∑c mh,c wh,c = ∑c mh,c . We use C=6. Without active bounds, λh =1 and every sibling has mass m̄ h . Active bounds can leave unequal effective masses while preserving total mass. The coefficient changes only the trajectory term.

For token ratio ρ and detached advantage A, S=min(ρA,clip(ρ,1−ε,1+ε)A). The dual-clipped form is Sc =S for A≥0 and Sc =max(S,cA) for A<0, with ε=0.2 and c=3. A detached offset centers the displayed PG loss without changing its gradient.

16

Reference regularization uses a low-variance token penalty with a tangent linear tail. Let δ= logπref − logπθ , M=10, and δ*=log(1+M). The penalty is: exp(δ)−δ−1 for δ≤δ* kM (δ)= . (D.2) M−δ*+M(δ−δ*) for δ>δ* The minimized actor loss is − JPG + βN−1 ∑i,j kM ( δi,j ). The tangent tail retains a correcting derivative where a hard cap would saturate. This modified regularizer is distinct from exact reference KL and from the old-policy PPO update monitor. Entropy regularization is disabled in the ALFWorld configuration. A valid response has exactly one <think>...</think> block followed by one <action>...</action> block, with only whitespace outside them and no characters in the CJK range U+4E00–U+9FFF. The extracted command is lowercased, whitespace-normalized, and checked against current admissible actions; WebShop also accepts a nonempty search query when the page allows search. A formatting violation or inadmissible command incurs local cost one. The extracted command is still submitted to the environment, whose transition determines execution success. Missing action tags trigger the environment wrapper’s invalid-command fallback. Costs enter returns before centering; no separate truncation cost is used.

Table A6. Complete evaluation of the likelihood-fitted WebShop update-100 checkpoint: 500 goals, six stochastic episodes per goal, and the 1,000-product catalog. The interval resamples whole goal clusters 10,000 times. Metric Episode-level success rate (%) Empirical pass@6 (%) Valid actions (%) Horizon termination (%) Mean episode steps

Appendix E. Evaluation Diagnostics

Result 81.07 (2432/3000) 87.40 (437/500) 99.88 8.67 6.70

Figure A3. WebShop allocation histories and probability diagnostics. (a) Observed conversion fraction among selected factual-homogeneous observation groups with completed suffix evidence. (b) Newly mixed factual-homogeneous observation groups per update. Both runs use 96 factual roots, 128 new suffixes, and a PPO minibatch size of 240. Thin points are measurements and solid curves are centered nine-record means. (c-d) Root mixedoutcome and Branch terminal-contrast reliability for the fitted run only: five equal-count prediction bins versus subsequent observed group frequency. The dashed diagonal denotes perfect frequency agreement. Root uses 1,600 completed task groups; Branch uses 3,195 selected groups with completed suffix evidence. Brier scores use the same prediction-outcome pairs.

E.1 WebShop success and allocation diagnostics Complete WebShop evaluation yields 81.07% Episodelevel success rate (2432/3000). Empirical pass@6 is 87.40% (437/500 goals). These are the 500-goal, six-repeat results of the update-100 checkpoint, separate from the smaller online assessments. The evaluated WebShop run uses 96 factual roots and 128 added suffixes per update, with likelihood-fitted Root and Branch predictors and local-state-contrast allocation. The historical random-branch run uses the same SFT initialization, task pool, rollout budgets, reward and credit rules, PG aggregation, and reference coefficient 0.05; its branch states are selected randomly with four new suffixes per state. The evaluated lineage covers 156 updates, Figures A3(a) and A3(b) compare the first 100 updates. Figure 4(b) shows its full 156-update history; only the update-100 checkpoint supplies Table A6. The complete WebShop assessment records 99.88% valid actions (20,079/20,104 turns) and 0.015% output truncation (3 turns). Among 568 failed episodes, 256 reach the 15action horizon. Failures average 10.41 actions versus 5.84 for successes, locating residual difficulty in task completion as well as interaction execution. The new evaluator stores binary rewards and supplies no native partial-score measure.

Across updates 1-100, the fitted-allocation run converts an average of 17.00 previously factual-homogeneous observation groups per update, versus 8.03 for random branching; over updates 81-100 the means are 18.50 and 6.00 (Figure A3b). The corresponding per-update conversion fractions among selected factual-homogeneous groups with completed evidence average 53.16% for the fitted run and 27.68% for the random run (Figure A3a); candidate pools differ. Each task/observation key counts once per update. The random run has no completed 3,000episode assessment, so Table A6 reports only the fitted run. The stored per-group predictions allow a direct online reliability check (Figure A3c-d). Across the first 100 updates, Root predicts mixed outcomes for 1,600 completed task groups with mean probability 46.94%, versus 37.69% observed (Brier 0.2145). Branch predicts a terminal contrast for 3,195 selected observation groups with completed suffix evidence: 58.66% predicted versus 52.93% observed (Brier 0.2338). Five equal-count prediction bins show overprediction, particularly at high Root scores; these online,

17

selected-group diagnostics do not establish calibration on independent tasks or unselected candidates.

E.2 Complete evaluation and acquired comparisons Complete ALFWorld evaluation records 99.17% valid actions and 0.20% truncated turns overall. Unseen Pick is the lowest-success task family at 87.92% (Table 1). Table A7 separates greedy and stochastic outcomes by split; its task-bootstrap intervals resample tasks rather than training seeds. Table A7. Complete final-model evaluation. The two stochastic success intervals shown are task-cluster bootstrap intervals, not training-seed intervals. Action validity and truncation are turnlevel measurements. Metric Successful episodes Success (%) Successful episodes Success (%) Task-bootstrap 95% interval Valid actions (%) Truncated turns (%)

Decoder Greedy Greedy Stochastic Stochastic

Seen 136/140 97.14 1369/1400 97.79

Unseen 127/134 94.78 1295/1340 96.64

Stochastic

95.93–99.29

94.10–98.73

Stochastic Stochastic

99.29 0.22

99.07 0.19

Figure A4. Pre-branch predictions and realized suffix contrasts. Top: the 175-update ALFWorld history; bottom: the evaluated WebShop run through update 100. Left: predicted oppositeoutcome probabilities averaged over eligible candidate or selected representatives. Right: percentages of new suffixes with an opposite terminal label, including those whose first command and next observation match the factual continuation. Thin traces and points are measured updates; solid curves are centered nine-record means. Suffix rates divide by the number of completed newly generated suffixes per update.

Selected branch representatives have higher predicted opposite-outcome probabilities than eligible candidates: 47.32% versus 25.93% over 175 ALFWorld updates, and 30.51% versus 18.54% over the first 100 WebShop updates. Among new suffixes, 34.50% and 28.38% end with the label opposite to their factual continuation. These are different statistical units from task success or physicalsibling advantages. For the selected WebShop groups with completed evidence, Root predicts 46.94% versus 37.69% observed mixed outcomes and Branch predicts 58.66% versus 52.93% observed contrasts; prediction is thus overoptimistic in this online diagnostic, especially for high Root scores. Candidate and selected prediction means cover different representative populations, whereas realized suffix rates cover completed continuations; these pairs do not measure probability calibration. In 13.16% of ALFWorld and 14.43% of WebShop suffixes, the first command and next observation match the factual continuation but the terminal label differs. For WebShop, Figure A3 instead pairs each selected group's advance prediction with its later outcome and reports online reliability diagnostics. Task-level acquisition, suffix outcomes, and the physical sibling advantages in Section 5 remain distinct statistical units.

Table A8. Pre-branch predictions and suffix contrasts. Entries are unweighted means over 175 ALFWorld and 100 WebShop update records. Candidate and selected scores average eligible and awarded task/observation representatives, respectively. Realized rates use completed new suffixes as their denominator; the last row additionally requires the first command and next observation to match the factual continuation. Diagnostic ALFWorld / WebShop Candidate predicted contrast (%) 25.93 / 18.54 Selected predicted contrast (%) 47.32 / 30.51 New suffix terminal contrasts (%) 34.50 / 28.38 Same-first-transition contrasts (%) 13.16 / 14.43

Over the first 100 WebShop updates, the fitted-allocation configuration converts 17.00 previously factualhomogeneous observation groups per update versus 8.03 under historical random branching; selected-group conversion fractions are 53.16% versus 27.68%. Both use the same SFT initialization and rollout budgets. This comparison describes two training configurations (Appendix E.1).

Appendix F. Observation-Group Density Over the first 100 actor updates, ALFWorld observationgroup density averages 0.424 under the default TSBPO configuration and 0.321 in our GiGPO reference run, a ratio of 1.32 (Table A9; Figure A5). These histories describe the comparison density available to the step baseline; the GiGPO run is separate from the published benchmark values in Table 1. For update r, let Gᵣ be the task/observation groups produced by the grouping call, including singletons. The numerator m̄ ᵣ averages their occurrence counts with equal group weights. The valid-turn denominator vᵣ is the update’s mean generated interaction length ℓ̄ᵣ multiplied by its factual

18

valid-action fraction fᵣ. The reported statistic is the perupdate ratio dᵣ, averaged equally over R=100 updates: m̄ r =|Gr |−1 ∑g∈Gr |g|,vr =ℓ̄r fr , (F.1) dr =m̄ r /vr ,d̄ =R−1 ∑Rr=1 dr . Each included update has one grouping call; Table A9 gives the mean and temporal SD of dᵣ. Repeated visits contribute occurrences and need not be independent trajectories. Our GiGPO reference uses the environmentspecific Qwen2.5-1.5B SFT initialization, 16 tasks with eight factual trajectories each (128 roots), no branches, mean-centered GiGPO credit, actor learning rate 3×10⁻⁶, PPO minibatches of 128, and a 50-action horizon. The ratio describes the two histories and is neither an effective sample size nor a gradient-variance estimate. Table A9. Observation-group density over the first 100 updates of each run. Means and temporal SDs use the per-update definition in Appendix F; singleton groups are included. Diagnostic Mean group size / valid turns Across-record SD Training updates Relative to GiGPO mean

GiGPO / TSBPO 0.321 / 0.424 0.088 / 0.092 100 / 100 1.00× / 1.32×

Figure A5. Observation-group density over the first 100 actor updates of each run. Panel (a) shows the per-update ratios defined in Appendix F, with continuous centered seven-record means; panel (b) shows their unweighted means. Each update contains one grouping call. Thin traces and filled markers show measurements. The denominator estimates valid turns per trajectory, rather than the total number of valid turns in a batch.

19

Related documents

• EXPO-FT: Sample-Efficient Reinforcement Learning Finetuning for Vision-Language-Action Models#630018
• EXPO-FT: Sample-Efficient Reinforcement Learning Finetuning for Vision-Language-Action Models#628156
• NLPG: Natural-Language Policy Gradients for Self-Evolving Language Agents#1118091
• T2SPO: Trajectory-to-Step Policy Optimization for Agentic Reinforcement Learning#1155323
• RPS: Information Elicitation with Reinforcement Prompt Selection#14045