One-sentence Summary

University of Science and Technology of China et al. propose CAST (Credit Assignment from Solver Teachers), which derives turn-level credit from game-solver value changes as solver advantages for RLVR, demonstrating that under a soft-optimal solver this scalar-only signal is equivalent to on-policy distillation without teacher logits, and CAST outperforms all trained baselines on Sokoban, Minesweeper, Rush Hour, ALFWorld, and WebShop.

Key Contributions

• CAST converts per-action changes in a game solver’s state value into solver advantages that provide fine-grained, turn-level credit for reinforcement learning with verifiable rewards, without requiring teacher logits.
• Maximizing the solver advantage is theoretically equivalent to on-policy distillation from the solver, and the signal is stabilized through asinh compression and batch-level RMS normalization, yielding an efficient logit-free distillation objective.
• Across Sokoban, Minesweeper, and Rush Hour, CAST outperforms all trained baselines under in-domain and unseen-difficulty settings, reaches DAPO’s peak validation performance in 1.7–2.0× fewer steps, and achieves the highest average zero-shot performance on ALFWorld and WebShop. Exact solver queries add negligible overhead.

Introduction

The authors tackle the challenge of training generalist LLM agents for interactive decision-making in environments like Sokoban, Minesweeper, and Rush Hour, where sparse terminal rewards create a severe credit-assignment problem: it is unclear which actions in a trajectory caused success or failure. Prior methods try to densify the signal via costly search, learned process reward models, or cross-trajectory comparisons, but each involves trade-offs in computation, supervision quality, or reliability. The authors leverage classical game solvers as turn-level teachers, introducing CAST (Credit Assignment from Solver Teachers), which computes a solver advantage by comparing solver-estimated state values before and after each LLM action. This scalar advantage is injected into reinforcement learning with verifiable rewards as fine-grained process supervision, and they prove that under a soft-optimal solver, maximizing it is equivalent to on-policy distillation without needing the solver’s full action distribution. With lightweight signal stabilization, CAST yields state-of-the-art in-domain and generalization performance, while adding negligible training overhead.

Method

The authors address the credit-assignment bottleneck in outcome-supervised reinforcement learning with verifiable rewards (RLVR) by introducing a solver-guided turn-level credit mechanism. Traditional methods like GRPO assign a single trajectory-level advantage to every token, which is insufficient for long-horizon games. To refine this, the authors leverage a game-specific solver as a turn-level teacher that scores each action individually, transforming the sparse terminal reward into a dense per-step process signal.

To score each action, the method utilizes the solver cost-to-go function, $N(s)$N(s), which represents the minimum amount of work required to reach a win from state $s$s. The authors define an auxiliary shortest-path objective and compute the solver advantage as:

Under the solver optimal policy, the expected next-state cost equals $N(s_t) - 1$N(st​)−1, making the raw advantage non-positive. To map progress to positive credit, the authors shift the advantage by +1, yielding the shifted solver advantage:

This shifted score directly reflects the drop in cost-to-go caused by a move, assigning +1 for optimal progress, 0 for no progress, and negative values for harmful moves.

Because the raw shifted advantage can be heavy-tailed and vary in scale across different games, the authors apply two lightweight transformations to shape the signal for stable training. First, an asinh compression, $g(x) = \ln(x + \sqrt{x^2 + 1})$g(x)=ln(x+x2+1​), is used to preserve small-progress values while logarithmically compressing rare and large dead-state penalties. Second, batch-level RMS normalization rescales the compressed signal by its root-mean-square magnitude over all turns in the batch, ensuring a consistent scale without shifting the zero point that encodes neutral progress.

The overall pipeline combining these signals is illustrated below.

The shaped solver signal is then integrated into the GRPO training pipeline. For a trajectory $i$i at turn $t$t, the final advantage combines the trajectory-level outcome advantage with the turn-level shaped solver advantage:

where $\alpha$α controls the strength of the solver guidance. This combined advantage replaces the standard outcome advantage in the clipped GRPO surrogate objective, allowing the terminal reward to anchor global win-or-loss credit while the solver signal refines it step by step.

Finally, the authors demonstrate that this solver advantage is mathematically equivalent to on-policy distillation (OPD). By treating the solver as a soft-optimal teacher policy, the solver advantage corresponds to the teacher log-preference for an action. Consequently, the policy-gradient update implicitly maximizes the task return while minimizing the cross-entropy from the student policy to the solver policy. This logit-free OPD formulation allows the student policy to use the solver distribution as a prior, tilting it exponentially based on the task advantage, which enables the student to potentially surpass the teacher performance.

Experiment

The evaluation uses three classic games (Sokoban, Minesweeper, Rush Hour) with in-domain and unseen-difficulty settings, plus zero-shot transfer to ALFWorld and WebShop, comparing a Qwen3-4B-Instruct-2507 base policy against training-free ReAct prompts, closed-source models, and outcome-only or process-level RL baselines. The experiments confirm that the solver-derived turn-level signal consistently improves performance, leading to higher success rates on training games, better generalization to harder levels and held-out domains, and faster training convergence. Ablations show that each design component (solver-advantage weight, asinh transformation, batch RMS normalization) contributes to the gain, while analysis reveals that solver queries add negligible training overhead and that replacing the exact solver with a learned value network preserves most of the benefit, demonstrating the method's practical utility.

Among closed-source models using ReAct prompting, Sonnet-4.6 leads overall, achieving the highest average success rates on both in-domain and unseen difficulty levels across the three training games. Gemini 2.5 Pro ranks second, while all models show a clear drop when moving from in-domain to unseen levels, with the gap varying by game. Sonnet-4.6 attains the best average success on both in-domain and unseen splits, followed by Gemini 2.5 Pro. Every model suffers a performance decline from in-domain to unseen difficulty, with especially sharp drops in some games such as Minesweeper.

In zero-shot out-of-distribution transfer, CAST achieves the highest success rates on both domains, outperforming all RL-trained baselines and the training‑free ReAct prompt. On ALFWorld it reaches 37.9% (5.8 points above the best trained baseline), on WebShop 22.7% (4.8 points above the best trained baseline), and an overall average of 30.3%, which is 5.6 points higher than the next best method. CAST attains the top domain averages: 37.9% on ALFWorld and 22.7% on WebShop, exceeding the strongest RL-trained baselines (GSPO at 32.1% and GiGPO at 17.9%) by clear margins. The training‑free ReAct baseline scores 30.2% on ALFWorld and 18.8% on WebShop, while CAST’s overall average of 30.3% is well above ReAct’s 24.5% and all other methods.

Two experiments assess agent performance under different conditions. The first compares closed-source models using ReAct prompting across training games, where Sonnet-4.6 achieves the highest success rates but all models exhibit a clear drop on unseen difficulty levels, with particularly sharp declines in games like Minesweeper. The second evaluates zero-shot out-of-distribution transfer, showing that CAST significantly outperforms both RL-trained baselines and the training-free ReAct prompt on ALFWorld and WebShop.