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

• URL: http://arxiv.org/abs/2601.04767v1
• Date: Thu, 08 Jan 2026 09:35:49 GMT
• Title: AT$^2$PO: Agentic Turn-based Policy Optimization via Tree Search
• Abstract summary: LLM agents have emerged as powerful systems for tackling multi-turn tasks by interleaving internal reasoning and external tool interactions.<n>We present AT$2$PO, a unified framework for multi-turn agentic RL that addresses three core challenges: limited exploration diversity, sparse credit assignment, and misaligned policy optimization.
• Score: 19.443576967819684
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: LLM agents have emerged as powerful systems for tackling multi-turn tasks by interleaving internal reasoning and external tool interactions. Agentic Reinforcement Learning has recently drawn significant research attention as a critical post-training paradigm to further refine these capabilities. In this paper, we present AT$^2$PO (Agentic Turn-based Policy Optimization via Tree Search), a unified framework for multi-turn agentic RL that addresses three core challenges: limited exploration diversity, sparse credit assignment, and misaligned policy optimization. AT$^2$PO introduces a turn-level tree structure that jointly enables Entropy-Guided Tree Expansion for strategic exploration and Turn-wise Credit Assignment for fine-grained reward propagation from sparse outcomes. Complementing this, we propose Agentic Turn-based Policy Optimization, a turn-level learning objective that aligns policy updates with the natural decision granularity of agentic interactions. ATPO is orthogonal to tree search and can be readily integrated into any multi-turn RL pipeline. Experiments across seven benchmarks demonstrate consistent improvements over the state-of-the-art baseline by up to 1.84 percentage points in average, with ablation studies validating the effectiveness of each component. Our code is available at https://github.com/zzfoutofspace/ATPO.

Related papers

• Process Reward Informed Tree Rollout for Effective Multi-Turn RL [58.392997761968566]
  In long-horizon agentic tasks, a uniform rollout strategy can waste budget on uninformative dead-end attempts.<n>We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL.<n>PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops paths to reduce wasted sampling.
  arXiv  Detail & Related papers  (2026-07-17T04:16:58Z)
• GD$^2$PO: Mitigating Multi-Reward Conflicts via Group-Dynamic reward-Decoupled Policy Optimization [54.596224644751565]
  Post-training reinforcement learning (RL) increasingly relies on multi-dimensional rewards to cultivate comprehensive capabilities.<n>To address this, existing methods such as Group reward-Decoupled Policy Optimization (GDPO) decompose the overall score into independent reward groups, then compute the RL loss separately within each group.<n>We propose Group-Dynamic reward-Decoupled Policy Optimization (GD$2$PO), which employs a conflict-aware filtering mechanism to mask out rollouts suffering from severe reward-wise disagreement.
  arXiv  Detail & Related papers  (2026-06-15T14:19:28Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• 3SPO: State-Score-Supervised Policy Optimization for LLM Agents [25.01222941080024]
  We propose textbfState-Score-Supervised Policy Optimization (3SPO), a novel RL algorithm that performs post-step policy optimization with dynamic state score supervision.<n> Experiments on ALFWorld and WebShop with Qwen2.5-1.5B/7B-Instruct show that 3SPO consistently outperforms GRPO by $+22.6%$ on ALFWorld and $+15.6$ points on WebShop.
  arXiv  Detail & Related papers  (2026-06-08T14:26:05Z)
• AIPO: Learning to Reason from Active Interaction [54.10819421625103]
  AIPO enables the policy model to proactively consult three functional collaborative agents when encountering reasoning bottlenecks.<n>AIPO consistently improves reasoning performance, generalizes robustly across different policy models and RLVR algorithms, and effectively expands the reasoning capability boundary of the policy model.
  arXiv  Detail & Related papers  (2026-05-08T19:06:55Z)
• Poly-EPO: Training Exploratory Reasoning Models [62.82992914206963]
  We present a framework for post-training language models (LMs) that explicitly encourages optimistic exploration and promotes a synergy between exploration and exploitation.<n>We propose Polychromic Exploratory Policy Optimization (Poly-EPO), which instantiates this framework with an objective that explicitly synergizes exploration and exploitation.
  arXiv  Detail & Related papers  (2026-04-19T22:54:19Z)
• MARS$^2$: Scaling Multi-Agent Tree Search via Reinforcement Learning for Code Generation [29.92851142870157]
  Reinforcement learning (RL) paradigms have demonstrated strong performance on reasoning-intensive tasks such as code generation.<n>We propose textbfMARS$2$ (Multi-Agent Reinforced Tree-Search Scaling), a unified RL framework in which multiple independently-optimized agents collaborate.
  arXiv  Detail & Related papers  (2026-04-16T02:52:24Z)
• RAPO: Expanding Exploration for LLM Agents via Retrieval-Augmented Policy Optimization [29.421185758698908]
  Agentic Reinforcement Learning (Agentic RL) has shown remarkable potential in large language model-based (LLM) agents.<n>We propose Retrieval-Augmented Policy Optimization (RAPO), a novel RL framework that introduces retrieval to explicitly expand exploration during training.<n>RAPO achieves an +5.0% average gain on fourteen datasets across three agentic reasoning tasks, while delivering 1.2x faster training efficiency.
  arXiv  Detail & Related papers  (2026-03-03T15:23:42Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• Empowering Multi-Turn Tool-Integrated Reasoning with Group Turn Policy Optimization [20.004150645050537]
  Group Turn Policy Optimization (GTPO) is a novel reinforcement learning algorithm designed for training Large Language Models (LLMs) on multi-turn Tool-Integrated Reasoning tasks.<n>GTPO introduces three key innovations: turn-level reward assignment that provides fine-grained feedback for individual turns, return-based advantage estimation, and self-supervised reward shaping.<n>Our comprehensive evaluation demonstrates that GTPO outperforms GRPO by 3.0% on average across diverse reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-11-18T19:01:16Z)
• Information Gain-based Policy Optimization: A Simple and Effective Approach for Multi-Turn LLM Agents [28.145430029174577]
  Large language model (LLM)-based agents are increasingly trained with reinforcement learning (RL) to enhance their ability to interact with external environments.<n>Existing approaches typically rely on outcome-based rewards that are only provided at the final answer.<n>In this paper, we propose Information Gain-based Policy Optimization (IGPO), a simple yet effective RL framework that provides dense and intrinsic supervision for multi-turn agent training.
  arXiv  Detail & Related papers  (2025-10-16T17:59:32Z)
• A Practitioner's Guide to Multi-turn Agentic Reinforcement Learning [12.179148605060298]
  We study what actually works and what doesn't for training large language models as agents via multi-turn reinforcement learning.<n>We break down the design space into three inter-related pillars -- environment, reward, and policy.<n>We distill these findings into a training recipe that guides co-design across the three pillars.
  arXiv  Detail & Related papers  (2025-10-01T17:23:04Z)
• Tree Search for LLM Agent Reinforcement Learning [23.7084695563981]
  Tree-based Group Relative Policy Optimization (Tree-GRPO) is a grouped agent RL method based on tree search.<n>By sharing common prefixes, the tree search sampling increases the number of rollouts achievable.<n>We demonstrate that the objective of intra-tree level group relative policy optimization is equivalent to that of step-level direct preference learning.
  arXiv  Detail & Related papers  (2025-09-25T14:37:09Z)
• Agentic Reinforcement Learning with Implicit Step Rewards [92.26560379363492]
  Large language models (LLMs) are increasingly developed as autonomous agents using reinforcement learning (agentic RL)<n>We introduce implicit step rewards for agentic RL (iStar), a general credit-assignment strategy that integrates seamlessly with standard RL algorithms.<n>We evaluate our method on three challenging agent benchmarks, including WebShop and VisualSokoban, as well as open-ended social interactions with unverifiable rewards in SOTOPIA.
  arXiv  Detail & Related papers  (2025-09-23T16:15:42Z)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)
