acceptodds
Under review as a conference paper at ICLR 2027

RTPO: Reverse-Turn Policy Optimization for Stabilizing Agentic RL Training

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 results showing that RTPO eliminates rollout–training context mismatch under matched conditioning, reduces turn-level credit bias, and enables drift-free on-policy continuation, while further establishing convergence of reverse-order optimization 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.

Primary area:
reinforcement learning
Keywords:
Multi-turn RL

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_SWAtOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

RTPO is a framework that aims to stabilize multi-turn LLM agent training by optimizing interaction turns in reverse order. It samples alternative continuations from the same environment state using the latest policy to assign credit to individual turns. It also keeps rollout and training contexts consistent while doing this. For Qwen3 models on several benchmarks agentic tasks, the authors report improvements over trajectory-level and turn-level RL baselines.

Critical strengths

Thank you so much for submitting your paper. Overall, the concept is clear to me and well explained. Below are my main strengths in no particular order.

  • Clever approach: I think your idea is very interesting and clever. Comparing alternative actions from the same environment state is not novel but a great concept for assigning credit to individual turns. What is novel though is how you regenerate their continuations with the latest policy. This makes a lot of sense, since earlier decisions should be evaluated against the downstream behavior of the current model. When you keep rollouts and training context consistent, your approach becomes very coherent and your results reflect that in training stability.
  • Great amount of detail in your analysis: you really go the extra mile and report many interesting evaluations for your method. For example, I really liked the rollout-training consistency and the on-/off-policy analysis. Reading the paper and seeing your effort to explain where your method's improvements arise is much appreciated and gives your method credibility.

There are also some other points that I really liked:

  • Presentation: Your figures are high-quality and explain the concept very well. I kept coming back to Fig. 2. Also, the links to the appendix were really helpful.
  • Implementation details: while I could not re-implement during review time, I think your pseudocode and expanded descriptions of context handling, sibling generation, and reverse-order updates help make the method concrete and easier to assess in the future.
Critical weaknesses

Unfortunately, despite the mentioned strengths, there are some weaknesses that make your assessment flawed in some cases and raise further questions.

  • Algorithmic improvements are questionable: despite the great amount of detailed analysis, I think the main comparison does not really show and/or separate the benefit of RTPO’s optimization procedure from correcting inconsistent rollout and training contexts. In Table 1, the baselines generate responses with earlier reasoning traces removed but train on reconstructed full histories. But your RTPO method preserves the actual rollout context. You could do the same for GRPO and SeeUPO as well, correct? This would also not introduce the reverse-order optimization then. You show that in Table 2 but with a different model (Qwen3-4B instead of Qwen3-8B). The average Pass@1 improvement over the strongest baseline is also relatively small (79 vs 78ish for ARPO). With that, your main results do not show how much improvement comes from the proposed algorithm and how much comes from correcting the context mismatch. You can easily convince me by showing the main baselines evaluated with matched rollout and training contexts for the original model.
  • Theory is not convincing (yet): your convergence analysis and result assume tabular representations and fixed policies, among other things. But your practical implementation (if I am not mistaken, please correct me if I am!) instead performs a finite number of clipped updates. But restricting the loss to one turn’s tokens does not freeze the model’s behavior at other turns, so an earlier-turn update can change previously optimized downstream behavior. In App. C you acknowledge this but in my opinion this leaves the theoretical justification for the practical reverse-order procedure incomplete. I could not find a comparison against forward-order or random-order updates with the same context handling, sibling sampling, and on-policy continuation. Such an ablation would help establish whether reverse ordering itself provides the claimed stabilization benefit when parameters are shared across turns. A small example could convince me, though!

Both of these points are easy to address and I would be happy to reconsider my score.

There are some other (mostly weaker) points that I would like to rephrase as questions (down below) and are not critical.

Questions for authors

As mentioned above, there are some non-critical but nevertheless important points that I would like to phrase as questions to the authors.

1) Reporting Relative Improvements: Could you clarify how the main headline improvements of 21.50% over GRPO and 10.76% over SeeUPO were calculated? Using the overall scores in Table 1, I obtain relative improvements of approximately 14.80% and 6.90%. Your percentages appear to normalize the differences by the vanilla model’s score. Is that correct? If so, could you make the denominator explicit and distinguish these values from relative improvements over the respective baselines?

2) Compute Comparisons: again, I really appreciate the detailed cost reporting. You show that under equal GPU-hours, RTPO matches GRPO on Pass@1 while improving Pass@4 and other metrics. Does a similar advantage hold under equal compute on the main math and search tasks. Especially wondering about the stronger turn-level or tree-based baselines? Matching rollout counts alone may not capture differences in generated tokens, optimization work, and synchronization overhead. Just some comments here would be helpful.

3) Related work: I think the related work discussion would benefit from including TSR [1] and GiGPO [2]. TSR improves multi-turn agent training through search-guided rollout construction, making it relevant for assessing the benefit of RTPO’s particular combination of branching, credit assignment, and reverse-order updates. GiGPO estimates local advantages by grouping actions from repeated environment states, which is closely related to RTPO’s state-matched sibling comparisons. Including these works would help clarify what RTPO contributes beyond improved rollout generation and existing state-based credit assignment.

