acceptodds
Under review as a conference paper at ICLR 2027

Fine-grained Credit Assignment for Multi-turn Critic-free LLM Reinforcement Learning with Sequential Equilibrium Optimization

Abstract

Critic-free group-based methods have shown strong potential for single-turn large language model (LLM) reinforcement learning (RL), owing to their reduced memory requirements and stable optimization. However, complex tasks often require multi-turn interactions, where the sparsity and delayed nature of verifiable rewards pose a fundamental challenge for credit assignment. Although recent methods alleviate this issue by introducing additional step-level groups or related mechanisms, trajectory-level grouping remains an essential component of advantage estimation and thus continues to exert a substantial influence on optimization. This motivates us to ask whether credit assignment can be further improved from a complementary perspective by directly refining the computation of trajectory-level advantages. To this end, we propose Sequential Equilibrium Policy Optimization (SEPO), a general credit assignment algorithm that can be flexibly integrated with a variety of existing group-based methods. SEPO introduces a novel multi-agent perspective that formulates multi-turn interaction as a fully cooperative sequential game. It then derives a solution to the subgame perfect Nash equilibrium through best-response optimization and aligns this solution procedure with multi-turn LLM RL, yielding more accurate trajectory-level credit assignment. Extensive experiments on ALFWorld and WebShop with Qwen2.5-1.5B, Qwen2.5-7B, and Qwen3-4B demonstrate that SEPO consistently improves over GRPO, GiGPO, and DAPO while holding the amount of data used for actor updates unchanged, validating the effectiveness and generality of its credit assignment mechanism.

Primary area:
reinforcement learning
Keywords:
LLM, Reinforcement Learning, Credit Assignment

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_vgjKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Sequential Equilibrium Policy Optimization (SEPO), a critic-free method for assigning credit to individual turns or chunks in multi-turn LLM reinforcement learning. SEPO shares a common interaction prefix across rollouts, explores alternative actions within a selected chunk, completes the remaining interaction at an exploitation temperature, and applies group-relative advantages only to the selected chunk. It motivates this procedure by treating turns as cooperative agents and analyzing best-response updates toward a subgame-perfect equilibrium. Experiments combine SEPO with GRPO, GiGPO, and DAPO across ALFWorld, WebShop, and seven search-based QA benchmarks, reporting success-rate improvements of up to 11 percentage points.

Critical strengths

SEPO addresses an important problem with an intuitive mechanism: comparing alternatives from the same history makes terminal rewards more informative about the particular decision being trained. Its compatibility with several existing algorithms, without an additional critic or reward model, is practically attractive. The empirical evaluation is reasonably broad, spanning several model sizes, three task families, and an additional vision-language Sokoban experiment; the strongest improvements occur with DAPO. Crucially, the appendix includes meaningful controls beyond the main fixed-update-data comparisons: against a larger-batch DAPO baseline with matched rollout volume, SEPO improves ALFWorld success from 88% to 93% and WebShop success from 80% to 84%. Component ablations, three-seed results for the main interactive environments, and comparisons with AT²PO strengthen the evidence that the rollout design contributes something beyond simply collecting more samples.

Critical weaknesses

The principal weakness is the gap between the theory and the implemented algorithm. Theorem 4.4 assumes independently parameterized decisions, exact best responses, and fair coverage of all histories, whereas SEPO uses a shared neural policy, sampled alternatives, PPO updates, and preferentially sampled histories; therefore, the theorem does not establish convergence or non-interference for actual SEPO training.

Questions for authors

Since HGPO directly addresses historical-context inconsistency and is discussed in your related work, could you compare SEPO against HGPO under matched rollout and wall-clock budgets? Does adding SEPO to HGPO provide further improvements?

7 comments

Thank you for your thoughtful reviews. In response to the feedback, we have made the following revisions:

  • Abstract and Introduction: We now explicitly state that SEPO requires additional rollouts.
  • Section 4.2: We clarify how Theorem 4.4 relates to SEPO.
  • Section 4.3: We explain how best-response updates motivate the design of SEPO.
  • Section 4.3: We add Theorem 4.6, which directly connects the variance decomposition in Proposition 4.5 to the mean squared error of the advantage estimator.
  • Section 5.5: We visualize how updating one chunk affects other chunks under parameter sharing and add an empirical analysis of advantage estimation error.
  • Appendix A.3: We provide the proof of Theorem 4.6.
  • Appendix D.1: We report how token counts, the number of turns used for policy updates, and training time per step vary with the number of agents.
  • Appendix D.4: We expand the comparisons with structured rollout baselines and report results across multiple random seeds.
  • Appendix D.5: We add ablation experiments to distinguish the contribution of history-distribution alignment from that of improved advantage estimation.
  • Appendix D.6: We add more comparisons in which all methods use the same number of rollouts.

We appreciate your feedback and hope that our response addresses your concerns.

Q1 About Theorem and SEPO

1.1 Theorem 4.4 does not directly apply to the implemented algorithm

Thank you for pointing out the need to distinguish more clearly between the theory and its implementation. Theorem 4.4 motivates SEPO by providing a theoretical guarantee for finding a subgame-perfect equilibrium (SPE) through best-response updates. It does not directly analyze SEPO itself. Our argument proceeds in three steps. Section 4.1 models multi-turn LLM interactions as a multi-agent game. Section 4.2 presents a best-response method for solving the game within this framework. Section 4.3 then introduces an approximation of these updates for multi-turn LLMs. Thus, Theorem 4.4 establishes the guarantee for the best-response updates in Section 4.2, whereas SEPO approximates this update principle in the multi-turn LLM setting.

The connection between the theory and SEPO lies in the local evaluation objective, how candidates are compared, and where credit is assigned. Given a history hh and a fixed continuation policy μ\mu, a local best response compares the conditional values of candidate actions at hh, given by Qμ(h,a)=E[R∣h,a;μ]Q^\mu(h,a)=\mathbb{E}[R\mid h,a;\mu].

