Research map / Bandits and online learning / Online convex optimization and games
Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes online mixture-of-experts bandit algorithms (successive expert elimination and weighted majority voting via MIP) with no-regret guarantees for committee-based aggregation, applied to LLM experts on GSM8K, CommonsenseQA, and BoolQ.
Problem
Online MoE methods such as EXP4 converge to the best single expert, failing to exploit collective gains from aggregating experts by voting; the goal is to learn the optimal expert committee and aggregation weights online with sample-efficient regret guarantees.
Approach
Combines majority/weighted voting aggregation with UCB-style successive elimination of experts (SEE) and an online weighted majority voting approach (θ-WMV) whose weights are chosen via a mixed-integer program over optimistic competency estimates, with regret bounds O(N log T / ε²) and O(sqrt(NT log T)).
Key results
- SEE on simulated Bernoulli experts (N=20) reduced cumulative regret to 546.2 vs 6932 for combinatorial UCB, reaching 0.980 majority accuracy.
- θ-WMV on GSM8K (N=9) achieved regret 587.0 vs 3443 for zooming, with majority accuracy 0.927.
- On CommonsenseQA (N=5), SEE attained 0.810 accuracy with regret 676.8 vs 1065 for combinatorial UCB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SEE instead of Comb. UCB | Bernoulli experts · Bernoulli | R_T: 6932 -> 546.2 | Helped |
| Use SEE instead of Comb. UCB | Bernoulli experts · Bernoulli | empirical accuracy: 0.370 -> 0.980 | Helped |
| Use θ-WMV instead of Zooming | LLM expert voting · GSM8K | R_T: 3443 -> 587.0 | Helped |
| Use θ-WMV instead of Zooming | LLM expert voting · GSM8K | empirical accuracy: 0.604 -> 0.927 | Helped |
| Use SEE instead of Comb. UCB | LLM expert voting · CommonsenseQA | R_T: 1065 -> 676.8 | Helped |
| Use SEE instead of Comb. UCB | LLM expert voting · CommonsenseQA | empirical accuracy: 0.664 -> 0.810 | Helped |
| Use θ-WMV instead of Zooming | LLM expert voting · BoolQ | R_T: 740.3 -> 360.9 | Helped |
| Use θ-WMV instead of Zooming | LLM expert voting · BoolQ | empirical accuracy: 0.694 -> 0.735 | Helped |
Limitations
- θ-WMV relies on solving a mixed-integer program that may be intractable for large expert pools
- Contextual/side information not used
- Independence assumption on experts for the theory; regret guarantees rely on assumed sub-Gaussian competencies and a minimum gap
Experimental setup
Datasets: GSM8K CommonsenseQA BoolQ
Benchmarks: GSM8K CommonsenseQA BoolQ
Metrics: cumulative regret aggregate majority-vote accuracy
Baselines: Combinatorial UCB Zooming algorithm EXP4
Builds on: EXP4 successive elimination bandit combinatorial UCB Condorcet jury theorem
Closest papers by meaning
- Equipping Experts/Bandits with Long-term Memory (NeurIPS 2019 · similarity 0.88)
- No-Regret Online Prediction with Strategic Experts (NeurIPS 2023 · similarity 0.88)
- Autonomy-of-Experts Models (ICML 2025 · similarity 0.87)
- Managing Self-Learning Experts under Per-Round Budget Constraints (NeurIPS 2026 · similarity 0.86)
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.86)
- Retraining-free Merging of Sparse MoE via Hierarchical Clustering (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.