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

CAST, from researchers at the University of Science and Technology of China, Nanjing University, Wuhan University, and Meituan, addresses sparse credit assignment when training LLM agents with reinforcement learning from verifiable rewards. Instead of giving every turn the same win-or-loss signal, it queries a game solver for each LLM action, measures the change in cost-to-go, and adds this shifted solver advantage to DAPO-style GRPO training. An asinh transformation compresses harmful outliers, while batch-level RMS normalization stabilizes scales across Sokoban, Minesweeper, and Rush Hour. The authors theoretically show that, under a soft-optimal solver assumption, this scalar advantage performs logit-free on-policy distillation: it encodes the teacher’s action preference without requiring teacher logits. Using Qwen3-4B-Instruct-2507, CAST raises the trained-baseline in-domain average from 44.7 to 62.1 and the unseen-difficulty average from 18.7 to 28.4, outperforming GRPO, GSPO, DAPO, and GiGPO on every game. It reaches DAPO’s peak validation performance with a 1.7–2.0× training speedup, and transfers zero-shot to ALFWorld and WebShop with an overall score of 30.3. For context, this surpasses the prompting averages of Gemini-2.5-Flash and Claude-Sonnet-4.5 on the in-domain games. Solver queries contribute only 73 ppm of total training-step time, and a learned DQN value network retains much of the benefit of exact solver guidance.