SEPO reflects this principle in three design choices:

  • Prefix sharing fixes the starting point for comparison. Candidates in the same group share the same history, so their returns can be compared to assess the current decision at that history.
  • Exploration within the target block and a common continuation policy allow candidates to be compared locally. SEPO samples different candidates for the target block and evaluates their continuations using the same parameter snapshot and decoding rule. Suffix validation uses the policy at the validation temperature as the continuation policy, so the comparison reflects the model’s behavior at evaluation time.
  • The loss mask directs the update to the target block being compared. Relative returns within the group are used to update the target block, so the training signal acts directly on the decision positions where the candidates differ.

The best-response perspective therefore guides how SEPO organizes rollouts, constructs the local credit signal, and applies the training objective. In this sense, it motivates SEPO and directly informs its design.

We agree that the main difference between Theorem 4.4 and SEPO lies in how they treat parameter sharing. To quantify how far a local update propagates under shared parameters, we conducted an additional experiment measuring how much an update to one turn affects other turns. In WebShop, we started from the same checkpoint of a previously trained model and ran four separate updates, each targeting only one of the four chunks. Holding the histories and response tokens fixed, we measured the KL divergence KL(πold∥πnew)\mathrm{KL}(\pi_{\mathrm{old}}\Vert\pi_{\mathrm{new}}) between the conditional token distributions before and after each update. To isolate the effect of each chunk, we reset the Adam optimizer’s momentum and disabled regularization terms, including the entropy loss, so that each update came solely from the selected chunk. For each update, we simulated the nonzero advantages that can arise with a group size of eight. We averaged the results over 64 repetitions, as shown in the table below.

Update ChunkTarget KL (×10−3\times 10^{-3})Other KL (×10−3\times 10^{-3})Other Target Ratio
13.3691.4090.418
23.1041.1860.382
32.1091.1230.532
42.1001.0680.508

For each of the four updates, the target chunk showed the largest mean KL divergence between the policies before and after the update. Mean KL divergence ranged from 2.10–3.37 × 10⁻³ for the target chunk and from 1.07–1.41 × 10⁻³ when averaged across the non-target chunks. Across the four updates, the divergence for the target chunk was 1.88–2.62 times the average for the non-target chunks. These results show that when an LLM shares parameters across turns, an update at a single chunk, history, or turn also affects decisions elsewhere, but the average effect is substantially smaller than the effect on the target chunk. The assumption of independent parameters therefore does not apply directly in this setting. One possible explanation for the smaller effects elsewhere is that the LLM’s representational capacity limits the extent to which updates at different decision points influence one another. Developing techniques to further reduce these effects of parameter sharing is an important direction for future research.

We have revised the wording in Section 4.2 of the main text to clarify the role of Theorem 4.4. We have also added the experimental results in Figure 5(a) and the accompanying analysis in Section 5.5.

1.2 Using sampled alternatives and PPO updates

The best-response problem defines the local optimization objective, and PPO provides a policy-gradient method for optimizing it under a parameterized policy.

For a fixed history hh and continuation policy μold\mu_{\mathrm{old}}, the local objective for the current action distribution qq is

F(q)=Ea∼q(⋅∣h)[Qμold(h,a)].F(q)=\mathbb{E}_{a\sim q(\cdot\mid h)}\left[Q^{\mu _{\mathrm{old}}}(h,a)\right].

Over the space of unrestricted action distributions, any maximizer of FF assigns all probability mass to actions with the highest conditional value. Such a distribution is an exact best response. For a parameterized policy qθq_\theta, the same objective has the following policy gradient:

∇θF(qθ)=Ea∼qθ(⋅∣h)[∇θlog⁡qθ(a∣h)(Qμold(h,a)−b(h))],\nabla_\theta F(q_\theta)=\mathbb{E}_{a\sim q _\theta(\cdot\mid h)}\left[\nabla _\theta \log q _\theta(a\mid h)\left(Q^{\mu _{\mathrm{old}}}(h,a)-b(h)\right)\right],

where both the continuation policy and the baseline are fixed during local optimization. An exact best response and a policy-gradient update can thus target the same local value objective. They differ in how they optimize it.

In practice, we use sampled local comparisons to construct PPO’s clipped surrogate objective. At the old policy, the importance ratio is 1 and clipping is inactive, so the clipped and unclipped surrogates have the same gradient. As the policy changes, clipping limits how much certain samples can continue to drive the update. A single PPO update is therefore a step toward optimizing the local value objective, without necessarily attaining its exact maximizer.

1.3 About preferentially sampled histories

We use validation histories to improve sample efficiency. With a limited number of updates, prefix validation lets us devote more updates to histories the policy is likely to encounter during validation.

For example, consider a history h1h_1 sampled from the current policy at the validation temperature. Because the policy has been optimized for the task, h1h_1 typically reflects a reasonable sequence of decisions from which the task can still be completed. Prefix validation therefore concentrates training on histories that are useful for completing the task and that better reflect those encountered during validation.

Without prefix validation, the policy may sample a history h2h_2 in which an earlier error has already made the task impossible to complete. Training on h2h_2 may then provide no useful signal, reducing the proportion of effective training samples. The marked drop in performance when we removed prefix validation in our ablation study supports this explanation.

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

This paper addresses the coarse-grained credit assignment problem in multi-turn reinforcement learning for large language models (LLMs), where sparse and delayed rewards make it difficult to attribute final outcomes to specific interaction turns. The authors introduce Sequential Equilibrium Policy Optimization (SEPO), a critic-free algorithm that reformulates multi-turn interactions as a fully cooperative sequential game solved via subgame perfect Nash equilibrium (SPNE). SEPO isolates individual turn contributions using a tailored rollout scheme featuring prefix sharing, update exploration, and suffix exploitation, alongside a turn-chunking strategy to manage computational costs. Extensive experiments across embodied agent tasks (ALFWorld, WebShop), search-augmented multi-step QA, and visual tasks demonstrate that SEPO achieves consistent and notable performance gains over strong baselines like GRPO, GiGPO, and DAPO.

