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

Yu Wang; Yi-Kai Zhang; Wentao Shi; Ziang Ye; Yuchun Miao; Yueqing Sun; Qi Gu; Xunliang Cai; Lan-Zhe Guo; Han-Jia Ye; Fuli Feng

Source-linked AI summary

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

Yu Wang, Yi-Kai Zhang, Wentao Shi, Ziang Ye, Yuchun Miao, Yueqing Sun, Qi Gu, Xunliang Cai, Lan-Zhe Guo, Han-Jia Ye, Fuli Feng

arXiv:2607.25308v1Jul 28, 2026cs.CLcs.AI

TL;DR

Long-horizon game agents lack scalable, fine-grained signals identifying which actions drive success. CAST converts solver value changes into turn-level RLVR credit, and it outperforms trained baselines across three games while reaching DAPO’s peak validation performance in 1.7–2.0× fewer training steps.

Problem
RLVR’s sparse terminal rewards provide little guidance about which decisions determine success, while denser existing process signals trade off computation, supervision, and reliability.
Method
CAST compares solver state values before and after each LLM action to derive solver advantages for RLVR, yielding logit-free on-policy distillation under a soft-optimal solver assumption.
Results
Across Sokoban, Minesweeper, and Rush Hour, CAST performs best among trained methods in both in-domain and unseen-difficulty evaluations and reaches DAPO’s peak validation performance in 1.7–2.0× fewer training steps.
Takeaways & Limitations
Solver-derived scalar feedback supplies effective turn-level supervision without teacher logits and transfers zero-shot to ALFWorld and WebShop.
Takeaways & Limitations
CAST’s theoretical equivalence to on-policy distillation assumes a soft-optimal solver, bounded solver advantages, and an unbiased GRPO task-return gradient under a frozen-visitation surrogate.

Abstract

from arXiv · show

Training large language models (LLMs) to act in long-horizon games is a promising step toward generalist decision-making, yet reinforcement learning with verifiable rewards (RLVR) relies on sparse final rewards that reveal little about which decisions determine success. Denser process signals could supply this missing turn-level credit, but existing sources are hard to keep both cheap and accurate. We observe that changes in a game solver's state value reveal whether an action advances the state toward success. Building on this insight, we propose CAST (Credit Assignment from Solver Teachers), which converts these value changes into solver advantages and injects them into RLVR as turn-level signals. We further show that, under a soft-optimal solver assumption, maximizing the solver advantage is equivalent to on-policy distillation from the solver, requiring only scalar values rather than teacher logits. Across Sokoban, Minesweeper, and Rush Hour, CAST outperforms all trained baselines on every game under both in-domain and unseen-difficulty evaluation and achieves the highest average zero-shot performance on ALFWorld and WebShop. Our code is available at https://github.com/Wloner0809/CAST.

1 INTRODUCTION

CAST addresses sparse outcome-only RLVR feedback by using game solvers as turn-level teachers that provide fine-grained credit for LLM actions. It converts solver value changes into solver advantages, yielding logit-free on-policy distillation with stabilizing signal transformations and strong performance across games and transfer tasks.

Motivation: Outcome-only RLVR cannot identify which trajectory decisions caused a game win or loss, creating a fundamental credit-assignment challenge.The paper frames scalable, fine-grained learning signals as a central bottleneck for generalist LLM game agents.
Method: CAST treats game solvers as turn-level teachers and uses solver value changes to assign fine-grained credit to LLM-sampled actions.Unlike solver-generated SFT trajectories, the approach supplies feedback during on-policy exploration, including after the model deviates from expert behavior.
Method: Maximizing solver advantage is equivalent to on-policy distillation under a soft-optimal solver assumption, without requiring teacher logits.Classical solvers provide an optimal action or scalar cost-to-go rather than a full token-space distribution.
Method: CAST stabilizes solver signals with asinh compression and batch-level RMS normalization across games and domains.The asinh transformation compresses extreme values while preserving small-signal resolution, while RMS normalization removes cross-domain scale differences.
Results: CAST achieves the best performance among trained methods on Sokoban, Minesweeper, and Rush Hour in both in-domain and unseen-difficulty settings.The paper also reports negligible solver overhead, substantial retention of exact-solver benefits with a learned value network, and the highest average zero-shot performance on ALFWorld and WebShop.

