Technical Summary: CAST (Credit Assignment from Solver Teachers)

Problem Statement

Training Large Language Models (LLMs) to act as generalist agents in long-horizon environments, such as classical games (Sokoban, Minesweeper, Rush Hour), faces a critical bottleneck: sparse reward signals. While Reinforcement Learning with Verifiable Rewards (RLVR) has succeeded in single-turn tasks, it relies on final outcome rewards (win/loss) that provide no information about which specific intermediate decisions led to success or failure. This creates a fundamental credit-assignment problem where every token in a trajectory receives the same coarse feedback, hindering the model's ability to learn long-horizon planning, goal-directed exploration, and error recovery. Existing attempts to densify these signals via costly search, learned process reward models, or cross-trajectory comparisons often suffer from trade-offs between computational cost, supervision quality, and signal reliability.

Methodology: CAST

The authors propose CAST (Credit Assignment from Solver Teachers), a framework that leverages domain-specific game solvers to provide fine-grained, turn-level supervision for LLM agents.

Core Mechanism

1. Solver as a Turn-Level Teacher: Instead of using a solver only to generate expert trajectories (which limits learning to expert-visited states), CAST uses the solver to evaluate the LLM's on-policy actions in real-time.
2. Solver Advantage Construction:
   • The solver computes a cost-to-go value, $N(s)$, representing the minimum steps required to win from state $s$.
   • For an action $a_t$ taken by the LLM transitioning from $s_t$ to $s_{t+1}$, the method calculates the change in cost-to-go.
   • A shifted solver advantage is defined as:
     $$\tilde{A}^{\pi_{Solver}}(s_t, a_t) = N(s_t) - \mathbb{E}[N(s_{t+1})]$$
   • This value is positive if the action reduces the distance to the goal (progress), zero if neutral, and negative if it increases the distance or leads to a dead end.
3. Signal Shaping: To prevent training instability caused by heavy-tailed values (e.g., large penalties for dead ends) and scale differences across games, CAST applies two transformations:
   • Asinh Compression: $g(x) = \text{asinh}(x)$, which preserves small values linearly while compressing extreme outliers logarithmically.
   • Batch-level RMS Normalization: Rescales the signal by its root-mean-square magnitude within a batch to ensure consistent scales, without subtracting the mean (to preserve the semantic meaning of zero as "no progress").
4. Integration with RLVR: The shaped solver advantage is added to the standard trajectory-level outcome advantage (e.g., from GRPO) to form a combined advantage signal:
   $$\hat{A}_{i,t} = \hat{A}^{outcome}_i + \alpha \cdot h(\tilde{A}^{\pi_{Solver}}_{i,t})$$
   This combined signal is used in the clipped surrogate objective to update the policy.

Theoretical Insight: Logit-Free On-Policy Distillation

The paper establishes a theoretical equivalence between maximizing the solver advantage and on-policy distillation (OPD) from a soft-optimal teacher.

• Under the assumption that a strong solver acts as a soft-optimal policy where action probabilities are proportional to $\exp(Q/\tau)$, the solver advantage is mathematically proportional to the log-probability of the action under the solver's policy.
• Key Contribution: This implies that the scalar solver advantage inherently encodes the teacher's preference distribution. Consequently, CAST achieves distillation without requiring teacher logits (the full action distribution), relying only on scalar values. This allows the student LLM to learn from the solver's value function efficiently.

Key Contributions

1. Solver-Derived Credit: The introduction of a method to convert game solver state-value changes into fine-grained, turn-level advantages for LLM training.
2. Logit-Free Distillation: A theoretical proof that maximizing solver advantages is equivalent to on-policy distillation, enabling efficient training using only scalar values rather than full teacher distributions.
3. Stable Signal Shaping: The use of asinh transformation and batch-level RMS normalization to handle extreme values and cross-domain scale variations, ensuring stable integration into RLVR.
4. Practicality: Demonstration that exact solvers add negligible overhead and that learned value networks (e.g., DQN) can serve as effective approximations when exact solvers are unavailable.

Experimental Results

The method was evaluated on Sokoban, Minesweeper, and Rush Hour, with zero-shot transfer to ALFWorld and WebShop.

• In-Domain Performance: CAST outperformed all trained baselines (GRPO, GSPO, DAPO, GiGPO) and training-free prompting methods (including strong closed-source models like Claude-Opus-4.6) across all three games in both in-domain and unseen-difficulty settings.
  • On average, CAST achieved a 62.1% success rate (Avg@4) on in-domain tasks and 28.4% on unseen difficulties, significantly outperforming the backbone DAPO (44.7% ID, 18.7% Unseen).
• Sample Efficiency: CAST reached the peak validation performance of DAPO in 1.7× to 2.0× fewer training steps across the three games.
• Zero-Shot Generalization: Without further fine-tuning, CAST agents transferred to ALFWorld and WebShop, achieving the highest average zero-shot performance (30.3% overall) among all methods, surpassing the next best baseline by 5.6 points.
• Ablation Studies:
  • The solver-advantage weight ($\alpha$) is critical; $\alpha=0.1$ provided the best balance between process guidance and outcome objectives.
  • Both asinh compression and RMS normalization were essential; removing either degraded performance, with the removal of asinh causing the most significant drop due to gradient instability from extreme values.
• Learned Solvers: Replacing the exact solver with a learned DQN value network retained most of the performance benefits, demonstrating the method's applicability beyond games with exact solvers.

Significance and Claims

The paper claims that CAST addresses the fundamental credit-assignment challenge in long-horizon RLVR by providing a scalable, fine-grained signal derived from domain solvers. By proving the equivalence to logit-free on-policy distillation, the method offers a practical pathway to align LLMs with expert value functions without the computational burden of generating full action distributions. The results suggest that reliable state evaluation—whether via exact solvers or learned value functions—provides a robust route from sparse outcomes to dense, actionable feedback, enabling LLMs to master complex, multi-step decision-making tasks more efficiently than outcome-only approaches.