Critical strengths
  • Highly Valuable Problem and Strong Empirical Performance: Resolving sparse and imprecise reward attribution in multi-turn RL is a fundamental and critical challenge for LLM agents. The paper validates SEPO across a wide range of complex benchmarks, demonstrating convincing and consistent performance boosts over strong baselines without relying on an explicit process reward model (PRM) or Critic.

  • Innovative Game-Theoretic Formulation: Reframing multi-turn interaction as a fully cooperative sequential game and applying parallel best-response updates provides a fresh and insightful perspective. The prefix-sharing and suffix-exploitation sampling design conceptually isolates inter-turn variance, delivering an elegant and principled approach to fine-grained credit assignment.

Critical weaknesses

Increased Rollout Computational Overhead: Because SEPO constructs independent rollout groups for each turn chunk to enable isolated exploration, the sampling time scales with the number of chunks (KK). While this additional cost is well-justified by the significant performance gains, it increases training latency compared to standard GRPO.

Questions for authors
  • What are the authors' thoughts on using adaptive or semantic-based turn chunking, rather than a fixed chunk size KK, to further optimize sampling efficiency?

  • Could the authors provide additional insights into how SEPO scales when applied to environments with extremely long interaction horizons (e.g., >10 turns)?

2 comments

Thank you for your kind reviews and constructive suggestions. In response to the feedback, we have made the following revisions:

  • Abstract and Introduction: We now explicitly state that SEPO requires additional rollouts.
  • Section 4.2: We clarify how Theorem 4.4 relates to SEPO.
  • Section 4.3: We explain how best-response updates motivate the design of SEPO.
  • Section 4.3: We add Theorem 4.6, which directly connects the variance decomposition in Proposition 4.5 to the mean squared error of the advantage estimator.
  • Section 5.5: We visualize how updating one chunk affects other chunks under parameter sharing and add an empirical analysis of advantage estimation error.
  • Appendix A.3: We provide the proof of Theorem 4.6.
  • Appendix D.1: We report how token counts, the number of turns used for policy updates, and training time per step vary with the number of agents.
  • Appendix D.4: We expand the comparisons with structured rollout baselines and report results across multiple random seeds.
  • Appendix D.5: We add ablation experiments to distinguish the contribution of history-distribution alignment from that of improved advantage estimation.
  • Appendix D.6: We add more comparisons in which all methods use the same number of rollouts.

We appreciate your feedback and hope that our response addresses your concerns.

Q1 Limitation on increased computational overhead

We acknowledge that the need for more rollouts is a key limitation of our method. To give readers a clearer picture of the trade-off between resource use and performance, the table below provides a more detailed comparison on WebShop using Qwen2.5-1.5B. For Global Seqlen Per Step, Update Sample Count Per Step, and Time Per Step, we report averages over the same five update steps across three random seeds. Although the exact values may vary with hardware conditions during training, the overall trends remain consistent.

As the number of agents increases, the total token count rises substantially, including tokens that are ultimately discarded. The increase is nonlinear: each additional agent tends to add fewer tokens. We attribute this mainly to lower variance, which reduces the amount of additional exploration. The reported count also includes copied tokens, so the number of tokens actually generated is lower.

The number of turns used for each update, including turns with zero advantage, remains roughly constant as the number of agents increases. This is consistent with our statement that the amount of data used per update is comparable across settings. The increase in training time per step also closely tracks the increase in token count.

Agent NumberGlobal Seqlen Per Step (All Generated Tokens)Update Sample Count Per Step (All Updated Turns including 0 Adv)Time Per StepFinal Performance (Success Rate)
1 (GRPO)51592810881790.63
276890411812940.63
398196910083470.67
4112874411203940.71

These results highlight a limitation of SEPO: it requires additional rollout tokens. Users can choose the number of agents to suit their rollout budget. We also provide a warmup strategy that reduces overall rollout costs by introducing SEPO later in training.

We have added these results and the accompanying analysis to Appendix D.1.

Q2 Adaptive or semantic-based turn chunking

We thank the reviewer for this constructive suggestion. We agree that adaptive turn chunking is the most important direction for future work on SEPO. The main limitation of fixed turn chunking is that chunk boundaries can cut across subtask boundaries. A single chunk may span several subtasks, while a single subtask may be split across two chunks. Because subtasks are often related, updating one chunk may then have a greater effect on other chunks. Adaptive turn chunking offers a way to address this issue.

We envision the following approach:

  1. For each group in a batch, independently sample one trajectory at the validation temperature.
  2. Identify up to KK key turns in each trajectory using signals such as abrupt changes in meaning or entropy, or the occurrence of a tool call.
  3. Use each key turn as the start of the chunk to be updated in the corresponding rollout. How to choose the end of the chunk remains an open question. The simplest option is to use a fixed chunk length.
  4. Apply the update to the selected chunk in each rollout.

We welcome further research in this direction.

Q3 About long interaction horizons

SEPO has shown some ability to handle long interactions in WebShop and ALFWorld. In our experiments, we capped interactions at 15 turns in WebShop and 50 turns in ALFWorld. As the resource comparison above shows, overall performance tended to improve as the number of chunks increased. At a given horizon, using more chunks means fewer turns per chunk, and these shorter chunks yielded better final performance. This suggests that if the number of chunks is held fixed, SEPO’s performance advantage may diminish as interactions grow longer.