2 METHOD

CAST formulates games as finite-horizon MDPs with sparse terminal win rewards, then adds dense turn-level supervision from solver cost-to-go changes while preserving the original objective. The resulting scalar solver advantages are stabilized, combined with GRPO outcome advantages, and under soft-optimality yield logit-free on-policy distillation.

Games as multi-turn MDPs: Games are modeled as finite-horizon MDPs whose sparse, verifiable reward is 1 only when the terminal state is solved.Sokoban and Rush Hour use complete boards, while Minesweeper uses a Markov information state consisting of the revealed board and induced hidden-mine constraints.
Outcome-supervised RLVR and its bottleneck: Outcome-only RLVR assigns identical trajectory-level credit to every turn, creating the long-horizon credit-assignment bottleneck.The terminal reward remains the true optimization objective; solver signals are auxiliary supervision.
A per-step score from the solver: Solver cost-to-go N(s) measures work remaining to win, so a shifted advantage gives +1 for optimal progress, 0 for no progress, and negative credit for harmful moves.Transitions into unsolvable dead states receive the finite penalty −N(st).
Shaping the signal for training: CAST applies asinh compression and batch RMS normalization, then adds the shaped solver signal to GRPO’s terminal outcome advantage at each turn.The transformations compress rare large dead-state penalties, align scales across games, and preserve zero as the meaning of no progress.
Equivalence to logit-free OPD: Under a soft-optimal solver, CAST’s policy-gradient update implicitly maximizes task return while minimizing cross-entropy to the solver, matching OPD without teacher logits.The identity AπSolver = τ log πSolver means one scalar action score encodes the teacher’s log-preference.

3 EXPERIMENTS

Experiments evaluate CAST on three procedurally generated games, compare it with trained and training-free baselines, and test generalization, efficiency, and design choices. CAST improves in-domain and unseen-difficulty performance, transfers to ALFWorld and WebShop, and adds limited pipeline overhead.

Datasets and benchmarks: CAST trains and evaluates on Sokoban, Minesweeper, and Rush Hour, spanning long-horizon planning, partial-observation inference, and constrained combinatorial search.Instances are procedurally generated across game-specific difficulty levels.
Training-free comparisons: 62.1 ID and 28.4 Unseen-Difficulty are CAST’s game-averaged Avg@4 scores, versus 16.6 and 5.9 for the frozen ReAct base policy.Training also exceeds ReAct scores from Gemini-2.5-Flash (58.7) and Claude-Sonnet-4.5 (50.4) on ID.
Controlled comparisons: Adding solver advantages lifts DAPO’s average from 44.7 to 62.1 on ID and from 18.7 to 28.4 on Unseen-Difficulty, while CAST leads every game in both settings.CAST also leads the outcome-only GRPO baseline, which scores 44.9 ID and 19.2 Unseen.
Training dynamics: 1.7–2.0× speedup results from CAST reaching DAPO’s peak validation Avg@4 after 120, 200, and 140 steps, versus DAPO’s 200, 400, and 240 steps.The games are Sokoban, Minesweeper, and Rush Hour, respectively.
OOD transfer: 37.9 on ALFWorld and 22.7 on WebShop are CAST’s highest domain averages, while its Overall score of 30.3 exceeds the second-best method by 5.6 points.These evaluations are zero-shot and use no further fine-tuning.
Practicality: 8.4% of an environment step is attributed to solver queries, but environment interaction occupies only 0.1% of trajectory runtime while LLM generation occupies 99.9%.CAST forms its process signal with one solver query per environment step.

4 CONCLUSION … B DATASETS AND BENCHMARKS

CAST addresses sparse turn-level credit assignment in RLVR by converting solver state-value changes into fine-grained solver advantages. The paper situates this approach among interactive game agents, process-signal methods, and logit-free solver distillation.

