Skip to content

Cross-Rollout Bellman Closure for Long-Horizon Agentic Reinforcement Learning

Sep 2026 · arXiv.org · Vol abs/2609.35082 · 0 citations
Computer Science

TL;DR

Cross-Rollout Bellman Closure (CRBC) is introduced, which merges each rollout group into a finite empirical process with absorbing success and failure boundaries and evaluates its behavior-policy Bellman fixed point with one linear solve.

Abstract

Group-based reinforcement learning such as GRPO trains LLM agents by comparing rollouts sampled for each task, without a learned critic. In long-horizon settings, these rollouts revisit shared anchor states, offering cross-rollout evidence for step-level credit. Ideally, step-level credit should incorporate evidence beyond the realized suffixes observed at an anchor while aggregating alternative continuations according to their empirical frequencies. Visit-local averaging pools realized suffix returns at shared anchors and respects observed frequencies, but does not recursively propagate evidence across rollouts, whereas shortest-path estimators have global reach but allow a rarely observed route to dominate an anchor's value. We introduce Cross-Rollout Bellman Closure (CRBC), which merges each rollout group into a finite empirical process with absorbing success and failure boundaries and evaluates its behavior-policy Bellman fixed point with one linear solve. This fixed point uses the same empirical action and transition frequencies to propagate evidence through shared anchors and aggregate alternative continuations. Backing up the resulting state values through observed transitions yields action values, whose gain over the corresponding state value provides step-level credit. A corresponding finite-depth family recovers visit-local return averaging at zero depth and converges to the exact closure as depth increases. The normalized closure credit is combined with the trajectory-level group advantage for policy optimization, without additional environment rollouts. Across ALFWorld, WebShop, and Sokoban benchmarks with multiple model scales, CRBC consistently improves final performance and learning efficiency. For example, CRBC outperforms the strongest evaluated baseline by 5.59 percentage points on ALFWorld with Qwen2.5-1.5B-Instruct.

View source

Similar papers

Preprint Nov 2026

Hindsight Credit Assignment over Trees for Agentic RL

Experimental results demonstrate consistent gains in task performance and rollout efficiency across model scales, highlighting structured hindsight credit assignment as an effective approach to long-horizon agent learning.

Peng Zhao, Yin-Hao Chen, Mao-Heng Yuan et al. · 0 citations
#artificial intelligence Preprint Oct 2026

Tree-Aware Posterior Distillation for Long-Horizon Agentic Reinforcement Learning

TreeOPSD is introduced, a critic-free, tree-aware posterior self-distillation framework for long-horizon agentic reinforcement learning that improves agentic capabilities across several competitive benchmarks and model scales, especially for long-horizon tasks.

Heming Zou, Qi Wang, Yi-Xiu Mao et al. · 2 citations
Preprint Nov 2026

BLPO: Beyond-Local Policy Optimization for Long-Horizon LLM Agents

Beyond-Local Policy Optimization (BLPO), which estimates task-progress advantages from experience shared across tasks and training updates, and accumulates context-relative returns in a global memory with balanced aggregation and reliability weighting to control bias and noise from heterogeneous tasks.

Xuan-Ren Chen, Chong-Yang Tao, Wen-Peng Hu et al. · 0 citations

Learning Beyond What You Sample: Off-Policy-Aware Cross-Model Trajectory Exchange for RLVR

GRAFT (Gated Replacement of Answer-Failed groups with peer Trajectories), an off-policy-aware framework that replaces all-fail groups with informative peer groups and transfers both successful and unsuccessful peer responses with peer-computed advantages, while controlling cross-model mismatch through sequence-level co...

Doohyuk Jang, Y. Park, Gyouk Chu et al. · 0 citations
#artificial intelligence Preprint Oct 2026

Hindsight-Privileged RLVR: Single-Rollout Token Credit Without Group Sampling

Reinforcement learning with verifiable rewards (RLVR) trains language models from checked task outcomes, but assigning a terminal reward to individual reasoning tokens or actions remains difficult. Group-relative methods such as Group Relative Policy Optimization (GRPO) sample several attempts per prompt, but lose thei...

Wei Chen, Yu-Bing Wu, Zhou-Shi Xu et al. · 0 citations
#artificial intelligence Preprint Oct 2026

Action-Value Calibration via Continuation Sharing for Long-Horizon Agentic Reinforcement Learning

Reinforcement learning for long-horizon agents relies on feedback from sequences of interactions, making credit assignment to individual actions difficult. Existing methods such as GiGPO compare actions at shared states to compute relative advantages, but estimate each action's value from a single sampled continuation....

Ying-Jian Chen, Lang Zhou, Zi-Xi Zhao et al. · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.