Technische Zusammenfassung: Über statische Verzerrung hinaus: Adaptive Multi-Fidelity-Banditen mit verbessernden Proxys

Problemdefinition

Diese Arbeit behandelt eine spezifische Erweiterung des stochastischen Multi-Armed-Bandit-Problems (MAB), bekannt als Multi-Fidelity Multi-Armed Bandits (MF-MAB). In herkömmlichen MF-MAB-Szenarien können Arme mit mehreren Feedbackquellen (Fidelitäten) bewertet werden, die Kosten gegen Genauigkeit abwägen. Traditionelle Rahmenwerke gehen von einer statischen Verzerrung zwischen niedrig-fidelen (günstigen) und hoch-fidelen (teuren) Quellen aus; die Diskrepanz bleibt unabhängig davon, wie oft die niedrig-fidele Quelle abgefragt wird, konstant.

Moderne Anwendungen, die lernbasierte Simulatoren und Large Language Models (LLMs) als Evaluatoren einsetzen, weisen jedoch eine andere Dynamik auf: Die niedrig-fidele Proxyquelle kann sich durch zusätzliche Kalibrierung oder wiederholte Nutzung verbessern. Der Artikel untersucht ein MF-MAB-Szenario mit Budgetbeschränkung, bei dem:

1. Es $K$ Arme mit einem stationären hoch-fidelen Zielmittelwert $\mu^{(H)}_k$ gibt.
2. Eine niedrig-fidele Quelle Beobachtungen $Y^{(L)}_{k,\tau}$ liefert, die sich basierend auf der Anzahl der Abfragen $\tau$ an diesen spezifischen Arm entwickeln.
3. Die niedrig-fidele Quelle mit einer Diskrepanz relativ zum hoch-fidelen Ziel beginnt, diese Diskrepanz jedoch mit zunehmender Abfragehäufigkeit der Quelle (z. B. durch Kalibrierung) abnimmt.
4. Das Ziel darin besteht, den kosten-gewichteten Pseudo-Regret zu minimieren, definiert als die kumulierten Kosten durch die Auswahl suboptimaler Arme, und nicht nur die Anzahl der Ziehungen.

Die Kernherausforderung besteht darin, zu bestimmen, wann die Abfrage der sich verbessernden niedrig-fidelen Quelle beendet und auf die teure hoch-fidele Quelle umgeschaltet werden soll. Eine statische Schwellenwertregel könnte zu früh umschalten und die Chance verpassen, dass die niedrig-fidele Quelle durch fortgesetztes günstiges Sampling ausreichend genau wird.

Methodik

Modellierung des verbessernden Proxys

Die Autoren führen eine ausgewählte-Durchschnitts-Diskrepanzschranke ein, um die sich entwickelnde Diskrepanz zu erfassen. Anstatt eine feste Verzerrung $|\mu^{(L)}_k - \mu^{(H)}_k| \le \zeta$ anzunehmen, gehen sie von einem sich entwickelnden Zertifikat $U_k(n)$ aus, sodass die kumulative Diskrepanz beschränkt ist:
$$\sum_{\tau=1}^n |\mu^{(L)}_k(\tau) - \mu^{(H)}_k| \le U_k(n)$$
Dies führt zu einer ausgewählten-Durchschnitts-Diskrepanzschranke $B_k(n) = \sup_{s \ge n} U_k(s)/s$, die die Diskrepanz zwischen dem empirischen niedrig-fidelen Mittelwert und dem wahren hoch-fidel Ziel begrenzt. Mit zunehmendem $n$ nimmt $B_k(n)$ ab und spiegelt die zunehmende Zuverlässigkeit des Proxys wider.

Der TACC-Algorithmus

Der Artikel schlägt den Threshold-Based Adaptive Continuation Companion (TACC)-Algorithmus vor. TACC arbeitet auf einer vertrauensbasierten Vorlage, führt jedoch eine neuartige begrenzte Fortsetzungsregel für die niedrig-fidele Quelle ein.

1. Konfidenzintervalle: TACC konstruiert Upper Confidence Bounds (UCB) für den hoch-fidel Zielwert $\mu^{(H)}_k$ unter Verwendung beider Fidelitäten.
   • Hoch-fideles UCB: Standardstatistisches Intervall.
   • Niedrig-fideles UCB: Standardstatistisches Intervall plus die Diskrepanzkorrektur $B_k(n)$.
2. Arm-Auswahl: Der Algorithmus wählt den Arm mit dem höchsten optimistischen Score aus, definiert als das Minimum der niedrig-fidel und hoch-fidel UCBs.
3. Fidelitätsauswahl (Die Kerninnovation):
   • Vor dem Schwellenwert: Wenn die statistische Unsicherheit (Radius) der niedrig-fidel Quelle über einem Schwellenwert $\gamma$ liegt, fährt der Algorithmus mit dem Sampling in niedriger Fidelität fort.
   • Nach dem Schwellenwert: Sobald der statistische Radius unter $\gamma$ fällt, würde eine statische Regel sofort auf hohe Fidelität umschalten. TACC prüft jedoch, ob eine begrenzte Fortsetzung kosteneffektiv ist.
   • Fortsetzungsregel: Der Algorithmus berechnet die erwartete Abnahme der Diskrepanzkorrektur $V_{k,t}(s)$, wenn $s$ zusätzliche niedrig-fidele Abfragen durchgeführt werden. Wenn die Reduktion der Diskrepanz ausreicht, um die Suboptimalität des Arms möglicherweise ohne hoch-fidele Bestätigung zu zertifizieren, und die Kosten dieser zusätzlichen Abfragen begrenzt sind (speziell $S_0 \lambda^{(L)} \le \lambda^{(H)}$), fährt TACC mit dem Sampling in niedriger Fidelität fort. Andernfalls schaltet er auf hohe Fidelität um.