4 CONCLUSION: CAST converts per-action changes in a game solver’s state value into turn-level solver advantages for LLM agents trained with RLVR.The method queries a solver on LLM-visited states to provide finer credit than sparse terminal rewards.
4 CONCLUSION: Under a soft-optimal solver assumption, CAST also has a logit-free on-policy distillation interpretation that does not require teacher logits.The solver-derived update uses scalar value information rather than teacher token distributions or log probabilities.
A RELATED WORK: Recent game-agent research equips LLMs or VLMs with memory, planning, reflection, and coordination for interactive play, often without updating model weights.The related work covers open-world exploration, general computer and video-game control, and reflective or multi-agent settings.
A RELATED WORK: Recent agentic-RL methods construct process signals below the trajectory level, including segment-, turn-, and token-level credit.Some approaches redistribute outcome information through grouping or decomposition and combine trajectory-level advantages with step-level comparisons over recurring or comparable states.
A RELATED WORK: Recent on-policy distillation methods learn from student-generated outputs but assume access to teacher token distributions or log probabilities.CAST differs by using solver-derived structured signals rather than requiring those teacher outputs.
A RELATED WORK: Classical solvers provide structured signals such as actions, feasibility, and cost-to-go values, linking solver-based learning to traditional imitation learning and search.This establishes the broader methodological context for CAST’s use of solver information.

B.1 DATASET DETAILS

The paper procedurally generates solvable game instances with controllable, game-specific difficulty, training on one in-domain tier and evaluating on both that tier and a harder unseen tier.

Data generation: Procedural generation controls difficulty while ensuring Sokoban layouts are solvable and Minesweeper boards begin with a fixed revealed safe-zone click.Sokoban uses reverse-playing search after random wall placement; Minesweeper places mines uniformly outside a 3×3 safe zone around the designated first-click cell.
Difficulty and splits: Difficulty varies by board size and game-specific counts: boxes in Sokoban, mines in Minesweeper, and total vehicles in Rush Hour.For Rush Hour, the vehicle count includes target vehicle A.
Difficulty and splits: Agents train only on a single in-domain tier and are evaluated on that tier plus a harder unseen-difficulty tier, with 200 evaluation instances per tier.The unseen tier increases the game-specific count and, for Sokoban and Minesweeper, enlarges the board; instances use independent random seeds.

B.2 OOD TRANSFER BENCHMARK DETAILS

The OOD transfer benchmark evaluates agents trained on three games zero-shot on ALFWorld and WebShop, using the same multi-turn, single-action interaction loop without further training. ALFWorld uses six standard TextWorld task types, while WebShop uses 500 test instructions with a 30-turn episode cap.

Cross-domain transfer: Agents trained on the three games are evaluated zero-shot on ALFWorld and WebShop without further training.Both benchmarks retain the games’ multi-turn loop and single-action interface, while changing observations and action spaces.
ALFWorld: ALFWorld evaluates instruction-following in a text-rendered household environment across six standard TextWorld task types.Each turn provides the current observation and admissible commands, and evaluation uses the seen validation split.
WebShop: WebShop evaluates shopping-instruction fulfillment on 500 standard test instructions, with each episode capped at 30 turns.Agents search, browse, and purchase products through page observations and actions such as search[query] and click[button].
Evaluation configuration: Both benchmarks use the games’ open-source decoding configuration with temperature 0.6, top-p 0.95, and four rollouts per instance.The configuration also allows up to 16,384 tokens per turn and 2,048 prompt tokens using SGLang serving.

B.3 OOD TRANSFER CASE STUDY · C IMPLEMENTATION DETAILS AND HYPERPARAMETERS

The OOD transfer case study shows that Sokoban-trained CAST behavior transfers zero-shot to WebShop, where the model recovers from a bad candidate, checks constraints, and earns the correct reward. The base model instead settles for an invalid item and receives no reward.

