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

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

한 줄 요약

CAST는 게임 솔버의 상태 가치 변화를 기반으로 LLM 에이전트의 턴 수준 신호를 생성하여 강화학습 성능을 향상시킨다.

핵심 기여도

**Solver-derived credit**: 게임 솔버를 턴 수준 교사로 활용하여 LLM의 각 행동에 대한 정밀한 신용 부여를 정의함.
**Logit-free distillation**: `solver advantage` 최대화가 on-policy distillation과 동등하다는 수학적 증명을 제시하며, `asinh` 변환과 RMS 정규화를 통해 안정성 확보.
**성능 및 일반화**: Sokoban, Minesweeper, Rush Hour에서 기존 방법 대비 1.7–2.0× 빠른 학습 속도와 최고 성능 달성.
**Zero-shot 전이**: ALFWorld와 WebShop에서 학습 없이도 최고 평균 성능 기록.

핵심 아이디어

기존 RLVR은 터미널 보상만을 기반으로 하여 턴 수준의 신호가 부족한 문제가 있었다. CAST는 게임 솔버가 각 상태에 대해 부여하는 `state value` 변화를 기반으로 `solver advantage`를 계산하고, 이를 턴 수준 신호로 활용한다. 이는 LLM이 어떤 행동이 성공에 가까워지는지를 실시간으로 학습할 수 있도록 한다.

수학적으로, `solver advantage`는 LLM의 행동이 상태 가치를 얼마나 증가시키는지를 측정하며, 이는 `on-policy distillation`과 동등한 효과를 가진다. 이론적 분석에 따르면, `solver advantage`는 솔버의 암묵적 행동 분포와 LLM의 분포를 정렬하는 데 충분하다. 이는 `teacher logits` 없이도 효과적인 지도가 가능하다는 것을 의미한다.

기술적 접근법

**Solver Advantage 계산**: LLM이 샘플링한 행동 전후의 `state value`를 비교하여 `solver advantage`를 계산.
**asinh 변환**: 극단적인 값의 영향을 줄이기 위해 `asinh` 함수를 사용하여 신호를 부드럽게 압축.
**Batch-level RMS 정규화**: 도메인 간 스케일 차이를 제거하기 위해 배치 단위 RMS 정규화 적용.
**Solver-advantage weight α**: 턴 신호와 최종 보상 간 가중치 조절. 실험적으로 α=0.1이 최적.
**Solver 대신 학습된 가치 함수 사용 가능성**: 정확한 솔버 없이도 학습된 가치 네트워크로도 CAST 적용 가능.

주요 결과

**Sokoban, Minesweeper, Rush Hour**: 기존 학습된 기반 모델 대비 모든 게임에서 최고 성능.
**DAPO 대비 학습 속도**: 1.7–2.0× 빠른 학습 속도로 최대 성능 달성.
**Zero-shot 성능**: ALFWorld와 WebShop에서 학습 없이도 최고 평균 성능 기록.
**Solver-advantage weight α=0.1**: 훈련 보상과 검증 성능 모두에서 가장 안정적이고 높은 결과.
**asinh + RMS 정규화**: 신호 안정성과 최종 성능에 유의미한 기여.

의의 및 한계

CAST는 터미널 보상만을 기반으로 한 RLVR의 한계를 극복하고, 턴 수준의 정밀 신호를 생성함으로써 LLM 에이전트의 학습 효율을 크게 향상시킨다. 특히, 정확한 솔버 없이도 학습된 가치 함수를 활용할 수 있다는 점에서 실용적 가치가 높다.

그러나, 솔버의 정확성에 따라 성능이 크게 달라질 수 있으며, 솔버가 제공하는 `state value`가 실제 최적 행동과 충분히 일치하지 않을 경우 신호의 신뢰도가 낮아질 수 있다. 또한, `asinh` 변환과 RMS 정규화는 실험적으로 최적화된 파라미터를 필요로 하며, 이는 다른 도메인으로 확장 시 재조정이 필요할 수 있다.

실용적 활용

CAST는 Sokoban, Minesweeper, Rush Hour와 같은 구조화된 게임 환경에서 LLM 에이전트의 학습을 향상시키는 데 유용하며, ALFWorld와 WebShop과 같은 복잡한 대화형 환경으로의 zero-shot 전이에도 적용 가능하다. 이는 LLM 기반 에이전트가 실제 세계에서의 장기적 결정 문제를 해결하는 데 기여할 수 있다.