Paper deep dive
RTPO: Reverse-Turn Policy Optimization for Stabilizing Agentic RL Training
Yugu Li, Jimmy Cao, Jianglin Qiao, Siyi Hu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/20/2026, 4:54:29 AM
Summary
The paper introduces Reverse-Turn Policy Optimization (RTPO), a framework designed to stabilize reinforcement learning (RL) training for multi-turn agentic workflows. It identifies three sources of instability in existing methods: rollout-training context mismatch, weak turn-level credit assignment, and asynchronous policy drift. RTPO addresses these by organizing rollouts as sparse reverse trees and performing policy updates in temporal reverse order, ensuring causally consistent credit assignment and on-policy continuation. Theoretical guarantees and experiments demonstrate that RTPO outperforms baselines like GRPO and TreeGRPO by significant margins.
Entities (11)
Relation Signals (7)
RTPO → addresses → Credit Assignment
confidence 95% · RTPO enables causally consistent turn-level credit assignment
RTPO → addresses → Policy Drift
confidence 95% · RTPO... on-policy continuation to control asynchronous drift
RTPO → addresses → context mismatch
confidence 95% · RTPO eliminates context mismatch... under the proposed turn-level formulation
RTPO → uses → Sparse Reverse Trees
confidence 95% · RTPO, which organizes multi-turn rollouts as sparse reverse trees
RTPO → outperforms → GRPO
confidence 90% · RTPO improves upon trajectory- and turn-level baselines by 21.50% and 10.76%, respectively
RTPO → outperforms → TreeGRPO
confidence 90% · RTPO improves upon trajectory- and turn-level baselines by 21.50% and 10.76%, respectively
Reinforcement Learning → enables → Large Language Models
confidence 85% · Training multi-turn agentic workflows with reinforcement learning (RL) enables large language models to perform complex reasoning
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Training multi-turn agentic workflows with reinforcement learning (RL) enables large language models to perform complex reasoning, use external tools, and conduct iterative search beyond single-turn settings. Yet multi-turn RL training remains highly unstable, often causing severe performance degradation as the number of turns increases. Through theoretical analysis, we identify three tightly coupled sources of instability: rollout-training context mismatch, weak turn-level credit assignment under sparse terminal rewards, and asynchronous policy drift when short and long trajectories are optimized under different policy versions. We show that these issues share a common structural origin in flattened trajectory optimization and address them through a unified reverse-turn formulation. We propose Reverse-Turn Policy Optimization (RTPO), which organizes multi-turn rollouts as sparse reverse trees and performs turn-level policy updates in temporal reverse order, aligning each decision with its downstream continuation. RTPO enables causally consistent turn-level credit assignment and on-policy continuation to control asynchronous drift. We provide theoretical guarantees showing that RTPO eliminates context mismatch and asynchronous drift under the proposed turn-level formulation, reduces credit bias, and converges to recursive optimality. Experiments on multi-turn agentic RL benchmarks show that RTPO improves upon trajectory- and turn-level baselines by 21.50% and 10.76%, respectively, highlighting its potential to support more stable training for tool-using agents.
Tags
Links
- Source: https://arxiv.org/abs/2608.18682v1
- Canonical: https://arxiv.org/abs/2608.18682v1
Trouble viewing inline? Open PDF directly →
Full Text
191,071 characters extracted from source content.
Expand or collapse full text
RTPO: Reverse-Turn Policy Optimization for Stabilizing Agentic RL Training Yugu Li Affiliation: School of CSIT Affiliation: Adelaide University Affiliation: Adelaide, SA 5000, Australia Email: yugu.li@adelaide.edu.au Jimmy Cao Affiliation: School of CSIT Affiliation: Adelaide University Affiliation: Adelaide, SA 5000, Australia Email: jimmy.cao@adelaide.edu.au Jianglin Qiao Affiliation: ACFR Affiliation: The University of Sydney Affiliation: Camperdown, NSW 2050, Australia Email: jianglin.qiao@sydney.edu.au Siyi Hu Affiliation: School of EECMS Affiliation: Curtin University Affiliation: Bentley, WA 6102, Australia Email: siyi.hu@curtin.edu.au Abstract Training multi-turn agentic workflows with reinforcement learning (RL) enables large language models to perform complex reasoning, use external tools, and conduct iterative search beyond single-turn settings. Yet multi-turn RL training remains highly unstable, often causing severe performance degradation as the number of turns increases. Through theoretical analysis, we identify three tightly coupled sources of instability: rollout–training context mismatch, weak turn-level credit assignment under sparse terminal rewards, and asynchronous policy drift when short and long trajectories are optimized under different policy versions. We show that these issues share a common structural origin in flattened trajectory optimization and address them through a unified reverse-turn formulation. We propose Reverse-Turn Policy Optimization (RTPO), which organizes multi-turn rollouts as sparse reverse trees and performs turn-level policy updates in temporal reverse order, aligning each decision with its downstream continuation. RTPO enables causally consistent turn-level credit assignment and on-policy continuation to control asynchronous drift. We provide theoretical guarantees showing that RTPO eliminates context mismatch and asynchronous drift under the proposed turn-level formulation, reduces credit bias, and converges to recursive optimality. Experiments on multi-turn agentic RL benchmarks show that RTPO improves upon trajectory- and turn-level baselines by 21.50% and 10.76%, respectively, highlighting its potential to support more stable training for tool-using agents. 1 Introduction Reinforcement learning (RL) has become a central paradigm for post-training large language models (LLMs), especially when supervision comes from final outcome rewards rather than dense token-level labels. Through outcome-based optimization, RL encourages behaviors such as planning, self-reflection, and verification, achieving strong results in single-turn mathematical reasoning (42; 59; 15; 27) and code generation (25; 45; 49). Motivated by these advances, recent work extends RL to multi-turn agentic workflows, especially Tool-Integrated Reasoning (TIR) (62; 14; 44; 9; 7; 30), where agents iteratively reason, call tools, receive feedback, and refine their behavior across turns. Despite this promise, RL training for multi-turn workflows remains unstable: models that improve on short workflows often degrade as the number of turns increases. This degradation is not merely due to longer sequences; it is amplified by temporal dependencies across turns, where each decision reshapes the context, environment state, and future decision distribution. Existing methods partially mitigate this issue but provide limited analysis of its causes. Trajectory-level methods such as PPO (41), GRPO (42), and GSPO (67) retain the flattened trajectory paradigm. Turn-decomposition methods such as SeeUPO (20) improve update granularity but still condition on flattened histories. Tree-based methods such as TreeGRPO (22) and ARPO (13) use shared prefixes or branching rollouts, but their advantage estimates are not fully aligned with each turn’s causal contribution to downstream continuation. Overall, the sources of instability remain underexplored at the training-pipeline level, and existing methods (see Appendix A for details) do not jointly address their shared origin. In this paper, we provide a theoretical analysis that identifies three coupled sources of instability: context mismatch between rollout and training, which breaks consistency between generated and optimized turn-level contexts; weak turn-level credit assignment, where sparse terminal rewards obscure the contribution of individual decisions; and asynchronous policy drift, where short and long trajectories are optimized under different versions of an evolving policy. Although these issues arise from different components of the training pipeline, we show that they share a common structural origin. We illustrate these sources in Figure 1 and analyze them formally in Sec. 2. Core Challenge. Motivated by our theoretical analysis, we ask: How can we improve multi-turn agentic RL performance by stabilizing turn-wise training with rollout–training consistency, turn-level credit assignment, and controlled asynchronous policy drift? To address this challenge, we propose Reverse-Turn Policy Optimization (RTPO), a policy optimization framework for stabilizing multi-turn agentic RL training, with theoretical details provided in Sec. 3. The key idea is to formalize sampled interactions as sparse trees and optimize turn-level policies in temporal reverse order, propagating continuation values from later turns to earlier ones through the reverse optimality guarantee. By constructing sibling continuations for each turn, RTPO estimates turn-level advantages under matched downstream conditions. This removes context inconsistency induced by flattened trajectory optimization, reduces turn-level credit bias through causal action alignment, and controls asynchronous policy drift through on-policy continuation. Our contributions are fourfold: (i) We identify coupled sources of instability in multi-turn agentic RL: context mismatch, weak turn-level credit, and asynchronous policy drift. (i) We provide a theoretical analysis showing that these sources share a common structural origin in flattened trajectory optimization. (i) We propose RTPO, a reverse-turn policy optimization framework with sparse reverse trees, turn-level on-policy updates, and theoretical guarantees on recursive optimality, context consistency, and reduced credit bias. (iv) We validate RTPO on multi-turn agentic RL benchmarks, where it outperforms strong baselines, including GRPO, TreeGRPO, ARPO, and SeeUPO, while further stabilizing the training pipeline. Figure 1: The identified training instability in multi-turn agentic RL arises from: (A) rollout–training context mismatch, (B) trajectory-only credit assignment, and (C) long-horizon policy drift. 2 Theoretical Analysis: Training Instability We argue that the instability of multi-turn RL training stems from rollout–training mismatch: rollouts are typically generated under truncated or summarized contexts, while training recomputes likelihood ratios under concatenated full-history contexts. This discrepancy biases policy optimization and worsens over long horizons. Moreover, the flattened full-history formulation provides only trajectory-level credit, causing terminal rewards to obscure individual turns. When trajectories are generated asynchronously, this mismatch further induces policy drift, as long trajectories generated under an older policy may be optimized after the policy has already been updated by shorter trajectories. Building on these observations and insights, we model a multi-turn interaction as a hierarchical Markov decision process (H-MDP) (16). Given an initial prompt q, turn k consists of a model response lkl_k and environment feedback fkf_k, producing the trajectory (q,l0,f0,…,ln−1,fn−1)(q,l_0,f_0,…,l_n-1,f_n-1). The turn-level state is Sk=(q,l0,f0,…,lk−1,fk−1)S_k=(q,l_0,f_0,…,l_k-1,f_k-1), and the turn-level action is the response lkl_k. Each response is generated autoregressively as lk=(ak,1,…,ak,Tk)l_k=(a_k,1,…,a_k,T_k), where the token-level state is sk,t=(Sk,ak,<t)s_k,t=(S_k,a_k,<t). Existing PPO- and GRPO-style methods (42; 67; 65; 64) typically flatten the full interaction into a single token sequence and optimize the resulting trajectory as follows: Jflat(θ)=[1G∑i=1G1∑tmi,t∑tmi,tmin(ρi,tAi,clip(ρi,t,1−ϵ,1+ϵ)Ai)],J^flat(θ)=E [ 1G _i=1^G 1 _tm_i,t _tm_i,t \! ( _i,tA_i,clip( _i,t,1-ε,1+ε)A_i ) ], (1) where ρi,t=πθ(ai,t∣xi,<t)/πθold(ai,t∣xi,<t) _i,t= _θ(a_i,t x_i,<t)/ _ _old(a_i,t x_i,<t) is the token-level importance-sampling (IS) ratio and AiA_i is a trajectory-level advantage assigned uniformly to all unmasked tokens in trajectory gig_i (gig_i belongs to a group of G trajectories). Full preliminaries are provided in Appendix B. 2.1 Rollout–Training Mismatch As illustrated in Figure 1-A, in multi-turn interactions, rollouts are often generated under a truncated or summarized context ϕ(x¯k)φ( x_k), while training recomputes token probabilities under the full flattened history x¯k x_k. Thus, the IS ratio used in training differs from the true IS ratio induced by the rollout distribution: ρk,tflat=πθ(ak,t∣x¯k)πθold(ak,t∣ϕ(x¯k))≠πθ(ak,t∣ϕ(x¯k))πθold(ak,t∣ϕ(x¯k))=ρk,ttrue. _k,t^flat= _θ(a_k,t x_k) _ _old(a_k,t φ( x_k))≠ _θ(a_k,t φ( x_k)) _ _old(a_k,t φ( x_k))= _k,t^true. (2) Because the denominator in ρk,tflat _k,t^flat does not match the distribution that actually sampled the token, the resulting policy-gradient estimate is biased. This mismatch becomes more severe in later turns as the omitted history grows. Moreover, when ϕφ is non-injective, distinct full-history states can collapse into the same truncated observation, inducing state aliasing and restricting optimization to an observation-induced policy class whose optimum may be strictly below the full-history optimum. See Appendix B.1 for the full theoretical analysis of rollout–training mismatch. 2.2 Trajectory-Only Credit Assignment Flattened training assigns a single trajectory-level advantage to all turns, even though different turns may contribute unequally to the final outcome, as shown in Figure 1-B. For trajectory gig_i, the population trajectory advantage can be decomposed at turn k as Ri−[R]=Ri−Qπ(Si,k,li,k)⏟downstream stochasticity+Aπ(Si,k,li,k)⏟true turn advantage+Vπ(Si,k)−μR⏟upstream state effect.R_i-E[R]= R_i-Q^π(S_i,k,l_i,k)_downstream stochasticity+ A^π(S_i,k,l_i,k)_true turn advantage+ V^π(S_i,k)- _R_upstream state effect. (3) Here, RiR_i denotes the final return of trajectory gig_i, Qπ(Si,k,li,k)=[R∣Si,k,li,k]Q^π(S_i,k,l_i,k)=E[R S_i,k,l_i,k], Vπ(Si,k)=[R∣Si,k]V^π(S_i,k)=E[R S_i,k], and μR=[R] _R=E[R]. This decomposition shows that the true turn-level advantage is only one component of the trajectory-level signal. When upstream state effects or downstream stochasticity dominate, the sign of the trajectory advantage may disagree with the true turn-level advantage, leading to incorrect or even reversed policy updates. Similarly, group-relative baselines provide valid local comparisons only when trajectories share the same turn-level state. Under cross-state grouping, the advantage estimator incurs additional bias Biascross=G−1G(Vπ(Si,k)−μR)Bias_cross= G-1G (V^π(S_i,k)- _R ), determined by the upstream trajectory without causal connection to the current action. See Appendix B.2 for the full theoretical analysis of trajectory-only credit assignment issues. 2.3 Long-Horizon Policy Drift In asynchronous training with parallel sampled trajectories (see Figure 1-C), shorter trajectories may complete and update the policy while longer trajectories are still being generated under an older policy. When these longer trajectories are later optimized, they become off-policy with respect to the current model. The unbiased correction would require the full-trajectory importance weight ωi=∏t=1Tiρi,t _i= _t=1^T_i _i,t. However, the PPO or GRPO method applies clipping independently at the token level, so the resulting correction differs from the true full-trajectory IS ratio: ∏t=1Ticlip(ρi,t,1−ϵ,1+ϵ)≠∏t=1Tiρi,t=ωi. _t=1^T_iclip( _i,t,1-ε,1+ε)≠ _t=1^T_i _i,t= _i. (4) Therefore, token-level clipping cannot faithfully correct long-horizon policy drift. The discrepancy compounds with trajectory length, while using the exact full-trajectory ratio is impractical because its variance grows rapidly with TiT_i. This explains why standard PPO- or GRPO-style training methods can become unstable or even collapse in long-horizon agentic RL. The full theoretical analysis of long-horizon policy drift is provided in Appendix B.3. 3 Method: Reverse-Turn Policy Optimization (RTPO) To address the training instability revealed by our theoretical analysis in Sec. 2, we propose Reverse-Turn Policy Optimization (RTPO) with theoretical guarantees for stabilizing agentic RL training, as shown in Figure 2. RTPO first models multi-turn interaction as a turn-boundary MDP and defines an independent sub-policy optimization objective for each turn (Sec. 3.1). This formulation enables reverse-order training to mitigate the mismatch between rollout and training contexts. RTPO then develops sparse tree rollouts based on maximum-value decomposition (Sec. 3.2) to estimate true turn-level advantages, enabling causally consistent turn-level credit assignment for the case of cross-trajectory comparison without state bias. Finally, RTPO designs an on-policy continuation mechanism (Sec. 3.3) that eliminates the need for downstream IS-ratio correction under PPO clipping, thereby addressing policy drift induced by asynchronous turns. Figure 2: Overview of RTPO in agentic RL training. After rollout, RTPO performs reverse-order turn-level policy optimization for each trajectory in the batch. Starting from the final turn k, the rollout (old) policy πold _old generates G−1G-1 sibling rollouts from the same turn boundary to estimate a group advantage and update the training (turn-level) policy to πk _k. The procedure then proceeds backward through turns k−1,k−2,…,0k-1,k-2,…,0, where each updated turn policy as πk−1,πk−2,…,π0 _k-1, _k-2,…, _0. To generate state-matched siblings for turn-level credit assignment, we design a sparse tree structure that assigns group-relative advantages to individual sibling rollouts at each turn and propagates optimization backward across the trajectory. Finally, RTPO applies on-policy continuation to coordinate asynchronous short- and long-trajectory updates from πk _k to π0 _0, reducing policy drift. 3.1 Turn-Level Policy Optimization Turn-boundary MDP for rollout-training match. We model a K-turn agent episode as a turn-boundary MDP ℳ=⟨¯,H,PH,RH,γH⟩M= X,A_H,P_H,R_H, _H , where the augmented state x¯k=(Sk,k) x_k=(S_k,k) encodes the interaction history SkS_k and the turn index k. At the turn-k boundary, the agent selects a macro-action uk≡lk∈H,k(Sk)u_k≡ l_k _H,k(S_k), corresponding to the complete turn-k response lk=(ak,1,…,ak,Tk)l_k=(a_k,1,…,a_k,T_k). Executing uku_k consumes τk=Tk _k=T_k token steps, after which the environment returns to the external tool feedback fkf_k, and the interaction history is updated as Sk+1=Sk∘(lk,fk)S_k+1=S_k (l_k,f_k). To define the conditioning context received by the model at turn k, we let ck=ψ(Sk)c_k=ψ(S_k), where ψ can be the identity map, a truncation operator, or a summarization operator. The turn-level policy is factorized as πθ=(πθ,0,…,πθ,K−1) _θ=( _θ,0,…, _θ,K-1), where each sub-policy is autoregressive at the token level: πθ,k(uk|ck)=∏t=1Tkπθ(ak,t|ck,ak,<t) _θ,k(u_k|c_k)= _t=1^T_k _θ(a_k,t|c_k,a_k,<t). This turn-boundary MDP decomposition factorizes the episode policy into K turn-level sub-policies, with each sub-policy mapping the conditioning context ck=ψ(Sk)c_k=ψ(S_k) to a complete response lkl_k. Here, ckc_k is kept identical between rollout and training. During rollout, RTPO records the exact context ckc_k received by the model, including any truncation or summarization, together with the corresponding old-policy log-probabilities. During training, the same ckc_k is used as input, and the loss is computed only over the output tokens in lkl_k. Hence, the denominator of the IS ratio is evaluated under the same conditioning context as in rollout: ρk,tRTPO=πθ(ak,t|ck,ak,<t)πθold(ak,t|ck,ak,<t) _k,t^RTPO= _θ(a_k,t|c_k,a_k,<t) _ _old(a_k,t|c_k,a_k,<t) (5) Per-turn policy optimization under reverse-order training. Training proceeds in reverse order through the turns k=K−1,K−2,…,0k=K-1,K-2,…,0. After turn k is completed, πθ,k _θ,k is frozen (e.g., subsequent turns produce no gradients for turn-k tokens). This reverse ordering ensures that when turn k is trained, the downstream policies in each turn πθ,k+1:K−1 _θ,k+1:K-1 have been optimized and fixed. During reverse-order training for turn-k, the environment is forked from the trunk trajectory’s boundary state SkS_k to generate G−1G-1 sibling rollouts in the sparse tree. Each sibling rollout j receives a turn-level advantage Aj,kHA_j,k^H (the details of sibling rollout generation are provided in Sec. 3.2). The policy optimization objective for turn k is then defined as: Jk(θ)=1G−1∑j=1G−11Tj,k∑t=1Tj,kmin(ρj,k,tAj,kH,clip(ρj,k,t, 1−ϵ, 1+ϵ)Aj,kH)J_k(θ)= 1G-1 _j=1^G-1 1T_j,k _t=1^T_j,k \! ( _j,k,t\,A_j,k^H,\;clip ( _j,k,t,\,1-ε,\,1+ε )\,A_j,k^H ) (6) where ρj,k,t=πθ(aj,k,t|ck,aj,k,<t)/πθold(aj,k,t|ck,aj,k,<t) _j,k,t= _θ(a_j,k,t|c_k,a_j,k,<t)/ _ _old(a_j,k,t|c_k,a_j,k,<t) is the token IS ratio and Tj,kT_j,k is the number of tokens generated by sibling rollout j at turn k. Only these G−1G-1 sibling rollouts are used for gradient updates; the trunk trajectory is excluded. In Theorem 1, we show that RTPO has local and global convergence guarantees through reverse-order turn-level policy optimization. Theorem 1: Convergence to Recursive Optimality Under standard assumptions, finite state and macro-action spaces, Robbins–Monro step sizes, sufficient per-turn exploration, frozen downstream policies, and bounded rewards, reverse-order turn-level optimization satisfies: (a) Per-turn convergence. For each turn k, fixing downstream policies reduces optimization to single-step Q-learning with a stationary continuation target; hence, per-turn policy πk _k converges under the stated assumptions. (b) Recursive optimality. Under reverse-order training, applying the above argument recursively from turn K−1K-1 to turn 00 yields a sequence of per-turn policies that is recursively optimal. (c) Global optimality. If the turn-level macro-action spaces are complete, i.e., the per-turn policy class can represent any globally feasible trajectory-level policy, then recursive optimality is equivalent to global optimality over the full trajectory. The proof of Theorem 1 is provided in Appendix C.2. 3.2 Turn-Level Credit Assignment Turn-level advantage function. We construct sparse tree rollouts at turn-level boundaries, elevating the advantage granularity from trajectory-only reward to turn-level credit while ensuring that all compared rollouts share the same state and are free from state bias. In turn k, G−1G-1 siblings independently generate turn-k responses from the shared boundary state SkS_k and continue to the terminal. The turn-level advantage function for sibling j is: Aj,kH=Q^j,k−V^kA^H_j,k= Q_j,k- V_k. Here, all siblings share the same state SkS_k, so advantage differences can only arise from two sources: different action choices at turn k and independent downstream sampling noise. The downstream noise has zero mean ([ξdown|Sk,lj,k]=0E[ _down|S_k,l_j,k]=0) and introduces no systematic bias; the upstream state term ξup=Vπ(Sk)−V¯ _up=V^π(S_k)- V from Eq. (3) is exactly zero, because all siblings share SkS_k. Furthermore, Aj,kHA^H_j,k is assigned only to the output tokens of turn k; the shared prefix SkS_k serves as the prompt input but does not enter the loss, so each token appears exactly once in the training batch. Turn-level value estimation. To identify turn-level values, we separate the local reward at each turn from the downstream completion value over the full trajectory. Based on the MAXQ principle (12), we define the following action-value decomposition for turn k: Q~kπ(Sk,uk)=rk+γτkFkπ(Sk+1) Q_k^π(S_k,u_k)=r_k+γ _kF_k^π(S_k+1). rkr_k is the immediate reward at turn k (rk=0r_k=0 for k<K−1k<K-1 under sparse rewards), and Fkπ(Sk+1)F_k^π(S_k+1) is the downstream continuation value representing the expected cumulative return from turn k+1k+1 onward under policy π, with base case FK−1π≡0F_K-1^π≡ 0. Then, the terminal reward RjR_j obtained by sibling j rolling out the policy from SkS_k to the terminal is a single Monte Carlo sample of the above: Q^j,k=Rj=rj,k+γτkF^j,k Q_j,k=R_j=r_j,k+γ _k F_j,k (7) where F^j,k F_j,k is a single sample of Fkπ(Sk+1)F_k^π(S_k+1). RjR_j is an unbiased estimator of Q~kπ Q_k^π. Note that the value estimation quality of Q^j,k Q_j,k depends on F^j,k F_j,k, i.e., the quality of the sampled downstream continuation value. If the downstream policy is not yet optimized, even a strong turn-k action may still produce Rj=0R_j=0 due to downstream errors, thereby contaminating the turn-level advantage with downstream noise. The case where F^j,k F_j,k is generated by an already optimized downstream policy is addressed in Sec. 3.3. After estimating the action values at each turn, we compute a state-specific value baseline from the sibling rollouts. Specifically, we define V^k V_k as the mean of the estimated Q-values across the G−1G-1 siblings: V^k=1G−1∑j=1G−1Rj V_k= 1G-1 _j=1^G-1R_j. In Theorem 2, we show that RTPO obtains accurate turn-level credit without bias from upstream and downstream effects. Theorem 2: Causally Consistent Turn-Level Advantage Estimation Consider turn k and suppose that the G−1G-1 sibling rollouts are forked from the same boundary state SkS_k, with each sibling rollout j∈1,…,G−1j∈\1,…,G-1\ independently sampling a turn-k macro-action uj,k≡lj,ku_j,k≡ l_j,k. Let Aj,kHA^H_j,k denote the turn-level advantage assigned to sibling rollout j. Then, under bounded rewards and independent sibling sampling, the turn-level advantage estimator satisfies the following properties: (a) Local unbiasedness up to finite-group bias. Conditional on SkS_k, the expectation of Aj,kHA^H_j,k is proportional to the true turn-level advantage, up to a finite-group bias of order O(1/G)O(1/G). Because all comparisons are made from the same boundary state, the estimator removes the upstream state-contamination term that appears in cross-trajectory comparisons. (b) Reduced value estimation error. The mean squared error of Aj,kHA^H_j,k is lower than that of trajectory advantage estimation whenever cross-state value variance is non-zero. The improvement gap is governed by the variance of values across different boundary states, which can be large in long-horizon, multi-turn tasks. (c) State-matched causal actions. Since all siblings share the same boundary state SkS_k, differences in their returns are causally attributable to the sampled turn-k macro-actions uj,ku_j,k, rather than to upstream trajectory differences. The resulting advantage is assigned only to turn-k output tokens, excluding prefix tokens from the gradient. The proof of Theorem 2 is provided in Appendix C.3. 3.3 On-Policy Continuation On-policy evolution. Asynchronous turn updates can induce policy drift that is not fully corrected by per-token IS clipping. In principle, one could correct this drift using the full trajectory-level IS product, but its variance grows exponentially with the horizon length, making it unstable for long-horizon multi-turn training. This drift directly affects the downstream continuation value FkF_k introduced in Sec. 3.2: under a stale or mismatched downstream policy, F^j,k F_j,k can systematically deviate from the true continuation value Fkπθ>kF_k _ _>k, while existing IS-based corrections are insufficient to remove this deviation. To avoid this issue, RTPO re-generates sibling continuations on-policy at each turn. Let θ0 _0 denote the parameters at the start of the policy evolution. During reverse-order training, the parameters are updated sequentially across turns. By the time optimization reaches turn k, the policies for downstream turns K−1,…,k+1K-1,…,k+1 have already been updated; we denote the resulting current parameters by θ>k _>k. Thus, under πθ>k _ _>k, the downstream turns k+1,…,K−1k+1,…,K-1 use the optimized continuation policy, whereas turn k and all upstream turns remain to be optimized. Note that the trunk is a complete trajectory generated at the start of the policy evolution using πθ0 _ _0. It does not participate in gradient updates, nor does it enter the computation of V^k V_k. Its sole role is to provide boundary states SkS_k and environment snapshots snapksnap_k as anchoring points for sibling forking. The trunk’s policy nature affects which states SkS_k are visited during training (state coverage), but does not affect the correctness of advantage estimation, since all siblings contributing to the estimate are generated on-policy. On-policy sibling generation. At the start of turn k, RTPO synchronizes the latest parameters θ>k _>k to the inference engine, forks the environment from snapksnap_k, and generates G−1G-1 siblings using πθ>k _ _>k. Each sibling rollout j generates a turn-k response, then continues with πθ>k _ _>k through turns k+1k+1 to K−1K-1, obtaining terminal reward RjR_j. Since the sampling policy equals the current policy, the trajectory-level IS weight is identically one: ωj=∏h=k+1K−1∏t=1Tj,hπθ>k(aj,h,t∣sj,h,t)πθ>k(aj,h,t∣sj,h,t)≡1. _j= _h=k+1^K-1 _t=1^T_j,h _ _>k(a_j,h,t s_j,h,t) _ _>k(a_j,h,t s_j,h,t)≡ 1. Since turn-level value estimation is Q^j,k=rj,k+γτkF^j,k Q_j,k=r_j,k+γ _k F_j,k from Sec. 3.2, the sibling’s downstream continuation is performed under the current policy πθ>k _ _>k, the sample F^j,k F_j,k is an unbiased draw from Fkπθ>k(Sj,k+1)F_k _ _>k(S_j,k+1). Therefore: Q^j,k=rj,k+γτkF^j,kπθ>k Q_j,k=r_j,k+γ _k F_j,k _ _>k (8) is an unbiased Monte Carlo estimate of Q~kπθ>k(Sk,uj,k) Q_k _ _>k(S_k,u_j,k). The entire value estimate requires no IS correction, is unaffected by clip truncation, and is free of multiplicative variance explosion. In Theorem 3, we show that RTPO conducts on-policy continuation to avoid policy drift and further reduces advantage-estimation errors. Theorem 3: On-Policy Continuation under Asynchronous Turns In the reverse-order training procedure of RTPO, at the start of each asynchronous turn k, sibling rollouts j∈1,…,G−1j∈\1,…,G-1\ are generated from the shared boundary state SkS_k using the current downstream policy πθ>k _ _>k and are then continued to termination under the same policy. Then the following two properties hold: (a) Drift-free on-policy continuation. Each sibling’s terminal return RjR_j provides an unbiased Monte Carlo estimate of the turn-level Q-value under the current downstream policy πθ>k _ _>k. Because the sampling policy and the evaluation policy coincide throughout the sibling continuation, the trajectory-level importance-sampling weight ωj _j is identically one, and no trajectory-level IS correction is required. (b) Dynamic error reduction in advantage estimation. As reverse-order training improves the downstream policies, the continuation value estimates F^j,kπθ>k F_j,k _ _>k become aligned with the current optimized downstream policy rather than a stale policy. Under bounded binary or normalized rewards, when the induced success probabilities move away from the high-uncertainty region around one-half, the variance of the Monte Carlo Q-value estimator decreases, thereby improving the signal-to-noise ratio of the resulting turn-level advantage estimates Aj,kHA^H_j,k. The proof of Theorem 3 is provided in Appendix C.4. 4 Experimental Results and Analysis Experimental Setting. We use Qwen3-8B (58) as the backbone for the main experiments on RTPO and all baselines, enabling Qwen3’s thinking mode for all multi-turn agentic RL rollouts. We compare RTPO with trajectory-level methods, including GRPO (42), and turn/tree-level credit methods, including ARPO (13), TreeGRPO (22), and SeeUPO (20). We consider 12 experiments covering comprehensive mathematical and knowledge reasoning benchmarks, where agents perform multi-turn RL training with external calculation and web-search tools. All methods are implemented in VeRL (43), with vLLM (24) for rollout generation and FSDP (66) for distributed training. We evaluate training performance and stability using task accuracy, tool-call statistics, log-probability comparisons, turn-level credit effects, and the hit rates of on-policy versus off-policy outputs. Detailed experimental setup, including base models, baselines, datasets, configurations, and evaluation metrics, is provided in Appendix D. Implementation details, including pseudocode, source code, training details, and the Qwen3 chat template, are provided in Appendix E. 4.1 Main Results We compare RTPO against the trajectory-level method GRPO and the turn-level method SeeUPO, and additionally include the untuned vanilla model as a non-RL reference. Table 1 reports both accuracy and the corresponding number of tool calls on each benchmark. We evaluate overall performance on mathematical reasoning and knowledge-intensive question answering across three difficulty tiers: easy (GSM8K), medium (AMC23, MATH500), and hard (AIME24, AIME25, OE-Math, HotpotQA, and 2Wiki). Our RTPO achieves the best performance across all eight benchmarks, improving overall accuracy over vanilla by 66.78%, outperforming GRPO (+21.50%) and SeeUPO (+10.76%). Further discussion and insights on tool calls are provided in Appendix F.1. Method M: Mathematical Reasoning K: Knowledge Reasoning Overall AIME24 AIME25 AMC23 MATH500 GSM8K OE-Math HotpotQA 2Wiki Acc Calls Acc Calls Acc Calls Acc Calls Acc Calls Acc Calls Acc Calls Acc Calls Acc Calls Vanilla 3.33 17 13.33 23 12.50 66 51.00 341 76.95 731 24.33 453 54.52 204 59.83 224 36.97+00.00% 2059(1631,428) GRPO 10.00 12 20.00 8 57.50 18 82.33 94 93.86 59 50.74 29 53.39 214 61.85 226 53.71+45.28% 660(220,440) SeeUPO 20.00 8 23.33 6 67.50 14 84.20 87 94.47 87 53.86 147 54.27 254 63.78 253 57.68+56.02% 856(349,507) RTPO 33.33 4 26.67 2 67.50 9 86.20 168 94.84 482 55.49 106 64.89 613 64.35 867 61.66+66.78% 2251(771,1480) Table 1: Performance comparison across eight tool-use agentic RL benchmarks. Acc denotes Pass@1 for mathematical tasks and best-span F1 for knowledge tasks, while Calls denotes the number of tool calls rounded to the nearest integer, such as Python and web-search calls. Overall subscripts indicate relative changes in accuracy compared with the vanilla model, along with total tool calls (M, K). 4.2 Rollout–Training Consistency Analysis To examine RTPO’s training-time advantage, we measure at each step the geometric-mean ratio between training-stage and rollout-stage token logprobs. This ratio captures rollout–training consistency: values near 11 indicate matched conditioning distributions, while deviations suggest that the full-history training policy favors outputs different from those sampled during rollout. The Kullback–Leibler (KL) divergence further quantifies the distributional gap, with smaller values indicating stronger rollout–training consistency. Figure 3 shows the log-probability ratio and KL divergence during training. On mathematical tasks, RTPO stays stable at 1.01.0, while SeeUPO fluctuates around 1.01.0 and GRPO recovers from 0.890.89 to 0.970.97 after 3030 steps. On knowledge tasks, RTPO again remains at 1.01.0, whereas SeeUPO and GRPO recover only from around 0.800.80 to 0.890.89 and 0.830.83 after 1414 steps. RTPO also achieves the lowest average KL divergence, indicating more consistent rollout-training contexts than the baselines. (a) Rollout-train ratio [M] (b) Rollout-train ratio [K] (c) KL divergence (M) (d) KL divergence (K) Figure 3: Rollout–training consistency comparison using log-probability ratios and KL divergence on mathematical (M) and knowledge (K) reasoning tasks. Zoom in for better visualization. A noteworthy observation is that, despite using different rollout and training contexts, baseline ratios still drift slowly toward 11. This resembles the bootstrapped alignment mechanisms in DAgger (40) and SCoRe (23). However, unlike RTPO’s structural consistency, this empirical alignment is incomplete, task-dependent, noisy, and consumes additional optimization budget. We provide further discussion and insights in Appendix F.2. 4.3 Effect of Turn-Level Credit Assignment To isolate the effect of RTPO’s turn-level credit signal, we feed the full interaction history as the rollout input for all methods, controlling for the rollout–training context mismatch presented in Sec 4.2. Under this control setting, performance differences mainly reflect the effect of credit assignment (CA) on advantage estimation. Because full interaction histories are used, the accuracy scores in Table 2 are substantially higher than those in Table 1. RTPO-CA achieves the highest overall average across the four mathematical reasoning benchmarks, as shown in Table 2. It achieves the best results on AMC23 (Pass@1 93.3393.33, Pass@4 100.0100.0), AIME25 (Pass@1 70.0070.00, Pass@4 76.6776.67), and MATH500 (Pass@1 86.6086.60, Pass@4 89.6089.60), while matching the best Pass@4 on AIME24 (80.0080.00). These results show that RTPO improves both solution coverage and the preference for correct answers, with the largest gain on the harder AIME25 benchmark. This supports the value of turn-level credit assignment: by forking sibling rollouts from the same boundary state SkS_k, RTPO forms a local baseline and attributes advantage directly to the current turn decision. Method AMC23 AIME24 AIME25 MATH500 Overall P@1 P@4 P@1 P@4 P@1 P@4 P@1 P@4 P@1 P@4 ARPO 90.00 97.50 73.33 73.33 63.33 73.33 86.00 88.80 78.15 83.23 TreeGRPO 92.50 96.67 63.33 80.00 56.67 70.00 86.20 89.40 74.67 84.00 SeeUPO 92.50 97.50 73.33 80.00 53.33 70.00 86.20 89.20 76.33 84.18 RTPO-CA 93.33 100.0 66.67 80.00 70.00 76.67 86.60 89.60 79.13 86.55 Table 2: Mathematical reasoning performance under controlled turn-level credit assignment (CA). Overall reports the average across benchmarks. Bold indicates the best result. 4.4 Policy Drift Correction To isolate the effect of on-policy continuation (Sec 3.3), we compare the default RTPO with an off-policy variant that reuses downstream continuations generated by πθ0 _ _0 during the initial rollout and corrects staleness using a clamped trajectory-level IS weight; see Appendix E.2 for details. We evaluate both variants on four knowledge-reasoning deep-search benchmarks (GAIA, WebWalkerQA, HLE, and XBench) using output-hit accuracy. As shown in Table 3, default RTPO outperforms the off-policy variant on GAIA (+5.83%+5.83\%, WebWalkerQA (+3.50%+3.50\%), and XBench (+7.00%+7.00\%). On HLE, the difference is negligible (−0.33%-0.33\%), indicating a near tie. This pattern supports Theorem 3(b): on-policy continuation is most beneficial when downstream policies change substantially during reverse-order training. GAIA, WebWalkerQA, and XBench involve longer retrieval and interaction horizons, where stale-rollout IS correction can introduce clamp-truncation bias that on-policy re-sampling avoids. In contrast, HLE is more closed-ended and often requires shorter search horizons, leading to smaller gains; additional results in Appendix F.3 further support this interpretation. In addition, we discuss the limitations, future work, and broader impacts of RTPO in Appendix F.4, F.5. Benchmark QS Off-Policy Hit Off-Policy Rate On-Policy Hit On-Policy Rate Δ GAIA 103 24 23.30% 30 29.13% +5.83% XBench 100 8 8.00% 15 15.00% +7.00% WebWalker 200 12 6.00% 19 9.50% +3.50% HLE 2096 261 12.45% 254 12.12% -0.33% Table 3: Output-hit comparison between on- and off-policy RTPO variants on knowledge tasks. Values are rounded to the nearest integer. Δ denotes the change from off-policy to on-policy hit rates. 5 Concluding Remarks This work identifies rollout–training mismatch as a fundamental source of instability in multi-turn agentic RL, particularly in tool-augmented mathematical reasoning and deep-search tasks. We provide a theoretical analysis showing how existing training pipelines produce unstable optimization signals and propose RTPO as a principled framework to address this issue. RTPO integrates rollout–training consistency, turn-level credit assignment, and on-policy continuation within a unified training pipeline. Supported by theoretical guarantees and empirical results, RTPO improves multi-turn optimization stability and provides a promising direction for training long-horizon tool-using agents. References Abel et al. (2020) D. Abel, N. Umbanhowar, K. Khetarpal, D. Arumugam, D. Precup, and M. Littman Value preserving state-action abstractions. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Cited by: §B.1. Allen et al. (2021) C. Allen, N. Parikh, O. Gottesman, and G. Konidaris Learning markov state abstractions for deep reinforcement learning. Advances in Neural Information Processing Systems. Cited by: §B.1, §F.2. Bertsekas (2025) D. P. Bertsekas Neuro-dynamic programming. In Encyclopedia of optimization, Cited by: §C.1. Browne et al. (2012) C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games. Cited by: Appendix A. Cao et al. (2026a) L. Cao, H. Ruan, Y. Li, P. Chao, W. Ning, H. Song, R. Chen, and Y. Li TreeAdv: tree-structured advantage redistribution for group-based rl. arXiv preprint arXiv:2601.03703. Cited by: Appendix A. Cao et al. (2026b) R. Cao, S. Bai, F. Yao, L. Dong, J. Xu, and L. Xiao ATPO: adaptive tree policy optimization for multi-turn medical dialogue. In The Fourteenth International Conference on Learning Representations, Cited by: Appendix A. Chang et al. (2026) Q. Chang, Z. Zhang, P. Hu, J. Du, J. Ma, Y. Pan, J. Zhang, Q. Liu, and J. Gao THOR: tool-integrated hierarchical optimization via RL for mathematical reasoning. In The Fourteenth International Conference on Learning Representations, Cited by: §1. Chen et al. (2025) K. Chen, Y. Ren, Y. Liu, X. Hu, H. Tian, T. Xie, F. Liu, H. Zhang, H. Liu, Y. Gong, et al. Xbench: tracking agents productivity scaling with profession-aligned real-world evaluations. arXiv preprint arXiv:2506.13651. Cited by: Appendix D. Chen et al. (2026) Y. Chen, G. Dong, and Z. Dou Toward effective tool-integrated reasoning via self-evolved preference learning. In The Fourteenth International Conference on Learning Representations, Cited by: §1. Cobbe et al. (2021) K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: Appendix D. Coulom (2006) R. Coulom Efficient selectivity and backup operators in monte-carlo tree search. In Proceedings of the 5th International Conference on Computers and Games, Cited by: Appendix A, §B.1. Dietterich (2000) T. G. Dietterich Hierarchical reinforcement learning with the maxq value function decomposition. Journal of artificial intelligence research. Cited by: §3.2. Dong et al. (2026) G. Dong, H. Mao, K. Ma, L. Bao, Y. Chen, Z. Wang, Z. Chen, J. Du, H. Wang, F. Zhang, G. Zhou, Y. Zhu, J. Wen, and Z. Dou Agentic reinforced policy optimization. In The Fourteenth International Conference on Learning Representations, Cited by: Appendix A, Appendix D, Appendix D, §1, §4. Gao et al. (2023) L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig Pal: program-aided language models. In International conference on machine learning, Cited by: §1. Guo et al. (2025) D. Guo, D. Yang, H. Zhang, J. Song, P. Wang, Q. Zhu, R. Xu, R. Zhang, S. Ma, X. Bi, et al. Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Cited by: §1. Hauskrecht et al. (1998) M. Hauskrecht, N. Meuleau, L. P. Kaelbling, T. Dean, and C. Boutilier Hierarchical solution of markov decision processes using macro-actions. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Cited by: §2. He et al. (2024) C. He, R. Luo, Y. Bai, S. Hu, Z. L. Thai, J. Shen, J. Hu, X. Han, Y. Huang, Y. Zhang, et al. Olympiadbench: a challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. arXiv preprint arXiv:2402.14008. Cited by: Appendix D. Hendrycks et al. (2021) D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt Measuring mathematical problem solving with the math dataset. Thirty-Fifth Annual Conference on Neural Information Processing Systems. Cited by: Appendix D. Ho et al. (2020) X. Ho, A. Duong Nguyen, S. Sugawara, and A. Aizawa Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th International Conference on Computational Linguistics, Cited by: Appendix D. Hu et al. (2026) T. Hu, Q. Fu, Y. Chen, Z. Liu, and B. Ding SeeUPO: sequence-level agentic-rl with convergence guarantees. arXiv preprint arXiv:2602.06554. Cited by: Appendix A, Appendix D, §1, §4. Jaakkola et al. (1994) T. Jaakkola, M. I. Jordan, and S. P. Singh On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation. Cited by: §C.1. Ji et al. (2026) Y. Ji, Z. Ma, Y. Wang, G. Chen, X. Chu, and L. Wu Tree search for LLM agent reinforcement learning. In The Fourteenth International Conference on Learning Representations, Cited by: Appendix A, Appendix D, §1, §4. Kumar et al. (2025) A. Kumar, V. Zhuang, R. Agarwal, Y. Su, J. D. Co-Reyes, A. Singh, K. Baumli, S. Iqbal, C. Bishop, R. Roelofs, et al. Training language models to self-correct via reinforcement learning. In The Thirteenth International Conference on Learning Representations, Cited by: §F.2, §4.2. Kwon et al. (2023) W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. E. Gonzalez, H. Zhang, and I. Stoica Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, Cited by: Appendix D, §4. Le et al. (2022) H. Le, Y. Wang, A. D. Gotmare, S. Savarese, and S. C. H. Hoi Coderl: mastering code generation through pretrained models and deep reinforcement learning. Advances in Neural Information Processing Systems. Cited by: §1. Li et al. (2025) K. Li, Z. Zhang, H. Yin, L. Zhang, L. Ou, J. Wu, W. Yin, B. Li, Z. Tao, X. Wang, et al. Websailor: navigating super-human reasoning for web agent. arXiv preprint arXiv:2507.02592. Cited by: Appendix D. Li et al. (2026) Y. Li, Z. Cao, J. Qiao, and S. Hu SSVPO: effective step-level credit assignment for RL training of language models. In The Fourteenth International Conference on Learning Representations, Cited by: §1. Lightman et al. (2023) H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe Let’s verify step by step. In The Twelfth International Conference on Learning Representations, Cited by: Appendix D. Lindenbauer et al. (2025) T. Lindenbauer, I. Slinko, L. Felder, E. Bogomolov, and Y. Zharov The complexity trap: simple observation masking is as efficient as llm summarization for agent context management. arXiv preprint arXiv:2508.21433. Cited by: §B.1. Liu et al. (2026) M. Liu, X. Ma, Y. Xie, Q. Chen, X. Liu, and Y. Ma ROGA: scaling generalist agents for office productivity tasks via tool generation. In The Fourteenth International Conference on Learning Representations, Cited by: §1. Loshchilov and Hutter (2017) I. Loshchilov and F. Hutter Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101. Cited by: Appendix D. Lu et al. (2025) M. Lu, W. Sun, W. Du, Z. Ling, X. Yao, K. Liu, and J. Chen Scaling llm multi-turn rl with end-to-end summarization-based context management. arXiv preprint arXiv:2510.06727. Cited by: §F.2. Mathematical Association of America (2023) Mathematical Association of America American mathematics competitions (AMC). Mathematical Association of America. Cited by: Appendix D. Mathematical Association of America (2024) Mathematical Association of America American invitational mathematics examination (AIME). Mathematical Association of America. Cited by: Appendix D. Mathematical Association of America (2025) Mathematical Association of America American invitational mathematics examination (AIME). Mathematical Association of America. Cited by: Appendix D. Mialon et al. (2023) G. Mialon, C. Fourrier, C. Swift, T. Wolf, Y. LeCun, and T. Scialom Gaia: a benchmark for general ai assistants. arXiv preprint arXiv:2311.12983. Cited by: Appendix D. Phan et al. (2025) L. Phan, A. Gatti, Z. Han, N. Li, J. Hu, H. Zhang, C. B. C. Zhang, M. Shaaban, J. Ling, S. Shi, et al. Humanity’s last exam. arXiv preprint arXiv:2501.14249. Cited by: Appendix D. Rafailov et al. (2023) R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn Direct preference optimization: your language model is secretly a reward model. Advances in Neural Information Processing Systems. Cited by: Appendix A. Robbins and Monro (1951) H. Robbins and S. Monro A stochastic approximation method. The Annals of Mathematical Statistics. Cited by: §C.2. Ross et al. (2011) S. Ross, G. Gordon, and D. Bagnell A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, Cited by: §F.2, §4.2. Schulman et al. (2017) J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §1. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. Li, Y. Wu, et al. Deepseekmath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: Appendix A, Appendix D, §1, §1, §2, §4. Sheng et al. (2024) G. Sheng, C. Zhang, Z. Ye, X. Wu, W. Zhang, R. Zhang, Y. Peng, H. Lin, and C. Wu HybridFlow: a flexible and efficient rlhf framework. arXiv preprint arXiv: 2409.19256. Cited by: Appendix D, §E.2, §4. Shinn et al. (2023) N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao Reflexion: language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems. Cited by: §1. Shojaee et al. (2023) P. Shojaee, A. Jain, S. Tipirneni, and C. K. Reddy Execution-based code generation using deep reinforcement learning. Transactions on Machine Learning Research. Cited by: §1. Silver et al. (2016) D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis Mastering the game of go with deep neural networks and tree search. Nature. Cited by: Appendix A. Singh et al. (2000) S. Singh, T. Jaakkola, M. L. Littman, and C. Szepesvári Convergence results for single-step on-policyreinforcement-learning algorithms. Machine Learning. Cited by: §C.1. Sun et al. (2025) S. Sun, H. Song, Y. Wang, R. Ren, J. Jiang, J. Zhang, F. Bai, J. Deng, W. X. Zhao, Z. Liu, et al. Simpledeepsearcher: deep information seeking via web-powered reasoning trajectory synthesis. arXiv preprint arXiv:2505.16834. Cited by: Appendix D. Team et al. (2025) K. Team, A. Du, B. Gao, B. Xing, C. Jiang, C. Chen, C. Li, C. Xiao, C. Du, C. Liao, et al. Kimi k1. 5: scaling reinforcement learning with llms. arXiv preprint arXiv:2501.12599. Cited by: §1. Tian et al. (2026) W. Tian, S. Zhang, K. Zhang, X. Chi, C. Fan, J. Lu, Y. Luo, Q. Zhou, Y. Zhao, N. Liu, S. Lin, Z. Qin, X. Ju, S. Zhang, and J. Tang SEEA-r1: tree-structured reinforcement fine-tuning for self-evolving embodied agents. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: Appendix A. Tsitsiklis (1994) J. N. Tsitsiklis Asynchronous stochastic approximation and q-learning. Machine learning. Cited by: §C.1. Wang et al. (2025a) X. Wang, S. Rosenberg, J. Michelini, C. Smith, H. Tran, E. Nyst, R. Malhotra, X. Zhou, V. Chen, R. Brennan, et al. The openhands software agent sdk: a composable and extensible foundation for production agents. arXiv preprint arXiv:2511.03690. Cited by: §B.1. Wang et al. (2025b) Z. Wang, K. Wang, Q. Wang, P. Zhang, L. Li, Z. Yang, X. Jin, K. Yu, M. N. Nguyen, L. Liu, et al. Ragen: understanding self-evolution in llm agents via multi-turn reinforcement learning. arXiv preprint arXiv:2504.20073. Cited by: Appendix A. Watkins and Dayan (1992) C. J. Watkins and P. Dayan Q-learning. Machine learning. Cited by: §C.1. Wu et al. (2025a) J. Wu, W. Yin, Y. Jiang, Z. Wang, Z. Xi, R. Fang, L. Zhang, Y. He, D. Zhou, P. Xie, et al. Webwalker: benchmarking llms in web traversal. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, Cited by: Appendix D. Wu et al. (2025b) X. Wu, K. Li, Y. Zhao, L. Zhang, L. Ou, H. Yin, Z. Zhang, X. Yu, D. Zhang, Y. Jiang, et al. Resum: unlocking long-horizon search intelligence via context summarization. arXiv preprint arXiv:2509.13313. Cited by: §B.1. Xue et al. (2026) Z. Xue, L. Zheng, Q. Liu, Y. Li, X. Zheng, Z. MA, and B. An SimpleTIR: end-to-end reinforcement learning for multi-turn tool-integrated reasoning. In First Workshop on Multi-Turn Interactions in Large Language Models, Cited by: Appendix A. Yang et al. (2025a) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: Appendix D, §4. Yang et al. (2024) A. Yang, B. Zhang, B. Hui, B. Gao, B. Yu, C. Li, D. Liu, J. Tu, J. Zhou, J. Lin, et al. Qwen2. 5-math technical report: toward mathematical expert model via self-improvement. arXiv preprint arXiv:2409.12122. Cited by: §1. Yang et al. (2025b) Z. Yang, Z. Guo, Y. Huang, X. Liang, Y. Wang, and J. Tang Treerpo: tree relative policy optimization. arXiv preprint arXiv:2506.05183. Cited by: Appendix A. Yang et al. (2018) Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. Cohen, R. Salakhutdinov, and C. D. Manning HotpotQA: a dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Cited by: Appendix D. Yao et al. (2023) S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao ReAct: synergizing reasoning and acting in language models. In International Conference on Learning Representations, Cited by: §1. Yu et al. (2026a) H. Yu, T. Chen, J. Feng, J. Chen, W. Dai, Q. Yu, Y. Zhang, W. Ma, J. Liu, M. Wang, and H. Zhou MemAgent: reshaping long-context LLM with multi-conv RL-based memory agent. In The Fourteenth International Conference on Learning Representations, Cited by: §F.2. Yu et al. (2026b) Q. Yu, Z. Zhang, R. Zhu, Y. Yuan, X. Zuo, YuYue, W. Dai, T. Fan, G. Liu, J. Liu, L. Liu, X. Liu, H. Lin, Z. Lin, B. Ma, G. Sheng, Y. Tong, C. Zhang, M. Zhang, R. Zhang, W. Zhang, H. Zhu, J. Zhu, J. Chen, J. Chen, C. Wang, H. Yu, Y. Song, X. Wei, H. Zhou, J. Liu, W. Ma, Y. Zhang, L. Yan, Y. Wu, and M. Wang DAPO: an open-source LLM reinforcement learning system at scale. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: §2. Yue et al. (2025) Y. Yue, Y. Yuan, Q. Yu, X. Zuo, R. Zhu, W. Xu, J. Chen, C. Wang, T. Fan, Z. Du, et al. Vapo: efficient and reliable reinforcement learning for advanced reasoning tasks. arXiv preprint arXiv:2504.05118. Cited by: §2. Zhao et al. (2023) Y. Zhao, A. Gu, R. Varma, L. Luo, C. Huang, M. Xu, L. Wright, H. Shojanazeri, M. Ott, S. Shleifer, et al. Pytorch fsdp: experiences on scaling fully sharded data parallel. arXiv preprint arXiv:2304.11277. Cited by: Appendix D, §4. Zheng et al. (2025) C. Zheng, S. Liu, M. Li, X. Chen, B. Yu, C. Gao, K. Dang, Y. Liu, R. Men, A. Yang, et al. Group sequence policy optimization. arXiv preprint arXiv:2507.18071. Cited by: Appendix A, §1, §2. Zhong et al. (2024) Y. Zhong, J. G. Kuba, X. Feng, S. Hu, J. Ji, and Y. Yang Heterogeneous-agent reinforcement learning. Journal of Machine Learning Research. Cited by: Appendix A. Appendix A Related Work Policy optimization in agentic RL. Recent post-training of large language models (LLMs) has shifted from supervised fine-tuning toward reinforcement learning with verifiable rewards (RLVR). Among existing approaches, GRPO [42], built upon PPO, reduces variance through token-level importance ratios and group-relative advantage estimation, and has become a representative algorithm for agentic RL. Its sequence-level refinement, GSPO [67], further defines importance ratios and clipping operations at the sequence level, leading to more stable training dynamics on models such as Qwen3. However, when these RL methods are directly transferred from single-turn to multi-turn agentic settings, a structural mismatch emerges between rollout and training. Existing methods often treat the entire multi-turn interaction as a single concatenated trajectory and distribute a single scalar reward uniformly across all tokens, thereby ignoring the actual contribution of each turn. More importantly, the rollout may operate on truncated or summarized contexts, whereas the training recomputes importance ratios over the full interaction history. This discrepancy induces a mismatch in conditioning distributions and weakens the assumptions under which PPO-style optimization is expected to remain stable. In long-horizon multi-turn scenarios, these issues can manifest as training divergence or eventual policy collapse. A noteworthy latest work is SeeUPO [20], which first models multi-turn interaction as a sequentially executed multi-agent bandit problem. Under the heterogeneous-agent RL framework [68], SeeUPO updates turn-level virtual agents in reverse execution order (T→T−1→⋯→1)(T→ T-1→·s→ 1), thereby inheriting the monotonic-improvement property and proving convergence to the globally optimal policy. This provides strong motivation for our proposed RTPO design, particularly its reverse-order turn updates. However, each turn-level agent in SeeUPO is still trained on the full chat history rather than on the turn-level conditioning context ckc_k actually observed by the model during rollout; therefore, the policy-forward mismatch is not eliminated. Moreover, within each turn, SeeUPO corrects downstream advantages using token-level importance-sampling reweighting. As the reverse training recursion proceeds and the number of involved turns accumulates, the variance of the importance-sampling ratio can grow multiplicatively. Although clipping bounds this ratio from above, it also introduces systematic bias into the per-turn advantage estimate. Tree-based credit assignment. To mitigate the sparse-credit problem caused by flattened trajectories in multi-turn agentic RL training, a recent line of work reorganizes rollouts into tree structures with shared prefixes, thereby constructing finer-grained credit signals. ARPO [13] adaptively tree branches at high-entropy nodes following tool calls and, through advantage attribution estimation, applies branch averaging to shared-prefix tokens while estimating advantages independently for tokens on disjoint branches. Afterward, TreeGRPO [22] abstracts each turn as a tree node and combines intra-tree and inter-tree group-relative advantages, theoretically establishing gradient-level equivalence with step-level DPO [38]. This tree-based formulation is extended in SEEA-R1 [50], which integrates MCTS [11, 4, 46] into embodied-agent settings and trains a multimodal generative reward model to densify sparse outcome rewards. Tree-structured credit assignment has also been explored in step/token levels. TreeRPO [60] adopts an N-ary tree for mathematical reasoning and constructs step-level rewards through bottom-up Bellman expectations. TreeAdv [5] employs entropy-triggered branching and redistributes leaf advantages to tokens using inverse-descendant-count weighting. Similarly, ATPO [6] operates under a hierarchical MDP and uses Bellman error and Q-value variance as uncertainty measures for adaptive expansion, while applying visit-count-based down-weighting to suppress update imbalance caused by repeated nodes. Although these tree-based rollouts improve the granularity of credit assignment in multi-turn training, they do not fully eliminate the propagation of trajectory-level credit mismatch to individual turns through the reconstructed tree. For instance, in Tree-GRPO and SEEA-R1, advantages are still derived from leaf returns, typically in the form Ai=Ri−mean(R)std(R)A_i= R_i-mean(R)std(R). As a result, prefix nodes that appear on multiple paths inherit trajectory-level signals from all descendant outcomes, causing the gradient direction at shared tokens to be perturbed by trajectory-level scalars originating from different rollouts. In TreeAdv, the 1/|S|1/|S| normalization attenuates the signal more aggressively near the root, precisely suppressing early decisions where informative gradients are often most needed. In addition, ARPO averages multi-branch advantages on shared tokens, which can dilute the signal linearly with the number of branches, while ATPO relies on a learned critic and is therefore exposed to critic-induced bias. Therefore, under the rollout–training contextual mismatch settings, shared-prefix tokens may still carry trajectory-level credit signals with significant residual bias. Policy gradient correction. Another line of work studies stable training from the perspective of correcting (off-)policy drift through interventions. SimpleTIR [57], by decomposing the policy gradient on softmax logits, attributes gradient explosion in multi-turn tool-integrated reasoning (TIR) to the accumulation of low-probability tokens under the distributional shift induced by tool feedback. It proposes filtering out entire trajectories that contain void turns: turns produce neither a complete code block nor a final answer to block harmful gradients. This method is empirically effective and plug-and-play; however, the void-turn criterion is tightly coupled with the code-execution setting of mathematical reasoning and is difficult to transfer to other scenarios, such as web search. It also inevitably discards a non-trivial fraction of training data. RAGEN [53] discovers the inconsistency between rollout and training engines for mismatch correction through numerical mechanisms such as truncated importance sampling. However, these approaches mainly address numerical discrepancies while overlooking the contextual mismatch between rollout conditioning and training recomputation. In contrast, our proposed RTPO does not rely on trajectory dropping or post-hoc numerical correction. Instead, it restructures the training paradigm from a turn-boundary MDP perspective, maintaining the on-policy optimization throughout the entire training process. Appendix B Full Theoretical Analysis: Training Instability Here, we provide the full theoretical analysis of training instability in multi-turn agentic RL: Single flattened-trajectory policy optimization (B.1): Standard rollouts are typically generated under truncated or summarized contexts for efficiency, whereas training re-evaluates tokens under concatenated full-history contexts without truncation. This rollout–training context mismatch induces biased importance-sampling (IS) ratios, thereby undermining stable policy optimization. Trajectory-only credit assignment (B.2): In multi-turn interactions, a given state may admit multiple valid actions, requiring accurate credit assignment for each action. However, credit computed from a single trajectory-level advantage can obscure the contribution of individual turns and therefore cannot provide a proper comparison among alternative actions. Long-horizon off-policy drift (B.3): In long-horizon tasks, standard policy optimization with per-token clipping is insufficient to correct policy drift under asynchronous training. Since later states depend on earlier generated actions and tool feedback, once the policy drifts, the later-turn states visited during rollout may no longer match those induced by the current policy. Preliminaries. A multi-turn interaction with TIR is represented as a standard trajectory (q,l0,f0,…,ln−1,fn−1)(q,l_0,f_0,…,l_n-1,f_n-1) spanning n turns, where q is the initial prompt, lkl_k is the response generated, and fkf_k is the corresponding external tool feedback returned by the environment for each turn k∈0,…,n−1k∈\0,…,n-1\. We formulate this process as a Hierarchical Markov Decision Process (H-MDP), which captures turn-level (high-level) planning and token-level (low-level) execution in multi-turn agentic RL. At the turn level, for each turn k, the agent state SkS_k represents all interaction history (q,l0,f0,…,lk−1,fk−1) (q,l_0,f_0,…,l_k-1,f_k-1 ), available before the current turn, including previous responses, tool calls, and corresponding environment feedback. The corresponding turn-level action is the decision of what response to produce at the current turn, denoted by lk∈Hl_k _H. After executing this action and receiving environmental feedback fkf_k, the turn-level state evolves as Sk+1=Sk∘(lk,fk)S_k+1=S_k (l_k,f_k), where ∘ denotes concatenation. Each turn-level action (response) lkl_k is generated autoregressively at the token level as lk=(ak,1,ak,2,…,ak,Tk)l_k=(a_k,1,a_k,2,…,a_k,T_k), where ak,t∈La_k,t _L denotes the token generated at step t, and TkT_k is the number of tokens in the response at turn k. The corresponding low-level state is sk,t=(Sk,ak,1,…,ak,t−1)∈Ls_k,t=(S_k,a_k,1,…,a_k,t-1) _L, which consists of the turn history SkS_k together with the token prefix generated so far in the current turn. Since the token only serves to generate the turn-level action (response) and does not itself receive intermediate reward, we set the low-level reward to RL=0R_L=0 and set γH=γL=1 _H= _L=1 as the discount factor. Our hierarchical formulation differs from existing policy optimization methods, which do not explicitly distinguish turn-level planning from token-level execution. Instead, they flatten the entire multi-turn interaction into a single token sequence, i.e., a single trajectory, and optimize it using clipped policy optimization methods in the PPO family. Let q∼q be an input prompt sampled from the task distribution, and let gii=1G\g_i\_i=1^G be a group of G trajectories of this form sampled from the old policy πθold _ _old conditioned on q, where θ denotes the current policy parameters and θold _old denotes the rollout policy parameters. For trajectory gig_i, we denote its turn-k state and response by Si,kS_i,k and li,kl_i,k, respectively: Jflat(θ)=q∼gii=1G∼πθold(⋅∣q)[1G∑i=1G1∑t′mi,t′∑tmi,tLi,tCLIP(θ)]J^flat(θ)=E_ subarraycq \\ \g_i\_i=1^G _ _old(· q) subarray [ 1G _i=1^G 1 _t m_i,t _tm_i,tL_i,t^CLIP(θ) ] (9) where i indexes the sampled trajectory, t indexes flattened token positions, and Li,tCLIP(θ)=min(ρi,t(θ)Ai,clip(ρi,t(θ), 1−ϵ, 1+ϵ)Ai)L_i,t^CLIP(θ)= \! ( _i,t(θ)A_i,\,clip\! ( _i,t(θ),\,1-ε,\,1+ε )A_i ) is the standard clipped surrogate objective with clipping threshold ϵε. ai,ta_i,t is the token generated at flattened position t in the i-th sampled trajectory, mi,tm_i,t is a binary mask indicating whether that token contributes to the policy gradient, and ρi,t(θ)=πθ(ai,t∣xi,<t)πθold(ai,t∣xi,<t) _i,t(θ)= _θ(a_i,t x_i,<t) _ _old(a_i,t x_i,<t) is the IS ratio. The context xi,<tx_i,<t is the flattened interaction context preceding token ai,ta_i,t, including previously generated response tokens and inserted environment feedback. The scalar AiA_i denotes the trajectory-level group-relative advantage, which is uniformly assigned to all unmasked tokens in trajectory gig_i. B.1 Single flattened-trajectory policy optimization: mismatch from rollout to training In multi-turn interactions, the accumulated history can become too long for the model to process in full. For example, an agent may search for information, call a tool, revise its plan based on the returned result, and repeat this process over many turns. By later turns, the prompt, previous responses, and tool feedback may already span tens of thousands of tokens. In practice, rollouts therefore often rely on a truncated or summarized context rather than the complete interaction history [52, 29, 56]. Therefore, existing methods typically reconstruct the whole interaction as a single concatenated sequence, or flattened trajectory, during training. This flattened training formulation evaluates each generated token under the concatenated prefix, rather than under the original context that was actually used during rollout. Consequently, tokens generated at turn k are optimized under a conditioning context that can differ from the rollout context that produced them. We refer to this discrepancy as a rollout-to-training mismatch induced by flattened-trajectory policy optimization. We next analyze how this mismatch distorts the likelihood-ratio estimation underlying clipped policy optimization in the PPO/GRPO family. Policy optimization mismatch across turns. Under flat training, the optimization mismatch across turns arises because the same generated token is conditioned on different contexts during rollout and training. We now formalize this mismatch and show that it induces a biased IS ratio. Let x¯k x_k denote the full interaction history before turn k, and let ϕ:¯→φ: X be an observation map that truncates or summarizes history beyond the model’s effective context length. During rollout, token-level actions are sampled conditioned on ϕ(x¯k)φ( x_k), so the true sampling distribution is πθold(ak,t∣ϕ(x¯k)) _ _old(a_k,t φ( x_k)). In clipped policy optimization of the PPO/GRPO family, the denominator of the IS ratio must match this rollout distribution. However, under flat training, the same token is re-evaluated under the concatenated full-history context, yielding πθold(ak,t∣x¯k) _ _old(a_k,t x_k). This leads to the mismatch ρk,tflat=πθ(ak,t∣x¯k)πθold(ak,t∣ϕ(x¯k))≠πθ(ak,t∣ϕ(x¯k))πθold(ak,t∣ϕ(x¯k))=ρk,ttrue. _k,t^flat= _θ(a_k,t x_k) _ _old(a_k,t φ( x_k))≠ _θ(a_k,t φ( x_k)) _ _old(a_k,t φ( x_k))= _k,t^true. (10) The denominator used in flat training, πθold(ak,t∣x¯k) _ _old(a_k,t x_k), does not match with the true rollout sampling probability, πθold(ak,t∣ϕ(x¯k)) _ _old(a_k,t φ( x_k)). Consequently, ρk,tflat _k,t^flat is a biased estimate of the correct IS ratio. Since clipped policy-gradient updates in the PPO/GRPO family depend on the IS ratio, the bias propagates into the gradient estimate and can distort the update direction, leading to instability in multi-turn agentic RL training. This mismatch becomes more severe for tokens generated in later turns, since the amount of history omitted during rollout typically grows with k, while flat training continues to re-evaluate these tokens under the concatenated training prefix. In the worst case, the resulting discrepancy in token probability can become extremely large. State aliasing and projected suboptimality. Beyond gradient bias, truncated contexts also introduce state aliasing, where distinct full-history states are mapped to the same truncated representation. When ϕφ is non-injective, different interaction histories may collapse into an identical observation zk=ϕ(x¯k)z_k=φ( x_k) [11]. The induced process over zkz_k may not preserve the Markov property of the original full-history process [2]. As a result, any policy conditioned only on zkz_k is confined to the observation-induced policy class Πϕ φ. Even if optimized exactly within this restricted class, such a policy can achieve only the projected optimum VΠϕ∗V^*_ _φ [1], which can be strictly lower than the true optimum V∗V^*. Therefore, projected suboptimality can arise, with VΠϕ∗<V∗V^*_ _φ<V^*. Under observation inconsistency, flattened-trajectory training may be limited to the projected optimum VΠϕ∗V^*_ _φ, which is strictly suboptimal relative to the full-history optimum V∗V^*. B.2 Trajectory-only credit assignment: mismatch across low- and high-quality turns In multi-turn interactions, trajectories generated from the same query can reach substantially different states by turn k. As a result, a trajectory-level return no longer provides a reliable credit signal for evaluating actions taken at that turn. Under flattened-trajectory training, credit is assigned only at the trajectory level and then shared across tokens within a single trajectory, which mismatches the turn-level structure of the decision process. Here, we analyze how a trajectory advantage entangles the contribution of the current turn with both upstream state effect and downstream stochasticity. A trajectory advantage entangles turn-level credit with context effects. A single trajectory advantage is typically defined as Ai=Ri−R¯A_i=R_i- R, where RiR_i denotes the final return of trajectory gig_i and R¯ R is the average return over the sampled group. This trajectory advantage is then assigned to all turns in the trajectory, without identifying each turn’s individual contributions. To expose the turn-level credit hidden in this trajectory return, we analyze its population counterpart, Ri−[R]R_i-E[R], by introducing the conditional expectations [R∣Si,k,li,k]E[R S_i,k,l_i,k] and [R∣Si,k]E[R S_i,k]: Ri−[R]=Ri−Qπ(Si,k,li,k)⏟ξdown:downstream stochasticity+Aπ(Si,k,li,k)⏟true turn-k advantage+Vπ(Si,k)−μR⏟ξup:upstream state effect,R_i-E[R]= R_i-Q^π(S_i,k,l_i,k)_ _down:\;downstream stochasticity+ A^π(S_i,k,l_i,k)_true turn-k advantage+ V^π(S_i,k)- _R_ _up:\;upstream state effect, (11) where Qπ(Si,k,li,k)=[R∣Si,k,li,k]Q^π(S_i,k,l_i,k)=E[R S_i,k,l_i,k], Vπ(Si,k)=[R∣Si,k]V^π(S_i,k)=E[R S_i,k], and μR=[R] _R=E[R]. The true turn-k advantage Aπ(Si,k,li,k)A^π(S_i,k,l_i,k) is therefore only one component of the trajectory advantage. The term ξdown _down captures downstream stochasticity after turn k, while ξup _up captures variation induced by the upstream state reached before turn k. Whenever ξdown+ξup _down+ _up dominates Aπ(Si,k,li,k)A^π(S_i,k,l_i,k) in magnitude, the sign of the trajectory advantage can disagree with that of the true turn advantage, i.e., sign(Ai)≠sign(Aπ(Si,k,li,k))sign(A_i) (A^π(S_i,k,l_i,k)), thereby reversing the gradient direction for turn k. Therefore, a trajectory advantage is not a valid turn-level credit signal for turn k, because it entangles the context effect of the current turn with both upstream state effects and downstream stochasticity. When these two terms dominate, the resulting policy update can assign incorrect credit to the current turn and may even reverse the intended policy gradient direction. Cross-trajectory baseline with state bias. Since group-based policy optimization methods generate multiple trajectories from the same input query by sampling several rollouts from the current or old policy, they typically compute advantages of the form Ai=Ri−bA_i=R_i-b, where RiR_i is the return of trajectory gig_i and b=1G∑j=1GRjb= 1G _j=1^GR_j is the group baseline. To determine whether the compared trajectories provide a valid turn-level credit signal, we examine whether they share the same turn-level state Si,kS_i,k. If they do, the baseline compares alternative outcomes from the same context and is therefore matched. Otherwise, the baseline mixes returns from different states and no longer reflects the local effect of the current turn, leading to mismatched credit assignment. Formally, viewing AiA_i as an estimator of the true turn-k advantage Aπ(Si,k,li,k)A^π(S_i,k,l_i,k) gives [Ai∣Si,k,li,k]=G−1G(Qπ(Si,k,li,k)−[Rj∣Si,k]⏟depends on grouping),j≠i.E[A_i S_i,k,l_i,k]= G-1G (Q^π(S_i,k,l_i,k)- E[R_j S_i,k]_depends on grouping ), j≠ i. (12) In the case of same-state grouping, where all trajectories in the group share the same state at turn k, we have [Rj∣Si,k]=Vπ(Si,k)E[R_j S_i,k]=V^π(S_i,k). In this case, the group baseline is anchored to the correct local decision context, and the resulting estimator differs from the true turn-level advantage only by the multiplicative factor (G−1)/G(G-1)/G. However, under cross-state grouping, trajectories within the same group may already reach different states by turn k. Then the baseline is no longer tied to the local state Si,kS_i,k, but is effectively centered around the global mean value as return, i.e., [Rj]=μRE[R_j]= _R. This introduces the additional bias: Biascross=G−1G(Vπ(Si,k)−μR).Bias_cross= G-1G (V^π(S_i,k)- _R ). (13) This bias is determined entirely by the upstream trajectory and has no causal connection to the action taken at turn k. In multi-turn interactions, trajectories often diverge into semantically distinct environment states by turn k. For example, one trajectory may issue a search query while another is executing code. As a result, the variance of Vπ(Si,k)V^π(S_i,k) across states can be large, making the cross-state bias comparable to, or even larger than, the true turn advantage Aπ(Si,k,li,k)A^π(S_i,k,l_i,k). Therefore, a cross-trajectory baseline cannot guarantee a valid local comparison signal for turn-level credit assignment. B.3 Long-horizon policy drift: PPO clipping mismatch asynchronous turns In long-horizon multi-turn training, policy updates can become asynchronous across turns, inducing turn policy drift. In practice, PPO-style methods use token clipping to constrain the IS ratio and limit policy drift during updates. However, this clipping mechanism is designed for near-on-policy updates with synchronized rollout data and does not explicitly account for turn-wise discrepancies when different parts of a trajectory are generated or optimized under different policy versions. Over long horizons, such mismatches can accumulate, shifting the update away from the near-on-policy learning and toward an off-policy setting. This occurs because, in asynchronous multi-turn training, policy updates may be performed before all trajectories have completed their rollouts. For instance, shorter trajectories may complete first and immediately contribute to an update, while longer trajectories are still being generated under an older policy. Specifically, short trajectories may finish first and update the policy from θ0 _0 to θ1 _1, while long trajectories are still being rolled out under πθ0 _ _0. By the time these longer trajectories are used for training, the current policy πθ1 _ _1 no longer matches the policy that generated them. In principle, this mismatch can be corrected by the full trajectory IS ratio: ωi=∏t=1Tiρi,t=∏t=1Tiπθ1(ai,t∣xi,<t)πθ0(ai,t∣xi,<t), _i= _t=1^T_i _i,t= _t=1^T_i _ _1(a_i,t x_i,<t) _ _0(a_i,t x_i,<t), (14) where ρi,t _i,t is the token IS ratio, xi,<tx_i,<t is the flattened multi-turn interaction context preceding token ai,ta_i,t, and TiT_i is the total number of tokens in the flattened trajectory gig_i. Weighting the loss by ωi _i would yield an unbiased correction to the policy objective. However, clipped policy optimization in the PPO/GRPO family does not employ an IS ratio for the full trajectory. Instead, it clips each token ratio ρi,t _i,t independently: ℒclip=∑t=1Timin(ρi,tAi,clip(ρi,t, 1−ϵ, 1+ϵ)Ai).L_clip= _t=1^T_i \! ( _i,t\,A_i,\;clip( _i,t,\,1-ε,\,1+ε)\,A_i ). (15) Therefore, if one composes the clipped token-level ratios into a trajectory-level correction, it generally differs from the true full-trajectory IS ratio: ∏t=1Ticlip(ρi,t, 1−ϵ, 1+ϵ)≠∏t=1Tiρi,t=ωi. _t=1^T_iclip( _i,t,\,1-ε,\,1+ε)≠ _t=1^T_i _i,t= _i. (16) Because PPO clipping is nonlinear, the product of clipped token-level ratios does not equal the true trajectory-level importance weight. In particular, each clipped ratio lies in [1−ϵ, 1+ϵ][1-ε,\,1+ε], so their product is restricted to [(1−ϵ)T,(1+ϵ)T][(1-ε)^T,\,(1+ε)^T], whereas the true ω can in principle take any value in (0,∞)(0,∞). Whenever ω falls outside this interval, per-token clipping necessarily yields a biased trajectory correction. Even when ω lies within the interval, the product of individually clipped ratios will generally differ from ω as soon as any ρt _t is clipped, since clipping and multiplication do not commute. This discrepancy compounds with trajectory length T: as more tokens are clipped, the gap between ∏tclip(ρt) _tclip( _t) and ω can grow progressively larger. Removing clipping and using the exact ω is not a practical solution, because its variance grows exponentially with T, making gradient estimates increasingly uninformative over the long horizons typical of multi-turn agentic RL. Hence, token-level clipping cannot faithfully reproduce the trajectory-level correction required for long-horizon policy drift. Appendix C Method: RTPO Theoretical Proofs C.1 Notation, Formal Problem Setup, and Technical Assumptions Notation convention. We create a multi-turn agentic episode, which consists of K turn-level interactions, written as (q,l0,f0,…,lK−1,fK−1)(q,l_0,f_0,…,l_K-1,f_K-1), where q is the initial prompt, lkl_k is the complete response generated by the agent at turn k, and fkf_k is the external tool or environment feedback returned after executing lkl_k. The turn index is denoted by k∈0,…,K−1k∈\0,…,K-1\, while the token index within a response is denoted by t. When multiple rollouts are sampled, we use i or j to index the rollout or sibling trajectory. Thus, Si,kS_i,k denotes the turn-k state in rollout i, and ai,k,ta_i,k,t denotes the t-th token generated at turn k in rollout i. When no rollout index is needed, we can write SkS_k, lkl_k, and ak,ta_k,t for a generic trajectory. We distinguish between a turn-level macro-action and its token-level realization. The macro-action at turn k is denoted by uk≡lku_k≡ l_k, where lk=(ak,1,…,ak,Tk)l_k=(a_k,1,…,a_k,T_k) is the complete response and TkT_k is the number of generated tokens in that response. The notation uku_k is used in the MDP and value-function definitions, while lkl_k emphasizes that the macro-action is implemented as a language-model response. In addition, the reward in a task is assigned at the turn or trajectory level. Tokens inside a response are treated as the low-level realization of the turn-level macro-action and do not receive separate intermediate rewards. Thus, the low-level token reward is set to zero. We write rkr_k for the immediate turn-level reward at turn k. In sparse-reward tasks, we typically have rk=0r_k=0 for k<K−1k<K-1, and the final task reward is observed only after the terminal turn. Turn-boundary MDP for rollout-training match. A K-turn agentic episode is modelled at turn boundaries as ℳ=⟨¯,H,PH,RH,γH⟩M= X,A_H,P_H,R_H, _H , where ¯ X is the augmented turn-boundary state space, HA_H is the high-level action space of complete responses, PHP_H is the transition kernel induced by executing a complete response and receiving tool feedback, RHR_H is the turn-level reward function, and γH _H is the turn-level discount factor. The augmented state at turn k is x¯k=(Sk,k)∈¯ x_k=(S_k,k)∈ X, where Sk=(q,l0,f0,…,lk−1,fk−1)S_k=(q,l_0,f_0,…,l_k-1,f_k-1) is the interaction history available before the current turn. Adding the turn index k in x¯k x_k can make the process Markov over a finite horizon, since the remaining number of turns can affect both the available decisions and the continuation value. At turn k, the agent selects a macro-action uk≡lk∈H,k(Sk)u_k≡ l_k _H,k(S_k), where H,k(Sk)A_H,k(S_k) denotes the set of feasible complete responses at state SkS_k and turn k. The macro-action is realized autoregressively as lk=(ak,1,…,ak,Tk)l_k=(a_k,1,…,a_k,T_k) and consumes τk=Tk _k=T_k token-generation steps. After executing uku_k and receiving environment feedback fkf_k, the turn-level history is updated by concatenation as Sk+1=Sk∘(lk,fk)S_k+1=S_k (l_k,f_k). Equivalently, since uk≡lku_k≡ l_k, one may write Sk+1=Sk∘(uk,fk)S_k+1=S_k (u_k,f_k). In Sec 3, we adopt this MDP terminology for the turn-boundary process. Strictly speaking, because each macro-action may span a variable number of token-level steps τk _k, this process can alternatively be formulated as a finite-horizon semi-MDP. This distinction does not affect our analysis, since policy optimization and credit assignment are defined exclusively over turn-boundary states and macro-actions. To maintain rollout–training consistency under conditional contexts, the policy need not condition on the full interaction history SkS_k. Instead, it may condition on a compressed or truncated context, provided that the same conditional context is used consistently during both rollout generation and policy optimization. Instead, the actual conditioning context at turn k is ck=ψ(Sk)c_k=ψ(S_k), where ψ may be the identity map, a truncation operator, or a summarization operator. This distinction is important in long-context multi-turn training: rollout may be performed under a truncated or summarized context, while training may otherwise recompute log-probabilities under a different context. RTPO avoids this mismatch by recording the exact context ckc_k used during rollout and reusing the same ckc_k during training. The turn-level policy factorizes as πθ=(πθ,0,…,πθ,K−1) _θ=( _θ,0,…, _θ,K-1), where each sub-policy maps the turn-level context ckc_k to a complete response. Each sub-policy is implemented autoregressively: πθ,k(uk∣ck)=∏t=1Tkπθ(ak,t∣ck,ak,<t). _θ,k(u_k c_k)= _t=1^T_k _θ(a_k,t c_k,a_k,<t). (17) Here, ak,<t=(ak,1,…,ak,t−1)a_k,<t=(a_k,1,…,a_k,t-1) is the token prefix generated within the current turn. Because the same ckc_k is used in rollout and training, the token-level importance-sampling (IS) ratio for turn k is evaluated under matched conditioning contexts: ρk,t=πθ(ak,t∣ck,ak,<t)πθold(ak,t∣ck,ak,<t). _k,t= _θ(a_k,t c_k,a_k,<t) _ _old(a_k,t c_k,a_k,<t). (18) Policy optimization with recursive optimality. A policy sequence πrec=(π0∗,…,πK−1∗)π^rec=( _0^*,…, _K-1^*) is recursively optimal if, for every turn k∈0,…,K−1k∈\0,…,K-1\, the turn-k sub-policy πk∗ _k^* maximizes the turn-level augmented value given that all downstream sub-policies have already been optimized and fixed. Formally, for each k, πk∗∈argmaxπkQ~kπ∗(Sk,uk) _k^*∈ _ _k Q_k^π^*(S_k,u_k), where the downstream policies πk+1∗,…,πK−1∗ _k+1^*,…, _K-1^* are treated as fixed during the optimization of πk∗ _k^*. This is a backward-induction notion of optimality: the last turn is optimized first, then the preceding turn is optimized assuming the last-turn policy is fixed, and so on until the first turn. Furthermore, we establish convergence to recursive optimality in a tabular finite-horizon setting. Assumptions below (A1–A10) are not intended to model the full neural implementation, but instead serve to isolate the theoretical effect of reverse-order turn-level policy optimization under standard stochastic approximation conditions. (A1) Finite turn-boundary spaces. The augmented state space ¯ X is finite, and for every turn k and every reachable state SkS_k, the feasible high-level action set H,k(Sk)A_H,k(S_k) is finite. (A2) Proper finite-horizon episodes. The number of turns K is finite. For every policy and every turn k, the macro-action duration satisfies πk[τk]<∞E_ _k[ _k]<∞. Thus, each turn terminates almost surely in a finite expected token length. (A3) Discounting or finite-horizon boundedness. Either γH∈(0,1) _H∈(0,1), or the problem is finite-horizon with K<∞K<∞ and γH∈(0,1] _H∈(0,1]. The latter case includes the undiscounted finite-horizon setting γH=1 _H=1. (A4) Tabular value representation. The value estimate Qk(S,u)Q_k(S,u) is stored separately for each turn-state-action tuple (S,u,k)(S,u,k). This assumption avoids approximation error and allows the proof to focus on the stochastic approximation dynamics induced by reverse-order updates. (A5) Reverse-order training with downstream freezing. Training is proceeding in the order k=K−1,K−2,…,0k=K-1,K-2,…,0. During turn k, the turn-k policy is updated while the downstream policies πk+1:K−1 _k+1:K-1 are held fixed. After turn k is completed, the turn-k policy is also frozen before moving to turn k−1k-1. (A6) GLIE exploration within each turn. Within turn k, the exploration schedule is greedy in the limit with infinite exploration (GLIE): every feasible turn-level action is selected with strictly positive probability infinitely often, while the policy becomes greedy in the limit. This ensures that all relevant action values at turn k are sufficiently sampled before the policy is frozen. (A7) State coverage. Every reachable boundary state SkS_k that can arise under the training process is visited infinitely often during turn k. This condition ensures that the tabular value estimate for each relevant state-action pair receives infinitely many updates. (A8) Robbins–Monro step sizes. For every tuple (S,u,k)(S,u,k), the learning rates satisfy ∑n=1∞αn(S,u,k)=∞ _n=1^∞ _n(S,u,k)=∞ and ∑n=1∞αn2(S,u,k)<∞ _n=1^∞ _n^2(S,u,k)<∞. These are the standard stochastic approximation step-size conditions. (A9) Bounded rewards. The turn-level rewards are uniformly bounded: |rk|≤rmax|r_k|≤ r_ almost surely for all k. (A10) Bounded iterates. The tabular value iterates remain uniformly bounded: |Qk(S,u)|≤Qmax|Q_k(S,u)|≤ Q_ throughout learning. This assumption is standard in stochastic approximation analyses and can be enforced by projection if necessary. (A11) Decision sufficiency of the conditioning context. The observation mapping ψ:Sk↦ckψ S_k c_k preserves all decision-relevant information for following turns. In other words, states that are indistinguishable under ψ share the same optimal action-value function, so the optimal policy at turn k depends on SkS_k only through ckc_k. This implies that Q~kπ∗ Q_k^π^* can be written as a function of (ck,u)(c_k,u) without loss, and the completeness condition Πglobal⊆(π0,…,πK−1):πk(⋅∣ck) _global \( _0,…, _K-1): _k(· c_k)\ in Theorem 1(c) is automatically satisfied. Assumptions (A1)–(A10) are standard regularity conditions for the convergence of reinforcement learning algorithms; identical or closely analogous conditions appear in the foundational convergence proofs of Q-learning [54, 51, 21], on-policy GLIE control [47], and the systematic treatment in 3. They are not specific to RTPO but rather constitute the minimal set of conditions under which any stochastic-approximation-based value-learning algorithm is known to converge. These assumptions (A1–A11) are intentionally stronger than those required in the practical neural network implementation. They are used to make the convergence argument mathematically clean in the tabular setting. In the realistic RTPO implementation, the policy is represented by a shared neural language model rather than by independent tabular sub-policies. Therefore, “freezing” a turn-level sub-policy should be interpreted operationally: after a turn is completed, subsequent turns mask out the corresponding turn tokens from the loss, so that those turn-level decisions no longer receive gradients. The tabular analysis should thus be read as an idealized counterpart that clarifies the role of reverse-turn optimization and downstream-policy freezing, rather than as a claim of global convergence for arbitrary neural function approximation. The extension to neural function approximation is discussed separately in Proposition C.2. We do not rely on the universal approximation property alone to claim convergence of the neural algorithm; instead, the tabular result serves as a principled limiting case that motivates the reverse-turn training design. Verification of decision sufficiency (A11) in RTPO. In the practical RTPO implementation, ψ corresponds to the chat-template truncation operator that removes the model’s internal reasoning trace (the content of <think> blocks) while preserving all externally observable elements: tool calls, tool results, and final answers. Two states SkS_k and Sk′S_k that differ only in their internal reasoning traces satisfy ψ(Sk)=ψ(Sk′)ψ(S_k)=ψ(S_k ). Since the environment transition kernel PHP_H depends exclusively on the executed tool calls and the returned feedback, not on the model’s internal reasoning, the next-state distribution and thus the continuation value Fkπ∗(Sk+1)F_k^π^*(S_k+1) are identical for SkS_k and Sk′S_k . The turn-level reward rkr_k likewise depends only on the externally observable action. Therefore, Q~kπ∗(Sk,u)=Q~kπ∗(Sk′,u) Q_k^π^*(S_k,u)= Q_k^π^*(S_k ,u) for all u, and Assumption (A11) is satisfied. When ψ is the identity map (full-history conditioning), (A11) holds trivially. Turn-level value estimation. We formulate the interaction as a hierarchical MDP, which decomposes the value of each turn into the local effect of the current macro-action and the downstream completion value, following a MAXQ-style value decomposition. The downstream continuation value after executing turn k is defined as Fkπ(Sk+1):=π[∑j=k+1K−1γH∑m=k+1j−1τmrj|Sk+1],FK−1π≡0.F_k^π(S_k+1):=E_π\! [ _j=k+1^K-1 _H _m=k+1^j-1 _mr_j\; |\;S_k+1 ], F_K-1^π≡ 0. (19) The base case FK−1π≡0F_K-1^π≡ 0 reflects that there are no downstream turns after the last turn. The exponent ∑m=k+1j−1τm _m=k+1^j-1 _m accounts for the number of token-generation steps elapsed between the next state Sk+1S_k+1 and the future reward rjr_j. When γH=1 _H=1, this reduces to the undiscounted finite-horizon setting used in many sparse-reward agentic RL tasks. The boundary-level augmented action-value function is: Q~kπ(Sk,uk):=[rk+γHτkFkπ(Sk+1)|Sk,uk]. Q_k^π(S_k,u_k):=E\! [r_k+ _H _kF_k^π(S_k+1)\; |\;S_k,u_k ]. (20) This value measures the expected return obtained by choosing the complete turn-k response uku_k at state SkS_k, followed by downstream policy execution from Sk+1S_k+1 onward. In sparse-reward settings, the immediate term rkr_k is often zero for nonterminal turns, so the quality of a turn-level action is primarily reflected through the downstream continuation value. The corresponding optimal value satisfies Q~k∗(Sk,uk)=[rk+γHτkFk∗(Sk+1)∣Sk,uk] Q_k^*(S_k,u_k)=E[r_k+ _H _kF_k^*(S_k+1) S_k,u_k], where Fk∗F_k^* is obtained by the usual backward Bellman optimality recursion over turn boundaries. C.2 Proof of Theorem 1: Convergence to Recursive Optimality We formalize Theorem 1 from Sec 3.1 before presenting the proof. Reverse-Order Training to Recursive Optimality Theorem 1 (Convergence to Recursive Optimality). Under Assumptions (A1)–(A10), including finite state and macro-action spaces, Robbins–Monro step sizes, sufficient exploration at each turn, exact freezing of optimized downstream policies, and bounded rewards, the reverse-order backward induction of turn-level policy optimization satisfies the following properties: (a) Per-turn convergence under fixed downstream policies. For each turn k, once the downstream policies πk+1:K−1∗ _k+1:K-1^* are fixed, the downstream continuation value becomes a stationary function: Fkπ∗(Sk+1)=π∗k+1:K−1[∑j=k+1K−1γH∑m=k+1j−1τmrj|Sk+1].F_k^π^*(S_k+1)=E_π^*_k+1:K-1\! [ _j=k+1^K-1 _H _m=k+1^j-1 _mr_j\; |\;S_k+1 ]. (21) Therefore, the turn-k target Yk:=rk+γHτkFkπ∗(Sk+1)Y_k:=r_k+ _H _kF_k^π^*(S_k+1) (22) is stationary conditional on (Sk,uk)(S_k,u_k), with conditional mean [Yk∣Sk,uk]=Q~kπ∗(Sk,uk).E[Y_k S_k,u_k]= Q_k^π^*(S_k,u_k). (23) The corresponding tabular update Qk(n+1)(S,u)←(1−αn)Qk(n)(S,u)+αnYkQ_k^(n+1)(S,u)←(1- _n)Q_k^(n)(S,u)+ _nY_k (24) is a single-step stochastic approximation problem and converges to Q~kπ∗ Q_k^π^* under the stated assumptions. Hence, the learned per-turn policy satisfies π^k→a.s.πk∗ π_k a.s. _k^*. (b) Recursive optimality under reverse-order training. Applying the per-turn convergence argument in reverse order, k=K−1,K−2,…,0,k=K-1,K-2,…,0, (25) yields a sequence of optimized and frozen downstream policies. At each turn k, the per-turn optimizer converges to πk∗(Sk)∈argmaxuk∈H,k(Sk)Q~kπ∗(Sk,uk), _k^*(S_k)∈ _u_k _H,k(S_k) Q_k^π^*(S_k,u_k), (26) given the fixed downstream policies πk+1∗,…,πK−1∗ _k+1^*,…, _K-1^*. The resulting policy sequence πrec=(π0∗,…,πK−1∗)π^rec=( _0^*,…, _K-1^*) (27) is recursively optimal. (c) Global optimality under context-sufficient macro-action completeness. If the turn-level macro-action spaces are complete with respect to the conditioning contexts ck=ψ(Sk)c_k=ψ(S_k), i.e., every globally feasible trajectory-level policy can be represented by a sequence of turn-level policies acting on these contexts, Πglobal⊆(π0,…,πK−1):πk(⋅∣ck),uk∈H,k(Sk), _global \( _0,…, _K-1): _k(· c_k),\;u_k _H,k(S_k) \, (28) Then, recursive optimality is equivalent to global optimality over the full trajectory: Vπrec(x¯0)=V∗(x¯0).V^π^rec( x_0)=V^*( x_0). (29) Proof. We prove parts (a)–(c) of Theorem 1 as follows. Proof of Theorem 1(a): per-turn convergence under fixed downstream policies. Fix a turn k and suppose the downstream sub-policies πk+1∗,…,πK−1∗ _k+1^*,…, _K-1^* are already optimized and frozen. By the definition in Theorem 1, the downstream continuation value is Fkπ∗(Sk+1)=π∗k+1:K−1[∑j=k+1K−1γH∑m=k+1j−1τmrj|Sk+1].F_k^π^*(S_k+1)=E_π^*_k+1:K-1\! [ _j=k+1^K-1 _H _m=k+1^j-1 _mr_j\; |\;S_k+1 ]. (30) Because the downstream policies πk+1:K−1∗ _k+1:K-1^* are frozen, Fkπ∗(Sk+1)F_k^π^*(S_k+1) is a fixed function of Sk+1S_k+1 throughout turn k. Define the augmented one-step target Yk=rk+γHτkFkπ∗(Sk+1).Y_k=r_k+ _H _kF_k^π^*(S_k+1). (31) Conditional on (Sk,uk)(S_k,u_k), the distribution of rkr_k, τk _k, and Sk+1S_k+1 is induced by the time-invariant turn-boundary transition kernel PHP_H. Since Fkπ∗F_k^π^* is fixed throughout turn k, the conditional distribution of YkY_k given (Sk,uk)(S_k,u_k) is stationary. The conditional mean of the target is exactly the augmented turn-level action value: [Yk∣Sk,uk]=[rk+γHτkFkπ∗(Sk+1)|Sk,uk]=Q~kπ∗(Sk,uk).E[Y_k S_k,u_k]=E\! [r_k+ _H _kF_k^π^*(S_k+1)\; |\;S_k,u_k ]= Q_k^π^*(S_k,u_k). (32) The target also has a bounded second moment. Since rewards are bounded, |rj|≤rmax|r_j|≤ r_ almost surely. Hence, for any policy π, |Fkπ(Sk+1)| |F_k^π(S_k+1) | =|π[∑j=k+1K−1γH∑m=k+1j−1τmrj|Sk+1]| = |E_π\! [ _j=k+1^K-1 _H _m=k+1^j-1 _mr_j\; |\;S_k+1 ] | ≤π[∑j=k+1K−1γH∑m=k+1j−1τm|rj||Sk+1] _π\! [ _j=k+1^K-1 _H _m=k+1^j-1 _m|r_j|\; |\;S_k+1 ] ≤(K−k−1)rmax≤Krmax, ≤(K-k-1)r_ ≤ Kr_ , (33) where we used γH∈(0,1] _H∈(0,1] and the finite horizon K. Therefore, |Yk|≤|rk|+γHτk|Fkπ∗(Sk+1)|≤(K+1)rmax,|Y_k|≤|r_k|+ _H _k|F_k^π^*(S_k+1)|≤(K+1)r_ , (34) so YkY_k has uniformly bounded conditional second moment. During turn k, the tabular update is Qk(n+1)(S,u)←(1−αn)Qk(n)(S,u)+αnYk.Q_k^(n+1)(S,u)←(1- _n)Q_k^(n)(S,u)+ _nY_k. (35) For each fixed (S,u,k)(S,u,k), this is a Robbins–Monro stochastic approximation to the stationary conditional mean [Yk∣S,u]=Q~kπ∗(S,u)E[Y_k S,u]= Q_k^π^*(S,u). The finite state and macro-action spaces imply that there are finitely many entries to estimate. Sufficient exploration ensures that every relevant (S,u)(S,u) pair is visited infinitely often during turn k. The step sizes satisfy ∑n=1∞αn(S,u,k)=∞,∑n=1∞αn2(S,u,k)<∞. _n=1^∞ _n(S,u,k)=∞, _n=1^∞ _n^2(S,u,k)<∞. (36) Together with bounded targets and bounded iterates, standard stochastic approximation gives Qk(n)(S,u)→a.s.Q~kπ∗(S,u)for every reachable (S,u).Q_k^(n)(S,u) a.s. Q_k^π^*(S,u) every reachable (S,u). (37) As exploration vanishes, the induced greedy policy converges to an optimal greedy selector: π^k(S)∈argmaxuQk(n)(S,u)⟹π^k(S)→a.s.πk∗(S)∈argmaxuQ~kπ∗(S,u). π_k(S)∈ _uQ_k^(n)(S,u) π_k(S) a.s. _k^*(S)∈ _u Q_k^π^*(S,u). (38) This completes the proof of Theorem 1(a). Proof of Theorem 1(b): reverse-order recursion gives recursive optimality. We now apply Theorem 1(a) in reverse order here. At the final turn k=K−1k=K-1, there are no downstream turns, so FK−1π(SK)≡0.F_K-1^π(S_K)≡ 0. (39) The augmented target reduces to YK−1=rK−1.Y_K-1=r_K-1. (40) By claim Theorem 1(a), the final-turn policy converges: π^K−1→a.s.πK−1∗. π_K-1 a.s. _K-1^*. (41) Now assume that for some k∈0,…,K−2k∈\0,…,K-2\, the downstream policies π^k+1,…,π^K−1 π_k+1,…, π_K-1 have already converged almost surely to πk+1∗,…,πK−1∗ _k+1^*,…, _K-1^* and have been frozen before turn k begins. Then the continuation value Fkπ∗(Sk+1)=π∗k+1:K−1[∑j=k+1K−1γH∑m=k+1j−1τmrj|Sk+1]F_k^π^*(S_k+1)=E_π^*_k+1:K-1\! [ _j=k+1^K-1 _H _m=k+1^j-1 _mr_j\; |\;S_k+1 ] (42) is fixed throughout turn k. Therefore, claim (a) applies to turn k, giving π^k→a.s.πk∗,πk∗(Sk)∈argmaxukQ~kπ∗(Sk,uk). π_k a.s. _k^*, _k^*(S_k)∈ _u_k Q_k^π^*(S_k,u_k). (43) By backward induction from K−1K-1 to 00, every turn-level policy converges to its optimal selector given the optimized and frozen downstream policies. Therefore, the resulting sequence πrec=(π0∗,…,πK−1∗)π^rec=( _0^*,…, _K-1^*) (44) is recursively optimal. Till here, we have completed the proof of Theorem 1(b). Proof of Theorem 1(c): context-sufficient macro-action completeness implies global optimality. Assume the turn-level macro-action spaces are complete with respect to the conditioning contexts ck=ψ(Sk)c_k=ψ(S_k), meaning that every globally feasible trajectory-level policy can be represented as a sequence of turn-level sub-policies (π0,…,πK−1)( _0,…, _K-1), with each πk _k acting on ckc_k and selecting a feasible macro-action uk∈H,k(Sk)u_k _H,k(S_k). We prove by backward induction that Vkπrec(Sk)=Vk∗(Sk)for every reachable Sk.V_k^π^rec(S_k)=V_k^*(S_k) every reachable S_k. (45) At the last turn, FK−1π≡0F_K-1^π≡ 0, so Q~K−1π(SK−1,u)=[rK−1∣SK−1,u]. Q_K-1^π(S_K-1,u)=E[r_K-1 S_K-1,u]. (46) Since πK−1∗ _K-1^* maximizes this quantity, VK−1πrec(SK−1)=maxu∈H,K−1(SK−1)[rK−1∣SK−1,u]=VK−1∗(SK−1).V_K-1^π^rec(S_K-1)= _u _H,K-1(S_K-1)E[r_K-1 S_K-1,u]=V_K-1^*(S_K-1). (47) Assume now that Vk+1πrec(Sk+1)=Vk+1∗(Sk+1)V_k+1^π^rec(S_k+1)=V_k+1^*(S_k+1) for every reachable Sk+1S_k+1. Then Fkπrec(Sk+1)=Fk∗(Sk+1).F_k^π^rec(S_k+1)=F_k^*(S_k+1). (48) By Assumption (A11), the optimal action-value Q~kπ∗(Sk,u) Q_k^π^*(S_k,u) depends on SkS_k only through ck=ψ(Sk)c_k=ψ(S_k). Therefore, the greedy policy πk∗∈argmaxuQ~kπ∗(Sk,u) _k^*∈ _u Q_k^π^*(S_k,u) is well-defined as a function of ckc_k alone, and we write πk∗(ck) _k^*(c_k) without ambiguity. Applying this to the inductive step: Vkπrec(Sk) V_k^π^rec(S_k) =Q~kπrec(Sk,πk∗(ck)) = Q_k^π^rec (S_k, _k^*(c_k) ) =[rk+γHτkFkπrec(Sk+1)|Sk,πk∗(Sk)] =E\! [r_k+ _H _kF_k^π^rec(S_k+1)\; |\;S_k, _k^*(S_k) ] =[rk+γHτkFk∗(Sk+1)|Sk,πk∗(Sk)] =E\! [r_k+ _H _kF_k^*(S_k+1)\; |\;S_k, _k^*(S_k) ] =maxu∈H,k(Sk)[rk+γHτkFk∗(Sk+1)|Sk,u] = _u _H,k(S_k)E\! [r_k+ _H _kF_k^*(S_k+1)\; |\;S_k,u ] =Vk∗(Sk). =V_k^*(S_k). (49) Thus Vkπrec(Sk)=Vk∗(Sk)V_k^π^rec(S_k)=V_k^*(S_k) for all k by induction. In particular, Vπrec(x¯0)=V∗(x¯0).V^π^rec( x_0)=V^*( x_0). (50) This proves Theorem 1(c), and completes the proof of Theorem 1. ∎ Interpretation. As the key technical point of this proof, turn-k target Yk=rk+γHτkFkπ∗(Sk+1)Y_k=r_k+ _H _kF_k^π^*(S_k+1) is stationary only, when the downstream policies πk+1∗,…,πK−1∗ _k+1^*,…, _K-1^* are already optimized and frozen. Reverse-order training provides exactly this condition. Without reverse-order freezing, FkπF_k^π would change during turn k, the target YkY_k would no longer be stationary, and the single-turn stochastic approximation argument would not apply. Proposition of Theorem 1: Asymptotic recursive optimality under neural function approximation. The convergence guarantee in Theorem 1 relies on Assumption (A4) from Appendix C.1, which postulates a tabular representation of QkQ_k. In the practical implementation of RTPO, QkQ_k is realized implicitly by a neural sub-policy πθk _ _k operating on the conditioning context ck=ψ(Sk)c_k=ψ(S_k). We now state the corresponding asymptotic guarantee under the neural function approximation; the proof follows the standard reduction from tabular Q-learning to projected Q-learning under a function class ℱθF_θ. This statement is formalized as a Proposition, which appears below as a neural-function-approximation extension of Theorem 1. Proposition of Theorem 1: Asymptotic recursive optimality under neural function approximation. Suppose the assumptions of Theorem 1 hold, with current assumption (A4) from Appendix C.1 replaced by new assumption (A4’) below: (A4’) Universal approximation. For every fixed Fkπ∗F_k^π^*, there exists θk∗∈Θ _k^*∈ such that the induced greedy policy πθk∗ _ _k^* realizes πk∗ _k^* on every reachable SkS_k in the support of the visitation distribution. Then, reverse-order training of RTPO produces a policy sequence (π^0,…,π^K−1)( π_0,…, π_K-1) that asymptotically realizes the recursively optimal policy. That is, for every k and every reachable SkS_k, limn→∞πθk(n)(⋅∣ck)=πk∗(⋅∣ck)a.s. _n→∞ _ _k^(n)(· c_k)= _k^*(· c_k) .s. Proof: Proposition of Theorem 1. Step 1. Reduction to projected Q-learning: Replace the tabular update with a parametric update on the function class πθk:θk∈Θ\ _ _k: _k∈ \, θk(n+1)←θk(n)−αn∇θk(S,u)∼μn[(Qθk(n)(S,u)−r~k)2], _k^(n+1)← _k^(n)- _n\, _ _kE_(S,u) _n\! [ (Q_ _k^(n)(S,u)- r_k )^2 ], (51) where μn _n is the visitation distribution induced by the current greedy-with-exploration policy and QθkQ_ _k is the implicit Q-function realized by πθk _ _k. The fixed point of this update is the projection of Q~k∗ Q_k^* onto the function class, ΠΘQ~k∗ _ Q_k^*, in the weighted L2(μ)L^2(μ) sense. Step 2: Asymptotic realizability: By assumption (A4’), there exists θk∗∈Θ _k^*∈ such that the induced greedy policy realizes πk∗ _k^* on every reachable SkS_k in the support of μ. This implies ΠΘQ~k∗=Q~k∗ _ Q_k^*\;=\; Q_k^* on the support of μ, so the projection error vanishes for the quantities relevant to the induced greedy policy. Combined with standard asymptotic results for stochastic gradient descent on smooth nonconvex objectives under Robbins–Monro step sizes [39], Qθk(n)(S,u)→Q~k∗(S,u)Q_ _k^(n)(S,u)→ Q_k^*(S,u) a.s. for every (S,u)(S,u) in the support of μ. Step 3. Backward induction in the function-class regime: Replace each step in the proof of Theorem 1 by Steps 1–2 above. The reverse induction structure is unchanged: the determinism of Fkπ∗F_k^π^* under frozen downstream sub-policies is purely a property of the SMDP and the freezing schedule (A5), independent of whether QkQ_k is tabular or parametric. Hence, the backward induction goes through and yields πθk(n)→πk∗ _ _k^(n)→ _k^* a.s. on the support of μ for every k. ∎ Remark on the assumption gap between (A4) and (A4’). Assumption (A4’) is strictly weaker than what would be required for finite-sample convergence rates: it asks only that the function class be rich enough to contain the optimal sub-policy in the asymptotic limit, not that the gradient dynamics realize this optimum at any finite iteration. For the modern Transformer architectures used in our experiments with Qwen3 models, the universal approximation property is widely accepted as a working assumption, and our experimental results in Sec 4 provide empirical evidence that the asymptotic guarantee transfers to practice. C.3 Proof of Theorem 2: Causally Consistent Turn-Level Advantage Estimation We formalize Theorem 2 from Sec 3.2 before presenting the proof. We compare the state-matched sibling advantage estimator used by RTPO with the trajectory-level advantage estimator used in flat-trajectory training. The key distinction is whether the baseline is computed from rollouts sharing the same boundary state SkS_k, or from complete trajectories that may have reached different boundary states by turn k. Turn-Level Credit Assignment without State Bias Theorem 2 (Causally Consistent Turn-Level Advantage Estimation). Consider turn k and suppose that G−1G-1 sibling rollouts are forked from the same boundary state SkS_k. Each sibling rollout j∈1,…,G−1j∈\1,…,G-1\ independently samples a turn-k macro-action uj,k≡lj,ku_j,k≡ l_j,k and then continues to the terminal. Let Q^j,k=Rj,V^k=1G−1∑j=1G−1Q^j,k,Aj,kH=Q^j,k−V^k Q_j,k=R_j, V_k= 1G-1 _j=1^G-1 Q_j,k, A^H_j,k= Q_j,k- V_k (52) denote the Monte Carlo turn-level action-value estimate, the state-matched sibling baseline, and the resulting turn-level advantage for sibling rollout j, respectively. Let the corresponding flat trajectory-level estimator be R¯=1G∑i=1GRi,Aitraj=Ri−R¯, R= 1G _i=1^GR_i, A_i^traj=R_i- R, (53) where gig_i denotes the i-th complete trajectory and Si,kS_i,k is its boundary state at turn k. Define Qπ(Sk,uj,k)=[R∣Sk,uj,k],Vπ(Sk)=u∼π(⋅∣ck)[Qπ(Sk,u)],Q^π(S_k,u_j,k)=E[R S_k,u_j,k], V^π(S_k)=E_u π(· c_k)[Q^π(S_k,u)], (54) and Aπ(Sk,uj,k)=Qπ(Sk,uj,k)−Vπ(Sk),μR=[R].A^π(S_k,u_j,k)=Q^π(S_k,u_j,k)-V^π(S_k), _R=E[R]. (55) Then, under bounded rewards and independent sibling sampling, the RTPO sibling advantage estimator satisfies the following properties: (a) Local unbiasedness up to finite-group bias. Conditional on the shared boundary state SkS_k and the sampled macro-action uj,ku_j,k, the state-matched sibling estimator satisfies: [Aj,kH∣Sk,uj,k]=G−2G−1Aπ(Sk,uj,k).E\! [A^H_j,k S_k,u_j,k ]= G-2G-1A^π(S_k,u_j,k). (56) Thus, Aj,kHA^H_j,k estimates the true turn-level advantage up to a finite-group bias of order O(1/G)O(1/G) and contains no upstream state-contamination term. In contrast, the trajectory-level estimator satisfies: [Aitraj∣Si,k,ui,k]=G−1GAπ(Si,k,ui,k)+G−1G(Vπ(Si,k)−μR),E\! [A_i^traj S_i,k,u_i,k ]= G-1GA^π(S_i,k,u_i,k)+ G-1G (V^π(S_i,k)- _R ), (57) where the second term is the upstream state-contamination term. (b) Reduced value estimation error. Let σV2:=VarSk[Vπ(Sk)] _V^2:=Var_S_k\! [V^π(S_k) ] (58) denote the variance of boundary-state values. Compared with the trajectory-level estimator, the sibling estimator removes the cross-state value component Vπ(Si,k)−μRV^π(S_i,k)- _R. Therefore, under a matched downstream-noise comparison, the trajectory estimator contains an additional MSE contribution proportional to σV2 _V^2, while the sibling estimator does not. In particular, when σV2>0 _V^2>0, the state-matched estimator removes a non-zero source of value-estimation error induced by cross-state baselines. (c) State-matched causal actions. All sibling rollouts share the same boundary state SkS_k. Therefore, differences in their returns are attributable to the sampled turn-k macro-actions uj,ku_j,k and independent downstream sampling noise, rather than to upstream trajectory differences. The resulting advantage Aj,kHA^H_j,k is assigned only to the output tokens of turn k, lj,k=(aj,k,1,…,aj,k,Tj,k),l_j,k=(a_j,k,1,…,a_j,k,T_j,k), (59) while the prefix tokens contained in the shared context ck=ψ(Sk)c_k=ψ(S_k) are excluded from the gradient. Proof. We prove parts (a)–(c) of Theorem 2 as follows. Proof of Theorem 2(a): local unbiasedness up to finite-group bias. Fix a turn k and a shared boundary state SkS_k. RTPO forks G−1G-1 sibling rollouts from the same environment snapshot snapksnap_k. Conditional on SkS_k, each sibling rollout independently samples its turn-k macro-action and downstream continuation. Thus, for any two distinct sibling rollouts j≠j′j≠ j , the return Rj′R_j of sibling j′j is conditionally independent of the action uj,ku_j,k sampled by sibling j: Rj′⟂uj,k|Sk.R_j \!\!\! u_j,k S_k. (60) Consequently, [Rj′∣Sk,uj,k]=[Rj′∣Sk]=Vπ(Sk).E[R_j S_k,u_j,k]=E[R_j S_k]=V^π(S_k). (61) Meanwhile, for the own return of sibling j, [Rj∣Sk,uj,k]=Qπ(Sk,uj,k).E[R_j S_k,u_j,k]=Q^π(S_k,u_j,k). (62) By definition, Aj,kH A^H_j,k =Rj−1G−1∑r=1G−1Rr =R_j- 1G-1 _r=1^G-1R_r =G−2G−1Rj−1G−1∑r≠jRr. = G-2G-1R_j- 1G-1 _r≠ jR_r. (63) Taking conditional expectation given (Sk,uj,k)(S_k,u_j,k) and using Eq. (61) and Eq. (62), [Aj,kH∣Sk,uj,k] [A^H_j,k S_k,u_j,k] =G−2G−1Qπ(Sk,uj,k)−G−2G−1Vπ(Sk) = G-2G-1Q^π(S_k,u_j,k)- G-2G-1V^π(S_k) =G−2G−1(Qπ(Sk,uj,k)−Vπ(Sk)) = G-2G-1 (Q^π(S_k,u_j,k)-V^π(S_k) ) =G−2G−1Aπ(Sk,uj,k). = G-2G-1A^π(S_k,u_j,k). (64) Therefore, the sibling estimator is locally unbiased up to the finite-group multiplicative factor (G−2)/(G−1)(G-2)/(G-1). Equivalently, the conditional bias relative to the true turn-level advantage is [Aj,kH∣Sk,uj,k]−Aπ(Sk,uj,k)=−1G−1Aπ(Sk,uj,k),E[A^H_j,k S_k,u_j,k]-A^π(S_k,u_j,k)=- 1G-1A^π(S_k,u_j,k), (65) which is O(1/G)O(1/G) and contains no term depending on Vπ(Sk)−μRV^π(S_k)- _R. We now contrast this with the trajectory-level estimator. In flat-trajectory training, the G trajectories are independently sampled from the same prompt but may reach different boundary states by turn k. The trajectory-level advantage is Aitraj A_i^traj =Ri−1G∑r=1GRr =R_i- 1G _r=1^GR_r =G−1GRi−1G∑r≠iRr. = G-1GR_i- 1G _r≠ iR_r. (66) The own return satisfies [Ri∣Si,k,ui,k]=Qπ(Si,k,ui,k).E[R_i S_i,k,u_i,k]=Q^π(S_i,k,u_i,k). (67) For r≠ir≠ i, trajectory r is generated by an independent upstream rollout and reaches its own boundary state Sr,kS_r,k. Thus, [Rr∣Si,k,ui,k]=Sr,k[Vπ(Sr,k)]=μR.E[R_r S_i,k,u_i,k]=E_S_r,k\! [V^π(S_r,k) ]= _R. (68) Substituting Eq. (67) and Eq. (68) into Eq. (66) gives [Aitraj∣Si,k,ui,k] [A_i^traj S_i,k,u_i,k] =G−1G(Qπ(Si,k,ui,k)−μR) = G-1G (Q^π(S_i,k,u_i,k)- _R ) =G−1G(Qπ(Si,k,ui,k)−Vπ(Si,k))+G−1G(Vπ(Si,k)−μR) = G-1G (Q^π(S_i,k,u_i,k)-V^π(S_i,k) )+ G-1G (V^π(S_i,k)- _R ) =G−1GAπ(Si,k,ui,k)+G−1G(Vπ(Si,k)−μR). = G-1GA^π(S_i,k,u_i,k)+ G-1G (V^π(S_i,k)- _R ). (69) The second term in Eq. (69) depends only on the upstream boundary state Si,kS_i,k and the global mean return μR _R. It has no causal dependence on the current turn action ui,ku_i,k and is precisely the cross-state contamination term. Therefore, the sibling estimator removes the upstream state-contamination term present in the trajectory-level estimator. This proves part (a) of Theorem 2. Proof of Theorem 2(b): reduced value estimation error. We compare the error of each estimator against its corresponding true turn-level advantage. For the sibling estimator, the target is Aπ(Sk,uj,k)A^π(S_k,u_j,k); for the trajectory estimator, the target is Aπ(Si,k,ui,k)A^π(S_i,k,u_i,k). The trajectory estimator contains the additional cross-state term Ci,k:=G−1G(Vπ(Si,k)−μR),C_i,k:= G-1G (V^π(S_i,k)- _R ), (70) whereas the sibling estimator does not contain such a term. Marginalizing over the boundary-state distribution, [Ci,k]=0,Var(Ci,k)=(G−1G)2VarSk[Vπ(Sk)]=(G−1G)2σV2.E[C_i,k]=0, (C_i,k)= ( G-1G )^2Var_S_k\! [V^π(S_k) ]= ( G-1G )^2 _V^2. (71) Thus, cross-trajectory baselines introduce an additional MSE component proportional to σV2 _V^2, while state-matched sibling baselines remove it. In addition to the squared-bias contribution above, the trajectory-level baseline R¯=1G∑r≠iRr R= 1G _r≠ iR_r introduces further variance from cross-state effects. Conditional on (Si,k,ui,k)(S_i,k,u_i,k), each RrR_r (r≠ir≠ i) is independent of the conditioning, so its conditional variance equals its unconditional variance: Var(Rr∣Si,k,ui,k)=Var(Rr)=Sr,k[Var(Rr∣Sr,k)]⏟σ¯down2+σV2,Var(R_r S_i,k,u_i,k)=Var(R_r)= E_S_r,k\! [Var(R_r S_r,k) ]_ σ_down^2+\; _V^2, (72) where the σV2 _V^2 term arises because Sr,kS_r,k varies across trajectories. This contributes G−1G2σV2 G-1G^2 _V^2 to the conditional variance of AitrajA_i^traj. By contrast, in the sibling estimator, all returns share the same boundary state SkS_k, so Var(Rr∣Sk)Var(R_r S_k) is a purely within-state quantity and contains no σV2 _V^2 component. More explicitly, the mean squared error can be decomposed as MSE(A^)=Var(A^)+Bias(A^)2.MSE( A)=Var( A)+Bias( A)^2. (73) For the trajectory estimator, the bias contains the cross-state term Ci,kC_i,k from Eq. (70). For the sibling estimator, the only systematic bias from part (a) is the finite-group term −1G−1Aπ(Sk,uj,k),- 1G-1A^π(S_k,u_j,k), (74) which is O(1/G)O(1/G). Therefore, under a matched downstream-noise comparison, the total σV2 _V^2 coefficient in the trajectory estimator’s marginal MSE combines the squared-bias contribution (Eq. (71)) with the baseline-variance contribution (Eq. (72)): (G−1G)2⏟Bias2+G−1G2⏟Var=(G−1)2+(G−1)G2=G−1G. ( G-1G )^\!2_Bias^2+\; G-1G^2_Var\;=\; (G-1)^2+(G-1)G^2\;=\; G-1G. (75) The sibling estimator incurs no σV2 _V^2 contribution from either source. The leading MSE difference is thus: MSE(Aitraj)−MSE(Aj,kH)=G−1GσV2+Δdown−O(1/G2),MSE(A_i^traj)-MSE(A^H_j,k)= G-1G\, _V^2+ _down-O(1/G^2), (76) where Δdown≥0 _down≥ 0 collects differences in downstream Monte Carlo noise between the two estimators under matched conditions. Hence, whenever σV2>0 _V^2>0, the state-matched sibling estimator has strictly lower MSE. This proves part (b) of Theorem 2. Proof of Theorem 2(c): state-matched causal actions. All sibling rollouts are forked from the same boundary state SkS_k. Therefore, conditional on SkS_k, sibling rollout j and sibling rollout j′j differ only in their sampled turn-k macro-actions and their independent downstream randomness: (uj,k,ξj)versus(uj′,k,ξj′),(u_j,k, _j) (u_j ,k, _j ), (77) where ξj _j denotes the downstream randomness of sibling j. Since the shared prefix state SkS_k is identical across siblings, any systematic difference in conditional expected return is attributable to the sampled turn-k macro-action: [Rj−Rj′∣Sk,uj,k,uj′,k]=Qπ(Sk,uj,k)−Qπ(Sk,uj′,k).E[R_j-R_j S_k,u_j,k,u_j ,k]=Q^π(S_k,u_j,k)-Q^π(S_k,u_j ,k). (78) The downstream randomness contributes to Monte Carlo noise but does not create an upstream state bias, because the upstream state is shared and fixed. Finally, RTPO assigns the resulting advantage only to the output tokens of turn k. For sibling rollout j, these tokens are lj,k=(aj,k,1,…,aj,k,Tj,k).l_j,k=(a_j,k,1,…,a_j,k,T_j,k). (79) The shared prefix ck=ψ(Sk)c_k=ψ(S_k) is used only as the conditioning input and is excluded from the gradient. Equivalently, the gradient support of the turn-k objective satisfies supp(∇θJk)⊆(j,k,t):j∈1,…,G−1,t∈1,…,Tj,k.supp( _θJ_k) \(j,k,t):j∈\1,…,G-1\,\;t∈\1,…,T_j,k\\. (80) Thus, prefix tokens receive zero gradient, and the credit signal is assigned only to the sampled turn-k output action. This proves part (c) of Theorem 2, and completes the proof of Theorem 2. ∎ Interpretation. The proof shows that the key difference between RTPO and flat-trajectory training is the baseline state. The sibling estimator compares alternative turn-k actions from the same boundary state SkS_k, so the baseline estimates the local value Vπ(Sk)V^π(S_k). In contrast, a flat-trajectory baseline compares returns from trajectories that may have reached different boundary states by turn k, so it is centered around the global mean μR _R. The resulting term Vπ(Si,k)−μRV^π(S_i,k)- _R is an upstream state-contamination term: it can dominate the true turn-level advantage even though it is unrelated to the current turn action. RTPO removes this term by constructing state-matched sibling rollouts and assigning the resulting advantage only to the output tokens of the current turn. C.4 Proof of Theorem 3: On-Policy Continuation under Asynchronous Turns We formalize Theorem 3 from Sec 3.3 before presenting the proof. The purpose is to show that RTPO avoids the off-policy drift induced by stale downstream rollouts. In asynchronous multi-turn training, a trajectory generated under an old policy may later be evaluated under an updated policy, which would require a long-horizon trajectory-level importance-sampling correction. RTPO avoids this issue by regenerating sibling continuations on-policy at each reverse-order turn. Setup. Let θ0 _0 denote the rollout parameters at the beginning of a training iteration, and let θ>k _>k denote the current parameters available at the start of turn k, after downstream turns k+1,…,K−1k+1,…,K-1 have already been optimized. A stale-rollout alternative would retain sibling continuations generated under πθ0 _ _0 and correct them using the trajectory-level importance-sampling weight: ωjold=∏h=k+1K−1∏t=1Tj,hπθ>k(aj,h,t∣cj,h,aj,h,<t)πθ0(aj,h,t∣cj,h,aj,h,<t). _j^old= _h=k+1^K-1 _t=1^T_j,h _ _>k(a_j,h,t c_j,h,a_j,h,<t) _ _0(a_j,h,t c_j,h,a_j,h,<t). (81) In contrast, RTPO synchronizes the latest parameters θ>k _>k to the inference engine at the start of turn k, forks G−1G-1 sibling rollouts from the shared boundary state SkS_k, and samples each sibling rollout j∈1,…,G−1j∈\1,…,G-1\ using πθ>k _ _>k from turn k until termination. We write uj,k≡lj,ku_j,k≡ l_j,k for the sampled turn-k macro-action of sibling j, and RjR_j for its terminal return. The Monte Carlo turn-level Q-value estimate is Q^j,k=Rj=rj,k+γHτj,kF^j,kπθ>k, Q_j,k=R_j=r_j,k+ _H _j,k F_j,k _ _>k, (82) where F^j,kπθ>k F_j,k _ _>k is the sampled downstream continuation value generated under the same current policy πθ>k _ _>k. The corresponding sibling advantage is Aj,kH=Q^j,k−V^k,V^k=1G−1∑r=1G−1Q^r,k.A^H_j,k= Q_j,k- V_k, V_k= 1G-1 _r=1^G-1 Q_r,k. (83) On-Policy Continuation without Drift Theorem 3 (On-Policy Continuation under Asynchronous Turns). Consider turn k in the reverse-order training procedure of RTPO. At the start of turn k, RTPO synchronizes the current downstream policy parameters θ>k _>k to the inference engine, forks G−1G-1 sibling rollouts from the shared boundary state SkS_k, and continues each sibling rollout j to termination under the same policy πθ>k _ _>k. Then the following two properties hold: (a) Drift-free on-policy continuation. Each sibling’s terminal return RjR_j is an unbiased Monte Carlo estimate of the current-policy turn-level Q-value: [Q^j,k∣Sk,uj,k]=Q~kπθ>k(Sk,uj,k).E\! [ Q_j,k S_k,u_j,k ]= Q_k _ _>k(S_k,u_j,k). (84) Moreover, because the sampling policy and the evaluation policy coincide throughout the sibling continuation, the trajectory-level importance-sampling weight satisfies ωj=∏h=k+1K−1∏t=1Tj,hπθ>k(aj,h,t∣cj,h,aj,h,<t)πθ>k(aj,h,t∣cj,h,aj,h,<t)≡1. _j= _h=k+1^K-1 _t=1^T_j,h _ _>k(a_j,h,t c_j,h,a_j,h,<t) _ _>k(a_j,h,t c_j,h,a_j,h,<t)≡ 1. (85) (b) Dynamic error reduction in advantage estimation. Under bounded binary or normalized rewards, the conditional variance of the Monte Carlo Q-value estimator is controlled by the current-policy success probability. In the binary case, if pj,k:=Q~kπθ>k(Sk,uj,k)∈[0,1],p_j,k:= Q_k _ _>k(S_k,u_j,k)∈[0,1], (86) then Var(Q^j,k∣Sk,uj,k)=pj,k(1−pj,k).Var( Q_j,k S_k,u_j,k)=p_j,k(1-p_j,k). (87) Therefore, when reverse-order training improves downstream policies so that pj,kp_j,k moves away from the high-uncertainty region around 1/21/2, the Q-value estimation variance decreases. Since Aj,kHA^H_j,k is computed from the sibling Q-value estimates, this improves the signal-to-noise ratio of the resulting turn-level advantage estimator. Proof. We prove parts (a) and (b) of Theorem 3 as follows. Proof of Theorem 3(a): drift-free on-policy continuation. Fix a turn k and a sibling rollout j. At the start of turn k, RTPO synchronizes the current downstream policy parameters θ>k _>k to the inference engine. The sibling rollout is forked from the shared boundary state SkS_k, samples the turn-k macro-action uj,k≡lj,ku_j,k≡ l_j,k, and then continues through turns k+1,…,K−1k+1,…,K-1 under the same policy πθ>k _ _>k. By the definition of the turn-level augmented action value, Q~kπθ>k(Sk,uj,k)=[rj,k+γHτj,kFkπθ>k(Sj,k+1)|Sk,uj,k], Q_k _ _>k(S_k,u_j,k)=E\! [r_j,k+ _H _j,kF_k _ _>k(S_j,k+1)\; |\;S_k,u_j,k ], (88) where Sj,k+1S_j,k+1 is the next boundary state reached by sibling j after executing uj,ku_j,k. Since the sampled downstream continuation F^j,kπθ>k F_j,k _ _>k is generated by rolling out the same current policy πθ>k _ _>k from Sj,k+1S_j,k+1 to termination, it is an unbiased Monte Carlo draw from the downstream continuation value: [F^j,kπθ>k∣Sj,k+1]=Fkπθ>k(Sj,k+1).E\! [ F_j,k _ _>k S_j,k+1 ]=F_k _ _>k(S_j,k+1). (89) Substituting Eq. (89) into Eq. (82) gives [Q^j,k∣Sk,uj,k] \! [ Q_j,k S_k,u_j,k ] =[rj,k+γHτj,kF^j,kπθ>k|Sk,uj,k] =E\! [r_j,k+ _H _j,k F_j,k _ _>k\; |\;S_k,u_j,k ] =[rj,k+γHτj,kFkπθ>k(Sj,k+1)|Sk,uj,k] =E\! [r_j,k+ _H _j,kF_k _ _>k(S_j,k+1)\; |\;S_k,u_j,k ] =Q~kπθ>k(Sk,uj,k). = Q_k _ _>k(S_k,u_j,k). (90) Therefore, each sibling terminal return provides an unbiased Monte Carlo estimate of the turn-level Q-value under the current downstream policy. Next, because the sibling is both sampled and evaluated under the same policy πθ>k _ _>k, the full trajectory-level importance-sampling weight is ωj=∏h=k+1K−1∏t=1Tj,hπθ>k(aj,h,t∣cj,h,aj,h,<t)πθ>k(aj,h,t∣cj,h,aj,h,<t)=1. _j= _h=k+1^K-1 _t=1^T_j,h _ _>k(a_j,h,t c_j,h,a_j,h,<t) _ _>k(a_j,h,t c_j,h,a_j,h,<t)=1. (91) Thus, no trajectory-level IS correction is required. This proves part (a) of Theorem 3. Proof of Theorem 3(b): dynamic error reduction in advantage estimation. We first consider the binary-reward case, where Rj∈0,1R_j∈\0,1\. Conditional on (Sk,uj,k)(S_k,u_j,k), define pj,k=ℙπθ>k(Rj=1∣Sk,uj,k)=Q~kπθ>k(Sk,uj,k).p_j,k=P_ _ _>k(R_j=1 S_k,u_j,k)= Q_k _ _>k(S_k,u_j,k). (92) Then Q^j,k=Rj Q_j,k=R_j is a Bernoulli random variable with mean pj,kp_j,k, and therefore Var(Q^j,k∣Sk,uj,k)=pj,k(1−pj,k).Var( Q_j,k S_k,u_j,k)=p_j,k(1-p_j,k). (93) The function f(p)=p(1−p)f(p)=p(1-p) is maximized at p=1/2p=1/2 and decreases as p moves toward either 00 or 11. Equivalently, p(1−p)=14−(p−12)2.p(1-p)= 14- (p- 12 )^2. (94) Therefore, if reverse-order training improves the downstream continuation policy so that the induced success probability moves away from the high-uncertainty region around 1/21/2, then the conditional variance of the Q-value estimator decreases. Formally, |pj,knew−12|>|pj,kold−12|⟹pj,knew(1−pj,knew)<pj,kold(1−pj,kold). |p_j,k^new- 12 |> |p_j,k^old- 12 | p_j,k^new(1-p_j,k^new)<p_j,k^old(1-p_j,k^old). (95) For normalized rewards Rj∈[0,1]R_j∈[0,1], the same statement holds as a bounded-variance control rather than an exact Bernoulli identity. In particular, by the Bhatia–Davis bound for random variables supported on [0,1][0,1], Var(Rj∣Sk,uj,k)≤[Rj∣Sk,uj,k](1−[Rj∣Sk,uj,k]).Var(R_j S_k,u_j,k) [R_j S_k,u_j,k] (1-E[R_j S_k,u_j,k] ). (96) Thus, moving the conditional mean away from the high-uncertainty middle region also reduces the worst-case variance bound for normalized returns. Finally, RTPO computes the turn-level advantage by subtracting the sibling baseline: Aj,kH=Q^j,k−V^k,V^k=1G−1∑r=1G−1Q^r,k.A^H_j,k= Q_j,k- V_k, V_k= 1G-1 _r=1^G-1 Q_r,k. (97) Since Aj,kHA^H_j,k is a centered function of the sibling Q-value estimates, reducing the Monte Carlo noise in Q^j,k Q_j,k reduces the noise entering the advantage estimator. Consequently, as reverse-order training improves downstream policies and the on-policy continuation values become more confident, the signal-to-noise ratio of Aj,kHA^H_j,k improves. This proves part (b) of Theorem 3, and completes the proof of Theorem 3. ∎ Comparison with stale trajectory-level IS correction. The drift-free property above should be contrasted with a stale-rollout alternative that reuses continuations generated under πθ0 _ _0 and then applies the trajectory-level IS weight ωjold _j^old in Eq. (81). Let Nj=∑h=k+1K−1Tj,hN_j= _h=k+1^K-1T_j,h (98) denote the number of tokens in the continuation from turn k to termination. If the per-token divergence between the current policy and the stale rollout policy is nonzero along this continuation, the variance of the full product IS weight can grow multiplicatively with NjN_j. To see this, suppose that for each token position (h,t)(h,t), the conditional second moment of the token ratio ρj,h,told=πθ>k(aj,h,t∣cj,h,aj,h,<t)πθ0(aj,h,t∣cj,h,aj,h,<t) _j,h,t^old= _ _>k(a_j,h,t c_j,h,a_j,h,<t) _ _0(a_j,h,t c_j,h,a_j,h,<t) (99) satisfies πθ0[(ρj,h,told)2∣cj,h,aj,h,<t]≥1+δfor some δ>0.E_ _ _0\! [ ( _j,h,t^old )^2 c_j,h,a_j,h,<t ]≥ 1+δ some δ>0. (100) Then the second moment of the product weight scales as πθ0[(ωjold)2]=πθ0[∏h=k+1K−1∏t=1Tj,h(ρj,h,told)2]≳(1+δ)Nj,E_ _ _0\! [ ( _j^old )^2 ]=E_ _ _0\! [ _h=k+1^K-1 _t=1^T_j,h ( _j,h,t^old )^2 ] (1+δ)^N_j, (101) up to the usual conditioning on autoregressive histories. Since πθ0[ωjold]=1E_ _ _0[ _j^old]=1, this implies Varπθ0(ωjold)=πθ0[(ωjold)2]−1≳(1+δ)Nj−1.Var_ _ _0( _j^old)=E_ _ _0\! [ ( _j^old )^2 ]-1 (1+δ)^N_j-1. (102) This illustrates the long-horizon instability of trajectory-level IS correction: even a small nonzero per-token policy mismatch can compound into a high-variance product over many tokens. Per-token PPO clipping does not remove this mismatch at the trajectory level, because clipping and multiplication do not commute: ∏h,tclip(ρj,h,told,1−ϵ,1+ϵ)≠clip(∏h,tρj,h,told,1−ϵ,1+ϵ). _h,tclip\! ( _j,h,t^old,1-ε,1+ε ) \! ( _h,t _j,h,t^old,1-ε,1+ε ). (103) Therefore, stale-rollout correction remains fundamentally different from RTPO’s on-policy sibling continuation, where the corresponding weight is ωj≡1 _j≡ 1. Interpretation. Theorem 3 shows why RTPO regenerates sibling continuations on-policy instead of reusing stale downstream rollouts. In asynchronous multi-turn training, stale continuations estimate values under outdated downstream policies and would require a long-horizon trajectory-level IS correction. RTPO avoids this by synchronizing θ>k _>k before sibling generation and rolling out each sibling to termination under the same current policy. As a result, the full trajectory IS weight is one, the Q-value estimate targets the current downstream policy, and the resulting turn-level advantage avoids policy-drift contamination. Appendix D Experimental Setup Base Models. We use Qwen3 models [58] as the backbone for RTPO and all baselines. These models support context lengths of up to 32,768 tokens, which is sufficient to accommodate the multi-turn interaction histories required by long-horizon agentic RL tasks. Since Qwen3 natively supports a thinking inference mode, we enable this mode consistently across all multi-turn agentic RL experiments to ensure that the model generates complete tool-integrated reasoning trajectories during rollout. We use Qwen3-8B as the main backbone because search-based agentic tasks require strong base-model capabilities for multi-turn evidence acquisition, information integration, and tool-augmented reasoning. This choice is supported by our main results in Sec. 4.1, the rollout–training consistency analysis in Sec. 4.2, and the policy-drift analysis in Sec. 4.4. To isolate the effect of turn-level credit assignment in Sec. 4.3, we use the smaller Qwen3-4B model for mathematical reasoning tasks. This is because credit assignment in these tasks depends more directly on the model’s intrinsic reasoning ability than on external knowledge retrieval, making the gains from turn-level credit assignment more discernible. Baselines. We compare RTPO with two categories of state-of-the-art multi-turn agentic RL methods. The first category consists of trajectory-only policy optimization methods, including GRPO [42] and. GRPO uses token-level importance ratios with group-relative advantage estimation. The second category includes turn-level and tree-based policy optimization methods, including ARPO [13], Tree-GRPO [22], and SeeUPO [20]. ARPO performs entropy-driven adaptive branching at uncertain tool-call nodes and estimates advantages separately for shared-prefix and branch-specific tokens. Tree-GRPO represents multi-turn agent interaction as a tree and constructs group-relative advantages at both intra-tree and inter-tree levels by sharing prefixes. SeeUPO treats each turn as an independent agent and performs sequential per-turn updates under a heterogeneous multi-agent learning, with a theoretical guarantee of monotonic improvement. Datasets. To ensure a fair comparison across methods in multi-turn agentic scenarios, we consider two representative tool-use tasks: mathematical reasoning and knowledge reasoning from search. Both require agents to interact with external tools, perform multi-turn reasoning, and adapt their actions based on intermediate feedback. For the mathematical reasoning task, we use the MATH dataset [18] for training, which covers challenging multi-step reasoning problems spanning algebra, geometry, number theory, probability, and other topics. The task requires agents to decompose complex problems, invoke external Python computation tools when necessary, and integrate intermediate results into the final answer, where successful solutions often depend on iterative calculation, verification, and correction. At the evaluation stage, we test generalization at two difficulty levels: (1) standard mathematical reasoning benchmarks, including GSM8K [10] and MATH-500 [28]; and (2) competition-level benchmarks, including AMC’23 [33], AIME’24 [34], AIME’25 [35], and OE-Math [17], which feature problems that demand extended chains of tool-augmented reasoning and advanced problem-solving capabilities. Since no training data are available for the competition-level benchmarks, all evaluations are conducted in a zero-shot setting. For the knowledge reasoning task on web search, we adopt the hard-search training set constructed by ARPO [13], consisting of 1,000 high-difficulty search samples drawn from two open-source deep-search data sources: SimpleDeepSearcher [48] and WebSailor [26]. These samples require extensive web retrieval, multi-source evidence integration, long-context reasoning, and frequent tool calls, providing a rigorous testbed for evaluating the model stability and sample efficiency of multi-turn agentic RL. On this task, we evaluate knowledge-intensive multi-hop question answering on HotpotQA [61] and 2WikiMultiHopQA [19], following the ARPO evaluation protocol [13] with LLM-as-Judge scoring based on Qwen2.5-72B-Instruct and report F1 scores. In addition, to examine the effect of on-policy continuation, we compare default RTPO with its off-policy variant, and conduct additional evaluation on four challenging deep-search benchmarks: GAIA [36], which evaluates general AI-assistant capabilities across three difficulty levels (Lv.1–Lv.3); WebWalkerQA [55], which focuses on interactive web navigation and multi-hop question answering; Humanity’s Last Exam [37], which covers expert-level problems in sciences, engineering, and humanities; and xBench [8], which evaluates cross-lingual deep-search capability. Since the training data are drawn exclusively from the hard-search source, all four benchmarks serve as held-out evaluation sets. We report Pass@1 with sampling temperature set to 0.60.6 and top-p set to 0.950.95. Configurations. All methods are implemented on top of the VeRL framework [43], with vLLM [24] for rollout generation and FSDP [66] for post-training. All experiments are conducted on 8×8× NVIDIA A100 GPUs. Unless otherwise specified, the training batch size is 6464 and the maximum single-turn response length is 40964096 tokens. The maximum interaction horizon is set according to task type: K=3K=3 turns for mathematical reasoning and K=6K=6 turns for web search. The learning rate is fixed at 1×10−61× 10^-6 with the AdamW [31] optimizer and a weight decay of 0.010.01. For branching-based baselines (ARPO and TreeGRPO), we follow the hyperparameters recommended in their original papers, including an entropy threshold of 0.40.4 and an initial sampling size of 88. Full hyperparameter configurations are provided in Appendix E.3. Evaluation Metrics. We evaluate RTPO and all baselines along multiple dimensions. For overall performance, we use Pass@1 accuracy as the primary indicator of final policy quality after optimization (Sec 4.1). We also measure the average number of tool calls to assess behavioral differences across methods under a fixed compute budget. For training stability, rollout–training consistency is evaluated using the log-probability ratio and KL divergence, as described in Sec. 4.2. We further conduct controlled experiments to examine whether RTPO’s turn-level credit assignment (Sec 4.3) and on-policy continuation (Sec 4.4) are consistent with the theoretical analysis. Each experiment is repeated three times to mitigate randomness, and we report the average performance. Appendix E Implementation Details E.1 Pseudocode The pseudocode for our proposed RTPO is shown in Algorithm 1. Algorithm 1 Reverse-Turn Policy Optimization (RTPO) 1: Query dataset D; policy πθ _θ; inference engine ℰE; sibling count G; PPO clip ϵε; max turns K; observation map ψ; PPO epochs E. 2: Updated parameters θ. 3: Phase 1: Trunk Rollout 4: For each query q∈q\!∈\!D, generate a complete trajectory (S0,u0,f0,…,uK−1,fK−1)(S_0,u_0,f_0,…,u_K-1,f_K-1) under πθ _θ by interacting with the environment. Record boundary states and environment snapshots Sk,snapkk=0K−1\S_k,snap_k\_k=0^K-1, and set conditioning contexts ck=ψ(Sk)c_k=ψ(S_k). The trunk provides anchors only and receives no gradient. 5: Phase 2: Reverse-Order Training 6: for k=K−1,K−2,…, 0k=K-1,\;K-2,\;…,\;0 do 7: Synchronize. Push current parameters θ (denoted θ>k _>k, reflecting downstream turns already optimized) to ℰE; freeze θold←θ>k _old← _>k as the IS denominator. 8: Sibling generation (on-policy). For each q∈q\!∈\!D and each sibling j=1,…,G−1j=1,…,G-1: restore environment from snapksnap_k; sample turn-k response uj,k∼πθ>k(⋅∣ck)u_j,k _ _>k(· c_k); continue under πθ>k _ _>k through turns k+1,…,K−1k+1,…,K-1 to terminal; receive reward Rj∈0,1R_j∈\0,1\. Record turn-k tokens aj,k,tt=1Tj,k\a_j,k,t\_t=1^T_j,k and their log-probs under θold _old. 9: Turn-level advantage. For each q∈q\!∈\!D, compute the sibling baseline and advantage: V^k=1G−1∑j=1G−1Rj,Aj,kH=Rj−V^k. V_k= 1G-1 _j=1^G-1R_j, A_j,k^H=R_j- V_k. All siblings share SkS_k, so Aj,kHA_j,k^H is free of upstream state contamination (Theorem 2). 10: PPO update (turn-k tokens only). 11: for epoch =1,…,E=1,…,E do 12: for each mini-batch from sibling turn-k tokens do 13: Compute IS ratios ρj,k,t=πθ(aj,k,t∣ck,aj,k,<t)/πθold(aj,k,t∣ck,aj,k,<t) _j,k,t= _θ(a_j,k,t c_k,a_j,k,<t)\,/\, _ _old(a_j,k,t c_k,a_j,k,<t). 14: Update θ via the clipped objective: Jk(θ)=1G−1∑j=1G−11Tj,k∑t=1Tj,kmin(ρj,k,tAj,kH,clip(ρj,k,t, 1−ϵ, 1+ϵ)Aj,kH).J_k(θ)= 1G-1 _j=1^G-1 1T_j,k _t=1^T_j,k \! ( _j,k,t\,A_j,k^H,\;clip ( _j,k,t,\,1-ε,\,1+ε )\,A_j,k^H ). 15: end for 16: end for 17: ⊳ Turn k complete; πθ,k _θ,k frozen; next turn inherits updated θ. 18: end for E.2 Source Code We provide the source code of RTPO in the Supplementary Material. The repository includes complete installation instructions and versioned dependency requirements. Our implementation is built upon VeRL [43], whose core additions are: (1) summarizing the output of each round, so that the next round can rollout without having access to the complete history, (2) on-policy tree rollouts, and (3) computation of per-turn advantage and reverse updates. We also provide out-of-the-box training and evaluation scripts to reproduce our main results on mathematical and knowledge reasoning tasks. E.3 Training Details We provide the detailed hyperparameters for all experiments in Table 4. Unless otherwise noted, the maximum prompt/response lengths are kept the same across all experiments. For computational fairness, the global sampling budget is set to 80k80k rollouts for mathematical reasoning (5k5k prompts × 1616 rollouts per prompt) and 16k16k for knowledge reasoning (1k1k prompts × 1616 rollouts per prompt). For the Qwen3 series, we use a sampling temperature of 0.90.9, the AdamW optimizer with a learning rate of 1×10−61× 10^-6, weight decay 0.010.01, and an initial KL coefficient of 0.020.02. The log-probability clipping range is set to [−10,10][-10,10]. The training batch size and the rollout batch size are both set to 6464. The maximum prompt length is 81928192 tokens and the maximum single-turn response length is 40964096 tokens for both tasks. The maximum interaction horizon is set to K=3K=3 turns for mathematical reasoning and K=6K=6 turns for web search. All methods are allocated a uniform budget of 1616 rollouts per prompt (see Table 4). Method Parameters Total Rollouts Structure GRPO n_agent=16=16 16 independent chains Chain SeeUPO rollout_n=16=16 16 chains + turn-level update Chain ARPO N=8,M=16N=8,\;M=16 8 initial + entropy branch to 16 Entropy tree TreeGRPO M=4,N=3,L=1M=4,\;N=3,\;L=1 4 trees × 4 leaves == 16 Random tree RTPO sibling rollouts Global Max budget State-matched tree Table 4: Hyperparameter settings for all experiments. For GRPO, we sample 1616 independent chains per prompt. For SeeUPO, we generate 1616 independent chains with sequential turn-level updates in reverse execution order. For ARPO, we set the initial sampling size to N=8N=8 and the global rollout budget to M=16M=16, with entropy weight β=0.2β=0.2, base probability α=0.5α=0.5, and branching threshold τ=0.5τ=0.5; rollouts that do not trigger entropy-driven branching are supplemented with independent chains until the budget of 1616 is reached. For TreeGRPO, we set the number of initial trees to M=4M=4, the number of expansion nodes per iteration to N=3N=3, and the number of expansion iterations to L=1L=1, yielding M×(L×N+1)=16M×(L× N+1)=16 rollouts per prompt via random node expansion. For RTPO, we first generate multiple trunk trajectories per prompt to establish turn-boundary states: 44 trunks for mathematical reasoning (K=3K=3) and 22 trunks for web search (K=6K=6), since in practice most trunks do not reach the maximum interaction horizon and terminate early with fewer tool calls. At each realized turn boundary SkS_k, G−1=2G-1=2 sibling rollouts are forked and continued to termination. To ensure computational fairness with baselines, RTPO enforces the same global sampling budget as all other methods (80k80k for mathematical reasoning, 16k16k for knowledge reasoning), so that the total number of generated rollouts across all prompts does not exceed that of any baseline. Per-prompt rollout counts may vary depending on early termination, but the global budget constraint guarantees that RTPO consumes no more rollout compute than the 1616-chain baselines in aggregate. All methods use a discount factor of γ=1γ=1. All experiments are conducted on a single node equipped with 8×8× NVIDIA A100 80GB GPUs, 256256 CPU cores, and 256256GB of system memory, running Ubuntu 22.04 LTS. The math task requires approximately 15 hours of training, whereas the knowledge task requires approximately 5 hours. E.4 Qwen3 Chat Template Figure 4: Examples of Qwen3 chat template. At each interaction turn, Qwen3 receives the current context and generates three components: (A) an internal reasoning trace enclosed by <think>...</think>, (B) textual commentary after </think>, and (C) a tool-call instruction, e.g., <tool_call>...</tool_call>. The tool call is executed by the external environment, which returns the result as an observation. Before constructing the next-turn input, the chat-template filter removes the <think>...</think> segment, while retaining the textual commentary, the tool-call instruction, and the appended tool-execution result. Thus, the input to the second turn consists of: (1) the original user request, (2) the previous textual commentary, (3) the previous tool call, and (4) the tool result. This filtered context enables the model to condition on the action history and environment feedback without carrying redundant internal reasoning traces, keeping the context length manageable while preserving decision-relevant information. The process is illustrated in Figure 4. Appendix F Additional Results and Insights F.1 Discussion of Main Results For the main experiments, we use Qwen3-8B as the base model and evaluate on two categories of multi-turn tool-use tasks: mathematical reasoning and web search. Qwen3 models automatically produce chain-of-thought content wrapped in <think>...</think> tags during inference. In our setup, each turn’s input is constructed using the standard Qwen3 chat template, which post-processes prior assistant content by stripping out the <think>...</think> segments so that subsequent turns observe only the final answer content following </think>. This design keeps the per-turn input context concise and aligns naturally with the turn-boundary MDP formulation underlying RTPO: each turn-level policy is conditioned on the visible context ckc_k rather than on the full raw interaction history. In addition, we report the complete accuracy results with mean and standard deviation, extending Table 1 to Table 5. Method M: Mathematical Reasoning K: Knowledge Reasoning AIME24 AIME25 AMC23 MATH500 GSM8K OE-Math HotpotQA 2Wiki Vanilla 3.33±0.00%3.33_± 0.00\% 13.33±3.33%13.33_± 3.33\% 12.50±2.50%12.50_± 2.50\% 51.00±0.40%51.00_± 0.40\% 76.95±0.15%76.95_± 0.15\% 24.33±0.68%24.33_± 0.68\% 54.52¯±0.72% 54.52_± 0.72\% 59.83±0.61%59.83_± 0.61\% GRPO 10.00±3.33%10.00_± 3.33\% 20.00±3.33%20.00_± 3.33\% 57.50±2.50%57.50_± 2.50\% 82.33±0.50%82.33_± 0.50\% 93.86±0.23%93.86_± 0.23\% 50.74±1.12%50.74_± 1.12\% 53.39±0.93%53.39_± 0.93\% 61.85±0.84%61.85_± 0.84\% SeeUPO 20.00¯±3.33% 20.00_± 3.33\% 23.33¯±3.33% 23.33_± 3.33\% 67.50¯±2.50% 67.50_± 2.50\% 84.20¯±0.35% 84.20_± 0.35\% 94.47¯±0.13% 94.47_± 0.13\% 53.86¯±0.45% 53.86_± 0.45\% 54.27±0.55%54.27_± 0.55\% 63.78¯±0.49% 63.78_± 0.49\% RTPO 33.33±0.00%33.33_± 0.00\% 26.67±0.00%26.67_± 0.00\% 67.50±0.00%67.50_± 0.00\% 86.20±0.20%86.20_± 0.20\% 94.84±0.08%94.84_± 0.08\% 55.49±0.30%55.49_± 0.30\% 64.89±0.34%64.89_± 0.34\% 64.35±0.27%64.35_± 0.27\% Table 5: Accuracy comparison across eight benchmarks. Values are reported as mean±std over three evaluation runs. Acc denotes Pass@1 (%) for mathematical tasks and best-span F1 (%) for knowledge reasoning tasks. Standard deviations are reported in percentage points. Performance and tool-use patterns on mathematical reasoning tasks. On mathematical tasks, tool-call frequency exhibits a trend that runs almost opposite to accuracy: Vanilla makes 17 Python calls on AIME24 yet solves only one problem, whereas RTPO solves ten with just four calls. This pattern reflects an intrinsic property of mathematical reasoning: the knowledge and derivations required to solve a math problem are primarily internalized in the model’s parameters, while the external Python tool serves as an auxiliary aid for verification and numerical computation rather than as a source of new information. Vanilla’s frequent tool use, therefore, largely reflects an inefficient strategy of repeated verification used to mask reasoning uncertainty. After RL training, the model gains stronger control over its own reasoning process, and tool calls collapse from redundant repeated verification into precise invocations at critical computation steps; consequently, the number of calls decreases while accuracy increases. RTPO’s advantage becomes particularly pronounced on the hardest math benchmarks: it reaches 33.33% Pass@1 on AIME24, surpassing SeeUPO (20.00%) and GRPO (10.00%) by 13.3 and 23.3 absolute points, respectively, and maintains a clear lead on AIME25 and OE-Math. RTPO simultaneously achieves the fewest tool calls and the highest accuracy on these hard problems, indicating that it learns the most efficient tool-use strategy. We further note that the gap between methods on mathematical tasks remains relatively small overall, since math problems typically require only a few interaction turns, and the context discrepancy between rollout and training stays at a manageable scale under short horizons; the robustness of standard training dynamics alone is sufficient for baselines to reach near-optimal performance in this regime. We provide an example to support our discussion, as shown in Figure 5. Figure 5: An example of different policy performance on a mathematical-reasoning task through Python tools. Performance and tool-use patterns on knowledge reasoning tasks. On knowledge-intensive question answering, RTPO reaches 64.89 F1 on HotpotQA, exceeding SeeUPO (54.27) and GRPO (53.39) by 10.6 and 11.5 points, respectively, and maintains a clear lead on 2Wiki. In contrast to mathematical tasks, the tool-use pattern on knowledge reasoning exhibits a positive correlation between call count and accuracy: RTPO issues 613 and 867 search calls on HotpotQA and 2Wiki, far exceeding the roughly 200 calls observed for the other methods. This contrast admits a natural explanation grounded in task structure: the factual information required to answer such questions does not reside in the model’s parametric knowledge and must be acquired through external retrieval, while multi-hop questions further demand cross-turn integration of multiple pieces of evidence. The lower retrieval counts of GRPO and SeeUPO indicate that they fail to learn to issue sustained follow-up queries and to expand retrieval across multiple turns. The underlying cause is that such hard tasks require longer interaction horizons and more frequent reasoning revision, so the rollout–training context mismatch is amplified as turns accumulate, and baseline methods must spend a larger share of their optimization budget compensating for this drift. RTPO eliminates this source of bias structurally, allowing the entire optimization budget to act directly on the task objective, which yields more stable improvements on long-horizon hard tasks. We provide an example to support our discussion, as shown in Figure 6. Figure 6: An example of different policy performance on a knowledge-reasoning task through web search tools. Taking both task categories together, RTPO learns to perform mathematical reasoning with fewer calls but more reliable internal reasoning, while performing knowledge reasoning with denser calls and more thorough external information integration. This bidirectional adaptation of tool-use behavior indicates that the advantage of RTPO does not stem from simply encouraging or suppressing tool calls, but rather from its turn-level optimization objective, which is able to learn a tool-use strategy matched to the underlying nature of each task. F.2 Insights from Rollout–Training Consistency Analysis Follow-up discussion from Sec 4.2, a noteworthy observation is that, despite using different conditioning contexts at the rollout and training stages, the baselines’ ratios still exhibit a slow drift toward 11. We find that this phenomenon is closely related to the mechanism revealed by DAgger [40]: when the training data is continually drawn from the distribution induced by the policy itself, the model gradually adapts to the distribution it actually operates on. In our setting, trajectories generated by summary-rollouts are reinforced under full-history-training, and parameter sharing causes the behaviors under the two conditionings to converge indirectly; the next rollout therefore falls closer to the region considered reasonable under the training context. SCoRe [23] observes the same bootstrapped alignment process in multi-turn online RL. In addition, some works point out that the summary can serve as a learnable sufficient statistic: if the summary preserves the decision-relevant information, the optimal policies under the two contexts can converge in an information-theoretic sense [2]; recent work on multi-turn RL further shows that the summary context can evolve into a learnable compact decision state under end-to-end optimization [32, 63]. However, this empirical alignment differs from the structural consistency of RTPO in three fundamental ways: (1) Alignment is incomplete and strongly depends on task complexity. GRPO recovers only to 0.970.97 on math after 3030 steps and only to 0.830.83 on search after 1414 steps; the longer the horizon and the faster the context accumulates, the harder the alignment becomes, which is reflected in the knowledge reasoning task in Table 1. (2)The alignment process is accompanied by oscillation. SeeUPO produces a 1.021.02 spike at step 99 on math and exhibits sustained small fluctuations, because the bootstrapped loop is driven by the advantage signal, and the variance of advantage estimates propagates directly into step-to-step jitter of the ratio. RTPO’s ratio is structurally guaranteed and is only affected by differences between the training and inference engines. (3) Empirical alignment consumes additional optimization budget. Bootstrapped alignment essentially allocates part of the policy’s capacity to an implicit objective—pulling the behavior under the summary toward the optimal behavior under the full history. RTPO removes this hidden cost, so that the optimization budget can act directly on the task objective. This is consistent with the lower search-call counts of baselines on long-horizon knowledge reasoning observed in Table 1: part of their training dynamics is diverted to patching the mismatch. Overall, the rollout–training ratio reveals not that baselines necessarily fail, but that baselines must rely on training dynamics to compensate for a gap that RTPO does not have by construction, and this compensatory mechanism becomes substantially less effective on long-horizon tasks. F.3 Additional Findings for Hard-Search Scenarios Benchmark QS Off Hit Off Rate On Hit On Rate Δ GAIA 103 24 23.30% 30 29.13% +5.83% L1 39 7 17.95% 10 25.64% +7.69% L2 52 16 30.77% 18 34.62% +3.85% L3 12 1 8.33% 2 16.67% +8.33% WebWalker 200 12 6.00% 19 9.50% +3.50% XBench 100 8 8.00% 15 15.00% +7.00% HLE 2096 261 12.45% 254 12.12% -0.33% Biology/Medicine 228 37 16.23% 38 16.67% +0.44% Chemistry 81 6 7.41% 6 7.41% +0.00% Computer Science/AI 220 20 9.09% 24 10.91% +1.82% Engineering 71 5 7.04% 8 11.27% +4.23% Humanities/Social Science 192 32 16.67% 23 11.98% -4.69% Math 947 114 12.04% 112 11.83% -0.21% Other 158 29 18.35% 29 18.35% +0.00% Physics 199 18 9.05% 14 7.04% -2.01% Table 6: Rechecked output-hit comparison between standard RTPO (on-policy) and its off-policy variant. Values are rounded to the nearest integer for better readability. Output-hit marks a sample correct if the output contains the gold answer or an alias. To quantify the independent contribution of on-policy continuation (Sec. 3.3), we use Qwen3-8B as the base model and compare standard RTPO with its off-policy variant. Both share the same reverse-order turn-level training and state-matched sibling structure; the only difference lies in how sibling downstream continuations are obtained. RTPO (on-policy) synchronizes the latest parameters θ>k _>k to the inference engine at the start of turn k and regenerates sibling continuations under πθ>k _ _>k until termination, so the trajectory-level IS weight is identically one, and the Q-value estimate is Q^j,kon=rj,k+γτj,kF^j,kπθ>k. Q^on_j,k=r_j,k+γ _j,k\, F_j,k _ _>k. (104) RTPO with off-policy variant instead reuses the downstream continuations already generated under πθ0 _ _0 during the initial rollout stage and corrects for the staleness via a clamped trajectory-level importance weight: Q^j,koff=rj,k+γτj,kω¯j,kF^j,kπθ0,ω¯j,k=clamp(∏h=k+1K−1∏t=1Tj,hπθ>k(aj,h,t∣sj,h,t)πθ0(aj,h,t∣sj,h,t),ρmin,ρmax). Q^off_j,k=r_j,k+γ _j,k\, ω_j,k\, F_j,k _ _0, ω_j,k=clamp\! ( _h=k+1^K-1 _t=1^T_j,h _ _>k(a_j,h,t s_j,h,t) _ _0(a_j,h,t s_j,h,t),\; _ ,\; _ ). (105) We compare the on-policy RTPO and its off-policy variant on four knowledge-reasoning deep-search benchmarks, as shown in Table 6. We use output-hit accuracy, which marks a sample correct if the full output contains the gold answer or an alias. The benchmarks include GAIA with three difficulty levels, WebWalkerQA, XBench, and HLE with eight subject subsets. F.4 Limitations and Future Work Although RTPO provides stronger theoretical guarantees and empirical performance than existing flat-trajectory methods, its algorithmic design has several limitations that motivate future work. Dependence on trunk quality. RTPO uses the boundary states SkS_k of a trunk trajectory as the forking points for sibling branches. As a result, the training signal at each reverse phase is anchored to the state sequence visited by the trunk. If the trunk makes a poor decision at an early turn, such as k=0k=0 or k=1k=1, later boundary states may lie in low-value regions where even strong turn-level actions fail to obtain positive terminal rewards. In this case, the turn-level advantages Aj,kHA_j,k^H may degenerate into near-zero signals, making the corresponding gradient update ineffective. In contrast, beam-style search methods, such as beam search or best-of-N, maintain multiple candidate prefixes and can discard low-quality paths earlier. RTPO currently relies on a single trunk anchor and does not explicitly incorporate trunk-level diversity or post-hoc trunk selection. A natural extension is multi-trunk sampling or retroactive trunk selection, where multiple complete trunks are generated during rollout and a high-reward trunk is selected as the anchor to improve boundary-state coverage. This would increase rollout cost, but would not change the reverse-order training formulation. Overhead of reverse multi-turn training. RTPO decomposes a K-turn episode into K sequential turn-level optimization phases. Each phase requires sibling generation, environment restoration, on-policy continuation to termination, and a PPO-style update. Compared with flat-trajectory methods, which perform a single optimization pass over the full trajectory, RTPO incurs additional cost that scales with the number of turns K and the number of sibling rollouts. Moreover, each reverse phase requires synchronizing the latest policy parameters to the inference engine before generating on-policy continuations, introducing additional inference-training latency. In our VeRL-based implementation, this overhead is partially mitigated by batched parallel sibling generation and asynchronous engine scheduling, but it cannot be fully removed. Designing more efficient sibling generation and update schedules is therefore an important direction for future work. Under-utilization of training tokens. RTPO assigns the turn-level advantage in phase k only to the sibling’s turn-k output tokens. Prefix tokens in ckc_k and downstream continuation tokens from turns k+1,…,K−1k+1,…,K-1 receive no gradient. In addition, the trunk trajectory is used only as an anchor and does not directly contribute to gradient updates. Thus, although sibling continuations are necessary for estimating terminal returns, their downstream tokens are discarded during policy optimization. For example, in a K=5K=5 episode with an average of 200 tokens per turn, the sibling continuation at phase k=2k=2 may generate around 600 downstream tokens, while only the 200 turn-k tokens are used for the PPO update. This reduced token utilization is the cost of causal turn-level credit assignment: by withholding gradients from non-turn-k tokens, RTPO avoids assigning credit to actions that are not causally responsible for the turn-k comparison, as stated in Theorem 2(c). Future work may explore auxiliary objectives, such as language-modeling losses or self-play rewards on downstream tokens, to improve token efficiency while preserving the causal consistency of the turn-level advantage. F.5 Broader Impacts The potential positive impact of RTPO is that more stable agentic RL training can reduce failed tool-use trajectories, improve sample efficiency, and support more reliable deployment of LLM agents in research, education, software engineering, and decision-support settings. RTPO may also make multi-turn RL training easier to analyze by separating turn-level decisions from full-trajectory outcomes. By enabling turn-level monitoring, RTPO can further improve our understanding of how agentic workflows learn to plan, search, and use tools over multiple turns. At the same time, stronger turn-refined agentic workflows may increase the capability of LLM agents to act autonomously across long-horizon tasks. If deployed without appropriate safeguards, such systems could produce incorrect outputs with high confidence, misuse external tools, or amplify harmful automation. Therefore, practical deployment should include safety constraints, tool-use monitoring, privacy-preserving data handling, and human oversight, especially in high-stakes domains. Appendix G Supplementary Theoretical Clarifications, Implementation Details, and Extended Experiments G.1 Stateful Tool-Agent Evaluation on τ3τ^3-Airline Experimental setting. We evaluate Qwen3-1.7B on a fixed set of 30 training tasks and the 20 held-out test tasks provided by the τ3τ^3-Airline environment. The agent must query and modify an airline database through multi-turn tool interactions, and earlier actions change the state observed in later turns. Table 7: Online training success rate on τ3τ^3-Airline. Method Step 10 Step 20 Step 30 Step 40 Step 50 GRPO 23.44% 25.00% 31.26% 29.69% 31.26% SeeUPO 31.23% 9.38% 14.83% 0.78% 0.78% Tree-GRPO 18.40% 14.95% 27.48% 24.53% 14.88% REFUEL 25.00% 31.25% 31.25% 28.12% 21.88% RTPO (G=3G=3) 15.63% 37.50% 50.00% 56.25% 40.63% RTPO obtains the highest online success rate from Step 20 onward and peaks at 56.25% at Step 40. The reduction to 40.63% at Step 50 indicates that continued optimization can produce late-stage degradation when the training set is small and the reward is sparse. Table 8: Held-out evaluation on the 20 τ3τ^3-Airline test tasks. Pass4 follows the definition used in the main paper. Method Pass@1 Pass@4 Pass4 Normal termination Generation truncation Avg. response tokens SeeUPO 0.00% 0.00% 0.00% 0.00% 98.75% 2,023.7 GRPO 11.25% 25.00% 0.00% 20.00% 60.00% 2,469.7 Tree-GRPO 16.25% 25.00% 10.00% 30.00% 47.50% 2,538.2 REFUEL 11.25% 20.00% 0.00% 18.75% 57.50% 2,621.2 RTPO (G=3G=3) 17.50% 30.00% 10.00% 45.00% 42.50% 1,688.8 RTPO achieves the highest Pass@1 and Pass@4 and the highest normal environment-termination rate. Relative to Tree-GRPO, it reduces the generation-truncation rate from 47.50% to 42.50% and the average response length from 2,538.2 to 1,688.8 tokens. Relative to REFUEL, RTPO improves Pass@1 from 11.25% to 17.50%, improves Pass@4 from 20.00% to 30.00%, and reduces average response length by approximately 35.6%. Table 9: Tool-execution quality on the held-out τ3τ^3-Airline tasks. Method Attempted calls Executed successfully Tool-error calls Execution success Response tokens/success GRPO 118 68 50 57.63% 21,952.9 SeeUPO 1 0 1 0.00% N/A Tree-GRPO 1 0 1 0.00% 15,619.5 RTPO 83 74 9 89.16% 9,650.5 RTPO attempts fewer tool calls than GRPO but completes more calls without execution errors. Tool-error calls decrease from 50 to 9, and the execution success rate increases from 57.63% to 89.16%. RTPO also requires approximately 9,650.5 response tokens per successful trajectory, which is 38.2% lower than Tree-GRPO and 56.0% lower than GRPO. G.2 Sensitivity to the Sibling Group Size The group-size hyperparameter is G; at each boundary, RTPO forks G−1G-1 sibling continuations from the same turn-boundary state SkS_k. The turn-level estimator is A^j,kH=Rj−1G−1∑r=1G−1Rr. A^H_j,k=R_j- 1G-1 _r=1^G-1R_r. (106) Theorem 2(a) gives [A^j,kH∣Sk,uj,k]=G−2G−1Aπ(Sk,uj,k).E\! [ A^H_j,k S_k,u_j,k ]= G-2G-1A^π(S_k,u_j,k). (107) Thus, the finite-group bias is of order O(1/G)O(1/G), and the multiplicative coefficient approaches one as G increases. Averaging more sibling returns also reduces sampling noise in the Monte Carlo baseline. Because all continuations begin from the same boundary state, this comparison does not reintroduce upstream-state contamination. Table 10: Effect of sibling group size on signal density and held-out performance in τ3τ^3-Airline. G Theoretical coefficient Pass@1 Pass@4 Zero-advantage rate Tokens/success 3 1/21/2 17.50% 30.00% 89.61% 9,650.5 4 2/32/3 20.00% 30.00% 82.66% 7,477.9 Increasing G from 3 to 4 reduces the zero-advantage rate from 89.61% to 82.66%, improves Pass@1 from 17.50% to 20.00%, and reduces inference tokens per successful trajectory from 9,650.5 to 7,477.9. The larger group therefore provides denser relative learning signals, but requires more offline exploration. Table 11: Performance–cost trade-off for sibling group size. G GPU-hours Training-generation tokens Pass@1 Pass@4 Avg. tool calls Avg. response tokens 3 21.48 846,207 17.50% 30.00% 1.038 1,688.8 4 28.06 2,139,039 20.00% 30.00% 0.662 1,495.6 Moving from G=3G=3 to G=4G=4 increases GPU-hours by approximately 30.6% and training-generation tokens by approximately 152.8%, while improving Pass@1 by 2.5 percentage points and leaving Pass@4 unchanged. The resulting policy uses approximately 36.2% fewer tool calls and 11.4% fewer response tokens at inference time. Consequently, G=3G=3 provides the stronger default cost–performance trade-off, whereas G=4G=4 is useful when Pass@1 and concise inference behavior are prioritized. For G=2G=2, the coefficient in Eq. (107) is zero, so the conditional expectation of the relative advantage degenerates to zero. Therefore, G=3G=3, corresponding to two sibling continuations, is the minimum viable configuration that preserves an informative relative signal. G.3 Trunk Quality and Failure Dynamics Table 12: Aggregate trunk outcomes in the τ3τ^3-Airline training run. Trunk metric Percentage of all trunks Final task success 40.00% Failed within Turn 1 6.88% Failed within the first 2 turns 22.50% Failed within the first 3 turns 28.75% Failed within the first 5 turns 39.38% No terminal environment signal 10.63% Average trunk length 5.39 turns Only 6.88% of trunks fail within the first turn, indicating that catastrophic early failure is not the dominant failure mode. Most errors occur in the middle or later stages. Moreover, an observed early failure under finite sampling is not equivalent to a strict dead state, because finite continuations cannot establish that every possible future policy is unable to recover. Table 13: Evolution of failure modes during RTPO training. Metric Step 10 Step 20 Step 30 Step 40 Step 50 Success rate 15.63% 37.50% 50.00% 56.25% 40.63% Normal termination but failure 46.88% 53.13% 46.88% 40.63% 59.38% No terminal signal 37.50% 9.38% 3.13% 3.13% 0.00% Failure within Turn 1 3.13% 6.25% 9.38% 6.25% 9.38% Failure within 2 turns 15.63% 15.63% 31.25% 25.00% 25.00% Failure within 3 turns 21.88% 25.00% 34.38% 25.00% 37.50% Failure within 5 turns 25.00% 40.63% 40.63% 31.25% 59.38% Avg. successful turns 4.40 3.92 1.88 2.06 1.92 Avg. failed turns 13.30 7.30 4.06 5.50 2.84 The fraction of trajectories without a terminal environment signal decreases from 37.50% at Step 10 to 0% at Step 50, while the average failed-trajectory length decreases from 13.30 to 2.84 turns. RTPO therefore substantially reduces trajectories that stall for a long time or fail to complete the interaction. Later failures increasingly take the form of fast but incorrect termination rather than persistent generation until truncation. The drop in success after Step 40 may reflect over-optimization on a limited task set under sparse binary rewards. The implementation does not use heuristic trunk filtering. All trunks are sampled on-policy from the current model. Filtering low-quality trunks could reduce sibling-sampling cost, but would alter the actually visited state distribution and concentrate optimization on manually selected states. Instead, RTPO retains all trunks and uses same-state sibling returns to determine whether a boundary supplies an informative relative signal. G.4 Selective-Gradient Optimization and Training Efficiency Why the loss is restricted to current-turn tokens. RTPO applies the policy loss only to the output tokens of the current-turn siblings. Prefix tokens and the trunk trajectory define the state and conditioning context that were actually reached, while the downstream continuation supplies the return used to evaluate the current action. Assigning the same turn-level advantage to prefix or downstream-continuation tokens would reintroduce the trajectory-level credit contamination analyzed in Theorem 2. Although only one turn receives gradients at a particular reverse stage, every turn is optimized when it becomes the current turn during the complete reverse sweep. The selective loss is therefore intended to isolate causal credit rather than to discard particular turns from training. Table 14: Training-generation cost and deployment-time response efficiency on τ3τ^3-Airline. Method Training-generation tokens Pass@1 Response tokens/success GRPO 604,532 11.25% 21,952.9 Tree-GRPO 781,325 16.25% 15,619.5 RTPO (G=3G=3) 846,207 17.50% 9,650.5 RTPO generates approximately 8.3% more training tokens than Tree-GRPO and 40.0% more than GRPO, while attaining the highest Pass@1. Relative to Tree-GRPO, it reduces response tokens per successful trajectory by 38.2%; relative to GRPO, the reduction is approximately 56.0%. The additional offline continuation sampling therefore does not translate into more verbose deployment-time inference. Wall-clock and GPU-hour overhead. Under the same Qwen3-1.7B model, four A100 GPUs, and 160 training trunks, the measured cost is: Table 15: End-to-end training cost under the same hardware. Method Wall-clock GPU-hours Generated tokens Relative cost GRPO 3.80 h 15.20 604,532 1.00×1.00× RTPO (G=3G=3) 5.37 h 21.48 846,207 1.41×1.41× RTPO increases wall-clock time and GPU-hours by approximately 41.3%, and training-generation tokens by approximately 40.0%. The additional cost comes primarily from sibling-continuation generation, turn-by-turn reverse updates, and synchronization of the latest policy between reverse stages. RTPO thus trades higher training-time computation for state-matched credit assignment and current-policy downstream continuations. Compute-matched comparison. The following comparison uses approximately the same total GPU-hour budget. It is distinct from the fully trained RTPO result at 21.48 GPU-hours. Table 16: GRPO and compute-matched RTPO under approximately equal training cost. Metric GRPO RTPO (G=3G=3), compute-matched GPU-hours 15.20 15.55 Pass@1 11.25% 11.25% Pass@4 25.00% 35.00% Environment completion 20.00% 30.00% Generation truncation 60.00% 47.50% Total tool calls 118 98 Tool-execution success 57.63% 62.24% Average tool calls 1.475 1.225 Average response tokens 2,469.7 2,437.7 With only approximately 2% more GPU-hours, RTPO matches GRPO on Pass@1, improves Pass@4 from 25.00% to 35.00%, and increases environment completion from 20.00% to 30.00%. It also reduces truncation, total tool calls, and average response length while improving tool-execution success. Matched maximum inference budget. All methods below use the same limits of 20 turns, 2,048 tokens per turn, and 8,192 response tokens per trajectory. Table 17: Performance under the same maximum inference budget. Method Pass@1 Pass@4 Avg. tool calls Avg. response tokens Successes/1K tokens GRPO 11.25% 25.00% 1.475 2,469.7 0.046 Tree-GRPO 16.25% 25.00% 0.013 2,538.2 0.064 RTPO (G=3G=3) 17.50% 30.00% 1.038 1,688.8 0.104 Under the same maximum inference budget, RTPO attains the highest Pass@1, Pass@4, and number of successful trajectories per 1,000 response tokens, while producing the shortest average responses. Its gains therefore do not come from allowing longer test-time trajectories. G.5 Tool-Use Behavior on GSM8K The total number of tool calls should be interpreted relative to dataset size: GSM8K contains 1,319 distinct test problems, while AIME24 and AIME25 each contain 30. Across all three benchmarks, RTPO improves accuracy while reducing the total number of calls relative to the vanilla model. Table 18: Accuracy and total tool calls across mathematical benchmarks. Benchmark Vanilla accuracy / calls RTPO accuracy / calls AIME24 3.33% / 17 33.33% / 4 AIME25 13.33% / 23 26.67% / 2 GSM8K 76.95% / 731 94.84% / 482 We further audit the complete trajectories for the first 100 distinct GSM8K test problems generated by the RTPO Qwen3-4B checkpoint. Table 19: Audit of Python use in 100 distinct GSM8K trajectories. Audit metric Result Distinct trajectories audited 100 Trajectories using Python 36% Average calls per trajectory 0.36 Trajectories with zero calls 64 Trajectories with one call 36 Trajectories with two or more calls 0 Calls with valid Python syntax 36/36 Calls executed successfully 36/36 Correct tool-using trajectories 34/36 Trajectories with repeated calls 0 There are no repeated questions and no trajectory invokes Python more than once. All 36 calls contain valid syntax and execute successfully. In 34 of the 36 tool-using trajectories, the model has already derived the correct numerical result before invoking Python. The calls are one-shot arithmetic checks rather than multi-step tool search, repeated code, or duplicate execution. For example, on GSM8K QID 55, the model first derives 30−2=2830-2=28 and 28/2=1428/2=14, then invokes Python once to verify the result before returning 14 14. Thus, the GSM8K call total reflects many distinct problems receiving a single low-cost numerical verification, rather than repeated tool use within a small set of trajectories. G.6 On-Policy Continuation and Synchronization Frequency As characterized by Theorem 3, standard RTPO synchronizes the rollout model after every reverse stage. When turn k is optimized, its downstream continuation is therefore generated by the current policy πθ>k _ _>k, after turns k+1,…,K−1k+1,…,K-1 have been updated. The resulting estimator is Q^j,kon=rj,k+γτj,kF^j,kπθ>k,ωj,k≡1. Q^on_j,k=r_j,k+γ _j,k F _ _>k_j,k, _j,k≡ 1. (108) This construction assigns the turn-k action a return under the current downstream policy and avoids a product of trajectory-level importance ratios. At the opposite synchronization endpoint, the off-policy variant reuses downstream continuations generated by the initial rollout policy πθ0 _ _0 and applies a clamped trajectory-level importance weight: Q^j,koff Q^off_j,k =rj,k+γτj,kω¯j,kF^j,kπθ0, =r_j,k+γ _j,k ω_j,k F _ _0_j,k, (109) ω¯j,k ω_j,k =clamp(∏h=k+1K−1∏t=1Tj,hπθ>k(aj,h,t∣sj,h,t)πθ0(aj,h,t∣sj,h,t),ρmin,ρmax). =clamp\! ( _h=k+1^K-1 _t=1^T_j,h _ _>k(a_j,h,t s_j,h,t) _ _0(a_j,h,t s_j,h,t), _ , _ ). (110) Table 20: Output-hit accuracy of off-policy and per-stage on-policy RTPO with Qwen3-8B. Benchmark Off-policy On-policy Difference GAIA 23.30% 29.13% +5.83+5.83 p GAIA Level 3 8.33% 16.67% +8.33+8.33 p WebWalkerQA 6.00% 9.50% +3.50+3.50 p XBench 8.00% 15.00% +7.00+7.00 p HLE 12.45% 12.12% −0.33-0.33 p Per-stage on-policy continuation yields consistent gains on the long-horizon deep-search tasks, with the largest improvement on GAIA Level 3. The two variants are broadly comparable on HLE, which is dominated by more static and shorter retrieval. These results localize the cost of stale continuations to the long-horizon settings targeted by RTPO. Fixed-interval synchronization and policy-KL-based adaptive synchronization lie between the fully on-policy and fully off-policy endpoints: they can reduce synchronization cost, but no longer strictly satisfy ω¯j,k≡1 ω_j,k≡ 1. G.7 Budget Consumption Across Training The initial policy produces longer trajectories and more tool calls, so early training stages are more expensive per trunk. The training schedule does not, however, reserve a fixed number of tool calls for each stage. Every stage continues under the predefined trunk-sampling and update schedule, and the actual per-trunk cost decreases as the policy becomes more efficient. Table 21: Evolution of success, tool use, and generation cost during RTPO training. Training point Task success Tool calls/trunk Tool-execution success Generated tokens/trunk Step 10 15.63% 7.34 74.04% 8,013.5 Step 20 37.50% 2.06 72.73% 7,758.8 Step 30 50.00% 0.97 87.10% 3,533.3 Step 40 56.25% 1.84 94.92% 5,469.0 Step 50 40.63% 0.94 93.33% 1,669.3 From Step 10 to Step 50, tool calls decrease from 7.34 to 0.94 per trunk, generated tokens decrease from 8,013.5 to 1,669.3 per trunk, and tool-execution success increases from 74.04% to 93.33%. Tool use therefore becomes less frequent and more reliable as training progresses. G.8 Further Distinctions from Related Methods SeeUPO. SeeUPO and RTPO both use reverse-order sequential updates at the procedural level, but they differ in motivation, theoretical object, and algorithmic mechanism. SeeUPO abstracts multi-turn interaction as sequentially executed multi-agent bandits and uses backward induction to establish monotonic improvement and global convergence for critic-free backbone algorithms. RTPO instead begins from three structural inconsistencies in a flattened multi-turn training pipeline: Rollout–Training Mismatch, Trajectory-Only Credit Assignment, and Long-Horizon Policy Drift. Its reverse order is one component of a turn-boundary formulation that is combined with state-matched sibling comparison and on-policy continuation. The contribution is therefore not the isolated use of reverse order, but the unified diagnosis, formalization, algorithm, and guarantees for the three coupled failure mechanisms. ArCHer. ArCHer addresses delayed reward in long-horizon multi-turn interaction through a hierarchical actor–critic design. Its high-level component learns turn-level values with off-policy value-based RL, and its low-level component uses the critic to train the token-level policy within each turn. RTPO does not learn an explicit critic; it constructs a turn-level Monte Carlo advantage from sibling returns sampled from the same boundary state. ArCHer also does not directly target the rollout–training conditioning mismatch or the asynchronous downstream-continuation drift analyzed by RTPO. REFUEL. REFUEL and RTPO both avoid an independent critic, but they address different mismatches. REFUEL uses covariate shift to describe the difference between training histories generated by a reference policy and deployment histories generated by the current learner. It iteratively collects self-generated data and reformulates multi-turn optimization as relative-future regression tasks. RTPO’s Rollout–Training Mismatch occurs within the same sampled batch, when rollout and likelihood recomputation condition on different contexts for the same tokens. Thus, REFUEL addresses policy-induced covariate shift across data-collection stages, whereas RTPO addresses context inconsistency between rollout and training-time recomputation. The matched τ3τ^3-Airline results in Table 8 additionally show higher final success, more reliable termination, and shorter responses for RTPO. R3 and SRL. R3 mitigates sparse-reward exploration by moving the curriculum starting point backward along an expert reasoning trajectory; its reverse mechanism is a demonstration-based reverse curriculum. SRL also relies on expert trajectories and derives step-wise supervision from similarity between model and expert actions. RTPO remains outcome-supervised and on-policy, estimates turn-level advantages from sibling continuations at the same boundary state, and jointly addresses conditioning-context mismatch, upstream-state contamination, and asynchronous continuation drift. G.9 Additional Limitations The supplementary results expose several limitations. First, the strict convergence guarantee in Theorem 1 belongs to the turn-level tabular formulation with exactly fixed downstream policies. A shared neural policy only approximates this recursive structure and does not inherit a global convergence guarantee for non-convex optimization. Second, RTPO is more expensive to train than GRPO. With G=3G=3, wall-clock time and GPU-hours increase by approximately 41.3%. Increasing to G=4G=4 improves Pass@1 and produces more concise inference, but raises training-generation tokens by approximately 152.8%, revealing a substantial performance–cost trade-off. Third, even with G=4G=4, the zero-advantage rate in the sparse binary-reward Airline environment remains above 80%. Denser rewards, adaptive sibling sampling, or prioritized selection of turn boundaries may improve the density and efficiency of the learning signal. Fourth, the online Airline success rate decreases from 56.25% at Step 40 to 40.63% at Step 50, indicating possible late-stage over-optimization on a limited set of sparse-reward training tasks. Finally, the original experiments report averages over three runs and include Qwen3-4B and Qwen3-8B, with K=3K=3 turns for mathematical reasoning and K=6K=6 turns for web-search tasks. Broader per-seed stability curves, additional model scales and turn lengths, and intermediate synchronization schemes based on a fixed interval or policy KL remain useful directions for future work.