B.3 OOD TRANSFER CASE STUDY: The base model chooses a brown solid-wood table, refuses to search again, and commits an irreversible purchase that cannot satisfy the walnut requirement.It over-applies a prompt tip and buys the wrong item, yielding reward 0.0.
B.3 OOD TRANSFER CASE STUDY: The contrast demonstrates recovery from an intermediate mistake and constraint checking before commitment, behaviors consistent with planning discipline learned in Sokoban.Every action is retained, while some reasoning is omitted and marked “[...]”.
B.3 OOD TRANSFER CASE STUDY: 6 steps – reward 1.0 for CAST (Sokoban-trained, zero-shot), versus 3 steps – reward 0.0 for the base model (untrained).The CAST-trained model completes the WebShop instruction successfully, while the base model buys a wrong item.
B.3 OOD TRANSFER CASE STUDY: CAST rejects the black, metal-frame candidate because it fails the color requirement and uses a second search to recover rather than settling.It refines the query to “sofa tables walnut solid wood.”
B.3 OOD TRANSFER CASE STUDY: CAST identifies a $237 solid-wood option under the $260 constraint and proceeds with it as the best available choice.The Baja Night Stand appears near the top after the refined search and is suitable for living room use.
B.3 OOD TRANSFER CASE STUDY: CAST inspects the product page’s brown, grey, walnut, and white selector and chooses walnut before buying.Selecting the required attribute is the action that enables the purchase to register as a perfect match.

C.1 AGENT IMPLEMENTATION … C.4 LEARNED VALUE NETWORK AS A SOLVER

The paper uses a shared turn-based agent scaffold across three games, with game-specific observations, action interfaces, termination rules, and sparse success rewards. Solver-derived costs provide turn-level advantages, while Rush Hour additionally tests replacing exact solver values with a learned value network.

C.1 AGENT IMPLEMENTATION: A shared scaffold appends each board observation to the context, asks the policy to reason and commit one parsed action, and repeats until termination or the turn budget.The full history, including prior reasoning, observations, responses, actions, and the terminal reward, forms the rollout optimized by RL objectives.
C.1 AGENT IMPLEMENTATION: Invalid or illegal actions leave the state unchanged, consume one turn, and return corrective feedback; reward 1 is given only when the game is solved.Episodes otherwise end on game-specific failures or exhausted turn budgets.
C.2 ENVIRONMENT IMPLEMENTATION: The environments share an interface but differ in state encoding, action semantics, and termination rules, while all provide a sparse terminal reward of 1 on success and 0 otherwise.Sokoban and Rush Hour use symbolic grids with coordinate listings, whereas Minesweeper uses indexed rows and columns.
C.3 SOLVER IMPLEMENTATION: Solver costs define Φ(s) = −N(s) and the oracle advantage A(s_t, a_t) = N(s_t) − N(s_t+1), yielding positive, zero, or negative signals for optimal, wasteful, or harmful moves in shortest-path domains.The solver is queried on states visited along each rollout.
C.3 SOLVER IMPLEMENTATION: Minesweeper uses a deterministic peek-free solver whose completion cost K(s) counts reveals needed to clear safe cells, or +∞ when its rollout fails.Constraint reasoning and global mine probabilities are used despite partial observability; fixed latent layouts and first-click reveals make K(s) deterministic for an instance.
C.3 SOLVER IMPLEMENTATION: Rush Hour training uses exact shortest-path lookups over reachable components within a state cap, falling back to bounded IDA∗ for larger components.Data-generation validation uses a separate bounded IDA∗ solver, and one slide of any distance counts as one move.
C.4 LEARNED VALUE NETWORK AS A SOLVER: A masked Double DQN value network replaces the exact Rush Hour solver by encoding the 6×6 board, outputting action Q-values, masking illegal actions, and setting V(s) = max_a∈A(s) Q(s,a).Its backend returns the cost surrogate bN(s) = −scale · V(s), producing advantages from successive value differences; training uses terminal-reward pretraining followed by two potential-regression stages.

C.5 EQUIVALENCE TO CROSS-ENTROPY DISTILLATION … C.5.3 LEMMAS

The section formalizes CAST’s solver-shaped update as task-return optimization regularized by student–solver cross-entropy under four assumptions. Its lemmas show that solver advantages become teacher log-preferences, reducing the shaped signal to a scaled log-probability term.