Increasing the number of chunks also raises computational overhead, so the appropriate balance depends on the environment. Four chunks appear to be a reasonable choice for our WebShop and ALFWorld settings. For environments with more than 100 turns, such as Crafter, further experiments are needed to determine how many chunks to use. We regret that our current resources do not allow us to conduct a thorough performance comparison at such long horizons in the near term. We consider this one of our highest priorities for future experiments.

The table below reports the average number of turns per interaction at the beginning and end of training in ALFWorld and WebShop, using GRPO+SEPO with Qwen2.5-1.5B-Instruct.

WebShopALFWorld
Before (0 step)14.7749.41
After (150 steps)6.1435.32
Reviewer_mBi8OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Another XXPO paper which studies credit assignment in critic-free group-based RL (GRPO/GiGPO/DAPO) for multi-turn LLM agents. SEPO models turns as agents in a fully cooperative sequential game, proves that parallel best-response updates converge to a subgame-perfect equilibrium (Thm 4.4), and instantiates this as a rollout scheme: for each of K=4 turn chunks, N rollouts share a low-temperature prefix, sample N candidate actions at the chunk, complete with a low-temperature suffix, and the group-relative advantage is applied only to that chunk's tokens. Experiments on ALFWorld, WebShop, and 7 QA datasets across 4 backbones show improvements over all three base methods, largest with DAPO (+6-11 points).

Critical strengths

The rollout design itself is clean and the paper is empirically diligent: the equal-budget controls in Appendix D.5 (Larger Batch, and especially Larger Batch Same Data, which matches rollout count, update data, and turn selection while removing the structured rollouts) are exactly the right counterfactuals, and SEPO beating that control (0.75 vs 0.68 on ALFWorld) is the paper's best evidence that the rollout structure, not just the budget, matters. DAPO+SEPO also beats rollout-matched DAPO Larger Batch in means on all three aggregate metrics. The explore-at-chunk/exploit-elsewhere temperature asymmetry is a genuinely distinctive design choice; the K-analysis linking chunk granularity to the non-zero-advantage rate is coherent; the integration works across three base methods and four backbones; honest limitations and per-iteration timings are reported.

Critical weaknesses

The theory is decorative. Under its own assumption (i) (independent parameterization across agents and histories), the "fully cooperative sequential game" is a finite-horizon MDP with a tabular policy, Def. 4.2's Eq. (3) is the Bellman optimality equation, and Thm 4.4's proof is the policy improvement theorem (Howard 1960); game-theoretically it is better-response dynamics in an exact potential game (Monderer & Shapley 1996). The SPE vocabulary does no work under full cooperation — there are no incentive conflicts or equilibrium-selection issues. Worse, assumption (i) is the theorem's entire mechanism (the potential Psi increases only because updating one pair leaves all other decisions fixed), and it is maximally violated by the deployed algorithm: one shared LLM, updated simultaneously on all K chunks in Eq. (10), so no decision is ever held fixed. The Remark's appeal to "large parameter capacity" is an unsupported conjecture. The best-response claim also fails at the estimator level: Eq. (7) is an identity that holds for any action-independent baseline; each candidate's value is a one-sample return under a different (exploitation-temperature) continuation policy, i.e., a biased proxy; and the update is a clipped policy-gradient step, not an argmax. Proposition 4.5 is the law of total variance applied to return variance; it says nothing about the advantage or gradient estimator, and the suffix-exploitation bias is never discussed.

The headline framing hides the budget. The abstract's "holding the amount of data used for actor updates unchanged" omits that SEPO uses ~4x rollouts and ~2.2x wall-clock, and Section 5.2 presents Table 1 without flagging this. The paper's own D.5 control shows the GRPO gains are budget-explained: GRPO (Larger Batch) matches or beats GRPO+SEPO under equal rollout volume (0.77 vs 0.75 ALFWorld; ties on WebShop). So one third of the headline is an artifact of the comparison budget. The DAPO gains survive the control in means but with z approximately 1.0-1.8 at n=3 seeds — directionally suggestive, statistically underpowered; Table 1 reports no baseline stds at all.

The ablations undermine the central mechanism. Removing prefix sharing — the component Proposition 4.5 formalizes — costs only ~0.06 (0.75 to ~0.69) and stays above GRPO; the paper's own explanation is that low-temperature prefixes are already similar. The largest drop comes from w/o prefix validation, i.e., the temperature of prefix sampling. A defensible reading is that the gains come mostly from evaluating candidate actions under near-deterministic context — variance reduction via decoding temperature — while the game-theoretic machinery contributes the narrative.

Related work misses the nearest neighbors. "Siblings branching from a shared prefix, group-relative advantage among siblings, advantage localized to the diverging segment" is the established tree-rollout mechanism: Tree-GRPO (arXiv:2509.21240, ICLR 2026, same 7 QA benchmarks) and ARPO (arXiv:2507.19849, ICLR 2026) are the closest precedents and are not cited; segment-level advantages have SPO (arXiv:2505.23564); the turn-as-agent framing has SeeUPO (with a stronger reverse-order optimality result) and RTPO. Without Tree-GRPO/ARPO baselines, the marginal value over the closest family is undemonstrated.

Secondary issues: the QA results are single-run with the justification that evaluation is deterministic, which conflates eval with training determinism — +1 point averages there are indistinguishable from seed noise; the 7B baselines are imported from Feng et al. while the authors' own 1.5B GRPO rerun deviates -6.8 points from the same source (larger than every claimed 7B delta), and the weaker of the two published GiGPO variants is used on WebShop; the evaluation protocol (set sizes, held-out splits, Score/Succ definitions, QA metric) is never specified; Table 4 switches backbone (Qwen3-4B) relative to Table 2 (Qwen2.5-3B) without explanation.

Questions for authors

