Learning to Orchestrate Agents under Uncertainty Mary Chriselda Antony Oliver∗1 , Lan Jiang2 , Aaron Bundi Anampiu3 , Elaf Almahmoud2 , Francesco Quinzan†4 , Umang Bhatt†2 1
arXiv:2605.27073v1 [cs.LG] 26 May 2026
Department of Applied Mathematics and Theoretical Physics, University of Cambridge 2 Centre for Human-Inspired Artificial Intelligence, University of Cambridge 3 African Institute for Mathematical Sciences, South Africa 4 Department of Engineering Science, University of Oxford
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 O( 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.
1
Introduction
Incorporating uncertainty in delegated decision-making process is a fundamental challenge across machine learning and autonomous systems [Olfati-Saber et al., 2007, Shalev-Shwartz, 2012, Wurman et al., 2007]. In real-world environments, where stochasticity is dominant (e.g., partial and noisy observations), variability in agent capabilities makes centralized control impractical and can break classical solutions. Classical frameworks (e.g., Dec-POMDPs, stochastic games, DCOPs) explicitly model uncertainty in decision-making but often assume known system models, have limited scalability, or simplify agent interactions, restricting applicability in complex coordination settings [Bernstein et al., 2002, Fioretto et al., 2018, Hansen et al., 2004, Heifetz et al., 2006, Oliehoek and Amato, 2016, Shoham and Leyton-Brown, 2008]. In practice, heterogeneity in agent reliability, operational cost, and resource constraints further complicates coordination, especially at scale where performance, risk, and cost must be jointly managed [Arjun et al., 2025, Rizk et al., 2019]. Surveys in distributed decision-making and heterogeneous multi-agent coordination consistently identify these issues as key barriers to scalable deployment [Olfati-Saber et al., 2007, Rizk et al., 2019]. Multi-agent (including single-agent) reinforcement learning (MARL) provides tools for learning cooperative behaviors under partial observability and decentralised execution [Buşoniu et al., ∗
Correspondence to: [email protected]. † indicates joint supervision.
1
2008, Hernandez-Leal et al., 2019]. Value decomposition and centralized training with decentralized policies can maximize joint rewards even with distinct roles and observations [Rashid et al., 2018, Sunehag et al., 2018]. However, many MARL methods implicitly assume similar reliability and reaction costs, and rarely address adaptive selection among heterogeneous agents of uncertain outputs. Modern AI systems and single-agent orchestration frameworks mitigate these challenges. In planning, reasoning, and AI agent teams, systems increasingly rely on specialized agents with different expertise, reliability, and computational cost. Effective orchestration requires deciding which agent(s) to invoke and when to combine multiple predictions for robustness. Recent work shows that dynamic selection and composition conditioned on context can outperform static pipelines [Cheng et al., 2023, Liang et al., 2023, Park et al., 2023]. A natural abstraction for sequential decision-making under uncertainty is the multi-armed bandit (MAB) framework, capturing the exploration–exploitation trade-off [Bubeck and CesaBianchi, 2012, Lattimore and Szepesvári, 2020]. In the special case, single-agent extensions of the MAB framework study cooperation, regret minimization, and communication among learners [Gupta et al., 2021, Landgren et al., 2016]. Yet most bandit models treat agents as interchangeable up to mean reward and ignore query costs, limiting their suitability for orchestration with heterogeneous reliability, non-stationarity, and explicit invocation costs. Optimal Transport (OT) offers a complementary way to compare distributions and quantify discrepancies between uncertain outcomes [Peyré and Cuturi, 2019, Villani, 2003]. OT is widely used for uncertainty-aware distributional comparison in domain adaptation [Courty et al., 2016], generative modeling [Arjovsky et al., 2017, Bousquet et al., 2017], and statistical inference [Panaretos and Zemel, 2020]. However, OT remains underexplored in single-agent delegation as a mechanism to compare agent output distributions and guide adaptive orchestration. Recent work suggests OT can be fruitfully combined with multi-agent reinforcement learning for scalability and alignment in complex environments [Baheri and Kochenderfer, 2024]. Our contribution. • Bandit-based orchestration with OT alignment: We cast delegation over a single agent as a stochastic bandit regularized by OT distances between agent output distributions and task-specific references, enabling uncertainty-aware alignment and adaptive decision-making. • Theoretical guarantees: We establish sublinear OT-regularized regret (1 of Theorem 4.1), structural optimality and robustness to noisy alignment (2-3 of Theorem 4.1), and convergence and consistency properties (5-4 of Theorem 4.1). • Empirical validation under heterogeneity and shift: We evaluate BOT-Orch across synthetic and semi-synthetic settings, including a human–AI triage scenario under deployment shift (Section 6-7), demonstrating consistent improvements over standard bandit and heuristic baselines in both i.i.d. and non-i.i.d. environments.
2
Related Work
Agent orchestration. Prior work on agent orchestration largely focuses on selecting agents based on expected utility or offline accuracy [Keswani et al., 2021, Lai et al., 2022, Rasal and Hauer, 2024]. However, these approaches often overlook practical constraints such as availability, cost, and capability. Recent work on human–AI orchestration highlights how interagent interactions shape system-level decision networks [Collins et al., 2024], yet uncertaintyaware adaptive orchestration under realistic constraints remains underexplored. We address this gap via uncertainty-aware OT-based orchestration. In a related direction, DiscoPOP 2
[Lu et al., 2024] learns loss functions without human input, optimizing over objectives. This suggests that automatic objective discovery could extend to orchestration. Bandit approaches. Multi-armed bandits provide a natural framework for sequential decision making under uncertainty, balancing exploration and exploitation [Chen, 2024, Lattimore and Szepesvári, 2020, Letard et al., 2024, Tong, 2024]. Recent surveys summarize advances in classical and contextual bandits and their applications [Chen, 2024, Letard et al., 2024], while empirical studies highlight design choices affecting performance [Bietti et al., 2021]. Emerging work connects bandits with large language models in complex environments [Xie et al., 2026]. Here, we use bandits to learn orchestrations that maximize expected utility across heterogeneous agents with uncertain performance. OT for uncertainty-aware orchestration. Optimal transport provides a principled framework for comparing probability distributions via geometrically meaningful discrepancies [Villani et al., 2008]. We use OT to quantify uncertainty in heterogeneous agent outputs through distributional disagreement and variability, building on recent work in OT-based uncertainty quantification with applications to health data science [Oliver et al., 2025a,b,c]. This provides uncertainty-aware weights capturing the trade-off between confidence and disagreement. The framework is well-suited for distributional and uncertainty-aware reinforcement learning settings such as those in [Bellemare et al., 2017, Osband et al., 2013], offering a unified approach to adaptive multi-agent coordination with both theoretical guarantees and strong empirical performance.
3
Preliminaries and Notation
In this section, we introduce the relevant concepts that are foundational to our framework.
3.1
Agents, Tasks, and Task Space
Let A := {a1 , . . . , aM } denote a finite set of M agents. Time evolves over a finite horizon t = 1, . . . , T . At each round t, a task xt ∈ X is observed. We assume that tasks are generated by a history-dependent stochastic process xt ∼ P(· | Ht ), where the history filtration is defined as Ht := σ xs , As , Rs , Ws : s = 1, . . . , t − 1 , and As ∈ {1, . . . , M } is Hs -measurable and denotes the agent selected at time s. For each agent ai ∈ A and task xt , let Rti ∈ R denote the (possibly counterfactual) reward that would be obtained if xt were assigned to agent ai , and let Wti ∈ R denote the corresponding task–agent alignment cost. Define vectors Rt := (Rt1 , . . . , RtM )⊤ ∈ RM , Wt := (Wt1 , . . . , WtM )⊤ ∈ RM . Analogously, we define the corresponding conditional mean quantities: ri (xt ) := E[Rti | xt ], wi (xt ) := E[Wti | xt ]. Note that task arrivals may depend on past observations, environmental conditions, or previous assignments.
3.2
Correlated Multi-Agent Rewards
Let Rt ∈ RM denote the vector of (joint) rewards at round t. We model its conditional moments given the current task xt and history Ht . Assume there exists a function r and a history-dependent drift term f : Ht → RM such that E[Rt | xt , Ht ] = r(xt ) + f (Ht ), and a positive semidefinite matrix Σt satisfying Cov[Rt | xt , Ht ] = Σt . Here, Σt may vary over time, capturing non-stationarity and cross-agent correlations. 3
i.i.d.
I.I.D. tasks as a special case. Suppose xt ∼ PX . If, in addition, the reward process is conditionally independent of the past given the current task, i.e. Rt ⊥ Ht | xt , then f ≡ 0, and the model reduces to E[Rt | xt ] = r(xt ),
Cov[Rt | xt ] = Σ,
for a constant covariance matrix Σ.
3.3
Survival-Based Rewards with Latent Frailty
In many systems, agent performance is naturally measured via time-to-event outcomes. For each task xt and agent ai , let Tt (i) > 0 denote the time-to-completion random variable. We allow right-censoring and introduce a censoring indicator δt (i) ∈ {0, 1}, where δt (i) = 1 indicates that the completion time is fully observed. We define a baseline survival function Si (τ | xt ) := P(Tt (i) > τ | xt ), which captures heterogeneity across tasks and agents. To model unobserved task-level difficulty, we introduce a latent frailty variable θt > 0, assumed i.i.d. with E[θt ] = 1. Conditional on (xt , θt ), we assume a proportional frailty model: P(Tt (i) > τ | xt , θt ) = Si (τ | xt )θt . Equivalently, θt acts as a multiplicative scaling of the baseline cumulative hazard. Under this construction, conditional on (xt , θt ), completion times are independent across agents: Tt (i) ⊥ Tt (j) | (xt , θt ), and marginalizing over θt induces dependence: Tt (i) ̸⊥ Tt (j) | xt . Specific to our setting, one suitable choice for defining the fraility reward function is as follows, Rti := δt (i) Si (Tt (i) | xt )θt . This survival-based formulation is suitable for modeling reliability, latency, and time-to-success in heterogeneous multi-agent systems.
3.4
OT-Based Alignment Costs
Beyond rewards, we also model how well an agent’s capabilities align with the requirements of a task. In many applications, both tasks and agents are naturally described by distributions rather than single feature vectors. For example, an agent may produce a distribution of outcomes (quality levels, response times, error types), while a task may specify a desired target distribution over outcomes. Let µi ∈ P(Y) denote the outcome distribution induced by agent ai over a measurable space Y, and let νt ∈ P(Y) represent the reference or desired outcome distribution associated with task xt . We quantify the mismatch between an agent and a task using the Wasserstein distance Wc (νt , µi ) Villani [2003], which measures the minimal cost of transporting mass from one distribution to the other under ground cost c. This provides a geometrically meaningful notion of alignment that accounts for the full distribution of outcomes rather than just summary statistics. We note that constructing a fixed reference measure is often non-trivial in practice, particularly when the task distribution is unknown or evolves over time. In the i.i.d. setting, a natural choice is to estimate a single representative measure of the environment using a Wasserstein barycenter of the observed task distributions, which provides a principled Fréchet mean in the space of probability measures Chewi et al. [2025]. This yields a stable global reference that summarises 4
the stationary data-generating process. In contrast, in the non-i.i.d. setting, where the task distribution may drift or depend on historical interactions, a single global barycenter is generally insufficient to capture temporal heterogeneity. Instead, one may consider time-adaptive or history-dependent barycenters, computed over sliding windows or exponentially weighted empirical measures, thereby producing a sequence of local barycenters that track the evolving environment. This leads to a dynamic reference structure that better reflects non-stationarity while preserving the geometric advantages of the Wasserstein framework. To incorporate randomness and modeling noise, we define the stochastic alignment cost Wti := Wc (νt , µi ) + ϵit ,
ϵit ∼ N (0, σi2 ).
Its conditional mean is wi (xt ) := E[Wti | xt ]. This formulation captures both systematic mismatch (via the Wasserstein term) and unpredictable variability (via the noise term ϵit ). Introducing alignment costs at this stage allows us to jointly model (i) how well an agent is suited to a task and (ii) the stochastic rewards that result from performing it, providing a foundational framework for assignment decisions under uncertainty.
3.5
Orchestration Policy and Objective
We now formalize the decision-making problem faced by the orchestrator. At each round t, after observing the task xt and past history Ht , the orchestrator selects a randomized policy πt ∈ ∆(A), where ∆(A) denotes the probability simplex over agents. An agent it ∼ πt is then sampled and assigned to handle task xt . Randomized policies enable exploration and robustness to uncertainty in agent performance. Per-round expected utility. The expected net reward under policy πt is defined as: Rt (πt ) := Eit ∼πt rit (xt ) − λwit (xt ) , λ > 0,
(1)
where ri (xt ) and wi (xt ) denote the conditional expected reward and alignment cost of assigning task xt to agent ai . Equivalently, Rt (πt ) = πt⊤ r(xt ) − λw(xt ) . Cumulative objective. The cumulative expected reward over a finite horizon T is R(π1:T ) :=
T X
Rt (πt ).
t=1
3.6
Regret and Optimal policy.
The orchestrator selects policies without access to the true reward r(xt ) and alignment cost distributions w(xt ). We evaluate performance against an oracle that has full knowledge of these quantities. This motivates the notion of an optimal policy, which maximizes expected per-round utility under complete information. Since, the oracle is unavailable in practice, the learner deploys a sequence of policies {πt }Tt=1 based on partial information. The performance gap between the learned policy and the oracle is quantified via regret, which measures cumulative suboptimality over the horizon. Sublinear regret implies asymptotic convergence to oracle performance. The optimal (oracle) policy at each round is given by: πt∗ := arg max π ⊤ (r(xt ) − λw(xt )). π∈∆(A)
5
(2)
Cumulative regret. We define the cumulative regret as the performance gap between the optimal policy and the learned policy: RT :=
T X
Rt (πt∗ ) − Rt (πt ) .
(3)
t=1
Remark 3.1. If tasks are i.i.d. and the environment is stationary, the problem reduces to a standard contextual bandit setting. Otherwise, the regret captures additional inefficiency arising from temporal dependence, non-stationary task arrivals, and stochastic alignment costs.
4
Theoretical Properties
We begin by stating the standing assumptions that remain in force throughout. (A1) The ground cost c : Y × Y → R+ is L-Lipschitz and bounded. (A2) Rewards are uniformly bounded: 0 ≤ Rt (i) ≤ Rmax for all t and all actions i ∈ A. (A3) The frailty variables (θt )t≥1 admit finite exponential moments. (A4) Conditional on (xt , θt ), censoring is independent of survival time. (A5) The learning rate satisfies ηt = O(t−1/2 ). Assumptions (A1)–(A5) ensure: (i) stability of Wasserstein distances under empirical perturbations; (ii) sub-exponential behaviour of frailty-adjusted rewards; (iii) well-posedness of the induced softmax stochastic approximation dynamics. We remark that these conditions are standard in the literature on stochastic approximation, Wasserstein-based learning, and frailty-adjusted reward models [Ambrosio et al., 2008, ShalevShwartz and Ben-David, 2014, Trillos and Slepčev, 2016]. In practice, they are not restrictive: Lipschitz and bounded costs are typical in OT and multi-agent learning applications, bounded rewards naturally arise in reinforcement learning, and learning rates of order t−1/2 are widely used to guarantee convergence. Moreover, our framework generalizes several prior works by allowing frailty variables with arbitrary distributions admitting finite exponential moments, rather than restricting to specific parametric forms [Del Barrio and Loubes, 2019, Wang et al., 2020].
4.1
Main Results
Following the assumptions in Section 4, we now present the main theoretical guarantees for the OT-regularised bandit model. The regret analysis is conducted for a general exponentialweights (softmax) procedure applied to bounded, OT-regularised reward signals. Importantly, the resulting guarantees depend only on the boundedness of these rewards and are independent of the specific model. The additional modeling components introduced in the setup, namely, correlated rewards, survival-based frailty, and non-i.i.d. task generation serve as a motivating probabilistic framework in which such bounded reward processes naturally arise. They are not directly used in the regret derivation, but instead provide one possible instantiation of the abstract reward model. Proofs are provided in Appendices B.2–B.4. Theorem 4.1 (Properties of OT-Regularized Orchestration). Assume (A1)–(A5) hold. Let A = {a1 , . . . , aM } be a finite set of agents, and let πt ∈ ∆(A) denote the orchestration policy at round t. Define the OT-regularized per-round utility Rt (πt ) be as in (1) and let the cumulative regret RT be as in (3) where the optimal policy πt∗ is as in (2). Let ϕt := πt denote the policy weight vector. Assume initial conditions are well-defined: ϕ0 ∈ ∆(|A| − 1). Then, the following statements hold for i ∈ {1, · · · , M }:
6
1. Sublinear OT-Regret. Define the policy by πt (i) = PMwt (i) , and wt+1 (i) = wt (i) exp ηt (Rti − j=1 wt (j) λWti ) , where Rti and Wti are the realized reward and OT costs. Define the pseudo-regret as P RT := Tt=1 maxi∈{1,...,M } E[Rti − λWti | xt ] − Eit ∼πt [Rtit − λWtit ] . Then, the cumulative OT-regularized regret satisfies √ RT = O( T ). 2. Structural OT-Optimality. For any i, j ∈ A, if E[Rti | xt ] = E[Rtj | xt ] and wi (xt ) < wj (xt ), then the OT-regularized utilities satisfy E[Rti | xt ] − λwi (xt ) > E[Rtj | xt ] − λwj (xt ). fi 3. Margin Robustness under Noisy Alignment. Let observed alignment costs √ be Wt = i i i 2 j i Wt + ϵt , with ϵt ∼ N (0, σ ). Define ∆ij (t) := w (xt ) − w (xt ). If |∆ij (t)| > σ 2 log 2, then f i < rj (xt ) − λW fj < 1 . P ri (xt ) − λW t t 4 Assume the policy updatefollows a stochastic 4. Convergence of Orchestration Weights. approximation scheme: ϕt+1 − ϕt = ηt Softmax(r(xt ) − λw(xt )) − ϕt , with step sizes ηt P P satisfying t ηt = ∞, t ηt2 < ∞. Then ϕt converges almost surely to an invariant point ϕ∞ of the mean-field ODE ϕ̇ = Softmax E[r(x)] − λE[w(x)] − ϕ. P 5. Uniform Consistency of Empirical Rewards. Let r̂t (i) := 1t ts=1 Rsi be the empirical average reward and let |Rti | ≤ Rmax be the bounded rewards. Then, we have t
sup r̂t (i) − i∈A
1X a.s. E[Rsi | Hs−1 ] −−−→ 0. t→∞ t s=1
In particular, in the i.i.d. case this implies a.s.
sup r̂t (i) − E[Rti ] −−−→ 0. t→∞
i∈A
We note that Theorem 4.1 provides a foundational characterization of OT-regularized bandit learning. It integrates distributional alignment into the reward structure, yielding principled agent differentiation 2, sublinear cumulative regret 1, robustness to noisy observations 3, convergence of orchestration weights 4, and uniform consistency of empirical rewards 5. The framework enables heterogeneous agents to learn coordinated policies under distributionallyaware uncertainty, supporting robust, adaptive orchestration in stochastic, partially observable environments. We refer the reader to Appendix B for a proof of Theorem 4.1.
5
The proposed algorithm
BOT-Orch combines bandit-based selection with OT alignment and survival-based rewards to handle heterogeneous, non-stationary agents. In the i.i.d. task setting (Algorithm 1 in the Appendix), a Boltzmann policy selects agents using exponentially smoothed rewards penalized by OT misalignment, balancing exploitation and alignment, while survival rewards capture latent difficulty, censoring, and reliability. The non-i.i.d. extension (Algorithm 2 in the Appendix) allows history-dependent task distributions and reward updates, handling temporal correlations, non-stationarity, and regime shifts via a correction term that encodes 7
memory effects. Overall, BOT-Orch is a risk-aware, alignment-regularized bandit algorithm in distributional space, where OT enforces task-agent compatibility and survival rewards provide robustness to censoring and heterogeneity. Its modular design accommodates alternative OT solvers, survival models, and exploration schemes, and motivates regret analysis under composite reward–cost objectives as well as questions of convergence and adaptivity in nonstationary environments.
6
Synthetic Experiments
6.1
Dataset and Task Description
We consider both i.i.d. and non-i.i.d. regimes (see Fig. 2–3 in the Appendix) in order to evaluate BOT-Orch under both stationary and evolving environments. The i.i.d. settings isolate performance under stable task distributions, whereas the non-i.i.d. settings introduce different forms of temporal dependence and distributional shift. In the stationary setting, we consider two environments. In IID-G, tasks xt are sampled i.i.d. over X and agent rewards are drawn from fixed Gaussian distributions with matched means (≈ 0.5) but heterogeneous higher-order structure. This setting evaluates whether the orchestration policy can distinguish between agents beyond mean reward alone. In IID-M, tasks are sampled i.i.d. from a half-moons distribution, while rewards are drawn from fixed distributions with similar means but differing variance, skewness, and bimodality, thereby introducing additional distributional heterogeneity. We then consider three forms of non-stationarity. In NonIID-PS, rewards are piecewisestationary, with fixed means but variance shifts occurring at unknown changepoints, inducing distributional shift without changing expected reward. In NonIID-SD, non-stationarity is introduced gradually through sinusoidal drift in the reward means over time. Finally, in NonIID-BB, latent reward means evolve according to a temporally correlated Brownian-bridge process with fixed endpoints, capturing smoothly varying latent dynamics. All experiments were conducted on a standard x86_64 CPU platform using 2 CPU cores, 13.6 GB RAM, and 107 GB disk storage.
6.2
Baselines
We compare BOT-Orch against the following baselines. All baselines operate on the same task stream and are evaluated with identical metrics and random seeds. • BOT-Orch (ours). Uses alignment-adjusted rewards rt (i) = r̂t (i) − λWt (i) and samples the selected agent it from a softmax policy over rt (i) (Algorithm 1–2). This couples OT alignment with sequential exploration/exploitation. • No-OT (λ = 0). Ablation removing the OT alignment term. The policy is computed from r̂t (i) only. This isolates the contribution of distributional alignment. • Random. Uniformly samples an agent each round. This serves as a naive lower bound that does not learn from observations. • UCB1 (MAB). A classical multi-armed bandit baseline that selects the agent with the highest upper confidence bound based on empirical reward estimates, balancing exploration and exploitation without OT alignment. We exclude baselines that require full-information feedback, i.e., access to the rewards of all agents at every round, since our setting assumes standard bandit feedback, where only the reward of the selected agent is observed. This includes simple greedy strategies based on
8
Environment IID IID-G IID-M Non-IID NonIID-BB NonIID-PS NonIID-SD
BOT-Orch
No-OT (λ=0)
Random
UCB1 (MAB)
537.43±16.57 459.84±9.27
656.31±22.64 545.85±17.74
673.99±19.08 553.07±19.16
664.89±29.85 549.48±7.40
410.04±71.06 571.43±18.71 564.13±18.11
503.14±91.24 713.81±25.79 717.24±22.51
520.28±101.61 734.65±30.08 707.69±18.33
496.60±79.57 729.51±28.34 708.60±16.06
Table 1: Cumulative Alignment Cost (mean ± 95% CI across 5 seeds; T = 200). IID condition uses Algorithm 1; Non-IID uses Algorithm 2. Best in bold. Cumulative Net Utility Oracle Regret Environment BOT-Orch No-OT (λ=0) Random UCB1 (MAB) BOT-Orch No-OT (λ=0) Random UCB1 (MAB) IID IID-G -467.528±17.60 -588.34±23.19 -605.71±18.91 -603.31±29.13 122.65±5.68 243.47±14.26 260.83±11.59 258.43±18.11 IID-M -386.10±10.04 -478.54±20.49 -482.81±18.65 -484.57±9.35 74.70±5.45 166.25±11.99 170.52±10.99 172.28±8.40 Non-IID NonIID-BB -335.25±70.42 -434.01±86.69 -449.34±100.73 -426.09±79.48 76.85±7.42 175.61±16.44 190.94±31.44 167.69±19.20 NonIID-PS -498.28±22.49 -642.77±25.89 -666.10±29.31 -663.22±27.77 126.77±11.68 271.26±11.84 294.58±20.25 291.71±14.45 NonIID-SD -492.92±18.74 -644.68±21.62 -637.82±18.54 -643.69±17.20 128.77±13.30 280.53±10.81 273.67±10.74 279.54±11.52
Table 2: Cumulative Net Utility and Oracle Regret (mean ± 95% CI across 5 seeds; T = 200). IID condition uses Algorithm 1; Non-IID uses Algorithm 2. Best in bold. exponentially smoothed reward estimates, which are not directly applicable under partial feedback without additional exploration or uncertainty-estimation mechanisms.
6.3
Evaluation Metrics
We use the following metrics for experimental comparison, computed per seed and aggregated as mean±95% confidence intervals across seeds. • Cumulative net utility. We evaluate the OT-regularized net utility Ut (it ) = Rt (it ) − PT λ Wt (it ), and report the cumulative net utility U (i ). This captures the overall t t t=1 performance when explicitly trading off reward quality and alignment cost via λ. P • Cumulative alignment cost. We report Tt=1 Wt (it ), the cumulative OT alignment cost incurred by the selected agent assignments. Lower values indicate more distributionally aligned agent-task matching. • Oracle regret. We report OT-regularized cumulative regret relative to the best alignmentP adjusted agent at each round: Tt=1 (maxi Ut (i) − Ut (it )) measuring efficiency loss due to suboptimal selection under uncertainty and non-stationarity.
6.4
Results
BOT-Orch achieves the highest cumulative net utility and lowest oracle regret across all environments (Table 1-2), consistently outperforming No-OT, Random, and UCB1. The improvement is particularly pronounced in non-i.i.d. settings, where BOT-Orch maintains low regret under distributional shifts such as piecewise variance changes and smooth drift. These results indicate that incorporating OT-based alignment enables more effective adaptation to heterogeneous and non-stationary agent behaviour. In Appendix D, we evaluate BOT-Orch on additional synthetic benchmarks using survivalbased metrics, showing that BOT-Orch achieves best performance. We further conduct an ablation study on the parameter λ (Appendix D.5). As λ increases, BOT-Orch exhibits performance improvements, with large gains relative to λ = 0 and diminishing returns at higher values.
9
Cumulative Net Utility Environment BOT-Orch No-OT (λ=0) Random IID 108.84±2.22 103.37±2.51 83.98±5.92 Non-IID 110.61±1.03 103.17±1.80 79.78±5.52
UCB1 80.55±4.88 85.82±4.91
Oracle Regret BOT-Orch No-OT (λ=0) Random UCB1 2.29±2.11 9.80±1.61 28.72±6.03 31.31±3.98 0.59±0.93 10.14±1.17 32.97±4.87 26.26±4.28
Team Accuracy Cumulative Alignment Cost Environment BOT-Orch No-OT (λ=0) Random UCB1 BOT-Orch No-OT (λ=0) Random UCB1 IID 0.980±0.010 0.907±0.022 0.917±0.020 0.902±0.026 1.28±0.53 10.51±1.61 10.28±2.01 11.14±1.33 Non-IID 0.993±0.007 0.905±0.016 0.905±0.024 0.919±0.025 0.85±0.23 10.84±1.18 11.69±1.62 9.46±1.43
Table 3: Deployment metrics across all four methods and both experimental conditions (Mean ± 95% CI across 30 seeds, T =114, λ=3.0). IID condition uses Algorithm 1; Non-IID uses Algorithm 2 (ID patients rounds 1–57, shifted rounds 58–114). Best in bold.
Figure 1: Cumulative learning curves. Top row : cumulative net utility. Bottom row : oracle regret. Right column: rolling escalation rate (window w=8 rounds). Left panels: IID condition (Algorithm 1); middle panels: Non-IID condition (Algorithm 2), with the dotted vertical line marking the shift onset at round 57; right panels: escalation rate evolution.
7
Semi-Synthetic Experiments: Human-AI Triage Under Deployment Shift
7.1
Dataset and Task Description
We use the Breast Cancer Wisconsin (Diagnostic) dataset, consisting of 569 patient cases with 30 numerical features and a binary target (malignant vs. benign). The data is split into 60% train, 20% calibration, 10% Test-ID, and 10% Test-Shift. To simulate deployment shift, we perturb a subset of features in Test-Shift with additive Gaussian noise N (0, 0.64) and a +0.5 standard-unit bias, modelling a change in patient population at deployment. At each round t, a patient xt arrives and the selected agent receives a reward of 1 if it classifies the patient correctly and 0 otherwise, under standard bandit feedback. We consider two agents: an AI classifier and a human proxy with complementary accuracy, where the human performs better on shifted cases while the AI performs better in-distribution. Full model details and accuracy statistics are provided in Appendix E. All experiments were conducted on a standard x86_64 CPU platform using 2 CPU cores, 13.6 GB RAM, and 107 GB disk storage.
10
7.2
Baselines
We compare the same four methods used in the synthetic experiments, now applied to the clinical triage task. We use α = 0.90, η = 5.0, λ = 3.0, and, for the non-i.i.d. variant, the same history correction form as Algorithm 2 with β = 0.05. Each episode has T = 114 rounds, and we average over n = 30 random seeds (patient orderings). We report mean ± 95% CI across seeds.
7.3
Evaluation Metrics
From Section 6.3, we use cumulative net utility, cumulative alignment cost, and oracle regret, defined as above. We additionally report metrics specific to the human–AI deferral setting, namely team accuracy, defined as the fraction of patients correctly classified by the selected agent (AI or human), and escalation rate, defined as the fraction of patients routed to the human expert. These additional metrics capture complementary aspects of orchestration quality beyond cumulative utility and regret. Together, these metrics provide insight into the trade-off between automation and human intervention, particularly under deployment shift and uncertainty.
7.4
Results
Table 3 summarizes the results. BOT-Orch achieves the highest cumulative net utility and lowest oracle regret in both regimes, outperforming all baselines. In the IID condition, it improves net utility by +5.5 over No-OT while reducing alignment cost by an order of magnitude. In the Non-IID setting, the gain is larger, reaching 110.61 ± 1.03 net utility and 0.59 ± 0.93 regret compared to 103.17 ± 1.80 and 10.14 ± 1.18 for No-OT. The No-OT ablation confirms that the OT term drives the improvement: removing it increases regret and alignment cost. BOT-Orch also exhibits targeted escalation under shift, routing fewer patients overall while increasing escalation on shifted cases, indicating effective adaptation to distributional mismatch. Figure 1 further shows that BOT-Orch separates from all baselines early and maintains the performance gap over time. In the Non-IID setting, the escalation rate increases after the shift, demonstrating online adaptation to the changing population. Furthermore, the rolling escalation rate in Figure 1 shows how the policy adapts over time, increasing reliance on the human expert when distributional shift or uncertainty rises. Additional results are presented in Appendix F, including more results on the escalation rate, diagnostic analysis, and an ablation study on the parameter λ. We observe that, as λ increases, performance improves markedly peaking around λ ≈ 3.0, after which gains saturate or slightly diminish at very high values.
8
Conclusion
We introduced BOT-Orch, a framework for uncertainty-aware agent orchestration that formulates delegation as an OT-regularized bandit problem over heterogeneous agents. By combining sequential decision-making with distributional alignment, BOT-Orch jointly accounts for agent reliability, alignment quality, and uncertainty when selecting agents under stochastic and potentially non-stationary environments. We established theoretical guarantees including sublinear OT-regularized regret, robustness to noisy alignment, and convergence of orchestration weights. Empirically, BOT-Orch consistently outperformed standard bandit and heuristic baselines across synthetic and semi-synthetic settings, particularly under distribution shift and heterogeneous agent behaviour. More broadly, our results suggest that incorporating distributional structure directly into orchestration policies can substantially improve robustness and adaptability in modern multi11
agent AI systems. This is especially relevant for emerging ecosystems composed of specialised models, reasoning systems, and tool-using agents, where orchestration increasingly plays a central role in overall system performance. Several limitations remain. First, computing Wasserstein distances can become computationally expensive in high-dimensional settings, potentially limiting scalability in real-time applications. Second, the alignment parameter λ introduces a reward–alignment trade-off that may require calibration across environments. Third, the framework assumes access to suitable task-specific reference distributions, which may be difficult to obtain or estimate reliably in open-world settings. Future work will investigate more scalable alignment mechanisms, adaptive calibration strategies, and evaluation in larger-scale real-world orchestration environments. We also believe that extending uncertainty-aware orchestration beyond single-agent delegation toward richer coordination and interaction settings is a promising direction for further study.
References Ambrosio, L., Gigli, N., and Savaré, G. (2008). Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zürich. Birkhäuser Basel, 2nd edition. Arjovsky, M., Chintala, S., and Bottou, L. (2017). Wasserstein gan. In ICML. Arjun, K., Parlevliet, D., Wang, H., and Yazdani, A. (2025). Optimizing coalition formation strategies for scalable multi-robot task allocation: A comprehensive survey. Robotics, 14(7):93. Baheri, A. and Kochenderfer, M. J. (2024). The synergy between optimal transport theory and multi-agent reinforcement learning. arXiv preprint arXiv:2401.10949. Explores integration of optimal transport theory with MARL for policy alignment, resource distribution, and non-stationarity mitigation. Bellemare, M. G., Dabney, W., and Munos, R. (2017). A distributional perspective on reinforcement learning. In International Conference on Machine Learning, pages 449–458. Bernstein, D. S., Givan, R., Immerman, N., and Zilberstein, S. (2002). The complexity of decentralized control of markov decision processes. Mathematics of Operations Research, 27(4):819–840. Bietti, A., Agarwal, A., and Langford, J. (2021). A contextual bandit bake-off. In Journal of Machine Learning Research, volume 22, pages 1–49. Bousquet, O., Gelly, S., Tolstikhin, I., Simon-Gabriel, C.-J., and Schoelkopf, B. (2017). From optimal transport to generative modeling: the vegan cookbook. arXiv preprint arXiv:1705.07642. Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1–122. Buşoniu, L., Babuška, R., and De Schutter, B. (2008). A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 38(2):156–172. Chen, Q. (2024). A survey on contextual multi-armed bandits. Applied and Computational Engineering, 53:287–295.
12
Cheng, Y. et al. (2023). Autogen: Enabling next-gen llm applications via multi-agent conversation. arXiv preprint arXiv:2308.08155. Chewi, S., Niles-Weed, J., and Rigollet, P. (2025). Wasserstein Barycenters, pages 211–227. Springer Nature Switzerland, Cham. Collins, K. M., Chen, V., Sucholutsky, I., Kirk, H. R., Sadek, M., Sargeant, H., Talwalkar, A., Weller, A., and Bhatt, U. (2024). Modulating language model experiences through frictions. arXiv preprint arXiv:2407.12804. Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A. (2016). Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 39(9):1853–1865. Del Barrio, E. and Loubes, J.-M. (2019). Frailty models and empirical process theory. Annals of Statistics, 47(5):2519–2543. Fioretto, F., Pontelli, E., and Yeoh, W. (2018). Distributed constraint optimization problems and applications: A survey. Journal of Artificial Intelligence Research, 61:623–698. Gupta, S., Chaudhari, S., Joshi, G., and Yağan, O. (2021). Multi-armed bandits with correlated arms. IEEE Transactions on Information Theory, 67(10):6711–6732. Hansen, E. A., Bernstein, D. S., and Zilberstein, S. (2004). Dynamic programming for partially observable stochastic games. In Proceedings of the National Conference on Artificial Intelligence (AAAI). Heifetz, A., Meier, M., and Schipper, B. (2006). Interactive unawareness. Journal of Economic Theory, 130(1):78–94. Hernandez-Leal, P., Kartal, B., and Taylor, M. E. (2019). A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 33:750–797. Keswani, V., Lease, M., and Kenthapadi, K. (2021). Towards unbiased and accurate deferral to multiple experts. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 154–165. Lai, V., Carton, S., Bhatnagar, R., Liao, Q. V., Zhang, Y., and Tan, C. (2022). Human-ai collaboration via conditional delegation: A case study of content moderation. In Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems, pages 1–18. Landgren, P., Srivastava, V., and Leonard, N. E. (2016). Distributed cooperative decisionmaking in multiarmed bandits: Frequentist and bayesian algorithms. CDC. Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. Letard, A., Gutowski, N., Camp, O., and Amghar, T. (2024). Bandit algorithms: A comprehensive review and their dynamic selection from a portfolio for multicriteria top-k recommendation. Expert Systems with Applications, 246:123151. Liang, J., Wang, W., et al. (2023). Taskmatrix.ai: Completing tasks by connecting foundation models with millions of apis. arXiv preprint arXiv:2303.16434. Lu, C., Holt, S., Fanconi, C., Chan, A., Foerster, J., van der Schaar, M., and Lange, R. (2024). Discovering preference optimization algorithms with and for large language models. Advances in Neural Information Processing Systems, 37:86528–86573. Olfati-Saber, R., Fax, J. A., and Murray, R. M. (2007). Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1):215–233. 13
Oliehoek, F. A. and Amato, C. (2016). A Concise Introduction to Decentralized POMDPs. Springer. Oliver, M. C. A., Graham, M., Manolopoulou, I., Medley, G. F., Pellis, L., Pouwels, K. B., Thorpe, M., and Hollingsworth, T. D. (2025a). Uncertainty quantification in cost-effectiveness analysis for stochastic-based infectious disease models: Insights from surveillance on lymphatic filariasis. Journal of Theoretical Biology, page 112197. Oliver, M. C. A., Hartman, E., and Needham, T. (2025b). Conic formulations of transport metrics for unbalanced measure networks and hypernetworks. arXiv preprint arXiv:2508.10888. Oliver, M. C. A., Roberts, M., Schönlieb, C.-B., and Thorpe, M. (2025c). Laplace learning in wasserstein space. arXiv preprint arXiv:2511.13229. Osband, I., Russo, D., and Van Roy, B. (2013). (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pages 3003–3011. Panaretos, V. M. and Zemel, Y. (2020). Statistical aspects of Wasserstein distances. Annual Review of Statistics and Its Application. Park, J. S., O’Brien, J., Cai, C. J., et al. (2023). Generative agents: Interactive simulacra of human behavior. UIST. Peyré, G. and Cuturi, M. (2019). Computational Optimal Transport. Foundations and Trends in Machine Learning. Rasal, S. and Hauer, E. (2024). Navigating complexity: Orchestrated problem solving with multi-agent llms. arXiv preprint arXiv:2402.16713. Rashid, T., Samvelyan, M., Schroeder, C., et al. (2018). Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In ICML. Rizk, Y., Awad, M., and Tunstel, E. W. (2019). Cooperative heterogeneous multi-robot systems: A survey. ACM Computing Surveys, 52(2):1–31. Robbins, H. and Monro, S. (1951). A stochastic approximation method. Annals of Mathematical Statistics, 22(3):400–407. Shalev-Shwartz, S. (2012). Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4:107–194. Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press. Shoham, Y. and Leyton-Brown, K. (2008). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press. Sunehag, P., Lever, G., Gruslys, A., et al. (2018). Value-decomposition networks for cooperative multi-agent learning. In AAMAS. Tong, R. (2024). A survey of the application and technical improvement of the multi-armed bandit. Applied and Computational Engineering, 77:25–31. Trillos, N. G. and Slepčev, D. (2016). A variational approach to the consistency of spectral clustering. Applied and Computational Harmonic Analysis, 40(2):274–319. Villani, C. (2003). Topics in Optimal Transportation. American Mathematical Society. Villani, C. et al. (2008). Optimal transport: old and new, volume 338. Springer.
14
Wang, Q. et al. (2020). Stochastic approximation for survival models with frailty terms. Statistics in Medicine, 39(10):1405–1420. Wurman, P. R., D’Andrea, R., and Mountz, M. (2007). Coordinating hundreds of cooperative, autonomous vehicles in warehouses. In AAAI Conference on Artificial Intelligence. Xie, M., Chen, S., and Lv, C. (2026). A component-based survey of interactions between large language models and multi-armed bandits. arXiv preprint.
15
SUPPLEMENTARY MATERIALS Contents A Algorithm: Bandit–OT Orchestration with Survival-Based Rewards
17
A.1 i.i.d. Task Arrivals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
A.2 Non-i.i.d. Task Arrivals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
B Appendix: Missing Proofs
19
B.1 Proof of 1 in Theorem 4.1 (Sublinear OT-Regret) . . . . . . . . . . . . . . .
19
B.2 Proof of 2 in Theorem 4.1 (Lipschitz stability of alignment-adjusted rewards)
21
B.3 Proof of 3 in Theorem 4.1 (Margin robustness under Gaussian noise) . . . . .
22
B.4 Proof of 4 in Theorem 4.1 (Convergence of orchestration weights) . . . . . . .
23
B.5 Proof of 5 in Theorem 4.1 (Consistency of reward estimates) . . . . . . . . . .
25
C Visualization of the Synthetic Datasets
26
D Additional Synthetic Experiments
27
D.1 Dataset and Task Description . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
D.2 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
D.3 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
D.4 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
D.5 Ablation Study: Sensitivity to the Alignment Penalty λ . . . . . . . . . . . .
28
E Semi-Synthetic Experiment Settings
28
F Additional Semi-Synthetic Experiments and Figures
29
F.1 Diagnostic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
F.2 Escalation Rate and Escalation Rate on Shifted Patients . . . . . . . . . . . .
30
F.3 Ablation Study: Sensitivity to the Alignment Penalty λ . . . . . . . . . . . .
30
16
A
Algorithm: Bandit–OT Orchestration with Survival-Based Rewards
A.1
i.i.d. Task Arrivals
Algorithm 1 BOT-Orch: i.i.d. Task Version 1: Input: Agents A = {a1 , . . . , aM }, OT cost c, alignment weight λ ≥ 0, horizon T , survival
model Si (·), learning rate α, inverse temperature ηt 2: Initialize estimated rewards r̂0 (i) = 0 and frailty θ0 = 1 for all i ∈ A 3: for t = 1 to T do 4: Sample task xt ∼ PX ▷ i.i.d. task sampling 5: Sample latent frailty θt ∼ p(θ) 6: for i = 1 to M do 7: Compute agent output distribution µi 8: Compute OT alignment cost Wt (i) = Wc (νt , µi ) + ϵt (i) 9: Sample survival time Tt (i) and censoring δt (i) 10: Compute reward: Rt (i) = δt (i) Si (Tt (i) | xt )θt 11: Update estimated reward: r̂t (i) = αr̂t−1 (i) + (1 − α)Rt (i) 12: end for 13: Compute orchestration policy: exp(ηt [r̂t (i) − λWt (i)]) πt (i) = PM j=1 exp(ηt [r̂t (j) − λWt (j)]) 14:
Sample and execute agent it ∼ πt
15: end for 16: Output: Policies {πt }T t=1 and cumulative reward
17
A.2
Non-i.i.d. Task Arrivals
Algorithm 2 BOT-Orch: Non-i.i.d. Task Version 1: Input: Same as Algorithm 1 2: Initialize r̂0 (i) = 0 and θ0 = 1 for all i ∈ A 3: for t = 1 to T do 4: Sample task xt ∼ P(xt | Ht ) ▷ history-dependent, non-i.i.d. 5: Sample latent frailty θt ∼ p(θt | Ht ) 6: for i = 1 to M do 7: Compute agent output distribution µi 8: Compute OT alignment cost Wt (i) = Wc (νt , µi ) + ϵt (i) 9: Sample survival time Tt (i) and censoring δt (i) 10: Compute reward: Rt (i) = δt (i) Si (Tt (i) | xt )θt 11: Update estimated reward using history: ▷ temporal dependence from past rewards r̂t (i) = αr̂t−1 (i) + (1 − α)Rt (i) + fi (R1:t−1 ) 12: 13:
end for Compute orchestration policy: exp(ηt [r̂t (i) − λWt (i)]) πt (i) = PM j=1 exp(ηt [r̂t (j) − λWt (j)])
Sample and execute agent it ∼ πt 15: Update history Ht+1 = Ht ∪ {(xt , Rt , Wt )} 16: end for 17: Output: Policies {πt }T t=1 and cumulative reward 14:
Derivation of Algorithms from the Theoretical Framework (Special Case Realisation). The BOT-Orch algorithms in Algorithms 1 and 2 can be formally interpreted as special cases of the abstract framework introduced in Theorem 4.1. At the theoretical level, the model is defined in terms of an unobserved alignment-adjusted reward process rt (i) = E[Rt (i) | xt ] − λWc (µi , νt ), over which the learning dynamics are characterised via exponential-weights updates on the simplex. The algorithms instantiate this framework by specifying an explicit stochastic realisation of the reward process together with a consistent estimator of its conditional expectation. In particular, the survival–frailty construction generates bounded random variables Rt (i) whose conditional expectation coincides with the abstract reward functional assumed in the theory, thereby embedding the model within a well-defined stochastic process satisfying assumptions (A2)–(A4). The empirical quantity r̂t (i), defined via exponential smoothing in the i.i.d. case and augmented with a history-dependent correction term in the non-i.i.d. case, constitutes a Robbins–Monro stochastic approximation of E[Rt (i) | xt ] Robbins and Monro [1951], ensuring asymptotic consistency under the respective dependence structures. Substituting this estimator into the theoretical objective yields a computable approximation of rt (i), while the entropy-regularised optimisation over ∆|A|−1 induces the softmax policy used in the algorithm. Consequently, the i.i.d. algorithm corresponds to the stationary special case in which (xt , θt ) are independent draws and the induced reward process is temporally homogeneous, whereas the non-i.i.d. algorithm generalises this construction to an adapted filtration Ht , allowing for history-dependent task and frailty evolution while preserving boundedness and measurability of the reward sequence. In both cases, the algorithm complements by providing an explicit 18
implementation of the main theorem, showing that BOT-Orch is a realised instance of the general OT-regularised exponential-weights framework under different assumptions on the data-generating process.
B
Appendix: Missing Proofs
This appendix contains full proofs of the statements in Section 4.
B.1
Proof of 1 in Theorem 4.1 (Sublinear OT-Regret)
Theorem B.1 (Sublinear OT-Regret). Assume (A1)–(A5). Let the BOT–Orch policy be defined by wt (i) πt (i) = PM , wt+1 (i) = wt (i) exp ηt (Rti − λWti ) , j=1 wt (j) where Rti and Wti are the realized reward and OT costs. Define the pseudo-regret RT :=
T X t=1
max
i∈{1,...,M }
E[Rti − λWti | xt ] − Eit ∼πt [Rtit − λWtit ] .
If the inverse-temperature schedule satisfies ηt ≍ t−1/2 by Assumption (A5), then √ RT = O( T ). Proof. The expected per-round utility of a policy πt ∈ ∆(A) is Rt (πt ) =
M X
πt (i) ri (xt ) − λwi (xt ) .
i=1
For each agent i, define the realized instantaneous utility uit := Rti − λWti , and its conditional expectation ūit := ri (xt ) − λwi (xt ). We compare against a fixed action i∗ ∈ {1, . . . , M }. The oracle policy selects Rt (πt∗ ) = max ri (xt ) − λwi (xt ) , 1≤i≤M
i.e. a point mass on the best action in each round. Define the log-partition potential Φt := log
M X
wt (i).
i=1
By assumption (A1), there exist constants a < b such that for all t, i, uit ∈ [a, b].
19
Step 1: Constant inverse temperature. Assume ηt ≡ η > 0. Then Φt+1 − Φt = log
M X
πt (i) exp ηuit .
i=1
Applying Hoeffding’s lemma, Φt+1 − Φt ≤ η
M X
πt (i)uit +
i=1
η2 (b − a)2 . 8
Summing over t = 1, . . . , T gives ΦT +1 − Φ1 ≤ η
T X M X
πt (i)uit +
t=1 i=1
η2T (b − a)2 . 8
On the other hand, for any fixed i∗ , ∗
∗
ΦT +1 ≥ log wT +1 (i ) = log w1 (i ) + η
T X
∗
uit .
t=1
With uniform initialization w1 (i) = 1, we obtain T X t=1
∗ uit −
T X M X
πt (i)uit ≤
t=1 i=1
ηT log M + (b − a)2 . η 8
Choosing s η=
8 log M T (b − a)2
yields r RT ≤ (b − a)
T log M . 2
Taking conditional expectations with respect to Ht−1 , E[uit | xt , Ht−1 ] = ri (xt ) − λwi (xt ), gives the same regret bound in expectation. Step 2: Time-varying inverse temperature. Let ηt ≍ t−1/2 . Then Φt+1 − Φt ≤ ηt
M X
πt (i)uit +
i=1
ηt2 (b − a)2 . 8
Summing over t yields T
RT ≤
(b − a)2 X 2 log M + ηt . ηT 8 t=1
Since ηt = ct−1/2 , √ 1 = O( T ), ηT so
T X
ηt2 = O(log T ),
t=1
√ RT = O( T ).
If uit admits a martingale decomposition with bounded increments, Azuma–Hoeffding implies √ that deviations between realized and conditional cumulative utilities are O( T ) (up to log factors), which does not change the overall regret rate. 20
B.2
Proof of 2 in Theorem 4.1 (Lipschitz stability of alignment-adjusted rewards)
Proposition B.2 (OT geometry and preference stability). Assume (A1). Let A = {a1 , . . . , aM } be the set of agents, X ⊂ Rd be the measurable space and Y denote the outcome space. For i ∈ {1, · · · , M } let each agent be denoted as ai and let µi ∈ P(Y) be its source outcome distribution. For each task xt ∈ X , let ν(xt ) ∈ P(Y) denote the task-induced target outcome distribution. Define the cost as Wti := Wc (νt , µi ) + ϵit , such that E[ϵit | xt ] = 0. Let the conditional cost wi (xt ) := E[Wti | xt ] = Wc (νt , µi ) and conditional reward as ri (xt ) := E[Rti | xt ]. Then, the following statements hold: (i) For any νt , νt′ ∈ P(Y), we have Wc (νt , µi ) − Wc (νt′ , µi ) ≤ L W1 (νt , νt′ ). (ii) If ri (xt ) = rj (xt ), then for any λ > 0, we have Wc (νt , µi ) < Wc (νt , µj ) ⇐⇒ ri (xt ) − λwi (xt ) > rj (xt ) − λwj (xt ). Proof. We outline the proof in a sequence. (i) By definition of wi (xt ; νt ) and wi (xt ; νt′ ), wi (xt ; νt ) − wi (xt ; νt′ ) = Wc (νt , µi ) − Wc (νt′ , µi ) .
(1)
Since c is L-Lipschitz by (A1), standard Wasserstein stability implies Wc (νt , µi ) − Wc (νt′ , µi ) ≤ L W1 (νt , νt′ ),
(2)
ri (xt ) − λwi (xt ) − rj (xt ) − λwj (xt ) = −λ wi (xt ) − wj (xt ) .
(3)
which proves (i). (ii) Using ri (xt ) = rj (xt ),
Since λ > 0, this implies ri (xt ) − λwi (xt ) > rj (xt ) − λwj (xt ) ⇐⇒ wi (xt ) < wj (xt ).
(4)
Substituting wi (xt ) = Wc (νt , µi ) completes the result. Lemma B.3 (Concentration of frailty-adjusted rewards). Assume (A3)–(A4). Fix xt ∈ X and ai ∈ A, and define the frailty reward as Rti := δt (i) Si (Tt (i) | xt )θt , where 0 ≤ Si (τ | xt ) ≤ 1, θt > 0, and δt (i) ∈ {0, 1}. Then, the centered reward Rti − E[Rti | xt ] is conditionally subGaussian. More precisely, for every ε > 0, 2 P Rti − E[Rti | xt ] > ε xt ≤ 2e−2ε . Proof. Since 0 ≤ Si (Tt (i) | xt ) ≤ 1 and δt (i) ∈ {0, 1}, we have 0 ≤ Rti ≤ 1
almost surely.
Fix xt and define m := E[Rti | xt ],
X := Rti − m.
Then m ∈ [0, 1] and E[X | xt ] = 0. We first bound the conditional moment generating function. For any λ ∈ R, convexity of y 7→ eλy on [0, 1] implies that for every y ∈ [0, 1], eλy ≤ (1 − y)e0 + yeλ = 1 − y + yeλ . 21
Applying this pointwise inequality to Rti and taking conditional expectation yields i
E[eλRt | xt ] ≤ 1 + m(eλ − 1). Therefore, i E[eλX | xt ] = e−λm E[eλRt | xt ] ≤ e−λm 1 + m(eλ − 1) =: ϕ(λ, m). Define ψ(λ) := log ϕ(λ, m). A direct computation gives ψ(0) = 0,
ψ ′ (0) = 0,
ψ ′′ (λ) =
m(1 − m)eλ . (1 − m + meλ )2
A direct simplification shows that ψ ′′ (λ) =
1 1 ≤ 2 4 4 cosh (λ/2)
for all λ ∈ R, m ∈ [0, 1].
Now apply Taylor’s theorem with integral remainder: Z λ (λ − s)ψ ′′ (s) ds. ψ(λ) = ψ(0) + ψ ′ (0)λ + 0
Using ψ(0) = ψ ′ (0) = 0 and ψ ′′ (s) ≤ 14 , we obtain Z λ ψ(λ) ≤
1 λ2 (λ − s) ds = . 4 8 0
Hence, λX
E[e
2 λ | xt ] ≤ exp , 8
so X is conditionally sub-Gaussian with variance proxy 1/4. Finally, for any λ > 0, Markov’s inequality gives λ2 P(X > ε | xt ) ≤ exp −λε + . 8 Optimizing in λ yields λ = 4ε, hence P(X > ε | xt ) ≤ exp(−2ε2 ). Applying the same argument to −X yields 2
P(|X| > ε | xt ) ≤ 2e−2ε .
B.3
Proof of 3 in Theorem 4.1 (Margin robustness under Gaussian noise)
fc (µi , ν) = Wc (µi , ν) + ϵi , where Lemma B.4 (Margin robustness under Gaussian noise). Let W 2 ϵi ∼ N (0, σ ) are independent. Define for λ > 0, ∆ij := λ(Wc (µj , ν) − Wc (µi , ν)). If ∆ij > 0, then the probability of incorrect ordering satisfies ! 2 ∆ ∆ 1 ij ij P ri (xt ) < rj (xt ) = Φ − √ ≤ exp − 2 . 2 4σ 2σ √ In particular, if ∆ij ≥ σ 2 log 2, then P ri (xt ) < rj (xt ) ≤ 14 . 22
Proof. Without loss of generality assume ∆ij > 0. The noisy difference satisfies e ij = λ(W fc (µj , ν) − W fc (µi , ν)) = ∆ij + Z, ∆ where Z = ϵj − ϵi ∼ N (0, 2σ 2 ). A misranking occurs when ri (xt ) < rj (xt ), which is equivalent e ij < 0, i.e. Z < −∆ij . Hence to ∆ ∆ij i j √ P(r (xt ) < r (xt )) = P(Z < −∆ij ) = Φ − . 2σ 2
Using the Gaussian tail bound Φ(−x) ≤ 12 e−x /2 for x ≥ 0, we obtain ! ∆2ij 1 i j P(r (xt ) < r (xt )) ≤ exp − 2 . 2 4σ √ The condition ∆ij ≥ σ 2 log 2 ensures the right-hand side is at most 1/4, completing the proof.
B.4
Proof of 4 in Theorem 4.1 (Convergence of orchestration weights)
Theorem B.5 (Almost-sure convergence of orchestration weights). Assume (A1)–(A5). Let (γt )t≥0 satisfy ∞ ∞ X X γt > 0, γt = ∞, γt2 < ∞. t=0
t=0
Assume the task process (xt ) is stationary and independent of (ϕt ), and that there exists a measurable function r̄ : X → RM such that E[Rti − λWti | xt ] = r̄i (xt ). Then (ϕt ) converges almost surely to the internally chain transitive set of the ODE ϕ̇ = Softmax(r̄(x)) − ϕ, where r̄(x) is evaluated under the stationary distribution of xt . Proof. Let Ft = σ(ϕs , xs , Rs , Ws : s ≤ t). The update can be written as ϕt+1 = ϕt + γt Softmax(ut ) − ϕt , where ut := (Rti − λWti )M i=1 . Define the drift: H(ϕt ) := E[Softmax(ut ) | Ft−1 ] − ϕt , and the noise term: ξt+1 := Softmax(ut ) − E[Softmax(ut ) | Ft−1 ]. Then ϕt+1 = ϕt + γt H(ϕt ) + ξt+1 . By boundedness of rewards, Softmax(ut ) takes values in the simplex, hence ξt+1 is a martingale difference sequence with bounded second moments.
23
Now use the stationarity assumption: since xt is stationary and independent of ϕt , E[Softmax(ut ) | Ft−1 ] = Ex∼πx Softmax(r̄(x)) , where πx is the invariant distribution of (xt ). Define the averaged drift H̄(ϕ) := Ex∼πx Softmax(r̄(x)) − ϕ. Then the recursion becomes a standard Robbins–Monro scheme: ϕt+1 = ϕt + γt H̄(ϕt ) + ξt+1 + o(1) . The function H̄ is Lipschitz on the simplex, and the noise term has bounded second moment. The step-size conditions ensure X X γt = ∞, γt2 < ∞, t
t
so the stochastic approximation framework applies. By the stochastic approximation theorem of Benaïm (1999), the piecewise linear interpolation of (ϕt ) is an asymptotic pseudo-trajectory of the ODE ϕ̇ = H̄(ϕ). Therefore, the limit set of (ϕt ) is contained in the internally chain transitive invariant sets of this ODE. Since the ODE is a linear contraction toward the fixed point ϕ∗ = Ex∼πx [Softmax(r̄(x))], all internally chain transitive sets reduce to this equilibrium, which is globally asymptotically stable. Hence,
a.s.
ϕt −−→ ϕ∗ .
Remark B.6. The proof follows a stochastic approximation argument in which the orchestration weights evolve as a Robbins–Monro recursion driven by a softmax response to OT-adjusted rewards. The key step is the decomposition of the update into a deterministic drift term and a martingale difference noise, allowing the dynamics to be linked to a limiting ordinary differential equation via the asymptotic pseudo-trajectory framework. Intuitively, the softmax operator induces a smooth, entropy-regularised selection mechanism that continuously reweights agents according to their relative OT-adjusted performance. Under step sizes satisfying the usual summability conditions, stochastic fluctuations vanish asymptotically, and the evolution tracks the averaged response of this softmax mechanism under the stationary task distribution. The main structural novelty lies in the fact that the drift is not driven by exogenous rewards but by optimal-transport-adjusted utilities, which couple agent performance through a geometric cost. This embeds a stochastic approximation scheme into a geometry-aware, mean-field decision system, where the limiting ODE describes an entropy-regularised flow toward stationary softmax equilibria.
24
B.5
Proof of 5 in Theorem 4.1 (Consistency of reward estimates)
Theorem B.7 (Empirical reward decomposition and consistency). Assume (A2)–(A4) and bounded rewards |Rti | ≤ Rmax . Define t
ri (xt ) := E[Rti | xt ],
r̂t (i) :=
1X i Rs . t s=1
Then the following hold: (i) i.i.d. case. If (xt , Rt )t≥1 are i.i.d., then for every i ∈ A, a.s.
r̂t (i) −−−→ E[Rti ]. t→∞
(ii) general (possibly non-i.i.d.) case. Let Ht−1 be the filtration generated by (xs , Rs )s≤t−1 , and define the martingale difference sequence ξt (i) := Rti − E[Rti | Ht−1 ]. Assume E[ξt (i) | Ht−1 ] = 0 and |ξt (i)| ≤ Rmax a.s. Then, for every i ∈ A, t
1X a.s. r̂t (i) − E[Rsi | Hs−1 ] −−−→ 0. t→∞ t s=1
Moreover, since A is finite, t
1X a.s. E[Rsi | Hs−1 ] −−−→ 0. sup r̂t (i) − t→∞ t i∈A s=1
Proof. We treat the two cases separately. (i) i.i.d. case. If (xt , Rt ) are i.i.d., then (Rti )t≥1 is an i.i.d. integrable sequence. Hence, by the strong law of large numbers, t
r̂t (i) =
1 X i a.s. Rs −−−→ E[Rti ]. t→∞ t s=1
(ii) general non-i.i.d. case. Let Ht := σ(xs , Rs : s ≤ t) and write Rti = E[Rti | Ht−1 ] + ξt (i),
ξt (i) := Rti − E[Rti | Ht−1 ].
Then (ξt (i), Ht ) is a martingale difference sequence with 2 E[ξt (i)2 | Ht−1 ] ≤ Rmax .
E[ξt (i) | Ht−1 ] = 0, Summing over t gives r̂t (i) =
t
t
s=1
s=1
t
t
s=1
s=1
1X 1X E[Rsi | Hs−1 ] + ξs (i). t t
Hence, r̂t (i) − Since
1X 1X E[Rsi | Hs−1 ] = ξs (i). t t
∞ X E[ξt (i)2 | Ht−1 ] t=1
t2
2 ≤ Rmax
∞ X 1 t=1
25
t2
< ∞,
the martingale strong law implies t
1X a.s. ξs (i) −−−→ 0. t→∞ t s=1
Therefore, t
r̂t (i) −
1X a.s. E[Rsi | Hs−1 ] −−−→ 0. t→∞ t s=1
Finally, since A is finite, taking a maximum preserves almost sure convergence: t
1X a.s. max ξs (i) −−−→ 0. t→∞ i∈A t s=1
Remark B.8. In the i.i.d. case, the empirical average r̂t (i) is formed from independent samples drawn from a fixed distribution, so the strong law of large numbers implies convergence to the constant mean E[Rti ]. In the non-i.i.d. case, the rewards are adapted to the history and admit the decomposition into a predictable component E[Rti | Ht−1 ] and a martingale difference noise term. Consequently, the empirical average splits into the time-average of the predictable process and a martingale average, and boundedness ensures that the latter vanishes almost surely. This yields that r̂t (i) tracks the time-averaged conditional expectation t
1X E[Rsi | Hs−1 ], t s=1
up to an asymptotically negligible martingale error. However, full convergence of r̂t (i) is not guaranteed in general, since the predictable process E[Rti | Ht−1 ] may itself fail to converge or even fail to admit a Cesàro limit (for instance, under oscillatory or adversarial dynamics). Additional structure, such as ergodicity or asymptotic stationarity of the conditional mean process, is required to ensure convergence of the empirical averages.
C
Visualization of the Synthetic Datasets
Figure 2: IID data generation (a) IID task contexts sampled from a half-moons distribution, illustrating a stationary but structured task space. (b) IID reward distributions for K agents, where rewards are independently drawn over time from fixed distributions with a matched mean (approximately 0.5) but heterogeneous higher-order properties (e.g., variance, skewness, and bimodality). 26
Figure 3: Non-IID data generation (a) Piecewise-stationary rewards where the variance changes at unknown changepoints while the mean remains fixed, shown as reward trajectories over time across agents. (b) Segment-wise reward histograms for a representative agent, revealing distributional shifts induced by variance changepoints. (c) Smooth-drift setting where agent reward means evolve gradually according to a sinusoidal drift (shown via rolling mean trajectories), inducing continuous non-stationarity. (d)Brownian-bridge setting illustrating temporally correlated latent mean paths constrained to fixed endpoints, producing structured stochastic dependence across time.
D
Additional Synthetic Experiments
D.1
Dataset and Task Description
Datasets and tasks are as in 6.
D.2
Baselines
Baselines are as in Section 6.
D.3
Evaluation Metrics
• Event rate. P Under survival-style feedback with censoring indicator δt (it ) ∈ {0, 1}, we report T1 Tt=1 δt (it ), i.e., the fraction of rounds with uncensored (fully observed) outcomes. Higher event rates indicate less censoring and more informative feedback. P • Mean observed time. We report the mean observed time T1 Tt=1 Ttobs (it ), where Ttobs (it ) = min{Tt (it ), Ct (it )} under right censoring. This metric summarizes the typical observed completion time under the censoring mechanism.
D.4
Results.
Table 4 reports event rate and mean observed time. BOT-Orch achieves the highest event rate and lowest mean observed time across all environments, in both IID and non-IID settings, consistently outperforming No-OT, Random, and UCB1. 27
Environment IID IID-G IID-M Non-IID NonIID-BB NonIID-PS NonIID-SD
Event Rate BOT-Orch No-OT (λ=0) Random
Mean Observed Time UCB1 (MAB) BOT-Orch No-OT (λ=0) Random UCB1 (MAB)
0.63±0.02 0.65±0.04
0.60±0.02 0.60±0.04
0.58±0.04 0.60±0.03
0.54±0.03 0.59±0.03
0.59±0.04 0.58±0.02
0.66±0.04 0.66±0.04
0.72±0.04 0.69±0.03
0.71±0.03 0.70±0.05
0.67±0.04 0.66±0.04 0.65±0.03
0.61±0.03 0.64±0.02 0.64±0.03
0.61±0.02 0.59±0.04 0.60±0.04
0.62±0.05 0.59±0.02 0.57±0.02
0.55±0.09 0.56±0.04 0.59±0.03
0.62±0.01 0.62±0.04 0.64±0.05
0.65±0.04 0.67±0.03 0.67±0.03
0.63±0.03 0.69±0.04 0.67±0.04
Table 4: Event Rate and Mean Observed Time (mean ± 95% CI across 5 seeds; T = 200). IID (Algorithm 1) λ Cum. net Regret Team acc. 0 -311.34±3.43 122.61±2.49 0.177±0.013 0.5 -271.42±2.79 82.68±1.92 0.336±0.011 1 -262.29±2.69 73.56±1.78 0.380±0.011 1.25 -259.93±2.57 71.19±1.78 0.386±0.011 1.5 -258.52±2.62 69.78±1.72 0.389±0.011 1.75 -257.98±2.27 69.24±1.47 0.398±0.009 2 -256.20±2.55 67.47±1.64 0.403±0.010 3 -253.76±2.49 65.02±1.60 0.412±0.011 5 -253.28±2.04 64.54±1.67 0.413±0.010 10 -251.99±2.16 63.25±1.46 0.420±0.009 11 -252.06±2.22 63.32±1.47 0.420±0.009 12 -252.05±2.28 63.32±1.51 0.420±0.009 13 -251.60±2.33 62.86±1.60 0.422±0.009 14 -251.71±2.42 62.97±1.50 0.423±0.009 15 -251.80±2.45 63.06±1.56 0.423±0.008 Reference baselines (λ-independent) No-OT -311.34±3.43 122.61±2.49 0.177±0.013 Random -315.75±3.74 127.02±3.11 0.177±0.010 UCB1 -313.22±3.92 124.48±2.93 0.177±0.012
Non-IID (Algorithm 2) Cum. net Regret Team acc. -722.67±47.12 317.61±21.59 0.177±0.013 -549.11±33.07 144.05±5.85 0.418±0.017 -531.17±31.69 126.11±4.86 0.453±0.017 -528.55±31.48 123.49±5.23 0.459±0.019 -526.24±31.88 121.18±5.18 0.462±0.018 -524.10±31.77 119.04±5.49 0.470±0.019 -524.22±31.76 119.16±5.05 0.469±0.018 -519.79±31.65 114.72±4.79 0.479±0.019 -515.97±32.03 110.91±5.11 0.484±0.020 -514.23±31.32 109.16±4.67 0.493±0.018 -513.61±31.26 108.54±4.71 0.495±0.018 -512.93±31.33 107.86±4.73 0.495±0.018 -513.01±31.01 107.95±5.00 0.494±0.018 -513.16±30.99 108.10±5.07 0.494±0.018 -513.45±31.02 108.39±5.01 0.493±0.018 -722.67±47.12 -731.00±50.00 -722.86±48.17
317.61±21.59 325.93±22.38 317.79±21.51
0.177±0.013 0.169±0.010 0.178±0.009
Table 5: λ grid search results for BOT-Orch on synthetic tasks. Mean ± 95% CI across 30 seeds, T = 114, evaluated with λeval = 1.0. λ = 0 reproduces No-OT by construction (sanity check). Selected λ∗ = 13 (bold) maximizes average Cum. net across IID/Non-IID panels. Reference baselines at the bottom are λ-independent.
D.5
Ablation Study: Sensitivity to the Alignment Penalty λ
The alignment penalty weight λ controls the trade-off between exploitation of historical reward estimates r̂t (i) and adherence to OT-based distributional alignment Wt (i). We conduct a grid search over λ ∈ {0.0, 0.5, 1.0, 1.25, 1.5, 1.75, 2.0, 3.0, 5.0, 10.0}, running BOT-Orch for 30 seeds under both the IID (Algorithm 1) and Non-IID (Algorithm 2) conditions. The No-OT, Random, and UCB1 baselines serve as fixed reference lines since they are independent of λ. Table 5 summarise the results.
E
Semi-Synthetic Experiment Settings
Agents. We set M = 2 agents: • Agent 0 (AI): a logistic regression classifier (L2, C=1.0) trained on the training split and calibrated using Platt scaling (isotonic regression) on the calibration split. Accuracy: 98.2% in-distribution, 80.7% under shift. • Agent 1 (Human): a simulated clinical expert with complementary accuracy 88.0% on in-distribution patients, 94.7% on shifted patients. The human expert is more accurate on the patients the AI handles worst, confirming a positive complementarity gap ∆comp > 0.
28
Tasks and reward. At each round t, a patient biopsy xt ∈ X arrives. The reward is binary correctness: Rt (i) = 1[agent i classifies patient t correctly]. This is bounded in [0, 1], satisfying Assumption (A2). We use bandit feedback throughout and only the chosen agent’s reward is observed. OT alignment costs. We use the output-space OT alignment cost on the binary label simplex {0, 1} with ground cost C = 01 10 (0-1 loss). Under this cost, the Wasserstein distance between the true label one-hot νt = δyt and each agent’s predictive distribution admits the closed form: Wt (AI) = 1 − Rt (AI) (probability AI is wrong on patient t),
(5)
Wt (human) = 1 − ph (xt ) (probability human is wrong on patient t),
(6)
where ph (xt ) is the human’s accuracy for that patient’s shift status. This is a direct instantiation of the general alignment cost Wc (νt , µi ) defined in Section 3.4. The closed form follows from the exactness of Sinkhorn transport on the 2 × 2 binary simplex. OT Dominance verification. With these costs, under distribution shift: Wt (AI) ≈ 0.193 vs. Wt (human) ≈ 0.053. The gap Wt (AI) − Wt (human) = 0.140 is large and positive on shifted patients, confirming the precondition of Theorem 4.2 Part 2 that the human has strictly lower alignment cost on shifted patients and should be preferred by the BOT-Orch policy. On in-distribution patients the relationship is reversed (Wt (AI) ≈ 0.018 < 0.120 = Wt (human)), so the AI is correctly preferred there. This is exactly the complementarity structure that BOT-Orch is designed to exploit without being told about the shift.
F
Additional Semi-Synthetic Experiments and Figures
F.1
Diagnostic Analysis
Figure 4 and 5 provide diagnostic analyses.
Figure 4: Escalation rate by distribution condition. Mean escalation rate for indistribution patients (blue) and shifted patients (red) per method. Error bars show standard deviation across seeds. Left: IID condition; right: Non-IID condition. BOT-Orch achieves a higher escalation rate on shifted patients relative to in-distribution patients compared to all baselines, demonstrating targeted routing. No-OT’s large error bars reflect bimodal behaviour across seeds: some runs converge to always-AI and others to always-human, due to the cold-start problem in the binary bandit without OT regularisation. 29
Figure 5: Agent selection trajectories, Non-IID condition (Algorithm 2). Rolling probability of routing to the human expert (window w=8 rounds) for each method over the deployment episode. The dotted vertical line marks the shift onset at round 57. BOT-Orch (top-left): routing probability rises after the shift, showing adaptation. No-OT (top-right): high variance, consistent with the bimodal cold-start behaviour observed in Table 3. UCB1 (bottom-right): also adapts but less precisely, routing more patients to the human without the alignment-cost targeting of BOT-Orch. Random (bottom-left): flat at 50% throughout as expected.
F.2
Escalation Rate and Escalation Rate on Shifted Patients
We present the escalation rate and escalation rate on shifted patients in Table 6 Escalation Rate Escalation Rate on Shifted Patients BOT-Orch No-OT (λ=0) Random UCB1 BOT-Orch No-OT (λ=0) Random UCB1 IID 0.214±0.066 0.493±0.360 0.505±0.046 0.519±0.061 0.283±0.085 0.499±0.362 0.533±0.064 0.514±0.073 Non-IID 0.192±0.023 0.485±0.484 0.505±0.046 0.506±0.062 0.209±0.019 0.488±0.495 0.494±0.065 0.612±0.074
Table 6: Deployment metrics across all four methods and both experimental conditions. Mean ± 95% CI across 30 seeds, T =114, λ=3.0. Esc. rate: fraction of patients routed to human. Esc.(shift): escalation rate on shifted patients only. IID condition uses Algorithm 1; Non-IID uses Algorithm 2 (ID patients rounds 1–57, shifted rounds 58–114).
F.3
Ablation Study: Sensitivity to the Alignment Penalty λ
The alignment penalty weight λ controls the trade-off between exploitation of historical reward estimates r̂t (i) and adherence to OT-based distributional alignment Wt (i). We conduct a grid search over λ ∈ {0.0, 0.5, 1.0, 1.25, 1.5, 1.75, 2.0, 3.0, 5.0, 10.0}, running BOT-Orch for 30 seeds under both the IID (Algorithm 1) and Non-IID (Algorithm 2) conditions. The No-OT, Random, and UCB1 baselines serve as fixed reference lines since they are independent of λ. Table 7 and Figure 6 summarise the results.
30
IID (Algorithm 1) λ Cum. net Regret Team acc. 0.0 103.37±2.51 9.80±1.61 0.907±0.022 0.5 102.83±3.92 10.06±3.50 0.935±0.026 1.0 105.65±5.57 7.03±5.13 0.964±0.028 1.25 106.17±6.04 6.33±5.60 0.970±0.027 1.5 106.90±5.37 5.29±5.08 0.975±0.022 1.75 107.18±5.74 4.96±5.61 0.979±0.021 2.0 107.27±5.95 4.48±5.65 0.980±0.021 3.0 108.84±2.22 2.29±2.11 0.988±0.010 5.0 108.88±1.25 1.01±1.04 0.993±0.006 10.0 105.90±1.01 0.26±0.38 0.993±0.008 Reference baselines (λ-independent) No-OT 103.37±2.51 9.80±1.61 0.907±0.022 Random 83.98±5.92 28.72±6.03 0.917±0.020 UCB1 80.55±4.88 31.31±3.98 0.902±0.026
Non-IID (Algorithm 2) Cum. net Regret Team acc. 103.17±1.80 10.14±1.17 0.905±0.016 98.17±2.73 14.92±2.06 0.908±0.019 98.02±6.26 14.61±6.10 0.930±0.029 102.47±6.83 9.98±6.69 0.955±0.027 106.04±6.21 5.91±6.18 0.970±0.025 108.04±5.57 4.08±5.50 0.981±0.018 109.19±5.53 2.71±5.48 0.986±0.017 110.61±1.03 0.59±0.93 0.993±0.007 109.61±0.99 0.37±0.67 0.995±0.006 106.34±0.73 0.10±0.29 0.995±0.006 103.17±1.80 79.78±5.52 85.82±4.91
10.14±1.17 32.97±4.87 26.26±4.28
0.905±0.016 0.905±0.024 0.919±0.025
Table 7: λ grid search results for BOT-Orch. Mean ± 95% CI across 30 seeds, T =114. λ=0 reproduces No-OT exactly (sanity check: difference = 0.000). Optimal value λ∗ =3.0 in bold. Reference baselines at the bottom are λ-independent. Sensitivity and Optimal λ. In the IID condition (Figure 6, top row), cumulative net utility increases monotonically from λ=0 through λ=5.0 before declining at λ=10.0. The difference between λ=3.0 (108.84 ± 2.22) and λ=5.0 (108.88 ± 1.25) is 0.04 units — well within one standard deviation — and the two values are statistically indistinguishable. Phase Transition in Non-IID Settings. A qualitatively different pattern emerges in the Non-IID condition (Figure 6, bottom row). For λ ∈ {0.5, 1.0, 1.25}, BOT-Orch performs worse than No-OT, with net utility falling to as low as 98.02 at λ=1.0 against the No-OT baseline of 103.17 (red-shaded cells in Table 7). This counterintuitive dip arises because any positive λ penalises the human agent during the first 57 in-distribution rounds (where Wt (human)=0.120 > Wt (AI)≈0), suppressing its EMA reward estimate through disuse. When the distribution shifts at round 58, a small λ is insufficient to override the depressed human reward history, and routing fails to redirect to the human. Performance recovers sharply above λ≈1.5, where the OT signal becomes strong enough to dominate stale reward estimates immediately when the shift arrives, and improves monotonically to the peak at λ∗ =3.0. Degeneracy at Large λ. For λ ≥ 5.0, the OT penalty dominates the reward signal entirely. The policy degenerates toward a near-deterministic OT routing rule, effectively ignoring learned reward history. Two symptoms confirm this regime: (i) the standard deviation of net utility collapses from ±5.53 at λ=2.0 to ±0.73 at λ=10.0 in Non-IID — not because the policy is more stable but because it is no longer exploring; and (ii) net utility falls at λ=10.0 (105.90 IID, 106.34 Non-IID) below the optimum at λ∗ =3.0. Identification of λ∗ =3.0. We identify λ∗ =3.0 as the joint optimum across both conditions on the primary metric. It achieves the peak net utility in the Non-IID condition (110.61 ± 1.03), is statistically tied with λ=5.0 in IID (gap 0.04 < pooled std 1.73), reduces variance by 3× relative to λ=2.0, and is the last value at which bandit learning and OT alignment both contribute meaningfully. The gain over the initial engineering value of λ=2.0 is +1.42 net utility in Non-IID, confirming that the grid search yields a meaningful improvement rather than a marginal one.
31
Figure 6: λ sensitivity curves. Cumulative net utility (left), oracle regret (centre), and team accuracy (right) as functions of λ for BOT-Orch (teal line with ±1 std shading). Horizontal dashed lines show the No-OT, Random, and UCB1 baselines. The dotted vertical line marks λ=2.0 (initial value); λ∗ =3.0 (grid-search optimum) is identified by the peak. Top row : IID (Algorithm 1); bottom row : Non-IID (Algorithm 2). In the Non-IID panels, performance at λ ∈ {0.5, 1.0, 1.25} falls below the No-OT baseline, revealing the phase transition.
Figure 7: Escalation rate on shifted patients (left axis, red) and cumulative alignment cost (right axis, teal) as functions of λ. Horizontal dashed lines show No-OT, Random, and UCB1 escalation rates. Alignment cost decreases monotonically with λ, confirming Theorem 4.2 Part 1. Left: IID condition; right: Non-IID condition.
32