# RTMC: Step-Level Credit Assignment via Rollout Trees

arXiv: https://arxiv.org/abs/2604.11037 · HTML: https://mlsanity.com/paper/2604.11037/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 13 Apr 2026.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)
- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 12 of 12)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [R2E-Gym: Procedural Environments and Hybrid Verifiers for Scaling Open-Weights SWE Agents](https://mlsanity.com/paper/2504.07164/) (2025)
- [AgentRL: Scaling Agentic Reinforcement Learning with a Multi-Turn, Multi-Task Framework](https://mlsanity.com/paper/2510.04206/) (2025)
- [Agentic Reinforcement Learning with Implicit Step Rewards](https://mlsanity.com/paper/2509.19199/) (2025)
- [Let It Flow: Agentic Crafting on Rock and Roll, Building the ROME Model within an Open Agentic Learning Ecosystem](https://mlsanity.com/paper/2512.24873/) (2025)
- [Exploiting Tree Structure for Credit Assignment in RL Training of LLMs](https://mlsanity.com/paper/2509.18314/) (2025)

## Built on by (most cited first, 12 of 12)

- [How Much, Then Where: Credit-Conserving Action-to-Token Allocation for Multi-Turn Agent Reinforcement Learning](https://mlsanity.com/paper/2608.07118/) (2026)
- [Semantic Consistency Policy Optimization for Reinforcement Learning of LLM Agents](https://mlsanity.com/paper/2606.25852/) (2026)
- [Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.28963/) (2026)
- [SWE-MILE: Asynchronous Potential-Induced Milestone Credit Assignment for Long-Horizon Software Engineering Agents](https://mlsanity.com/paper/2609.32631/) (2026)
- [SkillRubric: Co-Evolving Actor Guidance and Evaluator Rubrics for Multimodal Agents](https://mlsanity.com/paper/2609.34557/) (2026)
- [Cross-Rollout Bellman Closure for Long-Horizon Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.35082/) (2026)
- [EvoSteer: Online Self-Evolving Graph Orchestration via Reference-Anchored Credit Assignment](https://mlsanity.com/paper/2609.38661/) (2026)
- [Advancing Entropy-Level Credit Assignment in RLVR via Proximal Entropy Policy Optimization](https://mlsanity.com/paper/2609.39402/) (2026)
- [Characterizing a Configuration Where Inference-Time PRM-Pruned Fragment Grafting Is Inert: Evidence from Three Reasoning LMs](https://mlsanity.com/paper/2610.00047/) (2026)
- [SCAD: Structured Credit Assignment and Distillation for Long-Horizon Agents](https://mlsanity.com/paper/2610.03372/) (2026)
- [CIPO: Counterfactual Imagination Policy Optimization for Adaptive Tool Granularity Selection](https://mlsanity.com/paper/2610.04991/) (2026)
- [Matched-Context Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2610.13755/) (2026)

## Abstract (arXiv)

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.