Learning to Orchestrate Heterogeneous Agents under Uncertainty

Adaptive orchestration of heterogeneous agents requires making sequential delegation and aggregation decisions under uncertain and evolving agent behaviour, e.g., coordinating specialised AI models with varying reliability, cost, and response quality. While prior work on agent orchestration focuses on performance or cost, uncertainty in agent reliability and output distributions is typically not modelled explicitly at the orchestration level. In this work, we study the problem of adaptive orchestration of heterogeneous agents under uncertainty, where a meta-controller must decide when to delegate to a single agent and when to aggregate multiple agent outputs, accounting for reliability, cost, and uncertainty. We propose BOT-Orch, a lightweight framework that casts orchestration as a bandit problem over agents, regularized by OT distances between agent output distributions and task-specific reference distributions. We show that the regularised orchestration enjoys $\mathcal{O}(\sqrt{T})$ regret under standard assumptions, and provably induces preference ordering among agents with identical mean rewards but differing distributional alignment. Empirically, we demonstrate that BOT-Orch outperforms standard bandit and heuristic aggregation baselines in synthetic but adversarial task allocation settings with heterogeneous, non-i.i.d. agent behaviour.