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

# CAST: Game Solvers as Turn-Level Teachers for LLM Agents
Source: [https://arxiv.org/html/2607.25308](https://arxiv.org/html/2607.25308)
Yu Wang1,4\*, Yi\-Kai Zhang2,4\*, Wentao Shi1, Ziang Ye1,4, Yuchun Miao3,4, Yueqing Sun4 Qi Gu4, Xunliang Cai4, Lan\-Zhe Guo2, Han\-Jia Ye2, Fuli Feng1 1University of Science and Technology of China2Nanjing University3Wuhan University 4Meituan, China

###### Abstract

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 proposeCAST\(CreditAssignment fromSolverTeachers\), 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[github\.com/Wloner0809/CAST](https://github.com/Wloner0809/CAST)\.

\*\*footnotetext:Equal contribution\.\\raisebox\{0\.4pt\}\{\\faIcon\[regular\]\{envelope\}\}\\raisebox\{0\.4pt\}\{\\faIcon\[regular\]\{envelope\}\}footnotetext:Corresponding authors:guqi03@meituan\.comandshiwentao123@mail\.ustc\.edu\.cn\.## 1Introduction

As large language models \(LLMs\) and multimodal foundation models\(Yanget al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib36); Teamet al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib43)\)move from passive generation toward active decision\-making, a central goal is to build generalist agents that can make decisions in embodied and open\-world environments\(Intelligenceet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib44)\)\. Such agents need to act in evolving states, where the effects of early decisions may emerge only later and are often difficult to reverse\(Yeet al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib59)\)\. These settings require a broad range of capabilities, including long\-horizon planning, goal\-directed exploration, and recovery from mistakes\. Classical games such as Sokoban and Minesweeper offer an ideal testbed for these capabilities\(Junghanns and Schaeffer,[2001](https://arxiv.org/html/2607.25308#bib.bib46); Mnihet al\.,[2015](https://arxiv.org/html/2607.25308#bib.bib45); Huet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib11)\), with well\-defined rules, verifiable feedback, and scalable decision\-making environments\. In fact, such games can already be solved efficiently by domain\-specific solvers, ranging from heuristic search and dynamic programming to specialized DQN value networks\(Mnihet al\.,[2013](https://arxiv.org/html/2607.25308#bib.bib47)\)\. General\-purpose LLMs, by contrast, remain unreliable even in these structured environments, as shown in[Figure 1](https://arxiv.org/html/2607.25308#S1.F1)\(left\)\. Games therefore provide a bridge for studying how a general\-purpose LLM can become a reliable interactive agent\(Ouyanget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib13); Paglieriet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib10)\)\.

A central bottleneck in training generalist LLM game agents is the lack of scalable, fine\-grained learning signals\. Reinforcement Learning with Verifiable Rewards \(RLVR\) has been effective in single\-turn tasks\(Zhanget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib48);[Chenet al\.,](https://arxiv.org/html/2607.25308#bib.bib49); Guoet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib50)\), but in games, final rewards are often too sparse\. As illustrated in[Figure 1](https://arxiv.org/html/2607.25308#S1.F1)\(right\), such outcome signals cannot reveal which decisions in a trajectory cause the final win or loss, creating a fundamental credit\-assignment challenge\. To address this challenge, existing approaches obtain denser process signals through costly search\(Haoet al\.,[2023](https://arxiv.org/html/2607.25308#bib.bib24)\), learned process reward models\(Xiet al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib22)\), or cross\-trajectory comparisons such as GiGPO\(Fenget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib4)\), yet still face trade\-offs among computation, supervision, and signal reliability\. We observe that game solvers can provide this missing signal, as a solver can evaluate an action from the state at which it was taken\. SFT on solver\-generated expert trajectories, however, does not fully exploit this capability: it exposes the LLM only to expert\-visited states and offers little guidance once the model deviates during interaction\. This motivates an on\-policy RL paradigm in which the LLM explores under its own policy and the solver acts as a*turn\-level teacher*\.

Aligning the model’s on\-policy exploration with immediate solver feedback is, in essence, a form of on\-policy distillation \(OPD\)\. Existing LLM distillation methods\(Lu and Lab,[2025](https://arxiv.org/html/2607.25308#bib.bib29); Guet al\.,[2024](https://arxiv.org/html/2607.25308#bib.bib28)\), however, typically rely on teacher logits over the full token space, whereas classical solvers return only an optimal action or a scalar cost\-to\-go, not such a distribution\. We therefore proposeCAST\(CreditAssignment fromSolverTeachers\), a distillation strategy built directly on solvers\. Since a solver can complete a game from an intermediate state, it assigns every state astate value: how close that state is to winning\. For each action sampled by the LLM, CAST compares the solver values immediately before and after the action to obtain a solver advantage, and injects it into RLVR as turn\-level signals\. This converts the outcome reward into process supervision indicating whether the current action moves the state closer to success, at negligible training overhead\. Our theoretical analysis shows that, for a sufficiently strong solver, an action’s log\-probability under the solver’s implicit action distribution is strictly proportional to its one\-step change in state value\. Consequently, increasing the likelihood of actions with larger solver advantages is mathematically equivalent to on\-policy distillation that aligns the LLM’s action distribution with the solver’s\. This equivalence resolves the obstacle above: the scalar advantage already carries the teacher’s action preference, so a single scalar suffices for distillation without the teacher’s full action distribution, yielding an efficient logit\-free distillation\.

![Refer to caption](https://arxiv.org/html/2607.25308v1/x1.png)Figure 1:Overview\.\(Left\)Several current closed\-source LLMs struggle on classical games\.\(Right\)Outcome\-only RLVR lacks fine\-grained feedback, whereas our solver\-derived signal provides accurate turn\-level credit\.In practice, the absolute scale of solver signals varies across games and often contains extreme values that destabilize training\. We address this with two lightweight shaping steps\. First, anasinhtransformation smoothly compresses extreme values while preserving resolution in the small\-signal regime; a theoretical analysis shows this amounts to a robustified KL constraint\. Second, batch\-level root\-mean\-square \(RMS\) normalization removes cross\-domain scale differences\. These let the solver advantage serve as a stable, comparable process signal that integrates seamlessly into RLVR\.

We evaluate CAST on Sokoban, Minesweeper, and Rush Hour, which span complementary challenges in long\-horizon planning, partial\-observation inference, and constrained combinatorial search\. CAST achieves the best performance among all trained methods across every game under both in\-domain and unseen\-difficulty settings, consistently outperforming outcome\-only RLVR baselines and the process\-level baseline GiGPO\(Fenget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib4)\)\. It also reaches DAPO’s\(Yuet al\.,[2026a](https://arxiv.org/html/2607.25308#bib.bib2)\)peak validation performance in substantially fewer training steps and transfers zero\-shot to held\-out ALFWorld\([Shridharet al\.,](https://arxiv.org/html/2607.25308#bib.bib34)\)and WebShop\(Yaoet al\.,[2022](https://arxiv.org/html/2607.25308#bib.bib35)\)domains without further fine\-tuning\. Ablations validate the solver\-advantage weighting and signal transformations; further analyses show negligible solver overhead and that a learned value network retains much of the benefit of exact solver guidance\.

In summary, our contributions are as follows:

- •Solver\-derived credit\.We cast game solvers as turn\-level teachers and define a solver advantage that assigns fine\-grained credit to LLM\-sampled actions in RLVR\.
- •Logit\-free distillation\.We prove that maximizing this advantage is equivalent to on\-policy distillation, giving a distillation objective needing no teacher logits, and stabilize it withasinhcompression and batch\-level RMS normalization\.
- •Performance and generalization\.CAST reaches state\-of\-the\-art results on all three games in\-domain and at unseen difficulties, improves sample efficiency, and transfers zero\-shot to ALFWorld and WebShop\.
- •Practicality\.An exact solver adds negligible overhead, and a learned value network provides comparable performance when no exact solver exists\.

## 2Method

Our method lets a game\-specific solver act as a turn\-level teacher that scores each action the LLM takes, refining the sparse terminal reward into a dense per\-step process signal\.[Subsection 2\.1](https://arxiv.org/html/2607.25308#S2.SS1)formalizes games as reinforcement learning problems and identifies why outcome\-only RLVR is limited\.[Subsection 2\.2](https://arxiv.org/html/2607.25308#S2.SS2)introduces the solver teacher, constructs its per\-step score, gives the full pipeline that makes it stable and integrates it into training, and finally explains why this score is equivalent to on\-policy distillation \(OPD,[Theorem 2\.1](https://arxiv.org/html/2607.25308#S2.Thmtheorem1)\)\.

### 2\.1Preliminaries

##### Games as multi\-turn MDPs\.

We formulate each game as a finite\-horizon Markov decision process \(MDP\)ℳ=\(𝒮,𝒜,P,r,H\)\\mathcal\{M\}=\(\\mathcal\{S\},\\mathcal\{A\},P,r,H\)with horizonHH\. At turntt, the LLM policyπθ\\pi\_\{\\theta\}observes a textual rendering of the statest∈𝒮s\_\{t\}\\in\\mathcal\{S\}, samples an actionat∼πθ\(⋅∣st\)a\_\{t\}\\sim\\pi\_\{\\theta\}\(\\cdot\\mid s\_\{t\}\), and the environment transitions viaP​\(st\+1∣st,at\)P\(s\_\{t\+1\}\\mid s\_\{t\},a\_\{t\}\)until the episode terminates at some stepT≤HT\\leq H, yielding a trajectoryτ=\(s0,a0,…,sT\)\\tau=\(s\_\{0\},a\_\{0\},\\ldots,s\_\{T\}\)\. For Sokoban and Rush Hour,sts\_\{t\}is the complete board; for Minesweeper,sts\_\{t\}is the*information state*\(the revealed board plus the constraints it induces on hidden mines\), which is a sufficient statistic that keeps the process Markov\. The reward is sparse and verifiable:

rt=0\(t<T\),R​\(τ\)=rT=𝟏​\{sT∈𝒮solved\}\.r\_\{t\}=0\\quad\(t<T\),\\qquad R\(\\tau\)=r\_\{T\}=\\mathbf\{1\}\\\{s\_\{T\}\\in\\mathcal\{S\}\_\{\\text\{solved\}\}\\\}\.\(1\)This0/10/1terminal reward is the true optimization objective throughout the paper; every solver signal introduced later is auxiliary supervision and does not change what counts as winning\.

##### Outcome\-supervised RLVR and its bottleneck\.

RLVR maximizes the expected returnJ​\(θ\)=𝔼τ∼πθ​\[R​\(τ\)\]J\(\\theta\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\_\{\\theta\}\}\[R\(\\tau\)\]via policy gradients\(Suttonet al\.,[1999](https://arxiv.org/html/2607.25308#bib.bib54)\)\. To avoid a learned critic, GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.25308#bib.bib1)\)samples a group ofGGtrajectories fromπθold\\pi\_\{\\theta\_\{\\text\{old\}\}\}for a promptqqand normalizes their returns into a trajectory\-level advantage,

A^ioutcome=Ri−μRσR\+δ,μR=1G​∑j=1GRj,σR=1G​∑j=1G\(Rj−μR\)2,\\hat\{A\}^\{\\text\{outcome\}\}\_\{i\}=\\frac\{R\_\{i\}\-\\mu\_\{R\}\}\{\\sigma\_\{R\}\+\\delta\},\\qquad\\mu\_\{R\}=\\frac\{1\}\{G\}\\sum\_\{j=1\}^\{G\}R\_\{j\},\\quad\\sigma\_\{R\}=\\sqrt\{\\frac\{1\}\{G\}\\sum\_\{j=1\}^\{G\}\(R\_\{j\}\-\\mu\_\{R\}\)^\{2\}\},\(2\)with a small constantδ\>0\\delta\>0for numerical stability\. This trajectory\-level scalar is assigned to every token of the trajectory and optimized through a clipped surrogate objective, where the importance\-sampling ratioρt\\rho\_\{t\}betweenπθ\\pi\_\{\\theta\}andπθold\\pi\_\{\\theta\_\{\\text\{old\}\}\}is clipped to\[1−ϵ,1\+ϵ\]\[1\{\-\}\\epsilon,1\{\+\}\\epsilon\]:

𝒥GRPO​\(θ\)=𝔼q,\{oi\}∼πθold​\[1G​∑i=1G1\|oi\|​∑t=1\|oi\|\(min⁡\(ρt​A^i,clip⁡\(ρt,1−ϵ,1\+ϵ\)​A^i\)−βkl​DKL​\[πθ∥πref\]\)\]\.\\mathcal\{J\}\_\{\\mathrm\{GRPO\}\}\(\\theta\)=\\mathbb\{E\}\_\{q,\\,\\\{o\_\{i\}\\\}\\sim\\pi\_\{\\theta\_\{\\text\{old\}\}\}\}\\\!\\Bigg\[\\frac\{1\}\{G\}\\sum\_\{i=1\}^\{G\}\\frac\{1\}\{\|o\_\{i\}\|\}\\sum\_\{t=1\}^\{\|o\_\{i\}\|\}\\Big\(\\min\\\!\\big\(\\rho\_\{t\}\\,\\hat\{A\}\_\{i\},\\,\\operatorname\{clip\}\(\\rho\_\{t\},1\{\-\}\\epsilon,1\{\+\}\\epsilon\)\\,\\hat\{A\}\_\{i\}\\big\)\-\\beta\_\{\\text\{kl\}\}\\,D\_\{\\mathrm\{KL\}\}\\\!\\big\[\\pi\_\{\\theta\}\\,\\\|\\,\\pi\_\{\\text\{ref\}\}\\big\]\\Big\)\\Bigg\]\.\(3\)The bottleneck is now explicit: becauseA^i=A^ioutcome\\hat\{A\}\_\{i\}=\\hat\{A\}^\{\\text\{outcome\}\}\_\{i\}is computed solely from the terminal outcome, every turn in a trajectory receives the same credit\. This coarse trajectory\-level credit is the root of the credit\-assignment failure in long\-horizon games, motivating the turn\-level solver signal introduced next\.

### 2\.2Solver\-Guided Turn\-Level Credit

![Refer to caption](https://arxiv.org/html/2607.25308v1/x2.png)Figure 2:Method overview\.We augment GRPO’s outcome advantage with a shifted solver advantage derived from turn\-level cost\-to\-go changes\.##### A per\-step score from the solver\.

To score each action individually, we need a way to measure how good the current state is\. The0/10/1terminal reward cannot do this, as it only takes a value at the very end\. A solver can, because it completes a game from any state\. This property equips any solver with a general\-purpose measure that we call the*cost\-to\-go*N​\(s\)N\(s\): the minimum amount of work needed to reach a win from statess\. Its exact unit varies by game, but the meaning of “how far from the goal” is universal: for Sokoban and Rush Hour,N​\(s\)N\(s\)is the minimum number of actions to solve the board, and for Minesweeper it is the minimum number of reveals needed to clear all safe cells\.

A natural per\-step score isN​\(st\)−N​\(st\+1\)N\(s\_\{t\}\)\-N\(s\_\{t\+1\}\), the drop in cost\-to\-go caused by the move\. We ground this score in RL by defining an auxiliary shortest\-path objective \(−1\-1per action, terminal value0\) and settingVπSolver​\(s\)=−N​\(s\)V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\)=\-N\(s\), which makes states closer to the goal more valuable\.

QπSolver​\(st,at\)\\displaystyle Q^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\},a\_\{t\}\)=−1\+𝔼st\+1​\[VπSolver​\(st\+1\)\],and​VπSolver​\(st\)=−N​\(st\)\\displaystyle=\-1\+\\mathbb\{E\}\_\{s\_\{t\+1\}\}\[V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\+1\}\)\],\\,\\,\\text\{and\}\\,V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\}\)=\-N\(s\_\{t\}\)\(4\)AπSolver​\(st,at\)\\displaystyle A^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\},a\_\{t\}\)=−1\+N​\(st\)−𝔼st\+1​\[N​\(st\+1\)\]\.\\displaystyle=\-1\+N\(s\_\{t\}\)\-\\mathbb\{E\}\_\{s\_\{t\+1\}\}\[N\(s\_\{t\+1\}\)\]\.The advantageA=Q−VA=Q\-Vmeasures how much better a specific action is compared to the expected outcome under the solver’s policy\. The𝔼st\+1\\mathbb\{E\}\_\{s\_\{t\+1\}\}is over the environment transition; for the deterministic games studied here it reduces to the single resulting state, and we keep the expectation for generality\.

##### A shift so that progress maps to positive credit\.

Under the solver’s optimal policy, the expected next\-state cost𝔼st\+1​\[N​\(st\+1\)\]\\mathbb\{E\}\_\{s\_\{t\+1\}\}\[N\(s\_\{t\+1\}\)\]equalsN​\(st\)−1N\(s\_\{t\}\)\-1, because the solver always reduces the remaining steps by exactly one\. Substituting into[Equation 4](https://arxiv.org/html/2607.25308#S2.E4)givesAπSolver=−1\+\(N​\(st\)−\(N​\(st\)−1\)\)=0A^\{\\pi\_\{\\text\{Solver\}\}\}=\-1\+\(N\(s\_\{t\}\)\-\(N\(s\_\{t\}\)\-1\)\)=0: an optimal action has zero advantage, and any suboptimal action that fails to reduce the cost\-to\-go by a full step scores negative\. This makes the raw advantage non\-positive, which is inconvenient as a signal\. Shifting by\+1\+1gives the*shifted solver advantage*,

A~πSolver​\(st,at\)=AπSolver​\(st,at\)\+1=N​\(st\)−𝔼st\+1​\[N​\(st\+1\)\],\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\},a\_\{t\}\)=A^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\},a\_\{t\}\)\+1=N\(s\_\{t\}\)\-\\mathbb\{E\}\_\{s\_\{t\+1\}\}\[N\(s\_\{t\+1\}\)\],\(5\)which equals the drop in cost\-to\-go caused by the move\. Its meaning is direct: an optimal move that advances one step receives\+1\+1, a move with no progress receives0, and a harmful move receives negative credit\. The one special case is a transition into an unsolvable dead state, whereN​\(st\+1\)=∞N\(s\_\{t\+1\}\)=\\infty; we cap such a transition at the finite penalty−N​\(st\)\-N\(s\_\{t\}\), counting it as losing theN​\(st\)N\(s\_\{t\}\)steps that would otherwise have won the game\.

##### Shaping the signal for training\.

The shifted advantage is clean in theory but problematic if used directly\. First, it is heavy\-tailed: most moves change the cost\-to\-go by only0or±1\\pm 1, but the dead\-state penalty−N​\(st\)\-N\(s\_\{t\}\)can be large, and a few such extremes would dominate the gradient\. Second, its scale varies across games, as a hard board has a cost\-to\-go of dozens while an easy one has only a few\. We address both with two lightweight transformations\. First, anasinhcompression,

g​\(x\)=asinh⁡\(x\)=ln⁡\(x\+x2\+1\),g\(x\)=\\operatorname\{asinh\}\(x\)=\\ln\\\!\\big\(x\+\\sqrt\{x^\{2\}\+1\}\\,\\big\),\(6\)which is near\-linear for smallxx, so common small\-progress values are preserved and remain distinguishable, and grows only logarithmically for large\|x\|\|x\|, so rare dead\-state penalties are compressed\. We useasinhrather than a plain logarithm because it is defined and odd\-symmetric across negative, zero, and positive values, fully preserving the sign that encodes beneficial, neutral, and harmful moves\. Second, batch\-level RMS normalization rescales the signal by its root\-mean\-square magnitude over all turns in the batch,

