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

1 Introduction

• The paper focuses on automatically acquiring skills from trajectories, which can expand as agents encounter new tasks and environments.The introduction contrasts automatically acquired skills with manually crafted skills and describes them as more scalable.Source: §1 · p. 1
• Flat skill libraries retrieve mainly by semantic similarity, overlooking skill dependencies and leaving complex tasks without an ordered sequence or structured update cues.The introduction identifies merging redundant skills, splitting overly broad ones, and deprecating obsolete ones as examples of updates that lack structural evidence.Source: §1 · p. 2
• SKILLGRAPH distills skills from interaction trajectories into nodes with prerequisite, enhancement, and co-occurrence edges, then retrieves dependency-ordered sequences and updates the graph using training feedback.The graph and policy form a closed loop: policy-generated trajectories further refine the graph.Source: §1 · p. 2, Figure 1 · p. 2
• SKILLGRAPH achieves state-of-the-art performance across ALFWorld, WebShop, and seven search-augmented QA tasks, with especially strong gains on complex multi-step tasks.The evaluated tasks cover embodied manipulation, web navigation, and information retrieval.Source: §1 · p. 2

Memory mechanisms in agents

• Memory methods store trajectories, compress experience, or apply RL to memory structures; SKILLGRAPH instead represents experience as skill abstractions with typed dependencies and evolves them with the policy.The cited methods include runtime RL on episodic memory, meta-evolving memory systems, learned memory-construction policies, and co-adaptation of policy and memory bank.Source: §2 · p. 3

Graph structures for LLMs

• Prior LLM graph systems model reasoning steps, corpus entities, or task decompositions, while SKILLGRAPH applies graph structures to skill management and continuously adapts topology with policy learning.The cited graph systems include Graph-of-Thought, GraphRAG, and planning graphs.Source: §2 · p. 3

Agent skill evolution

• Voyager and ExpeL accumulate reusable skills or strategies, while SkillRL co-evolves a hierarchical skill bank; SKILLGRAPH adds typed relations and topology evolution.SKILLGRAPH’s distinction is elevating the skill bank into a structured dependency graph.Source: §2 · p. 3

3 SKILLGRAPH

• SKILLGRAPH integrates graph construction, graph-aware retrieval, and graph evolution into a closed-loop training procedure that co-evolves the graph and policy through reinforcement learning.The graph represents skills as nodes and their inter-skill relations as typed edges.Source: §3 · p. 3

3.1 Graph Construction

• Skills distilled from successful and failed trajectories become graph nodes, with prerequisite, enhancement, and co-occurrence edges encoding their relations.Nodes also maintain usage and success statistics, and prerequisite and enhancement edges determine topological levels.Source: §3.1 · pp. 3–4

3.2 Graph-Aware Retrieval

• Retrieval selects active general and task-matched seed skills, expands backward for prerequisites and forward along weighted edges, then topologically orders the resulting sequence.The sequence is capped at Kmax skills and prepended to the task prompt as structured guidance.Source: §3.2 · p. 4

3.3 Graph Evolution

• Because a static graph cannot track policy improvement and shifting skill relations, SKILLGRAPH evolves both skill nodes and edges using trajectory-level feedback at validation steps.The evolution pipeline adjusts available skills and their relations to shape future retrieval.Source: §3.3 · p. 4, §3.3.2 · p. 5

3.3.1 Node-Level: Adaptive Granularity Control

• Node-level updates insert skills for uncovered failures, merge skills with overlapping graph neighborhoods, split broad moderately successful skills, and deprecate frequently used low-success skills.Splitting applies when success is 0.15–0.4 with at least 10 uses; deprecation applies below 0.15 with at least 20 uses.Source: §3.3.1 · pp. 4–5

3.3.2 Edge-Level: Topology Evolution

• Edge-level updates reinforce paths used in successful trajectories, add co-occurrence edges observed in successful episodes, and decay and prune weak edges.Reinforcement increases weights along successful paths; decay applies multiplicatively at checkpoints before edges below the pruning threshold are removed.Source: §3.3.2 · p. 5