Hauptbeiträge

1. Problemformulierung: Der Artikel formalisiert das MF-MAB-Szenario mit verbessernden Proxyquellen und geht über die in der früheren Literatur vorherrschende Annahme einer statischen Verzerrung hinaus. Er führt die ausgewählte-Durchschnitts-Diskrepanzschranke ein, um die dynamische Reduktion der Diskrepanz zu modellieren.
2. Algorithmenentwurf: TACC wird als optimistischer Algorithmus vorgeschlagen, der eine Standard-Arm-Auswahl mit einer begrenzten Fortsetzungsregel nach dem Schwellenwert kombiniert. Diese Regel entscheidet explizit, ob die „Verbesserung" der niedrig-fidel Quelle eine Verzögerung der teuren hoch-fidel Abfrage rechtfertigt.
3. Theoretische Analyse: Die Autoren leiten eine instanzabhängige Regret-Schranke her. Die Analyse unterteilt suboptimale Arme in drei Klassen:
   • Einfache Arme ($A_\gamma$): Von niedriger Fidelität vor dem Schwellenwert zertifiziert.
   • Intermediäre Arme ($C_\gamma$): Nicht beim statischen Schwellenwert zertifiziert, aber nach begrenzter Fortsetzung in niedriger Fidelität zertifizierbar.
   • Schwere Arme ($H_\gamma$): Erfordern hoch-fidele Bestätigung.
     Die Schranke zeigt, dass TACC für erkannte intermediäre Arme die logarithmischen Kosten der hoch-fidel Bestätigung durch eine begrenzte Fortsetzungskosten in niedriger Fidelität ersetzt.
4. Empirische Validierung: Experimente mit synthetischen Banditen und einer kontrollierten LLM-as-a-Judge-Richtlinienbewertungsaufgabe zeigen, dass TACC den kosten-gewichteten Regret im Vergleich zu statischen Multi-Fidelity-Regeln (MF-UCB) und Baselines nur mit hoher Fidelität (UCB) reduziert.

Ergebnisse

Synthetische Experimente

In synthetischen Szenarien mit 200 und 500 Armen erzielte TACC konsistent einen niedrigeren kosten-gewichteten Regret als UCB, MF-UCB und statische Zwei-Fidelitäts-Regeln. Der Vorteil war in Szenarien mit hohen hoch-fidel Kosten (z. B. $\lambda^{(H)} = 50$) am ausgeprägtesten, wo die Vermeidung unnötiger hoch-fideler Bestätigungen durch begrenzte Fortsetzung erhebliche Einsparungen brachte.

LLM-as-a-Judge-Experiment

Die Autoren bewerteten TACC in einer Richtlinienbewertungspipeline, bei der Arme Prompt-Richtlinien für Natural Language Inference (NLI) waren.

• Aufbau: Niedrige Fidelität war ein „schwacher Richter" (ein kleineres LLM), das sich mit der Kalibrierung verbesserte; hohe Fidelität war ein „Verifizierer" (Ground Truth).
• Ergebnisse: TACC schnitt besser ab als alle Baselines, einschließlich einer direkten Ablation (DNC), die dieselben Diskrepanzschranken verwendete, aber die Fortsetzungslogik fehlte. TACC reduzierte den finalen kosten-gewichteten Regret um etwa 10–20 % im Vergleich zu den besten statischen Baselines und bestätigte, dass der Mechanismus der begrenzten Fortsetzung die verbessernde Natur des schwachen Richters effektiv nutzt, um eine vorzeitige Eskalation zum teuren Verifizierer zu vermeiden.

Bedeutung und Behauptungen

Der Artikel behauptet, dass die primäre Bedeutung dieser Arbeit darin liegt, anzuerkennen, dass Proxyquellen in modernen KI-Systemen nicht statisch sind. Indem die Autoren die niedrig-fidele Quelle als eine sich verbessernde Entität behandeln, zeigen sie, dass die optimale Strategie nicht darin besteht, lediglich basierend auf der aktuellen Unsicherheit die Fidelität zu wechseln, sondern das Sampling der günstigen Quelle adaptiv fortzusetzen, wenn erwartet wird, dass sie sich ausreichend verbessert, um die Mehrdeutigkeit aufzulösen.

Die Autoren formulieren ihren Beitrag bescheiden als kanonisches Zwei-Fidelitäts-Modell. Sie erkennen Einschränkungen an und stellen fest, dass die aktuelle Arbeit eine bekannte Diskrepanzschranke voraussetzt und sich auf eine arm-lokale Evolution konzentriert (wobei die Verbesserung nur auftritt, wenn ein spezifischer Arm abgefragt wird), anstatt auf ein globales Modell-Finetuning, das alle Arme gleichzeitig beeinflusst. Die Arbeit dient als grundlegender Schritt hin zu komplexeren, dynamischen Strategien zur Fidelitätszuweisung in Szenarien mit LLMs und lernbasierten Simulatoren.