• Agentic Reinforced Policy Optimization [66.96989268893932]
  Large-scale reinforcement learning with verifiable rewards (RLVR) has demonstrated its effectiveness in harnessing the potential of large language models (LLMs) for single-turn reasoning tasks.<n>Current RL algorithms inadequately balance the models' intrinsic long-horizon reasoning capabilities and their proficiency in multi-turn tool interactions.<n>We propose Agentic Reinforced Policy Optimization (ARPO), a novel agentic RL algorithm tailored for training multi-turn LLM-based agents.
  arXiv  Detail & Related papers  (2025-07-26T07:53:11Z)
• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  We propose a novel two-stage policy optimization framework that directly approximates the optimal advantage function.<n>$A$*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks.<n>It reduces training time by up to 2$times$ and peak memory usage by over 30% compared to PPO, GRPO, and REBEL.
  arXiv  Detail & Related papers  (2025-05-27T03:58:50Z)
• RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning [125.96848846966087]
  Training large language models (LLMs) as interactive agents presents unique challenges.<n>While reinforcement learning has enabled progress in static tasks, multi-turn agent RL training remains underexplored.<n>We propose StarPO, a general framework for trajectory-level agent RL, and introduce RAGEN, a modular system for training and evaluating LLM agents.
  arXiv  Detail & Related papers  (2025-04-24T17:57:08Z)
• Fleet of Agents: Coordinated Problem Solving with Large Language Models [10.167121757937062]
  Fleet of Agents (FoA) is a principled framework utilizing large language models as agents to navigate through dynamic tree searches.<n>FoA spawns a multitude of agents, each exploring the search space autonomously, followed by a selection phase.<n>FoA achieves the best cost-quality trade-off among all benchmarked methods and FoA + LMA3.2-11B surpasses the Llama3.2-90B model.
  arXiv  Detail & Related papers  (2024-05-07T09:36:23Z)
• HUGO -- Highlighting Unseen Grid Options: Combining Deep Reinforcement Learning with a Heuristic Target Topology Approach [1.0874597293913013]
  We present a search algorithm to find the Target Topologies (TTs) and upgrade our previously developed DRL agent CurriculumAgent (CAgent) to a novel topology agent. We achieve a 25% better median survival time with our TTs included.
  arXiv  Detail & Related papers  (2024-05-01T16:54:12Z)
• Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning [55.96599486604344]
  We introduce an approach aimed at enhancing the reasoning capabilities of Large Language Models (LLMs) through an iterative preference learning process. We use Monte Carlo Tree Search (MCTS) to iteratively collect preference data, utilizing its look-ahead ability to break down instance-level rewards into more granular step-level signals. The proposed algorithm employs Direct Preference Optimization (DPO) to update the LLM policy using this newly generated step-level preference data.
  arXiv  Detail & Related papers  (2024-05-01T11:10:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.