SKILLGRAPH: Skill-Augmented Reinforcement Learning for Agents via Evolving Skill Graphs

Skill libraries have emerged as a promising paradigm for enabling LLM agents to learn from experience, yet existing approaches typically treat skills as flat, independent units with limited explicit modeling of inter-skill relationships. Without such structure, compositional planning is weak, skill granularity is difficult to maintain, and relational signals between skills cannot be accumulated over training. To address these limitations, we propose SKILLGraph, which organizes skills into a structured skill graph with typed edges encoding prerequisite, enhancement, and co-occurrence relations. The framework revolves around three core stages: (1) Graph construction that distills skills from trajectories and organizes them into a directed dependency graph with typed relational edges; (2) Graph-aware retrieval that recovers dependency-respecting skill sequences through seed selection, graph expansion, and topological ordering; (3) Graph evolution that continuously adapts both skills via insertion, merging, splitting, and deprecation and their relations via RL-driven edge reinforcement, co-occurrence discovery, and pruning. These three stages form a closed training loop, enabling the skill structure and the policy to co-evolve. Experiments on ALFWorld, WebShop, and seven search-augmented QA tasks demonstrate state-of-the-art performance, with substantial gains on complex multi-step tasks requiring skill composition.