When Exploration Comes for Free with Mixture-Greedy: Do we need UCB in Diversity-Aware Multi-Armed Bandits?

1. Problemstellung

Die Arbeit adressiert das Problem der effizienten Auswahl und Kombination von mehreren generativen Modellen (z. B. GANs, Diffusionsmodelle, VAEs) in einem Online-Setting. Da das Generieren von Proben aus suboptimalen Modellen rechenintensiv ist und Evaluierungsbudgets begrenzt sind, wird dies als stochastischer Multi-Armed Bandit (MAB) formuliert.

Der entscheidende Unterschied zu klassischen MAB-Problemen liegt in der Zielsetzung:

• Klassisch: Ziel ist die Identifizierung eines einzelnen „besten Arms" (Best-Arm Identification).
• Hier: Unter diversitätsbewussten Metriken (wie FID, Vendi-Score, KID, RKE) kann eine nicht-degenerierte Mischung (Mixture) mehrerer Modelle die Leistung jedes einzelnen Modells übertreffen. Das Optimum liegt oft im Inneren des Wahrscheinlichkeits-Simplex $\Delta_m$, nicht an einer Ecke (d.h. nicht bei einem einzelnen Modell).

Bisherige Ansätze (z. B. Rezaei et al., 2025) adaptierten den Upper Confidence Bound (UCB)-Algorithmus für dieses Szenario, indem sie einen Explorations-Bonus in die Zielfunktion integrierten, um sicherzustellen, dass alle Modelle ausreichend gesampelt werden. Die Autoren hinterfragen jedoch die Notwendigkeit dieses expliziten Optimismus-Bonus.

2. Methodik: Mixture-Greedy

Die Autoren schlagen einen einfachen Mixture-Greedy-Algorithmus vor, der keinen expliziten UCB-Explorationsbonus verwendet.

• Algorithmus: In jeder Runde $t$ berechnet der Algorithmus die empirische Verlustfunktion $\hat{L}_{t-1}(\alpha)$ basierend auf den bisher gesammelten Daten. Er löst dann ein konvexes Optimierungsproblem über dem Simplex $\Delta_m$, um die Gewichte $\alpha_t$ zu finden, die den empirischen Score minimieren (bzw. maximieren).
• Sampling: Anstatt einen Arm deterministisch zu wählen, wird ein Arm $I_t$ gemäß der Verteilung $\alpha_t$ gesampelt, und eine Probe $X_t$ wird generiert.
• Optimierung: Zur effizienten Lösung auf dem Simplex wird der Exponentiated Gradient (EG)-Descent (ein Mirror-Descent-Verfahren mit KL-Geometrie) verwendet.
• Zielfunktionen: Die Methode wird für drei wichtige Klassen von Zielfunktionen analysiert:
  1. Fréchet Distance (FD): Basierend auf Momenten-Matching (Mittelwert und Kovarianz).
  2. Negative Log-Vendi (bzw. negative von-Neumann-Entropie): Basierend auf der Eigenwertstruktur der Kernel-Matrix.
  3. Konvexe quadratische Scores: Wie Kernel Distance (KD/MMD) und inverse RKE.

3. Theoretische Einblicke und Hauptbeiträge

Der Kernbeitrag des Papers ist die theoretische und empirische Demonstration, dass Exploration in diversitätsbewussten Mischungsproblemen intrinsisch durch die Geometrie der Zielfunktion entsteht und kein externer UCB-Bonus benötigt wird.

• Implizite Exploration: Bei diversitätsbewussten Metriken führt das Optimum typischerweise zu einer Mischung im Inneren des Simplex (alle $\alpha_i > 0$). Degenerierte Lösungen (nur ein Modell) werden von der Zielfunktion bestraft. Daher tendiert die Optimierung der empirischen Verlustfunktion dazu, Gewichte im Inneren des Simplex zu finden, was automatisch sicherstellt, dass alle Arme weiterhin Proben erhalten.
• Theoretische Garantien: Die Autoren beweisen sublineare Regret-Grenzen ($O(\sqrt{T})$) für den Mixture-Greedy-Algorithmus ohne UCB unter bestimmten strukturellen Bedingungen:
  • Für Log-Vendi: Unter Annahmen über die „Innovation" der Population (Assumption 2) bleibt der Algorithmus uniform vom Rand des Simplex fern, was zu einer linearen Abdeckung aller Arme führt.
  • Für Fréchet Distance: Unter einer „Population Interiority Margin" (das Optimum liegt mit einem gewissen Abstand im Inneren) wird ebenfalls sichergestellt, dass keine Gewichte gegen Null gehen.
  • Diese Ergebnisse gelten auch für lineare Treue-Terme (Fidelity), die mit den Diversitätsmetriken kombiniert werden.

4. Ergebnisse

Die empirischen Experimente wurden auf mehreren Datensätzen (ImageNet, FFHQ, LSUN-Bedroom) und mit verschiedenen generativen Modellen durchgeführt.

• Vergleich mit UCB: Der Mixture-Greedy-Ansatz konvergiert schneller als der Mixture-UCB-Ansatz (mit explizitem Explorationsbonus).
• Effizienz: In vielen Fällen (insbesondere bei nicht-quadratischen Metriken wie FID und Vendi, wo UCB-Schranken schwer zu konstruieren sind) führt der UCB-Bonus sogar zu einer geringeren Stichprobeneffizienz und langsameren Konvergenz, da er zu übermäßiger Exploration (Over-Exploration) zwingt.
• Leistung: Mixture-Greedy erreicht oft eine Leistung, die der des „Mixture Oracle" (das die optimalen Gewichte im Voraus kennt) sehr nahe kommt und übertrifft dabei deutlich die „One-Arm Oracle" (das nur das beste einzelne Modell nutzt).
• Robustheit: Die Ergebnisse sind robust gegenüber verschiedenen Feature-Extraktoren (Inception, CLIP, DINOv2), Kernel-Bandbreiten und Approximationen (Random Fourier Features).

5. Signifikanz und Fazit

Das Paper stellt ein fundamentales Designprinzip in Frage: Die Notwendigkeit von expliziten Optimismus-Boni (wie UCB) in Bandit-Problemen.

• Paradigmenwechsel: Für generative Modell-Auswahl unter Diversitätskriterien ist der klassische Ansatz „Exploration durch Unsicherheit" (UCB) nicht nur unnötig, sondern oft kontraproduktiv. Stattdessen entsteht Exploration natürlich aus der Struktur des Optimierungsproblems selbst, da das Ziel die Mischung von Modellen erfordert.
• Praktische Implikation: Dies ermöglicht einfachere, recheneffizientere Algorithmen (nur Greedy-Optimierung), die in der Praxis schneller konvergieren und weniger Samples benötigen.
• Zukunft: Die Arbeit zeigt, dass Bandit-Methoden für generative Modelle um die durch die Zielfunktion induzierte Geometrie herum entwickelt werden sollten, anstatt sich auf generische Optimismus-Boni zu verlassen.

Zusammenfassend beweist die Arbeit, dass bei der Auswahl von Mischungen generativer Modelle „Exploration kostenlos" ist, da die Diversitätsziele das System intrinsisch daran hindern, sich auf ein einzelnes Modell festzulegen.