C.5 EQUIVALENCE TO CROSS-ENTROPY DISTILLATION: The solver-shaped GRPO objective is formalized as task return regularized by cross-entropy between the student and solver.The section further decomposes this cross-entropy into a KL-divergence penalty and entropy reduction, and derives the closed-form optimal policy.
C.5 EQUIVALENCE TO CROSS-ENTROPY DISTILLATION: The analysis extends beyond the small-signal regime and provides a performance-improvement guarantee through the Performance Difference Lemma.
C.5.1 NOTATION: The notation models a finite-horizon undiscounted MDP with student policy πθ, solver policy πSolver, and the student’s unnormalized state-occupancy measure.The section defines task value, action-value, advantage, and information-theoretic quantities used in the distillation analysis.
C.5.1 NOTATION: Cross-entropy from πθ to πSolver equals the sum of KL divergence and the entropy of πθ.The policy-gradient derivation also uses baseline invariance for action-independent state functions.
C.5.2 ASSUMPTIONS: The assumptions require a soft-optimal solver, small solver advantages, GRPO consistency with task advantage, and a frozen state-visitation surrogate.The small-signal condition is |AπSolver| ≲1, while the shaping contribution is evaluated with dπθ fixed at the current iterate.
C.5.3 LEMMAS: Under a soft-optimal solver, the solver advantage satisfies 1/τ AπSolver(s, a) = log πSolver(a|s) up to the stated identity.Thus, action advantage and teacher log-preference encode the same signal up to temperature τ.
C.5.3 LEMMAS: Under the soft-optimal and small-signal assumptions, the shaped solver term reduces to a scaled teacher log-probability plus action-independent constants.The derivation Taylor-expands asinh(AπSolver + 1) around the optimal-move point, while batch-level normalization contributes only a constant coefficient.

C.5.4 MAIN THEOREM

Under Assumptions C.1–C.4, CAST’s policy-gradient update equals the gradient of an implicit objective combining task-return optimization with solver-guided cross-entropy. This shaping is equivalent to reverse-KL, mode-seeking distillation toward the solver, with an additional entropy term relative to standard KL regularization.

Main theorem: Under Assumptions C.1–C.4, CAST’s training-rule update direction equals the gradient of its implicit objective.The theorem establishes this equivalence for Equation 8.
Proof: The policy gradient decomposes additively into the GRPO task-return gradient and the solver-shaping gradient.This follows from linearity in the advantage weight, with the combined update written as g_ours = g_GRPO + g_shape.
Proof: The shaping term is equivalent to minimizing cross-entropy H(πθ, πSolver), the standard objective for knowledge distillation.The solver contribution reduces to β log πSolver(a|s) plus an action-independent constant.
Interpretation: Minimizing this cross-entropy simultaneously minimizes KL(πθ∥πSolver) and H(πθ), producing mode-seeking behavior toward the solver’s preferred actions.The student concentrates probability on preferred solver actions rather than distributing mass across all modes.
Relation to KL-regularized objectives: CAST’s implicit objective contains an additional −βH relative to standard KL regularization because its advantage weight omits −log πθ.Using log(πSolver/πθ), or adding entropy bonus +βH, would recover the standard KL-regularized objective exactly.

C.5.5 COROLLARIES

The corollaries characterize KL-regularized distillation with a closed-form optimal policy and explain how task advantage can let the student surpass the solver. They also extend the result to full-domain asinh-robustification, using a step-varying gain that down-weights outlier steps.

Closed-Form Optimal Policy: The KL-regularized objective has a closed-form maximizing policy proportional to the solver distribution multiplied by an exponentiated task-advantage tilt.The second-order condition confirms this solution is a maximum.
Why the student can surpass the solver: At finite β, exp(Atask/β) lets the optimal policy deviate from the solver wherever task reward warrants it, enabling the student to surpass the teacher.As β →∞, the policy converges to the solver in the pure-distillation limit.
Cross-Entropy Limitation: Cross-entropy regularization alone has no interior simplex optimum, whereas the KL-regularized subproblem isolates a component with a well-defined closed-form solution.The implicit objective decomposes into a KL penalty and an entropy reduction.
Full-Domain Robustified Distillation: Full-domain robustified distillation replaces constant β with βeff, preserving Theorem 2.1 while automatically down-weighting outlier steps.The effective gain retains the asinh nonlinearity and becomes step-dependent.
Full-Domain Robustified Distillation: As AπSolver →0, βeff →β, recovering Theorem 2.1; for large |A|, βeff decreases because asinh grows logarithmically while A grows linearly.This compresses unusually large solver advantages, such as dead-state penalties.

