Learning to Orchestrate Agents under Uncertainty

• URL: http://arxiv.org/abs/2605.27073v1
• Date: Tue, 26 May 2026 14:23:22 GMT
• Title: Learning to Orchestrate Agents under Uncertainty
• Abstract summary: We study the problem of adaptive orchestration of heterogeneous agents under uncertainty, where a meta-controller must decide when to delegate to an agent.<n>We propose BOT-Orch, a lightweight framework that recasts orchestration as a bandit problem over agents.<n>We show that the regularised orchestration enjoys $mathcalO(sqrtT)$ regret under standard assumptions, and provably induces preference ordering among agents with identical mean rewards but differing distributional alignment.
• Score: 6.259311190073734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Adaptive orchestration of heterogeneous agents requires making sequential delegation 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 an agent, accounting for reliability, cost, and uncertainty. We propose BOT-Orch, a lightweight framework that recasts 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 baselines in synthetic but adversarial task allocation settings with heterogeneous, non-i.i.d. agent behaviour.

Related papers

• From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents [75.69180947909148]
  We propose a trajectory-level UQ framework for large language model (LLM) agents.<n>RuPA represents an execution history as a directed trajectory graph in which reasoning states, tool interactions, and environment feedback are nodes connected by temporal and semantic dependency edges.<n>We evaluate RUPA on representative agent benchmarks, including $$-2, Terminal-Bench-2, and GAIA, using 6 open-source LLMs spanning multiple model families.
  arXiv  Detail & Related papers  (2026-08-17T01:40:14Z)
• Semantic Uncertainty-Guided Orchestration in Hierarchical Multi-Agent Systems [11.562923882714095]
  This paper introduces a semantic-uncertainty-guided orchestration approach, HASSUM.<n>It estimates uncertainty using semantic entropy and semantic density, which measure trust at the level of answer semantics rather than output probabilities.<n>Because the approach operates independently of any particular agent architecture, it can be integrated into a broad range of hierarchical and collaborative multi-agent systems.
  arXiv  Detail & Related papers  (2026-08-11T03:55:53Z)
• From Profiling to Synthesis: Benchmarking Implicit Behavioral Alignment in Personalized LLM Agents [56.187590188698955]
  Large Language Models have enabled increasingly capable autonomous agents, yet personalization remains critical for making such agents practically useful.<n>Recent benchmarks have begun evaluating personalization in agents, but they largely rely on static preference snapshots, fixed interaction logs, or question answering over predefined user profiles.<n>We introduce IBA-Bench, a benchmark for implicit behavioral alignment constructed from longitudinal interaction histories.<n>We propose IBA-Agent, an agent framework that reconciles conflicting priorities through broad retrieval and trajectory-level alignment.
  arXiv  Detail & Related papers  (2026-08-03T12:52:04Z)
• AgenticAITA: A Proof-Of-Concept About Deliberative Multi-Agent Reasoning for Autonomous Trading Systems [0.0]
  AGENTICAITA is an agentic AI framework that replaces the traditional signal then execute paradigm with a fully autonomous loop.<n>The framework demonstrates operational correctness of the deliberative pipeline, achieving 157 zero-intervention invocations across 76 assets.
  arXiv  Detail & Related papers  (2026-05-01T16:25:43Z)
• Taming Actor-Observer Asymmetry in Agents via Dialectical Alignment [59.536125286960186]
  Multi-agent frameworks assigning specialized roles are increasingly adopted to enable self-reflection and mutual auditing.<n>We find it simultaneously induces a human-like cognitive bias known as Actor-Observer Asymmetry.<n>ReTAS guides agents to synthesize conflicting viewpoints into an objective consensus.
  arXiv  Detail & Related papers  (2026-04-21T15:05:58Z)
• Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guarantees [6.310266319378214]
  Real-world decision-making systems operate in environments where state transitions depend on the agent's actions.<n>Standard Constrained MDP formulations assume the agent is the sole driver of state evolution.<n>We propose textbfRobust Hallucinated Constrained Upper-Confidence RL (textttRHC-UCRL), a model-based algorithm that maintains optimism over both agent and adversary policies.
  arXiv  Detail & Related papers  (2026-04-15T04:53:29Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• Prior-Agnostic Incentive-Compatible Exploration [32.22947381651758]
  In bandit settings, optimizing long-term regret metrics requires exploration.<n>We show that (weighted) swap regret bounds on their own suffice to cause agents to faithfully follow forecasts.<n>We instantiate our abstract bounds with concrete algorithms for guaranteeing adaptive and weighted regret in bandit settings.
  arXiv  Detail & Related papers  (2026-02-24T01:53:08Z)
• Agentic Uncertainty Quantification [76.94013626702183]
  We propose a unified Dual-Process Agentic UQ (AUQ) framework that transforms verbalized uncertainty into active, bi-directional control signals.<n>Our architecture comprises two complementary mechanisms: System 1 (Uncertainty-Aware Memory, UAM), which implicitly propagates verbalized confidence and semantic explanations to prevent blind decision-making; and System 2 (Uncertainty-Aware Reflection, UAR), which utilizes these explanations as rational cues to trigger targeted inference-time resolution only when necessary.
  arXiv  Detail & Related papers  (2026-01-22T07:16:26Z)
• Decoupling the Effect of Chain-of-Thought Reasoning: A Human Label Variation Perspective [60.45433515408158]
  We show that long Chain-of-Thought (CoT) serves as a decisive decision-maker for the top option but fails to function as a granular distribution calibrator for ambiguous tasks.<n>We observe a distinct "decoupled mechanism": while CoT improves distributional alignment, final accuracy is dictated by CoT content.
  arXiv  Detail & Related papers  (2026-01-06T16:26:40Z)
• AgentMisalignment: Measuring the Propensity for Misaligned Behaviour in LLM-Based Agents [0.0]
  Large Language Model (LLM) agents become more widespread, associated misalignment risks increase.<n>In this work, we approach misalignment as a conflict between the internal goals pursued by the model and the goals intended by its deployer.<n>We introduce a misalignment propensity benchmark, textscAgentMisalignment, a benchmark suite designed to evaluate the propensity of LLM agents to misalign in realistic scenarios.
  arXiv  Detail & Related papers  (2025-06-04T14:46:47Z)
• Steering No-Regret Agents in MFGs under Model Uncertainty [19.845081182511713]
  We study the design of steering rewards in Mean-Field Games with density-independent transitions.<n>We establish sub-linear regret guarantees for the cumulative gaps between the agents' behaviors and the desired ones.<n>Our work presents an effective framework for steering agents behaviors in large-population systems under uncertainty.
  arXiv  Detail & Related papers  (2025-03-12T12:02:02Z)
• Formalizing the Problem of Side Effect Regularization [81.97441214404247]
  We propose a formal criterion for side effect regularization via the assistance game framework. In these games, the agent solves a partially observable Markov decision process. We show that this POMDP is solved by trading off the proxy reward with the agent's ability to achieve a range of future tasks.
  arXiv  Detail & Related papers  (2022-06-23T16:36:13Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  We show that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules.
  arXiv  Detail & Related papers  (2021-09-30T11:09:31Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.