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

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.

Addressing Weaknesses:

1. 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).

The two baselines we compared our problem setting against were:

• 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.

• $\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.

  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.

2. 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.

   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.

• 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.

Answers to Questions:

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.

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).

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.

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.)

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

Typos: Thank you for pointing out minor typos in our paper. We will definitely address them in an update to our paper.

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.

---

We 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.

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.

1. 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.

2. 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.

• Please refer to the Target-$m$ Online Majority Expert Voting algorithm and detailed analysis in A.11.

3. 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. Saliently, 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.

4. 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.

Overall, 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.

Furthermore, 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.

---

We would be glad to offer further clarification if needed and hope our response will lead to an improved assessment of our paper.

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.

• 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.

2. 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.

3. 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.

• 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.

4. 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.

• 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.

Addressing the specific questions:

1. 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.

• 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.

• 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.

2. 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.

---

We 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.

Thank you for the detailed response. I appreciate the clarifications and the additional discussions. I still have a few remaining concerns regarding the literature, significance, and the scoring function design.

1. The citations for online MoE (e.g., [9, 14]) are general-purpose online learning textbooks and not specific to online MoE settings. Including more relevant work on online ensemble learning, expert aggregation, or top-K voting would better situate the contribution within the context of online LLM or ensemble selection.

2. I appreciate the discussion on combinatorial UCB, but would like to clarify my concern. Modern CMAB algorithms (e.g., Chen et al. 2013; Wang & Chen 2017; Merlis & Mannor 2019) are specifically designed to mitigate combinatorial explosion. Thus, I disagree with the claim that combinatorial UCB inherently suffers from this issue. In fact, many CMAB formulations can naturally model subcommittee selection, even without explicitly incorporating voting. Without a direct comparison or clearer justification of novelty beyond existing CMAB techniques, it remains difficult to assess the significance of the proposed methods.

3. I remain unconvinced by the context-independence assumption in the scoring function. My original question—if the score of a prediction $c \in C$ is independent of the query (or context) $x$, does that imply the optimal aggregated output is the same across all queries?—was not directly addressed. In practice, LLM outputs are typically query-dependent, so using a fixed scoring function across all contexts seems counterintuitive.

4. (Minor) I agree with Reviewer BNid that the problem setting is more aligned with ensemble-based LLM decision aggregation than with traditional MoE architectures. It may be helpful to revise the title or framing to better reflect the focus on voting-based expert aggregation.

5. (Minor) I understand that for classification-style tasks (e.g., GSM8K, BoolQ), ground-truth labels serve as the scoring signal. However, in open-ended tasks where no labels are available, how might the current scoring framework be extended? While this is not a major concern, I think it is a meaningful direction for future work.

(Chen et al. 2013) Chen, Wei, Yajun Wang, and Yang Yuan. "Combinatorial multi-armed bandit: General framework and applications." In International conference on machine learning, pp. 151-159. PMLR, 2013.

(Wang & Chen 2017) Wang, Qinshi, and Wei Chen. "Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications." Advances in Neural Information Processing Systems 30 (2017).

(Merlis & Mannor 2019) Merlis, Nadav, and Shie Mannor. "Batch-size independent regret bounds for the combinatorial multi-armed bandit problem." In Conference on Learning Theory, pp. 2465-2489. PMLR, 2019.

Yes, the current expression in line 66 should be updated to reflect that $G: C \times X \mapsto \mathbb{R}$. Consequently, Eq. 2.2 should be revised to:

$$p_i := \int_{x} G \left( c_i(x), x \right) dP(x).$$

Similarly, Eq. 2.1 should be updated so that $G(\cdot)$ takes both $c$ and $x$ as arguments. This ensures that the score varies across queries, as as accurately reflected in our experiments. The current static scoring function Eq. 2.,2, does not reflect the actual operation of the scoring function, and it is a minor error of expression which will be corrected.

In our experiments, for each context, the true label (i.e. correct answer) will receive an of score 1 from the scoring function - as it applies to the datasets (GSM8K, BoolQ etc.). Beyond this, there is no additional implicit mechanism by which the context still influences scoring - perhaps that’s where some misunderstanding could have arisen.

We will clarify these points in an update to our paper, and we thank the reviewer for bringing this to our attention.

We thank the reviewer deeply for the time and effort taken to review our paper, and your overall positive appraisal.

To 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]).

Furthermore, 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.

---

We 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.