Do you agree Thm 4.4 is finite-horizon policy iteration restated in SPE vocabulary? If not, what does the game formulation buy beyond policy improvement in a cooperative MDP — and can you give any shared-parameter analog (e.g., a performance-difference bound quantifying the coupling error) connecting the theorem to the algorithm actually run? Given that w/o prefix sharing retains most of the gain and the largest factor is prefix temperature, can you isolate how much of the improvement comes from the two-temperature schedule alone (e.g., a trajectory-level GRPO group with exploitation-temperature rollouts)? Can you add Tree-GRPO and/or ARPO baselines on the QA suite under your update-data accounting? Can you report 3 seeds for the QA experiments and baseline stds for Table 1? What are the eval set sizes and splits for ALFWorld/WebShop, and how are WebShop Score and Succ. computed?

13 comments

Thank you for your constructive reviews. In response to the feedback, we have made the following revisions:

  • Abstract and Introduction: We now explicitly state that SEPO requires additional rollouts.
  • Section 4.2: We clarify how Theorem 4.4 relates to SEPO.
  • Section 4.3: We explain how best-response updates motivate the design of SEPO.
  • Section 4.3: We add Theorem 4.6, which directly connects the variance decomposition in Proposition 4.5 to the mean squared error of the advantage estimator.
  • Section 5.5: We visualize how updating one chunk affects other chunks under parameter sharing and add an empirical analysis of advantage estimation error.
  • Appendix A.3: We provide the proof of Theorem 4.6.
  • Appendix D.1: We report how token counts, the number of turns used for policy updates, and training time per step vary with the number of agents.
  • Appendix D.4: We expand the comparisons with structured rollout baselines and report results across multiple random seeds.
  • Appendix D.5: We add ablation experiments to distinguish the contribution of history-distribution alignment from that of improved advantage estimation.
  • Appendix D.6: We add more comparisons in which all methods use the same number of rollouts.

We appreciate your feedback and hope that our response addresses your concerns.

Q1 About Theorem and SEPO

1.1 Theorem 4.4 is equivalent to policy improvement in a finite-horizon MDP

When we take the full history as the state, the fully cooperative, finite-horizon sequential game in our paper admits an equivalent formulation as an undiscounted MDP with rewards only at termination. A subgame-perfect equilibrium (SPE) then corresponds to a policy that satisfies the optimality condition at every history. In this sense, Theorem 4.4 is an instance of the classical policy improvement principle for our parallel local update rule. This equivalence clarifies the theoretical connection between the two formulations while leaving room for each to offer a distinct perspective. The game formulation serves three purposes.

  • It explicitly decomposes the sequential optimization problem into local decision problems with a shared objective. We write the policy as π=(π1,…,πK)\pi=(\pi_1,\ldots,\pi_K), with one component per turn or block. All components share the same task return. For each component, the optimization problem is to determine how changing the current decision can improve that return, given the history and the policies of the other components. This decomposition identifies what is being optimized locally and which conditions must be held fixed when evaluating it. Credit assignment in multi-turn decision-making can thus be understood as assessing each cooperating decision-maker’s contribution to the shared return. Equivalence to the MDP ensures that the decomposition preserves the original task objective, while the game formulation provides a way to organize and analyze the local problems.

  • It distinguishes the quality of the overall outcome from the relative value of the current decision. The overall objective is to maximize expected terminal return. At a particular turn, a local best response depends on how the expected return varies across the available choices, given the history reached and a fixed continuation policy. The relevant quantity is the conditional action value Qkμ(h,a)=E[R∣h,a;μ]Q_k^\mu(h,a)=\mathbb{E}[R\mid h,a;\mu], where μ\mu denotes the continuation policy. This makes credit assignment a local comparison in which the current history and continuation policy are held fixed, and the current decision varies. Differences in return across complete trajectories can reflect the quality of the history, the current choice, and subsequent behavior. A local best response evaluates the current alternatives under the same conditions. This allows us to apply the idea of assessing individual contributions in cooperative credit assignment to multi-turn decisions and gives us a starting point for designing local evaluation and optimization methods.

  • Theorem 4.4 connects local optimization to overall sequential optimality. Once we decompose the problem, we must establish whether improvements to individual components can jointly yield a sequentially optimal policy. Under assumptions including independent parameterization, exact best responses, and fair coverage, Theorem 4.4 shows that parallel local updates computed from the same pre-update policy can reach a policy that is optimal at every history. The connection between the proof and classical policy improvement gives another way to understand the update rule. The equivalence links the two perspectives: the cooperative decision-making perspective identifies the structure of the local optimization problems, and policy improvement in the MDP explains why these local updates are consistent with the overall objective. Deriving the same result in MDP terms shows that the two analyses are compatible. The game formulation still plays a role in organizing the optimization problem and guiding the design of the method.

The value of the game formulation is that it decomposes the task into cooperative local optimization problems in a way that preserves the original objective and translates directly into sampling and update rules. Expressing the analysis in MDP terms retains both the decomposition and the algorithmic steps it yields. The appropriate criterion for judging the formulation is whether it leads to concrete insights and effective design choices. Equivalence to an MDP alone is insufficient grounds for treating it as a change in terminology.

1.2 Theorem 4.4 does not directly apply to the implemented algorithm

Thank you for pointing out the need to distinguish more clearly between the theory and its implementation. Theorem 4.4 motivates SEPO by providing a theoretical guarantee for finding a subgame-perfect equilibrium (SPE) through best-response updates. It does not directly analyze SEPO itself. Our argument proceeds in three steps. Section 4.1 models multi-turn LLM interactions as a multi-agent game. Section 4.2 presents a best-response method for solving the game within this framework. Section 4.3 then introduces an approximation of these updates for multi-turn LLMs. Thus, Theorem 4.4 establishes the guarantee for the best-response updates in Section 4.2, whereas SEPO approximates this update principle in the multi-turn LLM setting.

