Technische Zusammenfassung: Lineare und neuronale duellierende Banditen mit verzögerter Rückmeldung

1. Problemdefinition

Die Arbeit behandelt das Problem der kontextuellen duellierenden Banditen (CDB) unter stochastischer verzögerter Rückmeldung. In Standard-CDB-Szenarien wählt ein Agent ein Paar von Armen (Kandidaten) aus und erhält sofortiges binäres Präferenzfeedback (z. B. $x_1 \succ x_2$), um eine latente Belohnungsfunktion zu erlernen. In realen Anwendungen wie der Ausrichtung von Large Language Models (LLM), der Prompt-Optimierung und der Display-Werbung ist das Feedback jedoch oft asynchron.

Das in dieser Arbeit formalisierte spezifische Szenario geht von folgenden Annahmen aus:

• Stochastische Verzögerungen: Das Feedback für eine Aktion, die in Runde $s$ durchgeführt wurde, trifft nach einer zufälligen Verzögerung $D_s$ ein.
• Harter Schwellenwert: Es gibt ein maximales Beobachtungsfenster $M$. Wenn $D_s > M$ gilt, wird das Feedback als fehlend behandelt (zensiert).
• Beobachtungswahrscheinlichkeit: Die Wahrscheinlichkeit, dass das Feedback innerhalb des Fensters eintrifft, beträgt $\rho = P(D_s \le M)$.
• Verzerrungs-Herausforderung: Im Gegensatz zu linearen Banditen, bei denen Schätzer geschlossene Lösungen haben (z. B. Ridge-Regression), verlassen sich duellierende Banditen auf die Maximum-Likelihood-Schätzung (MLE) unter dem Bradley-Terry-Luce-Modell (BTL). Das Fehlen geschlossener Lösungen bedeutet, dass naive Anpassungen herkömmlicher Techniken für verzögertes Feedback (wie einfache Imputation oder das Ignorieren fehlender Daten) systematische Verzerrungen einführen, die sich nicht einfach begrenzen oder korrigieren lassen.

2. Methodik

Die Autoren schlagen zwei neuartige Algorithmen vor, die diese Verzögerungen ohne heuristische Imputation handhaben: Lineare duellierende Banditen mit verzögerter Rückmeldung (LDB-DF) und Neuronale duellierende Banditen mit verzögerter Rückmeldung (NDB-DF).

Kernmechanismus: Inverse-Wahrscheinlichkeits-Gewichtung (IPW)

Die zentrale Innovation ist die Integration eines Inverse-Wahrscheinlichkeits-Gewichtungsmechanismus (IPW) direkt in die Verlustfunktion.

• Gewichtungsstrategie: Für eine Feedback-Instanz $y_s$, die in Runde $t$ beobachtet wird (wobei $s < t$), weist der Algorithmus ein Gewicht $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$ zu.
• Unverzerrte Korrektur: Durch Skalierung des Beitrags beobachteten Feedbacks mit $1/\rho$ wird der erwartete Gradient des Surrogatverlusts zu einem unverzerrten Schätzer des wahren Gradienten. Dies neutralisiert effektiv die Verzerrung, die durch den stochastischen Beobachtungsmechanismus und fehlende Daten eingeführt wird.

Algorithmus 1: LDB-DF (Lineares Setting)

• Modell: Geht von einer linearen Belohnungsfunktion $f(x) = \theta^\top \phi(x)$ aus.
• Schätzung: Minimiert einen IPW-regulierten logistischen Verlust unter Verwendung nur des „eingetroffenen" Feedbacks.
• Exploration: Nutzt eine Upper-Confidence-Bound (UCB)-Strategie. Der erste Arm wird gierig basierend auf der aktuellen Schätzung $\theta_t$ ausgewählt. Der zweite Arm wird so ausgewählt, dass die UCB der Präferenzdifferenz relativ zum ersten Arm maximiert wird, wobei ein Konfidenzradius $\beta_t$ integriert wird, der sowohl stochastisches Rauschen als auch durch Verzögerungen verursachte Unsicherheit berücksichtigt.
• Informationsmatrix: Wird sofort unter Verwendung der Merkmalsvektoren der ausgewählten Paare aktualisiert, unabhängig von der Feedback-Latenz.

Algorithmus 2: NDB-DF (Neuronales Setting)

