Skill-MAP-Elites: Open-Ended Evolution of Agent Skills through Behavioral Niches

Reusable skills adapt frozen large language model agents by encoding task procedures, tool-use strategies, and recovery policies as inspectable multi-file artifacts. Existing skill-evolution approaches select candidates primarily based on aggregate validation performance or predefined objectives, discarding behaviorally distinct stepping stones whose value emerges on unseen tasks. We formulate skill evolution as a quality-diversity problem and introduce Skill-MAP-Elites, which preserves high-performing skills across execution-grounded behavioral niches. The framework executes each candidate and characterizes its behavior by failure-type coverage, tool-call structure, task-stage coverage, execution cost, robustness, and cross-model gains. It assigns candidates to behavioral niches and selects local elites, separating archive coverage from within-niche optimization. Behavior-level mutations modify procedural structure, recovery strategies, postconditions, parameterization, and abstention policies. Uncertainty-aware admission and periodic reevaluation reduce incorrect elite assignments under sparse and variable rollouts. We evaluate the framework under matched execution budgets on expertise-intensive agent tasks, including transfer to unseen domains, execution models, and agent harnesses, and robustness to schema changes, tool noise, and token-budget perturbations. We compare Skill-MAP-Elites with iterative refinement, sampling-based search, Pareto selection, random archives, and novelty-only search. Descriptor and mutation ablations evaluate whether execution-grounded niches preserve complementary procedural capabilities beyond textual variation and unrestricted candidate retention.