The connection between the theory and SEPO lies in the local evaluation objective, how candidates are compared, and where credit is assigned. Given a history hh and a fixed continuation policy μ\mu, a local best response compares the conditional values of candidate actions at hh, given by Qμ(h,a)=E[R∣h,a;μ]Q^\mu(h,a)=\mathbb{E}[R\mid h,a;\mu].

SEPO reflects this principle in three design choices:

  • Prefix sharing fixes the starting point for comparison. Candidates in the same group share the same history, so their returns can be compared to assess the current decision at that history.
  • Exploration within the target block and a common continuation policy allow candidates to be compared locally. SEPO samples different candidates for the target block and evaluates their continuations using the same parameter snapshot and decoding rule. Suffix validation uses the policy at the validation temperature as the continuation policy, so the comparison reflects the model’s behavior at evaluation time.
  • The loss mask directs the update to the target block being compared. Relative returns within the group are used to update the target block, so the training signal acts directly on the decision positions where the candidates differ.

The best-response perspective therefore guides how SEPO organizes rollouts, constructs the local credit signal, and applies the training objective. In this sense, it motivates SEPO and directly informs its design.

We agree that the main difference between Theorem 4.4 and SEPO lies in how they treat parameter sharing. To quantify how far a local update propagates under shared parameters, we conducted an additional experiment measuring how much an update to one turn affects other turns. In WebShop, we started from the same checkpoint of a previously trained model and ran four separate updates, each targeting only one of the four chunks. Holding the histories and response tokens fixed, we measured the KL divergence KL(πold∥πnew)\mathrm{KL}(\pi_{\mathrm{old}}\Vert\pi_{\mathrm{new}}) between the conditional token distributions before and after each update. To isolate the effect of each chunk, we reset the Adam optimizer’s momentum and disabled regularization terms, including the entropy loss, so that each update came solely from the selected chunk. For each update, we simulated the nonzero advantages that can arise with a group size of eight. We averaged the results over 64 repetitions, as shown in the table below.

Update ChunkTarget KL (×10−3\times 10^{-3})Other KL (×10−3\times 10^{-3})Other Target Ratio
13.3691.4090.418
23.1041.1860.382
32.1091.1230.532
42.1001.0680.508

For each of the four updates, the target chunk showed the largest mean KL divergence between the policies before and after the update. Mean KL divergence ranged from 2.10–3.37 × 10⁻³ for the target chunk and from 1.07–1.41 × 10⁻³ when averaged across the non-target chunks. Across the four updates, the divergence for the target chunk was 1.88–2.62 times the average for the non-target chunks. These results show that when an LLM shares parameters across turns, an update at a single chunk, history, or turn also affects decisions elsewhere, but the average effect is substantially smaller than the effect on the target chunk. The assumption of independent parameters therefore does not apply directly in this setting. One possible explanation for the smaller effects elsewhere is that the LLM’s representational capacity limits the extent to which updates at different decision points influence one another. Developing techniques to further reduce these effects of parameter sharing is an important direction for future research.

We have revised the wording in Section 4.2 of the main text to clarify the role of Theorem 4.4. We have also added the experimental results in Figure 5(a) and the accompanying analysis in Section 5.5.

Reviewer_EpndOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Sequential Equilibrium Policy Optimization (SEPO) for multi-turn LLM reinforcement learning. It models turns or turn chunks as agents in a fully cooperative sequential game. For each selected chunk, SEPO constructs rollout groups with shared prefixes, exploratory actions within the chunk, and exploitative continuations. Group-relative advantages are assigned only to the selected chunk. Experiments integrate SEPO with GRPO, GiGPO, and DAPO on ALFWorld, WebShop, and search-augmented QA, with additional vision-language experiments.

Critical strengths
  • The multi-agent reinterpretation of multi-turn LLM RL and mapping best-response updates to a concrete group rollout design (prefix sharing + in-chunk exploration + suffix exploitation) is elegant and conceptually fresh within critic-free, outcome-level methods.

  • The turn-chunking mechanism is a practical compromise between per-turn granularity and rollout cost, and the analysis connects it to a clear variance/coverage trade-off.

  • The method is well-motivated and described with intuitive diagrams; the rollout mechanics and how SEPO integrates with group-based objectives are clear.

  • The empirical results are strong across multiple settings with useful ablations.

Critical weaknesses
  • The equilibrium guarantee does not directly apply to the implemented algorithm. Theorem 4.4 assumes independently parameterized decisions, exact best responses, and fair coverage of every agent-history pair. SEPO instead uses a shared LLM, sampled alternatives, and clipped policy-gradient updates, so updating one chunk can change other decisions. Although the authors acknowledge parameter sharing, the suggestion that model capacity mitigates interference does not establish approximate best-response behavior or convergence.

  • The credit-assignment gains are not fully disentangled from the training-history distribution. In Figure 5, exploratory prefixes reduce success from 0.71 to 0.62 on WebShop and from 0.75 to 0.68 on ALFWorld, close to GRPO, despite retaining shared histories, chunk-specific updates, and exploitative suffixes. Section 4.3 explicitly acknowledges that validation-temperature prefixes concentrate comparisons on histories encountered under the evaluation policy. A plausible alternative explanation is therefore that some gains arise from this history-distribution alignment, rather than solely from more accurate credit assignment. The current ablations do not fully separate these explanations or their interaction. Proposition 4.5 also concerns return variance under a fixed rollout distribution, not advantage-estimation or gradient error. A matched-history comparison would better substantiate the proposed mechanism.

  • The practical advantage depends on the resource budget and base algorithm. The main comparisons match actor-update data rather than total rollout cost. Appendix D.5 partially addresses this, but larger-batch GRPO slightly exceeds GRPO+SEPO on ALFWorld success (0.77 versus 0.75) and WebShop score (0.83 versus 0.81), with equal WebShop success. DAPO+SEPO remains stronger, so the evidence is positive but not uniform. Given the reported increase from 179 to 394 seconds per iteration, performance against GPU-hours and generated tokens would clarify the practical trade-off.

