AT$^2$PO: Agentic Turn-based Policy Optimization via Tree Search

1 Introduction

• Agentic RL faces limited trajectory diversity, sparse end-of-trajectory rewards, and policy objectives misaligned with turn-based interaction.Flat token- or sequence-level importance weighting overlooks turn-wise sampling and can yield unstable gradients and inefficient learning.Source: §1 · pp. 1–2
• AT2PO expands trees from uncertain turns and propagates sparse outcome rewards backward to estimate per-turn values and advantages without auxiliary supervision.Its turn-level tree jointly supports strategic exploration and fine-grained credit assignment.Source: §1 · p. 2
• ATPO performs importance sampling and clipping at the turn level, aligning policy updates with multi-turn decisions and improving stability and alignment over token- or sequence-level baselines.It is orthogonal to tree search and can be integrated into any multi-turn agentic RL pipeline.Source: §1 · p. 2
• AT2PO gains up to 1.84 percentage points in average over the state-of-the-art baseline across seven benchmarks.Ablation studies validate the effectiveness of each component.Source: §1 · p. 2

2.1 Reinforcement Learning for LLMs

• RL methods including GRPO [Guo et al., 2025], DAPO [Yu et al., 2025b], and GSPO [Zheng et al., 2025] use group-based advantages or token- and sequence-level optimization, whereas ATPO updates at the turn level.The turn-level objective aligns policy updates with turn-wise feedback to improve training stability and quality.Source: §2.1 · pp. 2–3

2.2 Agentic Reinforcement Learning

• Tree-GRPO [Ji et al., 2025] organizes rollouts into trees, but does not explicitly prioritize expansion; AT2PO branches from high-entropy nodes.Related agentic RL work also explores trajectory data, optimization, memory, multimodality, and efficiency.Source: §2.2 · p. 3

3 Preliminaries

• The agentic interaction is modeled as an MDP, with each time step taking the agent from observed state st through action at to state st+1.Each action combines internal reasoning with either a tool invocation or a final answer.Source: §3 · p. 3
• The policy samples actions until the agent emits its final answer, producing a trajectory of state–action pairs with a trajectory-level outcome reward.The reward is based on the outcome of the interaction.Source: §3 · p. 3
• The method uses group-based optimization, which samples candidate responses in groups to implicitly estimate advantages without an additional critic network.This is contrasted with actor-critic approaches such as PPO [Schulman et al., 2017].Source: §3 · p. 4

4 Methods

• The method uses a turn-level tree for rollout, tree-based credit assignment for outcome rewards, and turn-based optimization for training.These components are presented as targeting exploration diversity, fine-grained supervision, and training stability and quality.Source: §4 · p. 4

4.1 Entropy Guided Tree Expansion

• Entropy estimates identify the top K uncertain nodes for branching, while a penalty discourages repeatedly expanding the same nodes.Each observation–action pair forms a tree node; the continuation from a fork is regenerated using context from the root, producing M + LK leaf nodes with token budget (M + LK/2)B per tree.Source: §4.1 · pp. 4–5

4.2 Turn-wise Credit Assignment

• Node values are estimated from descendants, propagating normalized final outcome rewards backward through the tree to provide intermediate turns with credit signals.Final rewards are assigned to leaves using standard GRPO normalization.Source: §4.2 · p. 5

4.3 Agentic Turn-based Policy Optimization

• ATPO applies turn-wise importance ratios and clipping to each decision turn, using its own learning signal; it is orthogonal to tree search and can plug into multi-turn RL.The design bridges token-level methods' high-variance ratios and sequence-level methods' coarser objective and reward alignment.Source: §4.3 · pp. 5–6

5.1 Experiment Settings

• The evaluation uses seven question-answering benchmarks, three model backbones, Exact Match, and RLVR and agentic-RL baselines.Experiments use a tool-integrated knowledge search setting; training runs without an additional SFT phase.Source: §5.1 · p. 6

5.2 Main Results of AT2PO

• AT2PO has larger gains on multi-hop benchmarks, where nearly all validation samples require at least two tool interactions, versus 43.5% of single-hop samples needing only one.The turn-count distribution is shown in Figure 4.Source: §5.2 · pp. 6–7, Figure 4 · p. 8
• AT2PO achieves the best results among most compared methods, with improvements of up to 1.84 percentage points in average over the state-of-the-art baseline across multi-hop and single-hop benchmarks.On certain single-hop QA datasets, DAPO slightly outperforms AT2PO while using up to three times the rollout budget. At an equal computational budget, AT2PO achieves the highest average performance across all settings.Source: §5.2 · p. 6
• AT2PO maintains the most stable entropy trajectory; GRPO collapses early, while AEPO avoids early collapse but gradually diverges during long-horizon training.Figure 3 compares training entropy and HotpotQA performance for Qwen3-4B.Source: §5.2 · p. 7, Figure 3 · p. 7

5.3.1 Ablation Study on AT2PO

• Adding ATPO improves the GRPO-with-random-tree baseline across multi-hop benchmarks; entropy-guided expansion adds gains, and turn-wise credit assignment yields the best overall performance.The ablation progressively adds modules on Qwen3-4B for multi-hop benchmarks.Source: §5.3.1 · pp. 7–8, Table 2 · p. 8

