One-sentence Summary

Researchers from The Chinese University of Hong Kong, Shenzhen, Tianjin University, The Hong Kong University of Science and Technology (Guangzhou), and National University of Singapore propose COBRA-Skills, an efficient skill optimization framework that couples contextual-bandit-guided prioritization with evidence-grounded skill evolution to selectively allocate evaluations, achieving the strongest average performance across six heterogeneous agent benchmarks and three target models while reducing optimization cost by 55–58% versus SkillOpt and using only 50 unique optimization examples per benchmark.

Key Contributions

• Agent skill optimization is formulated as budgeted sequential optimization over a dynamically evolving candidate space, where candidate utilities are uncertain and can only be revealed through costly target-agent evaluations.
• COBRA-Skills couples contextual-bandit prioritization with evidence-grounded population evolution to jointly improve evaluation allocation, candidate retention, and continual skill refinement.
• Extensive experiments across six heterogeneous agent benchmarks, three target models (Qwen3.6-35B-A3B, GPT-5.4-Nano, Gemma-4-26B-A4B-it), and multiple execution harnesses show that COBRA-Skills achieves the strongest average performance among compared methods, reduces optimization cost by 55–58% relative to SkillOpt while using only 50 unique optimization examples per benchmark, and remains effective under external harnesses and self-teaching.

Introduction

LLM agents tackling repetitive tasks can leverage reusable “skills” that encode procedural knowledge, but creating reliable skills is challenging. Manual authoring demands domain expertise and effort, while skills generated purely from an LLM’s parametric knowledge often lack grounding and fail to improve downstream performance. Recent approaches ground skill construction in agent execution trajectories and apply iterative evolutionary refinement, yet these methods incur significant efficiency bottlenecks: they must execute candidates on held-out tasks to assess utility, wasting budget on low-quality candidates, and they repeatedly invoke LLMs to re-analyze trajectories and revise skills, driving up token costs.

The authors formulate agent skill optimization as a budgeted sequential decision problem over a dynamically changing candidate space, where each skill’s utility is uncertain and revealed only through costly evaluations. They propose COBRA-Skills, which couples contextual-bandit-guided prioritization with evidence-grounded population evolution. Candidate skills are treated as arms described by semantic embeddings, and a neural reward predictor with an uncertainty bonus (LinearUCB-style) balances exploitation and exploration to allocate evaluations efficiently. The population is periodically refreshed through three evolutionary operators that derive new skills from trajectory evidence—regeneration from no-skill runs, rollout mutation using current skill successes and failures, and crossover that refines a strong backbone with positive and negative evidence—while low-priority skills are pruned. This closed loop continually refines the search space and drastically reduces optimization cost while improving agent performance across diverse benchmarks.

Method

The authors formulate agent skill optimization as a sequential, budgeted problem: given a small optimization set $\mathcal{D}_{\text{opt}}$Dopt​ drawn from the target task distribution and an initial set of no-skill trajectories $\mathcal{T}_0$T0​, a teaching model $M_{\text{teach}}$Mteach​ must iteratively propose candidate skills that are evaluated by a black-box target agent $\mathcal{A}$A on $\mathcal{D}_{\text{opt}}$Dopt​. Each evaluation produces a reward $r_t$rt​ and execution rollouts $\mathcal{T}_t$Tt​, which are fed back to guide the search. The goal is to find a skill $s^*$s∗ that maximizes the expected metric across unseen instances from the same distribution, all within a fixed finite horizon of $T$T rounds.

To address this, COBRA-Skills operates a closed loop that interleaves contextual-bandit-guided selection and evidence-grounded population evolution. At a high level, the method maintains a fixed-size population $P_t$Pt​ of candidate skills. A neural reward predictor, trained on the history of evaluated skills, combines with an uncertainty-aware exploration bonus to compute a priority score for each candidate. The skill with the highest score is selected, deployed by agent $\mathcal{\mathcal{A}}$A, and its outcome enriches the optimization history. Periodically, low-priority skills are pruned and replaced by newly generated candidates produced by evidence-grounded evolutionary operators, allowing the population — and hence the search space — to evolve over time.

Bandit-guided skill search. Because evaluating every candidate is expensive, COBRA-Skills learns a lightweight reward model to allocate its evaluation budget efficiently. Each skill $s$s is first mapped to a semantic embedding $z_s = \phi(s)$zs​=ϕ(s) via a fixed encoder. A two-layer MLP $f_{\theta}$fθ​ with a ReLU hidden layer and scalar output predicts the skill’s reward. The predictor is fitted on the accumulated history $\mathcal{H}_{t-1}$Ht−1​ using mean-squared error with $\ell_2$ℓ2​ regularization:

Relying purely on predicted reward can over-exploit promising skills. The authors therefore augment the prediction with a LinearUCB-style exploration bonus:

where $A_{t-1} = \lambda I + \sum_{i=1}^{t-1} z_{s_i} z_{s_i}^\top$At−1​=λI+∑i=1t−1​zsi​​zsi​⊤​ is the regularized design matrix constructed from previously evaluated embeddings, and $\nu$ν controls exploration strength. This bonus grows for candidates in regions of the embedding space that have been visited infrequently, encouraging exploration.

The exploitation and exploration terms are combined into a priority score:

At each round, the skill with the highest $U_t(s)$Ut​(s) is selected for evaluation. The same score later guides population pruning: the $m$m candidates with the lowest recomputed priority are removed before the evolutionary replenishment step.

Evidence-grounded skill evolution. COBRA-Skills periodically refreshes the population to inject new search directions while retaining promising candidates. After pruning the $m$m lowest-priority skills, the vacant slots are filled by applying three evolutionary operators, all of which ground their generation in actual execution evidence.

• Regeneration constructs a new skill directly from the original no-skill trajectories $\mathcal{T}_0$T0​, without relying on any parent in the current population. This independent sampling diversifies the candidate pool and helps avoid premature convergence.

• Rollout mutation locally refines the skill $s_t$st​ that was selected and evaluated in the current round. It samples both successful and failed trajectories from the newly obtained rollouts $\mathcal{T}_t$Tt​ and uses them as concrete evidence to produce an improved variant. This couples the bandit-guided selection directly with evidence-based local refinement.

• Crossover leverages the full history $\mathcal{H}_t$Ht​ of evaluated skills. The evaluated skills are partitioned into high- and low-performing groups, and candidates are sampled from both. A high-performing skill serves as the backbone, while strategies from other strong skills provide positive evidence and underperforming skills act as negative evidence. The result is a performance-grounded recombination that avoids naive concatenation of parent texts.

Through this interplay of neural reward prediction, principled exploration, and evidence-driven evolutionary updates, COBRA-Skills continually re-focuses its evaluation budget on the most promising and uncertain candidates, iteratively refining skills from limited optimization samples.

Experiment

COBRA-Skills consistently outperforms baselines across six diverse agent benchmarks and three target models, delivering substantial accuracy gains while reducing optimization cost by over half through bandit-guided prioritization and dynamic skill evolution. Ablation studies confirm that both adaptive evaluation and evolutionary refinement are essential, and self-teaching with the target model retains most of the performance at roughly half the cost, showing the method does not rely on a stronger external teacher. Cross-model transfer experiments further indicate that the optimized skills capture reusable task-level strategies rather than model-specific heuristics.

COBRA-Skills attains the highest average accuracy on the Qwen3.6-35B-A3B agent, surpassing all baseline methods including evidence-grounded skill generation and evolutionary optimization. The largest gains over the no-skill baseline appear on LiveMath and SocialMaze, while the method records the best results on five of the six benchmarks. COBRA-Skills raises the average accuracy by 13.1 percentage points over the no-skill baseline on Qwen3.6-35B-A3B. It achieves top performance on Spreadsheet, DocVQA, LiveMath, SocialMaze, and ALFWorld, with especially strong improvements on LiveMath (from 32.3% to 55.3%) and SocialMaze (from 77.3% to 95.5%).

Across all three target models, COBRA-Skills achieves the largest average performance improvement over the no-skill baseline while incurring the lowest total optimization cost and cost per point of gain. Its efficiency advantage comes primarily from using substantially fewer teaching-model tokens than methods such as SkillOpt, reducing overall spending by more than half. COBRA-Skills delivers the highest ΔScore on every model, reaching +13.1 for Qwen3.6-35B-A3B, +26.9 for GPT-5.4-Nano, and the best performance on Gemma-4-26B-A4B-it as reported, with lower total cost than SkillOpt in each case. Compared to SkillOpt, COBRA-Skills cuts total optimization cost by over 55% and lowers cost per point of improvement by more than 60%, driven by a 67–80% reduction in teaching-model token usage. COBRA-Skills uses only 50 optimization examples per benchmark, a smaller pool than Trace2Skill and SkillOpt configurations, yet achieves higher gains, demonstrating efficient allocation of a limited evaluation budget.

COBRA-Skills obtains the highest average accuracy on both agent harnesses, raising the Claude Code baseline from 57.1% to 68.2% and reaching 72.4% on Codex. The gains are broad, with particularly large jumps on SocialMaze and Spreadsheet, while SkillOpt leads on DocVQA and LiveMath. On Claude Code, COBRA-Skills improves average accuracy by 11.1 percentage points over the no-skill baseline and surpasses the next-best method SkillOpt by 4.2 points. COBRA-Skills increases SocialMaze from 38.2% to 73.2% and Spreadsheet from 32.7% to 49.7%, whereas SkillOpt achieves the top individual scores on DocVQA and LiveMath. The same trend extends to Codex, where COBRA-Skills again achieves the highest average accuracy (72.4%), demonstrating consistent generalization across external harnesses.

Ablating either the bandit-guided skill prioritization or the population evolution in COBRA-Skills reduces average accuracy by more than 2 points, and a best-of-30 selection from a fixed pool trails by 2.5 points. These findings show that adaptive evaluation allocation and iterative candidate-space evolution contribute complementary benefits, and that simply generating more skill candidates cannot account for the gains. Without bandit prioritization, average performance drops by 2.2 points; without evolution, it drops by 2.4 points, underscoring the complementary nature of both components. Best-of-30 selection from a static skill pool lags 2.5 points behind the full COBRA-Skills method, confirming that the advantage is not merely due to access to more candidates.

COBRA-Skills is evaluated across multiple large language model agents and external coding harnesses, demonstrating that its bandit-guided skill optimization consistently outperforms baselines with the largest accuracy gains, particularly on complex tasks like LiveMath and SocialMaze. The method also achieves superior cost efficiency, using fewer teaching-model tokens and optimization examples while delivering the highest performance improvements per unit of cost. Ablation studies confirm that both adaptive evaluation allocation and iterative skill evolution are critical, as removing either leads to substantial drops, and simply expanding the candidate pool cannot replicate the benefits.