Questions for authors
  1. Can the authors quantify how updating a selected chunk changes behavior at other chunks or histories under shared parameters? This would clarify the practical relevance of the best-response interpretation.

  2. Can the authors measure advantage-estimation error, action-ranking reliability, or gradient signal-to-noise ratio rather than return variance alone?

  3. Can the authors report performance against generated tokens, environment interactions, and GPU-hours, including rollouts discarded by dynamic sampling? Do the rollout-matched findings extend to larger backbones?

  4. Why does prefix temperature have such a large effect in Figure 5, even when shared histories and chunk-specific updates are retained? Can the authors isolate the benefit of grouping rollouts by shared history from the benefit of sampling evaluation-aligned histories? For tasks with multiple distinct prefixes, one possible ablation is to use the same sampled rollouts and update tokens, but compare advantages computed within each shared-prefix group against advantages computed across different prefixes of the same task, with matched group sizes and budgets.

8 comments

Thank you for your insightful reviews. In response to the feedback, we have made the following revisions:

  • Abstract and Introduction: We now explicitly state that SEPO requires additional rollouts.
  • Section 4.2: We clarify how Theorem 4.4 relates to SEPO.
  • Section 4.3: We explain how best-response updates motivate the design of SEPO.
  • Section 4.3: We add Theorem 4.6, which directly connects the variance decomposition in Proposition 4.5 to the mean squared error of the advantage estimator.
  • Section 5.5: We visualize how updating one chunk affects other chunks under parameter sharing and add an empirical analysis of advantage estimation error.
  • Appendix A.3: We provide the proof of Theorem 4.6.
  • Appendix D.1: We report how token counts, the number of turns used for policy updates, and training time per step vary with the number of agents.
  • Appendix D.4: We expand the comparisons with structured rollout baselines and report results across multiple random seeds.
  • Appendix D.5: We add ablation experiments to distinguish the contribution of history-distribution alignment from that of improved advantage estimation.
  • Appendix D.6: We add more comparisons in which all methods use the same number of rollouts.

We appreciate your feedback and hope that our response addresses your concerns.

Q1 Theorem 4.4 does not directly apply to the implemented algorithm

Thank you for pointing out the need to distinguish more clearly between the theory and its implementation. Theorem 4.4 motivates SEPO by providing a theoretical guarantee for finding a subgame-perfect equilibrium (SPE) through best-response updates. It does not directly analyze SEPO itself. Our argument proceeds in three steps. Section 4.1 models multi-turn LLM interactions as a multi-agent game. Section 4.2 presents a best-response method for solving the game within this framework. Section 4.3 then introduces an approximation of these updates for multi-turn LLMs. Thus, Theorem 4.4 establishes the guarantee for the best-response updates in Section 4.2, whereas SEPO approximates this update principle in the multi-turn LLM setting.

The connection between the theory and SEPO lies in the local evaluation objective, how candidates are compared, and where credit is assigned. Given a history hh and a fixed continuation policy μ\mu, a local best response compares the conditional values of candidate actions at hh, given by Qμ(h,a)=E[R∣h,a;μ]Q^\mu(h,a)=\mathbb{E}[R\mid h,a;\mu].

SEPO reflects this principle in three design choices:

  • Prefix sharing fixes the starting point for comparison. Candidates in the same group share the same history, so their returns can be compared to assess the current decision at that history.
  • Exploration within the target block and a common continuation policy allow candidates to be compared locally. SEPO samples different candidates for the target block and evaluates their continuations using the same parameter snapshot and decoding rule. Suffix validation uses the policy at the validation temperature as the continuation policy, so the comparison reflects the model’s behavior at evaluation time.
  • The loss mask directs the update to the target block being compared. Relative returns within the group are used to update the target block, so the training signal acts directly on the decision positions where the candidates differ.

The best-response perspective therefore guides how SEPO organizes rollouts, constructs the local credit signal, and applies the training objective. In this sense, it motivates SEPO and directly informs its design.

We agree that the main difference between Theorem 4.4 and SEPO lies in how they treat parameter sharing. To quantify how far a local update propagates under shared parameters, we conducted an additional experiment measuring how much an update to one turn affects other turns. In WebShop, we started from the same checkpoint of a previously trained model and ran four separate updates, each targeting only one of the four chunks. Holding the histories and response tokens fixed, we measured the KL divergence KL(πold∥πnew)\mathrm{KL}(\pi_{\mathrm{old}}\Vert\pi_{\mathrm{new}}) between the conditional token distributions before and after each update. To isolate the effect of each chunk, we reset the Adam optimizer’s momentum and disabled regularization terms, including the entropy loss, so that each update came solely from the selected chunk. For each update, we simulated the nonzero advantages that can arise with a group size of eight. We averaged the results over 64 repetitions, as shown in the table below.

Update ChunkTarget KL (×10−3\times 10^{-3})Other KL (×10−3\times 10^{-3})Other Target Ratio
13.3691.4090.418
23.1041.1860.382
32.1091.1230.532
42.1001.0680.508

For each of the four updates, the target chunk showed the largest mean KL divergence between the policies before and after the update. Mean KL divergence ranged from 2.10–3.37 × 10⁻³ for the target chunk and from 1.07–1.41 × 10⁻³ when averaged across the non-target chunks. Across the four updates, the divergence for the target chunk was 1.88–2.62 times the average for the non-target chunks. These results show that when an LLM shares parameters across turns, an update at a single chunk, history, or turn also affects decisions elsewhere, but the average effect is substantially smaller than the effect on the target chunk. The assumption of independent parameters therefore does not apply directly in this setting. One possible explanation for the smaller effects elsewhere is that the LLM’s representational capacity limits the extent to which updates at different decision points influence one another. Developing techniques to further reduce these effects of parameter sharing is an important direction for future research.

