CAST Turns Game Solver Values Into Turn-Level Training Signals

Reinforcement learning for LLM agents has been stuck on a familiar wall: the model wins or loses at the end of a long sequence of decisions, but the reward signal says nothing about which of those decisions actually mattered. The standard assumption is that this is a fundamental difficulty of credit assignment in RL. It is not. It is a data problem, and game solvers already have the answer sitting in their state-value functions.

CAST (Credit Assignment from Solver Teachers) extracts that answer with almost no overhead. The core observation is straightforward: a solver that can evaluate any board position already knows whether a given move improved the situation. The difference between the solver's value estimate before and after a move is exactly the per-turn credit signal that RLVR is missing. CAST converts those value deltas into what the paper calls solver advantages, then injects them directly into the RLVR training loop as turn-level rewards alongside the sparse final signal.

The mechanism has a clean theoretical grounding that makes it more than an engineering patch. Under a soft-optimal solver assumption, maximizing the solver advantage turns out to be equivalent to on-policy distillation from the solver. That equivalence matters because it means CAST does not need the solver's output distribution or logits. It only needs scalar state values. The solver stays cheap, the training signal gets dense, and the method generalizes to any domain where a value function can be queried.

Think of it as the difference between a coach who tells a chess student "you lost" at the end of the game versus one who marks each move as good or bad as the game unfolds. The final outcome is the same sparse signal; the per-move annotations are what CAST adds, and they cost almost nothing to generate once a solver exists.

CAST beats every trained baseline on Sokoban, Minesweeper, and Rush Hour, in both in-domain and unseen-difficulty evaluation. It also posts the highest average zero-shot score across ALFWorld and WebShop, two environments where no game solver is available, which means the training improvements transfer to settings the method was not explicitly designed for. For teams training LLM agents on long-horizon tasks, the takeaway is direct: if a solver or any value-estimating oracle exists for your domain, its scalar outputs are a training resource worth using immediately.

We're thinking: We find the theoretical equivalence between solver-advantage maximization and on-policy distillation more significant than the benchmark numbers alone. It reframes the sparse-reward problem as a teacher-availability problem: the question is not whether RL can handle long horizons, but whether you have an oracle that can score intermediate states. Game domains have solvers; many production agent tasks have partial oracles too, such as unit tests that pass or fail mid-trajectory, API response validators, or simulation environments that can be queried for intermediate state quality. CAST's framing suggests those signals are being systematically underused. The caveat worth watching is whether value-function quality degrades gracefully when the solver is imperfect, a question the soft-optimal assumption papers over.

Key takeaways:

• CAST converts game-solver state-value deltas into turn-level advantage signals and injects them into RLVR, replacing sparse final rewards with dense per-step credit at minimal additional cost.
• CAST beats all trained baselines on three puzzle games under in-domain and out-of-distribution difficulty, and achieves the best average zero-shot performance on ALFWorld and WebShop; the main caveat is that results depend on having a reasonably accurate intermediate-state oracle.
• Teams training LLM agents on long-horizon tasks should audit their existing infrastructure for any oracle capable of scoring intermediate states, such as simulators, validators, or partial-reward functions, and treat those scalar outputs as turn-level teacher signals rather than leaving them unused.

Source: CAST: Game Solvers as Turn-Level Teachers for LLM Agents