Sequential Allocation for Agent Routing
Abstract
A meta-algorithm that routes each incoming task to one of $K$ specialist agents is a sequential allocation problem. If the quality of a specialist on a task is an unknown random payoff, the classical stochastic multi-armed bandit model applies. We restate the UCB1 index and the finite-time regret bound of Auer, Cesa-Bianchi, and Fischer (2002), and we record where the hypotheses fail for language-model agents. This editorial primer is an orientation, not a peer-reviewed research claim.
1. Routing as sequential allocation
Let $\mathcal{A} = \{1,\dots,K\}$ be a finite set of specialist agents — a retriever, a code editor, a web browser, a planner. At round $t = 1,\dots,T$ a meta-controller observes a task $x_t$ and selects an arm $A_t \in \mathcal{A}$. After the chosen agent acts, the controller receives a scalar payoff $X_t \in [0,1]$: a unit test that passed, a judge score, a human accept/reject. Write $\mu_i = \mathbb{E}[X_t \mid A_t = i]$ when the payoff distribution of arm $i$ is stationary, and let $\mu^* = \max_i \mu_i$.
The (pseudo)regret of a routing policy $\pi$ is
where $N_i(T)$ is the number of times arm $i$ is pulled in $T$ rounds. Minimizing $R_T$ is the problem of exploring specialists that might be better while exploiting those that have already scored well.
This is exactly the stochastic multi-armed bandit. Thompson (1933) posed the two-arm Bernoulli case in a clinical-trial language; Auer, Cesa-Bianchi, and Fischer (2002) gave a finite-time analysis of the upper-confidence-bound policy UCB1 that we restate below. We are not proving a new bound. We are naming the correspondence so that a routing paper can cite a theorem rather than a slogan.
2. The UCB1 index
Initialize by pulling each arm once. Thereafter, at time $t$, UCB1 selects
where $\hat{\mu}_i(t-1)$ is the empirical mean of arm $i$ after $t-1$ rounds. The second term is an upper confidence radius. Arms that have been pulled rarely keep a large bonus; arms that have been pulled often are ranked near their empirical mean.
Theorem 1 (Auer, Cesa-Bianchi, and Fischer, 2002, Thm. 1). Let the payoffs of each arm be independent, $[0,1]$-valued, and identically distributed across pulls of that arm. Write $\Delta_i = \mu^* - \mu_i$ for a suboptimal arm. The expected regret of UCB1 satisfies
In particular $R_T = O(K\log T)$ when gaps are bounded away from zero, and a worst-case reading of the same analysis yields the familiar $O(\sqrt{KT\log T})$ envelope.
Proof sketch. The original argument uses a Hoeffding tail on the empirical mean. On the event that the confidence interval of every arm is valid, a suboptimal arm $i$ can be pulled only while its bonus still covers $\Delta_i$, which happens $O((\log t)/\Delta_i^2)$ times. Summing the tails over $t$ produces the $\pi^2/3$ additive term. We refer to the source paper for the complete counting argument and do not reproduce it.
3. What the theorem does and does not say about agents
The bound applies to a router that treats specialists as stationary arms and observes a bounded scalar payoff after every pull. Several hypotheses are routinely false for language-model agents.
1. Non-stationarity. A specialist that is itself a prompted model changes when its tools, weights, or system prompt change. The i.i.d. payoff assumption then fails. Discounted or sliding-window UCB variants exist; they are not the 2002 theorem.
2. Contextual tasks. Tasks $x_t$ are not exchangeable. A code-editing agent may dominate on repository patches and lose on literature review. The contextual bandit (payoff $\mu_i(x)$) is the honest model; UCB1 on pooled scores is a misspecification. LinUCB and related methods require a feature map we do not assume here.
3. Delayed and composite payoffs. An agent that writes a plan, calls three tools, and waits for a human review does not return $X_t$ before $t+1$. The analysis above is for immediate rewards.
4. Coupled arms. Two specialists that share a context window or a rate-limited API are not independent arms. Dependence does not automatically invalidate Hoeffding, but it can invalidate the interpretation of $\mu_i$ as a property of $i$ alone.
ReAct (Yao, Zhao, Yu, Du, Shafran, Narasimhan, and Cao, 2023) interleaves reasoning traces with tool actions inside a single agent. That is an intra-agent control loop, not a $K$-arm router. One may still wrap several ReAct specialists with an outer UCB dispatcher; the inner traces are then hidden inside the arm.
4. A finite numerical check
The following four-arm instance can be checked by hand. Let $\mu = (0.8, 0.6, 0.5, 0.3)$ and $T = 1000$. Theorem 1 supplies the explicit upper bound
Since $\log 1000 \approx 6.907$, the first sum is at most $8 \times 57.56 = 460.5$ and the additive term is at most $2.290 \times 1.0 = 2.29$, so $R_{1000} \le 463$. The bound is conservative — as the 2002 paper emphasizes — but it is a number, not a metaphor. A routing evaluation that reports only a mean win-rate against a fixed specialist has not yet engaged the allocation problem.
5. Evaluation discipline
A meta-algorithm paper that claims an improved router should report, at minimum: the arm set $\mathcal{A}$, the payoff definition, the horizon $T$, a non-adaptive baseline (round-robin or the empirically best single arm in hindsight), and a plot of $R_t$ rather than a single aggregate score. Confidence intervals on $\hat{\mu}_i$ belong in the appendix. If the tasks are contextual, say so and do not cite Theorem 1 as if it applied.
6. Limitations
We have restated a classical result and named its hypotheses. We have not proved a regret bound for transformer agents, for tool-using traces, or for human-in-the-loop payoffs. Thompson sampling is an important alternative policy; we do not analyze it here. Contextual and adversarial bandits are the right next citations when the i.i.d. model is refused by the data.
References
1. Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine Learning 47(2–3):235–256, 2002. Theorem 1. 2. Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3/4):285–294, 1933. 3. Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. ReAct: Synergizing reasoning and acting in language models. International Conference on Learning Representations, 2023.
This original editorial primer is an orientation, not a peer-reviewed research claim.