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

Probleemstelling

In het veld van generatieve kunstmatige intelligentie (AI) hebben onderzoekers en practitioners vaak toegang tot meerdere vooraf getrainde generatieve modellen (bijv. GANs, Diffusiemodellen, VAEs) die verschillen in architectuur, trainingsdata en inferentiekosten. Het selecteren van het beste model of een combinatie van modellen is een fundamenteel probleem.

• Kostbaarheid: Het genereren van samples van suboptimale modellen is computatief duur en evaluatiebudgetten zijn beperkt.
• Mixture vs. Single Arm: In tegenstelling tot klassieke "Best-Arm Identification" (waarbij één enkel beste model wordt gekozen), tonen recente studies aan dat onder diversiteitsbewuste evaluatiemetrics (zoals FID, Vendi Score, KID, RKE) een niet-degeneratieve mix van generatoren strikt beter kan presteren dan elk individueel model.
• Huidige Aanpak: Bestaande methoden (zoals Mixture-UCB) passen het principe van Upper Confidence Bound (UCB) toe om exploratie te forceren. Ze voegen een "optimisme-bonus" toe aan de schattingen om onzekerheid te onderzoeken.
• De Vraag: Is deze expliciete UCB-exploratiebonus daadwerkelijk noodzakelijk voor diversiteitsbewuste selectie, of leidt deze juist tot trager convergeren en minder efficiënt gebruik van samples?

Methodologie: Mixture-Greedy

De auteurs stellen een nieuwe aanpak voor genaamd Mixture-Greedy, die geen expliciete UCB-exploratiebonus gebruikt.

1. Formulering: Het probleem wordt gemodelleerd als een stochastisch Multi-Armed Bandit (MAB) probleem over een simplex $\Delta_m$ (waarbij $\alpha$ de gewichten van de mix van $m$ generatoren voorstelt).
2. Doelfunctie: Het doel is om een score te maximaliseren (of een verlies te minimaliseren) gebaseerd op de gegenereerde samples. De auteurs focussen op drie families van objectieven:
   • Fréchet Distance (FD): Gebaseerd op momentenmatching (mean en covariance) van embeddings.
   • Negatieve log-Vendi: Gebaseerd op de Von Neumann entropie van de kernel Gram-matrix (een maat voor diversiteit).
   • Convexe kwadratische scores: Zoals Kernel Distance (KID) en RKE, soms gecombineerd met lineaire betrouwbaarheidstermen (fidelity).
3. Algoritme:
   • Op elke ronde $t$ berekent het algoritme de empirische loss $\hat{L}_{t-1}(\alpha)$ gebaseerd op de tot nu toe verzamelde samples.
   • Het lost het convex optimalisatieprobleem op: $\alpha_t = \arg\min_{\alpha \in \Delta_m} \hat{L}_{t-1}(\alpha)$.
   • Het kiest een arm (generator) $I_t$ volgens de verdeling $\alpha_t$ en trekt een sample.
   • Oplossingsmethode: Gebruik van Exponentiated Gradient (EG) descendie om de simplex-beperkingen efficiënt te respecteren.
4. Kernidee: In plaats van externe exploratie toe te voegen, vertrouwt het algoritme op de geometrie van de doelstelling zelf. Voor diversiteitsmetrics ligt het optimum vaak in het interieur van de simplex (een mix van modellen), niet op de rand (één enkel model). Het minimaliseren van de empirische loss drijft de oplossing van nature naar het interieur, wat impliceert dat alle arms voldoende worden gesampled.

Belangrijkste Bijdragen

1. Empirische Bevinding: Uit uitgebreide experimenten op meerdere datasets (ImageNet, FFHQ, LSUN-Bedroom) en metrics (FID, KID, RKE, Vendi) blijkt dat het toevoegen van een UCB-bonus de convergentie altijd vertraagt en de sample-efficiëntie verlaagt. Mixture-Greedy convergeert sneller en bereikt betere prestaties dan Mixture-UCB.
2. Theoretisch Inzicht: De auteurs tonen aan dat voor diversiteitsbewuste objectieven exploratie intrinsiek ontstaat uit de structuur van het optimalisatieprobleem.
   • Voor entropie-gebaseerde doelen (Vendi) en onder bepaalde randvoorwaarden voor FD en RKE, dwingt de doelstelling de optimale mix naar het interieur van de simplex.
   • Dit voorkomt dat het algoritme "instort" naar één arm (een bekend probleem bij pure greedy strategieën in lineaire bandieten).
3. Regret-Garanties: Ze bewijzen theoretische sublineaire regret-garanties voor Mixture-Greedy zonder UCB, voor:
   • Entropie-gebaseerde doelen (negatieve log-Vendi).
   • Fréchet Distance (onder een "population interiority margin" voorwaarde).
   • Kwaliteit-gebaseerde doelen (RKE/KD).
   • Combinaties met lineaire betrouwbaarheidstermen.

Resultaten

• Convergentie: In figuren 1 en 2 wordt getoond dat Mixture-Greedy sneller convergeert naar de "Mixture Oracle" (de theoretisch optimale mix) dan Mixture-UCB.
• Prestatie: Mixture-Greedy bereikt een lagere Fréchet Distance (beter) en een hogere Vendi Score (meer diversiteit) dan zowel de beste individuele arm als de UCB-baselines.
• Robuustheid: De resultaten zijn robuust voor verschillende feature extractors (Inception, CLIP, DINOv2), kernel-breedtes en het aantal Random Fourier Features.
• Synthetische Tests: Experimenten met tekst-naar-beeld en tekst-naar-tekst modellen (LLMs) bevestigen dat adaptieve mixen van modellen superieure diversiteit oplevert dan het gebruik van één model.

Betekenis en Conclusie

Dit paper daalt de fundamentele aanname dat expliciete optimisme-bonussen (UCB) noodzakelijk zijn voor effectieve exploratie in bandit-problemen.

• Paradigmaverschuiving: Voor generatieve modelselectie met diversiteitsmetrics is de "geometrie van de doelstelling" (de neiging om niet-degeneratieve mixen te belonen) voldoende om exploratie te genereren.
• Praktische Impact: Het verwijderen van de UCB-term vereenvoudigt het algoritme aanzienlijk, vermindert de rekentijd (geen berekening van confidencereeksen) en verbetert de prestaties, vooral voor niet-kwadratische metrics zoals FID en Vendi waar het construeren van strakke UCB-bounds moeilijk is.
• Toekomst: De auteurs suggereren dat toekomstige bandit-methoden voor generatieve AI ontworpen moeten worden rondom de specifieke geometrie van de evaluatiemetrics, in plaats van te vertrouwen op generieke optimisme-bonussen.

Kortom: Exploratie komt "gratis" uit de doelstelling zelf; we hebben UCB niet nodig.