COBRA-Skills: Contextual Bandit-Guided Evolution for Agent Skill Optimization

2609.11682 ↗ · 2026-09-10 · cs.AI

Pingchen Lu, Xiangyi Wang, Xiang Li, Jie Mao, Zikun Qu, Junfeng Luo, Yao Shu, Bryan Kian Hsiang Low, Zhongxiang Dai

The finding

Headline claim

A contextual-bandit-guided skill evolution framework (COBRA-Skills) improves LLM agent benchmark performance over prior skill-optimization methods while cutting optimization cost roughly in half, using only 50 optimization examples per benchmark.

The test

Six heterogeneous agent benchmarks (SearchQA, SpreadsheetBench, DocVQA, LiveMathematicianBench, SocialMaze, ALFWorld) x three target models (Qwen3.6-35B-A3B, GPT-5.4-Nano, Gemma4-26B-A4B-it), three runs each, comparing against no-skill baseline, LLM-authored skills, Trace2Skill, and SkillOpt, with token and dollar cost accounting.

Effect size & scope

Average gains over no-skill baseline: +13.1 (Qwen), +26.9 (GPT-5.4-Nano), +22.5 (Gemma) points; beats SkillOpt averages by ~4-5 points on Qwen and Gemma, ~3 on GPT-Nano. Cost: 55-58% cheaper than SkillOpt ($54.10 vs $121.02 on Qwen), 60-69% lower cost per point of improvement, with teacher token usage of only 3.0M vs 15.2M for SkillOpt. Gains are largest where baselines are weak (e.g., LiveMath 32.3 to 55.3 on Qwen); note some benchmarks show near-flat gains (DocVQA ~+3).

Limitations

Only 50 optimization examples means the optimized skills risk overfitting to the small optimization split despite held-out test claims; skill transfer across models was tested but details are thin; optimization examples are drawn from the same task distribution, so cross-distribution generalization is untested; cost comparisons depend on the specific baseline implementations (SkillOpt, Trace2Skill) which the authors tuned themselves; the token-cost advantage comes largely from delegating execution to the cheaper target model, which inflates target-token usage (115.92M vs 93.77M for SkillOpt). The paper concedes robustness only to harness changes and self-teaching, not to distribution shift.

Counterpoint

Standard method-paper pattern: authors implement their own baselines, pick favorable budgets, and the headline efficiency number depends heavily on which model pays which tokens. Six benchmarks with three runs each is a modest sample; standard errors on some cells are large (SocialMaze ±16.3 for one baseline on Gemma). A neural reward predictor over skill embeddings trained on dozens of observations could be effectively noise plus the LinearUCB exploration bonus, and ablation detail in the visible text is limited. Prompt templates for the evolutionary operators are hand-designed, so gains may hinge on template engineering rather than the bandit machinery.

Economy implication

Little or nothing yet at the macro level: this is a methods paper about making agent-skill optimization cheaper in development. If it replicates, the relevant 12-24 month signal is that reusable agent skills can be induced cheaply (tens of dollars, 50 examples) and transferred across models, which would slightly erode any moat a lab gains from proprietary skill libraries and reduce the data/compute bill for enterprises tuning agents in-house.

Who this matters for

Technical Capability: Agent builders get a concrete recipe for extracting more performance from small models on a fixed small task dataset at low cost, with published code.

Labor & Knowledge Work: If skill induction really costs ~$54 and 50 examples, the marginal cost of automating a new office task type drops further, relevant to how quickly firms can extend agents into new workflows.

Bears on (advisory · papers never write evidence)

[3.1] Inference cost per unit of capability is falling rapidly.

Abstract

Large language model (LLM) agents can benefit from reusable skills distilled from prior task experience, yet existing skill optimization methods often rely on costly execution-based evaluation and substantial task data. We introduce \textbf{COBRA-Skills}, an efficient framework that formulates skill optimization as budgeted sequential optimization over a dynamically evolving candidate space. COBRA-Skills couples contextual-bandit-guided prioritization with evidence-grounded skill evolution, selectively allocating evaluations to promising or informative candidates while continually refining the skill population from execution feedback. Across six heterogeneous agent benchmarks and three target models, COBRA-Skills consistently achieves the strongest average performance among compared methods, while reducing optimization cost by 55--58\% relative to SkillOpt and using only 50 unique optimization examples per benchmark. Further analyses show that COBRA-Skills remains robust to changes in the agent harness and performs effectively when the target model itself is used for skill generation and refinement.