Search papers, labs, and topics across Lattice.
This paper introduces Rollout-Tree Monte Carlo (RTMC), a novel critic-free reinforcement learning method that estimates per-step Q-values by aggregating return statistics across rollouts sharing common states, effectively building a rollout tree. RTMC uses a state-action signature system to compress interaction histories for efficient state matching across rollouts. Experiments on SWE-bench Verified demonstrate that RTMC improves pass@1 by 3.2 percentage points compared to GRPO, showcasing the benefits of fine-grained credit assignment without a learned critic.
Ditching the critic doesn't mean sacrificing fine-grained credit assignment: RTMC leverages overlapping states in rollout trees to estimate per-step Q-values, outperforming critic-free baselines on SWE-bench.
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.
DAMO