# SAG-Agent: Enabling Long-Horizon Reasoning in Strategy Games via Dynamic Knowledge Graphs

arXiv: https://arxiv.org/abs/2510.15259 · HTML: https://mlsanity.com/paper/2510.15259/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 17 Oct 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 14 of 14)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [UI-TARS: Pioneering Automated GUI Interaction with Native Agents](https://mlsanity.com/paper/2501.12326/) (2025)
- [Large Language Model-Brained GUI Agents: A Survey](https://mlsanity.com/paper/2411.18279/) (2024)
- [Is Your LLM Secretly a World Model of the Internet? Model-Based Planning for Web Agents](https://mlsanity.com/paper/2411.06559/) (2024)
- [UFO: A UI-Focused Agent for Windows OS Interaction](https://mlsanity.com/paper/2402.07939/) (2024)
- [From LLMs to LLM-based Agents for Software Engineering: A Survey of Current, Challenges and Future](https://mlsanity.com/paper/2408.02479/) (2024)
- [MetaAgents: Large Language Model Based Agents for Decision-Making on Teaming](https://mlsanity.com/paper/2310.06500/) (2023)
- [A Survey on (M)LLM-Based GUI Agents](https://mlsanity.com/paper/2504.13865/) (2025)
- [UFO2: The Desktop AgentOS](https://mlsanity.com/paper/2504.14603/) (2025)
- [OS Agents: A Survey on MLLM-based Agents for General Computing Devices Use](https://mlsanity.com/paper/2508.04482/) (2025)
- [API Agents vs. GUI Agents: Divergence and Convergence](https://mlsanity.com/paper/2503.11069/) (2025)
- [LLM-based Agentic Reasoning Frameworks: A Survey from Methods to Scenarios](https://mlsanity.com/paper/2508.17692/) (2025)
- [DSGBench: A Diverse Strategic Game Benchmark for Evaluating LLM-based Agents in Complex Decision-Making Environments](https://mlsanity.com/paper/2503.06047/) (2025)
- [Rethinking Agent Design: From Top-Down Workflows to Bottom-Up Skill Evolution](https://mlsanity.com/paper/2505.17673/) (2025)

## Built on by (most cited first, 1 of 1)

- [SPIKE: An Adaptive Dual Controller Framework for Cost-Efficient Long-Horizon Game Agents](https://mlsanity.com/paper/2605.18636/) (2026)

## Abstract (arXiv)

Most commodity software lacks accessible Application Programming Interfaces (APIs), requiring autonomous agents to interact solely through pixel-based Graphical User Interfaces (GUIs). In this API-free setting, large language model (LLM)-based agents face severe efficiency bottlenecks: limited to local visual experiences, they make myopic decisions and rely on inefficient trial-and-error, hindering both skill acquisition and long-horizon planning. To overcome these limitations, we propose SAG-Agent, an experience-driven learning framework that structures an agent's raw pixel-level interactions into a persistent State-Action Graph (SAG). SAG-Agent mitigates inefficient exploration by topologically linking functionally similar but visually distinct GUI states, constructing a rich neighborhood of experience that enables the agent to generalize from a diverse set of historical strategies. To facilitate long-horizon reasoning, we design a novel hybrid intrinsic reward mechanism based on the graph topology, combining a state-value reward for exploiting known high-value pathways with a novelty reward that encourages targeted exploration. This approach decouples strategic planning from pure discovery, allowing the agent to effectively value setup actions with delayed gratification. We evaluate SAG-Agent in two complex, open-ended GUI-based decision-making environments (Civilization V and Slay the Spire), demonstrating significant improvements in exploration efficiency and strategic depth over the state-of-the-art methods.