Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making

AI summary

Overview

Research area: Online learning and bandit theory applied to mixture-of-experts (MoE) aggregation, bridged with social choice / voting theory, with an application to aggregating large language models (LLMs).

Technical level: Advanced. The paper combines regret analysis, PAC-style concentration bounds, sub-Gaussian assumptions, and a mixed-integer program (MIP) formulation of optimal weighted voting. The motivating intuition is accessible, but the guarantees require comfort with bandit learning notation.

Scope: The paper proposes two online algorithms — Successive Expert Elimination (SEE) and θ-weighted majority voting (θ-WMV) — that learn how to aggregate a committee of experts (or LLM responses) in real time, with finite-time no-regret guarantees relative to the optimal aggregation parameters.

What This Paper Is About

Classical online mixture-of-experts algorithms such as EXP4 are guaranteed to converge to the best single expert in hindsight, which means they cannot exploit cases where a collective decision (e.g., majority voting) beats every individual expert — the "wisdom-of-the-crowd" effect. The authors ask whether one can instead design online learners that converge to the best collective decision-making committee rather than the best single expert, while learning experts' competencies and the aggregation strategy simultaneously. They answer this with two algorithms, theoretical regret bounds, and an application to online aggregation and fine-tuning of expert LLMs.

Key Contributions

1. Online expert aggregation methods. A family of algorithms that dynamically aggregate expert outputs in real time by combining majority voting with online learning, provably optimizing the collective aggregate competency of the expert set.
2. No-regret guarantees. Finite-time sublinear regret bounds for the proposed algorithms under ideal conditions, connecting online learning to social choice theory. SEE achieves regret in O(N log(T)/ε̃²); θ-WMV achieves regret in O(√(NT log(T))).
3. Structural results for committee formation. A Top-K ordinality lemma (the optimal committee is a subset of the Top-K experts by competency), a dominance lemma (optimal weighted majority voting is at least as accurate as egalitarian/plurality voting on the same committee), and an equality lemma for weight normalization.
4. LLM application. Empirical validation across realistic problem domains using online majority voting to aggregate responses from multiple LLMs serving as experts, where after each response the generative LLM dynamically reweighs its experts and/or selects the optimal committee to produce more accurate responses.

Main Findings

• The EXP4 limitation is the central gap. Algorithms such as EXP4 are guaranteed to converge to the best single expert in hindsight. This ensures asymptotic optimality relative to the best individual expert, but fails to capture gains from majority voting, plurality consensus, or any preference aggregation that outperforms every single expert.
• SEE regret bound. Theorem 1 states the total regret of the SEE algorithm is bounded by R_T ∈ O(N log(T)/ε̃²). The bound follows from PAC elimination sample complexity plus a union bound over O(N²) pairwise comparisons, with failure probability set to δ = 1/T; the dominant term arises from aggregating N−1 elimination rounds.
• θ-WMV regret bound. Theorem 2 states Algorithm 2 (θ-WMV, full bandit feedback) achieves R_T ∈ O(√(NT log(T))) under the stated assumption. A looser alternative bound under relaxed assumptions is also provided in the appendix.
• Breakage events drive elimination. Definition 3.2 defines a breakage event B_ij^t between experts i and j as p̂_j^t + UCB_j^t < p̂_i^t − UCB_i^t. The SEE algorithm keeps playing all experts until a breakage event occurs, then runs a removal test using the advantage function to truncate the candidate set.
• PAC sample complexity. Under Assumption 2.1 and sub-Gaussian competencies with mean p_i and variance σ_i² ≤ σ², using UCB_i^t := √(2σ_i² log(4/δ)/t), the breakage condition is met with probability at least 1−δ once t ≥ t_0 := 32σ² log(4/δ)/ε̃².
• Optimal committee is Top-K. Lemma 2.1 (Top-K Ordinality of Experts) shows the optimal expert committee E* ⊆ E is a subset of the Top-K experts based on their competencies, for 0 < K ≤ N. This avoids combinatorial search over all subsets under perfect information and permits a greedy construction.
• Weighted voting dominates plurality voting. Lemma 2.3 states that for any set of experts, the optimal majority weighted voting method always yields a stronger or equal predictive accuracy than the plurality vote of the same committee.
• Weights bind at equality. Lemma 2.2 shows that in solving for optimal θ, the constraint Q ≤ ||θ||₁ ≤ 2Q can be replaced with the equality ||θ||₁ = 2Q.
• Binary optimal weights follow the log-odds. For binary outcomes, θ*_i = log(p_i/(1−p_i)), a known result the paper cites and extends toward the multi-class online setting.
• Many weight configurations are equivalent. Proposition 2.1 shows that many different configurations of θ can lead to the same value of P_maj(E, θ), which the authors use to simplify the optimal weighted voting problem.
• Multi-class settings lack prior guarantees. Existing optimality guarantees for weighted majority voting require binary outcomes or large expert pools; the paper targets a modest, finite set of experts (approximately 20) where aggregate accuracy guarantees may or may not hold.
• LLM aggregation improves answer quality. The methods are applied to online aggregation of multiple LLMs as experts, yielding improved answer quality. The provided paper text is truncated before the experimental section, so specific accuracy numbers, dataset sizes, and benchmark names are not reported in the available content.

