Technische Samenvatting: Lineaire en Neuronale Dueling Bandits met Uitgestelde Feedback

1. Probleemdefinitie

Het artikel behandelt het probleem van Contextuele Dueling Bandits (CDB) onder Stochastische Uitgestelde Feedback. In standaard CDB-situaties kiest een agent een paar armen (kandidaten) en ontvangt onmiddellijke binaire voorkeursfeedback (bijvoorbeeld $x_1 \succ x_2$) om een latente beloningsfunctie te leren. Echter, in real-world toepassingen zoals het afstemmen van Large Language Models (LLM), prompt-optimalisatie en display-advertenties, is feedback vaak asynchroon.

De specifieke situatie die in dit werk wordt geformaliseerd, gaat uit van:

• Stochastische Vertragingen: Feedback voor een actie die in ronde $s$ is ondernomen, arriveert na een willekeurige vertraging $D_s$.
• Harde Drempel: Er is een maximum waarnemingsvenster $M$. Als $D_s > M$, wordt de feedback behandeld als ontbrekend (gecensureerd).
• Waarnemingskansen: De kans dat feedback binnen het venster arriveert, is $\rho = P(D_s \le M)$.
• Bias-uitdaging: In tegenstelling tot lineaire bandits, waar schatters gesloten-formule oplossingen hebben (bijvoorbeeld ridge-regressie), vertrouwen dueling bandits op Maximum Likelihood Schatting (MLE) onder het Bradley-Terry-Luce (BTL)-model. Dit gebrek aan gesloten-formule oplossingen betekent dat naïeve aanpassingen van standaard technieken voor uitgestelde feedback (zoals eenvoudige imputatie of het negeren van ontbrekende data) systematische bias introduceren die niet eenvoudig kan worden begrensd of gecorrigeerd.

2. Methodologie

De auteurs stellen twee nieuwe algoritmen voor die zijn ontworpen om deze vertragingen aan te pakken zonder heuristische imputatie: Lineaire Dueling Bandits met Uitgestelde Feedback (LDB-DF) en Neuronale Dueling Bandits met Uitgestelde Feedback (NDB-DF).

Kernmechanisme: Inverse Probability Weighting (IPW)

De centrale innovatie is de integratie van een Inverse Probability Weighting (IPW)-mechanisme direct in de verliesfunctie.

• Weegstrategie: Voor een feedbackinstantie $y_s$ die in ronde $t$ wordt waargenomen (waarbij $s < t$), wijst het algoritme een gewicht toe $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$.
• Ongewogen Correctie: Door de bijdrage van waargenomen feedback te schalen met $1/\rho$, wordt de verwachte gradiënt van de surrogaatverliesfunctie een ongewogen schatter van de ware gradiënt, waardoor de bias die wordt geïntroduceerd door het stochastische waarnemingsmechanisme en ontbrekende data effectief wordt geneutraliseerd.

Algoritme 1: LDB-DF (Lineaire Situatie)

• Model: Gaat uit van een lineaire beloningsfunctie $f(x) = \theta^\top \phi(x)$.
• Schatting: Minimaliseert een IPW-geregulariseerde logistieke verliesfunctie met uitsluitend "aangekomen" feedback.
• Exploratie: Gebruikt een Upper Confidence Bound (UCB)-strategie. De eerste arm wordt gulzig geselecteerd op basis van de huidige schatting $\theta_t$. De tweede arm wordt geselecteerd om de UCB van het voorkeursverschil ten opzichte van de eerste arm te maximaliseren, waarbij een betrouwbaarheidsstraal $\beta_t$ wordt opgenomen die rekening houdt met zowel stochastische ruis als door vertraging veroorzaakte onzekerheid.
• Informatiematrix: Wordt direct bijgewerkt met gebruik van feature-vectoren van geselecteerde paren, onafhankelijk van de feedbacklatentie.

Algoritme 2: NDB-DF (Neuronale Situatie)