3.3.3 Progressive Unlocking

• Progressive unlocking activates level-(L+1) skills only after the average success rate of level-L skills exceeds the unlocking threshold.This makes advanced compositional skills available after their lower-level foundations are reliable.Source: §3.3.3 · p. 5

3.4 Policy Optimization and Closed-Loop Training

• At validation, policy-generated trajectories refine skill nodes and edges, while the updated graph supplies structured retrieval for subsequent policy learning.The procedure initializes skills and relations, retrieves and topologically orders relevant skills, applies GRPO updates, and evolves the graph during training.Source: §3.4 · p. 6

4.1 Experimental Setup

• Evaluation covers six ALFWorld task categories, WebShop, and seven QA benchmarks, with comparisons to closed-source LLMs, memory methods, RL, and memory-augmented RL.Source: §4.1 · pp. 6–7

4.2 Main Results

• On ALFWorld, SKILLGRAPH beats GPT-4o by 42.6 points and Gemini-2.5-Pro by 30.3; on WebShop, it exceeds both by over 48 points.Source: Table 1 · p. 7, §4.2 · p. 7
• Against vanilla GRPO, SKILLGRAPH gains 13.0 points on ALFWorld and 18.3 on WebShop; against SkillRL, it gains 11.7 on WebShop.Source: Table 1 · p. 7, §4.2 · p. 8
• Trained on NQ and HotpotQA, SKILLGRAPH averages 48.9 across seven QA benchmarks and transfers zero-shot to five unseen datasets.Source: Table 2 · p. 8, §4.2 · p. 8

4.3 Analysis

• WebShop’s graph grows from ∼20 to ∼140 nodes, while active nodes plateau as failing skills are deprecated and average node success rises.Source: Figure 2 · p. 8, §4.3 · p. 9
• Removing graph-aware retrieval drops ALFWorld by −31.2; WebShop responds most to removing graph evolution (−14.1) or graph structure (−11.7), while removing cold-start SFT drops both by −17.2.Source: Table 3 · p. 8, §4.3 · pp. 8–9
• SKILLGRAPH surpasses SkillRL after roughly 50 training steps and maintains shorter prompts than flat retrieval throughout training.Source: Figure 3 · p. 9, §4.3 · p. 9

• SKILLGRAPH achieves state-of-the-art performance on ALFWorld, WebShop, and seven search-augmented QA benchmarks, with the largest gains on complex tasks requiring ordered skill composition.Source: §5 · p. 9
• The framework unifies graph construction, graph-aware retrieval, and graph evolution in a closed training loop that co-evolves the skill graph and agent policy through RL.Source: §5 · p. 9
• The framework relies on a strong teacher model, adding inference cost during graph evolution; cross-environment transfer and scaling to larger models and more diverse tasks remain open questions.Source: §5 · p. 9

A Supplementary Details for SKILLGRAPH

• The appendix supplies formal definitions, derivations, and implementation specifics that supplement the method description.Source: A Supplementary Details for SKILLGRAPH · p. 12

A.1 Level Computation

• Skill levels are computed by BFS over directional dependency edges, assigning level 0 to nodes without prerequisite or enhancement parents and otherwise one more than the maximum parent level.Source: §A.1 · p. 12
• Co-occurrence edges are excluded because they represent symmetric association and could introduce cycles; levels are recomputed after each graph evolution step.Source: §A.1 · p. 12

A.2 Edge Initialization

• Initialization adds co-occurrence edges of weight 0.3 between task-specific skills in the same category and enhancement edges of weight 0.2 from each general skill to all task-specific skills; prerequisite edges emerge during graph evolution.Source: §A.2 · p. 12

A.3 Statistics Update

• At validation checkpoints, success and usage counts are updated from the latest trajectory batch; retrieval into a prompt counts as use, and a successful corresponding rollout counts as success.Source: §A.3 · p. 13

