Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making
Authors: Larkin Liu
Jalal Etesami
Venue: NeurIPS 2025 poster ()
Keywords: Online Learning
Mixture of Experts
Primary area: general_machine_learning

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.

Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making
Larkin Liu" Technische Universität München Riebaki AI larkin. iiu@uumdde
Jalal Etesami
Technische Universität München j etesami @tum.
Abstract
We explore the use of expert-guided bandit learning, which we refer to as online mixturee-ff-xpertt (OMoE). In this setting, given context, a candidate commit- tee 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 succes- sive elimination, efficiently pruning suboptimal exploration actions. The second mechanism, leveraging the
algorithm employs an online nrigghedd-mjjority respective voting power of each expert proportional their predictive power. We derive theoretical guarantees for the regret properties in the bandit setting under ideal cireumstances, and empirical results are provided accordingly. As mod- ern 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 gen- erative LLM dynamically reweighs its set of experts and/or selects the optimal committee of experts to generate the most accurate response. Our results intro- duce new methodologies and no-regret guarantees for combining multiple experts improve on the performance of the an aggregate model overall.
Introduction
The mixture-of-experts (MoE) model is a powerful concept in applied machine learning and so- cial choice, leveraging the collective decision-making capabilities of group of experts yield improved predictions or more computationally efficient models. The core idea is that within a col- lection of N experts, E, there exists possible subgroup, m C E, whose combined predictions are well-optimized on some well-defined metric (e.g. collective accuracy, model efficiency etc.). Classically, MoE models involved the design of gating mechanism (a.k.a router) that aims to op- timally transform the output of many experts into single more optimal output. Traditionally, this involved training an offline model from labelled data optimize some loss function via supervised learning 2 3] Concerning neural architecture design for offline learning, the MoE framework has been wide integrated several sfate-of-the-arl LLMs (e.g. DeepSeek-MoE, Mixtral) for token prediction tasks
More recently, pertinent to applications on AI alignment, the online version of MoE has garnered significant interest. This is particularly useful when agents interact with an environment in a repeated manner, receiving feedback in an online fashion, and needing to optimize real-time.
[ [4 7 g
Online Mixture of Experts: Historically, online MoE was framed as prediction with expert ad- vice problem, which has been extensively studied in the learning literature (9
The core principle involves aggregating predictions from multiple experts, where each expert assigned weight proportional to its historical predictive performance. Previous online MoE learning algo- rithms, such EXP4, are theoretically guaranteed to converge to the best single expert in hindsight [13 [4 9] While this property ensures asymptotic optimality relative to the best individual ex- pert. it introduces concerning limitation. Specifically, such algorithms fail account for scenarios
I0
II 12
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

#anoo1 makin 570,000 yeur joet recetved 126 raico. maken axse sesunt as kanset but recatved zaice.
Prompt
Now ewch wove norey wi'll Drotel wake corpared to karocts
P(x)
Online Optimization
2S, DOO
.500
X
Majorit Voting Agpregator
Maj.
Scoring Function
20, oc0
0
(6=((x))
Algoritims
Reeponsse
Voding
Parameder
Figure 1: Online Mixture Experts via Majority Voting. At each timestep. context x sampled from distribution P(x). A prompt derived from x is used to query a set of expert candidates Eeand- The responses are aggregated via majority voting mechanism parameterized by 0, yielding a single output. All expert responses and the aggregated output evaluated by scoring function (c.g., oracle human). The voting parameters i updated online to maximize expected score, using full-bandit feedback over a finite time horizon.
where an aggregate outcome of the experts' predictions- such as a majority voting, plurality con- sensus, any form of preference aggregation- could yield superior performance compared to any single expert. In social choice, this phenomenon is often referred to as the wisdom-of-the-crowe there exists potential improvement from collective decision-making. traditional online MoE meth- ods, such as EXP4, would not capture this. This gap highlights key question, could we design an algorithm that provides convergence the best collective pociisionmmaking committee rather than to the best single expert? In our setting, we aim to learn both the competencies of the experts, and sufficiently optimal strategy to combine the experts aggregate outcome real-time online environ- ment. Evidently this also has important ramifications to generative LLMs, allowing for adaptively improved responses to tasks across various domains, when multiple LLMs are available.
If
Key Contributions: We make the following contributions in our work,
Online Expert Aggregation: We introduce a family of methods that dynamically aggregate expert outputs in real-time through combination of majority voting and online learning. This provably optimizes the collective aggregate competency of the expert set.
LLM Application: We empirically validate the effectiveness of our method across realistic problem domains via online majority voting mechanisms aggregate responses from multi- ple LLMs serving as experts, yielding improved answer quality.
No-Regret Guarantees: We provide theoretical guarantees with respect to the sublinear finite-time regret of the learning algorithm relative the optimal solution under perfect information, bridging online learning methods to social choice theory.
Problem Setting
To formally describe the problem setting, consider a learning model where the output is generated by combining the results of multiple weak learners through an aggregation function. These weak leamers, referred to as experts, produce individual outputs, and the aggregation function determines how these outputs are combined. Let E denote the set of expert with the size N. Provided context E X, expert i E & makes prediction cx(x) C, which represents an abstract categorical ordering or a singleton. Since (Ci) might be different sets (e.g..
(cat, dog, mouse) and Cj- (mouse, eagle, fly)), introduce standardizer G(-) that maps arbitrary collection of prediction spaces (ee to a unified output space C. Formally, the standardizer satisfies.
n C: :((C)((() C.., 339

---

We refer to the size of the standardized output as De:= := |6([C)
Aggregation function: It is Mg BeE C. C and characterized by a set of parameters Neee It takes as input the experts' predictions {ci( and produces new prediction č C.
The goodness of the aggregation function's 's output valued by the scoring func- tion, 6 C + R which assigns real-value score in IK to it's prediction. Suppose series of contexts, x, are randomly drawn from distribution This contextual information is passed into each expert. and the predictions are subsequently aggregated parametrically. As indicated in Eq. 2.I), the prediction itself may be context-dependent. The scoring function evaluates the accuracy or quality of the prediction. The performance of given aggregation function Mg is measured by the average scoring function,
Scoring function:
[ G Mo ((c(()))es) dP(x),
E
No] =
(2.1)
where ( o Mg denotes the composition of the scoring and aggregation functions. We aim is to max- imize the average scoring function, formulated as, 8* arg max Ex-P(6 o Ag]. The properties of the utility function, such as commutativity or monotonicity, can depend on the structure of the aggregation outcomes, Our goal is to design an algorithm that learns the optimal parameters for the aggregation algorithm in online setting.
The standard dimension represents unified responses across experts (e.g, a fixed set of answers for LLMs). We distinguish two approaches: (1) catalogue-basee the model produces catalogue of items where each expert selects from, and (2) model-based, where experts (e.g., transformers, MLPs) project arbitrary outputs to a standardized logit or token space RD. We applied the catalogue based standardizer for experiments.
Remark 1. Catalogue Standardizer:
The score of individual expert, expert's competency, can be obtained from the scoring function by computing the expectation over all possible contexts distributed according to P(x) as follows,
p: J (cx(x)) dP((x).
(2.2)
In more straightforward terms, the competeney of an expert refers to its individual ability to maxi- mize the cooring-aggregationn function over a singleton committee consisting of itself -.e. the ability of the expert to individually predict the correct answer among candidate solutions. In voting theory, this is an important piece of information measuring potential effectiveness of aggregating experts. The average scoring function is the expectation over the composition of the aggregation first 2(.). followed by the scoring function ((-), according to distribution P(x) over all contexts, Eq. (2.I) Which we denote as the corrig-aggreeaation function, or aggregation function for brevity.
Assumption 2.1. E-Incrementality (Heterogeneous Expert Competencies): Every expert has different Ps. offset by at least è increment, that inf (p: - Pp) 2 ē, Vi.j E 1...N.
The celebrated Condorcet's Jury Theorem states that with competent experts (p; > 0.5), majority voting accuracy approaches as N DC. List and Goodin [16] extends this plurality voting, showing asymptotic accuracy can hold even with p; < 0.5 under strict reliability assumptions, i.e. that the probability of any expert selecting the correct class is greater than selecting any incorrect class. However, when these assumptions fail, in- competent experts can degrade aggregate accuracy, highlighting the need for robust expert aggrega- tion in our setting. Our work applies epistemological social choice theory focusing on maximizing predictive accuracy with a modest, finite set of experts (~22),, where aggre- gate accuracy guarantees may or may not hold [16] 18 19) Unlike traditional social choice settings, we prioritize maximizing output accuracy (and accordingly minimizing regret) under imperfect in- formation. Key challenges include dynamically inferring heterogeneous expert competencies and aggregating unreliable multi-class predictions under sample efficiency constraints.
Extensions of Condorcet's Jury Theorem:
15
[17 T6 to MoE models,
2.1 Egalitarian Majority Voting
Consider a special setting in which experts' scored prediction are binary Im( = {0, 1}. where indicates that the expert is deemed correct and 0 if incorrect. Suppose that the cggre-aggregttion function is the majority voting with random bie-breaking In this setting, the composition of the
3

---

scoring and aggregation function is expressed in Eq. 22. In words, it is whenever majority of the experts give one and zero otherwise.
(
@ (((c(()))
[((e())))
+I
[((c(()) SEC
.Y,
(2.3)
FEE
where I(.) is the indicator function and Y Be(1/2) is Bernoulli random variable with parameter 1/2. Let 24 := fz [x)) } to be the set of contexts for which expert gives a correct prediction
and 2T its complement. Note that the measure of X, is pt- Using this definition, the average scoring function can be rewritten as follows,
B 2 P
U X (1115N12
+
N
X3
JE8
SES
|S|=N/2
Remark 2. This setting can be extended to non-binary prediction set, i.e., (1, K)
for some K and the output of the aggregation function i Imm whenever majority of experts vote for i. In the event of a tie among the experts, the aggregation function outputs one of the tied items uniformly at random. That is the Bernoulli variable in (..3) will be replaced with uniform random variable over the set of items that received the highest (tied) number of votes.
Independent Experts:
Suppose that the experts are independent, i.e., P(Nies X,) = -liess P(X;) for all S S E. In this case, the average scoring function will be,
Bi6 e 21
Σ (1- Σ SCE
I (1-Pp)) CS
(2.4)
SCE
ES
JESS
SES
18/>//2
|S|-N/2
Evaluating the above averaging function is combinatorially complex its complexity grows ponentially with the number of experts N. Combinatorial multi-armed bandit (CMAB) have been applied for this purpose in [20 21 22] Such methods assume the learning algorithm has access to an offline ag..)xapproiitttonn oracle oracle where, with probability B, it outputs a solution whose value is at least proportional of the maximum reward. Specifically, when the reward function is monotone and submodular, such an oracle can be given where a = 1 1/e. In our setting, the learner does not have access such (a:3)-oracle. For instance, adding experts existing com- mittee does not result in any generalizable behaviour in our majority voting setting. Throughout this paper, we assume that the experts are independent. However, as is discussed in Section 3 our proposed algorithms assemble their committees solcly using the marginal experts' competencies and subsequently, the theoretical guarantces remain valid even if the experts are correlated.
Optimal Egalitarian Committee (OEC): The optimal egalitarian committee (EC), also known as the binary weighted participation problem, refers the formation of committee in which each expert receives exactly one vote. Examples of such committees include corporate boards, academic panels, and juries. In machine learning, similar structures appear ensemble methods such as Ran- dom Forests, boosting algorithms, deep learning ensembles, and Mixture-of-Exper (MoE) models.
While online learning algorithms like EXP4 typically converge to the best expert in hindsight, prior work has shown that it is often possible to achieve better performance by identifying an optimal egalitarian committee- that is, a subset of experts whose aggregated votes outperform the best ex- pert. In this setting, the final prediction is determined by majority vote, and the resulting combined estimate exceed the accuracy of any individual expert. We denote this committee as E" E.
When considering the multi-class classification problem, for a majority vote to pass, more than some minimum amount, referred to quota, of the experts should have voted for the correct answer, each occurring with probability Pt. For majority voting, we set the quota to half of the number of experts (Optionally, the quota could also be reduced to allow for the experts to arrive at clear option as a winner from a choice of options
[17] ). We denote the average scoring function of candidate committee set Ecand C E by P Panj (Eeana) and is given by,
Pnaj (Eeand) =
Σ
II iES
((--)))+ (1-
Σ
II IES
II JE.0
(1-1).
(2.5)
SCE |S] 2 Ecant
jES
SC SCE
|||=

---

Accordingly, the optimal committee is Es E arg ma Paaj (Ecana).
Successive Expert Elimination Function: To form th OEC, intuitively successively include each expert sorted by their respective Pi, to a candidate expert set Ecand. given that such an inclusion
would improve the overall accuracy of the committee. For any subset E' Ecand- define the advantage function as follows,
3 (Ecand: E²) := F (Éeand UE' - Pnas (Écana), and na
(2.6)
Clearly, when the above function is negative, the addition of E' Eeand will not produce Ex, i.e..
3(Eaand E') 0 = E" + Ecand U
Lemma 2.1. Top-K Ordinality of Experts: The optimal expert committee E E is a subset of Top-K experts based on their competencies, for K S N. (Proof can found in Appendix A.
To build the OFC under the perfect information, i.e., experts' competen- cies are known, we propose constructive algorithm, where we with &eand = E, and succes- sively eliminate admissible subsets E", until there is no further possible improvement via the 3(-). Given the result of Lemma 2. starting with all experts, E, the of admissible experts must fall within the set of Top-K experts for some unknown 0 < K < N, i.e. E' S TopK(E). The benefit of Lemma 2.1 allows us to efficiently compute the OEC, avoiding combinatorial search over all possi- ble subsets. Under perfect information, this allows us to construct the OEC via a greedy algorithm. (See Al Algorithm in Appendix.)
Elimination of Experts:
2.2 Weighted Majority Voting
We extend from the egalitarian committee in Section 2.1 to a scenario where voters a committee have unequal voting power. Intuitively, more accurate experts should have stronger voting power to sway the accuracy of the majority voting system. In weighted majority voting (WMV) system, the voting mechanism is decision-making system where each expert has a specific level of influence, determined by an assigned weight. Previously (13] investigated the problem providing only an optimal error guarantee limited binary predictions, in the offline setting where voters can only produce one of two outputs {0, 1]. We aim to extend the setting to multiple class predictions with no-regret guarantees in the online setting.
We denote the weight of expert E by 0; E R. These weights often reflect factors such as expertise, historical performance, or stake in the outcome. Each expert votes for candidate class, and the total weight of votes for each candidate is calculated. The option with the weight that surpasses a quota
chosen the final decision. This approach extends simple majority voting by allowing experts to have unequal influence, making it useful in contexts like corporate governance, expert panels, and machine learning ensembles, where experts vary in reliability or expertise. Let us define IP Fuaj( .EE0 0) as the aggregate scoring function of a committee of voters with unequal weights denoted by 0 (0.)1EE-
Pnn (E,0): = Σ 0S,00
( p.)
II
where FN(5,0):=I Σ jES
0,
SC8
ÉES
JESc
(2.7)
(2.8)
where Ejer 0, = 0. In words the above selection function decides whether the configuration S of the committee E meets the feasibility requirements for the vote to pass. In the special case where all weights are one, then (2.7) reduces to (2.4) with an appropriate tie-breaking. The weighted majority voting problem with quota Q can be stated as,
max PER $20
Praj (E,
(2.9)
In our experiments, for simplicity, we used Q N/2, ensuring majority consensus. This guarantees a clear winner when the majority experts predict optimally. Should majority decision un- reachable, a random class is sampled uniformly as the winner. To help further simplify the solution Eq. (2.9). via Lemma 2.2 we can solve for at equality as opposed to constrained cap on Q. constituting more convenient expression encompassing the latter.
5

---

Lemma 2.2. Weights Satisfied at Equality: When solving for the optimal weights for 9-weighted
majority voting. the constraint Q < |01| S 2Q, from Eq. 2.9 can be replaced with ||0|| 2Q.
(Proof is available in Appendix A.5
2.2.1 Solving the Optimal Weighted Voting Committee
A key objective is optimizing the parameters, 8, to maximize majority voting accuracy in Eq. 2.7
While convex combinations of expert outputs with non-zero weights may yield higher optima, the problem involves iterative combinatorial complexity. For binary outcomes, i.e. only two classes to vote for, optimal weights follow the log-odds ratio: 0r log(ps/1 pt), v0, E [23 24 (see Appendix A.13 for a discussion and proof). For multi-class settings, the specifications of the problem challenges the aforementioned existing theoretical guarantees. Everaere, Konieczny, and Marquis (18) and Abramowitz, Lev, and Mattei (25) provide further insight, yet optimality guar- antees still require binary outcomes or large expert pools. Karge and Rudolph [19] provides non-asymptotic bounds via competency gap, but remains limited for small-scale online settings. Therefore, our problem requires novel approaches balancing accuracy maximization with sample efficiency and expert heterogeneity. First, we leverage potential simplifications in optimal weighted majority voting problem structure.
Discrete Image: Many configurations of 0 can lead to the same result for Feay(E,)) 0). (Proof is provided in Appendix A.3 A.3
Proposition 2.1.
The results of Prop. 2.1 rather intuitive, stating that many different configurations of weights could lead to the same expected accuracy via majority voting. One can prove this constructively more experts do not contribute So long as their weights do not contribute to swinging a majority vote for any possible outcome (i.e. this could be an infinitesimally small weight), it could be a valid optimal solution. Next, we provide an algorithm which for any given ordering over the competencies, denoted as Ord(p) == (P1, P2, .......PP................. PNN), such that p1 P2 2 PN.. computes an optimal set of weights.
by considering a scenario where
the optimal solution.
Mixed Integer Program Formulation: The exact formulation of the optimal weights in the vot- ing problem can be formulated as a mixed-integer program (MIP), governed by the properties out- lined in this section. Let 0 [0, B2........ 0x] be a positive vector, where 0 2 for all i. Let X2, .2,..., X2*] be a predefined vector where xs E {0, 1 and represents configuration S C &, ie.. [xsl, = if and only if expert j is voted correctly in configuration S. We also define Zs as binary variable corresponding to S, determined by the following if-else condition,
Zs = [1
if x5 0 Q>Q, otherwise,
where Q E R is the given quota. The problem in 2.9 can be formulated as an MIP with the following objective function,
Es P (1 IES
(2.10)
BERN
SCE
JES"
This MIP computes the expected value over all voting outcomes using binary selection variable and possibility variable Zg. When maximizing for the MIP objective, we must formulate a set of valid constraints. Leveraging Lemma 2.2 tighten the quota condition, introducing constraint E, 02
2Q. Assumption 2.1 enforces 0 F o, constraint. Importantly, enforce logical consistency by ensuring that complementary voting outcomes cannot simultaneously satisfy both an outcome and its complement (e.g. if scenario S = [0, 1, 1, is possible and Zs 1, then its complement S [L, O, O, 1] is not, implying Zs= 0.). These constraints collectively validate voting configurations, enforce expert competency distinctions, and eliminate contradictory outcomes, while maximizing for global solution. We provide the details for this MIP formulation in Appendix A.S.
Lemma 2.3. Majority Voting Dominance over Egalitarian Voting:
For any set of experis, the optimal majority weighted voling method will always yield a stronger or equal predictive accuracy than the plurality vote of the committee. (Proof can be found in Appendix
Lemma 2.3 posits that given the same committee of experts, utilizing the 0 (-WMV algorithm (Alg-
2). to aggregate experts' output will always yield a stronger result than using egalitarian voting.

---

Therefore, if the computational resources are available the 6- B-WMV algorithm will produce better accuracy. However, this depends on the systems ability to serve all experts and provide solution to the MIP expressed in Eq. (2.10). If the goal is to learn an efficient representation of experts (i.e.
sparse set of experts) then SEE (in Alg. T can be a better choice to retain efficiency.
3 Online Learning
In previous work, the online MoE problem was typically framed as no-regret problem relative to the best single expert in hindsight (Hannan consistency). Recent work on online MoE learning focuses on identifying top-K experts based on their competencies. A prominent gap remains in efficiently learning optimal aggregation with heterogeneous expert competencies without combina- torial explosion. Prior work assumes either pairwise feedback (duelling) or submodularity, yet there remains focal body of work addressing optimal MoE aggregation in an online learning setting. Key previous approaches include duelling bandits, where pairwise comparisons identify dominant experts [26] 27) and submodular bandits, which treat committee formation as a matroid optimiza-
tion problem with greedy guarantees 28 29 Alternatively, satisficing methods [30
trade optimality for efficiency, while Top-K bandits [33
34 35) leverage competency ordering
for successive acceptance and elimination of arms. Despite the ample amount of research in the online Top-K arm-selection area, a prominent research gap yet remains which bridges voting theory to online no-regret guarantees.
Notion of Regret: As our proposed algorithm is a no-regret learner, we formally introduce the notion of regret in Def. 3.1] Cumulative regret, Rr, is defined as the difference between the expected majority voting aggregate accuracy, Paay (E, ), under parameters, 0", subtracted by the expected aggregate accuracy under the current parameters Paaj(E; )²).
Definition 3.1. Regret: The cumulative regret of an online algorithm over time horizon of length T that selects sel of weights 0' round is given by Rr -Ein P (E, 0*) I sag((E, 0²).
3.1 Successive Expert Elimination (SEE)
The idea of successive elimination in online learning was demonstrated in Even-Dar et al. [33 where the successive elimination bandit algorithm with PAC bound on sample complexity was proposed, along with both a gap dependent and gap independent versions based on the UCB. Re- jwan and Mansour (35) presents a successive elimination algorithm in the full-bandii-feedbbcck setting (a minor detail is that only the sum of rewards is available, which is an additive result from the individual rewards). Yet, it does not consider the optimal Top-K expert selection (only that K is given). To distinguish, in our situation, the aggregate reward, Paaj function is not necessarily addi- tive, and the Top-K K is not given beforehand and must be determined. We first propose an algorithm based on the UCB, where there is some confidence range between our estimate of Pt and the true value for each expert pf. This confidence bound should shrink over time with increasing samples.
Bij
Figure 2: Illustration a breakage event Bay.
Definition 3.2. Breakage Event: A breakage event round denoted as BI between experts and j denotes an event where the upper confidence limit of the empirical estimation of j competency at round t, pr less than the lower confidence limit of pt, i.e.
Byy 1' + UCB, < of UCB/
Intuition of Successive Expert Elimination (SEE): The key idea of SEE is that we can use the confidence bounds to successively eliminate experts from candidate committee until we arrive at a final set of optimal candidates, with high confidence. The algorithm begins with the complete set of candidate committee equal to the set of all experts Eeard + E and all experts are played at each round until a breakage event occurs B At the event of a breakage, we first order the experts whose estimated competencies
lower than expert j. say j1; p5, < 1/ S... ... S DJ (pictured as blue points in Diagram 2 Then, we define To as the set [Lix), je ... (.)).....). To perform removal test, for each element E' in TE
j, such that
7

---

we consult the advantage function to see if B(E 8¹) S 0; that is no advantage can be obtained by including E" with high confidence. If all experts in E (Ji..., could be subsequently eliminated from &eand (i.e. removal of blue points from the previous union of blue and green w.r.t Diagram 2
Algorithm Successive Expert Elimination (SEE)
1: Ecand f E
Set the candidate expert the full of experts.
2: for t= to do
Estimate 1 and upper confidence bound, UCB for each expert in &eand- 4: if any B event is observed then
3:
> Breakage event occurs.
5:
for every Bij, in descending order do
6:
Eand f Eン cand
7:
cand if' 31E 8 S0, 3E E Topp then
b Perform removal test.
8:
Ecand + Ecand \ Ceand'
b Expert set truncation.
9: end
10: end for
11: end
12:
end for
13:
return Ecand
Lemma 3.1. PAC Sample Complexity: Suppose that the competency each expert is modeled as sub-Guat Gaussian random variable with mean ps and variance of S a². Under Assumption 2.1 for any two experts i and j. if the number of samples t and shrinkage term UCB, satisfy
UCB : 20? log(4/5)
t2 32o log(4/6)
2²
then, with probability at least 1 5, (0,1), the breakage condition, B will be met. (Proof provided in Appendix A.6) Theorem 1. Regret Bound for SEE: The total regret of SEE Algorithm in 7 bounded by:
Rr E O (N lo)(
(3.1)
Sketch of Proof: The bound follows PAC elimination sample complexity (Lemma 3.1 followed by a union bound over O(N2) pairwise comparisons. Next, we set the failure probability 1/T to control catastrophic regret. The dominant term arises from aggregating N elimination rounds, each contributing O (T) regret. (For complete proof see Appendix A.7
3.2 Online Weighted Majority Voting Solution (Full Bandit Feedback)
Full Bandit Feedback: As discussed in previous section, the optimal weighed majority voting problem (6-WMV) can be cast as an MIP under perfect information. Consequently, this can be integrated into UCB style bandit algorithms. To implement no-regret learning algorithm, we solve for the best- and worst-case outcomes under uncertainty in the experts' competencies via the MIP, and quantify the corresponding shrinkage in the bounded simple regret.
Algorithm 0- W-Weeghted Majority Voting with Full Bandit Feedback (0-WMV)
Require: Set of experts E with E (1,...,N) N).
Ecand <-
Set the candidate expert set the full set of experts.
2: for = 1 to do
3: Estimate ý and upper confidence bound, UCB, using the history for all experts in Eoand-
4: Solve for 0* with optimistic estimates, j + UCB,, via MIP.
5: Elicit all responses from &, and combine responses using weighted majority voting with 0*
6: Receive feedback from scoring function, and add the history.
7: end for
8: return 0

---

LSPE AA
250
2707
1500
200
2002
-209
2008
226
127
2005
1004
2..0
2156
208
4007
4000
6000
200
Brrottoriiiee leep
Benateerlee Sapp
(a) Optimal Egalitarian Voting.
(b) Optimal Weighted Voting.
(c) LLM Experts.
Figure 3: Comparison of Cumulative Regret for MoE Voting Environments. Fig. 3a
SEE simulated
Berouuli experts; Fig. [3b] 8-WMV on simulated Bemoulli experts; Fig. [c LLM experts across domains (c.g., GSM8k, BoolQ etc.), with tasks sampled from each domain. Shaded regions show UCB uncertainty. Evidently, SEE and 8-WMV consistently outperform baselines in regret minimization.
Algorithm
N
Er
p
Rr
%R
maj
Domain
SEE
20
0.992
0,010
546.2
0.921
0.980
Bernoulli
Comb. UCB
0.992
0.010
6932
0.370
Bemoulli
8-WMV
0.927
0.027
587.0
0.829
0.927
GSM8K
Zooming
9
0.927
0.027
3443
0.604
GSM8K
SEE
5
3
0,810
0.031
676.8
0.364
0,810
Commonsense
Comb. UCB
5
0,810
0.031
1065
0.664
CommonsenseQA
0-WMV
5
0.735
0.013
360,9
0.512
0.735
BoolQ
Zooming
0.735
0.013
740.3
0.694
BoolQ
Table I: Multi-armed bandit experiment results showing consistent performance across environments, with
time horizon T S 10 Performance metrics show reduced cumulative regret (Rz) and increased empirical accuracy (Pma) across baselines. Extended empirical results can found Appendix C.5
Theorem 2. Regret Bound for 9-WMV: Under the Assumption A.1 Algorithm 2 achieves a regret bound of Rr E O (VNTlogg) (T) (Proof in Appendix A.11
Sketch of Proof: We show that the MIP solution to Eq. (2. 10 under 0* misspecificatiin is bounded by the difference outcome scenario probabilities, which is also bounded by the uncertainty esti- mates of the expert's competencies, + UCB (see Lemma A. in Appendix). Subsequently, using standard PAC concentration bound arguments (i.e. Lemma 3.J). we derive the expected cumulative regret. A looser alternative bound under relaxed assumptions is also provided in Appendix A.16
Targeted-m Online Majority Expert Voting: In MoE applications, computational constraints often limit the number of experts that can be queried at each timestep to at most m. We address this extension to the problem by partitioning the experts into N/m groups and running a win- dowed phase of la rounds per group. This ensures high-probability breakage detection while pre- serving the original regret bounds, sealed by multiplicative N/m factor (Lemma 3.1 Specifically, the targeted-m variant of maintains O (N² log T T/mē²) regret, matching the original setting's guarantees with respect to T despite the query limitation.
Corollary 3.1. Targeted-m WMV: An algorithm exists that allows for the regret bounds of Theorems 7 Mand? to hold with an multiplicative factor of N N/m. (Proof can be found in Appendix A.12
4 Empirical Study
We evaluate online learning in both model-based and data-derived settings. the model-based set- ting. NN Bernoulli experts with fixed success probabilities test each algorithm's 's ability to distinguish and optimize for varying competencies under noise. In data-derived setting, we sample tasks
from diverse domains: GSM8K (36] (mathematical reasoning), Commonsense(A [37] (implicit knowledge), and BoolQ (38) (evidence-based binary inference), each presenting unique challenges. Experts are instantiated as LLMs with varying reasoning capabilities (see Appendix C.I

---

Propose-then-Vont Vote: Datasets used in our experiments, such as CommonsenseQQ [37 BoolQ [88 etc., constitute structured labelled data, that the catalogue of answers is provided to the LLM to choose from (note Remark T. But as we tackle unstructured open-ended tasks for experts, we need to standardize the vote aggregation functions with proper structure in order to elicit the appropriate expert feedback. One solution is to use the MoE to generate each individually their top responses to a prompt. By default, this is added to the admissible catalogue and the expert votes for their own response among the candidate responses. This, propose-then-vole mechanism essentially uses the committee to first determine the answer catalogue, and then vote on it. (For additional details and complete set of comprehensive experiments please refer to Appendix
Results Summary:
We analyze SEE (Algorithm D and 0-WMV (Algorithm 2 in terms of ex-
pected aggregate accuracy IP (E )²) (Eq. (2.7) and cumulative regret Rt (Def. 3.1 As base-
lines, we compare against combinatorial UCB bandits and the zooming algorithm [39 which serve
as no-regret benchmarks. Further details- - including prompting strategies ochain-oftthought, expert LLM specifications, baseline implementations, and ablation studies are provided in Appendix C
5
Conclusion
We introduce a new no-regret learning framework for online decision-making with voting-based expert ensembles, unifying online learning and social choice theory as a key contribution. Our al- gorithms- for egalitarian voting and 0-WMV for weighted majority voting-provice provable cumulative regret guarantees with UCB-style analysis, accompanied by definitive empirical per- formance. There are of course, also some limitations. First, although we consider up to a modest number of experts, the (-WMV algorithm depends on the solution to a mixed-integer program which could become overly complex when a large number of experts is introduced. Second, we did not consider the additional use of contextual and/or side information for the MoE framework to enhance regret minimization performance. Nevertheless, both learning algorithms offer practical advantages for ensemble MoE systems, particularly in LLM applications demonstrated. This work estab- lishes both theoretical foundations and practical tools for voting-based ensemble learning, opening new directions at the intersection of online learning and collective decision-making.
Acknowledgements
We would like to thank Nicholas Mattei, Ben Abramowitz and Ariel D. Procaccia, as well as the reviewers for their insightful feedback and suggestions for our work.
References
[1] Matthew Richardson and Pedro Domingos. "Learning with knowledge from multiple ex- perts". In: Proceedings of the 20th international conference on machine learning (ICML-03). 2003. pp. 624-631.
[2] Steven Nowlan and Geoffrey E Hinton. "Evaluation of adaptive mixtures of competing ex- perts". In: Advances in neural information processing systems 3 (1990).
[3] Chenglei Si al. "Getting MoRE out of Mixture of Language Model Reasoning Experts". In: Findings of the Association for Computational Linguisties: EMNLP 2023. Ed. by Houda Bouamor, Juan Pino, and Kalika Bali. Singapore: Association for Computational Linguis-
tics, Dec, 2023, pp. 8234-8249, DOL: 10. 18653/v1/2023. http:////22......n...eaaa cenddngg--enlp... 552 URL: https://aclanthollae
2223/2023.r0 windingsn-nnnn emllp. 552/
[4] Quentin Anthony et al. "Blackmamba: Mixture of experts for state-space models". In: arXiv
preprint arXiv:2402.0177/ (2024).
[5] Noam Shazeer al. "Outrageously large neural networks: The sparsely-gated mixture-of- experts layer". In: arXiv preprint arXiv:1701.0653 (2017).
[6] Damai Dai et al. "Deepseekmoe: Towards ultimate expert specialization in mixture-of-eexerts language models". In: arXiv preprint arXiv:2401.0666 (2024).
[7] Albert Q Jiang et al. "Mixtral of experts". In: arXiv preprint urXiv:2401.0400 (2024).
[8] William Fedus, Jeff Dean, and Barret Zoph. "A review of sparse expert models in deep learn-
ing". In: arXiv preprint 22Xiv:2209.0166 (2022).
10

---

[9] Nicolo Dessa-Binnchi and Gábor Lugosi. Prediction, learning, and games. Cambridge univer- sity press, 2006.
[10] Ze- Ze-Feng Gao et al. "Parameter-Effiiien Mixture-of -ixture-of-Experts Architecture for Pre-trained Lan- guage Models". In: Proceedings of the 29th International Conference Computational Lin- guistics. Gyeongju, Republic of Korea: International Committee on Computational Linguis-
org/ wtg/2022.col.ng-1.... 2888/ [11] Shaohan Huang et al. "Multi-Head Mixturre-o--Expert In: arXiv preprint 4555452404.1504
tics, 2022, pp. 3263-3273, URL: htttt:
(2024). URL: https: //axxvv...vv///. org/ atspaab////24/// 15045.
[12] Weilin Cai et al. "A Survey on Mixture of Experts". In: arXiv preprint arXiv:2407.0620
(2024). URL: hot::httss//aarer
httg/aba/2400 .62044
[13] Nick Littlestone and Manfred K Warmuth. "The weighted majority algorithm". In: Informa-
tion and computation 108.2 (1994), pp. 212-261.
[14] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. Marquis de Condorcet Marie Jean Antoine Nicolas de Caritat. Essai sur I' l'application de I' l'analyse à la probabilité des décisions rendues la pluralité des voix. French. Paris: De I'Imprimerie Royale, 1785.
[15]
[16] Christian List and Robert E. Goodin. "Epistemic Democracy: Generalizing the Condorcet Jury Theorem". In: Journal of Political Philosophy 9.3 (2001), pp. 277-306. DOI: 10. 1111/
1467-9760.00 00128
[17] Felix Brandt et al. Handbook of computational social choice. Cambridge University Press, 2016.
[18] Patricia Everaere, Sébastien Konieczny, and Pierre Marquis. "The epistemic view of belief merging:
track the truth?" In: ECA/ 2010. IOS Press, 2010, pp. 621-626.
[19] Jonas Karge and Sebastian Rudolph. "The More the -osst-Case-Mrrrier: A Generalized Con- dorcet Jury Theorem for Belief Fusion." " In: KR. 2022.
[20] Nadav Merlis and Shie Mannor. "Batch-size independent regret bounds for the combinatorial multi-armed bandit problem".. In: Conference on Learning Theory. PMLR. 2019, pp. 2465- 2489.
[21] Wei Chen, Yajun Wang, and Yang Yuan. "Combinatorial multi-armed bandit: General frame- work and applications". In: International conference on machine learning. PMLR. 2013, pp. 151-159.
[22] Qinshi Wang and Wei Chen. "Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications". In: Advances in Neural Information Processing Systems 30 (2017).
[23] Daniel Berend and Aryeh Kontorovich. "Consistency of weighted majority votes". In: Ad- vances in Neural Information Processing Systems 27 (2014).
[24] Shmuel Nitzan and Jacob Paroush. "Optimal decision rules in uncertain dichotomous choice situations". In: International Economic Review (1982), pp. 289-297.
[25] Ben Abramowitz, Omer Lev, and Nicholas Mattei. "Who Reviews The Reviewers? A Multi- Level Jury Problem". In: arXiv preprint 1xXiv:2211.0844 (2022).
[26] Yisong Yue et al. "The k-armed dueling bandits problem". In: Journal of Computer and Sys- tem Sciences 78.5 (2012), pp. 1538-1556.
[27] Miroslav Dudik et al. "Contextual ducling bandits". In: Conference on Learning Theory.
PMLR. 2015, pp. 563-587.
[28] Lin Chen, Andreas Krause, and Amin Karbasi. "Interactive submodular bandit". In: Advances in Neural Information Processing Systems 30 (2017).
[29] Elad Hazan and Satyen Kale. "Online Submodular Minimization." " In: Journal of Machine Learning Research 13.10 (2012).
[30] Rad Niazadeh al. "Online learning via offline greedy algorithms: Applications in market design and optimization".. In: Proceedings of the 22nd ACM Conference on Economics and Computation. 2021, pp. 737-738.
[31] Qing Feng, Tianyi Ma, and Ruihao Zhu. "Satisficing Regret Minimization in Bandits". In: The Thirteenth International Conference on Learning Representations.
[32] Daniel Russo and Benjamin Van Roy. "Satisficing in Time-Sensitive Bandit Learning". In: Mathmmtics of Operations Research 47.4 (2022), pp. 2839-2839. DOI: 10. 1287 moor.
2021. 1229
11

---

[33] Eyal Even- et al. "Action elimination and stopping conditions for the multi aamti bandit and reinforcement learning problems." " In: Journal of machine learning research 7.6 (2006).
[34] Séebastian Bubeck, Tengyao Wang, and Nitin Viswanathan. "Multiple identifications in multi-armed bandits". In: International Conference Machine Learning. PMLR. 2013,
pp. 258-265.
[35] Idan Rejwan and Yishay Mansour. "Top-k combinatorial bandits with full-bandit feedback".
In: Algorithmic Learning Theory. PMLR. 2020, pp. 752-776.
[36] Karl Cobbe et al. "Training Verifiers to Solve Math Word Problems". In: arXiv preprint
arXiv:21 10.11 111//..14100 14168 (2021).
[37] Alon Talmor et al. "CommonsenseQAA: A Question Answering Challenge Targeting Com- monsense Knowledge". In: Proceedings of the 2019 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). Minneapolis, Minnesota: Association for Computational Linguis- ties, June 2019, pp. 4149-4158.
DO1: 10. 18653/v1/N19- 1421 arXiv: 1811. 00937 [cs]
URL: httttpss//alclantollooyy/ org/ N19- 1421
[38] Christopher Clark et al. "BoolQ: Exploring the Surprising Difficulty of Natural Yes/No Ques- tions". In: NAACL. 2019.
[39] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. "Multi-armed bandits in metric spaces". In: Proceedings of the fortieth annual ACM symposium Theory of computing. 2008, pp. 681-690.
[40] Jason Wei et al. "Chain-of ofoin-oo--ie ofi---ffffftee thought prompting elicits reasoning in large language models". In: Advances neural information processing systems (2022). pp. 24824 24837.
12

---

Checklist
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The main claims of the paper are clearly presented in the abstract and intro- duction, with supporting theory and empirical evidence.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work are mentioned in the Conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are clearly stated in Section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Experimental results are clearly presented in the paper, with reproduction
data in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer:
[Yes]
Justification:
The methods and procedures reproduce the results clearly outlined in
Algorithm 1
Tand Moreover, implementation details are outlined in Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
onPolicy)
more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We provide full details in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
Uncertainty estimates are provided in all graphs presented in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g,, Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Experimental hardware specifications can found in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics h httprrrrppp..cpppaaaacccccccaaaa
Answer: [Yes]
Justification: Our research complics with all ethical guidelines, in no way do we have intent motivation to produce harmful or unethical output detrimental to humanity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the introduction of the paper we discuss several applications of the paper, including LLM alignment and achieving better understanding efficient agent learning.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There exists potential for high risk misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Code and methodology be openly used with proper credits given to thors.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, wwtppppppppahooooo cow com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
No digital assets were used in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing was used in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No study participants were used in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLM's were used as any important, original, or non-standard component of the core methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy httg:e/e//eurigg.cc///offreeeeee for what should or should not be described.
19

---

A Proofs for Core Theory
A.1 Proof for Lemma 2.1
Top-K Ordinality of Experts: The optimal expert committee & C a subset of Top-K experts based on their competencies, for 0 < K S N.
Proof. Suppose there is an expert in the optimal committee and another expert j with higher competency, i..., P; Pj who is not included in the optimal expert committee. In this case, replacing experts é and results a new committee with higher average score, leading to a contradiction. We prove it for when the size of the optimal committee is odd. Similar proof can be written for when
even. Let [1* = 2s + 1 for some s, E e but j & mx and p. < Pj- We form a new committee En E [i). Let (kkk) be the event that precisely experts in Ex correct including expert i. We also define S to be the event that i incorrect but k - other experts voted correctly in Er. Similarly,
that the probability of either (k) or (;(k) occurs in committee 8" is equal the probability of either (K)) or Sj occurs in & for all la E {s + .... 2s + 1]. This implies the sum of these events are the same for both committees in (.5 Note that when lo = + 1, both events S (k) and ()(k) will not appear in the average scoring 2.5) as both of these events experts are correct and s are incorrect. Moreover, the probability that event (y + 1) occurs is higher than the probability of the event (s 1) since in the former expert is correct and the latter expert and Pj > Pi-
define (k(k) and ()(k) in committee En. It is straightforward
A.2 Proof for Lemma 2.33
Majority Voting Dominance over Egalitarian Voting: For any set experts, the optimal majority weighted voting method will always yield stronger equal predictive accuracy then the plurality vote of the committee.
Proof. Suppose &x denotes the OEC where | = M. In this case, we define 0 such that 0 1 i E Ex and zero, otherwise. Next, we show that IP nan (E, (E,0) 2 (En)(E"), where the quota is Q rather than ~* 1/2 as in 2.5 Let S1 S E S2 = S n (E*),, then,
FnnJ (E,0) = Σ (S(,,
II iES
P: II (1 pp))
SC8
JESc
= Σ Σ
(Si US2
II P: II SES,
(1 (1-P)) pU)
II iE82
(1 Ps) jE(E*)e))8
II
SISE* So((Et)
jEE
Note that,
8 (8,0)
Σ9,> 1 1Sn Q
JES
This implies that the nonzero terms in the above summation are those with ||| > Q. Therefore, can simplify the summation as
Pmny (E, Σ Σ
II P: (eS1
II jEE
(1-p;)
II iE82
P:
II )
(1 (1-p,)
SIEE" Sc
S11=Q
= Σ
Il P: II
(1-P))
Σ S.C(E")
II P: II iES2
(1-p;)
SICF" 1
(ES
JEE
JE(E*)
20

---

Σ
II iES,
II (E8")S11
(1 (p-p))
=Paas(E*).
Pi
S.CE* |
A.3 Proof for Proposition 2.1
Discrete Image: Many configurations of f can lead to the same result for Paag (E, 0).
Proof. I Fuaj(E (E,0) is a function with finite number of discontinuities (jumps), which is bounded by 2N, the number of possible committees.
Let = [8,,... 8 be a set of weights and = {Si...., Sk} be all the set of configurations for which Ljes, 0z Q for all [K]. Let Si be the configuration which has the lowest sum of weights, i.c. S arg min; Ejes, 0z. Then, define lr be a new of weights in which some of the weights in S are disturbed by such that Ejes, 02 = Ejes, 05 and the remaining weights are left unchanged. After this distribution, some weights in S₁ are reduced by e, some increased, and some are left unchanged. Let So arg maxses Ejes Oz. Then, set e S min min(E (Ejes, JES, 0g Q,Q Ejes, O, Clearly, by this choice of all the configurations in S will pass the aggregation criterion and other configurations will be added to the S, that is PP mag (E, Fa (E,0")
n
A.4 Remark 3 Wedge Property
Remark 3. Wedge Property: Provided expert competencies, P1.P2 ......PP .N, with the ordering pi 2 P2 2 PN. there exists optimal solution with parameters 0* that maximizes IP Raay(E, 0) and are constrained by the ordering, 0, , 0x-
The intuition behind Remark 3 hinges on the idea that more competent voters would contribute more in terms of voting power in the expert committee compared to less competent experts. Voting power can be measured by various metrics such as the Shapley-Shubie Index or Banzhaf Power Index, which measures the amount of contribution that each voter contributes to swinging the collective decision. Having more weight, or allocated votes, to the expert reflects this property. Therefore expect monotone increasing wedge property the expert weight 0 proportional to the ordering on pt. Enabling this as a constraint for any optimization program will tighten the search space for optimal solutions, making it more computationally efficient.
A.5 Proof for Lemma 2.2
Weights Satisfied at Equality: When solving for the optimal for 0-weighted majority voting, we can replace the constraint Q < E'' 0,, from Eq. (2.8) with a binding equality Σ 0; = 2Q, obtain valid solution. (Proof is available in Appendix A.5
Proof. We can begin by considering 2Q, or two times the quota, as the total number of votes in an electorate. We would like to allocate the total number of allowable votes among the voters to ensure total representation, allocating any less could end up with suboptimalities. If the quota, Q too high in comparison to the total number of votes allotted, then it could be the case that some participants who would have contributed optimally to the voting committee, are unable to participate due to quota limitations. In order to ensure majority voting, more than half of the total votes must pass for any certain choice by definition. Therefore, between Q and 2Q, the objective IP (0) is strictly non-decreasing, as more useful voters could potentially be included in the voting pool without sacrificing exclusion of others. Since the objective function is strictly non non-decreasing w.r.t N
in put 0, then for any mixed-integer program, the constraint Q < Σ S 2Q can be replaced by binding constraint Σ 0, = =QQ.
21

---

A.6
Proof for Lemma 3.1
PAC Sample Complexity: For any two distributions for experts and j. if the number of samples t and shrinkage term (t,, satisfies,
UCB - 20 log(4/0) (4/6)
16(0) + log(4/6)
4J
then, with probability at least - 6, E (0, 1), the breakage condition, B, will be met.
Proof. Without loss of generality, let us consider = and j = 2. Let there exist two sub-Gaussian distributions parameterized with means P1: P2 and variances of o². respectively. Given (0,1), we seek the minimal number samples required to distinguish between the two distributions with probability at least - 8. Due to Hoeffding'ss inequality, with respect the number of samples t, the empirical means jf and pl must satisfy,
{UCC))) 20
P (1p) pal UCB!) < 2 exp
E (1,2).
Let us set the confidence bound shrinkage parameter UCB as,
UCB := 20 log(4/6)
E {1,2}.
The condition for breakage, By,, is indicated by non-overlapping confidence intervals, can be ex- pressed as,
b r e (4) + e2(()
Therefore, with probability at least 1 - 8, the intervals are separated when
A + o²) log(4/5)
A 2 2
2 (c)
t
Solving for 4,5 yields the sample complexity:
32a log log(4/8)
16(0; o))
4.
2
22
where Ai = Ip: - Pyl. ē min Ay and o; 2 a for all
A.7 Proof for Theorem
Regret Bound for SEE Algorithm: The SEE algorithm achieves a total regret Rr bounded by,
N Rr E log T)
During execution, there exist (2 possible pairwise com- parisons leading expert elimination, but the algorithm would encounter most --11 elimination events. For each climination round, we can expect the most samples to be drawn when Ai be- tween experts, i and is minimized, therefore, the maximum sample complexity breakage among all experts is upper-bounded by the sum over t4,411 from i goes from I to N - 1. Furthermore, we also impose conditions limit the sub-optimal inclusion experts under conser- vative advantage function estimates (Def. A.2), so long as the UCB is sufficiently sampled such that UCB Eaa (illustrated by Condition A. As consequence Lemma 3.1 will still hold by the same derivation, but we take the smaller of two gaps, where we define <min 4s,
Proof. Pairwise Comparison Regret:
(N)
achieve full
Enin == min(é, Ema)))
where minzy Aiy and fnaj can be computationally derived per Def. sample complexity result from Lemma 3.1 the regret decomposes as,
Leveraging the
22

---

16(0, + t log(4/6)
Rr S
6TA Failure Cost
(A.1)
Explention Cost
Here, we apply the fact that the optimality gap is upper bounded, Pan (E, S
In order to translate the sample complexity result from Lemma [31 into a regret bound, we must realize that we expect to play suboptimally with probability 1-8. 6. Next, å represents the probability where a catastrophic breakage even could happen (i.e. the algorithm eliminated expert from the committee, even though they were supposed be part of the optimal expert committee). If catas- trophic breakage were to occur, we could obtain a upper bounded worst-case regret of TÅ. where A (the maximum expert competency difference) so essentially a regret of T. Therefore, we select = 1/7 /T to offset this issue. By selecting = 1/",, the failure cost is effectively an up- per bounded by a constant (in this case 1), and the exploration cost scales logarithmically with the number of samples T. We can further express Eq. A.1 as,
RT
N-1
32a
log +1) 0
No
log(T))
min
ain
23

---

A.8 Mixed Integer Program Formulation for Optimal Weights
Problem Formulation: Let 0 [81, 02 v be continuous positive vector, where 0; 2 0 for all i = 1,2..... 2%
Let x [ 22, ................................ 22N| be a given fixed vector. Define z = [Z Zz,... Z2x]
as binary vector corresponding each scenario S, as determined by the following if-else condition,
{ Zs 10 otherwise.
x; 0 0> Q =
where Q IT is a given constant, and Zs is the indicator of the specific scenario. Then, the objective in (2.10) can be written as the dot product p. where p p....... P(s) s)s and ps, with slight abuse of notation, is defined by,
ps II P: iES
I1 (1
ps), SES,
JESt
where is the size of all scenarios of size 2
Mixed Integer Linear Program Formulation:
The problem can be formulated as mixed-
integer linear program (MIP) as follows:
II E
L
P: II (1-P,) pj)
(A.2)
OERN
SES
iES
JES
subject to:
N
Σ
2,0 Q 2 <MIPZs,
S S
(A.3)
1=1
Σ 0z Q S MZs. 1=1
AA E S
(A.4)
Σ 03 2Q,
(A.5)
0 0g E
Vj, E (1, < k
(A.6)
Zş Zg 1
AS E S, where AS E.
X,.
(A.7)
Zs (0, 1).
(A.8)
As standard notation for indicator variable Z,, define M as very large number, and exIP very small number, such that the indicator condition Eq. (.2) will hold as specified.
Description of Constraints This MIP is formulated with the objective variable as the dot product between a binary selection variable which dictates the possible voting outcomes, and possibility variable which dictates the possibility of this outcome among the constraints This produces valid sum over all possibilities and their individual expected values, over which the summation over indicates the expectation over the configuration provided set of weights 0.
Correct Vote Indicators: The two constraints,
A.3 and A.4 ensure that if
Σ 0.y0 Q 2; 0 otherwise.
Electorate Approval Condition:
A.3 and A.8 the variable 2; is binary and is determined by the condition E 0, 2
the two constraints
The constraint (A5)) ensures the total sum of 02 is fixed to 2Q. Lemma 2.2 provides constraint tightening which allows to solve address the quota inequality with more convenient constraint.
Equality at Quota:
24

---

Encrrmennalitty (Heterogeneous Expert Competencies) and 6-Wedge Property: (A.6) enforces the Assumption[2.1 and the B-Wedge property in Remark imposing minimum difference between all pairs of 0,, 0j.
Proper Outcome Complements: The constraint (A.7 ensures that complementary binary vectors X; and X3 cannot both have 2, = and 2 1. (c.g. a specific outcome where expert 1,3,4 votes correctly, cannot have any of 1,3, 4 also voting incorrectly)
A.9 Assumption on Summation of Competencies
Let us denote in shorthand, z(p) == arg max, z p such that z(p) is the value of z that maximizes the dot product of any given p. Let denote the optimistic estimate estimates and p represent the pessimistic estimates of scenario probabilities based on UCB uncertainty for expert competencies.
Assumption A.1. For scenario probabilities p and scenario indicator vector z inequality holds such that,
{00 (0,1)1s), the
Σ
P z =.P.. P.
(A.9)
where, and P, refer the maximum and minimum probabilities subject to UCB bounds over competency estimates, i.e. p; UCB, Vp; .I.....PN.
we assume that the variation in z(p) z(p) p is sufficiently small compared the fluctuation in the shrinking UCB. In the worst scenario, for each 2N scenario probabilities, we could add a deviation term of N x UCB for each scenario (although this is highly conservative estimate).
To provide additional discourse on Assumption A.1
The Bonferroni inequalities provide sequence of upper and lower bounds on the probability of the union of N events, refining the standard inclusion exclusion principle. These inequalities alternate between over- and under-estimates as more terms are included, ulti- mately converging to the exact probability when all N terms are considered.
Bonferroni Expansion:
inclusion-exclusion
For events A1, A2,..., AN, the exact probability of their union is given by:
P
(UA A
(-1)
where Sş represents the sum of the probabilities all k-wise intersections:
S
Σ
P(A; A 0 Aix).
156 Ci SRSN
General k-th Order Bonferroni Inequality: The Bonferroni inequalities state that truncating the inclusion-exclusion series at the k-th term yields an upper or lower bound depending on whether odd even. If k is odd, the partial is upper bound,
N PUAL
A
11
j=1
l: is even, the partial sum a lower bound,
N
P
U
A
2
(-15+ts
i=
j=1
Let (A1, Ag...., An)
N (P(A1), P(A2), P(As).... P(AN)).
independent
events with
success probabilities
25

---

A
P(Ai) P(42) P(As) P(AN) P(A) P(AinAs) A()2
1 n As) P Aa
Given expert competencies, we could express.
N
P
A 1=1
+
P3 PN PIP2
PIP3 P2P3
P1P2Pa
II
Pi
S1
S2
S3
we were to vary p; UCB, we would incorporate this modification into all the terms in Bonferroni expansion. Given the alternating = structure of the Bonferroni expansion, Ass. A.1 posits that the difference between, any two MIP solutions under p; versus 2, would entail a difference of,
z p 2 p
L.P.
Z.PIP2 2.PIP3 Z.PTP3 Z.PiP2Ps
Z
Pi
i=1
N
N
L.P: +Z,P,P2 + Z.P,P3 + ZoP.Pp -.....---PPP.. + Z.
1=1
i=1
Higher onder
Where p; = p; + UCB, and 22 p: UCB, and Z, the indicator variable for whether the specific scenario is possible, and equivalent in both the upper and lower bounding formulations. Ass. A.1 posits that the higher order terms of the Bonferroni expansion serve to cancel each other out, such that T oo, and UCB 0.
z p 2
Pr
(A.10)
This is in most cases where the values of the expert competencies are spread out over [0, and not highly concentrated around a single number, which is supported by Ass. 2.1 It also tends to be true as we have a modest size of experts, as our setting. possible to check, whether Ass. A. holds provided p, and p. as JCB-based estimates input into the MIP. Our empirical analysis has demonstrated that this assumption holds in all tested configurations of expert competencies.
A.10 Bound on Max-Min Probabilities for Weighted Majority Voting
Lemma A.1. Under the Assumption A. the regret of any learning algorithm (Def. 3.1 which provides bounds the individual agent competencies p; in majority voting setting be bounded by,
N
N
reg.
(A.11)
1=
Proof. Under full-bandit feedback, as we draw more samples the estimate of each individual expert's competencies improve, and the confidence bound shrinks, and with high confidence the estimate of each competency is bounded by, + UCB. Recall that the probability of each scenario S E S denoted by ps is given by,
II EES
(1 (1-p))) Pj), SCS,
JESo
where contains N elements. Let be the binary vector that maximizes T for given p. We further subject to constraint,
26

---

[8] Σ Zs -
S/ 2
vZs E
(A.12)
represents the restriction on Zs. such that then its complement Zs- = 0. Which, giving winning condition for tie-free weighted majority voting Σi= 8 > Q, and Q N/2, implies that the summation of Zs over all scenarios cannot be greater than half of all scenarios 0. because its scenario complement, S must be not be possible. This constraint is imposed because Zs {0, 13 represents the possibility the scenario the set all possible scenarios, and any possible scenario always excludes its complement, S therefore Zs= and the sum over is at most one half of (S]. Let p represent the probability vector of 2 possible scenarios in S. Therefore, the regret is expressed as,
The constraint in Eq (A.12)
reg: maxz z p' 2pp)
(A.13)
Establishing the Inequality: We establish the key inequality to bound our regret,
<p) p S zpp) S maxz p S <p)
(A.14)
We consider the Bonferroni inequalities, via first order Bonferroni inequality,
maxz P P
U
A4
Pe
(A.15)
i=1
Where A; defined probability of success of expert i, for N experts. The probability of the union of A,, that is at least one experts predicts correctly, is always greater than or equal to the probability that at least N/2 experts predict correctly (majority condition). Therefore, for any vector z adhering to constraints from Eq. (A.12). we can use the union bound over all expert competencies to upper bound the majority correct vote probability, leading upper bounds,
Pi
Z P
P
(A.16)
From the bound Eq. A.15 combined with constraints the sensitivity of the competency estimates as limited by Assumption A.I we can obtain bounds on the simple regret of the algorithm under uncertainty of expert competencies,
reg.
Pi
Σ i=1
(A.17)
A.11 Proof of Theorem 2
Regret Bound for 9-WMY Algorithm: An algorithm based on A-MIP weight assignment, such as in Algorithm achieves regret bound of Ro O (v NT log())
Proof. Provided the result from Lemma A.I we simply account for the uncertainty difference be- tween the two estimated sums for Ex=1 Pi and Σx=1 Pi. Let Sy. Σ Pi, denotes the true summed competencies, thus any deviation from Sy via estimating p; will give the PAC bound of ΣN (p: P.). Let express the uncertain quantity as UCB, where,
27

---

UCBy Σ pr So
PAC Bounds for Summation of Binomial Trials: The UCBy represents the radius that the timate Ei=1 P; should fall within with probability 1 6. Consider N independent binomial ex- periments, where the i-th experiment consists of n, trials with success probability p:- Let f4: denote the empirical probability of success, where k; is the number of successes observed in the i-th experiment. We are interested in deriving 1 PAC bound for the sum of the true probabilities
Sy Em
Hoeffding's Inequality for Unequal n,; Using Hoeffding's inequality, the deviation of the em- pirical sum Ex= P. from the true sum Sy can be bounded. Let {X1,) ) be independent Bernoulli random variables with parameter p: [0, 1]. for i ,....,...... ... That is, for each fixed i,
X Bernoulli(p:). i.d. for j 1, I,..., 744
and the samples are independent across different i. Our goal is to establish a concentration inequality for the sum of these empirical means, Sy, around its expectation, μ.. Where.
n2
N
N
P
X j=1
S
Pis
Σ
p
(A.18)
Th:
Each P; is average of n4 independent Bernoulli random variables bounded in [0, 1]. Hence, P. itself lies in the interval [0, 1). We can write,
N
N
Σ
P
X1..
Consider the collection of all M = Eim weighted sum of these variables, where each Xi, is multiplied by 1 1/n4-
i ny independent random variables {Xt,). The sum S is
Hoeffding-Tyye Concentration Bound: For any
0, it holds that (see Lemma A.4
2
P
Σ
Pe 26
exxp
N
Diml
To achieve 1 PAC bound, set the right-hand side and solve for
2e
In(2/8)
N
=
exxp
ΣE
N
2
(A.19)
Thus, with probability at least - 6:
ln(2/8) 2
Σ
Dr Sz
S
(A.20)
T4
The term E captures the variability introduced by the unequal number of trials n,, Experi- ments with smaller n, contribute more to the bound due to their higher uncertainty, while experi- ments with larger n, contribute less due their lower uncertainty.
Suppose the complete full bandit feedback, we always play every single arm,, therefore each time interval, would play each expert exactly N times, therefore n; = t, for all experts at round
28

---

t. We can then use an integral to bound summation as,
In (2/6)
In(2/5)
In(2/0
'.
1 / dil
S N
n4
To solve for the definite integral,
L
T
/-
T
di
111 dl
(A.21)
V8
1
12
T
2T -2(1) 2(1))1222277 =
(A.22)
Putting this back into the original inequality.
In(2/5)
(2/2/)) 2v N (VT -1)
(A.23)
2
74
2
Eq. (A.25) bounds the high probability estimation uncertainty of the algorithm, where at each time step the regret can be bounded in the high probability regime. Therefore, we can express the expected regret from as,
RT S 2NN (n(20) (VT-1) + TÂo
(A.24)
We can choose 5 = 7. allowing to vanish. Therefore, the expected regret is bounded by,
Rr E o (VNNToogg()
(A.25)
Worst-Cass Bound: is possible to check, whether Ass. A.T holds provided pt and p. and should this condition not hold, the algorithm will still retain its no-regret properties, however, it will incur a looser regret bound, illustrated in Appendix A.
A.12 Proof for Corollary 3.1
Targeted-m Setting: An algorithm exists that allows for the regret bounds Theorems [ and 2 Na met log T
to
hold with an additional multiplicative N/m factor (e.g., SEE's regret becomes O
Proof. The algorithms presented in the previous sections were developed under the assumption that all experts could be queried each round. However, this assumption may be restrictive certain applications where only m experts are available at any round. We refer to this setting as targeted-m, and in the following, we propose an extension of the previous algorithm to address this constraint
A simple modification of the previous algorithm can be applied to the targeted-m setting. Specifi- cally, we partition the N experts into (N/m) groups of size each. Then, run burn-in period during which all experts within each group are queried for tn rounds, where to is defined Lemma 3.1 This results in the total to (N/m) m) number of queries. The purpose of the burn-in period is to ensure that any breakage event, if it occurs, does so with high probability. Afterwards, we apply Algorithms I or 2 for assembling the OEC or finding the optimal weights in the weighted majority voting problem. respectively. Therefore, the regret bounds of Theorems remain valid with an additional factor of N N/m, e.g., the regret of SEE in the Targeted-m setting will be O( miz log T'). D
29

---

A.13 Binary Outcome Expert Weighting
Lemma A.2. Optimal Majority Voting Expert Weights for Binary Classification: From Nitzan and Paroush (24y, in weighted majority voting scenario, as described in Sec. [22] when the space of outcomes is binary (binary classification), the optimal weighting that maximizes the combined predictive accuracy for all experts combined is,
Ps
3. log
(A.26)
1-P Pt
Where Pj is the competency of expert (the probability that the expert predicts correctly.)
Proof. We begin with few key assumptions. First as stated, that the space of predictive outcomes binary, the expert predicts true, they receive a value of 1, and false a value of 0. Let y denote set of outcomes (i.e. y [1,0, 1, 1, O] indicates that experts 3, 5 selected the correct answer out of 5 experts). Due to the binary aspect of the outcomes, if an expert consistently predicts the incorrect outcome, we can always negate their prediction (predict the opposite) obtain equally consistently correct outcome. Further, let us define an aggregation function [w) + {0, J that takes any outcome and aggregates all individual outcomes form a single outcome in {0, 1}.
Suppose we impose an arbitrary pairing over outcomes. Let A(y) denote the selection over y where we impose the positive outcomes voters. Let Byy) denote its compliment. Thus for any outcome y = A(y) U Byy). This implies that if all outcomes are 1 in A(y) the outcome of (y) will result in overall positive outcome y 1, Vy A(v) = f(y) 1. The compliment, Byy) is by definition mutually exclusive from A(y) therefore it is not possible to include both in the selection voting criteria (either A(y) B(y) for any outcome y.) We also can see that there is a deterministic relations that maps any selection A(v) to its compliment Byy) (i.e.
Pairing with Compliments:
if A(v) [1, 0, 1, 1, 0] -
Byy) 00, 0, 0, 1J.) Therefore, the of all outcomes y is paired in such a way. Let us denote this as (v), Bg (v)) for each pair.
Maximizing [v](y)); In order to maximize the probability that f(y) 1, for each pair (y), B&(x)) (y)) we must determine a selection rule that selects the greater of P(As(v)) or P P(Ba(y)). For notation purposes, we impose that,
P(Ax(t)) 2 P(Ba(v)), Vk E K. =
(A.27)
Should a selection rule be found such that Eq. (A.27) holds, then the value [[]( is maximized. This simply holds because all outcomes are assigned to pairs, and events in each mutually exclu- sive (or condition), and events between pairs are not (and condition). We can express this probability as,
P(A(t) = II P: II
( p3)
2 II [1
P:)
II PS = P(B())) JEB
(A.28)
EAA
JEB
EEA
This forms a sufficient condition, long the selection rule fulfills Eq. (A.28)
Selection Rule: It just so happens that our selection rule f(y) selects fly) 1, then the weighted sum of outcomes in A(y) must exceed that of Byy) by definition. Thus,
Σ Bay N Σ 3,Flip(b))
(A.29)
YEA
JEB
Where Flip represents the bitwise operator (for example [1, 1, + |0,0, 1). This forms necessary condition for the selection rule to output f(y)
Log-Odds Weights: Given the sufficient and necessary conditions produce [Bf outlined in Eq. A.28) and Eq. (A.29). We can readjust Eq. (A.28) such that,
II EEA
Pi
Pj
(A.30)
(1
P:)
(1
pt)
JEB
30

---

Taking the logarithm, we obtain,
Σ
log
Pi
2
log
Pj
(A.31)
(1 P+)
(1 Pi)
EEA
jEB
The optimal weights therefore are equivalent
3: = log
Pi (1pp) P.)
(A.32)
Likewise for j as well, mutatis mutandis. To summarize, the sufficient and necessary conditions from Eq. (A.28) and Eq. (A.29) enforce single unique solution for the optimality condition of [[f(y) expressed in (A.32).
A.14 Relation Between the Optimal Binary Classification and Weighted Majority Voting
The setting of Nitzan and Paroush 24 considers first, arbitrary neutral decision rules, whereas restrict our analysis to specific class of majority voting systems operating over sub-committees. Consequently, the binary voting framework of Nitzan and Paroush (24) encompasses strictly larger set of decision rules, which allows the approach to achieve superior performance only in the binary classification setting.
For example, consider a simple setting in which there are only two experts with competencies {pi > P2 > (. According
Nitzan and Paroush [24] the optimal neutral decision rule is given by f x2) = sign(w) (1 + W222). where W/ = log(p: p;)) )) > and r; E {1, -11 11} is the expert i's decision. The success probability of this decision rule will be,
P (f 1) P (sign(w (w
+ w222) 1) P (z) 1, 1)+ P 1, 1)
= P1P2 + P1 (1 - P2) P1
This performance can be achieved using the WMV scheme by considering 0N and 02 0 and quota Q = 0.5 in 2.7 In this case, (2.7 will be
Pan (E, 0) = P1P2 + P1(1 - p2) = Pt.
Now, suppose {pi 0.5 > P2] such that wi /2// For example, Pi 0.6 and P2 0.1. In this case, /(11, x22 will always flip the decision of expert and ignore expert which leads to the success probability of 1 P22 0.9. But this performance cannot be achieved by the WMV. Because, the optimal committee is only expert 1, then the success probability is 0.6. If the optimal committee contains both of them, then the success is 0.6 0.1 0.6 0.9 + 0.4 0.1 0.64.
A.15 Non-Contradiction of Expert Inclusion
Definition A.1. Inclusion Signal: The inclusion signal of the advantage function 3(E1, E2) de- fined as
1 (((E,1))) >>)>) 0).
Given E and &g are disjoint subsets of 1 (3 &g) > 0) serves an indicator representing whether the advantage function is positive. This indicates if it is advantageous to retain the expert set Eg in &
the original & E U& or truncate
Definition A.2. Conservative Advantage Function: Given two mutually exclusive subsets E₁ C E and Eg C E, where ε & for optimistic and pessimistic estimates expert competencies of po. denoted as Pi and p, respectively, the conservative advantage function is defined as
8(),
31

---

such that,
& = (pi,...,PNh
= ( -.x
That is, & represents the egalitarian voting committee substituting the optimistic estimates of the ex- pert competencies Pi, and & represents the egalitarian voting committee substituting the pessimistic estimates of expert competencies. P.-
Remark 4. Guarantee on Consistent Exclusion: Given a bisection B12 that divides two an or- dering over set of experts, &, into two ordered sets, El and Eg, where ps > Pj for all E Ei and j E E2, it follows that,
3(E 50 B(E1,8)) 5.
We begin by asserting that any committee with dominant competencies for all experts (i.c. N experts, all experts have higher competencies in one committee than another) will result in Pma(()) & mmg (E), and it follows, (En E2) S ma (E,, (E,, When we are provided a condition E2) < 0 this implies P (en I (E)), by the definition from Eq. (2.6). Therefore, (ma((E,, < (E) S (ma)(E)) = Paay (Ei, E2) S (E)) = 3(E,, &2) s 0. We can conclude that, 8(E1, E2 < = 8(E1,E2) I O. Notice that during breakage Bıj, the bisection property 12 naturally divides & into two sets at the barrier between and (see Diagram 2), and we can be free to select & from within & without contradicting the bisection property (i.e. P: > Pj for E & and j E E2). Therefore, it holds that,
36) 0 = E2) 5.
In other words, if a conservative advantage function is applied, when this conservative advantage function, B Eg) signals to exclude & from & U E2, then with high probability 5, this exclusion of Eg from the optimal committee is valid.
Condition A.1. Consistent Inclusion: Provided an egalitarian voting committee with experts E, mutually exclusive subsets ε,, & are formed
and their respective competencies pı ... .Np where from the breakage event, Bij. such that p; > Pj. Vi E & V. E &2 (see Diagram 2}. and sufficient samples are drawn, such that 2UCB < Caaj. it follows that the inclusion signal (see Def. [A.1) of the conservative advantage function, 3(E E2), must be consistent with the inclusion signal computed under the true competencies, BEE,, 32), i.e.,
3 3 &2) > - E2) > 0.
Note that the expert elimination condition checks the condition 3(E, E2) for any candidate set, where p; > Pj, Vi &,, Vj E & with high probability. 1 1- 5. It is therefore not possible to falsely eliminate &a from ε with high confidence, as we are stipulating the lowest estimates of competence for & (group with higher competence) and highest estimates of competence for & (group with lower competence)-
advantage exists here, then we can confidently eliminate Eg from E. In the reverse situation without additional constraints, the inclusion signal under the conservative estimate of BEE,,E, Σ2) may be inconsistent with the inclusion signal under true competencies 3(E &2) (i.e. the signs of the two signals are different). Therefore, we next define Enaj as a property of the expert configuration such that consistency is achieved, per Condition A.I
Definition A.3. Connsiittt Gap: We denote consistency gap, Cnaj [0, 1). as the maximum value such that Condition A.7
For any configuration of experts, there must exist Gaj such that Condition A.I holds, as there are no constraints on how small Gaj can be. When we draw enough samples such that 2UCB < Gaaj, then we will obtain a consistent elimination function, when our confidence of expert competencies is less than the gap needed for always computing inclusion-consistent advantage functions with high confidence. Given the properties of the problem, i.e. expert competency arrangements {pr}. an exact computation can be performed to determine fmaj. and the value of émaz is independent of the number of the number of experts or number of samples T. Let (112) denote the set of bisections of & (i.e. division of the set of experts into two sets post breakage, where p. > Py for all E₁ and
32

---

j E Eg). The range of admissible Eaaj values can be expressed as,
((E) {UCB Sign (B(E,,
Sign (B(E1, E2)) V(Ei, E2) E {812]
(A.33)
We express 6naj
Euaj arg max UCBEg(E)
(A.34)
A.16 Alternative Bound for Theorem 2
We provide an alternative upper bound for Theorem 2 which upper bounds the regret of 9-WMV algorithm. As preliminaries, introduce the definition for S(O) and Lemma A.3 which stipulate that any two sets in S()) cannot be disjoint.
Definition A.4. For a given set of weights, we denote by S(0) the collection {Si, S of all configurations of experts such that ExEs, On Q for all and S & for all + j.
Lemma A.3. Any two sets in (()) have non-empty intersection.
Proof. Otherwise, we have least i and such that S; Sy =0. Then, EkESJUS, On > 2Q while due to constraint ||@|| s 2Q. This a contradiction.
Theorem 3. Regret Bound for O-WMV: An algorithm based on O-MIP weight assignment, such as in Algorithm achieves regret bound of Ri E eO 22(2 C /NTlog (NT)).
Proof. Let p be the empirical estimate ps after collecting i.idd samples, then due to Hoeffding's inequality, we have.
tea 20
tea
P (1 p.l 2 e) < 2 exx
< 2 2xxp
20
where a = max, Recall that at each round, we collect samples from all experts. Thus, after t rounds, we have collected precisely samples from each expert. Using Union bound, we have
le2
P (10 pal S c, Vi (1,..., N1) 2 2N exp
(A.35)
2o
Using the inclusion-exclusion principle, and the definition S(0) = (Si,..., Sk., we have
k
Pnag (E, 0)
Σ
II PS
Σ
II
P3 +
1== JES
1 JES, US..
When Ip. -p61- s c for all experts, i.e., i E [N), for any given 0 we obtain,
P Puaj (E, 0) Panj (E,0)
Pj
Σ
II
Pj +..
Σ
II
83 +..)
i 1= JES,
1 jES; US12
JESi
4 jES., USig
Σ p:)E.
JES.
U...U...US
where [a] denotes the ceiling real number a. As shown in Remark for a simple scenario, the first inequality is tight. The last inequality is due to Lemma A.3 which implies that the maximum repetitions of each P5 in the above double summation. Knowing that Ejes,u.uss. Pj $ N. leads to the bound )
size of ((0) is ( and consequently, we have at most
33

---

Applying the Stirling's approximation, we can achieve the following,
(E (E, Pnajj (E, (E,
< Ne 2 VNe..
2
Applying the concentration result in Eq.
A.355. D. we obtain,
(- le2
(-1e3
man (E, 0) - Panj (E, 0) S 2" VNo 2 P 1s - sslssiie 2 1 -2N exp
2o (-20²
Now, requiring the probability be at least 1 8, we obtain,
IP (Pas (E, - Paa (E, 0) S 60) 21-6.
(A.36)
where,
co(t) 2N 02
2N 8
log
Let consider two possible cases round I; (i) Pnay (E, 0*) (E, > 2ea(1) and (ii) Pan (E,0*) (E, 0*) I (t). Next, we show that case won't happen with high proba- bility. To this end, using the concentration in (A.36), we imply that the following events hold with probability least 1 25.
Pnag (E,07) Pnaj (E,07) s ct()),
Pna (E,0*) - P Pmnj' (E, 0²) S <n(().
Combining the above incqualities with the assumption case (i), i.., 2 (Ea)(E, (E, 8²) > 2co(t), implies Paaj (') < Paaj (E, 0*). This is a contradiction with /r E arg maxo Pasj (). Thus, with probability - 25, case (ii) occurs. By letting = 1/())), we could bound the regret as follows,
T
10
T (E - (Pnn)(E,
RT
(E, - -Ena)(E
Σ (=1
Σ
1=1
(=o+1
1 to + -T to) (1
1
(to(t)
T
I to 1 (1 T 18NNN log (4TN) 1" T Veate dt
1
(2 00 o V /TTlog (NT)
where 2N4 log N4T.). Note that during the initial phase, when & S to. we bound the instantaneous regrets by their worst scenario that is I as the utility function is probability.
Remark 5. Let consider N = 3 experts with competencies P1, Pr,P2,Ps and weights 0 = 1,, In this case, S(A)= {[1, 2), 3), (2.3)}. Moreover, let Ps = Pt + c forr all i, where c S min; P; then
- p1p3 + p2p3 - - 2(1 P1p223) IP (E, 0) P (E (E, 0) = pip - أ1 + -
= [pl + +22) (pi + pa)p + (p2 pa)e 362 -2(p1p2 + P1P3 + + - 2(pi + +2 + pa) - 26
12(p1 + P2 Ps (P1P2 + P123 + p2P3))
(2(p1 P2 p2) 3)²² 2.
34

---

The introduced bound (ابلT)) ( (Ejssussuus;?)) P.) Ps) c= 2(p1 + p2 + pa)e. Now, lets compare the exact value and the bound for when p = (.02, 03, In this case,
(
Σ
p5)= (e (),0) P (aa
0.18e |0.1748 2.82c -
2
JESILB,US
Note that the above expression can be arbitrary small as p.s tends to zero.
A.17 Scaling Variance of L/n; for Bernoulli Variables
Lemma AA. For estimates sums of Bernoulli variables X; {0, 1), where pe is the probability of success for variable X Ps is the empirical estimate, and n4 is the empirical count of successes, holds that,
2c Σ
PP
2
< 2exp
Proof. Scaling 1/n,; Since each X E [0, 1]. the range of each scaled variable X., is contained in {0, 1/ns). Each original Bernoulii random variable Xi takes values in {0, 1}, thus,
X E [0, 1].
When forming the empirical mean,
1 Xi.
j=1
each summand inside the sum is scaled by 1/n2, Therefore,
Xi
{o,
1 n2,
10.1/n].
74
This implies the range of each scaled variable is reduced from length to length 1/n, This scaling is allows us to applying Hoeffding's 's inequality, as the concentration bound depends on the sum of the squared lengths of these ranges,
1
- 0 =
n2
Hence, the variance proxy in the concentration bound is governed by Σ 1 n.
Applying Hoeffding's inequality for sums independent bounded variables, for any e 0:
2c²
P S[S2 11 2 c)
exp
N
ni
0
2
ni
Simplifying the denominator,
1
1
n1
74
i=1
i=
Hence,
2ca
IP
Pt
2exp
35

---

B Algorithms
B.1 Greedy Algorithm for Constructing Optimal Egalitarian Committee
Algorithm 3 Greedy Algorithm- Construct Optimal Committee with Accuracy Fnaj
Require: Set experts and Ecans
Ensure: Optimal Peaj and Suec
I: Sort all experts by their accuracy measure pi, resulting in sorted {p: H).
2: Ecand
3: for j 210 N do
4: if F(Ecams, E 2 O,
34A E Topk(E then
D Check the advantage function.
cand
5: Ecand + E..
1'a20 Peas (Econa)
end if
8: end for
9:
Eosc Ecand
10:
return Pnnj, Eosc
B.2 Zooming Algorithm
Algorithm Zooming Algorithm for Lipschitz Bandits
1: Input: Metric space (X, d). Lipschitz constant L > 0, time horizon '''
2: Initialization: Set active arms Active = 0
3: for é 1,2,..... de
4: Update Confidence Intervals:
x Active
6: Compute empirical mean reward:
(e(a) (x(x) n(( r2(2)
7:
Compute confidence radius:
2log T
r2(x) -1 (x(
8:
end for
Activate New Arms:
10:
for x E X Active do
11:
if Activ d(x, y) > re(y) then Add x to Active end end for
12:
13:
15:
Select Arm to Play:
arg max arAcctivee (ie(x) +r((w))
16:
Play Arm æxt
17:
Observe reward r, and update re (2x.)
18:
end for
The zooming algorithm from Kleinberg, Slivkins, and Upfal 339 strategies in a metric space by maintaining confidence intervals around the estimated rewards of active arms, serving as an appropriate benchmark bandit algorithm for when the reward function lacks convexity. It dynamically activates new arms that are sufficiently far from existing ones (based on their confidence radii) and prioritizes arms with high upper confidence bounds. In non-convex spaces, the algorithm leverages the Lipschitz condition to generalize observations across nearby arms, ensuring efficient exploration while adapting to the structure of the problem instance.
adaptively explores and exploits
36

---

C Experiment Details
C.1 LLM Offline Performance Benchmarking (i.e. Expert Competencies)
Model Performance vs.
Dataset
GSMBK
COA
BoolQ
Accurasy (N)
Model (Shape)
Aya
OpenOrca
Qwen
Mistral
Gemma
DeepseokRR
phi-4
Panams (B)
Figure 4: Visualization of performance comparison language models across three benchmarks (GSM8K,
CQA, BoolQ) as a function of parameter count (7B, 8B, 14B).
Model
GSMSK Acc. (%)
CQA Acc. (%)
BoolQ Acc. (%)
Params, (B)
Aya
7.71
9.20
43.00
OpenOrca
12.90
12.80
10.40
Samantha
15.69
18.50
11.30
Notus
25.53
22.90
3,91
7
Qwen
31.25
32,66
48.98
14
Mistral
43.88
43.20
65.31
Gemma
47.07
62,68
55.10
Deepseck-Ri -1
79.52
73.83
71.43
14
phi-4
92.69
78.90
71.63
14
Table Model performance ranking. Models listed by their accuracy across various domains offline setting, alongside their respective parameter count (billions).
C.2 Description of Datasets for Task Generation in Online Simulation
Dataset
Description
Testing Capabilities and Limitations
GSMBK
The collections questions are relatively basic and relevant to mathematics. The ex- pert is allowed to propose any answer they would like (in this case limited to integers). Open-source from benchmark dataset from Talmor et al. (37 containing 9.26k ques- tions with common sense yes/no questions.
Collection 8.5k middle school-level math problems from Cobbe et al. (36) solvable by elementary operations and logical reasoning.
CommonsenseQA
This dataset benchmarks the reasoning capa- bilities of LLMs, and provides catalogue of candidate answers choose from.
BoolQ
-answeing dataset from Clark 338 that focuses on logical reasoning and evaluation boolean expressions. It is part of the BIG- BIG-Bench Hard (BBH) suite.
This dataset examines the logical reasoning capabilities LLMs and provides cata- logue of possible answers true and false.
Table 3: Overview of selected evaluation datasets.
37

---

C.3 Computing Specifications
Component
Specification
CPU
Intel Core @ 3.60 GHz
Cores/Threade
16
GPU
NVIDIA GeForce RTX 2080
VRAM
&BB GDDR6
CUDA Version
11.8
System Memory
64 GB DDR4
Storage
NVMe SSD
Python Version
3.8.10
9.5.2 Table 4: Computing hardware and software library specifications.
Gurobi Optimizer
38

---

C.4 Chain-of-Thought Prompting with Constrained Output Formatting
Structured Chain-of-Thought Prompting: Our approach implements a constrained variant of chain-of-thought (CoT) prompting (40) with strict output formatting rules. We provide prompt
template for each of the domains.
C.4.1 GSM8K Prompt Template
### Instructions:
1. Read question carefully and identify what is being asked.
2. Solve the problem methodically, showing each step clearly.
3. Double-check your calculations before finalizing the answer.
4. Your final output MUST follow EXACTLY this format:
### Reasoning:
[Your step-by-step reasoning here]
### Final Answer: [Numerical Value]
### Required Output Format Rules:
Only numbers allowed in final answer (e.g., 42, 3.14, 2/3) uncertain, return ### Final Answer:
additional text after final answer Final anawer must be the last line
### Question: {question}
### Choices: {choices)
### Reasoning:
C.4.2 CommonsenseQA Prompt Template
### Instructions:
1. Read the question carefully and identify what is being asked.
2. Solve the problem methodically, showing each step clearly. Double-check your calculations before finalizing the answer.
4. Your final output MUST follow EXACTLY this format:
### Reasoning:
[Your step-by-step reasoning here]
### Final Answer: One of catagories [A, B, C, D, E]
### Required Output Format Rules:
(e.g., A, B, C, D, E) If you cannot determine the answer, you MUST pick a random answer from [A, B, c, D, E]. additional text, explanations, or characters after final answer. The final answer line must be the very last line of your response.
Only numbers allowed in the final
### Question: {question]
### Choices: {choices)
### Reasoning:
39

---

C.4.3 BoolQ Prompt Template
### Instructions:
1. Read the question carefully and identify what is being asked.
2. Solve the problem methodically, showing each step clearly.
3. Double-check your calculations before finalizing the answer.
4. Your final output MUST follow EXACTLY this format:
### Reasoning:
[Your step-by-step reasoning here]
### Final Answer: One of catagories [true, false]
### Required Output Format Rules:
Only numbers are allowed in the final anawer (e.g., true, false)
If you cannot determine the answer, you MUST pick a random answer from [true, false].
No additional text, explanations, or characters after the final answer.
The final answer line must be the very last line of your response.
### Question: {question}
### Reasoning:
C.4.4 Output Parsing Algorithm
The response parsing algorithm enforces strict numerical output constraints through regular expres- sion matching:
Algorithm Response Parser
procedure PARSERESPONSE(R:
pattern <- " Final (- [ (+)]), 2:
3: match t regex_ search/ pattern IGNORECASE)
4: if match. success then
5:
return grochh
6: else
7:
return "0"
8: end if
9:
end procedure
40

---

C,5
Extended Empirical Results
Algorithm
[3]]
Fimi
Rr
%R. +
P
Domain
Config. Id.
SEE
20
0.992
0.010
546.2
0.921
0.980
Beroulli
SE3
Comb. UCB
20
0.992
0.010
6932
0.370
Bernoulli
SC3
SEE
15
0,985
0.040
649.8
0.867
0.969
Bernuuli
SE3
Comb. UCB
0.985
0.040
4906
0.549
Bernuuli
SC2
SEE
0.883
0.010
535.3
0.719
0.871
Bernoulli
SEI
Comb. UCB
0.883
0,010
1905
0.759
Bernoulli
SCI
0-WMV
9
0.644
0.004
217.4
0.545
0.606
Beroulli
WV3
Zooming
0.644
0.004
478.4
0.449
Beroulli
WZ3
0-WMV
0.911
0.004
312.4
0.331
0.853
Bernoulli
WV2
Zooming
6
0.911
0.004
467.0
0.765
Bemoulli
W72
0-WMV
0.881
0.106
287.0
0.474
0.835
Bernuuli
WVI
Zooming
3
0.881
0.106
546
0.681
Bernuulii
WZ1
0-WMV
0.897
0.023
200.1
0.080
0.828
Bernoulli
WS4
SEE
0.897
0.023
216.0
0.806
Bemoulli
WE5
0-WMV
5
0.811
0.05
203.8
0.114
0.732
Bernuuli
WS5
SEE
5
0.811
0.05
230.1
0.707
Bernuuli
WE5
0-WMV
3
0.89
0.02
202.6
0.484
0.817
Bernoulli
WS6
SEE
3
0.68
0.05
392.7
0.427
Bernuuli
WE6
0-WMV
9
0.927
0.027
587.0
0.829
0.927
GSMSK
WG3
Zooming
9
0.927
0.027
3443
0.604
GSM8K
ZG3
MVWMV
6
0.927
0.132
420.6
0.353
0.918
GSM8K
WG2
Zooming
6
0.927
0.132
650.2
0.891
GSM8K
7G2
WVWMV
3
0.439
0.057
302.0
0.660
0.433
GSM8K
WG1
Zooming
0.439
0.057
886.0
0.369
GSM8K
ZG1
SEE
9
4
0.807
0.036
328.2
0.939
0.805
CommonsenseeA
CS3
Comb. UCB
9
4
0,807
0.036
5437
0.293
Commonsense
CC3
SEE
5
0,810
0.031
676.8
0.364
0.810
CommonsenseQQ
CS2
Comb. UCB
0.810
0.031
1065
0.664
CommonsenseQA
CC2
SEE
0.810
0.051
339.0
0.65
0.807
CommonsenseeA
CSL
Comb. UCB
0.810
0.051
970
0.763
Commonsense(A
CSI
B-WMV
9
0.763
0.0085
210.1
0.402
0.675
BoolQ
WB3
Zooming
9
0.763
0.0085
351.4
0.483
BoolQ
ZB3
0-WMV
0.735
0.013
360.9
0.512
0.735
BoolQ
WB2
Zooming
0.735
0.013
740.3
0.694
BoolQ
ZB2
0-WMV
4
0.735
0.04
183.1
0.225
0.667
BoolQ
WB1
Zooming
4
0.735
0.04
236.4
0.586
BoolQ
ZB1
Table 5: Multi-armed bandit experiment results showing consistent performance across environments, with time harizon T < 10 Performance metrics show reduced cumulative regret (Rr) and increased empirical accuracy (Pmn)) across baselines.
41

---

C.5.1 Empirical Results: Successive Expert Elimination with Bernoulli Experts
Cumulative Regret
Reward
2500
2000
0.6
Regret
1500
Reward
0.4
1000
STE
Comb. UCB
4000
2000
4000
6000
8000
10000
beration/Time Step
Iteration/Time Stop
Config. SEI & SCI
ps: [0.1, 0.65, 0.77, 0.79, 0.8].
Cumulative Regret
Reward
1.0
5000
Coutb UCB
4000
Regret
3000
Reward
0.4
2000
0.2
0.0
10000
Berstion/Time Step
Itoration/Time Stop
Config. SE2 SC2 ps: 12, 0.23, 0.31, 0.37, 0.42, 0.49, 0.55, 0.63, 0.68, 0.72, 0.76, 0.81, 0.87, 01488,0.99 0.92, 0.98).
Cumulative Regret
Reward
SEE
1.0
7000
Commb UCS
Regret
Reward
4000
3000
1000
2000
4050
6000
8000
10000
2000
4000
6000
8000
10200
Iteattiov/Time Step
Iteration/Time Step
Config. SE3 SC3 Ps: [0.01, 0.09, 0.12, 0.15, 0.19, 0.22, 0.26, 0.30, 0.33, 0.70, 0.73, 0.76, 0.78, 0.81, 0.84, 0.86, 0.89, 0.91].
Figure 5: Mean values calculated over 1,000 trials, with finite time horizon T = =10, 100,00, with shaded regions representing confidence intervals of -UCB.
42

---

C.5.2 Empirical Results: 8-Weighted Majority Voting with Bernoulli Experts
Cumulative Regret
Reward
600
Zooming
0.8
0.5
Regret
Reword
100
250
500
1000
1250
1500
1750
2000
250
500
750
1000
1250
1900
1750
2000
Iteration/Time Step
Iteration/Timm
Config. WV1 & WZI [0.332, 0.775, 0.881].
Cumulative Regret
Reward
WWV
WRVV Zowming
5.0
0.8
0.6
Regret
Reward
0.4
100
0.0
1500
750
Beration/Time Stop
Iteration/Time Stop
Config. WV2 & WZ2 pi: [0.388, 0.561, 0.782, 0. 799, 0.803, 0.841].
Cumulative Regret
Reward
600
WWV Zoom
WRVV Zooming
0.5
0.4
Regret
Reward
0.2
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
heration/Time Step
Iteration/Time Stop
Config. WV3 & WZ3 P:: [0.261, 0.370, 0.382, 0.499, 0.503, 0.511, 0.542, 0.616,
Figure 6: Mean values are calculated over 1,000 trials, with finite time horizon T = 2000, with shaded regions representing confidence intervals of +UCB.
43

---

C.5.3 Empirical Results: 8-WMW vs. SEE Voting with Bernoulli Experts
Cumulative Regret
Reward
0.8
250
200
0.6
Regret
Reward
150
0.4
200
400
800
1000
4.0
600
800
1900
BerationnTTim Step
Iteration/Time
Config. WS4 & WE4 [0.763, 0.786, 0.8492).
Cumulative Regret
Reward
WWV
WRY SEE
0.7
250
0.5
Regret
Reward
0.4
0.3
50
0.1
0.0
IteaaioonTiime Stop
Iteration/Time Stop
Config. WS5 & WE5
pi: [0.435, 0.501, 0.667, 0.114, 0.792).
Cumulative Regret
Reward
WWV SEz
WWV
0.8
SEE
Regret
300
Reward
0.0
200
400
600
850
1000
200
400
600
800
1000
heration/Time Step
Iteration/Time Stop
Config. WS6 & WE6 p:: (0.121,0.23)) 0.319, 0.374, 0.428, 0.198, 0.552, 0.637, 0.681].
Figure 7: Mcan values are calculated over 1,000 trials, with finite time horizon T = 1000, with shaded regions representing confidence intervals of -UCB. To note, for small batch of experts, the regret performances are near-identical the optimal committee consists of single best expert among few. The learning complexity not high, and both algorithms converge
optimal solution quickly. W.V demonstrates a clear advantage in regret minimization, aligning with our theory from Lemma [2.3 that the weighted majority voting committee will always yield superior solution compared to the egalitarian committee.
number of experts increases,
44

---

C.5,4 Empirical Results: 8-Weighted Majority Voting with GSM8K Tasks
Cumulative Regret
Reward
Zoomlnn
0.3-
Regret
Reward
600
0.2
400
WWW
Zooming
2000
4000
6000
8000
30000
Step
Config. WGI & ZGI LLM Expert Set: [notus, qwen-14b, mistral].
Cumulative Regret
Reward
0.5
2000
WWY Zooming
0.4
Regret
Reward
1000
0.1
0.0
Zoeming
10000
10000
Berstion/Time Step
Iteration/Time Stop
Config. WG2 & 7G2 LLM Expert Set: [samantha-nistral, notus, quen-14b, mistral, gemma-7b, deepseek-ri-14t
Cumulative Regret
Reward
SEE Comb. UCB
0.8
3000
2500
Regret
Reward
1500
0.4
1000
0.0
4000 Beratior/Time Step
8000
10000
4000
6000
8000
10000
Iteration/Time Step
Config. WG3 & ZG3 LIM Expert Set [aya, mistral-openorca, samantha-nistral, notue, qwen-14b, mistral, gemma-7b. beepseek-r-144, phi4].
Figure 8: Questions
sampled from the GSM8K dataset 36 Mean values caleulated 1,000
trials, with finite time horizon 10, 000, with shaded regions representing confidence intervals of +UC.
45

---

C.5.5
Empirical Results: Successive Expert Elimination Voting with Commonsense
Tasks
Cumulative Regret
Reward
1000
0.6-
Regret
Reward
0.2
200
SEE Crmb. UKh
2003
4000
8000
10000
2000
4000
10000
IerstionnTTime Step
Iteration/Time
Config. CSI & CCI LLM Expert Set: [gemma- -b, phi4, deepseek-r1-144
Cumulative Regret
Reward
SEE Comb. UCB
0.8
Regret
Reward
0.4
1000
0.0
2000
4000
3000
10000
4000
0000
8000
10000
Iteration/Timee Step
Iteration/Time Step
Config. CS2 CC2 LLM Expert Set: [mistral, quen-14b, gemma- 7b, phi4, deepseek-r1-14b1]
Cumulative Regret
6000
Comb. UCB
5000
0.6
4000
Regret
Reward
3000
2000
1000
Comb
2000
1000
6200
8000
10000
2000
6000
6000
8000
10200
horationyTime Step
Iteration/Timee Step
Config. CS3 & CC3 LLM Expert Set: [aya, mistral-openoree samantha-mistral notus, mistral, qwen-14b, gemma-7b, phi4, deepseek-r1-14b))
Figure 9; Questions were sampled from the CommonsenseQA dataset 1,000 trials, with finite time horizon T' = 10, 000, with shaded regions representing confidence intervals of +UCB
37
Mean values are calculated over
46

---

C.5.6 Empirical Results: Successive Expert Elimination Voting with BoolQ Tasks
Cumulative Regret
Reward
300
Zooming
250
200
Regret
Reword
200
400
800
1000
200
4.0
600
800
1900
Reration/TTmm Step
Iteration/Time
Config. WB1 & ZBI LLM Expert Set: [mistral, gemma-7b, deepseek-r1-14b, phi4].
Cumulative Regret
Reward
WWY
0.7
WRV Zoeming
Regret
300
Reward
0.3
0.2
0.1
Beration/Time Stop
Iteration/Time Stop
Config. WB2 & ZB2 LLM Expert Set: [qwen-14b, mistral, gemma-7b, deopseek-r1-14b, phi4].
Cumulative Regret
Reward
WWV Zocom
WWV
0.7
Zooming
0.6
0.5
Regret
Reward
0.4
200
0.3
0.1
0.0
200
400
600
850
1000
200
400
600
800
1000
heration/Time Step
Iteration/Time Stop
Config. WB3 & 7B3 LLM Expert Set: [eamanth--mistral] quen-14b, mistral-openorca, notus, aya, mistral, gemma-7b, 7b, deepseek-r1-14b, phi4].
Figure 10: Questions were sampled from the BoolQ dataset 38
Mean values are calculated over 1,000 trials, with finite time horizon 000, with shaded regions representing confidence intervals of LUCB.
47


Reviews:
[{"review_id": "H2fkOhPOxz", "reviewer": "Reviewer_nmuN", "summary": "The paper is concerned with merging output of experts, which are typically LLMs, in the on-line mode. If I understood the setup correctly, the predictions are rankings on finite sets and we want to compete against optimal weighted committees of the experts. The paper proposes two algorithms, one working through expert elimination and assigning weights to experts. Regret bounds are proven for the algorithms. The papers refers to them as 'no-regret', which, I presume, stands to mean $o(T)$ regret. There is empirical evaluation using LLMs.", "questions": "Are we still talking about rankings or 0-1 predictions in Section 3? If it is about ranking, is the number of categories fixed or bounded? Do we count only one top vote from an expert, or do other choices matter?\n\nMy ultimate goal is to understand how the result of the paper compares with well-known Weighted Majority of Littlestone and Warmuth, 1994.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "This is an interesting and practical results.\n\nIt may be just me, but I found the organisation of the paper rather confusing. Section 2 is quite detailed, but as far as was able to ascertain, it deals with batch setup and was included mainly for motivation. The original contribution of the paper is in Section 3, and it is rather terse. I would like to clarify a few points and see a clearer comparison with the extensive machinery of prediction with expert advice.", "was_revised": true, "final_justification": "Upon reading the discussion, I am inclined to keep my assessment of the paper.\n\nThe authors' use of terminology seems awkward and causes some confusion (prediction with expert advice vs voting) but the result seems interesting.", "rebuttal": "We thank the reviewer deeply for the time and effort taken to review our paper, and your overall positive appraisal.\n\nTo clarify the questions, we build on the work of (Littlestone and Warmuth [13]) by proving finite-time regret bounds, whereas (Littlestone and Warmuth [13]) provide only an error guarantee. In this work, we do not consider the rank over experts’ predictions but rather their top prediction. Our work provides a finite-time regret guarantee. The successive elimination algorithm we employ is based on established successive elimination bandit algorithms from (Even-Dar et al. [30]) and (Rejwan and Mansour [32]).\n\nFurthermore, the guarantee from (Littlestone and Warmuth [13]) is **limited to binary predictions**, where voters can only produce one of two outputs ({0,1}). Similar work can also be found in (Ntizan and Paroush [21]). We expand on these ideas by **providing no-regret guarantees for an optimal committee of experts** that covers the space of multi-class (i.e., N) prediction outputs, not just binary outputs. We provide two solution strategies for this method: one based on successive elimination, in Section 3.1, which can be employed to target model efficiency by limiting the group of selected experts and another based on optimal weighted voting, in Section 3.2, which extracts the optimal majority voting weights (parameters) under imperfect information.\n\n---\nWe hope this clarifies your questions and thank you once again for the thoughtful feedback. We would be glad to provide further clarification if needed. If our response helps to address any remaining concerns, we would appreciate a adjustment of the overall assessment."}, {"review_id": "YLt2DvUuEo", "reviewer": "Reviewer_HeLJ", "summary": "This paper proposes an online learning framework for expert aggregation via majority or weighted voting, aiming to outperform single expert through collective decision-making. It introduces two algorithms, Successive Expert Elimination (SEE) and $\\theta$-Weighted Majority Voting ($\\theta$-WMV), with theoretical regret guarantees. Experiments on synthetic data and multi-LLM tasks demonstrate improved performance over baselines.", "questions": "1) In Section 2 (line 66), the scoring function is defined independently of the context $x$. Does it imply the optimal aggregated output is the same across all queries? This is counterintuitive in settings like LLMs, where the optimal outputs should be context-dependent.\n\n2) How is the scoring function defined in practice, particularly for open-ended tasks?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1) The paper introduces a new perspective on expert selection via voting-based aggregation, moving beyond traditional online single expert selection.\n2) The proposed algorithms are accompanied by formal regret analyses.\n\nWeaknesses\n1) The problem studied is not aligned with standard Mixture-of-Experts (MoE) models used in modern LLMs (e.g., DeepSeek-MoE, Mixtral). The paper’s claim that MoE selects only a single expert is inaccurate. This mismatch could mislead readers and should be explicitly clarified.\n2) The citations for \"online MoE\" primarily cover general bandit algorithms (e.g., EXP4), without discussing more directly relevant work such as combinatorial bandits, Top-K selection, or their applications to expert or LLM ensemble selection, which makes it difficult to assess the significance.\n3) While theoretically sound, both proposed algorithms adapt standard techniques like UCB-based elimination without introducing fundamentally new algorithmic ideas.\n4) The experiments are restricted to synthetic Bernoulli simulations and simple multi-LLM voting tasks. The rationale for including baselines like Zooming and “Comb. UCB” (not properly referenced) is unclear. The empirical section does not thoroughly analyze why the proposed methods outperform these baselines.", "was_revised": true, "final_justification": "After multiple rounds of discussion during the rebuttal phase, I remain conservative on this submission. As noted previously, my main concerns are: (1) the lack of references on online MoE or online ensemble learning, (2) the need for a more careful comparison with CMAB methods, and (3) the more critical issue of the context-aware scoring function.\n\nFor the first two points, I believe the authors should strengthen the literature review and provide a more thorough comparison with existing work. Regarding the third point, after several rounds of questions and clarifications, the authors eventually acknowledged that their original scoring function definition is not suitable for the LLM setting. While I accept that the theoretical guarantees may not be significantly affected, the scoring function is a foundational component of their method. Given its central role, a careful re-examination is necessary.", "rebuttal": "1. To clarify, we do not claim that the current implementations of MoE are limited to selecting only a single expert, with reference to [4, 5, 6, 7, 8]. For example the work in (Shazeer et al 2017 [5]) selects the optimal 2 experts. We simply state that the MoE architecture is generally used in LLM inference, and that traditionally these models are learned offline via supervised learning (lines 24-26). Furthermore, the vast majority of these problem settings (whether its online, or offline learning), are not accompanied by theoretical guarantees.\n\n- However, in the context of online learning the vast expanse of scientific literature, via algorithms, such as EXP4 [13, 14, 9], are theoretically guaranteed to converge only to the best single expert, such methods are bound to the performance of the best expert. In this work, based on the classical result on social choice models and voting theory, we consider a majority or weighted voting in a sub-committee of experts which can result in even a better performance than the best expert. \n\n2. We assert that a significant variety of bandit algorithms was mentioned in our paper. In lines 221-233, we provide an ample literature review on Top-K combinatorial bandits, as well as other methods to address our problem (eg. submodular bandits, satisficing bandits, duelling bandits etc.) . Further, in lines 179 -182, we discuss the combinatorial complexity of solving our online problem. In fact, the SEE method we propose uses strategies devised from Top-K combinatorial bandits. We would like to understand what exactly the reviewer means when by “difficulty asses the significance” and also specifically where the LLM ensemble selection is unclear per se. \n\n3. A natural approach to decision-making problems is to frame them as variants of the multi-armed bandit framework. By adapting established algorithms—such as UCB or Thompson Sampling—one can then derive tailored solutions for specialized settings (e.g. causal bandits, or top-k ranking). Consequently, the key innovation in such work—mirroring our own—resides not only in the problem formulation but also in the detailed analysis of the adapted bandit algorithm.\n\n- To reiterate, our online algorithms (Alg 1 and Alg 2) converge to the best optimal subset of experts, unlike prior work which only guarantees convergence to the best single or top-K experts [9, 10, 11, 12, 13,14]. Our no-regret guarantees required a nontrivial and carefully constructed analysis (see Appendix A.7, A.10), as optimizing for the best voting committee—under both egalitarian and weighted settings—poses inherent complexities that go deep beyond conventional UCB analysis.\n\n4. We provide discussion on Top-K combinatorial bandits earlier lines 171-183. To be more clear, Combinatorial UCB runs regular UCB, but with a combinatorial selection of arms rather than each arm independently. This is a principled no-regret learning algorithm, but suffers from combinatorial explosion of arms. Our successive elimination algorithm does not exhibit this characteristic - and therefore would exhibit improved regret minimization advantage.\n\n- The zooming algorithm (Kleinberg et. al. 2008 [36]) is used for no-regret learning in repeated games for general continuous multi-dimension Lipschitz action spaces. The zooming algorithm is a general solution to the Lipschitz bandit problem in continuous action space setting, with a general non-convex reward function. Notably, the zooming algorithm is one of the few scarce algorithms where no-regret guarantees exist. Our algorithm leverages additional information from the online majority voting problem setting - because of this we expect it to perform better than the zooming algorithm, when used as a baseline.\n\n### Addressing the specific questions:\n\n1. **Contextual information** is passed into each expert (predictor) and the predictions are aggregated parametrically - given the structured approach via majority voting. It is important to note that the scoring function evaluates the accuracy or quality of the prediction. As indicated in Eq. 2.1, the prediction itself may be context-dependent. In the current implementation, contextual information is used to learn the optimal parameters for expert aggregation. As discussed in lines 298-303, we draw tasks (contexts) from a diverse set of task domains (e.g. GSM8K, CommonsenseQA, BoolQ etc.) - we provide more detailed descriptions in the Appendix C. This is a probability distribution, where certain types of contexts are emitted from. Our goal is to design an algorithm that learns the optimal parameters for the aggregation algorithm.\n\n- Not having the context be directly visible to the expert aggregation algorithm presents some advantages in the context of privacy in machine learning. In the LLM setting, the current algorithm(s) do not need to observe the input of the prompts, and in principle, can receive an one-way encrypted message from each expert. Therefore our methods provide meaningful applications when context (prompt) privacy is of a concern.\n\n- We do acknowledge that a per-context MoE predictor could align more with the standard LLM based literature. Possibly, this is interesting for future work, but deserves a separate treatment using other learning algorithms. Our paper could provide insights for researchers who wish to pursue this direction of research.\n\n2. **The scoring function** used is the label of the extracted task (which could also be one-way encrypted). As discussed in lines 298–303, each database—GSM8K [33] (mathematical reasoning), CommonsenseQA [34] (implicit knowledge), and BoolQ [35]—contains labeled answers for each task (math, commonsense reasoning, etc.). We use the labels for each task in the dataset to provide a score for the LLM’s responses. More detailed descriptions of the prompting strategy, baseline LLM performances, and descriptions of each dataset are provided in Appendices C.1–C.4.\n\n---\nWe are grateful to the reviewer for their thoughtful comments and for recognizing the contributions of our work. If further clarification would be helpful, we are happy to provide it. We would appreciate it if our response leads to a more favorable reassessment."}, {"review_id": "jsdk7woSXw", "reviewer": "Reviewer_BNid", "summary": "This paper proposes a novel framework called Online Mixture of Experts (OMoE) for aggregating multiple expert predictions in real time to achieve superior collective decision-making, as opposed to selecting a single best expert. The authors introduce two main algorithms: (1) Successive Expert Elimination (SEE) for egalitarian voting, and (2) $\\theta$-Weighted Majority Voting ($\\theta$-WMV) for scenarios where experts should be weighted by predictive quality. The key contribution lies in combining techniques from online learning and social choice theory to provide provable no-regret guarantees. The framework is motivated by applications such as online aggregation of large language models (LLMs), where leveraging the \"wisdom of the crowd\" may outperform any single model.", "questions": "Please comment on or discuss the above weakness parts.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- **Original Problem Formulation:**\n    \n    The paper targets a gap in standard online learning frameworks like EXP4, which are designed to identify the single best expert. In contrast, OMoE explicitly models **group decision quality** and allows the learner to benefit from aggregating multiple expert outputs. This is a compelling direction, especially in settings like LLM ensemble inference.\n    \n- **Sound Algorithm Design and Analysis:**\n    - **SEE** leverages a bandit-based successive elimination strategy for pruning low-performing experts under an egalitarian majority-voting regime.\n    - **$\\theta$-WMV** introduces a more expressive model where experts are weighted by their predictive power. The use of a UCB framework with mixed-integer programming to compute optimal voting weights is clever, albeit potentially computationally intensive.\n        \n        Both algorithms are analyzed rigorously, with regret bounds stated clearly and supported by PAC-style analysis.\n        \n- **Bridging Online Learning and Social Choice Theory:**\n    \n    The connection to optimal voting rules and top-K ordinal aggregation offers an intellectually satisfying perspective and could inspire future work across disciplines.\n    \n\n**Weaknesses:**\n\n1. **Forced Fit with MoE Terminology:**\n    \n    Although framed as a mixture of experts problem, the setting is arguably closer to **ensemble LLM decision aggregation** than traditional MoE architectures (which involve conditional routing and sparsity). The terminology may overpromise or mislead readers familiar with MoE in deep learning.\n    \n2. **High Inference Overhead:**\n    \n    Since the proposed algorithms require querying all (or most) experts at each round, the approach may be **infeasible in latency- or cost-sensitive settings**, particularly when each expert is a large model like an LLM. This undermines the practicality of the method in online LLM inference tasks.\n    \n3. **Weak Modeling of Real-World Feedback:**\n    \n    The formulation assumes access to a scoring function GG that reflects correctness of the experts’ outputs. However, in real-world LLM applications (e.g., open-ended QA), determining whether an output is \"correct\" is often **ambiguous or costly**. This introduces challenges in reward signal design, supervision cost, and label fidelity.\n    \n4. **Catalogue Assumption Limits Generality:**\n    \n    The reliance on a predefined catalogue of possible outputs restricts scalability to **structured prediction tasks** with limited output space. In more realistic NLP tasks—like summarization, image captioning, or generative QA—this assumption is too restrictive and may lead to poor performance or inapplicability.\n    \n\n**Writing and Presentation Issues:**\n\n- The **abstract mentions three algorithms**, though only two are actually proposed. This may confuse readers and should be corrected.\n- The notation is at times **inconsistent or overloaded**, e.g., the symbol $P$ appears with different meanings in different parts of the paper. A careful notation pass is recommended.", "was_revised": true, "final_justification": "The authors solved most of my concerns regarding the MoE term, the efficiency, and the uncertainty of the scoring function. So I raise my score accordingly.", "rebuttal": "We sincerely appreciate the reviewer’s diligent review and valuable insights. In response to the points raised, we aim to provide further clarification to address their concerns.\n\n1. When it comes to multi-agent learning, we believe the **term Mixture of Experts** can capture a wide variety of meanings. The first time this terminology was introduced was in (Nowland and Hinton 1990 [3]), and it was later adopted in conditional routing systems introducing sparsity (Anthony et al. 2024 [4], Shazeer et al. 2017 [5], Dai et al. 2024 [6]), etc. We refer to MoE in its more native introductory form, as in (Nowland and Hinton 1990 [3]). Specifically, we address the online learning problem for MoEs, whereas [4,5,6] address the offline learning problem and, most critically, do not provide theoretical guarantees for their methods. If the terminology is one of the major deficits of our paper, we’d be happy to reword it to “ensemble model aggregation” or “ensemble learning” with LLM applications, as opposed to MoE—nevertheless, we do not see this as a major impasse to either the theory or application of our paper.\n\n2. With respect to **sparsity and high inference overhead**, in fact, our current algorithms (SEE and $\\theta$-OMV) do accommodate model sparsity by targeting a specific number of experts used at any given time. This reduces overhead by limiting the number of experts employed to reduce or regulate computational overhead. We have already included an analysis of this mode of operation and proved in Corollary 3.1 that this increases the complexity of no-regret learning by a factor of $N/m$, while retaining the exact complexity with respect to $T$, or the number of samples.\n\n- Please refer to the Target-$m$ Online Majority Expert Voting algorithm and detailed analysis in A.11.\n\n3. **Open Ended QA:** We do not focus on the problem setting where open-ended questions or RL alignment problems exist in general. Although we recognize that RL alignment, robust reward design, and open-ended QA pose rich and interesting questions in the RL space, we are focused on our core problem and seek to provide rigorous, provable guarantees.\nSaliently, our **core problem setting deals with epistemological ensemble learning**—with extensions to Condorcet’s jury theorem in an online MoE setup. We provide a discussion of this in lines 92–97 of our paper. We believe that this contribution already underscores valuable insights and applications for both the online learning and social choice communities—as well as provides new algorithms for ensemble learning in application.\n\n4. **Our framework is designed for structured prediction tasks**. However, there is no specific limitation regarding the cardinality of the output space. We make a deliberate choice to address the problem of majority voting for multi-class prediction accuracy under expert competence uncertainty—a problem that is non-trivial and largely unsolved.\n\nOverall, our paper aims first to provide provable guarantees for a well-defined problem in online MoE (or ensemble learning) via majority voting. We provide rigorous theoretical guarantees, accompanied by avenues for applications in MoE LLMs. Although several heuristic-based and empirically designed algorithms do exist, provable solutions to this current MoE problem do not exist, to the best of our knowledge. We hope this lends additional appreciation for our current paper.\n\nFurthermore, thank you for bring up minor inconsistencies with our notation and typos, we would be happy to fix this up in an update to our draft. \n\n---\nWe would be glad to offer further clarification if needed and hope our response will lead to an improved assessment of our paper."}, {"review_id": "FTBGWWW0uP", "reviewer": "Reviewer_P2T7", "summary": "This paper presents two settings for decision making with expert sets. The first setting does this by finding the optimal egalitarian expert committee (OEC), i.e., a set of experts whose majority vote outperforms any individual expert. While the experts in the OEC all receive one vote, the second setting proposes finding the optimal weighted voting committee -- where the votes of the experts are weighted by some measure of their competencies. The paper provides optimal solutions in both scenarios when the competencies of the experts are known. It then discusses how these settings can be used for the online Mixture of Experts (MOE) problem, with a new notion of regret in terms of the best set of experts (as opposed to the best individual expert, in standard no regret algorithms for MOE). Two algorithms are proposed corresponding to each setting -- Successive Expert Elimination (SEE) where the OEC is found by eliminating experts with estimated low competencies and $\\theta$-weighted Majority Voting ($\\theta$-WMV) where the voting weights are found using optimistic estimates of competencies. Regret bounds for both the algorithms are derived. Finally, empirical results are presented for online fine-tuning of LLM experts on real datasets.", "questions": "Questions:\n1. How should one choose between the two proposed algorithms in practice? Are there scenarios when one should be prefered over the other?\n2. What is the difference between the \"average scoring function\" (Line 70) and the \"scoring-aggregation function\" (Line 81)?\n3. Line 105: $X_i$ be created conditioned on $c_i(x)$, which is the output prediction. Should it instead not be conditioned on the prediction being correct / incorrect?\n4. Should the condition on $\\theta$ in Equation 2.9 be two-sided (as on line 176)?\n5. Algorithm 1, line 5: \"in descending order\" of what? \n\nOther minor comments:\n1. The abstract reads \"We propose three algorithms ...\" (line 4) but I only see two algorithms discussed in the paper (SEE and $\\theta$-WMV)\n2. Line 44: \"provides convergence best collective\" -> \"provides convergence to best ...\"\n3. Lines 47-48: \"LLM's\" -> \"LLMs\"\n4. Lines 222-223: The sentence \"Recent work on online ... is key\" doesn't read right.\n5. Line 235: \"difference between to expected ...\" doesn't read right.\n6. Line 323: \"amount of experts\" -> \"number of experts\"\n\nI am willing to increase my overall score if the questions/comments mentioned above are addressed and Section 4 (empirical study) is updated with enough detail (see weaknesses for specifics).", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. Clarity: The paper is well-written and easy to understand. The key insights for the SEE and $\\theta$-WMV algorithms are also presented well. My only qualm is with the discussion of the experiments and empirical results, as mentioned in more detail under weaknesses.\n\n2. Well-motivated problem: The problem with the existing notion of regret (w.r.t the best expert) for online Mixture of Experts is well-motivated and the two settings, the egalitarian expert committee and majority voting with a set of experts, are novel in the context of the MOE problem and are discussed in enough detail.\n\n3. The proposed algorithms seem useful in practice for a large enough number of experts (up to 20 in the experiments, Table 1), while providing meaninful regret guarantees (theorems 1-2).\n\n4. Moreover, the proposed algorithms report lower cumulative regret values when compared to baselines in both model-based (with Bernoulli experts) and data-derived settings (with LLM experts) (Table 1).\n\n**Weaknesses**\n\n1. Rushed experiments section: Section 4 (Empirical Study) could use some more details about\n    - The baselines that the proposed algorithms are compared against: These are mentioned in Figure 3 and Table 1 with the results but not discussed at all in the main text (what are they? what the key differences when compared to the proposed algorithms?)\n    - A brief discussion of the results: The results summary paragraph (Line 312 onwards) merely mentions the setup very briefly. The captions for Figure 3 and Table 1 do not discuss the implications of the results either. It would be very helpful to discuss the results in at least a couple of lines to give some more context. It would also be interesting to see what the egalitarian committees found empirically look like in the LLM setup (are the optimal committees found?) and what the weights found for the majority voting approach indicate (which LLMs are weighted higher and why?).\n\n2. Figure 3, with the main comparison of cumulative regret across techniques, is very difficult to parse. The colors are too similar to be differentiated on the graph. I would suggest increasing the sizes of these graphs, using a more diverse color pallette for distinguishing algorithms, and briefly discussing the key takeaway in the caption.\n\nOverall, I am pleased with the clarity of most of the main text (except the experiments section). I also find the expert set notion of regret and the use of top-k bandits with the two proposed algorithms in this setting original. I think that the problem is well-motivated and the application to MOE indicates that this work is indeed significant. This should encourage future work on no regret algorithms with expert sets and MOE. Please see the Questions section below for other questions and suggestions to further improve the paper.", "was_revised": true, "final_justification": "I find the new notion of regret with respect to a set of experts novel and very interesting. The proposed algorithms are explained in enough detail -- the regret bounds look good and the experiments demonstrate empirical usefulness. \n\nWith the assumption that the Experiments section will be updated with the details on the baselines, the typos resolved, and the plots updated for clarity, I think the changes would be minor and would like to recommend acceptance.", "rebuttal": "We thank the reviewer for your positive appraisal of our work - we provide a response to address some of the minor weaknesses and questions regarding our paper.\n\n### Addressing Weaknesses:\n\n1. **Empirical Experiments Clarification (Figure 3 and Table 1):** Due to space constraints, we had to shorten the exposition on describing the empirical performance of the models. In brief, we intend to demonstrate that our algorithms, when compared to their respective baselines, are superior in terms of regret minimization (lower is better). \n\nThe two baselines we compared our problem setting against were:\n\n- **SEE vs. Combinatorial UCB.** We compare the SEE algorithm with the combinatorial UCB bandit algorithm. The combinatorial UCB is a general algorithm and considers all possible combinatorial combinations of expert committees - even possibly ones that are not likely to be optimal. SEE seeks to eliminate potential experts early, if they are highly unlikely to be optimal in a majority vote. Therefore, combinatorial UCB serves as a reasonable baseline, and the superior performance is likely due to SEE’s gradual elimination possibilities in the action space - making the algorithm more efficient.  \n\n- **$\\theta$-WMV vs Zooming (baseline):** The problem of online learning in repeated games where the reward function (in this case our scoring function) is in some general unknown format, is generally difficult. The zooming algorithm (Kleinberg et. al. 2008 [36]) appropriate for no-regret learning in repeated games for general continuous multi-dimension Lipschitz action spaces, accompanied with theoretical guarantees, provides a good general baseline. The zooming algorithm does not assume convexity of the reward function, and is one of the few algorithms which offer theoretical guarantees for this type of problem setting. \n\n    Due to zooming’s generality, its no-regret guarantee is weaker than the no-regret learning guarantee of our $\\theta$-WMV (Alg. 2). This can be confirmed both theoretically and empirically, from our experiments. Feel free, also refer to the work of (Kleinberg et. al. 2008 [36]) for details. We use the zooming algorithm as a baseline to compare with our designed algorithm, $\\theta$-WMV (Alg. 2), that addresses the online majority voting problem setting.\n\n2. **Brief Discussion of Results:** Due to space constraints, we relegated some discussion of results and procedural details to  Appendix C. We provide the details on a larger ablation study, with the chain-of-thought prompting strategy, and LLM individual benchmarks. We believe the results are relatively easy to interpret, basically our algorithm is superior to the aforementioned baselines in terms of regret minimization. The differences are relatively stark in Fig. 3a and 3b), nevertheless we agree that we should produce a new plot for 3c) as too many overlapping shades are distorting the interpretation of the plots. \n\n    An clearer way to compare the plots in its current form would be “blue vs green”. For each dataset (eg. CQA, Bool etc.) we provide comparison between the **green (our paper’s algorithm)** and the **blue (the baselines)**. It is clear that our algorithms exhibit superior performance in terms of regret minimization. Further detailed views, and additional ablations, are provided in Appendix C.5.\n\n- **Updates to Plots:** Unfortunately due to the restrictions on providing PDF updates we could not upload new charts (unlike last year’s NeuRIPS), however, we hope the additional comprehensive experiments in Appendix C.5 notes show more clarity, and we will take your suggestion to polish up our plots to make them more interpretable - should we have a chance for make a camera ready version.\n\n### Answers to Questions:\n\n**Q1. Conditions where one algorithm is preferred over another:** Lemma 2.3 posits that given the same committee of experts, utilizing the $\\theta$-WMV (Alg. 2) to aggregate experts’ output will always yield a stronger result than using egalitarian voting. Therefore, if the computational resources are available we should use the $\\theta$-WMV algorithm for better predictive accuracy. However, if there are limited computational resources, or if the goal is to learn an efficient representation of experts (i.e. a sparse set of experts) then perhaps SEE (Alg. 1) algorithm is a better choice to retain efficiency.\n\n**Q2: Average scoring function vs score-aggregation function:** The average scoring function is the expectation over the composition of the aggregation first $A(\\cdot)$, followed by the scoring function $G(\\cdot)$, according to distribution $P(x)$ over all contexts. The score-aggregation function is actually just the aggregation function $A(\\cdot)$ (we will update our draft to avoid confusion).\n\n**Q3. W.r.t. To Eq. 2.3,**  the set $\\mathcal{X}_i$ is defined as a subset of contexts for which a given expert i’s prediction, denoted by $c_i$, returns the correct answer. This allows us to partition the space of contexts depending on whether the expert was correct or not. Each expert has its own partitions, and subsequently allows us to rewrite the average scoring function in line 108. \n\n**Q4. Eq. 2.9 Two-sided:** To be consistent we should correct this to the same two sided condition as in line 276, however, in its current form it makes no difference, due to Lemma 2.2, because the maximizing solution can be replaced with $|| \\theta || = 2Q$, so even if $|| \\theta_1 || < 2Q$ it could be suboptimal, as there is an equivalent maximizing solution at $|| \\theta || = 2Q$. (Nevertheless, we will make the minor update to be consistent.)\n\n**Q5. Descending Order (Alg. 1 Line 5):** This refers to the descending order of the expert’s competencies $p_i$. We perform the removal test by adding incrementally weaker experts to a shadow committee, and removing them entirely for future consideration should their theoretical contributions to the committee yield suboptimal results, under optimistic estimate\n\n**Typos:** Thank you for pointing out minor typos in our paper. We will definitely address them in an update to our paper. \n\n**Updates to Plots:** Unfortunately due to the restrictions on providing PDF updates we could not upload new charts (unlike last year’s NeuRIPS), however, we hope the additional comprehensive experiments in Appendix C.5 notes show more clarity, and we will take your suggestion to polish up our plots to make them more interpretable - should we have a chance for make a camera ready version.\n\n---\n\nWe thank the reviewer once again for your insightful comments and suggestions. Should further clarifications and/or discussions be required we would be happy to oblige. We hope the additional details and response will lead to an increase in overall assessment of our paper."}]

Author rebuttal:

Meta-review: The paper proposes a novel online learning framework, Online Mixture of Experts (OMoE), for collective decision-making through expert aggregation, particularly in settings involving large language models (LLMs). It introduces two algorithms: Successive Expert Elimination (SEE) for egalitarian majority voting and θ-Weighted Majority Voting (θ-WMV) for weighted voting based on expert competencies. The key contributions include rigorous no-regret guarantees for these algorithms under a new regret formulation—defined with respect to optimal expert committees rather than single best experts. 

The reviewers appreciated the original formulation and theoretical grounding, highlighting that the approach extends classical online learning and voting mechanisms in meaningful ways. However, concerns were raised regarding: (1) the alignment of the problem with traditional MoE terminology (R2, R3); (2) incomplete or unclear experimental details and baseline descriptions (R4); (3) context-independence in the scoring function which seemed unrealistic for LLMs (R2); and (4) literature positioning especially in relation to CMAB and ensemble learning (R2). 

Overall, I recommend acceptance. Despite some open concerns—mainly around scope (e.g., generalizability to broader NLP tasks) and literature framing—the paper presents a novel and well-argued contribution to the field of online expert aggregation. It offers both solid theoretical insights and promising empirical performance. Please incorporate the final suggestions of the reviewers in the camera-ready version as promised.
Decision: Accept (poster)