h​\(x\)=g​\(x\)RMSℬ​\(g\)\+ϵ,RMSℬ​\(g\)=1\|ℬ\|​∑\(i,t\)∈ℬg​\(A~πSolver​\(si,t,ai,t\)\)2,h\(x\)=\\frac\{g\(x\)\}\{\\mathrm\{RMS\}\_\{\\mathcal\{B\}\}\(g\)\+\\epsilon\},\\qquad\\mathrm\{RMS\}\_\{\\mathcal\{B\}\}\(g\)=\\sqrt\{\\tfrac\{1\}\{\|\\mathcal\{B\}\|\}\\textstyle\\sum\_\{\(i,t\)\\in\\mathcal\{B\}\}g\\\!\\left\(\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{i,t\},a\_\{i,t\}\)\\right\)^\{2\}\},\(7\)whereℬ\\mathcal\{B\}contains all turns in the batch, placing the signal on a consistent scale across games\. We divide by the RMS*without*subtracting the mean, which is deliberate: the value0should keep meaning “no progress” so that positive stays beneficial and negative stays harmful; subtracting the mean would shift this zero point and destroy the sign information on which the signal relies\.

##### Combining with GRPO\.

We combine this per\-step process signal with the terminal reward, so as to keep the true objective of winning while adding fine\-grained per\-step credit \([Figure 2](https://arxiv.org/html/2607.25308#S2.F2)\)\. For trajectoryiiat turntt, we writeA~i,tπSolver≜A~πSolver​\(si,t,ai,t\)\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\_\{i,t\}\\triangleq\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{i,t\},a\_\{i,t\}\)for the shifted solver advantage evaluated at that trajectory’s state\-action pair\. We add the shaped solver signal to GRPO’s outcome advantage and broadcast the result to every token of the turn,

A^i,t=A^ioutcome\+α​h​\(A~i,tπSolver\),\\hat\{A\}\_\{i,t\}=\\hat\{A\}^\{\\text\{outcome\}\}\_\{i\}\+\\alpha\\,h\\\!\\left\(\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\_\{i,t\}\\right\),\(8\)with a single coefficientα\\alphacontrolling the strength of solver guidance\. Three granularities meet here:A^ioutcome\\hat\{A\}^\{\\text\{outcome\}\}\_\{i\}is trajectory\-level and identical across all turns of a trajectory, anchoring the global win\-or\-loss credit;h​\(A~i,tπSolver\)h\(\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\_\{i,t\}\)is turn\-level and varies step by step, refining credit within the trajectory; and their sum is broadcast to the token level, since GRPO optimizes over tokens\. The combined advantageA^i,t\\hat\{A\}\_\{i,t\}replacesA^ioutcome\\hat\{A\}^\{\\text\{outcome\}\}\_\{i\}in the clipped GRPO surrogate of[Equation 3](https://arxiv.org/html/2607.25308#S2.E3), so the terminal reward still anchors trajectory\-level credit while the solver signal refines it turn by turn\.

##### Equivalence to logit\-free OPD\.

Having presented the complete pipeline, we now show that the solver advantage is not merely a hand\-designed signal but is mathematically equivalent to distilling from the solver\. The key observation is that a sufficiently strong solver can be viewed as a*soft\-optimal*teacher policy whose action probabilities grow exponentially with the action value:πSolver​\(a∣s\)∝exp⁡\(QπSolver​\(s,a\)/τ\)\\pi\_\{\\text\{Solver\}\}\(a\\mid s\)\\propto\\exp\\\!\\big\(Q^\{\\pi\_\{\\text\{Solver\}\}\}\(s,a\)/\\tau\\big\)for a temperatureτ\>0\\tau\>0\(Ziebartet al\.,[2008](https://arxiv.org/html/2607.25308#bib.bib52); Haarnojaet al\.,[2018](https://arxiv.org/html/2607.25308#bib.bib51)\)\. Takinglog\\logimmediately givesAπSolver​\(s,a\)=τ​log⁡πSolver​\(a∣s\)A^\{\\pi\_\{\\text\{Solver\}\}\}\(s,a\)=\\tau\\,\\log\\pi\_\{\\text\{Solver\}\}\(a\\mid s\): the solver advantage is exactly the teacher’s log\-preference for the action\. We then obtain the following result \(proved in Appendix[C\.5](https://arxiv.org/html/2607.25308#A3.SS5)\):

###### Theorem 2\.1\(Implicit Objective of CAST\)\. Assume the solver is soft\-optimal with temperatureτ\>0\\tau\>0, the solver advantages satisfy\|AπSolver\|≲1\|A^\{\\pi\_\{\\text\{Solver\}\}\}\|\\lesssim 1, and GRPO provides an unbiased task\-return gradient under a frozen\-visitation surrogate\. Then the policy\-gradient update of the training rule[Equation 8](https://arxiv.org/html/2607.25308#S2.E8)equals the gradient of𝒥​\(θ\)=𝔼s0∼μ​\[Vtaskπθ​\(s0\)\]⏟task return−β​𝔼s∼dπθ\[H\(πθ\(⋅\|s\),πSolver\(⋅\|s\)\)\]⏟cross\-entropy distillation,β=α​τ2​\(RMSℬ​\(g\)\+ϵ\),\\mathcal\{J\}\(\\theta\)=\\underbrace\{\\mathbb\{E\}\_\{s\_\{0\}\\sim\\mu\}\\\!\\big\[V^\{\\pi\_\{\\theta\}\}\_\{\\text\{task\}\}\(s\_\{0\}\)\\big\]\}\_\{\\text\{task return\}\}\-\\;\\beta\\,\\underbrace\{\\mathbb\{E\}\_\{s\\sim d^\{\\pi\_\{\\theta\}\}\}\\\!\\Big\[\\mathrm\{H\}\\\!\\big\(\\pi\_\{\\theta\}\(\\cdot\|s\),\\,\\pi\_\{\\text\{Solver\}\}\(\\cdot\|s\)\\big\)\\Big\]\}\_\{\\text\{cross\-entropy distillation\}\},\\,\\,\\,\\beta=\\frac\{\\alpha\\,\\tau\}\{\\sqrt\{2\}\\,\(\\mathrm\{RMS\}\_\{\\mathcal\{B\}\}\(g\)\+\\epsilon\)\}\\,,\(9\)whereH​\(πθ,πSolver\)=−𝔼a∼πθ​\[log⁡πSolver​\(a∣s\)\]\\mathrm\{H\}\(\\pi\_\{\\theta\},\\pi\_\{\\text\{Solver\}\}\)=\-\\mathbb\{E\}\_\{a\\sim\\pi\_\{\\theta\}\}\[\\log\\pi\_\{\\text\{Solver\}\}\(a\\mid s\)\]is the cross\-entropy fromπθ\\pi\_\{\\theta\}toπSolver\\pi\_\{\\text\{Solver\}\}, anddπθ​\(s\)d^\{\\pi\_\{\\theta\}\}\(s\)is the expected number of times statessis visited during an episode\.

The theorem reveals that our method implicitly maximizes the task return while minimizing the cross\-entropy fromπθ\\pi\_\{\\theta\}toπSolver\\pi\_\{\\text\{Solver\}\}, which is the objective of OPD\(Lu and Lab,[2025](https://arxiv.org/html/2607.25308#bib.bib29)\)\. We have:

*Logit\-free OPD\.*Traditional distillation requires the teacher’s full output distribution\. Here, the identityAπSolver=τ​log⁡πSolverA^\{\\pi\_\{\\text\{Solver\}\}\}=\\tau\\log\\pi\_\{\\text\{Solver\}\}means a single scalar per action already encodes the teacher’s log\-preference, that is, no logits needed\.

*Why the student can surpass the solver\.*Isolating the KL component of[Equation 9](https://arxiv.org/html/2607.25308#S2.E9)and solving the per\-state optimization yields a closed\-form optimal policyπ∗​\(a\|s\)∝πSolver​\(a\|s\)​exp⁡\(Ataskπθ​\(s,a\)/β\)\\pi^\{\*\}\(a\|s\)\\propto\\pi\_\{\\text\{Solver\}\}\(a\|s\)\\,\\exp\\\!\\big\(A^\{\\pi\_\{\\theta\}\}\_\{\\text\{task\}\}\(s,a\)/\\beta\\big\): the solver distribution serves as a prior, and the task advantage tilts it exponentially\. Atβ→∞\\beta\\to\\infty\(pure distillation\),π∗→πSolver\\pi^\{\*\}\\to\\pi\_\{\\text\{Solver\}\}; at finiteβ\\beta, the tilt letsπ∗\\pi^\{\*\}deviate wherever the task reward warrants it, so the student can*surpass*the teacher\.

## 3Experiments

Our experiments address four research questions below:

RQ1:Does the solver\-derived turn\-level signal outperform outcome\-only and process\-level RL baselines in\-domain on the training games \([Subsection 3\.2](https://arxiv.org/html/2607.25308#S3.SS2)\)?

RQ2:Do the trained agents generalize to unseen difficulty levels within the training games and to held\-out domains \([Subsection 3\.2](https://arxiv.org/html/2607.25308#S3.SS2),[Subsection 3\.3](https://arxiv.org/html/2607.25308#S3.SS3)\)?

RQ3:Does each design component contribute to the final performance, namely the solver\-advantage weight, theasinhtransformation, and batch\-level RMS normalization \([Subsection 3\.4](https://arxiv.org/html/2607.25308#S3.SS4)\)?

RQ4:Is solver guidance practical, i\.e\., does it add little training overhead and remain effective when the solver is a learned value network \([Subsection 3\.5](https://arxiv.org/html/2607.25308#S3.SS5)\)?

### 3\.1Experimental Setup

##### Datasets and Benchmarks

We train and evaluate on three classic games,Sokoban,Minesweeper, andRush Hour, whose clear rules and efficient solvers provide verifiable rewards and process\-level supervision\. Together, they span complementary reasoning challenges, from long\-horizon planning and partial\-observation inference to constrained combinatorial search\. For each game, we procedurally generate instances across difficulty levels defined by game\-specific structural parameters and calibrated with solver\-derived solution complexity\. We canonicalize board configurations to remove duplicates, prevent overlap between training and test instances, and verify solvability with the corresponding solver\. Evaluation covers two within\-game settings:*In\-Domain*\(ID\), covering difficulty levels seen during training, and*Unseen\-Difficulty*, covering harder levels held out from training\. We evaluate each setting on 200 held\-out instances per game\. Throughout,*unseen difficulty*denotes this within\-game shift, whereas*OOD transfer*denotes zero\-shot evaluation on a held\-out task domain\. Full generation and difficulty\-control details are given in Appendix[B\.1](https://arxiv.org/html/2607.25308#A2.SS1)\.

To probe OOD transfer beyond the training games, we further evaluate zero\-shot on two held\-out agentic domains without any further fine\-tuning: the embodied benchmark ALFWorld\([Shridharet al\.,](https://arxiv.org/html/2607.25308#bib.bib34)\)and the web benchmark WebShop\(Yaoet al\.,[2022](https://arxiv.org/html/2607.25308#bib.bib35)\); benchmark sources and evaluation protocols are detailed in Appendix[B\.2](https://arxiv.org/html/2607.25308#A2.SS2)\.

##### Baselines and Models

We useQwen3\-4B\-Instruct\-2507\(Yanget al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib36)\)as the base policy for all trained methods\. As training\-free references, we evaluate the frozen base policy with a ReAct\-style prompt\(Yaoet al\.,[2023](https://arxiv.org/html/2607.25308#bib.bib5)\), together with a suite of strong closed\-source models under the same prompt, namelyGemini\-2\.5\-Flash\(Comaniciet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib37)\),Gemini\-2\.5\-Pro\(Comaniciet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib37)\),Claude\-Sonnet\-4\.5\(Anthropic,[2025b](https://arxiv.org/html/2607.25308#bib.bib38)\),Claude\-Opus\-4\.5\(Anthropic,[2025a](https://arxiv.org/html/2607.25308#bib.bib39)\),Claude\-Sonnet\-4\.6\(Anthropic,[2026b](https://arxiv.org/html/2607.25308#bib.bib40)\), andClaude\-Opus\-4\.6\(Anthropic,[2026a](https://arxiv.org/html/2607.25308#bib.bib41)\)\. For trained baselines, we compare against outcome\-only RLVR methods that fine\-tune the same base policy with the same sparse terminal reward: GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.25308#bib.bib1)\), GSPO\(Zhenget al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib3)\), and DAPO\(Yuet al\.,[2026a](https://arxiv.org/html/2607.25308#bib.bib2)\)\. This keeps the terminal reward fixed and focuses the comparison on the added solver\-derived turn\-level signal\. We also include GiGPO\(Fenget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib4)\), a process\-level baseline, to examine whether solver\-guided supervision provides gains beyond anchor\-state process shaping\.

##### Implementation Details

The agent plays each game through a multi\-turn ReAct\-style loop, alternating between reasoning over a textual board rendering and emitting one action per turn, until the episode ends on a solve, an illegal move, or an exhausted turn budget \(Appendix[C\.1](https://arxiv.org/html/2607.25308#A3.SS1)\)\. Sokoban, Minesweeper, and Rush Hour share this interface but differ in their state encodings and step dynamics, which we detail in Appendix[C\.2](https://arxiv.org/html/2607.25308#A3.SS2)\. For each game we build a dedicated solver that returns, for any reachable state, the optimal action valueQπSolverQ^\{\\pi\_\{\\text\{Solver\}\}\}and state valueVπSolverV^\{\\pi\_\{\\text\{Solver\}\}\}: weighted A⋆search for Sokoban, constraint\-satisfaction solving with exact combinatorial mine\-probability inference for Minesweeper, and a precomputed full\-state distance table via multi\-source reverse BFS for Rush Hour \(Appendix[C\.3](https://arxiv.org/html/2607.25308#A3.SS3)\)\. We query these solvers on the states visited during rollouts to form the solver\-advantage signal\.

CAST is implemented on top of the DAPO backbone, from which we retain the token\-mean loss and clip\-higher objective, augmenting its outcome objective with the solver\-advantage process signal described in[Section 2](https://arxiv.org/html/2607.25308#S2)\. Following common practice, all environments use a 0/1 sparse reward\. We train with a batch size of 16, 8 rollouts per prompt, and a maximum response length of 16384 tokens; the solver\-advantage weight is set toα=0\.1\\alpha\{=\}0\.1by default, and the remaining training settings are listed in Appendix[C\.6](https://arxiv.org/html/2607.25308#A3.SS6)\. For evaluation, we score every game by success rate\. To reduce sampling variance, for each instance we draw four independent rollouts and report the average success rate, denoted Avg@4\. Unless otherwise noted, all tables report the mean over3 independent runs, taking each run’s final checkpoint at step 200 \(Sokoban\), 400 \(Minesweeper\), and 300 \(Rush Hour\) for both within\-game and OOD\-transfer evaluation; closed\-source references use a single run under the same Avg@4 protocol\.

### 3\.2Main Results on the Training Games

Table 1:Main results on the training games\.Avg@4 success rate \(%\) on in\-domain \(ID\) and unseen\-difficulty \(Unseen\) levels;Averageaggregates the three games\. Within the Qwen3\-4B\-Instruct\-2507 block, bold and underlined values mark the best and second\-best results, respectively\.TypeApproachSokobanMinesweeperRush HourAverageIDUnseenIDUnseenIDUnseenIDUnseenClosed\-Source Models \(ReAct; G = Gemini\)PromptingG\-2\.5\-Flash64\.033\.338\.123\.073\.963\.658\.740\.0PromptingG\-2\.5\-Pro77\.545\.650\.818\.892\.088\.973\.451\.1PromptingSonnet\-4\.560\.029\.334\.422\.856\.942\.350\.431\.5PromptingOpus\-4\.571\.937\.347\.329\.470\.459\.163\.241\.9PromptingSonnet\-4\.679\.547\.157\.642\.588\.181\.475\.157\.0PromptingOpus\-4\.682\.551\.564\.655\.392\.685\.379\.964\.0Base Model: Qwen3\-4B\-Instruct\-2507PromptingReAct44\.316\.84\.50\.41\.10\.516\.65\.9RL TrainingGRPO71\.330\.59\.70\.553\.826\.744\.919\.2RL TrainingGSPO72\.628\.328\.25\.024\.811\.541\.914\.9RL TrainingDAPO71\.931\.329\.87\.332\.517\.444\.718\.7RL TrainingGiGPO70\.629\.613\.71\.451\.931\.345\.420\.8RL TrainingCAST \(Ours\)77\.034\.844\.711\.064\.739\.562\.128\.4##### Comparison with training\-free baselines\.

Training substantially improves theQwen3\-4B\-Instruct\-2507base policy\. With a ReAct framework, the frozen base reaches game\-averaged Avg@4 scores of 16\.6 on ID and 5\.9 on Unseen\-Difficulty; after training, our 4B agent reaches 62\.1 and 28\.4\. On ID, it also exceeds the ReAct scores of two closed\-source models, Gemini\-2\.5\-Flash \(58\.7\) and Claude\-Sonnet\-4\.5 \(50\.4\), showing the practical benefit of solver\-guided RL beyond prompting alone for this base policy\.

##### Controlled comparison against trained baselines\.

Trained from the same base with the same final reward, CAST attains the best Avg@4 in every game under both evaluation settings\. The cleanest comparison is against DAPO, our backbone with the solver\-advantage signal removed: adding this signal lifts the ID average from 44\.7 to 62\.1 and the Unseen\-Difficulty average from 18\.7 to 28\.4, isolating its contribution\. The lead also holds over the outcome\-only baseline GRPO \(44\.9 ID, 19\.2 Unseen\) and the process\-level baseline GiGPO \(45\.4, 20\.8\), and spans all three games rather than coming from a single environment\. Minesweeper shows the largest ID gain of\+14\.9\+14\.9over the best trained baseline, while its Unseen\-Difficulty score of 11\.0 leaves room for improvement on harder instances\.

##### Training dynamics\.

[Figure 3](https://arxiv.org/html/2607.25308#S3.F3)shows that solver guidance improves both training efficiency and validation performance\. CAST attains the highest validation Avg@4 on all three games and reaches DAPO’s peak after only 120, 200, and 140 training steps on Sokoban, Minesweeper, and Rush Hour, respectively, compared with 200, 400, and 240 steps for DAPO, corresponding to a1\.71\.7–2\.0×2\.0\\timesspeedup\. CAST leads on training reward across all three games, clearly on the harder Minesweeper and Rush Hour and edging ahead only late on the easier Sokoban\.

![Refer to caption](https://arxiv.org/html/2607.25308v1/x3.png)Figure 3:Training dynamics\.Horizontal dashed lines mark DAPO’s peak validation Avg@4; vertical dotted lines mark when CAST and DAPO first reach it, in orange and blue respectively\. Curves are EMA\-smoothed at0\.60\.6, with bands showing the standard deviation over three runs\.

### 3\.3Zero\-Shot OOD Transfer

Table 2:Zero\-shot OOD transfer\.Avg@4 success rate \(%\) on ALFWorld and WebShop;Averageaggregates source\-game agents, andOverallaggregates both domains\. Dashes denote entries not applicable to ReAct; bold and underlined values mark the best and second\-best results, respectively\.TypeMethodALFWorldWebShopOverallSok\.Mine\.RushAverageSok\.Mine\.RushAverageBase: Qwen3\-4B\-Instruct\-2507PromptingReAct———30\.2———18\.824\.5RL TrainingGRPO31\.522\.327\.927\.220\.414\.018\.017\.522\.4RL TrainingGSPO34\.222\.040\.032\.118\.013\.120\.917\.324\.7RL TrainingDAPO37\.335\.218\.630\.417\.518\.813\.616\.623\.5RL TrainingGiGPO35\.624\.932\.130\.917\.220\.216\.417\.924\.4RL TrainingCAST \(Ours\)38\.433\.941\.437\.923\.225\.119\.722\.730\.3[Table 2](https://arxiv.org/html/2607.25308#S3.T2)shows that the benefits of solver\-guided training extend beyond the source games\. CAST achieves the highest domain average on both ALFWorld \(37\.9\) and WebShop \(22\.7\), exceeding the strongest trained baseline by 5\.8 and 4\.8 points, respectively\. It also outperforms training\-free ReAct on both domains and attains the best Overall score of 30\.3, 5\.6 points above the second\-best method\. A WebShop case study is provided in Appendix[B\.3](https://arxiv.org/html/2607.25308#A2.SS3)\.

### 3\.4Ablation Studies

We ablate the key design choices of CAST on Sokoban\.

1. 1\.Solver\-advantage weightα\\alpha\([Figure 4](https://arxiv.org/html/2607.25308#S3.F4)left\): the weight trades off the process signal against the outcome objective, and our defaultα=0\.1\\alpha\{=\}0\.1is best on both validation Avg@4 and training reward\. Whenα\\alphais too small the process signal is diluted and the run behaves like the outcome\-only baseline, converging slowly to a lower plateau\. Whenα\\alphais too large the signal crowds out the sparse outcome objective: validation Avg@4 climbs quickly at first but peaks early and then declines, and training reward becomes unstable and drops in late training\. Onlyα=0\.1\\alpha\{=\}0\.1keeps improving and stays stable throughout\.
2. 2\.Transformation and normalization\([Figure 4](https://arxiv.org/html/2607.25308#S3.F4)right\): theasinhtransformation and batch\-level RMS normalization play complementary roles, and removing either lowers the final Avg@4\. Droppingasinhhurts most: without it the run is slowest and stays lowest throughout, since unbounded solver advantages let a few large values dominate the update\. Dropping RMS normalization instead matches the full method early but plateaus and dips late, with noisier training reward, indicating that per\-batch rescaling is what keeps the signal stable as training progresses\.

![Refer to caption](https://arxiv.org/html/2607.25308v1/x4.png)\(a\)Solver\-advantage weightα\\alpha: Val Avg@4
![Refer to caption](https://arxiv.org/html/2607.25308v1/x5.png)\(b\)asinh\+ batch RMS: Val Avg@4
![Refer to caption](https://arxiv.org/html/2607.25308v1/x6.png)\(c\)Solver\-advantage weightα\\alpha: Train rewards
![Refer to caption](https://arxiv.org/html/2607.25308v1/x7.png)\(d\)asinh\+ batch RMS: Train rewards

Figure 4:Ablation studies on Sokoban\.Left column: sweeping the solver\-advantage weightα\\alpha\.Right column: removing/replacing theasinhtransformation and batch\-level RMS normalization\. Curves are EMA\-smoothed at0\.60\.6\.
### 3\.5Analysis

We analyze the practicality of solver guidance from two angles: the training\-time overhead it adds, and whether it still helps when the exact solver is replaced by an approximate learned value network\.

##### Solver runtime overhead\.

Forming the solver\-advantage signal requires one solver query per environment step to obtainQπSolverQ^\{\\pi\_\{\\text\{Solver\}\}\}andVπSolverV^\{\\pi\_\{\\text\{Solver\}\}\}for the current state\.[Figure 6](https://arxiv.org/html/2607.25308#A3.F6)shows that the relative cost of these queries rapidly diminishes at broader levels of the training pipeline\. Although solver queries account for8\.4%8\.4\\%of an environment step, environment interaction itself occupies only0\.1%0\.1\\%of trajectory runtime, with the remaining99\.9%99\.9\\%dominated by LLM generation\. Solver time therefore accounts for only0\.01%0\.01\\%of a trajectory\. Since rollout collection occupies60\.7%60\.7\\%of a training step, the solver’s estimated end\-to\-end contribution is just7373ppm of total training\-step wall\-clock time, making its overhead negligible relative to generation and policy optimization\.

##### Learned value networks as solvers\.

Solver guidance can also use an approximate learned value function as the process\-signal source, which extends it to the traditional RL or deep RL\. On Rush Hour, we replace the exact solver with a DQN\-based value network\(Van Hasseltet al\.,[2016](https://arxiv.org/html/2607.25308#bib.bib42)\)trained without solver distances, then refined by self\-distillation and a small geometric prior; we use its state values as the process signal \(details in Appendix[C\.4](https://arxiv.org/html/2607.25308#A3.SS4)\)\. As shown in[Figure 5](https://arxiv.org/html/2607.25308#S3.F5), the learned\-network variant closely tracks the exact\-solver version and ends only slightly below it in validation Avg@4\. It remains above the trained baselines at the end of training and, unlike DAPO and GSPO, shows no comparable late\-stage drop in validation Avg@4\. Thus, even with a learned value function, CAST retains much of the benefit of exact\-solver guidance, showing that solver guidance carries over to standard RL rather than depending on a hand\-built solver\.

![Refer to caption](https://arxiv.org/html/2607.25308v1/x8.png)\(a\)Val Avg@4
![Refer to caption](https://arxiv.org/html/2607.25308v1/x9.png)\(b\)Train rewards

Figure 5:Learned value network as a solver on Rush Hour\.We replace the exact solver with a DQN\-based value network trained without solver distances as the process\-signal source\. Curves are EMA\-smoothed at0\.60\.6; bands show the standard deviation across the 3 runs\.

## 4Conclusion

We address turn\-level credit assignment in RLVR for LLM game agents, where sparse terminal rewards provide little direct guidance about which actions lead to success or failure\. CAST queries a game solver on LLM\-visited states and converts per\-action changes in the solver’s state value into solver advantages that provide fine\-grained, turn\-level credit; under a soft\-optimal solver assumption, this update also admits a logit\-free on\-policy distillation interpretation without teacher logits\. Across Sokoban, Minesweeper, and Rush Hour, CAST achieves the best performance among trained methods on every game under both in\-domain and unseen\-difficulty evaluation, reaches DAPO’s peak validation performance in1\.71\.7–2\.0×2\.0\\timesfewer training steps, and attains the highest average zero\-shot performance on held\-out ALFWorld and WebShop\. Solver queries add negligible training overhead, while an approximate learned value network retains much of the benefit of exact solver guidance\. More broadly, our results suggest that reliable state evaluation offers a practical route from sparse outcomes to fine\-grained credit, whether the evaluator is an exact solver or a learned value function\.

## References

- On\-policy distillation of language models: learning from self\-generated mistakes\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 21246–21263\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px3.p1.1),[§C\.5\.4](https://arxiv.org/html/2607.25308#A3.SS5.SSS4.p3.3)\.
- T\. Anthony, Z\. Tian, and D\. Barber \(2017\)Thinking fast and slow with deep learning and tree search\.Advances in neural information processing systems30\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px3.p1.1)\.
- Anthropic \(2025a\)Introducing claude opus 4\.5\.Note:[https://www\.anthropic\.com/news/claude\-opus\-4\-5](https://www.anthropic.com/news/claude-opus-4-5)Cited by:[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- Anthropic \(2025b\)Introducing claude sonnet 4\.5\.Note:[https://www\.anthropic\.com/news/claude\-sonnet\-4\-5](https://www.anthropic.com/news/claude-sonnet-4-5)Cited by:[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- Anthropic \(2026a\)Introducing claude opus 4\.6\.Note:[https://www\.anthropic\.com/news/claude\-opus\-4\-6](https://www.anthropic.com/news/claude-opus-4-6)Cited by:[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- Anthropic \(2026b\)Introducing claude sonnet 4\.6\.Note:[https://www\.anthropic\.com/news/claude\-sonnet\-4\-6](https://www.anthropic.com/news/claude-sonnet-4-6)Cited by:[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- J\. Chen, Q\. He, S\. Yuan, A\. Chen, Z\. Cai, W\. Dai, H\. Yu, J\. Chen, X\. Li, Q\. Yu,et al\.\(2026\)Enigmata: scaling logical reasoning in large language models with synthetic verifiable puzzles\.Advances in Neural Information Processing Systems38,pp\. 3613–3661\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- L\. Chen, H\. Gao, T\. Liu, Z\. Huang, F\. Sung, X\. Zhou, Y\. Wu, and B\. Chang \(2025\)G1: bootstrapping perception and reasoning abilities of vision\-language model via reinforcement learning\.arXiv preprint arXiv:2505\.13426\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- \[9\]Y\. Chen, Y\. Wang, Y\. Zhang, Z\. Ye, Z\. Cai, Y\. Shi, Q\. GU, H\. Su, X\. Cai, X\. Wang,et al\.Learning to self\-verify makes language models better reasoners\.InForty\-third International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p2.1)\.
- G\. Comanici, E\. Bieber, M\. Schaekermann, I\. Pasupat, N\. Sachdeva, I\. Dhillon, M\. Blistein, O\. Ram, D\. Zhang, E\. Rosen,et al\.\(2025\)Gemini 2\.5: pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities\.arXiv preprint arXiv:2507\.06261\.Cited by:[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- L\. Fan, G\. Wang, Y\. Jiang, A\. Mandlekar, Y\. Yang, H\. Zhu, A\. Tang, D\. Huang, Y\. Zhu, and A\. Anandkumar \(2022\)Minedojo: building open\-ended embodied agents with internet\-scale knowledge\.Advances in Neural Information Processing Systems35,pp\. 18343–18362\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- L\. Feng, Z\. Xue, T\. Liu, and B\. An \(2026\)Group\-in\-group policy optimization for llm agent training\.Advances in Neural Information Processing Systems38,pp\. 46375–46408\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p2.1),[§1](https://arxiv.org/html/2607.25308#S1.p5.1),[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- Y\. Gu, L\. Dong, F\. Wei, and M\. Huang \(2024\)Minillm: knowledge distillation of large language models\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 32694–32717\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p3.1)\.
- L\. Guertler, B\. Cheng, S\. Yu, B\. Liu, L\. Choshen, and C\. Tan \(2025\)Textarena\.arXiv preprint arXiv:2504\.11442\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- D\. Guo, D\. Yang, H\. Zhang, J\. Song, P\. Wang, Q\. Zhu, R\. Xu, R\. Zhang, S\. Ma, X\. Bi,et al\.\(2025\)Deepseek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p2.1)\.
- Y\. Guo, L\. Xu, J\. Liu, D\. Ye, and S\. Qiu \(2026\)Segment policy optimization: effective segment\-level credit assignment in rl for large language models\.Advances in Neural Information Processing Systems38,pp\. 114399–114431\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1)\.
- T\. Haarnoja, A\. Zhou, P\. Abbeel, and S\. Levine \(2018\)Soft actor\-critic: off\-policy maximum entropy deep reinforcement learning with a stochastic actor\.InInternational conference on machine learning,pp\. 1861–1870\.Cited by:[Assumption C\.1](https://arxiv.org/html/2607.25308#A3.SS5.SSS2.1.p1.1),[§C\.5\.7](https://arxiv.org/html/2607.25308#A3.SS5.SSS7.Px1.p1.1),[§2\.2](https://arxiv.org/html/2607.25308#S2.SS2.SSS0.Px5.p1.4)\.
- S\. Hao, Y\. Gu, H\. Ma, J\. Hong, Z\. Wang, D\. Wang, and Z\. Hu \(2023\)Reasoning with language model is planning with world model\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,pp\. 8154–8173\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p2.1)\.
- \[19\]S\. He, L\. Feng, Q\. Wei, X\. Cheng, L\. Feng, and B\. AnHierarchy\-of\-groups policy optimization for long\-horizon agentic tasks\.InThe Fourteenth International Conference on Learning Representations,Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1)\.
- L\. Hu, M\. Huo, Y\. Zhang, H\. Yu, E\. P\. Xing, I\. Stoica, T\. Rosing, H\. Jin, and H\. Zhang \(2025\)Lmgame\-bench: how good are llms at playing games?\.arXiv preprint arXiv:2505\.15146\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- P\. Intelligence, K\. Black, N\. Brown, J\. Darpinian, K\. Dhabalia, D\. Driess, A\. Esmail, M\. Equi, C\. Finn, N\. Fusai,et al\.\(2025\)π0\.5\\pi\_\{0\.5\}: a vision\-language\-action model with open\-world generalization\.arXiv preprint arXiv:2504\.16054\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- A\. Junghanns and J\. Schaeffer \(2001\)Sokoban: enhancing general single\-agent search methods using domain knowledge\.Artificial Intelligence129\(1\-2\),pp\. 219–251\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- S\. Kakade and J\. Langford \(2002\)Approximately optimal approximate reinforcement learning\.InProceedings of the nineteenth international conference on machine learning,pp\. 267–274\.Cited by:[§C\.5\.6](https://arxiv.org/html/2607.25308#A3.SS5.SSS6.p1.1),[Proposition C\.11](https://arxiv.org/html/2607.25308#A3.SS5.SSS6.p2.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1)\.
- \[24\]A\. Kazemnejad, M\. Aghajohari, E\. Portelance, A\. Sordoni, S\. Reddy, A\. Courville, and N\. Le RouxVinePPO: refining credit assignment in rl training of llms\.InForty\-second International Conference on Machine Learning,Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1)\.
- J\. Li, P\. Zhou, R\. Meng, M\. P\. Vadera, L\. Li, and Y\. Li \(2026\)Turn\-ppo: turn\-level advantage estimation with ppo for improved multi\-turn rl in agentic llms\.InFindings of the Association for Computational Linguistics: EACL 2026,pp\. 6227–6243\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1)\.
- Y\. Li, T\. Xu, Y\. Yu, X\. Zhang, X\. Chen, Z\. Ling, N\. Chao, L\. Yuan, and Z\. Zhou \(2025\)Generalist reward models: found inside large language models\.arXiv preprint arXiv:2506\.23235\.Cited by:[Proposition C\.12](https://arxiv.org/html/2607.25308#A3.SS5.SSS6.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.p1.5.1),[§C\.5\.6](https://arxiv.org/html/2607.25308#A3.SS5.SSS6.p6.15)\.
- B\. Liu, L\. Guertler, S\. Yu, Z\. Liu, P\. Qi, D\. Balcells, M\. Liu, C\. Tan, W\. Shi, M\. Lin,et al\.\(2025\)Spiral: self\-play on zero\-sum games incentivizes reasoning via multi\-agent multi\-turn reinforcement learning\.arXiv preprint arXiv:2506\.24119\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- K\. Lu and T\. M\. Lab \(2025\)On\-policy distillation\.Thinking Machines Lab: Connectionism\.Note:https://thinkingmachines\.ai/blog/on\-policy\-distillationExternal Links:[Document](https://dx.doi.org/10.64434/tml.20251026)Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p3.1),[§2\.2](https://arxiv.org/html/2607.25308#S2.SS2.SSS0.Px5.p3.2)\.
- V\. Mnih, K\. Kavukcuoglu, D\. Silver, A\. Graves, I\. Antonoglou, D\. Wierstra, and M\. Riedmiller \(2013\)Playing atari with deep reinforcement learning\.arXiv preprint arXiv:1312\.5602\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- V\. Mnih, K\. Kavukcuoglu, D\. Silver, A\. A\. Rusu, J\. Veness, M\. G\. Bellemare, A\. Graves, M\. Riedmiller, A\. K\. Fidjeland, G\. Ostrovski,et al\.\(2015\)Human\-level control through deep reinforcement learning\.nature518\(7540\),pp\. 529–533\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- A\. Y\. Ng, D\. Harada, and S\. Russell \(1999\)Policy invariance under reward transformations: theory and application to reward shaping\.InIcml,Vol\.99,pp\. 278–287\.Cited by:[§C\.5\.6](https://arxiv.org/html/2607.25308#A3.SS5.SSS6.1.p1.7),[Proposition C\.12](https://arxiv.org/html/2607.25308#A3.SS5.SSS6.p4.pic1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.p1.4.4)\.
- M\. Ouyang, S\. Hu, K\. Q\. Lin, H\. T\. Ng, and M\. Z\. Shou \(2026\)GameWorld: towards standardized and verifiable evaluation of multimodal game agents\.arXiv preprint arXiv:2604\.07429\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- D\. Paglieri, B\. Cupiał, S\. Coward, U\. Piterbarg, M\. Wołczyk, A\. Khan, E\. Pignatelli, Ł\. Kuciński, L\. Pinto, R\. Fergus,et al\.\(2025\)Balrog: benchmarking agentic llm and vlm reasoning on games\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 96666–96702\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- S\. Ross and J\. A\. Bagnell \(2014\)Reinforcement and imitation learning via interactive no\-regret learning\.arXiv preprint arXiv:1406\.5979\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px3.p1.1)\.
- S\. Ross, G\. Gordon, and D\. Bagnell \(2011\)A reduction of imitation learning and structured prediction to no\-regret online learning\.InProceedings of the fourteenth international conference on artificial intelligence and statistics,pp\. 627–635\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px3.p1.1),[§C\.5\.6](https://arxiv.org/html/2607.25308#A3.SS5.SSS6.p6.15)\.
- J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. Klimov \(2017\)Proximal policy optimization algorithms\.arXiv preprint arXiv:1707\.06347\.Cited by:[Assumption C\.4](https://arxiv.org/html/2607.25308#A3.SS5.SSS2.4.p1.2),[Remark C\.9](https://arxiv.org/html/2607.25308#A3.SS5.SSS5.2.p1.3),[§C\.5\.7](https://arxiv.org/html/2607.25308#A3.SS5.SSS7.Px4.p1.1)\.
- Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. Li, Y\. Wu,et al\.\(2024\)Deepseekmath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[§C\.5\.7](https://arxiv.org/html/2607.25308#A3.SS5.SSS7.Px3.p1.1),[§2\.1](https://arxiv.org/html/2607.25308#S2.SS1.SSS0.Px2.p1.4),[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. Yao \(2023\)Reflexion: language agents with verbal reinforcement learning\.Advances in neural information processing systems36,pp\. 8634–8652\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- \[39\]M\. Shridhar, X\. Yuan, M\. Cote, Y\. Bisk, A\. Trischler, and M\. HausknechtALFWorld: aligning text and embodied environments for interactive learning\.InInternational Conference on Learning Representations,Cited by:[§B\.2](https://arxiv.org/html/2607.25308#A2.SS2.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p5.1),[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px1.p2.1)\.
- D\. Silver, T\. Hubert, J\. Schrittwieser, I\. Antonoglou, M\. Lai, A\. Guez, M\. Lanctot, L\. Sifre, D\. Kumaran, T\. Graepel,et al\.\(2017\)Mastering chess and shogi by self\-play with a general reinforcement learning algorithm\.arXiv preprint arXiv:1712\.01815\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px3.p1.1)\.
- R\. S\. Sutton, D\. McAllester, S\. Singh, and Y\. Mansour \(1999\)Policy gradient methods for reinforcement learning with function approximation\.Advances in neural information processing systems12\.Cited by:[§C\.5\.1](https://arxiv.org/html/2607.25308#A3.SS5.SSS1.p2.2),[§C\.5\.4](https://arxiv.org/html/2607.25308#A3.SS5.SSS4.3.p3.1),[§2\.1](https://arxiv.org/html/2607.25308#S2.SS1.SSS0.Px2.p1.4)\.
- W\. Tan, W\. Zhang, X\. Xu, H\. Xia, Z\. Ding, B\. Li, B\. Zhou, J\. Yue, J\. Jiang, Y\. Li,et al\.\(2025\)Cradle: empowering foundation agents towards general computer control\.InInternational Conference on Machine Learning,pp\. 58658–58725\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- M\. L\. Team, A\. Gui, B\. Li, B\. Tao, B\. Zhou, B\. Chen, C\. Zhang, C\. Gao, C\. Zhang, C\. Han,et al\.\(2026\)Longcat\-flash\-thinking\-2601 technical report\.arXiv preprint arXiv:2601\.16725\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- H\. Van Hasselt, A\. Guez, and D\. Silver \(2016\)Deep reinforcement learning with double q\-learning\.InProceedings of the AAAI conference on artificial intelligence,Vol\.30\.Cited by:[§3\.5](https://arxiv.org/html/2607.25308#S3.SS5.SSS0.Px2.p1.1)\.
- \[45\]G\. Wang, Y\. Xie, Y\. Jiang, A\. Mandlekar, C\. Xiao, Y\. Zhu, L\. Fan, and A\. AnandkumarVoyager: an open\-ended embodied agent with large language models\.Transactions on Machine Learning Research\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- H\. Wang, C\. T\. Leong, J\. Wang, J\. Wang, and W\. Li \(2025\)Spa\-rl: reinforcing llm agents via stepwise progress attribution\.arXiv preprint arXiv:2505\.20732\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1)\.
- K\. Wang, P\. Zhang, Z\. Wang, Y\. Gao, L\. Li, Q\. Wang, H\. Chen, Y\. Lu, Z\. Yang, L\. Wang,et al\.\(2026\)Vagen: reinforcing world model reasoning for multi\-turn vlm agents\.Advances in Neural Information Processing Systems38,pp\. 172871–172933\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1)\.
- Z\. Xi, C\. Liao, G\. Li, Z\. Zhang, W\. Chen, B\. Wang, S\. Jin, Y\. Zhou, J\. Guan, W\. Wu,et al\.\(2026\)Agentprm: process reward models for llm agents via step\-wise promise and progress\.InProceedings of the ACM Web Conference 2026,pp\. 4184–4195\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.25308#S1.p2.1)\.
- Y\. Xie, Y\. Ma, S\. Lan, A\. Yuille, J\. Xiao, and C\. Wei \(2025\)Play to generalize: learning to reason through game play\.arXiv preprint arXiv:2506\.08011\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px1.p1.1)\.
- A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv,et al\.\(2025\)Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p1.1),[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- S\. Yao, H\. Chen, J\. Yang, and K\. Narasimhan \(2022\)Webshop: towards scalable real\-world web interaction with grounded language agents\.Advances in Neural Information Processing Systems35,pp\. 20744–20757\.Cited by:[§B\.2](https://arxiv.org/html/2607.25308#A2.SS2.SSS0.Px2.p1.2),[§1](https://arxiv.org/html/2607.25308#S1.p5.1),[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px1.p2.1)\.
- S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. Cao \(2023\)ReAct: synergizing reasoning and acting in language models\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- Z\. Ye, W\. Shi, Y\. Liu, Y\. Wang, Z\. Cai, Y\. Shi, Q\. Gu, X\. Cai, and F\. Feng \(2026\)Look before you leap: autonomous exploration for llm agents\.arXiv preprint arXiv:2605\.16143\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p1.1)\.
- Q\. Yu, Z\. Zhang, R\. Zhu, Y\. Yuan, X\. Zuo, Y\. Yue, W\. Dai, T\. Fan, G\. Liu, L\. Liu,et al\.\(2026a\)Dapo: an open\-source llm reinforcement learning system at scale\.Advances in Neural Information Processing Systems38,pp\. 113222–113244\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p5.1),[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- Y\. Yu, M\. Yang, J\. Li, Y\. Gao, F\. Liu, Y\. Yang, Z\. Lin, J\. Lyu, Y\. Liu, Z\. Lu,et al\.\(2026b\)ProAct: agentic lookahead in interactive environments\.arXiv preprint arXiv:2602\.05327\.Cited by:[Appendix A](https://arxiv.org/html/2607.25308#A1.SS0.SSS0.Px2.p1.1)\.
- Y\. Zhang, Z\. Yao, H\. Hao, Y\. Sun, Q\. Gu, H\. Su, X\. Cai, D\. Zhan, and H\. Ye \(2026\)V0V\_\{0\}: A generalist value model for any policy at state zero\.arXiv preprint arXiv:2602\.03584\.Cited by:[§1](https://arxiv.org/html/2607.25308#S1.p2.1)\.
- C\. Zheng, S\. Liu, M\. Li, X\. Chen, B\. Yu, C\. Gao, K\. Dang, Y\. Liu, R\. Men, A\. Yang,et al\.\(2025\)Group sequence policy optimization\.arXiv preprint arXiv:2507\.18071\.Cited by:[§3\.1](https://arxiv.org/html/2607.25308#S3.SS1.SSS0.Px2.p1.1)\.
- B\. D\. Ziebart, A\. L\. Maas, J\. A\. Bagnell, and A\. K\. Dey \(2008\)Maximum entropy inverse reinforcement learning\.InAAAI,D\. Fox and C\. P\. Gomes \(Eds\.\),pp\. 1433–1438\.Cited by:[Assumption C\.1](https://arxiv.org/html/2607.25308#A3.SS5.SSS2.1.p1.1),[§2\.2](https://arxiv.org/html/2607.25308#S2.SS2.SSS0.Px5.p1.4)\.

## Appendix

## Appendix ARelated Work

##### LLMs as Game Agents\.

Recent work has moved foundation models from passive text generation toward interactive game play\. Prompted and scaffolded agents equip LLMs or VLMs with memory, planning, reflection, and coordination, showing that they can interact with games in open world exploration\([Wanget al\.,](https://arxiv.org/html/2607.25308#bib.bib6)\), general computer and video game control\(Tanet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib7)\), and reflective or multi\-agent settings\(Shinnet al\.,[2023](https://arxiv.org/html/2607.25308#bib.bib8)\), often without updating model weights\. In parallel, game environments and benchmarks make such interaction measurable and scalable: open world platforms\(Fanet al\.,[2022](https://arxiv.org/html/2607.25308#bib.bib9)\)and recent benchmarks for LLMs and VLMs\(Paglieriet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib10); Huet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib11); Guertleret al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib12); Ouyanget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib13)\)provide testbeds for evaluating and training game agents\. Game RL with outcome supervision then turns final rewards from games and puzzles into training signals for improving reasoning, transfer, or performance in specific games\(Xieet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib14); Chenet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib15);[2026](https://arxiv.org/html/2607.25308#bib.bib16); Liuet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib17)\)\. These signals are clean and verifiable, but remain coarse for long trajectories: they indicate whether an attempt succeeds, while providing limited guidance about which intermediate decisions mattered\.

##### Credit Assignment and Process Signals in Agentic RL\.

To address the coarse credit provided by final outcomes, recent agentic RL methods construct process signals below the trajectory level, at the segment, turn, or token\(Liet al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib18); Guoet al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib19); Wanget al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib20)\)\. Some methods redistribute outcome information through grouping or decomposition, combining trajectory\-level advantages with step\-level comparisons over recurring or comparable states\(Fenget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib4);[Heet al\.,](https://arxiv.org/html/2607.25308#bib.bib21)\)\. Others learn process evaluators for agent trajectories, including process reward models that estimate stepwise promise and progress\(Xiet al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib22)\), and learned turn\-level critics for multi\-turn environments\(Wanget al\.,[2026](https://arxiv.org/html/2607.25308#bib.bib23)\)\. Search\- and rollout\-based approaches instead estimate intermediate values by expanding possible continuations, producing value estimates or process labels for policy improvement\(Haoet al\.,[2023](https://arxiv.org/html/2607.25308#bib.bib24);[Kazemnejadet al\.,](https://arxiv.org/html/2607.25308#bib.bib25); Yuet al\.,[2026b](https://arxiv.org/html/2607.25308#bib.bib26)\)\. These signal sources expose a recurring trade\-off: grouping methods require comparable intermediate states, learned verifiers and critics require additional training signals or models, and search or rollout estimates can add substantial computation or depend on the rollout policy\. In contrast, our work uses game\-specific solvers as an external source of turn\-level supervision\.

##### Logit\-Free Distillation from Solvers and Search\.

CAST is also related to distillation, but differs in the teacher signal it uses\. Recent LLM on\-policy distillation learns from student\-generated outputs, but assumes access to teacher token distributions or log probabilities\(Agarwalet al\.,[2024](https://arxiv.org/html/2607.25308#bib.bib27); Guet al\.,[2024](https://arxiv.org/html/2607.25308#bib.bib28); Lu and Lab,[2025](https://arxiv.org/html/2607.25308#bib.bib29)\)\. Classical solvers instead provide structured signals such as actions, feasibility, and cost\-to\-go values, connecting our setting to traditional imitation learning and search distillation\. DAgger queries an oracle on learner\-visited states\(Rosset al\.,[2011](https://arxiv.org/html/2607.25308#bib.bib30)\), AggreVaTe supervises actions with cost\-to\-go estimates\(Ross and Bagnell,[2014](https://arxiv.org/html/2607.25308#bib.bib31)\), and expert\-iteration methods distill search\-improved decisions into a policy\(Anthonyet al\.,[2017](https://arxiv.org/html/2607.25308#bib.bib32); Silveret al\.,[2017](https://arxiv.org/html/2607.25308#bib.bib33)\)\. These methods target task\-specific policies, whereas we attach scalar solver advantage estimates to LLM\-sampled actions, yielding a logit\-free process signal that plugs directly into RLVR\.

## Appendix BDatasets and Benchmarks

### B\.1Dataset Details

##### Data generation\.

Each game uses a procedural generator that produces instances at a controllable difficulty\.Sokobanrooms are grown by random wall placement and then populated by a reverse\-playing search, which guarantees a solvable layout in which at least one box must be pushed\.Minesweeperboards place mines uniformly at random outside a3×33\{\\times\}3safe zone around a designated first\-click cell, which the environment reveals at the start of every episode so that the board is fixed from the agent’s first action onward; we do not filter for no\-guess solvability, so a few boards may still require a probabilistic guess, which the oracle handles as described in Appendix[C\.3](https://arxiv.org/html/2607.25308#A3.SS3)\.Rush Hourboards are sampled at random and kept only if an exact solver confirms an optimal solution whose length lies in a target range; this solver is used only for data construction and differs from the training oracle of Appendix[C\.3](https://arxiv.org/html/2607.25308#A3.SS3)\.

##### Difficulty and splits\.

Difficulty is controlled by board size and a game\-specific count: boxes for Sokoban, mines for Minesweeper, and total vehicles for Rush Hour\. For each game, we train on a single in\-domain \(ID\) tier and hold out a harder unseen\-difficulty tier, obtained by increasing this count and, for Sokoban and Minesweeper, enlarging the board; both tiers are listed in Table[3](https://arxiv.org/html/2607.25308#A2.T3)\. Each tier provides200200evaluation instances\. All instances are drawn from independent random seeds and de\-duplicated by a hash of their initial board, so that no instance recurs within the training set and no evaluation instance appears in training\. The textual state encoding and action interface of each environment are described in Appendix[C\.2](https://arxiv.org/html/2607.25308#A3.SS2)\.

Table 3:Per\-game in\-domain \(ID\) and unseen\-difficulty \(Unseen\) tiers\. Agents are trained only on ID and evaluated on both tiers; for Rush Hour, the count includes the target vehicleA\.GameSplitBoard\# Boxes, Mines,or VehiclesSokobanID6×66\{\\times\}62 boxesUnseen7×77\{\\times\}73 boxesMinesweeperID6×66\{\\times\}67 minesUnseen7×77\{\\times\}710 minesRush HourID6×66\{\\times\}67 vehiclesUnseen6×66\{\\times\}69 vehicles

### B\.2OOD Transfer Benchmark Details

To measure cross\-domain transfer, we take each agent trained on the three games and evaluate it zero\-shot, with no further training, on two standard text\-agent benchmarks, ALFWorld and WebShop\. Both are driven by the same multi\-turn loop and single\-action interface as the games \(Appendix[C\.1](https://arxiv.org/html/2607.25308#A3.SS1)\), differing only in their observations and action space, so that any success reflects abilities transferred from game training rather than benchmark\-specific tuning\.

##### ALFWorld\.

ALFWorld\([Shridharet al\.,](https://arxiv.org/html/2607.25308#bib.bib34)\)is an embodied household benchmark in which the agent completes a natural\-language instruction \(e\.g\. heating an object and placing it\) by navigating and manipulating objects in a text\-rendered room\. We use its TextWorld engine over the six standard task types and evaluate on the*seen*validation split\. Each turn presents the current observation together with the list of admissible commands, and the agent replies with one command such asgo to,take,open, orheat; an invalid command is rejected with feedback and the episode continues\. An episode runs for up to3030turns\.

##### WebShop\.

WebShop\(Yaoet al\.,[2022](https://arxiv.org/html/2607.25308#bib.bib35)\)is a simulated online store in which the agent must fulfill a shopping instruction by searching, browsing, and purchasing a product that matches the requested attributes and price\. The text observation renders the current page, and the agent acts throughsearch\[query\]andclick\[button\], choosing from the clickable elements listed for that page\. We evaluate on the standard500500test instructions, with each episode capped at3030turns\. WebShop reports two metrics, a continuous match score and a binary success rate; we use the success rate, counting an instruction as solved only on a perfect match\.

Both benchmarks are decoded with the same open\-source configuration as the games \(Table[8](https://arxiv.org/html/2607.25308#A3.T8)\): SGLang serving, temperature0\.60\.6, top\-pp0\.950\.95, up to16,38416\{,\}384tokens per turn and2,0482\{,\}048prompt tokens, and44rollouts per instance\.

### B\.3OOD Transfer Case Study

We compare the base modelQwen3\-4B\-Instruct\-2507and its Sokoban\-trained model on the same WebShop instruction; the latter receives only solver\-guided Sokoban training before zero\-shot evaluation\. The instruction asks, “*Find me easy clean sofa tables with solid wood for living room with color: walnut, and price lower than 260\.00 dollars*”\. WebShop credits a purchase only on a full attribute match; here, thewalnutoption must be selected on the product page before the irreversiblebuy now\. The base model commits to an invalid brown table, whereas the CAST\-trained model rejects a poor candidate, searches again, and selects the required color before buying\. This contrast illustrates recovery from an intermediate mistake and constraint checking before commitment, behaviors consistent with the planning discipline learned in Sokoban\. Every action is retained, while some reasoning is omitted for brevity and marked as “\[…\]”\.

Base model \(untrained\) 3 steps – reward 0\.0S0obs:search page\.think:“A good search term would be ‘solid wood sofa table’ as it captures the essential product type and material\. This avoids over\-specificity and allows the system to return relevant results that can be filtered later for color and price\.”search\[solid wood sofa table\]S1obs:50 results; none of the listed titles says*walnut*\.think:“\[…\] The most suitable product that meets the solid wood and price criteria is the ‘Wyndenhall’ table, even though it’s brown\. It is solid wood, priced under $260, and fits the purpose\.”click\[b084hbqytd\]S2obs:Wyndenhall product page \(“Natural Aged Brown”\); it exposes*no*color option\.think:“\[…\] We cannot do a second one with ‘walnut’ because that would include color — which violates the rule\. Therefore, we cannot search again\. \[…\] we should proceed with buying the best available match\.”over\-applies a prompt tip, refuses to explore, and commits the irreversiblebuyon a page that can never satisfy the goal\.click\[buy now\]wrong item \-\- reward 0\.0

CAST \(Sokoban\-trained, zero\-shot\) 6 steps – reward 1\.0S0obs:search page\.think:“Since I cannot include size or color in the search term \(as per tips\), I should search for ‘sofa tables solid wood’ to get relevant products\. \[…\]”search\[sofa tables solid wood\]S1obs:50 results; none of the titles says*walnut*\.think:“The best match in terms of solid wood and low price is the ‘SunnyPoint Classic Side Table’ \(B084ZPN17C\), even though it’s not walnut\. \[…\] I will click on the SunnyPoint table, assuming it might be a close enough match for the task\.”click\[b084zpn17c\]S2obs:SunnyPoint side table page — black, metal frame, not solid walnut wood\.think:“The current product does not meet the color requirement\. I should not proceed with this one\. I need to go back to search with a refined term that includes ‘walnut’ to get better results\. \[…\] I will now search for ‘sofa tables walnut solid wood’ to target the exact color and material\.”rejects a bad candidate and spends its second search to recover, rather than settling\.search\[sofa tables walnut solid wood\]S3obs:re\-ranked results; the Baja solid\-wood table \($237\) now appears near the top\.think:“The Baja Night Stand \(B079N3VLRJ\) is solid wood, priced under $260, and is suitable for living room use\. \[…\] I will proceed to click on it as the best available option within constraints\.”click\[b079n3vlrj\]S4obs:Baja product page exposes a color selector:brown / grey /walnut/ white\.think:“The available color options in the page show: brown, grey, walnut, white\. I should click on the ‘walnut’ color option to see if any product with walnut finish appears\. \[…\] This is the best next step to fulfill the color requirement\.”sees awalnutoption and selects it*before*buying — the move that actually registers the required attribute\.click\[walnut\]S5obs:page looks unchanged after selectingwalnut\.think:“Clicking on ‘walnut’ did not change the product listing \[…\] I should buy this product as the best available option\. Therefore, I will proceed with ‘Buy Now’ for this product\.”click\[buy now\]perfect match \-\- reward 1\.0

## Appendix CImplementation Details and Hyperparameters

### C\.1Agent Implementation

All three games share a single agent scaffold, with game\-specific system prompts, observation formatting, action parsers, and feedback\. At each turn the agent appends the environment’s text observation of the current board to the context and asks the policy to reason and then commit to one action, which it parses and passes back to the environment; the loop repeats until the game is solved, fails, or reaches its turn budget\.

##### Observation and action format\.

Each turn shows the current board together with the number of remaining steps, and, when the previous action was invalid or ineffective, a short line of corrective feedback\. Sokoban and Rush Hour render the board as a symbolic grid paired with a coordinate listing of each entity, while Minesweeper shows the symbolic grid with row and column index headers but no separate coordinate listing\. The policy is asked to reason and then place a single action inside a fenced block, such as`‘‘‘Up‘‘‘`for Sokoban,`‘‘‘reveal 3 2‘‘‘`for Minesweeper, or`‘‘‘A\+2‘‘‘`for Rush Hour\. We read the last fenced block in the response, so intermediate reasoning is ignored, and parse it with a per\-game rule into a concrete action\.

##### History and trajectories\.

The agent conditions on the full context history, including its own reasoning, so that turnttsees every earlier observation and response\. The resulting trajectory, the ordered sequence of observations, responses, actions, and the terminal0/10/1reward, is the token\-level rollout optimized by the RL objectives in Appendix[C\.6\.1](https://arxiv.org/html/2607.25308#A3.SS6.SSS1)\.

##### Invalid actions and termination\.

An unparseable or illegal action, such as an unknown token, an out\-of\-bounds cell, or a move blocked by a wall, does not end the episode: it leaves the state unchanged, consumes one turn, and returns corrective feedback so the policy can retry\. An episode ends only when the game is solved, a game\-specific failure occurs \(a mine hit in Minesweeper, or a deadlock in Sokoban\), or the turn budget is exhausted, and yields reward11only on success\.

##### System prompts\.

Each environment uses a fixed system prompt that specifies its rules and action format\. For reproducibility, we list the exact prompt of every environment below: the three training games first, followed by the two OOD transfer benchmarks\.

Sokoban[⬇](data:text/plain;base64,eFlvdSBhcmUgYSBwbGF5ZXIgc29sdmluZyBhIFNva29iYW4gcHV6emxlLgoKU29rb2JhbiBRdWljayBHdWlkZQpHb2FsOiBQdXNoIGFsbCBib3hlcyAoWCkgb250byB0YXJnZXRzIChPKS4KClN5bWJvbHM6CiMgV2FsbCB8IF8gRW1wdHkgfCBPIFRhcmdldCB8IFggQm94IHwgKiBCb3ggb24gdGFyZ2V0IHwgUCBQbGF5ZXIgfCBTIFBsYXllciBvbiB0YXJnZXQKClJ1bGVzOgoxLiBZb3UgY2FuIHB1c2ggYSBib3ggYnkgbW92aW5nIGludG8gaXQgaWYgdGhlIHNwYWNlIGJlaGluZCBpdCBpcyBmcmVlLgoyLiBZb3UgY2Fubm90IHB1bGwgYm94ZXMuCjMuIFdhbGxzIGFyZSBpbXBhc3NhYmxlLgoKVmFsaWQgQWN0aW9uIChzZXBhcmF0ZWQgYnkgfCApOgpVcCB8IERvd24gfCBMZWZ0IHwgUmlnaHQKCllvdSB3aWxsIGJlIHByb3ZpZGVkIHRoZSBjdXJyZW50IG9ic2VydmF0aW9uLCBwbGVhc2UgZGVjaWRlIG9uIHRoZSBuZXh0IGFjdGlvbi4KWW91IHNob3VsZCBzaG93IHlvdXIgdGhvdWdodCBwcm9jZXNzIGFuZCB0aGVuIGlucHV0IHRoZSBmaW5hbCBhY3Rpb24gaW4gYSBgYGAgYmxvY2suCllvdSBzaG91bGQgb25seSBvdXRwdXQgdGhlIE5FWFQgQUNUSU9OIGF0IGVhY2ggaXRlcmF0aW9uIGluIHRoZSBgYGAgYmxvY2suCkZvciBleGFtcGxlLCBpZiB5b3Ugd2FudCB0byBtb3ZlIHVwLCB5b3Ugc2hvdWxkIG91dHB1dDogYGBgVXBgYGAKUGxlYXNlIHNob3cgeW91ciB0aGlua2luZyBwcm9jZXNzIGFuZCBwdXQgdGhlIGZpbmFsIGFjdGlvbiBpbiBhIGBgYCBibG9jay4KSW4gZXZlcnkgdHVybiwgdGhlIGZpbmFsIGFjdGlvbiBNVVNUIGJlIG9uZSBvZiBVcCwgRG93biwgTGVmdCwgUmlnaHQu)xYouareaplayersolvingaSokobanpuzzle\.SokobanQuickGuideGoal:Pushallboxes\(X\)ontotargets\(O\)\.Symbols:\#Wall\|\_Empty\|OTarget\|XBox\|\*Boxontarget\|PPlayer\|SPlayerontargetRules:1\.Youcanpushaboxbymovingintoitifthespacebehinditisfree\.2\.Youcannotpullboxes\.3\.Wallsareimpassable\.ValidAction\(separatedby\|\):Up\|Down\|Left\|RightYouwillbeprovidedthecurrentobservation,pleasedecideonthenextaction\.Youshouldshowyourthoughtprocessandtheninputthefinalactionina\`\`\`block\.YoushouldonlyoutputtheNEXTACTIONateachiterationinthe\`\`\`block\.Forexample,ifyouwanttomoveup,youshouldoutput:\`\`\`Up\`\`\`Pleaseshowyourthinkingprocessandputthefinalactionina\`\`\`block\.Ineveryturn,thefinalactionMUSTbeoneofUp,Down,Left,Right\.

Minesweeper[⬇](data:text/plain;base64,WW91IGFyZSBhIHBsYXllciBwbGF5aW5nIGEgTWluZXN3ZWVwZXIgZ2FtZS4KCk1pbmVzd2VlcGVyIFJ1bGVzOgotIFRoZSBib2FyZCBpcyBhIGdyaWQgb2YgY2VsbHMuIFNvbWUgY2VsbHMgY29udGFpbiBoaWRkZW4gbWluZXMuCi0gWW91ciBnb2FsIGlzIHRvIHJldmVhbCBhbGwgY2VsbHMgdGhhdCBkbyBOT1QgY29udGFpbiBtaW5lcy4KLSBXaGVuIHlvdSByZXZlYWwgYSBjZWxsOgogIC0gSWYgaXQgY29udGFpbnMgYSBtaW5lLCB0aGUgZ2FtZSBpcyBvdmVyICh5b3UgbG9zZSkuCiAgLSBJZiBpdCBkb2VzIG5vdCBjb250YWluIGEgbWluZSwgYSBudW1iZXIgaXMgc2hvd24gaW5kaWNhdGluZyBob3cgbWFueSBvZiBpdHMgOCBuZWlnaGJvcmluZyBjZWxscyBjb250YWluIG1pbmVzICgwLTgpLgogIC0gSWYgdGhlIG51bWJlciBpcyAwLCBhbGwgYWRqYWNlbnQgY2VsbHMgYXJlIGF1dG9tYXRpY2FsbHkgcmV2ZWFsZWQuCi0gWW91IG1heSBhbHNvIHBsYWNlIG9yIHJlbW92ZSBhIGZsYWcgb24gYSBjZWxsIHRvIG1hcmsgb3IgdW5tYXJrIGl0IGFzIGEgc3VzcGVjdGVkIG1pbmUuCi0gUmVtb3ZpbmcgZmxhZ3MgaXMgYWxsb3dlZCBhbmQgZW5jb3VyYWdlZCBpZiB5b3VyIGxhdGVyIHJlYXNvbmluZyBzaG93cyB0aGUgZmxhZyB3YXMgaW5jb3JyZWN0LgoKQm9hcmQgU3ltYm9sczoKICAuICBVbnJldmVhbGVkIGNlbGwKICBGICBGbGFnZ2VkIGNlbGwgKHN1c3BlY3RlZCBtaW5lKQogMC04IFJldmVhbGVkIGNlbGwgc2hvd2luZyB0aGUgY291bnQgb2YgYWRqYWNlbnQgbWluZXMKICAqICBNaW5lIChzaG93biBvbmx5IHdoZW4geW91IGhpdCBvbmUpCgpBY3Rpb25zIChvbmUgcGVyIHR1cm4pOgogIHJldmVhbCBSIEMgIC0tIFJldmVhbCB0aGUgY2VsbCBhdCByb3cgUiwgY29sdW1uIEMuCiAgZmxhZyBSIEMgICAgLS0gVG9nZ2xlIGEgZmxhZyBvbiB0aGUgY2VsbCBhdCByb3cgUiwgY29sdW1uIEMgKHBsYWNlIGEgZmxhZyBpZiBub25lIGV4aXN0cywgb3IgUkVNT1ZFIGl0IGlmIGFscmVhZHkgZmxhZ2dlZCkuCgpZb3Ugc2hvdWxkIHNob3cgeW91ciB0aGlua2luZyBwcm9jZXNzLCB0aGVuIG91dHB1dCBleGFjdGx5IE9ORSBhY3Rpb24gaW5zaWRlIGEgYGBgIGJsb2NrLgpGb3IgZXhhbXBsZTogYGBgcmV2ZWFsIDMgMmBgYCBvciBgYGBmbGFnIDAgNGBgYApVc2UgbG9naWMgYW5kIGRlZHVjdGlvbiB0byBhdm9pZCBtaW5lcy4gVGhpbmsgc3RlcC1ieS1zdGVwIGJlZm9yZSBhY3Rpbmcu)YouareaplayerplayingaMinesweepergame\.MinesweeperRules:\-Theboardisagridofcells\.Somecellscontainhiddenmines\.\-YourgoalistorevealallcellsthatdoNOTcontainmines\.\-Whenyourevealacell:\-Ifitcontainsamine,thegameisover\(youlose\)\.\-Ifitdoesnotcontainamine,anumberisshownindicatinghowmanyofits8neighboringcellscontainmines\(0\-8\)\.\-Ifthenumberis0,alladjacentcellsareautomaticallyrevealed\.\-Youmayalsoplaceorremoveaflagonacelltomarkorunmarkitasasuspectedmine\.\-Removingflagsisallowedandencouragedifyourlaterreasoningshowstheflagwasincorrect\.BoardSymbols:\.UnrevealedcellFFlaggedcell\(suspectedmine\)0\-8Revealedcellshowingthecountofadjacentmines\*Mine\(shownonlywhenyouhitone\)Actions\(oneperturn\):revealRC–RevealthecellatrowR,columnC\.flagRC–ToggleaflagonthecellatrowR,columnC\(placeaflagifnoneexists,orREMOVEitifalreadyflagged\)\.Youshouldshowyourthinkingprocess,thenoutputexactlyONEactioninsidea\`\`\`block\.Forexample:\`\`\`reveal32\`\`\`or\`\`\`flag04\`\`\`Uselogicanddeductiontoavoidmines\.Thinkstep\-by\-stepbeforeacting\.

Rush Hour[⬇](data:text/plain;base64,WW91IGFyZSBhIHBsYXllciBzb2x2aW5nIGEgUnVzaCBIb3VyIHNsaWRpbmctYmxvY2sgcHV6emxlLgoKUnVzaCBIb3VyIFF1aWNrIEd1aWRlCkdvYWw6IFNsaWRlIHRoZSByZWQgY2FyIChsYWJlbGVkIEEpIGhvcml6b250YWxseSB1bnRpbCBpdCByZWFjaGVzIHRoZSBleGl0IG9uIHRoZSByaWdodCBlZGdlIG9mIGl0cyByb3cuCgpCb2FyZDoKLSBBIDZ4NiBncmlkIG9mIGNlbGxzLCB6ZXJvLWluZGV4ZWQgKHJvdywgY29sKS4KLSBDYXJzIGFuZCB0cnVja3MgYXJlIGxhYmVsZWQgQSwgQiwgQywgLi4uIEVhY2ggb2NjdXBpZXMgMiBvciAzIGNlbGxzIGluIGEgbGluZS4KLSBUaGUgcmVkIGNhciBBIGlzIGhvcml6b250YWwgYW5kIHNpdHMgb24gdGhlIGV4aXQgcm93OyB0aGUgZXhpdCBpcyBvbiB0aGUgcmlnaHQgZWRnZSBvZiB0aGF0IHJvdy4KLSBIb3Jpem9udGFsIGNhcnMgY2FuIG9ubHkgbW92ZSBsZWZ0IG9yIHJpZ2h0LiBWZXJ0aWNhbCBjYXJzIGNhbiBvbmx5IG1vdmUgdXAgb3IgZG93bi4KLSBDZWxscyBtYXJrZWQgJ3gnIGFyZSB3YWxscyBhbmQgbmV2ZXIgbW92ZS4gRW1wdHkgY2VsbHMgYXJlICcuJyAob3IgJ28nKS4KLSBDYXJzIGNhbm5vdCBvdmVybGFwLCBwYXNzIHRocm91Z2ggZWFjaCBvdGhlciwgb3IgcGFzcyB0aHJvdWdoIHdhbGxzLgoKQWN0aW9uIGZvcm1hdDoKLSBPdXRwdXQgYSBzaW5nbGUgbW92ZSBhcyA8Y2FyPjxzaWduPjxzdGVwcz4uCi0gRm9yIGEgaG9yaXpvbnRhbCBjYXI6ICcrJyBtb3ZlcyByaWdodCwgJy0nIG1vdmVzIGxlZnQ7IEZvciBhIHZlcnRpY2FsIGNhcjogJysnIG1vdmVzIGRvd24sICctJyBtb3ZlcyB1cC4KLSA8c3RlcHM+IGlzIHRoZSBudW1iZXIgb2YgY2VsbHMgdG8gc2xpZGUgKG9taXQgaXQgdG8gc2xpZGUgMSBjZWxsKS4KLSBBbGwtb3Itbm90aGluZzogPHN0ZXBzPiBtdXN0IGJlIGV4YWN0bHkgaG93IGZhciB0aGUgY2FyIGNhbiBzbGlkZS4gT3ZlcnNob290aW5nIChtb3JlIHRoYW4gdGhlIGZyZWUgY2VsbHMpIGRvZXMgbm90aGluZy4KLSBPbmUgc2xpZGUgb2YgYW55IGRpc3RhbmNlIGNvdW50cyBhcyBPTkUgbW92ZTsgcHJlZmVyIGEgc2luZ2xlIG11bHRpLWNlbGwgc2xpZGUgKGUuZy4gQSszKSBvdmVyIHNldmVyYWwgMS1jZWxsIG1vdmVzLgotIEV4YW1wbGVzOiBBKzIgKG1vdmUgY2FyIEEgcmlnaHQgMiBjZWxscyksIEItMSAobW92ZSBjYXIgQiB1cCAxIGNlbGwpLCBDKzMgKG1vdmUgY2FyIEMgZG93biAzIGNlbGxzKS4KCllvdSB3aWxsIGJlIHByb3ZpZGVkIHRoZSBjdXJyZW50IG9ic2VydmF0aW9uLCBwbGVhc2UgZGVjaWRlIG9uIHRoZSBuZXh0IGFjdGlvbi4KWW91IHNob3VsZCBvbmx5IG91dHB1dCB0aGUgTkVYVCBBQ1RJT04gYXQgZWFjaCBpdGVyYXRpb24gaW4gdGhlIGBgYCBibG9jay4KRm9yIGV4YW1wbGUsIGlmIHlvdSB3YW50IHRvIG1vdmUgY2FyIEEgcmlnaHQgMiBjZWxscywgeW91IHNob3VsZCBvdXRwdXQ6IGBgYEErMmBgYApQbGVhc2UgcHV0IHRoZSBmaW5hbCBhY3Rpb24gaW4gYSBgYGAgYmxvY2su)YouareaplayersolvingaRushHoursliding\-blockpuzzle\.RushHourQuickGuideGoal:Slidetheredcar\(labeledA\)horizontallyuntilitreachestheexitontherightedgeofitsrow\.Board:\-A6x6gridofcells,zero\-indexed\(row,col\)\.\-CarsandtrucksarelabeledA,B,C,…Eachoccupies2or3cellsinaline\.\-TheredcarAishorizontalandsitsontheexitrow;theexitisontherightedgeofthatrow\.\-Horizontalcarscanonlymoveleftorright\.Verticalcarscanonlymoveupordown\.\-Cellsmarked'x'arewallsandnevermove\.Emptycellsare'\.'\(or'o'\)\.\-Carscannotoverlap,passthrougheachother,orpassthroughwalls\.Actionformat:\-Outputasinglemoveas<car\><sign\><steps\>\.\-Forahorizontalcar:'\+'movesright,'\-'movesleft;Foraverticalcar:'\+'movesdown,'\-'movesup\.\-<steps\>isthenumberofcellstoslide\(omitittoslide1cell\)\.\-All\-or\-nothing:<steps\>mustbeexactlyhowfarthecarcanslide\.Overshooting\(morethanthefreecells\)doesnothing\.\-OneslideofanydistancecountsasONEmove;preferasinglemulti\-cellslide\(e\.g\.A\+3\)overseveral1\-cellmoves\.\-Examples:A\+2\(movecarAright2cells\),B\-1\(movecarBup1cell\),C\+3\(movecarCdown3cells\)\.Youwillbeprovidedthecurrentobservation,pleasedecideonthenextaction\.YoushouldonlyoutputtheNEXTACTIONateachiterationinthe\`\`\`block\.Forexample,ifyouwanttomovecarAright2cells,youshouldoutput:\`\`\`A\+2\`\`\`Pleaseputthefinalactionina\`\`\`block\.

ALFWorld[⬇](data:text/plain;base64,WW91IGFyZSBhbiBleHBlcnQgYWdlbnQgY29tcGxldGluZyBob3VzZWhvbGQgdGFza3MgaW4gYW4gZW1ib2RpZWQgZW52aXJvbm1lbnQuIFlvdXIgdGFzayBpcyB0byBjb21wbGV0ZSBob3VzZWhvbGQgdGFza3MgYnkgbmF2aWdhdGluZyByb29tcyBhbmQgaW50ZXJhY3Rpbmcgd2l0aCBvYmplY3RzLgoKQWN0aW9uIFNwYWNlOgpZb3VyIGFjdGlvbiBtdXN0IGJlIG9uZSBvZiB0aGUgZm9sbG93aW5nLCBzdHJpY3RseSBmb2xsb3dpbmcgdGhlIGNvbW1hbmQgKGFyZ3VtZW50KSBmb3JtYXQuCgpOYXZpZ2F0aW9uICYgT2JzZXJ2YXRpb24KLSBsb29rOiBMb29rIGFyb3VuZCB5b3VyIGN1cnJlbnQgbG9jYXRpb24gdG8gZ2V0IG1vcmUgZGV0YWlscy4KLSBpbnZlbnRvcnk6IENoZWNrIHRoZSBvYmplY3QgeW91IGFyZSBjdXJyZW50bHkgaG9sZGluZyAoeW91IGNhbiBvbmx5IGhvbGQgb25lKS4KLSBnbyB0byAocmVjZXB0YWNsZSk6IE1vdmUgdG8gYSByZWNlcHRhY2xlIChlLmcuLCB0YWJsZSwgZnJpZGdlLCBzaW5rKS4KCkludGVyYWN0aW5nIHdpdGggUmVjZXB0YWNsZXMKLSBvcGVuIChyZWNlcHRhY2xlKTogT3BlbiBhIHJlY2VwdGFjbGUuCi0gY2xvc2UgKHJlY2VwdGFjbGUpOiBDbG9zZSBhIHJlY2VwdGFjbGUuCgpJbnRlcmFjdGluZyB3aXRoIE9iamVjdHMKLSB0YWtlIChvYmplY3QpIGZyb20gKHJlY2VwdGFjbGUpOiBQaWNrIHVwIGFuIG9iamVjdCBmcm9tIGEgcmVjZXB0YWNsZS4KLSBtb3ZlIChvYmplY3QpIHRvIChyZWNlcHRhY2xlKTogUGxhY2UgdGhlIG9iamVjdCB5b3UgYXJlIGhvbGRpbmcgaW50byBvciBvbnRvIGEgcmVjZXB0YWNsZS4KLSBleGFtaW5lIChvYmplY3QpOiBFeGFtaW5lIGFuIG9iamVjdCBjbG9zZWx5IHRvIGxlYXJuIGl0cyBwcm9wZXJ0aWVzLgoKQ2hhbmdpbmcgT2JqZWN0IFN0YXRlcwotIGhlYXQgKG9iamVjdCkgd2l0aCAocmVjZXB0YWNsZSk6IEhlYXQgYW4gb2JqZWN0IHdpdGggYSBkZXZpY2UgKGUuZy4sIG1pY3Jvd2F2ZSkuCi0gY29vbCAob2JqZWN0KSB3aXRoIChyZWNlcHRhY2xlKTogQ29vbCBhbiBvYmplY3Qgd2l0aCBhIGRldmljZSAoZS5nLiwgZnJpZGdlKS4KLSBjbGVhbiAob2JqZWN0KSB3aXRoIChyZWNlcHRhY2xlKTogQ2xlYW4gYW4gb2JqZWN0IHdpdGggYSBkZXZpY2UgKGUuZy4sIHNpbmspLgotIHNsaWNlIChvYmplY3QpIHdpdGggKG9iamVjdCk6IFNsaWNlIGFuIG9iamVjdCB1c2luZyBhIHNoYXJwIG9iamVjdCAoZS5nLiwga25pZmUpLgoKSW1wb3J0YW50IFJ1bGVzOgoxLiBZb3UgbXVzdCBmaXJzdCBuYXZpZ2F0ZSB0byBhIGxvY2F0aW9uIGJlZm9yZSBpbnRlcmFjdGluZyB3aXRoIG9iamVjdHMgdGhlcmUKMi4gWW91IGNhbiBvbmx5IGhvbGQgb25lIG9iamVjdCBhdCBhIHRpbWUKMy4gU29tZSBvYmplY3RzIG5lZWQgdG8gYmUgaGVhdGVkLCBjb29sZWQsIG9yIGNsZWFuZWQgYmVmb3JlIHBsYWNpbmcgdGhlbQo0LiBBbHdheXMgY2hlY2sgYXZhaWxhYmxlIGFjdGlvbnMgdG8gc2VlIHdoYXQgYWN0aW9ucyBhcmUgY3VycmVudGx5IHZhbGlkCgpSZXNwb25zZSBGb3JtYXQ6ClRoaW5rIHRocm91Z2ggeW91ciBhcHByb2FjaCBzdGVwIGJ5IHN0ZXAsIHRoZW4gcHJvdmlkZSB5b3VyIGFjdGlvbiBpbiBhIGBgYCBibG9jay4KRm9yIGV4YW1wbGU6IGBgYGdvIHRvIGNvdW50ZXJ0b3AgMWBgYApBbHdheXMgcHJvdmlkZSBleGFjdGx5IE9ORSBhY3Rpb24gYXQgYSB0aW1lLg==)Youareanexpertagentcompletinghouseholdtasksinanembodiedenvironment\.Yourtaskistocompletehouseholdtasksbynavigatingroomsandinteractingwithobjects\.ActionSpace:Youractionmustbeoneofthefollowing,strictlyfollowingthecommand\(argument\)format\.Navigation&Observation\-look:Lookaroundyourcurrentlocationtogetmoredetails\.\-inventory:Checktheobjectyouarecurrentlyholding\(youcanonlyholdone\)\.\-goto\(receptacle\):Movetoareceptacle\(e\.g\.,table,fridge,sink\)\.InteractingwithReceptacles\-open\(receptacle\):Openareceptacle\.\-close\(receptacle\):Closeareceptacle\.InteractingwithObjects\-take\(object\)from\(receptacle\):Pickupanobjectfromareceptacle\.\-move\(object\)to\(receptacle\):Placetheobjectyouareholdingintoorontoareceptacle\.\-examine\(object\):Examineanobjectcloselytolearnitsproperties\.ChangingObjectStates\-heat\(object\)with\(receptacle\):Heatanobjectwithadevice\(e\.g\.,microwave\)\.\-cool\(object\)with\(receptacle\):Coolanobjectwithadevice\(e\.g\.,fridge\)\.\-clean\(object\)with\(receptacle\):Cleananobjectwithadevice\(e\.g\.,sink\)\.\-slice\(object\)with\(object\):Sliceanobjectusingasharpobject\(e\.g\.,knife\)\.ImportantRules:1\.Youmustfirstnavigatetoalocationbeforeinteractingwithobjectsthere2\.Youcanonlyholdoneobjectatatime3\.Someobjectsneedtobeheated,cooled,orcleanedbeforeplacingthem4\.AlwayscheckavailableactionstoseewhatactionsarecurrentlyvalidResponseFormat:Thinkthroughyourapproachstepbystep,thenprovideyouractionina\`\`\`block\.Forexample:\`\`\`gotocountertop1\`\`\`AlwaysprovideexactlyONEactionatatime\.

WebShop[⬇](data:text/plain;base64,WW91IGFyZSBhbiBleHBlcnQgYWdlbnQgY29tcGxldGluZyBhIHdlYi1iYXNlZCBzaG9wcGluZyB0YXNrLiBZb3UgbmVlZCB0byBpbnRlcmFjdCB3aXRoIHRoZSB3ZWIgZW52aXJvbm1lbnQgdG8gY29tcGxldGUgdGhlIHRhc2suCgpBdmFpbGFibGUgYWN0aW9uczoKLSBzZWFyY2hbcXVlcnldOiBTZWFyY2ggZm9yIHByb2R1Y3RzIHVzaW5nIGtleXdvcmRzCi0gY2xpY2tbZWxlbWVudF06IENsaWNrIG9uIGEgcGFnZSBlbGVtZW50IChwcm9kdWN0IGxpbmssIG9wdGlvbiwgQnV5IE5vdywgZXRjLikKCllvdSB3aWxsIGJlIHByb3ZpZGVkIHRoZSBjdXJyZW50IHN0YXRlIG9mIHRoZSB3ZWJwYWdlLCBwbGVhc2UgZGVjaWRlIG9uIHRoZSBuZXh0IGFjdGlvbi4KWW91IHNob3VsZCBzaG93IHlvdXIgdGhvdWdodCBwcm9jZXNzIGFuZCB0aGVuIHB1dCB0aGUgZmluYWwgYWN0aW9uIGluIGEgYGBgIGJsb2NrLgpZb3Ugc2hvdWxkIG9ubHkgb3V0cHV0IHRoZSBORVhUIEFDVElPTiBhdCBlYWNoIGl0ZXJhdGlvbiBpbiB0aGUgYGBgIGJsb2NrLgpGb3IgZXhhbXBsZSwgaWYgeW91IHdhbnQgdG8gc2VhcmNoIGZvciBzaG9lcywgeW91IHNob3VsZCBvdXRwdXQ6IGBgYHNlYXJjaFtzaG9lc11gYGAKSWYgeW91IHdhbnQgdG8gY2xpY2sgQnV5IE5vdywgeW91IHNob3VsZCBvdXRwdXQ6IGBgYGNsaWNrW0J1eSBOb3ddYGBgClBsZWFzZSBzaG93IHlvdXIgdGhpbmtpbmcgcHJvY2VzcyBhbmQgcHV0IHRoZSBmaW5hbCBhY3Rpb24gaW4gYSBgYGAgYmxvY2suCk91dHB1dCBleGFjdGx5IE9ORSBhY3Rpb24gcGVyIHR1cm4u)Youareanexpertagentcompletingaweb\-basedshoppingtask\.Youneedtointeractwiththewebenvironmenttocompletethetask\.Availableactions:\-search\[query\]:Searchforproductsusingkeywords\-click\[element\]:Clickonapageelement\(productlink,option,BuyNow,etc\.\)Youwillbeprovidedthecurrentstateofthewebpage,pleasedecideonthenextaction\.Youshouldshowyourthoughtprocessandthenputthefinalactionina\`\`\`block\.YoushouldonlyoutputtheNEXTACTIONateachiterationinthe\`\`\`block\.Forexample,ifyouwanttosearchforshoes,youshouldoutput:\`\`\`search\[shoes\]\`\`\`IfyouwanttoclickBuyNow,youshouldoutput:\`\`\`click\[BuyNow\]\`\`\`Pleaseshowyourthinkingprocessandputthefinalactionina\`\`\`block\.OutputexactlyONEactionperturn\.

### C\.2Environment Implementation

The three environments share the same interface but differ in their state encoding, action semantics, and termination rules\. Sokoban and Rush Hour pair a symbolic grid with an explicit zero\-indexed coordinate listing, whereas Minesweeper uses a symbolic grid with indexed rows and columns\. All environments give a single sparse terminal reward of11on success and0otherwise\.

##### Sokoban\.

The board uses the symbols\#\(wall\),\_\(empty\),O\(target\),X\(box\),\*\(box on target\),P\(player\), andS\(player on target\)\. The four actionsUp/Down/Left/Rightmove the player, pushing a box one cell when the cell behind it is free; boxes cannot be pulled and walls are impassable\. The episode ends in success when every box covers a target, or otherwise on a detected deadlock or the step budget\.

##### Minesweeper\.

Only revealed information is shown: an unrevealed cell is\., a flag isF, a revealed count is a digit0–8, and a mine is\*\(shown only when hit\); a numeric header indexes the rows and columns\. The actions arereveal R Candflag R C, where a flag toggles a marker and revealing a0cell flood\-fills its zero\-valued neighborhood\. The episode ends in failure on hitting a mine, in success once every non\-mine cell is revealed, or on the step budget\. Each instance fixes a latent mine layout and a first\-click cell that the environment reveals before the agent acts, so every rollout starts from the same partially revealed board; this removes the initial blind guess that standard Minesweeper would otherwise require\.

##### Rush Hour\.

Vehicles are labeledA,B,C, …by index, with the target red carAhorizontal on the exit row; empty cells are\., walls arex, and the exit lies at the right edge ofA’s row\. An action⟨\\langlecar⟩⟨±⟩⟨\\rangle\\langle\\pm\\rangle\\langlesteps⟩\\rangleslides one vehicle along its orientation \(\+\+is right or down,−\-is left or up\) by a given number of cells, and is all\-or\-nothing: it executes only if every intermediate cell is free, so a blocked or overshooting move leaves the board unchanged\. The episode ends in success whenAreaches the exit, or otherwise when the step budget is exhausted\.

### C\.3Solver Implementation

Each game provides a solver\-derived costN​\(s\)N\(s\)that measures the remaining work from statess\. We define the potentialΦ​\(s\)=−N​\(s\)\\Phi\(s\)=\-N\(s\)and per\-step oracle advantageA​\(st,at\)=Φ​\(st\+1\)−Φ​\(st\)=N​\(st\)−N​\(st\+1\)A\(s\_\{t\},a\_\{t\}\)=\\Phi\(s\_\{t\+1\}\)\-\\Phi\(s\_\{t\}\)=N\(s\_\{t\}\)\-N\(s\_\{t\+1\}\)\. In the shortest\-path domains, this gives\+1\+1to an optimal move,0to a wasteful move, and a negative score to harmful moves\. Minesweeper uses the analogous solver\-completion cost defined below\. The solver is queried on states visited along each rollout\.

##### Sokoban\.

We computeN​\(s\)N\(s\)by A∗over states\(player,\{boxes\}\)\(\\textit\{player\},\\\{\\textit\{boxes\}\\\}\)with a minimum\-cost box\-to\-target assignment as an admissible heuristic\. The search returns the shortest solution within its node budget and remains cheap because the training tiers have few boxes on small grids\. The same solver also supports the deadlock check used for optional early termination\.

##### Minesweeper\.

Partial observability makes an optimal deterministic cost\-to\-go ill\-defined, so hereK​\(s\)K\(s\)measures the work of a deterministic peek\-free solver\. Using constraint reasoning and global mine probabilities,K​\(s\)K\(s\)is the number of reveal actions needed to clear all safe cells, or\+∞\+\\inftyif the solver rollout fails, including when a required probabilistic reveal hits a mine\. Because each instance fixes its latent mine layout and first\-click reveal \(Appendix[C\.2](https://arxiv.org/html/2607.25308#A3.SS2)\),K​\(s\)K\(s\)is deterministic for that instance while the agent remains partially observed\. The oracle advantage isK​\(st\)−K​\(st\+1\)K\(s\_\{t\}\)\-K\(s\_\{t\+1\}\)\.

##### Rush Hour\.

The training oracle uses a different solver from the one that generates the data\. Data generation validates each board with a bounded IDA∗search \(Appendix[B\.1](https://arxiv.org/html/2607.25308#A2.SS1)\)\. For training, we instead precompute a shortest\-path table over the board’s reachable component, giving exactN​\(s\)N\(s\)lookups within the configured state cap; larger components fall back to bounded IDA∗\. One slide of any distance counts as a single move\.

![Refer to caption](https://arxiv.org/html/2607.25308v1/x10.png)

![Refer to caption](https://arxiv.org/html/2607.25308v1/x11.png)

Figure 6:Solver overhead on Sokoban\.Top: wall\-clock breakdowns at three granularities\. The left pie decomposes an average batch\-level optimizer step \(190\.0190\.0s\), which includes the parallel collection of128128trajectories \(1616prompts×8\\times\\,8rollouts\), the policy update, and other operations\. Rollout collection, policy update, and other operations account for60\.7%60\.7\\%,15\.5%15\.5\\%, and23\.7%23\.7\\%of step time, respectively; the last category consists mainly of periodic validation and checkpointing\. The middle pie shows that LLM generation accounts for99\.9%99\.9\\%of the runtime of a single trajectory, while the right pie shows that solver queries account for8\.4%8\.4\\%of a single environment step\.Bottom: the solver’s time share across increasingly broad scopes on a logarithmic scale\. Accounting for parallel rollout collection, its estimated share decreases from8\.43%8\.43\\%of an environment step to0\.01%0\.01\\%of a trajectory and7373ppm of a training step\.

### C\.4Learned Value Network as a Solver

To test whether an exact solver is required at deployment, we replace the Rush Hour oracle with a DQN\-based value network\. A masked Double DQN encodes the6×66\{\\times\}6board with a small transformer and outputs oneQQ\-value per action; illegal actions are masked, andV​\(s\)=maxa∈𝒜​\(s\)⁡Q​\(s,a\)V\(s\)=\\max\_\{a\\in\\mathcal\{A\}\(s\)\}Q\(s,a\)\. The backend returns the cost surrogateN^​\(s\)=−scale⋅V​\(s\)\\widehat\{N\}\(s\)=\-\\text\{scale\}\\cdot V\(s\), so the environment computesA​\(st,at\)=N^​\(st\)−N^​\(st\+1\)=scale​\[V​\(st\+1\)−V​\(st\)\]A\(s\_\{t\},a\_\{t\}\)=\\widehat\{N\}\(s\_\{t\}\)\-\\widehat\{N\}\(s\_\{t\+1\}\)=\\text\{scale\}\\,\[V\(s\_\{t\+1\}\)\-V\(s\_\{t\}\)\]\. Solved states use a fixed value above the non\-terminal network range, ensuring that a solving move receives positive advantage\.

We train the network in three stages on the same underlying ID split used for LLM training, without generating new puzzle instances\. The base network learns from a terminal success reward with a per\-step penalty\. We then apply two warm\-started potential\-regression stages: the first distills a one\-step lookahead potential, while the second repeats the one\-step target and adds the geometric prior−0\.05​b​\(s\)\-0\.05b\(s\), whereb​\(s\)b\(s\)counts occupied cells between the red car and the exit\. These optimization targets use game rewards, frozen network predictions, game dynamics, and the geometric prior, but no solver\-distance targets\. Hyperparameters are listed in Table[4](https://arxiv.org/html/2607.25308#A3.T4)\.

Table 4:Training and deployment configuration of the DQN\-based value network\. All stages use the same architecture and warm\-start from the preceding checkpoint\.SettingValueEncoderTransformer,dmodel=128d\_\{\\text\{model\}\}\{=\}128,88heads,33layers,512512\-d outputBase RL algorithmMasked Double DQN,nn\-step33,γ=0\.99\\gamma\{=\}0\.99Base rewardTerminal success indicator minus0\.010\.01per stepBase training steps3×1063\{\\times\}10^\{6\}Distillation objectiveTwo stages of one\-step potential regressionGeometric prior blend−0\.05×\-0\.05\\timesoccupied path\-cell count \(second stage\)Distillation epochs150150per stageLearning rate10−410^\{\-4\}\(base\) /10−310^\{\-3\},5×10−45\{\\times\}10^\{\-4\}\(distill\)Training boards8,0008\{,\}000puzzles from the ID training splitDeploymentscale=2\\text\{scale\}\{=\}2, solved\-state value=1\.0\{=\}1\.0
### C\.5Equivalence to Cross\-Entropy Distillation

This section formalizes the distillation interpretation of the combined training rule[Equation 8](https://arxiv.org/html/2607.25308#S2.E8)\. We prove that, under four explicit assumptions, the implicit objective of the solver\-shaped GRPO update is a task return regularized by the cross\-entropy between the student and the solver\. We then decompose this cross\-entropy to reveal both a KL\-divergence penalty and a mode\-seeking entropy reduction, derive the closed\-form optimal policy, characterize the full\-domain behavior when the small\-signal assumption is relaxed, and give a performance\-improvement guarantee via the Performance Difference Lemma\.

#### C\.5\.1Notation

We work in the finite\-horizon MDPℳ=\(𝒮,𝒜,P,r,H\)\\mathcal\{M\}=\(\\mathcal\{S\},\\mathcal\{A\},P,r,H\)from[Subsection 2\.1](https://arxiv.org/html/2607.25308#S2.SS1)with undiscounted returns \(γ=1\\gamma=1\)\. Letπθ\\pi\_\{\\theta\}denote the student \(LLM\) policy andπSolver\\pi\_\{\\text\{Solver\}\}the solver’s implicit policy\. We writeVtaskπ,Qtaskπ,AtaskπV^\{\\pi\}\_\{\\text\{task\}\},Q^\{\\pi\}\_\{\\text\{task\}\},A^\{\\pi\}\_\{\\text\{task\}\}for the value, action\-value, and advantage functions under the task reward, anddπθ​\(s\)=∑t=0H−1Pr⁡\(st=s∣πθ\)d^\{\\pi\_\{\\theta\}\}\(s\)=\\sum\_\{t=0\}^\{H\-1\}\\Pr\(s\_\{t\}=s\\mid\\pi\_\{\\theta\}\)for the \(unnormalized\) state occupancy measure ofπθ\\pi\_\{\\theta\}, so that∑sdπθ​\(s\)=H\\sum\_\{s\}d^\{\\pi\_\{\\theta\}\}\(s\)=H\. We define the following standard information\-theoretic quantities for any statess:

ℋ\(πθ\(⋅\|s\)\)\\displaystyle\\mathcal\{H\}\\big\(\\pi\_\{\\theta\}\(\\cdot\|s\)\\big\)=−∑aπθ​\(a\|s\)​log⁡πθ​\(a\|s\),\\displaystyle=\-\\textstyle\\sum\_\{a\}\\pi\_\{\\theta\}\(a\|s\)\\log\\pi\_\{\\theta\}\(a\|s\),\(10\)KL\(πθ\(⋅\|s\)∥πSolver\(⋅\|s\)\)\\displaystyle\\mathrm\{KL\}\\big\(\\pi\_\{\\theta\}\(\\cdot\|s\)\\,\\\|\\,\\pi\_\{\\text\{Solver\}\}\(\\cdot\|s\)\\big\)=∑aπθ​\(a\|s\)​log⁡πθ​\(a\|s\)πSolver​\(a\|s\),\\displaystyle=\\textstyle\\sum\_\{a\}\\pi\_\{\\theta\}\(a\|s\)\\log\\frac\{\\pi\_\{\\theta\}\(a\|s\)\}\{\\pi\_\{\\text\{Solver\}\}\(a\|s\)\},\(11\)H\(πθ\(⋅\|s\),πSolver\(⋅\|s\)\)\\displaystyle\\mathrm\{H\}\\big\(\\pi\_\{\\theta\}\(\\cdot\|s\),\\,\\pi\_\{\\text\{Solver\}\}\(\\cdot\|s\)\\big\)=−∑aπθ​\(a\|s\)​log⁡πSolver​\(a\|s\)\.\\displaystyle=\-\\textstyle\\sum\_\{a\}\\pi\_\{\\theta\}\(a\|s\)\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)\.\(12\)The last quantity is the cross\-entropy fromπθ\\pi\_\{\\theta\}toπSolver\\pi\_\{\\text\{Solver\}\}\. These three are related by the identity:

H​\(πθ,πSolver\)=KL​\(πθ∥πSolver\)\+ℋ​\(πθ\),\\mathrm\{H\}\(\\pi\_\{\\theta\},\\,\\pi\_\{\\text\{Solver\}\}\)=\\mathrm\{KL\}\(\\pi\_\{\\theta\}\\,\\\|\\,\\pi\_\{\\text\{Solver\}\}\)\+\\mathcal\{H\}\(\\pi\_\{\\theta\}\),\(13\)which expresses the cross\-entropy as the sum of the KL divergence and the entropy ofπθ\\pi\_\{\\theta\}\.

Throughout, we use the*baseline invariance*property of policy gradients\(Suttonet al\.,[1999](https://arxiv.org/html/2607.25308#bib.bib54)\): for any functionc​\(s\)c\(s\)independent of the action,𝔼a∼πθ​\[∇θlog⁡πθ​\(a\|s\)⋅c​\(s\)\]=0\\mathbb\{E\}\_\{a\\sim\\pi\_\{\\theta\}\}\[\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\|s\)\\cdot c\(s\)\]=0\.

#### C\.5\.2Assumptions

###### Assumption C\.1\(Soft\-Optimal Solver\)\.

There exists a temperatureτ\>0\\tau\>0such that the solver acts as the optimal policy of a soft \(maximum\-entropy\) MDP\(Ziebartet al\.,[2008](https://arxiv.org/html/2607.25308#bib.bib52); Haarnojaet al\.,[2018](https://arxiv.org/html/2607.25308#bib.bib51)\):

πSolver​\(a\|s\)=exp⁡\(1τ​\(QπSolver​\(s,a\)−VπSolver​\(s\)\)\),VπSolver​\(s\)=τ​log​∑a′exp⁡\(QπSolver​\(s,a′\)/τ\)\.\\pi\_\{\\text\{Solver\}\}\(a\|s\)=\\exp\\\!\\Big\(\\tfrac\{1\}\{\\tau\}\\big\(Q^\{\\pi\_\{\\text\{Solver\}\}\}\(s,a\)\-V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\)\\big\)\\Big\),\\qquad V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\)=\\tau\\log\\textstyle\\sum\_\{a^\{\\prime\}\}\\exp\\\!\\big\(Q^\{\\pi\_\{\\text\{Solver\}\}\}\(s,a^\{\\prime\}\)/\\tau\\big\)\.\(14\)

###### Assumption C\.2\(Small\-Signal Regime\)\.

The solver advantages encountered during training satisfy\|AπSolver\|≲1\|A^\{\\pi\_\{\\text\{Solver\}\}\}\|\\lesssim 1\. Since most moves change the cost\-to\-go by0or±1\\pm 1, this holds for the vast majority of training steps\. Under this condition,asinh⁡\(AπSolver\+1\)\\operatorname\{asinh\}\(A^\{\\pi\_\{\\text\{Solver\}\}\}\+1\)is well\-approximated by its first\-order Taylor expansion around11\(the value at an optimal move\)\. This assumption is relaxed in[Section˜C\.5\.5](https://arxiv.org/html/2607.25308#A3.SS5.SSS5)\.

###### Assumption C\.3\(GRPO Consistency\)\.

The group\-relative advantageA^ioutcome\\hat\{A\}^\{\\text\{outcome\}\}\_\{i\}\([2](https://arxiv.org/html/2607.25308#S2.E2)\) is an unbiased estimator of the task advantageAtaskπθA^\{\\pi\_\{\\theta\}\}\_\{\\text\{task\}\}up to a positive scaling constant \(absorbed into the learning rate\)\.

###### Assumption C\.4\(Frozen Visitation Surrogate\)\.

Following standard practice in PPO\-style methods\(Schulmanet al\.,[2017](https://arxiv.org/html/2607.25308#bib.bib53)\), the shaping termα​h​\(A~i,tπSolver\)\\alpha\\,h\(\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\_\{i,t\}\)is treated as a per\-step immediate weight, and its policy\-gradient contribution is computed under a surrogate objective that holds the state visitation distributiondπθd^\{\\pi\_\{\\theta\}\}fixed at the current iterate\.

#### C\.5\.3Lemmas

###### Lemma C\.5\(Advantage–Log\-Probability Identity\)\. Under[Section˜C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2), for all\(s,a\)\(s,a\):AπSolver​\(s,a\)=τ​log⁡πSolver​\(a\|s\)\.A^\{\\pi\_\{\\text\{Solver\}\}\}\(s,a\)=\\tau\\,\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)\.\(15\)

###### Proof\.

Taking the logarithm of[Equation 14](https://arxiv.org/html/2607.25308#A3.E14)giveslog⁡πSolver​\(a\|s\)=1τ​\(QπSolver​\(s,a\)−VπSolver​\(s\)\)=1τ​AπSolver​\(s,a\)\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)=\\frac\{1\}\{\\tau\}\\big\(Q^\{\\pi\_\{\\text\{Solver\}\}\}\(s,a\)\-V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\)\\big\)=\\frac\{1\}\{\\tau\}A^\{\\pi\_\{\\text\{Solver\}\}\}\(s,a\)\. Multiplying both sides byτ\\tauyields[Equation 15](https://arxiv.org/html/2607.25308#A3.E15)\. ∎

Intuition\.Under a soft\-optimal policy, how much better an action is than average \(AπSolverA^\{\\pi\_\{\\text\{Solver\}\}\}\) and how strongly the teacher prefers it \(log⁡πSolver\\log\\pi\_\{\\text\{Solver\}\}\) are the same quantity up to the temperatureτ\\tau\. This translates the advantage signal into a teacher log\-preference signal\.

###### Lemma C\.6\(Shaping Reduces to Scaled Log\-Probability\)\. Under Assumptions[C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2)and[C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2), the shaped solver term in[Equation 8](https://arxiv.org/html/2607.25308#S2.E8)satisfies:α​h​\(A~i,tπSolver\)=β​log⁡πSolver​\(ai,t\|si,t\)\+c0\+O​\(\(AπSolver\)2\),\\alpha\\,h\\\!\\big\(\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\_\{i,t\}\\big\)=\\beta\\,\\log\\pi\_\{\\text\{Solver\}\}\(a\_\{i,t\}\|s\_\{i,t\}\)\+c\_\{0\}\+O\\\!\\big\(\(A^\{\\pi\_\{\\text\{Solver\}\}\}\)^\{2\}\\big\),\(16\)whereβ:=α​τ/\(2​\(RMSℬ​\(g\)\+ϵ\)\)\>0\\beta:=\\alpha\\tau\\big/\\big\(\\sqrt\{2\}\\,\(\\mathrm\{RMS\}\_\{\\mathcal\{B\}\}\(g\)\+\\epsilon\)\\big\)\>0is a batch\-level constant andc0c\_\{0\}is an action\-independent constant that vanishes from the policy gradient by baseline invariance\.

###### Proof\.

Recall thatA~=AπSolver\+1\\widetilde\{A\}=A^\{\\pi\_\{\\text\{Solver\}\}\}\+1\([Equation 5](https://arxiv.org/html/2607.25308#S2.E5)\) andh​\(x\)=g​\(x\)/\(RMS\+ϵ\)h\(x\)=g\(x\)/\(\\text\{RMS\}\+\\epsilon\)withg=asinhg=\\operatorname\{asinh\}\([Equation 7](https://arxiv.org/html/2607.25308#S2.E7)\)\. Writeβ′=α/\(RMS\+ϵ\)\\beta^\{\\prime\}=\\alpha/\(\\text\{RMS\}\+\\epsilon\), soα​h​\(A~\)=β′​asinh⁡\(A\+1\)\\alpha\\,h\(\\widetilde\{A\}\)=\\beta^\{\\prime\}\\,\\operatorname\{asinh\}\(A\+1\)\. Under[Section˜C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2), Taylor\-expand around the optimal\-move pointA=0A=0\(i\.e\.,A~=1\\widetilde\{A\}=1\)\. Usingasinh′⁡\(x\)=1/x2\+1\\operatorname\{asinh\}^\{\\prime\}\(x\)=1/\\sqrt\{x^\{2\}\+1\}:

asinh⁡\(A\+1\)=asinh⁡\(1\)\+112\+1⋅A\+O​\(A2\)=asinh⁡\(1\)\+A2\+O​\(A2\)\.\\operatorname\{asinh\}\(A\+1\)=\\operatorname\{asinh\}\(1\)\+\\frac\{1\}\{\\sqrt\{1^\{2\}\+1\}\}\\cdot A\+O\(A^\{2\}\)=\\operatorname\{asinh\}\(1\)\+\\frac\{A\}\{\\sqrt\{2\}\}\+O\(A^\{2\}\)\.Thusα​h​\(A~\)=β′​asinh⁡\(1\)⏟c0\+β′2​A\+O​\(A2\)\\alpha\\,h\(\\widetilde\{A\}\)=\\underbrace\{\\beta^\{\\prime\}\\operatorname\{asinh\}\(1\)\}\_\{c\_\{0\}\}\+\\frac\{\\beta^\{\\prime\}\}\{\\sqrt\{2\}\}\\,A\+O\(A^\{2\}\)\. By[Section˜C\.5\.3](https://arxiv.org/html/2607.25308#A3.SS5.SSS3),A=τ​log⁡πSolverA=\\tau\\log\\pi\_\{\\text\{Solver\}\}, so the action\-dependent term becomesβ′​τ2​log⁡πSolver=β​log⁡πSolver\\frac\{\\beta^\{\\prime\}\\tau\}\{\\sqrt\{2\}\}\\log\\pi\_\{\\text\{Solver\}\}=\\beta\\log\\pi\_\{\\text\{Solver\}\}\. ∎

Intuition\.Theasinh\\operatorname\{asinh\}function, expanded around the optimal\-move baselineA~=1\\widetilde\{A\}=1, is locally linear inAπSolverA^\{\\pi\_\{\\text\{Solver\}\}\}\. Combined with the batch\-constant RMS normalization, the shaped signal reduces toβ⋅log⁡πSolver\\beta\\cdot\\log\\pi\_\{\\text\{Solver\}\}, a constant coefficient times the teacher’s log\-preference\.

#### C\.5\.4Main Theorem

We now prove[Theorem 2\.1](https://arxiv.org/html/2607.25308#S2.Thmtheorem1)from[Section 2](https://arxiv.org/html/2607.25308#S2), restated here for convenience\.

[Theorem 2\.1](https://arxiv.org/html/2607.25308#S2.Thmtheorem1)\(Implicit Objective of CAST\)\.Under Assumptions[C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2)–[C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2), the policy\-gradient update direction of the training rule[Equation 8](https://arxiv.org/html/2607.25308#S2.E8)equals the gradient of:𝒥ours\(θ\)=𝔼s0∼μ\[Vtaskπθ\(s0\)\]−β𝔼s∼dπθ\[H\(πθ\(⋅\|s\),πSolver\(⋅\|s\)\)\],β=α​τ2​\(RMSℬ​\(g\)\+ϵ\)\.\\mathcal\{J\}\_\{\\text\{ours\}\}\(\\theta\)=\\mathbb\{E\}\_\{s\_\{0\}\\sim\\mu\}\\\!\\big\[V^\{\\pi\_\{\\theta\}\}\_\{\\text\{task\}\}\(s\_\{0\}\)\\big\]\-\\beta\\,\\mathbb\{E\}\_\{s\\sim d^\{\\pi\_\{\\theta\}\}\}\\\!\\big\[\\mathrm\{H\}\\big\(\\pi\_\{\\theta\}\(\\cdot\|s\),\\,\\pi\_\{\\text\{Solver\}\}\(\\cdot\|s\)\\big\)\\big\],\\,\\,\\beta=\\frac\{\\alpha\\,\\tau\}\{\\sqrt\{2\}\\,\(\\mathrm\{RMS\}\_\{\\mathcal\{B\}\}\(g\)\+\\epsilon\)\}\\,\.\(17\)

###### Proof\.

We assemble the lemmas in four steps\.

*Step 1 \(Additivity\)\.*The training rule usesA^i,t=A^ioutcome\+α​h​\(A~i,tπSolver\)\\hat\{A\}\_\{i,t\}=\\hat\{A\}^\{\\text\{outcome\}\}\_\{i\}\+\\alpha\\,h\(\\widetilde\{A\}^\{\\pi\_\{\\text\{Solver\}\}\}\_\{i,t\}\)as the advantage weight\. Since the policy gradient is linear in the advantage weight, the update decomposes asgours=gGRPO\+gshapeg\_\{\\text\{ours\}\}=g\_\{\\text\{GRPO\}\}\+g\_\{\\text\{shape\}\}\.

*Step 2 \(GRPO→\\totask return\)\.*By[Section˜C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2)and the policy gradient theorem\(Suttonet al\.,[1999](https://arxiv.org/html/2607.25308#bib.bib54)\):

gGRPO∝∇θ𝔼s0∼μ​\[Vtaskπθ​\(s0\)\]\.g\_\{\\text\{GRPO\}\}\\propto\\nabla\_\{\\theta\}\\,\\mathbb\{E\}\_\{s\_\{0\}\\sim\\mu\}\[V^\{\\pi\_\{\\theta\}\}\_\{\\text\{task\}\}\(s\_\{0\}\)\]\.
*Step 3 \(Shaping→\\tonegative cross\-entropy\)\.*By[Section˜C\.5\.3](https://arxiv.org/html/2607.25308#A3.SS5.SSS3), the shaping weight reduces toβ​log⁡πSolver​\(a\|s\)\\beta\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)plus an action\-independent constant\. Sincelog⁡πSolver\\log\\pi\_\{\\text\{Solver\}\}does not depend onθ\\theta, by[Section˜C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2)the shaping term is the gradient of a surrogate:

gshape=∇θ\(β𝔼s∼dπθ,a∼πθ\[logπSolver\(a\|s\)\]\)=−∇θ\(β𝔼s∼dπθ\[H\(πθ\(⋅\|s\),πSolver\(⋅\|s\)\)\]\),g\_\{\\text\{shape\}\}=\\nabla\_\{\\theta\}\\Big\(\\beta\\,\\mathbb\{E\}\_\{s\\sim d^\{\\pi\_\{\\theta\}\},\\,a\\sim\\pi\_\{\\theta\}\}\\big\[\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)\\big\]\\Big\)=\-\\nabla\_\{\\theta\}\\Big\(\\beta\\,\\mathbb\{E\}\_\{s\\sim d^\{\\pi\_\{\\theta\}\}\}\\big\[\\mathrm\{H\}\\big\(\\pi\_\{\\theta\}\(\\cdot\|s\),\\,\\pi\_\{\\text\{Solver\}\}\(\\cdot\|s\)\\big\)\\big\]\\Big\),where the last equality uses the definition of cross\-entropy[Equation 12](https://arxiv.org/html/2607.25308#A3.E12):𝔼a∼πθ​\[log⁡πSolver​\(a\|s\)\]=−H​\(πθ,πSolver\)\\mathbb\{E\}\_\{a\\sim\\pi\_\{\\theta\}\}\[\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)\]=\-\\mathrm\{H\}\(\\pi\_\{\\theta\},\\pi\_\{\\text\{Solver\}\}\)\.

*Step 4 \(Combine\)\.*Summing Steps 2 and 3 directly yields[Equation 17](https://arxiv.org/html/2607.25308#A3.E17)\. ∎

Reading the theorem\.GRPO provides the “do the task right” gradient; the shaped solver advantage provides the “act like the teacher” gradient\. The teacher’s signal enters through the cross\-entropyH​\(πθ,πSolver\)\\mathrm\{H\}\(\\pi\_\{\\theta\},\\pi\_\{\\text\{Solver\}\}\), the standard objective for knowledge distillation\(Agarwalet al\.,[2024](https://arxiv.org/html/2607.25308#bib.bib27)\)\. By the decomposition[Equation 13](https://arxiv.org/html/2607.25308#A3.E13), minimizing the cross\-entropy is equivalent to simultaneously minimizingKL​\(πθ∥πSolver\)\\mathrm\{KL\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\text\{Solver\}\}\)\(move toward the solver\) and minimizingℋ​\(πθ\)\\mathcal\{H\}\(\\pi\_\{\\theta\}\)\(reduce entropy\)\. The latter makes the objective*mode\-seeking*: the student concentrates probability on the solver’s preferred actions rather than spreading mass across all modes\. This is the natural behavior of reverse\-KL distillation\.

#### C\.5\.5Corollaries

###### Corollary C\.8\(Closed\-Form Optimal Policy\)\. Fix the state visitation distribution\. The policy that maximizes the per\-state KL\-regularized objectiveℒ​\(π\)=𝔼a∼π​\[Ataskπθ​\(s,a\)\]−β​KL​\(π∥πSolver\)\\mathcal\{L\}\(\\pi\)=\\mathbb\{E\}\_\{a\\sim\\pi\}\[A^\{\\pi\_\{\\theta\}\}\_\{\\text\{task\}\}\(s,a\)\]\-\\beta\\,\\mathrm\{KL\}\(\\pi\\\|\\pi\_\{\\text\{Solver\}\}\)subject to∑aπ​\(a\)=1\\sum\_\{a\}\\pi\(a\)=1is:π∗​\(a\|s\)∝πSolver​\(a\|s\)​exp⁡\(1β​Ataskπθ​\(s,a\)\)\.\\pi^\{\*\}\(a\|s\)\\propto\\pi\_\{\\text\{Solver\}\}\(a\|s\)\\,\\exp\\\!\\Big\(\\frac\{1\}\{\\beta\}\\,A^\{\\pi\_\{\\theta\}\}\_\{\\text\{task\}\}\(s,a\)\\Big\)\.\(19\)

###### Proof\.

Introduce a Lagrange multiplierλ\\lambdafor the normalization constraint:

ℒ=∑aπ​\(a\)​Atask−β​∑aπ​\(a\)​log⁡π​\(a\)πSolver​\(a\)\+λ​\(1−∑aπ​\(a\)\)\.\\mathcal\{L\}=\\textstyle\\sum\_\{a\}\\pi\(a\)A\_\{\\text\{task\}\}\-\\beta\\sum\_\{a\}\\pi\(a\)\\log\\frac\{\\pi\(a\)\}\{\\pi\_\{\\text\{Solver\}\}\(a\)\}\+\\lambda\\big\(1\-\\sum\_\{a\}\\pi\(a\)\\big\)\.Setting∂ℒ/∂π​\(a\)=0\\partial\\mathcal\{L\}/\\partial\\pi\(a\)=0giveslog⁡π​\(a\)πSolver​\(a\)=1β​Atask​\(s,a\)−1−λβ\\log\\frac\{\\pi\(a\)\}\{\\pi\_\{\\text\{Solver\}\}\(a\)\}=\\frac\{1\}\{\\beta\}A\_\{\\text\{task\}\}\(s,a\)\-1\-\\frac\{\\lambda\}\{\\beta\}\. Exponentiating and absorbing theaa\-independent terms into a normalization constant yields[Equation 19](https://arxiv.org/html/2607.25308#A3.E19)\. The second\-order condition∂2ℒ/∂π​\(a\)2=−β/π​\(a\)<0\\partial^\{2\}\\mathcal\{L\}/\\partial\\pi\(a\)^\{2\}=\-\\beta/\\pi\(a\)<0confirms this is a maximum\. ∎

Why the student can surpass the solver\.Equation[Equation 19](https://arxiv.org/html/2607.25308#A3.E19)has the form*posterior*∝\\propto*prior*×\\times*likelihood*: the solver distribution serves as a prior, and the task advantage tilts it exponentially\. In the pure\-distillation limitβ→∞\\beta\\to\\infty, the tilt vanishes andπ∗→πSolver\\pi^\{\*\}\\to\\pi\_\{\\text\{Solver\}\}\. At finiteβ\\beta, the factorexp⁡\(Atask/β\)\\exp\(A\_\{\\text\{task\}\}/\\beta\)letsπ∗\\pi^\{\*\}deviate wherever the task reward warrants it, enabling the student to*surpass*the teacher\.

###### Corollary C\.10\(Full\-Domain Robustified Distillation\)\. Dropping[Section˜C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2)and retaining theasinh\\operatorname\{asinh\}nonlinearity, define the step\-varying effective gain:βeff​\(AπSolver\)=α​τRMSℬ​\(g\)\+ϵ⋅asinh⁡\(AπSolver\+1\)−asinh⁡\(1\)AπSolver\.\\beta\_\{\\text\{eff\}\}\(A^\{\\pi\_\{\\text\{Solver\}\}\}\)=\\frac\{\\alpha\\,\\tau\}\{\\mathrm\{RMS\}\_\{\\mathcal\{B\}\}\(g\)\+\\epsilon\}\\cdot\\frac\{\\operatorname\{asinh\}\(A^\{\\pi\_\{\\text\{Solver\}\}\}\+1\)\-\\operatorname\{asinh\}\(1\)\}\{A^\{\\pi\_\{\\text\{Solver\}\}\}\}\.\(20\)Then[Theorem 2\.1](https://arxiv.org/html/2607.25308#S2.Thmtheorem1)holds withβ\\betareplaced byβeff\\beta\_\{\\text\{eff\}\}: the constant distillation coefficient becomes step\-dependent, automatically down\-weighting outlier steps\. AsAπSolver→0A^\{\\pi\_\{\\text\{Solver\}\}\}\\to 0,βeff→β\\beta\_\{\\text\{eff\}\}\\to\\beta\(by L’Hôpital’s rule, the ratio tends toasinh′⁡\(1\)=1/2\\operatorname\{asinh\}^\{\\prime\}\(1\)=1/\\sqrt\{2\}\), recovering[Theorem 2\.1](https://arxiv.org/html/2607.25308#S2.Thmtheorem1)\.

###### Proof\.

Without the Taylor truncation, the action\-dependent part ofα​h​\(A~\)\\alpha\\,h\(\\widetilde\{A\}\)isβ′​\(asinh⁡\(A\+1\)−asinh⁡\(1\)\)\\beta^\{\\prime\}\\big\(\\operatorname\{asinh\}\(A\+1\)\-\\operatorname\{asinh\}\(1\)\\big\)\(the constantβ′​asinh⁡\(1\)\\beta^\{\\prime\}\\operatorname\{asinh\}\(1\)vanishes by baseline invariance\)\. Factoring outAA:

β′​asinh⁡\(A\+1\)−asinh⁡\(1\)A⋅A=βeffτ⋅τ​log⁡πSolver\\beta^\{\\prime\}\\,\\frac\{\\operatorname\{asinh\}\(A\+1\)\-\\operatorname\{asinh\}\(1\)\}\{A\}\\cdot A=\\frac\{\\beta\_\{\\text\{eff\}\}\}\{\\tau\}\\cdot\\tau\\log\\pi\_\{\\text\{Solver\}\}where the last step uses[Section˜C\.5\.3](https://arxiv.org/html/2607.25308#A3.SS5.SSS3)\. Substitutingβeff\\beta\_\{\\text\{eff\}\}forβ\\betain Step 3 of the theorem proof, the remaining steps are identical\. For large\|A\|\|A\|,βeff\\beta\_\{\\text\{eff\}\}decreases becauseasinh\\operatorname\{asinh\}grows only logarithmically whileAAgrows linearly, so the ratio shrinks\. ∎

Intuition\.Theasinh\\operatorname\{asinh\}compression causes the effective distillation strength to decrease for steps with unusually large solver advantages \(e\.g\., dead\-state penalties\), matching the design intent of soft\-compressing extreme values\.

#### C\.5\.6Performance Improvement via the Performance Difference Lemma

We now use the Performance Difference Lemma\(Kakade and Langford,[2002](https://arxiv.org/html/2607.25308#bib.bib56)\)to give a complementary perspective: the solver advantage used as a per\-step reward defines an*augmented return*whose maximization provably improves over the solver, with a sub\-optimality bound that scales linearly in the horizonHHrather than quadratically\.

###### Proposition C\.11\(Performance Difference Lemma\(Kakade and Langford,[2002](https://arxiv.org/html/2607.25308#bib.bib56)\)\)\. For any two policiesπ,π′\\pi,\\pi^\{\\prime\}and any reward functionrrin a finite\-horizon MDP:Vrπ​\(s0\)−Vrπ′​\(s0\)=∑t=0H−1𝔼st∼dtπ​\[𝔼a∼π\(⋅\|st\)​\[Arπ′​\(st,a\)\]\]\.V^\{\\pi\}\_\{r\}\(s\_\{0\}\)\-V^\{\\pi^\{\\prime\}\}\_\{r\}\(s\_\{0\}\)=\\sum\_\{t=0\}^\{H\-1\}\\mathbb\{E\}\_\{s\_\{t\}\\sim d^\{\\pi\}\_\{t\}\}\\\!\\Big\[\\mathbb\{E\}\_\{a\\sim\\pi\(\\cdot\|s\_\{t\}\)\}\\\!\\big\[A^\{\\pi^\{\\prime\}\}\_\{r\}\(s\_\{t\},a\)\\big\]\\Big\]\.\(21\)

The PDL states that the value gap between two policies equals the cumulative advantage of the new policyπ\\pievaluated under the old policyπ′\\pi^\{\\prime\}’s value function, but weighted by the new policy’s own state distribution\. It is a standard result in RL theory; we state it without proof\.

###### Proposition C\.12\(Endogenous Reward and Reward Shaping\)\. Under[Section˜C\.5\.2](https://arxiv.org/html/2607.25308#A3.SS5.SSS2), define the solver’s*endogenous reward*\(Liet al\.,[2025](https://arxiv.org/html/2607.25308#bib.bib58)\):r^​\(st,at\)=τ​log⁡πSolver​\(at\|st\)\+VπSolver​\(st\)−VπSolver​\(st\+1\)\.\\hat\{r\}\(s\_\{t\},a\_\{t\}\)=\\tau\\log\\pi\_\{\\text\{Solver\}\}\(a\_\{t\}\|s\_\{t\}\)\+V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\}\)\-V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\+1\}\)\.\(22\)This is a potential\-based reward shaping of the base signalr~​\(s,a\)=τ​log⁡πSolver​\(a\|s\)\\tilde\{r\}\(s,a\)=\\tau\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)with potentialΦ​\(s\)=VπSolver​\(s\)\\Phi\(s\)=V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\)\. By the reward shaping theorem\(Nget al\.,[1999](https://arxiv.org/html/2607.25308#bib.bib57)\), potential\-based shaping preserves the optimal policy:r^\\hat\{r\}andr~\\tilde\{r\}induce the same policy ordering and the same policy gradient\.

###### Proof\.

Writer^​\(st,at\)=r~​\(st,at\)\+Φ​\(st\)−Φ​\(st\+1\)\\hat\{r\}\(s\_\{t\},a\_\{t\}\)=\\tilde\{r\}\(s\_\{t\},a\_\{t\}\)\+\\Phi\(s\_\{t\}\)\-\\Phi\(s\_\{t\+1\}\)\. The added termΦ​\(st\)−Φ​\(st\+1\)\\Phi\(s\_\{t\}\)\-\\Phi\(s\_\{t\+1\}\)is a potential\-based shaping function: it depends only onsts\_\{t\}andst\+1s\_\{t\+1\}and uses the potentialΦ​\(s\)=VπSolver​\(s\)\\Phi\(s\)=V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\)\. By the reward shaping theorem\(Nget al\.,[1999](https://arxiv.org/html/2607.25308#bib.bib57), Theorem 1\), potential\-based shaping preserves the optimal policy and the policy ordering: the optimal policy underr^\\hat\{r\}andr~\\tilde\{r\}is the same, and both rewards induce the same policy gradient \(up to a state\-dependent baseline\)\. ∎

Connection to the implicit objective\.By[Section˜C\.5\.3](https://arxiv.org/html/2607.25308#A3.SS5.SSS3), our training rule usesβ​r~​\(s,a\)/τ=β​log⁡πSolver​\(a\|s\)\\beta\\tilde\{r\}\(s,a\)/\\tau=\\beta\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)as the per\-step advantage weight\.[Section˜C\.5\.6](https://arxiv.org/html/2607.25308#A3.SS5.SSS6)shows that this base signalr~=τ​log⁡πSolver\\tilde\{r\}=\\tau\\log\\pi\_\{\\text\{Solver\}\}is related to the endogenous rewardr^\\hat\{r\}by potential\-based shaping, so they share the same policy gradient\. In our deterministic games with the shortest\-path solver rewardrS=−1r\_\{S\}=\-1per step, a direct calculation shows that the endogenous reward reduces tor^​\(st,at\)=rS=−1\\hat\{r\}\(s\_\{t\},a\_\{t\}\)=r\_\{S\}=\-1for all\(st,at\)\(s\_\{t\},a\_\{t\}\): substitutingAπSolver=\(rS\+VπSolver​\(st\+1\)\)−VπSolver​\(st\)A^\{\\pi\_\{\\text\{Solver\}\}\}=\(r\_\{S\}\+V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\+1\}\)\)\-V^\{\\pi\_\{\\text\{Solver\}\}\}\(s\_\{t\}\)into[Equation 22](https://arxiv.org/html/2607.25308#A3.E22), the value\-function terms telescope and only the base rewardrS=−1r\_\{S\}=\-1remains\. This confirms that the action\-quality information resides entirely in the base signalr~=τ​log⁡πSolver=AπSolver\\tilde\{r\}=\\tau\\log\\pi\_\{\\text\{Solver\}\}=A^\{\\pi\_\{\\text\{Solver\}\}\}, which by[Section˜C\.5\.3](https://arxiv.org/html/2607.25308#A3.SS5.SSS3)equals the solver advantage, and the shaping potential plays no role in the policy gradient\.

Performance improvement guarantee\.Applying the PDL \([Section˜C\.5\.6](https://arxiv.org/html/2607.25308#A3.SS5.SSS6)\) withπ=πθ\\pi=\\pi\_\{\\theta\}andπ′=πSolver\\pi^\{\\prime\}=\\pi\_\{\\text\{Solver\}\}under the augmented rewardraug=rtask\+\(β/τ\)⋅r~r\_\{\\text\{aug\}\}=r\_\{\\text\{task\}\}\+\(\\beta/\\tau\)\\cdot\\tilde\{r\}:

Vraugπθ​\(s0\)−VraugπSolver​\(s0\)=∑t𝔼dtπθ,πθ​\[AraugπSolver​\(st,at\)\]\.V^\{\\pi\_\{\\theta\}\}\_\{r\_\{\\text\{aug\}\}\}\(s\_\{0\}\)\-V^\{\\pi\_\{\\text\{Solver\}\}\}\_\{r\_\{\\text\{aug\}\}\}\(s\_\{0\}\)=\\sum\_\{t\}\\mathbb\{E\}\_\{d^\{\\pi\_\{\\theta\}\}\_\{t\},\\pi\_\{\\theta\}\}\\\!\\big\[A^\{\\pi\_\{\\text\{Solver\}\}\}\_\{r\_\{\\text\{aug\}\}\}\(s\_\{t\},a\_\{t\}\)\\big\]\.\(23\)By[Theorem 2\.1](https://arxiv.org/html/2607.25308#S2.Thmtheorem1), our training rule performs gradient ascent on𝒥ours\\mathcal\{J\}\_\{\\text\{ours\}\}, which is precisely the augmented returnVraugπθV^\{\\pi\_\{\\theta\}\}\_\{r\_\{\\text\{aug\}\}\}\(up to constant boundary terms from reward shaping\)\. The PDL guarantees that whenever𝔼πθ​\[AraugπSolver​\(s,⋅\)\]≥0\\mathbb\{E\}\_\{\\pi\_\{\\theta\}\}\[A^\{\\pi\_\{\\text\{Solver\}\}\}\_\{r\_\{\\text\{aug\}\}\}\(s,\\cdot\)\]\\geq 0at every state, the student’s augmented value improves over the solver’s, i\.e\.,Vraugπθ≥VraugπSolverV^\{\\pi\_\{\\theta\}\}\_\{r\_\{\\text\{aug\}\}\}\\geq V^\{\\pi\_\{\\text\{Solver\}\}\}\_\{r\_\{\\text\{aug\}\}\}\. Moreover, following the analysis ofLiet al\.\([2025](https://arxiv.org/html/2607.25308#bib.bib58)\), if the solver is anϵπ\\epsilon\_\{\\pi\}\-approximate expert \(in the sense thatmaxs,a\|logπSolver\(a\|s\)−logπ∗\(a\|s\)\|≤ϵπ\\max\_\{s,a\}\|\\log\\pi\_\{\\text\{Solver\}\}\(a\|s\)\-\\log\\pi^\{\*\}\(a\|s\)\|\\leq\\epsilon\_\{\\pi\}for the true optimal policyπ∗\\pi^\{\*\}\), the sub\-optimality ofπθ\\pi\_\{\\theta\}under the task reward scales asO​\(H​ϵπ\)O\(H\\epsilon\_\{\\pi\}\), improving over theO​\(H2​ϵπ\)O\(H^\{2\}\\epsilon\_\{\\pi\}\)bound of behavioral cloning\. The linear dependence onHHarises because the reward\-shaping structure ofr^\\hat\{r\}eliminates the compounding\-error problem inherent in imitation learning\(Rosset al\.,[2011](https://arxiv.org/html/2607.25308#bib.bib30)\)\.

#### C\.5\.7Discussion of Assumptions

##### \(A1\) Soft\-optimal solver\.

[Section˜C\.5\.3](https://arxiv.org/html/2607.25308#A3.SS5.SSS3)requires the solver to be a soft\-optimal policy\(Haarnojaet al\.,[2018](https://arxiv.org/html/2607.25308#bib.bib51)\)\. When the solver deviates from optimality, the distillation interpretation degrades proportionally:πSolver\\pi\_\{\\text\{Solver\}\}should be understood as the solver’s empirical behavior distribution\. For our three games, the solvers are near\-optimal, making this assumption well\-justified\.

##### \(A2\) Small signal\.

The linearization ofasinh⁡\(A\+1\)\\operatorname\{asinh\}\(A\+1\)aroundA=0A=0is accurate when\|AπSolver\|≲1\|A^\{\\pi\_\{\\text\{Solver\}\}\}\|\\lesssim 1, which holds for the vast majority of moves\. For the rare large\-magnitude steps \(e\.g\., transitions to dead states\),[Section˜C\.5\.5](https://arxiv.org/html/2607.25308#A3.SS5.SSS5)provides the exact characterization viaβeff\\beta\_\{\\text\{eff\}\}: the qualitative conclusion is unchanged, only the distillation coefficient becomes step\-dependent\.

##### \(A3\) GRPO consistency\.

The group\-relative baseline\(Shaoet al\.,[2024](https://arxiv.org/html/2607.25308#bib.bib1)\)introduces finite\-sample variance but does not bias the gradient direction\. This affects the precision of the task\-return term but not the structural form of the implicit objective\.

##### \(A4\) Frozen visitation surrogate\.

Treating the shaping term as a per\-step immediate weight and freezing the visitation distribution omits the long\-range term∇θdπθ\\nabla\_\{\\theta\}d^\{\\pi\_\{\\theta\}\}, the same approximation used in PPO surrogate objectives\(Schulmanet al\.,[2017](https://arxiv.org/html/2607.25308#bib.bib53)\)\. This is consistent with how the method applies the solver signal on a per\-turn basis in practice\.

### C\.6Training and Evaluation Details

#### C\.6\.1Training Hyperparameters

All backbone RL algorithms we compare \(GRPO, DAPO, and GSPO\) share the same backbone model, training data, rollout budget, and optimizer configuration, and differ only in their policy\-optimization objective\. CAST uses the DAPO objective, while GiGPO is implemented as a separate process\-level baseline\. We list the shared configuration in Table[5](https://arxiv.org/html/2607.25308#A3.T5), the objective\-specific hyperparameters in Table[6](https://arxiv.org/html/2607.25308#A3.T6), and the GiGPO\-specific hyperparameters in Table[7](https://arxiv.org/html/2607.25308#A3.T7)\.

Table 5:Shared training configuration used by all algorithms\.HyperparameterValueBackbone modelQwen3\-4B\-Instruct\-2507Learning rate1e\-6Train batch size16Rollouts per prompt \(GG\)8Training updates \(Sokoban / Minesweeper / Rush Hour\)200 / 400 / 300Table 6:Objective\-specific hyperparameters for each backbone RL algorithm\. The GSPO clip thresholds are much smaller than those of GRPO/DAPO because GSPO clips at the sequence\-level importance ratio rather than the token level, so the two are not on the same scale\.HyperparameterGRPODAPOGSPOLoss modevanillavanillagspoLoss aggregationtoken\-meantoken\-meanseq\-mean\-token\-meanKL loss coefficient0\.0010\.0010\.00\.00\.00\.0Clip ratio \(low\)0\.20\.20\.20\.20\.00030\.0003Clip ratio \(high\)0\.20\.20\.280\.280\.00040\.0004Dual\-clip constantcc3\.03\.03\.03\.03\.03\.0Dynamic sampling \(filter groups\)OffOffOffTable 7:GiGPO\-specific hyperparameters for the process\-level baseline\.HyperparameterValueGiGPO enabledYesStep\-advantage weight1\.01\.0Step\-advantage normalizationmean\_std\_normDiscount factorγ\\gamma0\.950\.95
#### C\.6\.2Evaluation Settings

We evaluate every model under a single protocol across the three games\. Each instance is run as the same multi\-turn agent loop used in training \(Appendix[C\.1](https://arxiv.org/html/2607.25308#A3.SS1)\), and an episode is scored with the sparse0/10/1environment reward: an instance counts as solved only if the agent reaches the goal within the per\-game turn budget\. For each game, we report both the in\-domain \(ID\) tier and the harder unseen\-difficulty \(Unseen\) tier of Table[3](https://arxiv.org/html/2607.25308#A2.T3), evaluating on the200200\-instance test split of each tier\. Every instance is attempted with44independent rollouts\.

##### Open\-source models\.

Open\-source backbones are served locally with SGLang and decoded with temperature0\.60\.6and top\-pp0\.950\.95\. We use a cumulative response budget of16,38416\{,\}384tokens per episode and a configured initial prompt limit of2,0482\{,\}048tokens\. The per\-episode turn budget is game\- and split\-specific:3030turns for Sokoban and Minesweeper ID and4040for their Unseen tier, and2020turns for Rush Hour on both tiers\.

Table 8:Evaluation settings for open\-source models, taken from the evaluation configs\. The per\-episode turn budget varies by game and split\.SettingValueInference engineSGLangTemperature0\.60\.6Top\-pp0\.950\.95Response\-token budget per episode16,38416\{,\}384Configured initial prompt limit2,0482\{,\}048Rollouts per instance44Turn budget \(Sokoban / Minesweeper\)3030\(ID\) /4040\(Unseen\)Turn budget \(Rush Hour\)2020
##### Closed\-source models\.

Closed\-source models are queried through an OpenAI\-compatible API under the same interaction protocol, per\-game turn budgets, and0/10/1scoring as the open\-source setting\. We evaluate six proprietary models: Claude Sonnet 4\.5, Claude Sonnet 4\.6, Claude Opus 4\.5, Claude Opus 4\.6, Gemini 2\.5 Pro, and Gemini 2\.5 Flash, with temperature1\.01\.0, top\-pp1\.01\.0, and44rollouts per instance\. We use the same configured episode\-level response budget and initial\-prompt setting as above\.

Table 9:Evaluation settings for closed\-source models\. The interaction protocol, per\-episode turn budgets, and0/10/1scoring match the open\-source setting \(Table[8](https://arxiv.org/html/2607.25308#A3.T8)\)\.SettingValueServing interfaceOpenAI\-compatible APITemperature1\.01\.0Top\-pp1\.01\.0Response\-token budget per episode16,38416\{,\}384Configured initial prompt limit2,0482\{,\}048Rollouts per instance44Turn budget \(Sokoban / Minesweeper\)3030\(ID\) /4040\(Unseen\)Turn budget \(Rush Hour\)2020