We have revised the wording in Section 4.2 of the main text to clarify the role of Theorem 4.4. We have also added the experimental results in Figure 5(a) and the accompanying analysis in Section 5.5.

Q2 Whether the gain comes from better advantage or the history-distribution alignment

We agree that history-distribution alignment contributes to performance, but more accurate advantage estimation remains the main source of the performance gains. To examine the contribution of better credit assignment more closely, we conducted additional analyses and ablation experiments.

First, we added Theorem 4.6 immediately after Proposition 4.5 to explain how the variance reduction established in Proposition 4.5 leads to more accurate advantage estimates. We also added an experiment in Section 5.5 to test this result by directly comparing the accuracy of SEPO’s advantage estimates with that of two alternatives.

Starting from a checkpoint obtained after 50 GRPO update steps, we sampled 64 validation histories in WebShop. For each history, we sampled eight candidate next chunks and estimated an advantage for each one. To construct a reference estimate, we sampled 16 continuation trajectories from each candidate chunk at the validation temperature and used MCTS to estimate its QQ-value, denoted by Q∗Q^*. For each history, we averaged Q∗Q^* over its eight candidate chunks to obtain V∗V^*. The resulting A∗=Q∗−V∗A^* = Q^* - V^* serves as an approximation to the ideal advantage for each candidate.

We then compared three ways of estimating the advantage of each candidate chunk:

  1. SEPO. We estimated QQ for each candidate using a single suffix sampled at the validation temperature. To obtain its advantage, we subtracted the mean QQ over candidates sharing the same history.
  2. Across-history. We used exactly the same QQ estimates as SEPO but computed the group mean used for VV across candidates from different histories.
  3. Exploration suffix. We estimated QQ using a suffix sampled at the exploration temperature, then subtracted the group mean to obtain the advantage.

We evaluated the three methods using the following metrics:

  1. Centered MSE measures the centered mean squared error between each method’s advantage estimates and the reference advantages A∗A^*.
  2. Sign Accuracy measures the fraction of candidate chunks for which the estimated advantage has the same sign as A∗A^*.
  3. Post-Update Success measures the WebShop success rate after one policy update using each method’s advantage estimates.

The table below reports the results.

MethodCentered MSESign AccuracyPost Update Success
SEPO1.1680.8750.352
across history1.8760.7420.336
exploration suffix1.2410.8750.344

As the table shows, SEPO’s advantage estimates are closest to the target advantages. When we kept the same set of histories but regrouped the candidates so that each group included candidates from different histories, the estimates deviated substantially more from the targets and matched their signs less often. This variant had the lowest post-update success rate. Replacing suffix validation with suffix exploration left overall sign accuracy unchanged, while both centered MSE and post-update success decreased slightly. These results provide empirical evidence for the contributions of prefix sharing and suffix validation to advantage estimation.

Our theoretical and empirical analyses show that SEPO produces more accurate advantage estimates. We conducted an additional experiment to show that SEPO’s performance gains stem primarily from more accurate advantage estimation and cannot be explained by history-distribution alignment alone. We evaluated three additional baselines on WebShop using Qwen2.5-1.5B-Instruct:

  • Validation GRPO samples every chunk in every rollout at the validation temperature.
  • Chunk Exploration GRPO randomly selects one chunk per rollout to sample at the exploration temperature and samples all remaining chunks at the validation temperature.
  • Only Prefix Validation is a SEPO variant with both prefix sharing and suffix validation disabled.

The table below reports the results.

MethodWebShop
Qwen2.5-1.5B-InstructScoreSucc.
validation GRPO0.10 0.040.03 0.00
chunk exploration GRPO0.23 0.080.04 0.01
only prefix validation0.80 0.010.64 0.00
GRPO+SEPO0.81 0.030.71 0.03

Comments on the paper

2 comments

Dear Reviewers,

Thank you very much for your valuable feedback on our work! As the author-reviewer discussion period is approaching its end, we would be happy to address any remaining questions or concerns you may have. We sincerely appreciate your time and consideration!

Best regards,

The Authors

AuthorsOpenReview ↗

Summary of rebuttal experiments and revisions for SEPO

Dear ACs,

Thank you for the time you have devoted to our submission and for overseeing the discussion. As the discussion period draws to a close, several reviewers have yet to follow up on our responses. We would like to highlight three revisions that bear directly on the questions they raised.

  1. Theory and parameter sharing (Sections 4.2–4.3 and 5.5). We clarified the assumptions behind Theorem 4.4 and explained how its idealized best-response updates motivate SEPO. We also measured how a local update propagates through the shared model. On WebShop, updating one chunk changed the policy at other chunks as well, but the mean KL divergence at the targeted chunk was 1.88–2.62 times the average at the other chunks.
  2. Evidence for more accurate credit assignment (Theorem 4.6, Figure 5, and Appendix D.5). We added a theoretical analysis of advantage-estimation error and tested its prediction on WebShop. Holding the sampled histories and candidate returns fixed, grouping candidates by shared history reduced centered MSE from 1.876 to 1.168 and improved sign agreement with the reference advantages from 74.2% to 87.5%. In a separate ablation, full SEPO achieved 71% success versus 64% with prefix validation alone. Together, these results support a contribution from more accurate local credit assignment beyond the benefit of aligning training and evaluation histories.
  3. More baselines and rollout costs (Appendices D.1, D.4, and D.6). We added comparisons with multiple structured rollout baselines in QA, extended performance comparisons under matched rollout counts to a larger model and additional baselines, and included multi-seed results using GiGPO as the baseline in QA.

We hope this summary helps you assess the revised paper. We would be happy to clarify any of these results while the discussion remains open.

Best regards,

Authors of Paper22752

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.