• Modell: Approximiert die nichtlineare Belohnungsfunktion mittels eines vollvernetzten neuronalen Netzwerks $h(x; \theta)$ mit ReLU-Aktivierungen.
• Schätzung: Trainiert das Netzwerk online unter Verwendung desselben IPW-gewichteten Kreuzentropieverlusts und lernt nur aus dem Teil des Feedbacks, der innerhalb des gültigen Fensters eingetroffen ist.
• Theoretischer Rahmen: Die Analyse erfolgt im Regime des Neural Tangent Kernel (NTK). Der Algorithmus geht davon aus, dass das Netzwerk hinreichend breit ($m$) ist, sodass es sich bei der Initialisierung im Gradienten-Merkmalsraum annähernd wie eine lineare Funktion verhält.
• Exploration: Ähnlich wie im linearen Fall wird eine UCB-Strategie eingesetzt. Der Explorationsbonus wird aus dem NTK-Merkmalsraum abgeleitet und quantifiziert die epistemische Unsicherheit in der Präferenzdifferenz.

3. Theoretische Beiträge

Die Arbeit liefert strenge Regret-Schranken für beide Settings und charakterisiert explizit den Einfluss der Verzögerungsparameter ($M$ und $\rho$).

• Lineare Regret-Schranke: Die kumulative Regret für LDB-DF wird als $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$ etabliert.

  • Der Term $\frac{M}{\rho}$ wirkt als multiplikativer Strafzusatz. Eine kleinere Beobachtungswahrscheinlichkeit $\rho$ (weniger Stichproben) und ein größerer Schwellenwert $M$ (längere potenzielle Verzögerungen) erhöhen die Regret linear.
  • Wenn $\rho=1$ und $M=1$ (keine Verzögerung), stellt die Schranke den State-of-the-Art-Wert $\tilde{O}(d\sqrt{T})$ für Standard-lineare duellierende Banditen wieder her.

• Neuronale Regret-Schranke: Die kumulative Regret für NDB-DF wird als $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$ etabliert, wobei $\tilde{d}$ die effektive Dimension der NTK-Matrix ist.

  • Der Beweis stützt sich auf eine neuartige „Addieren-und-Subtrahieren"-Zerlegungstechnik, um Martingal-Rauschen von systematischer Verzerrung zu trennen, die durch Verzögerungen induziert wird.
  • Die Analyse bestätigt, dass die fundamentale Härte des Problems (Abwägung zwischen Beobachtungswahrscheinlichkeit und Verzögerungsausmaß) auch bei komplexen nichtlinearen Funktionsapproximatoren bestehen bleibt.

4. Experimentelle Ergebnisse

Die Autoren bewerten LDB-DF und NDB-DF gegenüber Baselines, die entweder Verzögerungen ignorieren oder heuristische Imputation verwenden.

• Baselines:
  • Ignore: Verwendet dieselbe Modellarchitektur, verwirft aber ausstehendes Feedback bis zum Eintreffen ohne Gewichtung.
  • Heuristic: Imputiert fehlendes Feedback unter Verwendung der vom aktuellen Modell vorhergesagten Präferenz (verzerrter Proxy).
• Datensätze:
  • Synthetisch: Lineare, quadratische und kubische Belohnungsfunktionen mit stochastischen geometrischen Verzögerungen.
  • Realwelt: Automatisierte Prompt-Optimierung unter Verwendung des InstructZero-Benchmarks (29 Aufgaben zur Instruktion-Induktion).
• Ergebnisse:
  • Beide vorgeschlagenen Algorithmen übertreffen die Baselines in Bezug auf die kumulative Regret signifikant.
  • In nichtlinearen Settings konvergiert die Heuristic-Baseline oft aufgrund sich selbst verstärkender Vorhersagefehler (Halluzinationen) in suboptimale Regionen, während die Ignore-Baseline unter Datenknappheit leidet.
  • LDB-DF und NDB-DF demonstrieren Robustheit gegenüber Feedback-Latenz und navigieren den Suchraum in Prompt-Optimierungsaufgaben effektiv.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, eine kritische Lücke im präferenzbasierten Lernen zu schließen, indem sie das erste einheitliche Framework bereitstellt, das gleichzeitig folgende Aspekte handhabt:

1. Präferenzfeedback (Duellierend): Binäre relative Ergebnisse statt absoluter Belohnungen.
2. Nichtlineare Approximation (Neural): Komplexe Belohnungslandschaften durch neuronale Netzwerke.
3. Stochastische Verzögerungen/Fehlende Daten: Realistische Feedback-Latenz und Zensur.

Die Autoren betonen, dass ihr Ansatz von heuristischer Imputation abweicht und eine prinzipielle, unverzerrte Lösung via IPW bietet. Die theoretische Analyse etabliert die ersten Regret-Schranken für dieses spezifische Setting und zeigt, dass die Leistungsverschlechterung vorhersehbar ist und linear von den Verzögerungseigenschaften ($M/\rho$) abhängt. Die Arbeit wird als fundamentaler Schritt zur Verbesserung des asynchronen präferenzbasierten Lernens in Human-in-the-Loop-Systemen positioniert, insbesondere für LLM-Ausrichtung und Prompt-Optimierung.