Methodology in Plain English

The setup is a repeated decision problem. At each timestep a context x is drawn from a distribution P(x). The context is passed to a set of experts (each producing a prediction, possibly in a different label space). A standardizer maps all expert prediction spaces into one shared output space, and an aggregation function parameterized by θ combines the experts' predictions into a single output. A scoring function then rates that output, and the learner only sees this aggregate score — not which individual expert was right. The goal is to choose θ so the expected score is as high as possible.

Two aggregation mechanisms are studied. The first is egalitarian majority voting, where every expert gets exactly one vote and the majority (or plurality, with uniform random tie-breaking) wins. The second is weighted majority voting, where each expert i carries a weight θ_i and a candidate wins if the total weight of its supporters exceeds a quota Q.

To form the optimal egalitarian committee under known competencies, the authors prove that the optimal committee is always a subset of the Top-K experts ranked by competency, then greedily add or remove experts using an "advantage function" that measures whether adding a subgroup improves the committee's expected accuracy.

For weighted voting, they formulate the exact optimal weights as a mixed-integer program (MIP) with binary "possibility" variables Z_S indicating whether a given voting configuration S passes the quota. Constraints enforce logical consistency (a configuration and its complement cannot both pass), the equality normalization on total weight, and distinct competency values. In the binary case the MIP's answer coincides with the classic log-odds weights.

For the online setting, the learner does not know the true competencies p_i and must estimate them from feedback. SEE uses upper confidence bounds: it keeps all experts active until a breakage event reveals that one expert is provably worse than another with high confidence, then removes the whole block of experts below the breakpoint, provided the advantage function confirms no loss. θ-WMV instead solves the MIP at each round using optimistic competency estimates (empirical estimate plus UCB), draws a full-bandit feedback sample, and repeats. A variant handles the case where compute limits the number of experts queried per round to at most m, by partitioning the N experts into N/m groups and running a windowed phase of t_0 rounds per group. Experiments use the catalogue-based standardizer, in which experts select from a fixed catalogue of items rather than projecting to a shared logit space.

Why This Matters

Impact on research. The paper reframes online mixture-of-experts from "converge to the best single expert" (Hannan consistency) to "converge to the best collective decision," importing tools from Condorcet-style jury theorems and social choice into bandit learning. It also contributes a rare set of finite-time regret bounds for multi-class weighted majority voting with a small expert pool, a regime where prior results required binary outcomes, asymptotic arguments, or large expert pools.

Real-world applications:

• LLM routing and ensembling. Aggregating responses from multiple LLMs as experts to improve answer quality, with weights updated after each answer.
• Online fine-tuning of generative models. Using the aggregation as a feedback loop so a generative LLM reweighs or reselects its committee per response.
• Committee and panel decisions. Corporate boards, academic review panels, and juries are the paper's canonical examples of egalitarian voting; weighted voting covers settings where members differ in expertise.
• Ensemble methods in machine learning. Random Forests, boosting, and deep ensembles share the same structural problem of optimally combining many weak learners.

Industry relevance. Compute-constrained deployments often cannot query every model for every request; the targeted-m variant directly addresses serving only m experts per timestep, which maps onto real routing and cost-control requirements in production model-serving systems.

Future Directions

• Tightened results beyond the idealized assumptions. Theorem 2 is stated under a specific assumption, and the paper notes a looser alternative bound under relaxed assumptions; closing the gap between ideal and realistic conditions remains open.
• Practical methods for multi-class optimal weighting. Binary optimal weights are known in closed form (log-odds), but multi-class settings with small expert pools still require solving the MIP or approximating it, which limits deployment at scale.
• Correlated experts. The paper assumes independent experts throughout but argues the guarantees remain valid under correlation because committees are assembled from marginal competencies alone; empirical characterization under correlated LLM errors would test this.
• Full empirical characterization of the LLM application. The provided text is truncated before the experimental results, so benchmark names, dataset sizes, expert counts, and accuracy improvements are not reported here and remain to be examined in the full paper.

Target Audience

Researchers and graduate students working on online learning, bandit algorithms, and mixture-of-experts architectures; practitioners building LLM routing, ensembling, or model-selection systems who need regret-style guarantees rather than heuristics; and researchers at the intersection of social choice theory and machine learning interested in when collective aggregation provably beats the best individual.

Authors’ abstract

We explore the use of expert-guided bandit learning, which we refer to as online mixture-of-experts (OMoE). In this setting, given a context, a candidate committee of experts must determine how to aggregate their outputs to achieve optimal results in terms of aggregate accuracy. We propose two algorithms to address this problem. The first algorithm combines aggregate voting with UCB-driven successive elimination, efficiently pruning suboptimal exploration actions. The second algorithm employs an online weighted-majority-voting mechanism, leveraging the respective voting power of each expert proportional to their predictive power. We derive theoretical guarantees for the regret properties in the bandit setting under ideal circumstances, and empirical results are provided accordingly. As a modern study on applications, these methods are applied to the online fine-tuning of a set of expert large language models (LLMs), where after each response, the generative LLM dynamically reweighs its set of experts and/or selects the optimal committee of experts to generate the most accurate response. Our results introduce new methodologies and no-regret guarantees for combining multiple experts to improve on the performance of the an aggregate model overall.