A.4 Node Evolution: Additional Details

• New skills begin isolated and gain co-occurrence edges after appearing with an existing skill in at least two successful episodes; merges inherit both nodes’ edges, while split skills receive ordered prerequisite edges and relevant redistributed edges.Source: §A.4 · p. 13

A.5 Progressive Unlocking: Additional Details

• During the first five training steps, only non-deprecated level-0 skills are active; later unlocking uses success rates smoothed with a Beta(1, 1) prior and may unlock multiple levels at one checkpoint.Source: §A.5 · p. 13

• Each skill record contains an identifier, title, principle, applicability condition, and category; SKILLGRAPH adds graph metadata such as level, exposure counts, success rate, creation step, and deprecation status.Source: B Additional Implementation Details · p. 13
• Co-occurrence edges require at least two co-appearances in successful validation episodes, and deprecated nodes remain saved for auditability but are excluded from the active graph.Source: B Additional Implementation Details · p. 13

C Experimental Details

• ALFWorld uses success rate, WebShop uses normalized task score and binary success rate in Table 1 and task score in Table 3, and QA uses exact-match accuracy.The search-augmented QA retriever returns the top 3 passages from a Wikipedia index built with E5; training uses NQ and HotpotQA, with evaluation on seven datasets.Source: C Experimental Details · p. 13
• Training hyperparameters are listed per environment, while SKILLGRAPH-specific hyperparameters are shared across all three environments.Tables 4 and 5 provide these respective settings.Source: C Experimental Details · p. 13, Table 4 · p. 14, Table 5 · p. 14

D Confidence Intervals

• SKILLGRAPH’s results are reported with 95% confidence intervals across benchmarks.Table 6 contains the intervals.Source: D Confidence Intervals · p. 14, Table 6 · p. 15

E Prompt Templates

• Retrieved skills are inserted into prompts in dependency order, while environment-specific variants adapt the action space and observation format.The retrieved skill block is shared across ALFWorld, WebShop, and search-augmented QA; graph ordering is made visible to the policy without a special model architecture.Source: E Prompt Templates · pp. 14–15
• Failure-driven updates ask a teacher model to propose new actionable skills from failed trajectories and avoid duplicating existing skill titles.Separate curator prompts merge semantically overlapping skills and split high-usage, low-success skills into simpler sub-skills.Source: E Prompt Templates · pp. 15–16

F Additional Search Training Results

• The step-200 checkpoint gives the best average search-augmented QA score, although NQ and HotpotQA peak slightly earlier at step 180.The unified step-200 checkpoint is reported in Table 2 for a consistent selection rule; Table 7 covers in-domain NQ and HotpotQA and held-out transfer datasets.Source: Table 7 · p. 16, F Additional Search Training Results · p. 16

G Compute Resources

• Training runs used approximately 280 GPU-hours on a single node with 8 NVIDIA A100 80GB GPUs, 224 CPU cores, and 2048 GB of system memory.Table 8 summarizes dataset, environment, and model licenses; all listed assets are publicly available and permit academic research use.Source: G Compute Resources · p. 16, Table 8 · p. 17, J Asset Licenses · p. 17

H Broader Impact

• The authors identify simulated-environment evaluation as the current scope, with real-world deployment requiring careful validation and additional safety constraints.They also note risks from biased trajectory-derived skills and errors or hallucinated skills introduced by the teacher model; human review may be needed for safety-critical applications.Source: H Broader Impact · p. 17

I LLM Usage Statement

• LLMs serve as teacher models for skill distillation, SFT data generation, and graph evolution, and as the RL-fine-tuned base policy.The authors also report using LLMs to polish manuscript language and state that assisted content was manually reviewed, verified, and edited.Source: I LLM Usage Statement · p. 17

J Asset Licenses

• The paper summarizes licenses for its datasets, environments, and models and states that all assets permit academic research use.The summary is provided in Table 8.Source: J Asset Licenses · p. 17, Table 8 · p. 17