[1] TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agents [2] Group-in-Group Policy Optimization for LLM Agent Training

7 comments
AuthorsOpenReview ↗

Response(1/4)

Thank you for the thoughtful review. We appreciate your recognition of our key contribution, regenerating continuations with the current policy so that earlier decisions are evaluated in light of how that policy would continue from them. We are glad that the rollout–training consistency and on-/off-policy analyses helped explain the gains in training stability, and that Figure 2 and the pseudocode made the method and its implementation easier to follow.

Below, we address each of your concerns and questions point by point.

W1: Separating the contribution of the algorithm itself from that of "fixing the context"; evaluating context-consistent baselines on the original model

Thank you for the suggestion. Under the setting of Table 1 with the original model Qwen3-8B, now we implemented and trained "training–inference-consistent" versions (i.e., Context Matching (CM)) of the baselines (GRPO-CM, SeeUPO-CM). For each turn, these two versions compute the IS ratio under the same context that was actually used when that turn was generated. We found that both CM variants lead to longer outputs and more truncation; we therefore used a longer context limit of 16K and an evaluation limit of 3 turns, and sampled 16 times per problem.

Table R4: Context-consistent baselines (Qwen3-8B, each cell is Pass@1 / Pass@16)

MethodContextAIME24AIME25AIME26AMC23MATH500Avg. (5 benchmarks)Training GPU hoursTime per step (s)
GRPOInconsistent52.50 / 76.6738.33 / 56.6741.67 / 63.3385.00 / 97.5079.80 / 87.6059.46 / 76.3531.3723
GRPO-CMConsistent55.83 / 76.6735.21 / 63.3340.00 / 66.6783.91 / 100.0081.03 / 88.8059.20 / 79.0944.61030
SeeUPOInconsistent53.33 / 76.6335.21 / 58.3340.63 / 63.5484.06 / 97.5080.06 / 87.6358.66 / 76.7331.7732
SeeUPO-CMConsistent56.04 / 76.6736.25 / 60.0040.00 / 63.7585.16 / 97.5081.11 / 87.4859.71 / 77.0840.8941
RTPOConsistent56.67 / 80.0036.67 / 63.3345.83 / 66.6788.75 / 97.5081.86 / 88.8061.96 / 79.2629.2751

After matching the context, the five-benchmark average Pass@1 / Pass@16 of GRPO changes by −0.26 / +2.74 percentage points, and that of SeeUPO changes by +1.05 / +0.35 percentage points. Under the training–inference-consistent condition, RTPO still achieves the highest five-benchmark average Pass@1 / Pass@16 (61.96 / 79.26)

We will add this new result in the revised manuscript.

AuthorsOpenReview ↗

Response(2/4)

W2: The theory relies on tabular representations and fixed policies; a comparison with forward / random orders or a small example

Thank you for the careful reading. Theorem 1 focuses on an idealised tabular setting in which each turn's policy is optimised once and then frozen; as stated in Appendix C.1, it is not a convergence guarantee for the shared-parameter implementation. Such a gap between the analysed setting and the practical algorithm is common in many RL policy optimisation: for example, TRPO's monotonic-improvement theorem is stated for exact advantages and a maximum-KL penalty, whereas the practical algorithm uses sampled advantages, an average-KL constraint and neural policies (Schulman et al., 2015); likewise, exact global-convergence results for policy-gradient methods are typically established for tabular policies, while results with function approximation carry approximation-error terms (Agarwal et al., 2021).

To connect the theory more closely to our implementation, we provide below contexts that hold under shared parameters (Lemma A, Prop. B and Prop. C).

(1) Theory that does not rely on tabular representations or frozen downstream policies Notation. SkS_k is the boundary state at the start of turn k (the full visible history so far), UkU_k is the output of turn k, and RR is the terminal reward. dkπd_k^{\pi} is the distribution of SkS_k under policy π\pi and depends only on the upstream π<k\pi_{<k}; Qkπ(s,u)=E[R∣Sk=s,Uk=u]Q_k^{\pi}(s,u)=\mathbb{E}[R\mid S_k=s,U_k=u] (continuing with π\pi afterwards) depends only on the downstream π>k\pi_{>k}. For any k, J(π)=Es∼dkπ∑uπk(u∣s) Qkπ(s,u)J(\pi)=\mathbb{E}_{s\sim d_k^{\pi}}\sum_u \pi_k(u\mid s)\,Q_k^{\pi}(s,u).

