RTMC: Step-Level Credit Assignment via Rollout Trees

Tao Wang; Suhang Zheng; Xiaoxiao Xu

cs.LGApr 13, 2026

RTMC: Step-Level Credit Assignment via Rollout Trees

Authors: Tao Wang, Suhang Zheng, Xiaoxiao Xu

Organizations: Alibaba Group

Abstract

Multi-step agentic reinforcement learning benefits from fine-grained credit assignment, yet existing approaches offer limited options: critic-free methods like GRPO assign a uniform advantage to every action in a trajectory, while learned value networks introduce notable overhead and can be fragile under sparse rewards. We observe that group rollouts targeting the same problem often traverse overlapping intermediate states, implicitly forming a tree whose branches diverge at successive decision points. Building on this insight, we introduce Rollout-Tree Monte Carlo (RTMC) advantage estimation, which aggregates return statistics across rollouts sharing a common state to produce per-step Q-values and advantages--without any learned critic. A state-action signature system compresses raw interaction histories into compact, comparable representations, making cross-rollout state matching tractable. On SWE-bench Verified, RTMC improves pass@1 by 3.2 percentage points over GRPO.

Figures & tables

s_{0}

(

N{=}4

)

\overset{\scriptstyle a_{1}}{\swarrow}

\overset{\scriptstyle a_{2}}{\searrow}

R{=}0,\;G_{0}{=}0

s_{1}

(

N{=}3

)

\overset{\scriptstyle a_{3}}{\swarrow}

\overset{\scriptstyle a_{4}}{\searrow}

R{=}1,\;G_{0}{=}\gamma

s_{2}

(

N{=}2

)

\overset{\scriptstyle a_{5}}{\swarrow}

\overset{\scriptstyle a_{6}}{\searrow}

R{=}1,\;G_{0}{=}\gamma^{2}

R{=}0,\;G_{0}{=}0

\hat{Q}(s_{0},a_{1}){=}0

\hat{Q}(s_{0},a_{2}){=}\tfrac{\gamma+\gamma^{2}}{3}

\hat{V}(s_{0}){=}\tfrac{\gamma+\gamma^{2}}{4}

\hat{A}(s_{0},a_{2}){>}0

\hat{A}(s_{0},a_{1}){<}0

Figure 1: A rollout tree from four rollouts. Rollout 1 terminates at depth 1 via

a_{1}

(failure), while rollouts 2–4 share action

a_{2}

and diverge at deeper states

s_{1},s_{2}

. Returns

G_{0}

are discounted from terminal rewards back to

s_{0}

, yielding per-action advantages.

Category	Description	Example
view	Inspect file content (full or range-based)	file_editor view , cat , head
search	Locate files or code patterns	search , grep , find , ls
modify	Edit existing code (replace or insert)	str_replace , insert
create	Create a new file	file_editor create
execute	Run a script for debugging or reproduction	python reproduce.py
test	Execute test suites to validate changes	pytest , python -m unittest

Table 1: Action categories classified by effect on problem-solving progress. Dedicated tools and bash commands with equivalent effects map to the same category.

Operation	Encoding	Example	Notes
View (full file)	Vf	core.py:Vf
View (partial)	V[b]	core.py:V[2]	Lines 200–299
Modify	M:xxxx	core.py:M:a3f2	4-char content hash
Insert	I:xxxx	core.py:I:b7c1	4-char content hash
Search	S	core.py:S
Create	C	test.py:C

Table 2: State signature operation encodings.

Method	Resolved	Pass@1	$\Delta$ vs Baseline
Baseline (no training)	234 / 500	46.8%	—
GRPO	245 / 500	49.0%	+2.2 pp
GRPO + Step Reward	252 / 500	50.4%	+3.6 pp
Rollout-Tree MC	261 / 500	52.2%	+5.4 pp

Table 3: Pass@1 on SWE-bench Verified (500 problems), determined by majority vote over 3 evaluation runs. Best checkpoint selected for each method.

\Delta

denotes improvement over the baseline.

Figure 2: Training episode resolve rate on the R2E dataset. All methods start from the same pretrained checkpoint and share the GRPO optimization framework; they differ only in how per-token advantages are computed. The progressive separation confirms that finer-grained credit assignment yields more effective policy gradients.

Configuration	Pass@1
Rollout-Tree MC w/o prior ( $n_{\text{prior}}{=}0$ )	49.7%
Rollout-Tree MC full ( $n_{\text{prior}}{=}2$ )	52.2%
Improvement from prior smoothing	+2.5 pp

Table 4: Ablation of prior-based value smoothing. Removing the prior (

n_{\text{prior}}{=}0

) reduces pass@1 by 2.5 percentage points.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Rollout-Tree visualization extracted from training-time rollouts on datalad_final_05ea .

Figure 4: Step-level advantage for each of the 8 rollouts (4 success, 4 failure) in datalad_final_05ea . Each subplot title shows the method and rollout outcome (SUCCESS/FAIL). GRPO and GRPO+Step provide coarse-grained credit assignment, while RTMC produces step-varying advantages that reflect local action quality within the rollout tree.

Figure 5: Quadrant analysis of step-level advantage agreement between GRPO+Step and RTMC on datalad_final_05ea (4 success, 4 failure rollouts). Each bar shows the number of action steps (with percentage) falling into the four agreement quadrants. Blue bars ( X $-$ , Y+ ) indicate steps where RTMC assigns positive advantage while GRPO+Step assigns negative—steps RTMC rescues in failure rollouts (3%). Orange bars ( X+, Y $-$ ) indicate steps GRPO+Step blindly rewards but RTMC correctly penalizes as suboptimal (15% of success-rollout steps).

Step-Level Credit Assignment in RL

Step-level credit assignment in reinforcement learning links delayed rewards to the actions or reasoning steps that produced them.

See all 164 papers

Cross-Rollout Bellman Closure for Long-Horizon Agentic Reinforcement Learning
Sep 28, 2026Yangyang Ren, Haodong Zhu, Linlin Yang +3Critic-Free RL Step-Level Credit Assignment in RL
Beihang University · Zhongguancun Academy · Communication University of China +2
Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning
Sep 24, 2026Xincheng Yao, Haobo Fu, Weiming Liu +1Agentic RL Credit Assignment in RL
School of Information Science and Electronic Engineering, Shanghai Jiao Tong University. · Tencent AI Platform Department. · MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University.
TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents
Jul 15, 2026Leitian Tao, Baolin Peng, Wenlin Yao +5Credit Assignment in RL Step-Level Credit Assignment in RL
University of Wisconsin–Madison · Microsoft Research

Sep 28, 2026J/K move · Enter open · S save

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

Yangyang Ren, Haodong Zhu, Linlin Yang, Sheng Xu+2

Beihang University · Zhongguancun Academy · Communication University of China+2

Critic-Free RL Step-Level Credit Assignment in RL Temporal Credit Assignment Agentic RL RL for LLM Agents Policy Learning+1

Open paper AskPDF arXiv

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.

Abstract

Step-Level Credit Assignment in RL

Explore similar work

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

Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning

TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents