R$^2$Orch: Recursive Self-Improvement for Agent Orchestration via Self-Play within a Skill-Internalization Loop

AI summary

Overview

Research area: Reinforcement learning for LLM-based multi-agent systems, specifically the training of an orchestrator (called the Director) that assembles agent teams into executable graphs, combined with skill internalization and self-play curriculum design.

Technical level: Advanced. The paper combines two-time-scale stochastic approximation, KL-regularized policy optimization, GRPO-style group-relative estimation, Bayesian posterior decisions, and randomized-experiment (Neyman) estimators; the empirical section assumes familiarity with agent-graph orchestration and skill-scaffold training.

Scope: The paper proposes R²Orch, a two-loop self-play framework with a task-selection objective (Recursive Learnability) and a skill-retirement rule (Skill Withdrawal), and evaluates it on twelve benchmarks spanning question answering, math, code, and interactive tasks.

What This Paper Is About

Agent orchestrators that learn to compose teams of agents are usually trained on task pools collected in advance and propped up by "skills" injected into the prompt. This creates three problems: curricula are hand-designed, group-based RL loses its learning signal when every rollout for a task reaches the same outcome (advantage collapse), and skills are kept or retired based on a single noisy score. R²Orch's goal is to make the orchestrator improve itself — choosing its own tasks and retiring its own skills — so that it eventually performs well with no skills in its context at all ("zero-skill deployment").

Key Contributions

1. Recursive Self-Play Orchestration: A two-loop paradigm in which an inner loop (Proposer–Director self-play) improves the orchestrator on self-chosen tasks, and an outer loop improves how the inner loop improves by withdrawing skills. The loops are joined by a downward channel (the objective) and an upward channel (the evidence).
2. Recursive Learnability: A training objective for the Proposer that scores each candidate task by the outcome variance of rollouts that read the context with the candidate skill withheld — formally ℓ_rec(x) = 4·p⁻(1−p⁻), which peaks at p⁻ = 0.5 and vanishes when rollouts collapse to all-right or all-wrong.
3. Skill Withdrawal: A controlled-evaluation mechanism that hides one skill in a random part of each rollout group (n_h hidden rollouts, n_v visible, with n_h > n_v), turning ordinary self-play into a randomized block experiment; an unbiased paired contrast feeds a Bayesian-bootstrap posterior that decides when a skill can leave, at no extra rollouts.
4. Theory and a closed cycle: Propositions 1–3 establish that zero-skill success equals starting success plus inner gains minus outer costs, that a task's gain grows with its Recursive Learnability, and that random hiding makes the paired contrast unbiased — closing the loop where failures become skills, skills become parameters, and withdrawals expose new failures.

Main Findings

• Best on all twelve benchmarks: R²Orch leads every benchmark in Table 1 (five-run mean ± std, each test set 128 items except AIME 2026 with 30). Its IID average is 89.79 ± 1.01 versus 86.00 for PATS, 82.34 for FlowSteer, 81.57 for SESA, and 81.40 for SKILL0; its OOD average is 78.79 ± 0.17 versus 76.13 for PATS and 73.52 for FlowSteer.
• Largest margins on hard and interactive tasks: AIME 2026 accuracy 81.33 ± 2.98 versus 74.00 for PATS and 67.33 for FlowSteer; ALFWorld success rate 90.63 versus 87.97; WebShop (OOD) success rate 91.09 versus 87.97.
• Orchestration, not backbone training, drives the gain: The untrained Qwen3.5-9B backbone scores 61.35 IID / 49.84 OOD and DeepSeek-V4-Flash 69.64 / 66.95; SFT reaches 56.87 / 51.13 and GRPO 61.04 / 52.07, while orchestration methods reach much higher.
• Transfer without retraining: A Director trained with Qwen3.5-9B Workers improves all six other backbones on every benchmark, narrowing the IID range across backbones from 25.7 to 6.4 points; gains are largest on interactive tasks and smallest on math, which is described as near its ceiling.
• Zero-skill accuracy overtakes skill-assisted accuracy midway through training: Because most of each rollout group hides the candidate skill, updates already teach success without it; a skill stops helping before it leaves, keeping the outer cost small.
• Both loops are necessary: Removing Skill Withdrawal entirely (fixed scaffold) drops AIME 2026 from 81.33 to 66.67, ALFWorld from 90.63 to 77.81, and WebShop from 91.09 to 76.09 in the zero-skill ablation (Table 2).
• Withholding the skill matters for task selection: Learnability measured on the current scaffold (skill in context) scores 70.67 on AIME and 86.88 on ALFWorld versus 81.33 and 90.63 for Recursive Learnability, and trails on the OOD mean as well.
• Paired contrasts beat success-rate gates: Success-rate thresholds, preset budgets, and validation gaps trail the paired contrast (AIME: 74.67, 70.67, and 72.67 respectively versus 81.33).
• Proposer behavior shifts as predicted: New groups on tasks of intermediate success rate reach mixed outcomes, and thus a nonzero GRPO signal, about four times as often as at p = 0 or p = 1; the trained Proposer learns to skip already-solved candidates and produces the most distinct graph types.
• Withdrawals are well justified: All 12 withdrawals satisfy the decision rule on the skill's own contrasts, with posterior E[Δ⁺] at most 0.019, and around each withdrawal the seed skill cards no longer raise held-out accuracy.
• Selection is cheap: Because the hidden part of each group already measures the score, task selection adds no rollouts and uses the fewest rollouts and tokens per effective group among the compared Proposer objectives.

Methodology in Plain English

The system has two learned policies. A Director builds an agent graph one edit at a time (add an agent, set its prompt, set its model, set its layer, consider a relation, delete, set output, finish), where each edit is validated before the next. A Proposer chooses which tasks the Director practices on.

During training, the tasks are run in groups of G = n_h + n_v rollouts. Each task comes with a set of retrieved "skills" (procedural hints in the prompt). In a random majority of the group, one candidate skill is hidden; in the rest it stays visible. This single design does two jobs at once. First, the Director's gradient update mostly trains on the skill-hidden context, so it is already learning to work without that skill. Second, comparing the hidden and visible portions gives an unbiased estimate of how much the skill actually helps on that task.

The Proposer is rewarded for proposing tasks whose hidden-context rollouts still disagree with each other — tasks sitting in the learnable middle rather than already solved or hopeless. A KL-regularized objective yields a closed-form "Gibbs curriculum" that tilts the base task distribution toward high-learnability tasks, and the Proposer is updated pairwise.

For skills, the per-task contrasts accumulate into a Bayesian-bootstrap posterior per skill, with Dirichlet weights and a prior record so untested skills can also be sampled. A Thompson draw first tests the skill closest to withdrawal. Bayes decision rules then retire a skill when its expected positive benefit falls below a threshold ε, and admit new skills under an admission risk α, both gated by a minimum record count. New skills are distilled from groups where both the hidden and visible parts fail, so the failures that withdrawals expose become the next things to internalize.

The authors prove three properties: that zero-skill performance decomposes into starting performance plus accumulated inner gains minus withdrawal costs; that a task's achievable gain grows with its Recursive Learnability under a small trust region; and that random hiding makes the skill-effect estimate unbiased.

Why This Matters

Impact on research. The paper reframes two standard failure modes — advantage collapse in group-based RL and one-score-per-skill library drift — as a single experimental-design problem, and shows they can be addressed with the same randomized rollout group already being generated. This removes the need for hand-built curricula, extra rollouts, or leave-one-skill-out validation runs, and it gives a formal accounting (inner gains minus outer costs) for what "self-improvement" actually buys.

Potential real-world applications:

• Multi-step customer-support or IT triage systems, where an orchestrator must assemble and hand off between specialized agents and where each hand-off compounds error.
• Software engineering agents resolving repository issues, matching the SWE-Bench setting where R²Orch reports 42.81 resolved versus 40.47 for the next-best baseline.
• Web navigation and shopping agents (WebShop), where the paper reports both the highest score and the largest transfer gains.
• Clinical and open-domain question answering pipelines (MedQA, HotpotQA, MuSiQue), where routing between retrieval, reasoning, and verification agents is the core difficulty.

Industry relevance. The transfer result is the commercially interesting one: a single Director trained with one Worker backbone improved six other backbones with no retraining and narrowed the IID spread from 25.7 to 6.4 points. That suggests orchestration skill can be trained once and shipped against whatever model is cheapest or most current, and that weaker models benefit most because the graph supplies planning and checking they lack.

Future Directions

• Automatic initial skills. The stated limitation: R²Orch starts from skills hand-customized per dataset, and all subsequent withdrawals, revisions, and distillations build on them; deriving the initial skills automatically for a new domain is left open.
• Pushing further toward and past zero skills. The framework is designed to reach zero-skill deployment; whether the scaffold can be dispensed with entirely from the start, rather than annealed away, is untested.
• Extending beyond the tested backbones and domains. Transfer is demonstrated on six other Worker backbones and four task domains; behavior on agent graphs with much deeper or more heterogeneous team structures is not reported.
• Stress-testing the Bayesian decision thresholds. Withdrawal quality is demonstrated on 12 withdrawals with posterior E[Δ⁺] at most 0.019; how the ε, α, and n_min settings behave under noisier verifiers or domains with far larger skill libraries is not reported.

Target Audience

Researchers and advanced practitioners in LLM agent systems and reinforcement learning — particularly those working on learned orchestration, self-play curricula, skill libraries, and GRPO-family training — who want a method that ties task selection and skill retirement into one statistically grounded loop. It is also relevant to engineers deploying multi-agent pipelines who need to know which scaffolding can be safely removed before shipping a model with a leaner prompt.

Authors’ abstract

In recent years, agentic orchestration has been widely applied to solve complex human tasks. However, existing orchestration learning still faces key challenges, including hand-designed curricula, advantage collapse when a task's rollouts all reach the same outcome, and unreliable evaluation signals that judge each skill by one noisy score. To address these challenges, we propose R$^2$Orch, a new paradigm of Recursive Self-Play Orchestration: an inner loop of self-play that improves the orchestrator on self-chosen tasks, and an outer loop that improves how the inner loop improves. To support this paradigm, we introduce Recursive Learnability, a training objective that rewards a Proposer for choosing tasks whose rollouts keep reaching different outcomes as skills are withdrawn. Built on this objective, we further propose Skill Withdrawal, in which the outer loop withdraws each skill once a controlled evaluation within self-play shows that the orchestrator performs as well without it. Moreover, the two loops form one cycle: failures are distilled into skills, skills into parameters, and withdrawals lead the Proposer to new failures, so the orchestrator moves toward zero-skill deployment. Experimental results on twelve datasets show that R$^2$Orch consistently outperforms baselines across question answering, math, code, and interactive tasks. Our code is available at https://github.com/beita6969/R2Orch.