Paper deep dive
PTGPO: Prefix Tree Group Policy Optimization
Ruolin Chen, Yang Li, Jihang Wang, Zhuoya Zhao, Yuchen Liu, Jiaming Xu, Qian Zhang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Training language agents on long-horizon interactive tasks is challenging because sparse terminal rewards provide weak credit signals for intermediate actions. Existing group-based methods either assign a shared trajectory-level advantage or estimate step-level advantages from state groups, which may conflate the current action with subsequent decisions. We propose Prefix Tree Group Policy Optimization (PTGPO), a critic-free method that constructs prefix trees over trajectory suffixes within anchor-state groups. PTGPO assigns each tree edge a credit given by the difference between its child and parent empirical mean returns, capturing the conditional return change revealed by each additional action. These prefix-tree credits provide fine-grained learning signals without requiring a critic or additional rollouts. Experiments on interactive benchmarks ALFWorld, WebShop and Sokoban show that PTGPO consistently improves over RL baselines, demonstrating its effectiveness.
Tags
Links
- Source: https://arxiv.org/abs/2610.14737v1
- Canonical: https://arxiv.org/abs/2610.14737v1
Trouble viewing inline? Open PDF directly →
Full Text
25,928 characters extracted from source content.
Expand or collapse full text
PTGPO: Prefix Tree Group Policy Optimization Ruolin Chen Yang Li Jihang Wang Zhuoya Zhao Yuchen Liu Jiaming Xu Qian Zhang †thanks: $⋆$Equal contribution. $†$Corresponding author (xujiaming1@xiaomi.com, q.zhang@ia.ac.cn). Abstract Training language agents on long-horizon interactive tasks is challenging because sparse terminal rewards provide weak credit signals for intermediate actions. Existing group-based methods either assign a shared trajectory-level advantage or estimate step-level advantages from state groups, which may conflate the current action with subsequent decisions. We propose Prefix Tree Group Policy Optimization (PTGPO), a critic-free method that constructs prefix trees over trajectory suffixes within anchor-state groups. PTGPO assigns each tree edge a credit given by the difference between its child and parent empirical mean returns, capturing the conditional return change revealed by each additional action. These prefix-tree credits provide fine-grained learning signals without requiring a critic or additional rollouts. Experiments on interactive benchmarks ALFWorld, WebShop and Sokoban show that PTGPO consistently improves over RL baselines, demonstrating its effectiveness. Index Terms: LLM agent, reinforcement learning, credit assignment, policy optimization †address: 1 Brain-inspired Cognitive AI Lab, Institute of Automation, Chinese Academy of Sciences 2 School of Artificial Intelligence, University of Chinese Academy of Sciences 3 HyperAI Team, Xiaomi Corporation 4 University of Ottawa 1 Introduction Recent advances [8, 20] in large language models (LLMs) have extended their capabilities beyond static text generation toward interactive reasoning and decision-making. LLM-powered agents can perceive, reason, and act across diverse environments, including embodied tasks [14, 16], web navigation [22, 5], and interactive games [10, 19]. Unlike single-turn generation, these applications require long-horizon planning and coherent sequences of actions, where intermediate decisions shape subsequent observations and task completion. Reinforcement learning (RL) provides a natural post-training framework for improving such agents through interaction and task-level feedback [9, 7, 17]. A central challenge is translating this feedback into effective learning signals for the individual decisions made throughout an episode. Group-based reinforcement learning methods such as GRPO [12] have become an effective critic-free paradigm for LLM training, where multiple responses can be sampled for the same prompt and compared using verifiable outcome rewards. These methods have demonstrated strong performance on single-turn tasks, particularly mathematical reasoning. However, extending these methods to long-horizon multi-turn agentic tasks remains challenging [17]. In such environments, an episode may involve many interaction steps, while rewards are often sparse, so assigning a single trajectory-level advantage to every action obscures which decisions actually caused success or failure [18, 15]. Recent methods such as GiGPO [4] mitigate this issue by grouping steps with identical environment states. However, computing step-level advantages from trajectory outcomes within such groups may conflate the grouped action with later decisions, creating a credit-assignment mismatch. As illustrated in Fig. 1, even when two samples share the same current state and take the same action, their terminal rewards may differ, or even have opposite signs, because their subsequent actions diverge. This difference should not be attributed to the current action, but rather to the subsequent action that actually determines the outcome. However, these decisive actions often occur after the trajectories have entered sparse or non-identical states, where reliable state-level groups can no longer be formed. The unresolved return variation should therefore be carried forward along the shared action prefix and progressively decomposed as subsequent actions are revealed. When the trajectories branch into groups with different conditional mean returns, credit can be assigned to the newly revealed branching action. Figure 1: Comparison of state-group and prefix-tree credit assignment under the undiscounted setting (γ=1γ=1). Identical actions may receive conflicting advantages when their subsequent actions lead to different returns. PTGPO recursively groups trajectory suffixes by action prefix, where node values denote empirical mean returns and edge labels denote child-parent mean differences. Colors indicate identical actions. Figure 2: Illustration of PTGPO advantage decomposition under the undiscounted setting (γ=1)(γ=1). Episode-level advantages are shared by all actions in the same trajectory, while prefix-tree credits redistribute return residuals to branching decisions that change the conditional mean return. “End” marks the termination of a prefix decomposition. In this work, we propose Prefix Tree Group Policy Optimization (PTGPO), a critic-free method for fine-grained credit assignment in long-horizon tasks. PTGPO constructs a prefix tree for each anchor-state group, recursively grouping trajectory suffixes by shared action prefixes. For each parent-child edge in the tree, PTGPO assigns credit equal to the difference between the child and parent empirical mean returns. This quantity measures the conditional return increment introduced by the newly revealed action. Across three challenging agentic benchmarks ALFWorld, WebShop and Sokoban, PTGPO consistently outperforms existing prompting and RL baselines. Our analysis further shows that the proposed prefix-tree credit assignment provides effective step-level learning signals, making PTGPO a practical solution for long-horizon agentic tasks with sparse rewards. 2 Method For each sampled trajectory i, let its length be TiT_i. For each sampled step (i,t)(i,t), we define the discounted return as R^t(i)=∑u=tTiγu−tru(i), R^(i)_t= _u=t^T_iγ^u-tr^(i)_u, (1) where γ∈[0,1]γ∈[0,1] is the discount factor. In sparse terminal-reward tasks, intermediate rewards are zero. Following GiGPO, we use the same anchor-state matching strategy to construct step-level root groups over sampled rollouts. Let s~ s denote an anchor state, and let (s~)=(i,t)∣st(i)=s~G( s)=\(i,t) s_t^(i)= s\ (2) be the set of all step occurrences that share this anchor state. For each group, PTGPO builds a prefix tree. Let da_d be a sequence of d actions. The corresponding node is the set p(s~,d)=(i,t)∈(s~)|(at(i),…,at+d−1(i))=d.p( s,a_d)= \(i,t) ( s)\; |\;(a_t^(i),…,a_t+d-1^(i))=a_d \. (3) Samples with the same action sequence of length d are included. The root is p(s~,∅)=(s~)p( s, )=G( s). If d+1a_d+1 extends da_d by one action ada_d, then the node p(s~,d+1)p( s,a_d+1) is a child of p(s~,d)p( s,a_d), and we have p(s~,d+1)⊆p(s~,d).p( s,a_d+1) p( s,a_d). (4) Thus, starting from the root, PTGPO recursively splits each node according to the next action, merging sampled steps with the same future action prefix into the same branch. For any nonempty node, its empirical mean return is μ^(p(s~,d))=1|p(s~,d)|∑(i,t)∈p(s~,d)R^t(i). μ (p( s,a_d) )= 1|p( s,a_d)| _(i,t)∈ p( s,a_d) R_t^(i). (5) For a sampled step (i,t)(i,t) with st(i)=s~s_t^(i)= s, consider its prefix-tree path, where d=(at(i),…,at+d−1(i))a_d=(a_t^(i),…,a_t+d-1^(i)) and 0=∅a_0= . The unnormalized state-group step advantage [4] then admits the following decomposition along a path expanded to depth D: R^t(i)−μ^(p(s~,∅)) R_t^(i)- μ (p( s, ) ) =∑d=0D−1Δ(p(s~,d),p(s~,d+1)) = _d=0^D-1 (p( s,a_d),p( s,a_d+1) ) (6) +[R^t(i)−μ^(p(s~,D))], + [ R_t^(i)- μ (p( s,a_D) ) ], where Δ(p(s~,d),p(s~,d+1))=μ^(p(s~,d+1))−μ^(p(s~,d)) (p( s,a_d),p( s,a_d+1) )= μ (p( s,a_d+1) )- μ (p( s,a_d) ) (7) is the credit assigned to the newly added action at+d(i)a_t+d^(i) for each (i,t)∈p(s~,d+1)(i,t)∈ p( s,a_d+1), reflecting the change in mean return from parent to child, while differences due to later actions remain within p(s~,d+1)p( s,a_d+1) for further decomposition. A node can be expanded only if |p(s~,d)|≥τexpand|p( s,a_d)|≥ _expand. Table 1: Performance on ALFWorld and WebShop. We train each RL method with 3 random seeds and report the mean and standard deviation. The best performances are highlighted in bold. Type Method ALFWorld WebShop Pick Look Clean Heat Cool Pick2 All Score Succ. Closed-Source Model Prompting GPT-4o 75.3 60.8 31.2 56.7 21.6 49.8 48.0 31.8 23.7 Prompting Gemini-2.5-Pro 92.8 63.3 62.1 69.0 26.6 58.7 60.3 42.5 35.9 Qwen2.5-1.5B-Instruct Prompting Direct Prompt 5.9 5.5 3.3 9.7 4.2 0.0 4.1 23.1 5.2 Prompting ReAct 17.4 20.5 15.7 6.2 7.7 2.0 12.8 40.1 11.3 Prompting Reflexion 35.3 22.2 21.7 13.6 19.4 3.7 21.8 55.8 21.9 RL Training PPO 64.8±3.5 40.5±6.9 57.1±4.9 60.6±6.6 46.4±4.0 47.4±1.9 54.4±3.1 73.8±3.0 51.5±2.9 RL Training RLOO 88.3±3.0 52.8±8.6 71.0±5.9 62.8±8.7 66.4±5.5 56.9±4.7 69.7±2.5 73.9±5.6 52.1±6.7 RL Training GRPO 85.3±1.5 53.7±8.0 84.5±6.8 78.2±7.9 59.7±5.0 53.5±5.6 72.8±3.6 75.8±3.5 56.8±3.8 RL Training GiGPO 93.6±6.7 82.1±8.0 90.3±6.9 89.7±5.5 77.5±4.0 73.3±11.4 84.8±5.5 81.6±4.6 67.5±4.8 RL Training PTGPO (Ours) 96.6±3.6 87.6±6.9 97.4±2.3 100.0±0.0 86.0±6.6 89.3±8.2 92.6±2.5 87.1±0.4 74.3±1.5 Qwen2.5-7B-Instruct Prompting Direct Prompt 33.4 21.6 19.3 6.9 2.8 3.2 14.8 26.4 7.8 Prompting ReAct 48.5 35.4 34.3 13.2 18.2 17.6 31.2 46.2 19.5 Prompting Reflexion 62.0 41.6 44.9 30.9 36.3 23.8 42.7 58.1 28.8 RL Training PPO 92.3±4.0 64.0±8.4 92.5±2.4 89.5±7.0 80.3±2.0 68.8±8.3 80.4±2.7 81.4±3.1 68.7±5.1 RL Training RLOO 87.6±4.3 78.2±8.3 87.3±5.8 81.3±7.6 71.9±5.2 48.9±8.4 75.5±4.6 80.3±3.2 65.7±4.0 RL Training GRPO 90.8±5.1 66.1±6.7 89.3±5.4 74.7±6.9 72.5±5.4 64.7±7.3 77.6±5.2 79.3±2.8 66.1±3.7 RL Training GiGPO 95.2±5.9 86.7±4.3 96.4±3.4 93.7±5.9 84.1±5.9 92.8±2.4 91.9±1.6 82.5±1.3 70.5±1.1 RL Training PTGPO (Ours) 100.0±0.0 96.0±3.5 97.3±2.4 97.6±4.1 86.9±5.0 97.2±2.4 96.0±1.1 90.7±2.0 82.0±1.6 Table 2: Performance on Sokoban. We train each RL method with 3 random seeds and report the mean and standard deviation. The best performances are highlighted in bold. Type Method Sokoban [6×6] Prompting Direct Prompt 11.7 RL Training GRPO 73.9±1.6 RL Training GiGPO 77.6±2.5 RL Training PTGPO 85.2±1.6 PTGPO normalizes each credit by the standard deviation of returns in its root group: σ^(p(s~,∅))=Std(R^t(i)∣(i,t)∈p(s~,∅)). σ (p( s, ) )=Std ( \ R_t^(i) (i,t)∈ p( s, ) \ ). (8) For action ak(i)a_k^(i), PTGPO sums the normalized edge credits from starting steps t=0,…,kt=0,…,k: AkPT,(i)=∑t=0kΔ(p(st(i),k−t),p(st(i),k−t+1))σ^(p(st(i),∅)).A_k^PT,(i)= _t=0^k (p (s_t^(i),a_k-t ),p (s_t^(i),a_k-t+1 ) ) σ (p(s_t^(i), ) ). (9) Each edge credit is normalized by the standard deviation of the root group associated with its starting step t, with each term capturing a distinct conditional-return innovation under a different anchor-conditioned prefix decomposition. In practice, the accumulated magnitude remains well controlled because the maximum expansion depth of each prefix tree is limited and valid root groups become increasingly sparse along the trajectory. Finally, PTGPO is combined with the base episode advantage: Aepisode,(i)=R^Ti(i)−μRσR,A^episode,(i)= R^(i)_T_i- _R _R, (10) where μR _R and σR _R are the mean and standard deviation of terminal rewards across the group. Ak(i)=Aepisode,(i)+AkPT,(i).A^(i)_k=A^episode,(i)+A^PT,(i)_k. (11) Here Aepisode,(i)A^episode,(i) is sequence-level and shared by all actions in the response, while AkPT,(i)A^PT,(i)_k provides step-level credit by decomposing the suffix-dependent return along the prefix tree. Fig. 2 gives an intuitive example of the resulting advantage decomposition. PTGPO shifts credit from uniformly rewarding or penalizing every step to emphasizing the key decision points that separate successful and failed trajectories. Then the clipped policy optimization objective of PTGPO is: (θ)=[min( (θ)=E [ ( ρk(i)(θ)Ak(i), ρ^(i)_k(θ)A^(i)_k, (12) clip(ρ(i)k(θ),1−ϵ,1+ϵ)A(i)k)]. (ρ^(i)_k(θ),1-ε,1+ε )A^(i)_k ) ]. where ρk(i)(θ)=πθ(ak(i)∣sk(i))πθold(ak(i)∣sk(i)).ρ^(i)_k(θ)= _θ(a^(i)_k s^(i)_k) _ _old(a^(i)_k s^(i)_k). (13) 3 Experiments 3.1 Setup Benchmarks. We train agents on three challenging multi-turn benchmarks: ALFWorld [14], WebShop [22] and Sokoban [10]. ALFWorld is a text-based embodied environment where agents complete household tasks through multi-step interaction. WebShop is a web-based interactive benchmark where LLM agents navigate a simulated shopping website to purchase items matching user instructions. Sokoban is a visual grid-based game benchmark where agents move boxes onto target locations through multi-step actions. Baselines. We compare PTGPO against baselines across paradigms: (1) Closed-source models: GPT-4o [6] and Gemini-2.5-Pro [3]. (2) Prompting methods: ReAct [23] and Reflexion [13]. (3) RL training methods: PPO [11], RLOO [1], GRPO [12] and GiGPO [4], covering both critic-based and group-based policy optimization methods. For VLMs, we focus on comparisons with group-based RL methods. Implementation. We use Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct [21] as the base models for ALFWorld and WebShop, and Qwen2.5-VL-3B-Instruct [2] for Sokoban. For fair comparison, all RL methods use identical training configurations. We train each method for 160 training iterations with a discount factor of γ=0.95γ=0.95 and a learning rate of 1×10−61× 10^-6. In each iteration, we sample 16 training instances and generate a group of 8 trajectories for each instance, resulting in 128 rollouts per iteration. Each episode allows up to 50 environment steps in ALFWorld and up to 15 environment steps in WebShop and Sokoban. We use 8 NVIDIA H20 96GB GPUs for training. Table 3: Ablation study of PTGPO on ALFWorld and WebShop using Qwen2.5-1.5B-Instruct, and on Sokoban using Qwen2.5-VL-3B-Instruct. The best performances are highlighted in bold. Variant ALFWorld WebShop Sokoban PTGPO 92.6±2.5 74.3±1.5 85.2±1.6 Advantage Composition w/o Episode-level Adv 92.4±1.1 71.8±3.9 81.5±4.4 w/o Prefix-tree Adv 72.8±3.6 56.8±3.8 73.9±1.6 Aggregation Strategy Mean 84.3±1.6 71.4±2.1 82.3±2.3 Nearest Anchor 91.5±2.3 73.2±1.6 84.1±1.0 Prefix Depth d=2d=2 87.6±4.4 70.0±0.9 78.6±5.1 d=4d=4 88.3±2.2 72.9±1.0 83.3±6.6 d=8d=8 92.1±1.2 74.5±1.9 83.6±1.6 Expansion Threshold τexpand=4 _expand=4 90.0±3.6 72.0±3.7 83.6±3.4 τexpand=6 _expand=6 85.5±1.1 71.1±2.2 81.5±1.2 τexpand=8 _expand=8 84.3±2.9 73.3±3.8 81.8±1.7 3.2 Experiment Results 3.2.1 Main Results Table 1 shows that PTGPO consistently outperforms prompting methods and RL baselines across multi-turn agentic tasks. On Qwen2.5-1.5B, PTGPO achieves 92.6 on ALFWorld and 74.3% success on WebShop, improving over GRPO by 19.8 and 17.5 points, respectively. With Qwen2.5-7B, PTGPO further improves to 96.0 on ALFWorld and 82.0% success rate on WebShop. On the visual Sokoban benchmark, PTGPO reaches 85.2 as shown in Table 2, outperforming GRPO and GiGPO, demonstrating its effectiveness for both LLM and VLM agents. To further examine the training dynamics, Figure 3(a) reports the episode success rate on ALFWorld as a representative example. PTGPO reaches around 0.8 success rate after about 75 steps, while GiGPO reaches a similar level after about 105 steps and GRPO fails to do so within 160 steps, showing better training efficiency. 3.2.2 Ablation Studies Table 3 evaluates the main components and design choices of PTGPO. Unless otherwise specified, the full method uses unrestricted prefix-tree expansion with τexpand=2 _expand=2 and sums all valid prefix credits associated with each action. Removing the prefix-tree advantage reduces performance by 19.8, 17.5, and 11.3 points on ALFWorld, WebShop, and Sokoban, respectively, confirming that fine-grained prefix credit is the primary source of improvement. In comparison, removing the episode-level advantage has little effect on ALFWorld but causes larger drops on WebShop and Sokoban, indicating that the trajectory-level signal provides complementary global supervision. We next compare different strategies for combining the credits assigned to the same action by multiple anchor states. Mean aggregation consistently underperforms the default summation strategy, with a particularly large drop on ALFWorld. Using only the nearest valid anchor performs substantially better than mean aggregation, but remains below credit summation on all three benchmarks. These results suggest that different anchor states provide complementary credit signals: restricting learning to the nearest anchor discards useful longer-range evidence, whereas averaging can dilute informative signals when only a small number of valid anchors are available. Summation preserves and accumulates these signals. Moreover, because an action can only receive credit from trees that reach it, the number of accumulated terms is bounded by the tree depth and is further limited by sparse state matching and the expansion threshold. Increasing the maximum prefix depth generally improves performance. Expanding the depth from 22 to 88 improves ALFWorld from 87.6 to 92.1 and WebShop from 70.0 to 74.5, while Sokoban improves from 78.6 to 83.6. Depth 88 is already close to unrestricted expansion, consistent with Fig. 3(b), which shows that most trees terminate within eight levels. Finally, increasing τexpand _expand generally degrades performance. Although a larger threshold yields more reliable node-level return estimates, it prevents many sparsely supported branches from being expanded and consequently removes useful fine-grained credits. Overall, τexpand=2 _expand=2 provides the best balance between estimation reliability and credit coverage. Figure 3: (a) Episode Success Rate during Training on ALFWorld. (b) Distribution of maximum expanded tree depth at epoch 160 on ALFWorld. 3.2.3 Computational Overhead We measure the method-specific advantage computation cost on ALFWorld with Qwen2.5-1.5B-Instruct at epoch 160. PTGPO shares the same rollout, probability computation, and policy update pipeline as other group-based methods, with a common cost of about 210.968s per iteration, and introduces additional computation only for prefix-tree construction and prefix-wise advantage estimation. The method-specific advantage computation costs are 0.192s for GRPO, 0.559s for GiGPO, and 1.713s for PTGPO. Despite the additional overhead introduced by prefix-tree construction, PTGPO’s extra computation accounts for only 0.812% of the common training cost and has a negligible impact on overall training efficiency. 4 Conclusion In this paper, we propose PTGPO, a novel reinforcement learning method for long-horizon interactive agents with sparse rewards. PTGPO mitigates the credit assignment problem by decomposing trajectory returns through prefix-wise conditional mean increments, assigning step-level credit to actions according to how future action prefixes change expected returns. Experiments on interactive benchmarks show that PTGPO consistently improves over existing RL baselines. Further analyses demonstrate the importance of prefix-tree advantages and show that PTGPO introduces only minor computational overhead without requiring extra rollouts or critic models. References [1] A. Ahmadian, C. Cremer, M. Gallé, M. Fadaee, J. Kreutzer, O. Pietquin, A. Üstün, and S. Hooker (2024) Back to basics: revisiting reinforce-style optimization for learning from human feedback in llms. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 12248–12267. Cited by: §3.1. [2] S. Bai, K. Chen, X. Liu, J. Wang, W. Ge, S. Song, K. Dang, P. Wang, S. Wang, J. Tang, et al. (2025) Qwen2.5-vl technical report. arXiv preprint arXiv:2502.13923. External Links: Link Cited by: §3.1. [3] G. Comanici, E. Bieber, M. Schaekermann, I. Pasupat, N. Sachdeva, I. Dhillon, M. Blistein, O. Ram, D. Zhang, E. Rosen, et al. (2025) Gemini 2.5: pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261. Cited by: §3.1. [4] L. Feng, Z. Xue, T. Liu, and B. An (2026) Group-in-group policy optimization for llm agent training. Advances in Neural Information Processing Systems 38, p. 46375–46408. Cited by: §1, §2, §3.1. [5] B. Gou, D. R. Wang, B. Zheng, Y. Xie, C. Chang, Y. Shu, H. Sun, and Y. Su (2025) Navigating the digital world as humans do: universal visual grounding for gui agents. In International Conference on Learning Representations, Vol. 2025, p. 30851–30883. Cited by: §1. [6] A. Hurst, A. Lerer, A. P. Goucher, A. Perelman, A. Ramesh, A. Clark, A. Ostrow, A. Welihinda, A. Hayes, A. Radford, et al. (2024) Gpt-4o system card. arXiv preprint arXiv:2410.21276. Cited by: §3.1. [7] B. Jin, H. Zeng, Z. Yue, J. Yoon, S. Arik, D. Wang, H. Zamani, and J. Han (2025) Search-r1: training llms to reason and leverage search engines with reinforcement learning. arXiv preprint arXiv:2503.09516. Cited by: §1. [8] A. Liu, A. Mei, B. Lin, B. Xue, B. Wang, B. Xu, B. Wu, B. Zhang, C. Lin, C. Dong, et al. (2025) Deepseek-v3. 2: pushing the frontier of open large language models. arXiv preprint arXiv:2512.02556. Cited by: §1. [9] Z. Qi, X. Liu, I. L. Iong, H. Lai, X. Sun, J. Sun, X. Yang, Y. Yang, S. Yao, W. Xu, et al. (2025) Webrl: training llm web agents via self-evolving online curriculum reinforcement learning. In International Conference on Learning Representations, Vol. 2025, p. 79791–79821. Cited by: §1. [10] M. B. Schrader (2018) Gym-sokoban. GitHub. Note: https://github.com/mpSchrader/gym-sokoban Cited by: §1, §3.1. [11] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §3.1. [12] Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. Li, Y. Wu, et al. (2024) Deepseekmath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: §1, §3.1. [13] N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao (2023) Reflexion: language agents with verbal reinforcement learning. Advances in neural information processing systems 36, p. 8634–8652. Cited by: §3.1. [14] M. Shridhar, X. Yuan, M. Côté, Y. Bisk, A. Trischler, and M. Hausknecht (2020) Alfworld: aligning text and embodied environments for interactive learning. arXiv preprint arXiv:2010.03768. Cited by: §1, §3.1. [15] H. Tan, X. Yang, H. Chen, J. Shao, Y. Wen, Y. Shen, W. Luo, X. Du, L. Guo, and Y. Li (2026) Hindsight credit assignment for long-horizon llm agents. arXiv preprint arXiv:2603.08754. Cited by: §1. [16] G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar (2023) Voyager: an open-ended embodied agent with large language models. arXiv preprint arXiv:2305.16291. Cited by: §1. [17] Z. Wang, K. Wang, Q. Wang, P. Zhang, L. Li, Z. Yang, X. Jin, K. Yu, M. N. Nguyen, L. Liu, et al. (2025) Ragen: understanding self-evolution in llm agents via multi-turn reinforcement learning. arXiv preprint arXiv:2504.20073. Cited by: §1, §1. [18] Z. Wang, Y. Yan, H. Li, T. Pan, D. Li, R. Zhang, W. Lu, J. Xiao, Y. Zhuang, and Y. Shen (2026) Milestone-guided policy learning for long-horizon language agents. arXiv preprint arXiv:2605.06078. Cited by: §1. [19] Z. Xu, C. Yu, F. Fang, Y. Wang, and Y. Wu (2023) Language agents with reinforcement learning for strategic play in the werewolf game. arXiv preprint arXiv:2310.18940. Cited by: §1. [20] A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. (2025) Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §1. [21] A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, et al. (2024) Qwen2.5 technical report. arXiv preprint arXiv:2412.15115. External Links: Link Cited by: §3.1. [22] S. Yao, H. Chen, J. Yang, and K. Narasimhan (2022) Webshop: towards scalable real-world web interaction with grounded language agents. Advances in Neural Information Processing Systems 35, p. 20744–20757. Cited by: §1, §3.1. [23] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao (2022) React: synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629. Cited by: §3.1.