CM2: Reinforcement Learning with Checklist Rewards for Multi-Turn and Multi-Step Agentic Tool Use

Paper: 2602.12268 Authors: Zhen Zhang, Kaiqiang Song, Xun Wang, Yebowen Hu, Weixiang Yan, Chenyang Zhao, Henry Peng Zou, Haoyun Deng, Sathish Reddy Indurthi, Shujian Liu Categories: cs.AI

Abstract

AI agents are increasingly deployed to handle complex real-world tasks requiring multi-turn interactions and external tool invocation. However, applying reinforcement learning to such scenarios faces fundamental challenges: realistic objectives often lack verifiable rewards, multi-turn and multi-step agentic tool use remains underexplored in RL contexts, and building executable tool environments is prohibitively expensive. This paper introduces CM2 (Checklist rewards for Multi-turn and Multi-step tool use), an RL framework that replaces traditional verifiable outcome rewards with structured checklist rewards. By decomposing intended behaviors into fine-grained binary criteria with explicit evidence grounding, CM2 transforms open-ended evaluation into stable classification decisions. The framework employs sparse reward assignment with dense evaluation criteria and trains in scalable LLM-simulated environments. Experimental results demonstrate consistent improvements over supervised fine-tuning, with an 8B model achieving 8-point gains on $\tau$-Bench, 10 points on BFCL-V4, and 12 points on ToolSandbox, matching or exceeding similarly-sized open-source baselines.

Key Contributions

• Checklist Reward Framework: Introduces a novel reward mechanism that decomposes complex agent behaviors into fine-grained, verifiable binary criteria with explicit evidence grounding, making RL training more stable and interpretable
• Sparse-Dense Strategy: Balances training stability and informativeness through sparse reward assignment combined with dense evaluation criteria across multiple behavioral dimensions
• Scalable LLM-Simulated Environment: Eliminates the need for costly executable tool environments by leveraging LLM simulation, enabling training on diverse tool sets without heavy engineering overhead
• Strong Empirical Results: Demonstrates consistent improvements over SFT baselines across multiple benchmarks, with the 8B model achieving performance comparable to or exceeding larger open-source models

Methodology

The CM2 framework addresses the core challenge of reward design for multi-turn, multi-step tool-using agents through several key innovations:

Checklist Reward Structure: Instead of relying on verifiable final outcomes, CM2 decomposes each turn’s intended behavior into a structured checklist of binary criteria. Each criterion includes: (1) a clear behavioral expectation, (2) explicit evidence requirements from the agent’s output, and (3) structured metadata for systematic evaluation. This decomposition converts subjective, open-ended judgments into more objective classification tasks.

Reward Assignment Strategy: The framework adopts a “sparse assignment, dense criteria” approach. Rewards are assigned sparsely—only at specific decision points—but each assignment considers dense evaluation across multiple criteria. This design prevents reward hacking while maintaining rich feedback signals. The reward function can be formalized as:

$R(s, a) = \sum_{i=1}^{n} w_i \cdot \mathbb{1}[\text{criterion}_i(s, a) = \text{true}]$

where $w_i$ represents the weight of criterion $i$, and $\mathbb{1}[\cdot]$ is the indicator function.

LLM-Simulated Tool Environment: Rather than building and maintaining executable tool environments, CM2 uses LLM simulation to model tool behaviors and outcomes. This approach dramatically reduces engineering costs while enabling coverage of diverse tool sets. The simulator generates realistic tool responses based on the agent’s actions, creating a scalable training environment.

Training Pipeline: The RL training process uses Proximal Policy Optimization (PPO) with the checklist-based reward signal. Starting from a supervised fine-tuned base model, the agent explores the simulated environment, receives checklist-based feedback, and iteratively improves its policy for multi-turn tool use.

Experimental Results

The experiments validate CM2’s effectiveness across three challenging benchmarks for agentic tool use:

Benchmark Performance: Starting from an 8B parameter base model and training on an 8k-example RL dataset, CM2 achieves:

• $\tau$-Bench: 8-point improvement over SFT baseline
• BFCL-V4: 10-point improvement over SFT baseline
• ToolSandbox: 12-point improvement over SFT baseline

These gains are particularly notable given the relatively small RL dataset size, suggesting that checklist rewards provide highly informative training signals.

Comparison with Baselines: The CM2-trained 8B model matches or outperforms similarly-sized open-source baselines, including models specifically designed for tool use. Remarkably, it even exceeds the performance of the judging model used to generate checklist evaluations in some cases, indicating that the RL process successfully extracts and generalizes behavioral patterns beyond the judge’s explicit knowledge.

Ablation Studies: The paper demonstrates that both components—checklist decomposition and the sparse-dense reward strategy—are essential. Removing either component leads to degraded performance, with pure outcome-based rewards showing instability and dense reward assignment causing reward hacking behaviors.

Generalization: The framework shows strong generalization to unseen tools and task variations, suggesting that the learned policies capture fundamental reasoning patterns for tool use rather than memorizing specific tool behaviors.

Implications and Future Directions

CM2 represents a significant step toward practical RL for complex agentic systems. The checklist reward paradigm offers several advantages:

Scalability: By eliminating the need for executable environments and verifiable outcomes, CM2 enables RL training on much larger and more diverse tool sets than previously feasible. This scalability is crucial for real-world deployment where agents must handle hundreds or thousands of tools.

Interpretability: The explicit checklist structure provides transparency into what behaviors are being rewarded, making it easier to diagnose training issues and align agent behavior with intended objectives. Each criterion serves as a interpretable component of the overall reward signal.

Flexibility: The framework can accommodate various task types and behavioral requirements by adjusting the checklist criteria. This flexibility makes it applicable beyond tool use to other multi-turn, multi-step agent scenarios.

Future Research Directions: Several promising extensions emerge:

• Automated checklist generation from task specifications
• Hierarchical checklists for complex, long-horizon tasks
• Integration with other RL algorithms beyond PPO
• Application to multi-agent scenarios with coordinated tool use
• Combining checklist rewards with sparse verifiable outcomes when available

The work also raises important questions about the role of LLM judges in RL training and the potential for self-improvement loops where agents exceed their evaluators’ capabilities.

Takeaways

1. Checklist rewards provide a practical alternative to verifiable outcomes for RL training of complex agents, decomposing open-ended behaviors into stable binary criteria
2. The sparse-dense reward strategy effectively balances training stability with informative feedback signals in multi-turn, multi-step scenarios
3. LLM-simulated tool environments enable scalable RL training without costly executable infrastructure, dramatically expanding the scope of trainable tool sets
4. An 8B model trained with CM2 achieves 8-12 point improvements over SFT across multiple benchmarks, matching or exceeding larger specialized baselines
5. The framework’s success suggests that fine-grained behavioral decomposition may be key to applying RL in realistic agentic settings where traditional reward engineering fails