• Model: Benadert de niet-lineaire beloningsfunctie met een volledig verbonden neurale netwerk $h(x; \theta)$ met ReLU-activaties.
• Schatting: Traint het netwerk online met dezelfde IPW-gewogen cross-entropy-verliesfunctie, leertend uitsluitend van het subset van feedback dat binnen het geldige venster is aangekomen.
• Theoretisch Kader: De analyse wordt uitgevoerd in het Neural Tangent Kernel (NTK)-regime. Het algoritme gaat ervan uit dat het netwerk voldoende breed is ($m$) zodat het zich bij initialisatie ongeveer als een lineaire functie gedraagt in de gradiënt-featurespace.
• Exploratie: Net als in het lineaire geval wordt een UCB-strategie toegepast. De exploratiebonus is afgeleid van de NTK-featurespace en kwantificeert epistemische onzekerheid in het voorkeursverschil.

3. Theoretische Bijdragen

Het artikel biedt rigoureuze regret-grenzen voor beide situaties, waarbij expliciet het effect van vertragingparameters ($M$ en $\rho$) wordt gekarakteriseerd.

• Lineaire Regret-Grens: De cumulatieve regret voor LDB-DF is vastgesteld als $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$.

  • De term $\frac{M}{\rho}$ fungeert als een multiplicatieve straf. Een kleinere waarnemingskans $\rho$ (minder steekproeven) en een hogere drempel $M$ (langere potentiële vertragingen) verhogen de regret lineair.
  • Wanneer $\rho=1$ en $M=1$ (geen vertraging), herstelt de grens de state-of-the-art $\tilde{O}(d\sqrt{T})$ voor standaard lineaire dueling bandits.

• Neuronale Regret-Grens: De cumulatieve regret voor NDB-DF is vastgesteld als $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$, waarbij $\tilde{d}$ de effectieve dimensie van de NTK-matrix is.

  • Het bewijs maakt gebruik van een nieuwe "optellen-en-aftrekken"-decompositietechniek om martingale-ruis te scheiden van systematische bias die door vertragingen wordt veroorzaakt.
  • De analyse bevestigt dat de fundamentele moeilijkheid van het probleem (de afweging tussen waarnemingskans en omvang van de vertraging) behouden blijft, zelfs met complexe niet-lineaire functiebenaderingen.

4. Experimentele Resultaten

De auteurs evalueren LDB-DF en NDB-DF tegen baselines die vertragingen negeren of heuristische imputatie gebruiken.

• Baselines:
  • Negeren: Gebruikt dezelfde modelarchitectuur maar verwijdert aanstaande feedback tot aankomst zonder weging.
  • Heuristisch: Imputeert ontbrekende feedback met de voorspelde voorkeur van het huidige model (gewaardeerde proxy).
• Datasets:
  • Synthetisch: Lineaire, kwadratische en kubische beloningsfuncties met stochastische geometrische vertragingen.
  • Real-world: Geautomatiseerde Prompt-optimalisatie met behulp van de InstructZero-benchmark (29 instructie-inductietaken).
• Vondsten:
  • Beide voorgestelde algoritmen presteren significant beter dan baselines op het gebied van cumulatieve regret.
  • In niet-lineaire situaties convergeert de Heuristische baseline vaak naar suboptimale gebieden door zelfversterkende voorspellingsfouten (hallucinaties), terwijl de Negeren-baseline lijdt aan data-schaarste.
  • LDB-DF en NDB-DF tonen robuustheid tegen feedbacklatentie en navigeren effectief door de zoekruimte in prompt-optimalisatietaken.

5. Betekenis en Claims

Het artikel claimt een kritieke kloof in voorkeurgebaseerd leren te overbruggen door het eerste unified framework te bieden dat gelijktijdig omgaat met:

1. Voorkeursfeedback (Dueling): Binaire relatieve uitkomsten in plaats van absolute beloningen.
2. Niet-lineaire Benadering (Neuraal): Complexe beloningslandschappen via neurale netwerken.
3. Stochastische Vertragingen/Ontbrekende Data: Realistische feedbacklatentie en censurering.

De auteurs benadrukken dat hun aanpak afwijkt van heuristische imputatie en een principiële, ongewogen oplossing biedt via IPW. De theoretische analyse vestigt de eerste regret-grenzen voor deze specifieke situatie, en toont aan dat de prestatiedegradeer voorspelbaar is en lineair afhankelijk is van de vertragingseigenschappen ($M/\rho$). Het werk wordt gepositioneerd als een fundamentele stap voor het verbeteren van asynchroon voorkeurleren in systemen met menselijke tussenkomst, met name voor LLM-afstemming en prompt-optimalisatie.