Lemma A (exact stage decomposition). If π′\pi' differs from π\pi only in its behavior at turn k, then J(π′)−J(π)=Es∼dkπ[∑u(πk′(u∣s)−πk(u∣s)) Qkπ(s,u)].J(\pi')-J(\pi)=\mathbb{E}_{s\sim d_k^{\pi}}\Big[\sum_u\big(\pi'_k(u\mid s)-\pi_k(u\mid s)\big)\,Q_k^{\pi}(s,u)\Big]. Proof. The upstream is unchanged, so dkπ′=dkπd_k^{\pi'}=d_k^{\pi}; the downstream is unchanged, so Qkπ′=QkπQ_k^{\pi'}=Q_k^{\pi}. Substituting into the expression for JJ above and subtracting gives the result. The proof only uses the fact that the behavior outside turn k is unchanged; it requires neither a tabular representation nor a frozen downstream.

Corollary (turn-by-turn decomposition). Let π(k)=(π<k,π≥k′)\pi^{(k)}=(\pi_{\lt k},\pi'_{\ge k}), i.e., the new policy is used from turn kk onward and the old policy before it. Adjacent terms differ only at turn kk, so by Lemma A

J(π′)−J(π)=∑k=1KEs∼dkπ[∑u(πk′−πk)(u∣s) Qkπ(k+1)(s,u)],J(\pi')-J(\pi)=\sum_{k=1}^{K}\mathbb{E}_{s\sim d_k^{\pi}}\Big[\sum_u\big(\pi'_k-\pi_k\big)(u\mid s)\,Q_k^{\pi^{(k+1)}}(s,u)\Big],

where the states come from the old upstream and the continuations come from the updated downstream.

Prop. A (unbiasedness with a single trunk sample). RTPO samples the trunk only once at the start of each sweep (the states follow dkπd_k^{\pi}), and at each stage regenerates the siblings and continuations with the latest parameters. If each stage changes only the behavior of its own turn, then when the update order is reverse, K,K−1,…,1K,K-1,\dots,1, the stage-k objective is exactly an unbiased estimate of the k-th term above: when turn k is processed, the upstream has not yet been updated, so the trunk states still follow the current dkd_k; the downstream has already been updated, and the continuations are generated by the current parameters. Hence the sum of the stage objectives equals the true improvement. For any other order, some upstream turn is always updated before turn k, so the current dkd_k in general no longer equals the trunk distribution; unless the trunk is resampled before that stage, the objective of that stage is biased (the example in Prop. D below is one instance).

AuthorsOpenReview ↗

Response(3/4)

Prop. B (improvement lower bound under shared parameters). Remove the condition that each stage changes only its own turn. Let θ0→θ1→⋯→θK\theta_0\to\theta_1\to\dots\to\theta_K be the parameters after each stage within one sweep, and AkA_k the objective of stage kk. Then

J(θK)−J(θ0)≥∑kAk−c,Rmax⁡∑k(∑j≠kEs∼djTV(πjθk,πjθk−1)(s)⏟change to other turns in this stage+TV(dkθk−1,dkθ0)⏟shift of trunk states),J(\theta_K)-J(\theta_0)\\ \ge\\ \sum_k A_k-c\\,R_{\max}\sum_k\Big(\underbrace{\textstyle\sum_{j\ne k}\mathbb{E}_{s\sim d_j}\mathrm{TV}\big(\pi_j^{\theta_k},\pi_j^{\theta_{k-1}}\big)(s)}_{\text{change to other turns in this stage}}+\underbrace{\mathrm{TV}\big(d_k^{\theta_{k-1}},d_k^{\theta_0}\big)}_{\text{shift of trunk states}}\Big),

which has the same form as TRPO's "surrogate objective minus a divergence penalty".

Proof sketch. Within each stage, split the parameter change into "changing only turn kk" and "changing the other turns". The former is handled by Lemma A, and each term of the latter is controlled by ∣∑u(π′−π)Q∣≤2Rmax⁡TV\lvert\sum_u(\pi'-\pi)Q\rvert\le 2R_{\max}\mathrm{TV}. The difference between the trunk distribution and the current dkd_k is likewise controlled by TV.

The key difference lies in the second drift term. Under reverse order, the upstream turns are affected within the sweep only indirectly through parameter sharing, so this term contains only unintended cross-turn changes. Under forward and random orders, it also contains the intended updates of the upstream turns.

Prop. C (convergence to a stationary point for any order). Each stage is one (clipped) policy-gradient step. At the start of a stage, the gradient of the stage-k objective equals the turn-k term of ∇J\nabla J plus an O(η)O(\eta) bias, which comes from the parameter changes made by the earlier stages of the same sweep; this holds for any order. A whole sweep is therefore one step along ∇J\nabla J with an O(η2)O(\eta^2) error. When JJ is LL-smooth, the gradient estimates have bounded variance, and the step sizes satisfy ∑tηt=∞\sum_t\eta_t=\infty and ∑tηt2<∞\sum_t\eta_t^2<\infty, the standard nonconvex stochastic-gradient analysis gives lim inf⁡t∥∇J(θt)∥=0\liminf_t\|\nabla J(\theta_t)\|=0.

Prop. D (Theorem 1 is a special case; a small example that can be computed by hand). Under the protocol "each turn is optimized once and then frozen", reverse order is exactly backward induction in dynamic programming and reaches the recursive optimum in one pass (Theorem 1). Other orders cannot always do so in one pass, as the following two-turn problem shows:

  • At turn 1, choose aa or bb. After bb, the reward is 0.5 regardless of what turn 2 does. After aa, choosing xx at turn 2 yields 1 and choosing yy yields 0; the initial policy chooses xx with probability 0.1.
  • forward: Optimize turn 1 first. Here Q1(a)=0.1<Q1(b)=0.5Q_1(a)=0.1<Q_1(b)=0.5, so it chooses bb and freezes; the final reward is 0.5.
  • reverse: Optimize turn 2 first, choosing xx after aa; then optimize turn 1, where now Q1(a)=1>0.5Q_1(a)=1>0.5, so it chooses aa; the final reward is 1, i.e., optimal.
  • random: With probability 1/2, turn 1 is processed first, with the same result as forward.
  • When multiple sweeps are allowed, each sweep makes at least one more turn (counting backward from the last turn) optimal, so any order reaches the optimum within at most K sweeps; reverse needs only one.

Therefore, under shared parameters, the role of reverse order is to obtain unbiased stage objectives from a single trunk sample and to confine the error to unintended cross-turn drift (Prop. B), instead of guaranteeing that the downstream policy no longer changes.

(2) Comparison changing only the update order. Setting: Qwen3-4B, math task. We compare three orders, reverse, forward and random, where random re-permutes the turns at every step. Controlled variables: everything except the order is identical, including context handling (rollout and training use the same context), the number of siblings per boundary state, regenerating the continuations with the latest parameters at each stage, as well as the data, number of steps and hyperparameters.

Table R1: Comparison of update orders

OrderPass@1 step 10step 20step 30GPU hours (step 30)
reverse0.750.820.8516.56
forward0.700.780.7815.99
random0.710.790.7916.55

When the trunk is sampled only once per sweep, reverse order avoids the shift in the trunk state distribution caused by upstream turns being explicitly updated first; the remaining shift comes only from indirect cross-turn changes caused by parameter sharing. In the experiment that changes only the update order, the three orders use similar training GPU hours, and reverse order reaches a Pass@1 of 0.85 at step 30, 7 and 6 percentage points higher than forward and random, respectively.

We will add this new result in the revised manuscript.

Reviewer_qWt1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Reverse-Turn Policy Optimization (RTPO) to stabilize multi-turn agentic RL. RTPO combines reverse-order policy updates, state-matched sibling rollouts for turn-level credit assignment, and on-policy continuation to address context mismatch and policy drift. Experiments on mathematical reasoning and tool-use benchmarks demonstrate improvements over existing RL methods.

Critical strengths
  • The paper addresses training instability in multi-turn agentic RL, particularly credit assignment and policy drift, which are important challenges for long-horizon agent training.
  • State-matched sibling rollouts provide a more localized advantage signal, while on-policy continuation helps reduce the impact of stale downstream trajectories.
  • RTPO achieves competitive performance across mathematical reasoning and knowledge-intensive benchmarks, with additional evaluations on stateful tool-use tasks.
Critical weaknesses
  1. The main components of RTPO are closely related to existing methods. Reverse-order turn-level optimization has already been explored in SeeUPO, while tree-based credit assignment is studied in TreeGRPO and ARPO. On-policy continuation is also a relatively straightforward way to avoid stale rollouts. The paper should better clarify what fundamentally distinguishes RTPO from combining these existing techniques.

  2. Although the paper evaluates credit assignment and on-policy continuation separately, it does not directly establish the necessity of reverse-order optimization. In particular, a forward-order baseline using the same state-matched sibling rollouts and on-policy continuation would help determine whether the reverse training order provides additional benefits.

  3. The convergence analysis assumes tabular policies and fixed downstream policies. However, RTPO uses a shared-parameter neural network, where updating an earlier turn can also modify the policies for previously optimized downstream turns. Consequently, the theoretical guarantees do not directly apply to the actual training algorithm.

  4. The paper treats context mismatch as a structural limitation of flattened trajectory optimization. However, this mismatch appears to depend on how the training pipeline reconstructs contexts. Existing implementations could potentially preserve the exact rollout context without adopting reverse-order optimization. The paper should clarify whether this issue is inherent to existing algorithms or specific to the evaluated implementations.

Questions for authors

see weaknesses

9 comments
AuthorsOpenReview ↗

Response(1/6)

Many thanks for your comments and for recognising our contribution to stabilising long-horizon agent training by addressing credit assignment and policy drift, as well as the breadth of our evaluation. We address the weaknesses you raised point by point below.

W1: The fundamental differences between RTPO and SeeUPO, Tree-GRPO and ARPO

Existing methods and RTPO differ in both the problems they address and the assumptions underlying their theoretical guarantees. We will clarify these differences in the revised manuscript, as detailed below.

1. Reverse order: in RTPO it is the most efficient choice, not a prerequisite for convergence.

  • SeeUPO models multi-turn interaction as heterogeneous multi-agents acting sequentially and borrows the monotonic improvement theorem of HAML; its convergence guarantee holds only under reverse order. Its experiments also show a strong dependence on the order: on Qwen3-14B (SeeUPO Table 4), the average avg@4 is 55.20 and 42.29 for the natural and random orders, versus 60.80 for reverse order; with random order, AppWorld drops from 63.60 to 33.33.
  • RTPO's stage decomposition (Lemma A) holds for any order, and every stage regenerates the continuations, so any order is a valid algorithm that converges to a stationary point (Prop. C). The advantage of reverse order is efficiency: a single trunk sample suffices to make every stage objective unbiased (Prop. A, see W2), and one pass completes the sweep. The experiments agree: when only the update order is changed (Table R1, see W2), forward and random both train stably and keep improving (Pass@1 rises from 0.70 / 0.71 to 0.78 / 0.79), and reverse order is the best (0.85).

2. State-matched siblings: handling both the upstream and the downstream, not only the upstream. Eq. (3) of the paper decomposes the trajectory advantage into an upstream state term, the true advantage of turn k, and a downstream term.

  • ARPO and Tree-GRPO let branches share prefixes, and comparing branches under the same node cancels the upstream state term. However, the branch returns come from the leaves and are assigned to all tokens after the node: the contribution of downstream turns is still mixed into the signal of turn k, and the tokens of downstream turns also receive the advantage of turn k.
  • RTPO's siblings branch from the same boundary state SkS_k, and the loss acts only on the tokens of turn k: the upstream state term is canceled, downstream turns do not share the advantage of turn k, and downstream randomness enters only as zero-mean noise (Theorem 2).

3. On-policy continuation: necessary for unbiasedness under turn-wise updates, and inexpensive. Under turn-wise updates, downstream turns are updated first, so continuations sampled before the update become samples of the old policy; using them to estimate the value of turn k under the current downstream is biased.

  • SeeUPO corrects this with a product of the importance ratios of the updated turns, whose variance grows multiplicatively with the number of turns, and clipping then introduces bias; the branches of ARPO and Tree-GRPO are all sampled once before the update.
  • RTPO regenerates the continuations with the latest parameters at every stage, so the importance weight is always 1 (Theorem 3). Table 3 of the paper compares the two approaches: the off-policy version reuses the continuations from the initial rollout and corrects them with truncated importance weights; the on-policy version is higher by 5.83, 3.50 and 7.00 percentage points on GAIA, WebWalkerQA and XBench, respectively, and essentially on par on HLE (−0.33). The overhead of regeneration is also small: RTPO's time per step is close to GRPO's (751 s vs. 723 s, Table R4).

Therefore, RTPO introduces a novel contribution to each of the three existing components and integrates them into a single training procedure with theoretical guarantees. By Lemma A, for the stage-k objective to equal the true improvement, three conditions must hold simultaneously: comparing only actions at the same state (state-matched siblings), trunk states following the current dkd_k (reverse order), and continuations reflecting the updated downstream (on-policy continuation). Directly combining SeeUPO's reverse order, the branches of ARPO / Tree-GRPO, and continuations sampled before the update breaks the third condition; the off-policy version in Table 3 of the paper is exactly this combination.

AuthorsOpenReview ↗

Response(2/6)

W2: The necessity of reverse order; comparison with a forward baseline using the same siblings and on-policy continuation

Theorem 1 of RTPO only proves the sufficiency of reverse order. Now we have added new theoretical results on necessity and a comparison that changes only the update order following your suggestion.

Theory (notation and Lemma A are given at the ending of our full response).

Prop. A (unbiasedness with a single trunk sample). RTPO samples the trunk only once at the start of each sweep (the states follow dkπd_k^{\pi}), and at each stage regenerates the siblings and continuations with the latest parameters. If each stage changes only the behavior of its own turn, then when the update order is reverse, K,K−1,…,1K,K-1,\dots,1, the stage-k objective is exactly an unbiased estimate of the k-th term of the turn-by-turn decomposition: when turn k is processed, the upstream has not yet been updated, so the trunk states still follow the current dkd_k; the downstream has already been updated, and the continuations are generated by the current parameters. Hence the sum of the stage objectives equals the true improvement. For any other order, some upstream turn is always updated before turn k, so the current dkd_k in general no longer equals the trunk distribution; unless the trunk is resampled before that stage, the objective of that stage is biased. The shared-parameter case is treated by Prop. B in W3.

Prop. D (Theorem 1 is a special case; a counterexample for necessity). Under the protocol "each turn is optimized once and then frozen", reverse order is exactly backward induction in dynamic programming and reaches the recursive optimum in one pass (Theorem 1). Other orders cannot always do so in one pass, as the following two-turn problem shows:

  • At turn 1, choose aa or bb. After bb, the reward is 0.5 regardless of what turn 2 does. After aa, choosing xx at turn 2 yields 1 and choosing yy yields 0; the initial policy chooses xx with probability 0.1.
  • forward: Optimize turn 1 first. Here Q1(a)=0.1<Q1(b)=0.5Q_1(a)=0.1<Q_1(b)=0.5, so it chooses bb and freezes; the final reward is 0.5.
  • reverse: Optimize turn 2 first, choosing xx after aa; then optimize turn 1, where now Q1(a)=1>0.5Q_1(a)=1>0.5, so it chooses aa; the final reward is 1, i.e., optimal.
  • random: With probability 1/2, turn 1 is processed first, with the same result as forward.
  • When multiple sweeps are allowed, each sweep makes at least one more turn (counting backward from the last turn) optimal, so any order reaches the optimum within at most K sweeps; reverse order needs only one.

Experiment: changing only the update order. Qwen3-4B, math task. We compare three orders, reverse, forward and random, where random re-permutes the turns at every step; forward is the baseline suggested by the reviewer. Everything except the order is identical: the same state-matched siblings (the same number of siblings per boundary state), regenerating the continuations with the latest parameters at each stage, context handling (rollout and training use the same context), as well as the data, number of steps and hyperparameters.

Table R1: Comparison of update orders

OrderPass@1 step 10step 20step 30GPU hours (step 30)
reverse0.750.820.8516.56
forward0.700.780.7815.99
random0.710.790.7916.55

Conclusion.

  • The three orders use similar training GPU hours, and reverse order reaches a Pass@1 of 0.85 at step 30, 7 and 6 percentage points higher than forward and random, respectively. Forward uses exactly the same siblings and on-policy continuation as RTPO, and the only difference is the update order; this gap therefore comes from reverse order itself. We will include the new theoretical analysis and experimental results in the revised manuscript.
AuthorsOpenReview ↗

Response(3/6)

W3: The convergence analysis assumes tabular policies and a fixed downstream, whereas RTPO uses a shared-parameter network

Thank you for the careful reading. Theorem 1 analyzes the idealized tabular version (independent parameters for each turn, each turn optimized once and then frozen), and Appendix C.1 of RTPO notes that it is not a convergence guarantee for a shared-parameter network. Such a gap between the analysed setting and the practical algorithm is common in many RL policy optimisation: for example, TRPO's monotonic-improvement theorem is stated for exact advantages and a maximum-KL penalty, whereas the practical algorithm uses sampled advantages, an average-KL constraint and neural policies (Schulman et al., 2015); likewise, exact global-convergence results for policy-gradient methods are typically established for tabular policies, while results with function approximation carry approximation-error terms (Agarwal et al., 2021).

To show more clearly how the theory corresponds to the actual implementation in RTPO, we give below the results under shared parameters together with proof sketches; the full proofs will be included in Appendices C.5–C.8 of the revised manuscript.

First, we clarify two points.

  • Theorems 2 and 3 apply to shared-parameter LLMs as they are. They characterize the estimators that RTPO actually uses, and neither proof uses a tabular representation or a frozen downstream.
  • The exact stage decomposition does not depend on the policy representation. Lemma A and the turn-by-turn decomposition (see the ending of this response) only use the fact that the behavior outside turn k is unchanged, and hold for any policy representation. The tabular assumption in Theorem 1 only serves to guarantee that each stage can be solved exactly; the structural properties that support reverse order (Prop. A and D, see W2) do not depend on it.

(1) Improvement lower bound under shared parameters (Prop. B). With shared parameters, the stage-k update also changes the other turns. Let θ0→θ1→⋯→θK\theta_0\to\theta_1\to\dots\to\theta_K be the parameters after each stage within one sweep, and AkA_k the stage-k objective (the single-turn improvement on the trunk states dkθ0d_k^{\theta_0} with the current downstream as continuation). Then J(θK)−J(θ0) ≥ ∑kAk − c Rmax⁡∑k(∑j≠kEs∼djTV(πjθk,πjθk−1)(s)⏟change to other turns in this stage+TV(dkθk−1,dkθ0)⏟shift of trunk states),J(\theta_K)-J(\theta_0)\ \ge\ \sum_k A_k\ -\ c\,R_{\max}\sum_k\Big(\underbrace{\textstyle\sum_{j\ne k}\mathbb{E}_{s\sim d_j}\mathrm{TV}\big(\pi_j^{\theta_k},\pi_j^{\theta_{k-1}}\big)(s)}_{\text{change to other turns in this stage}}+\underbrace{\mathrm{TV}\big(d_k^{\theta_{k-1}},d_k^{\theta_0}\big)}_{\text{shift of trunk states}}\Big), where c=2c=2 can be taken when the rewards lie in [0,Rmax⁡][0,R_{\max}]. This has the same form as the improvement lower bound of TRPO (Schulman et al., 2015), "surrogate objective minus a divergence penalty", and holds for parameterized policies.

Proof sketch.

  • Let πmid\pi^{\mathrm{mid}} be the policy that uses θk\theta_k at turn k and θk−1\theta_{k-1} at all other turns. By Lemma A, J(πmid)−J(θk−1)J(\pi^{\mathrm{mid}})-J(\theta_{k-1}) is exactly the single-turn improvement on dkθk−1d_k^{\theta_{k-1}}.
  • πθk\pi_{\theta_k} and πmid\pi^{\mathrm{mid}} differ only at turns j≠kj\ne k. Under a maximal coupling of their trajectories, the probability that they separate at turn j is at most Es∼djTV(πjθk,πjθk−1)(s)\mathbb{E}_{s\sim d_j}\mathrm{TV}(\pi_j^{\theta_k},\pi_j^{\theta_{k-1}})(s), so ∣J(θk)−J(πmid)∣≤Rmax⁡∑j≠kEs∼djTV|J(\theta_k)-J(\pi^{\mathrm{mid}})|\le R_{\max}\sum_{j\ne k}\mathbb{E}_{s\sim d_j}\mathrm{TV}.
  • The difference between the expectations of the single-turn improvement under dkθk−1d_k^{\theta_{k-1}} and under the trunk distribution dkθ0d_k^{\theta_0} is at most 2Rmax⁡ TV(dkθk−1,dkθ0)2R_{\max}\,\mathrm{TV}(d_k^{\theta_{k-1}},d_k^{\theta_0}).
  • Summing over k gives the result.

The difference between reverse order and the other orders lies in the second drift term: under reverse order, the upstream turns are affected within the sweep only indirectly through parameter sharing, so this term contains only unintended cross-turn changes; under forward and random orders, it also contains the intended updates of the upstream turns. When the parameters of different turns are decoupled, the first term is zero, and under reverse order the second term is also zero, so the decomposition is exact; if, in addition, each stage is assumed to be solved exactly, we recover Theorem 1.

Reviewer_7xuoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes RTPO to stabilize multi-turn agentic RL by combining matched rollout and training contexts, state-matched sibling continuations, and reverse-order turn-level updates. At each stage, fresh continuations estimate the current turn's advantage, while the policy loss is restricted to that turn's output tokens. Experiments cover mathematical reasoning, web search, and stateful tool use.

Critical strengths
  1. The paper is well-written and easy to follow.
  2. The paper identifies concrete problems in multi-turn RL pipelines and presents a coherent framework addressing context mismatch, turn-level credit assignment, and stale downstream continuations. The theoretical analysis provides useful motivation under its stated assumptions.
  3. The empirical evaluation is broad and includes targeted analyses of the proposed mechanisms, beyond final task performance alone. Improvements over strong baselines, together with additional stateful tool-use experiments and explicit training-cost measurements, support the practical value of the approach.
Critical weaknesses
  1. The independent contribution of reverse-order optimization remains unclear. The experiments examine context consistency, credit assignment, and on-policy continuation, but do not directly compare reverse, forward, and random turn-update orders while holding these other components fixed. Since reverse-order optimization is central to the paper, this comparison is important for establishing whether the ordering itself accounts for the gains.
  2. The training-cost trade-off deserves stronger validation on the main benchmarks. On τ3\tau^3-Airline (Appendix G.4), full RTPO training uses 21.48 GPU-hours versus 15.20 for GRPO, which makes me concerned about whether the performance gain is just an effect of more computation. The main math and search experiments match rollout counts rather than actual GPU-hours, leaving their performance advantage under equal training compute uncertain.
Questions for authors
  1. Could you compare reverse, forward, and random update orders with identical context handling, sibling sampling budgets, and policy synchronization frequency?
  2. Could you report Pass@1 versus cumulative GPU-hours on the main mathematical and search tasks, comparing RTPO with GRPO and SeeUPO under matched training budgets?
6 comments
AuthorsOpenReview ↗

Response(1/3)

We are glad you found the paper easy to follow. Thank you for recognising how our theoretical analysis of the training–rollout mismatch motivates RTPO and how comparisons with strong baselines help assess its practical value.

To address your comments, we have added new theoretical analyses and experiments. We summarise them below and then respond to each comment in turn.

  • New theory (a brief summary in the new Sec. 3.4 of the main text, with full proofs in the appendix):
    • Lemma A (Exact stage decomposition, Appendix C.5). When only turn kk is changed, the true improvement equals the single-turn improvement under the turn-kk boundary-state distribution dkd_k, with continuations following the current downstream policy. This holds independently of a tabular representation or whether the downstream policy is frozen. Addresses W1.
    • Prop. A (Estimability with a single trunk sample, Appendix C.5). When the trunk is sampled only once per sweep and continuations are regenerated at each stage, every stage's objective is unbiased if and only if the update order is reverse. Addresses W1.
    • Prop. D (Theorem 1 is a special case, Appendix C.8). Under Theorem 1's protocol of “optimizing each turn once and then freezing it,” reverse order is necessary and sufficient to attain the recursive optimum in one sweep, with necessity established by a two-turn counterexample. If multiple sweeps are allowed, any order can attain the optimum in at most KK sweeps. Addresses W1.
  • New experiments:
    • Table R1 (Appendix G.8). Comparison on Qwen3-4B varying only the update order (reverse, forward, random).
    • Table R2, Table R3 (Appendix G.9). Comparison of RTPO, GRPO, and SeeUPO at the same training GPU hours on the two main tasks, math and search, using the Table 1 setting (Qwen3-8B).
AuthorsOpenReview ↗

Response(2/3)

W1 & Q1: The independent contribution of reverse updates and a comparison of reverse, forward, and random with all other components held fixed

Our response proceeds in two steps. We first explain the theoretical role of reverse order and then present a controlled experiment that varies only the update order.

The theoretical role of reverse order. Let dkπd_k^{\pi} denote the distribution of the boundary state SkS_k at turn kk, which depends only on the upstream policy π<k\pi_{<k}. Let Qkπ(S,u)Q_k^{\pi}(S,u) denote the expected terminal reward from taking action uu at turn kk and then continuing under π\pi, which depends only on the downstream policy π>k\pi_{>k}. RTPO samples the trunk only once per sweep and regenerates sibling continuations at each stage using the latest parameters. In this procedure, when turn kk is processed in reverse order, the upstream turns have yet to be updated, so the trunk states follow the current dkd_k exactly. The downstream turns have already been updated, and continuations are regenerated using the current parameters, so the continuation rewards estimate the current QkQ_k. Every stage's objective is unbiased, and one sweep suffices. With forward or random order, however, there is always some upstream turn that is updated before turn kk, so the trunk states cease to follow the current dkd_k. Maintaining unbiasedness requires resampling the trunk before each stage. Otherwise, the stage objective is biased. Thus, reverse order is the only order that keeps every stage's objective unbiased with a single trunk sample (new Prop. A). Our new Prop. D further shows that, under Theorem 1’s protocol of optimising each turn once and then freezing it, reverse order is also the only order that can attain the recursive optimum in one sweep, and uses a two-turn counterexample to show that other orders cannot do so. If multiple sweeps are allowed, any order can attain the optimum in at most KK sweeps, while reverse order requires only one. We will add Sec. 3.4 to the main text to explain this, with the proofs of Lemma A and Prop. A in Appendix C.5 of the revised version and the proof of Prop. D in Appendix C.8.

Experiment varying only the update order (new experiment, with the full setup and curves to appear in Appendix G.8 of the revised version). We used Qwen3-4B to compare three orders on the MATH training set, reverse, forward, and random, with the random order reshuffled at each step. Everything apart from the order was identical, including context handling (the same context for rollout and training), the sibling sampling budget (G−1G−1 continuations per boundary state), policy synchronization frequency (continuations regenerated using the latest parameters at each stage), and the data, number of steps, and hyperparameters.

Table R1: Update order comparison (Qwen3-4B, math)

OrderPass@1 step 10step 20step 30GPU hours (step 30)
reverse0.750.820.8516.56
forward0.700.780.7815.99
random0.710.790.7916.55

With all other components held identical, reverse order yields higher training reward than forward and random orders throughout training. Forward and random orders both bias the stage objectives, so their performance is similar. Only reverse order keeps every stage's objective unbiased with a single trunk sample. Thus, reverse order makes an independent contribution to RTPO's gains.

We will include the new theoretical analysis and experimental results in the revised manuscript.

AuthorsOpenReview ↗

Response(3/3)

W2 & Q2: Comparison at the same training GPU hours

We appreciate your interest in post-training efficiency and agree that methods with the same rollout count may require different amounts of computation.

Regarding App. G.4. The cost of full RTPO training is 21.48 GPU hours. Table 16 in the same section (page 44, lines 2343–2361) gives a comparison at matched GPU hours (RTPO 15.55, GRPO 15.20). The two methods have the same Pass@1 (both 11.25%), while RTPO raises Pass@4 from 25.00% to 35.00% and the environment completion rate from 20.00% to 30.00%. In other words, on τ-Airline, RTPO's gains do not depend on additional compute. This point was not sufficiently prominent in the original text, and we will state it explicitly in the main text.

Comparison at equal GPU hours on the main experiments. To verify this on the main tasks, we reran training for math and search using the Table 1 setting (page 8, line 404) on the same hardware (4 × AMD MI355X), with Qwen3-8B (see App. E.3, pages 35–36, for training details). These are new experiments and will appear in Appendix G.9 of the revised version. Budget point: We take the GPU hours of the method that finishes training first and select models near that budget for the other methods. In practice, this was RTPO, which exhausted its 80,000-sample budget at step 35, using 29.2 GPU hours. For GRPO and SeeUPO, we use step 39, at 31.3 and about 31.7 GPU hours, respectively, slightly more than RTPO.

  • Evaluation: All three algorithms use the same sampling settings as in the paper. For AIME24, AIME25, AIME26, and AMC23, we sample four times per question and report Mean@4 (mean accuracy) and Pass@4 (at least one correct response out of four).

Table R2: Math at the same GPU-hour budget (Qwen3-8B, Table 1 setting, with Mean@4 / Pass@4 in each cell)

MethodTraining stepsTraining GPU hoursAIME24AIME25AIME26AMC23Average
GRPO3931.330.00 / 50.0020.00 / 40.0023.33 / 36.6763.13 / 85.0034.11/ 52.92
SeeUPO3931.732.50 / 58.3322.50/40.0030.00/37.5065.63/87.5037.66/55.83
RTPO3529.236.67 / 66.6722.50 / 40.0034.17 / 63.3371.88 / 92.5041.30 / 65.63

Table R3: Knowledge/Search at the same GPU-hour budget (Qwen3-8B) Budget point: We take the GPU hours of the method that finishes training first and select models near that budget for the other methods. In practice, this was RTPO, which exhausted its sampling budget at step 11, using 9.96 GPU hours. For GRPO and SeeUPO, we use steps 16 and 14, at 10.10 and about 9.82 GPU hours, respectively.

  • Evaluation: All three algorithms use the same sampling settings as in the paper. We sample four times per question and report the mean F1 score.
MethodTraining stepsTraining GPU hoursHotpotQA2WikiAverage
GRPO1610.1050.352.751.5
SeeUPO149.8253.156.554.8
RTPO119.9654.957.956.4

On the mathematical reasoning task, RTPO used 29.2 GPU-hours for training, compared with 31.3 for GRPO. Averaged across the four items, RTPO outperformed GRPO by 7.19 points in Mean@4 and 12.71 points in Pass@4, and SeeUPO by 3.64 and 9.80 points on the same metrics, respectively. On the knowledge reasoning task involving search, RTPO outperformed GRPO by 4.9 points and SeeUPO by 1.6 points at comparable training costs.

We will include the above new experimental results in the revised manuscript.

In conclusion, thank you for your positive assessment and for pointing out where the evidence could be clearer. If the additional analysis addresses those points and strengthens your confidence in our findings, we would welcome a higher score to reflect your updated assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.