5.3.2 Scheme Analysis of Turn-wise Credit Assignment

• Directly using node value Vn as the advantage performs best across datasets; child-weighted aggregation leads, while difference-based formulations perform noticeably worse.Child-mean and leaf-mean aggregation remain competitive but slightly inferior.Source: §5.3.2 · p. 8, Table 3 · p. 8

• AT2PO combines entropy-guided exploration, turn-wise reward propagation, and turn-aligned policy updates; experiments across seven benchmarks show consistent improvements over strong baselines.The paper presents the framework as a promising approach for training LLM agents on complex multi-turn reasoning and tool-use tasks.Source: §6 · p. 8

• Tree-based expansion adds computational overhead compared with linear rollouts, particularly when computational resources are sufficient.The expansion process requires multiple sequential iterations.Source: §7 · p. 9
• The authors identify more efficient rollout strategies through enhanced parallelization as future work.Source: §7 · p. 9
• Evaluation in a broader range of agentic environments remains future work to further assess generalization and robustness.Source: §7 · p. 9

A Analysis of ATPO Objective

• ATPO uses turn-level importance ratios to suppress highly off-policy turns without discarding updates from more on-policy turns.This provides a turn-granular alternative to token-level GRPO and sequence-level GSPO objectives.Source: A Analysis of ATPO Objective · p. 12
• Hturn stabilizes around 0.66 on multi-hop and 0.62 on single-hop benchmarks, and gradually increases during training.The authors interpret the values as evidence of variation in turn-level updates and the upward trend as increasingly balanced updates.Source: A Analysis of ATPO Objective · p. 13, Figure 5 · p. 13

B.1 Reward Design

• The reward is 1 only when the final answer exactly matches ground truth and the output satisfies the required format.An incorrectly formatted response receives zero regardless of answer correctness.Source: §B.1 · p. 13

B.2 Prompt Template

• The prompt uses think tags for reasoning, search tags for tool requests, result tags for returned search content, and answer tags for the final response.The final answer is extracted from a boxed answer for exact-match scoring.Source: §B.2 · p. 13, Prompt Template · p. 14

B.3 Datasets

• The evaluation includes four multi-hop QA datasets and three single-hop QA datasets.The multi-hop set is HotpotQA, 2WikiMultiHopQA, Musique, and Bamboogle; the single-hop set is Natural Questions, TriviaQA, and PopQA.Source: §B.3 · p. 14

B.4 Baseline Settings

• Baselines include training-free ReAct, GRPO, DAPO, GSPO, AEPO, and Tree-GRPO.The section specifies baseline-specific configurations, including clipping and rollout settings.Source: §B.4 · pp. 14–15

B.5 Search Tool Settings

• The search tool uses Wikipedia as its corpus, an e5-base-v2 retriever, and a knowledge base of 21 million entries.At each turn, the search engine returns the top-k relevant data.Source: §B.5 · p. 15

B.6 Hardware and Artifacts

• Experiments use Qwen3-4B, Qwen3-8B, and Qwen2.5-7B on eight NVIDIA H20 GPUs with the VeRL framework.The models are described as backbone models for agentic RL training.Source: §B.6 · p. 15

C Analysis on Training Stability

• Replicated Tree-GRPO runs often collapsed early on Qwen3 models, which the authors primarily traced to retokenization drift.Detokenizing responses and retokenizing the dialogue can change token sequences, creating inconsistencies between sampled and training trajectories.Source: C Analysis on Training Stability · pp. 15–16
• Preserving generated token IDs from rollout through training eliminates retokenization-induced shifts and keeps policy entropy and gradient norm consistent without collapse.The text-in–token-out pipeline bypasses intermediate detokenization and retokenization; Figure 7 compares the two schemes.Source: Figure 7 · p. 15, C Analysis on Training Stability · p. 16
• Consistency between training and inference remains an unresolved stability challenge beyond the paper’s scope.The authors describe the token-preservation fix as resolving one key source of instability, not all such challenges.Source: C Analysis on Training Stability · p. 16

D.1 Ablation Study on AT2PO

• Adding ATPO to GRPO with random tree search improves all multi-hop benchmarks; adding entropy-guided expansion and then turn-wise credit assignment yields further gains, with full AT2PO performing best.The study adds modules progressively on Qwen3-4B under a fixed backbone and consistent task suite.Source: §D.1 · p. 16

D.2 Scheme Analysis of Turn-wise Credit Assignment

• The comparison varies node-value aggregation across child-weighted propagation, child-mean, and leaf-mean strategies, and tests node value against TD, global, and combined advantage signals.The main experiments use A_n = V_n; the combined signal is described as used in prior work (Hou et al., 2025).Source: §D.2 · pp. 16–17
• Directly using node value as the advantage performs consistently strongly across datasets; child-weighted aggregation is best, while difference-based alternatives perform noticeably worse.Child-mean and leaf-mean aggregation remain competitive but slightly inferior; the combined signal performs worst among the variants.Source: §D.2 · p. 17

E Case Study

• Case studies present one AT2PO-generated example from each of seven benchmarks; multi-hop QA typically shows more multi-turn tool calls and interactions than single-hop QA.Colored boxes distinguish agent states and actions during the reasoning process.Source: E Case Study · p. 17