C.5.6 PERFORMANCE IMPROVEMENT VIA THE PERFORMANCE DIFFERENCE LEMMA … C.6.1 TRAINING HYPERPARAMETERS

CAST’s solver-advantage reward admits a performance-improvement guarantee, with sub-optimality scaling as O(Hε_π) rather than O(H^2ε_π) under an approximate solver. The analysis also identifies assumptions behind the distillation interpretation and describes shared training configurations for the compared algorithms.

C.5.6 PERFORMANCE IMPROVEMENT VIA THE PERFORMANCE DIFFERENCE LEMMA: The solver advantage defines an augmented return whose maximization provably improves over the solver, with a sub-optimality bound linear rather than quadratic in horizon H.The bound scales linearly in H instead of quadratically.
C.5.6 PERFORMANCE IMPROVEMENT VIA THE PERFORMANCE DIFFERENCE LEMMA: Potential-based shaping with Φ(s) = V^πSolver(s) preserves the optimal policy ordering and policy gradient relative to the base signal τ log πSolver(a|s).The shaping term depends on consecutive states and changes neither the optimal policy nor the policy gradient, up to a state-dependent baseline.
C.5.6 PERFORMANCE IMPROVEMENT VIA THE PERFORMANCE DIFFERENCE LEMMA: In the per-step reward setting, action-quality information resides entirely in ˜r = τ log πSolver = A^πSolver, while the shaping potential contributes no policy-gradient information.For the solver’s constant step reward rS = −1, the endogenous reward reduces to rS after value-function terms telescope.
C.5.6 PERFORMANCE IMPROVEMENT VIA THE PERFORMANCE DIFFERENCE LEMMA: Whenever E_πθ[A^πSolver raug(s, ·)] ≥ 0 at every state, the student’s augmented value satisfies V^πθ raug ≥ V^πSolver raug.The guarantee applies the Performance Difference Lemma with π = πθ and π′ = πSolver under the augmented reward.
C.5.6 PERFORMANCE IMPROVEMENT VIA THE PERFORMANCE DIFFERENCE LEMMA: O(Hε_π) is the solver-distillation sub-optimality bound under an ε_π-approximate expert, improving over behavioral cloning’s O(H^2ε_π) bound.The approximation condition is max_s,a |log πSolver(a|s) − log π*(a|s)| ≤ ε_π.
C.5.7 DISCUSSION OF ASSUMPTIONS: The distillation interpretation assumes a soft-optimal solver, and deviations from optimality degrade that interpretation proportionally.The three game solvers are described as near-optimal, making the assumption well-justified for those experiments.
C.5.7 DISCUSSION OF ASSUMPTIONS: The analysis assumes mostly small solver advantages, unbiased GRPO gradient direction, and a frozen visitation surrogate consistent with PPO-style per-step weighting.For rare large-magnitude steps, βeff gives an exact characterization; GRPO affects variance, while freezing visitation omits ∇θd^πθ.
C.6.1 TRAINING HYPERPARAMETERS: GRPO, DAPO, and GSPO share the backbone model, training data, rollout budget, and optimizer, differing only in policy-optimization objective; CAST uses DAPO.GiGPO is a separate process-level baseline, with shared settings listed in Table 5 and objective-specific settings in Table 6.

C.6.2 EVALUATION SETTINGS

The evaluation uses a unified multi-turn protocol with sparse solved/unsolved rewards across in-domain and harder unseen-difficulty tiers. Open-source and closed-source models follow matched interaction and scoring procedures, with distinct decoding and rollout settings.

Evaluation protocol: Each instance uses the training-time multi-turn agent loop and receives a sparse 0/1 reward, counting as solved only when the goal is reached within the per-game turn budget.Each game and tier is evaluated on its 200-instance test split.
Evaluation protocol: Both in-domain and harder unseen-difficulty tiers are evaluated for all three games under the same protocol.The tiers correspond to Table 3, with 200 test instances per tier and game.
Closed-source models: Six proprietary models are evaluated through an OpenAI-compatible API with temperature 1.0, top-p 1.0, and 4 rollouts per instance.They use the same interaction protocol, turn budgets, 0/1 scoring, episode response budget, and initial-prompt setting as the open-source evaluation.