Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards

Titel: Multi-Armed Bandits met door Machine Learning gegenereerde Surrogaatbeloningen

Auteurs: Wenlong Ji, Yihan Pan, Ruihao Zhu, en Lihua Lei (Stanford, Northwestern, Cornell)
Datum: April 2026 (voorspeld/publicatie datum in paper)

1. Probleemstelling

Het Multi-Armed Bandit (MAB) probleem is een raamwerk voor sequentiële besluitvorming onder onzekerheid, waarbij een beslisser moet kiezen tussen verschillende acties ("armen") om de cumulatieve beloning te maximaliseren of de spijt (regret) te minimaliseren.

• Huidige beperking: Traditionele MAB-algoritmen (zoals UCB en Thompson Sampling) vertrouwen uitsluitend op online data die tijdens het proces wordt verzameld. Dit leidt vaak tot een tekort aan data in de vroege fasen, wat resulteert in hoge spijt.
• De uitdaging: In veel praktische scenario's (bijv. klinische proeven, aanbevelingssystemen) is er rijke offline data beschikbaar (bijv. gebruikerscovariaten, historische records) voordat de online fase begint.
• Het dilemma: Men kan Machine Learning (ML) modellen gebruiken om deze offline data om te zetten in surrogaatbeloningen (voorspellingen). Echter, deze voorspellingen zijn vaak bevooroordeeld (biased) en kunnen de rangschikking van de echte beloningen verkeerd voorspellen, vooral omdat ze vaak moeten extrapoleren naar nieuwe omgevingen die niet in de historische data voorkomen.
• De kernvraag: Hoe kunnen we deze ML-gegenereerde surrogaatbeloningen gebruiken om de prestaties van een bandit-algoritme te verbeteren, zelfs als de voorspellingen systematisch fout zijn (gecorreleerd met de echte beloning, maar met een willekeurige bias), zonder dat we de exacte bias of covariantie kennen?

2. Methodologie: MLA-UCB

De auteurs introduceren een nieuw setting en een nieuw algoritme genaamd Machine Learning-Assisted Upper Confidence Bound (MLA-UCB).

Het Setting

• Offline Fase: Er is een statische pool van surrogaatbeloningen $\{\hat{R}^{off}_{k,s}\}$ beschikbaar voor elke arm $k$, gegenereerd door een ML-model op basis van kenmerken.
• Online Fase: Bij het trekken van een arm $k$ observeert de beslisser zowel de ware beloning $R_{k,s}$ als de surrogaatbeloning $\hat{R}_{k,s}$ (gegenereerd door hetzelfde ML-model).
• Aannames: De ware en surrogaatbeloningen zijn bivariate Gaussisch verdeeld met onbekende middelen en een onbekende covariantiematrix. De middelen kunnen willekeurig verschillen (grote bias), maar er is een correlatie $\rho_k$ tussen de voorspelling en de werkelijkheid.

Het Algoritme (MLA-UCB)

Het algoritme combineert online data met offline data via een debiasing techniek gebaseerd op Prediction-Powered Inference (PPI).

1. Schatter voor de gemiddelde beloning:
   In plaats van alleen het steekproefgemiddelde van de online data te gebruiken, schat MLA-UCB het gemiddelde $\mu_k$ als volgt:
   $$\hat{\mu}^{MLA}_{k,n} = \bar{R}_{k,n} - \hat{\lambda}_{k,n} (\bar{\hat{R}}_{k,n} - \bar{\hat{R}}^{off}_{k})$$
   Waarbij:

   • $\bar{R}_{k,n}$: Gemiddelde van online ware beloningen.
   • $\bar{\hat{R}}_{k,n}$: Gemiddelde van online surrogaatbeloningen.
   • $\bar{\hat{R}}^{off}_{k}$: Gemiddelde van offline surrogaatbeloningen.
   • $\hat{\lambda}_{k,n}$: Een schatter voor de regressiecoëfficiënt (verhouding van covariantie tot variantie).

   Deze formule corrigeert de bias van de offline data door het verschil tussen online en offline surrogaatgemiddelden te gebruiken als een schatting van de bias, gewogen door de correlatie.

2. Vertrouwensgrenzen (Confidence Bounds):
   Het algoritme bouwt een bovengrens op door een t-test om te keren.

   • Het gebruikt een unieke variantie-schatting die rekening houdt met de onzekerheid in de regressiecoëfficiënt.
   • Het is variantie-agnostisch: Het vereist geen vooraf kennis van de variantie van de beloningen of de covariantie tussen ware en surrogaatbeloningen.
   • De bovengrens wordt berekend als: $\hat{\mu}^{MLA}_{k,n} + \text{UCB-term}$. De UCB-term bevat een schaalfactor gebaseerd op de t-verdeling en een term die de variantiereductie door de correlatie weerspiegelt.

3. Batched Uitbreiding:
   Voor scenario's waar beslissingen in batches worden toegepast (bijv. prijsaanpassingen voor groepen gebruikers) en de data niet-Gaussisch is, gebruiken de auteurs zelf-genormaliseerde matige afwijkingen (self-normalized moderate deviation bounds). Dit zorgt voor geldige betrouwbaarheidsintervallen zonder strikte Gaussische aannames.

3. Belangrijkste Bijdragen

1. Nieuw Framework: Definities van MAB met ML-gegenereerde surrogaatbeloningen die zowel offline als online beschikbaar zijn, waarbij de bias onbekend en willekeurig groot mag zijn.
2. MLA-UCB Algoritme: Een algoritme dat PPI-methoden integreert in bandits. Het vereist geen kennis van de bias of de covariantiematrix, maar levert wel verbeteringen op zolang er enige correlatie ($\rho_k \neq 0$) is.
3. Theoretische Optimaliteit:
   • Onder Gaussische aannames wordt een spijtbegrens (regret upper bound) afgeleid die strikt beter is dan die van klassieke UCB-algoritmen.
   • De leidende term van de spijt wordt gereduceerd met een factor $(1 - \rho_k^2)$.
   • Er wordt een spijtondergrens (regret lower bound) bewezen die aantoont dat MLA-UCB asymptotisch optimaal is voor een brede klasse van beleid, zelfs met een poly-logaritmische offline steekproefgrootte.
4. Robuustheid: Het algoritme werkt ook voor niet-Gaussische data en batched settings, met bewezen spijtreductie.
5. Empirische Validatie: Uitgebreide simulaties en echte wereldtoepassingen tonen aan dat het algoritme consistent minder spijt genereert dan klassieke UCB, zelfs bij sterke bias.

4. Resultaten

• Theoretische Resultaten:
  • Als $\rho_k \to 1$, wordt de spijt verwaarloosbaar (effectief alsof er extra online observaties zijn).
  • Als $\rho_k = 0$, presteert het algoritme even goed als de beste klassieke UCB (geen schade door het gebruik van nutteloze surrogaatdata).
  • De spijtreductie is evenredig met $(1 - \rho_k^2)$, wat betekent dat zelfs een zwakke correlatie leidt tot significante verbeteringen.
• Simulaties:
  • In Gaussische settings neemt de cumulatieve spijt af naarmate de offline steekproefgrootte ($N$) en de correlatie ($\rho$) toenemen.
  • In niet-Gaussische settings (gegenereerd door LLMs, SVR, Neuronale Netwerken, Beslissingsbomen) blijft de verbetering behouden, hoewel de theorie strikt genomen alleen voor Gaussische data is bewezen.
• Echte Wereld Toepassingen:
  1. Selectie van Taalmodellen (LLMs): Het kiezen van de beste proprietary LLM voor een taak, waarbij open-source modellen als surrogaat dienen. MLA-UCB vond sneller de beste modellen dan UCB.
  2. Video-aanbeveling: Het maximaliseren van kijkduur op een platform. Een model getraind op historische data diende als surrogaat. Ondanks bias in de voorspellingen, leidde MLA-UCB tot een lagere spijt.

5. Significantie en Impact

Dit paper is significant omdat het een brug slaat tussen Machine Learning en Sequential Decision Making op een manier die tot nu toe theoretisch onoplosbaar leek vanwege de bias in ML-voorspellingen.

• Praktische relevantie: Het lost het probleem op dat organisaties vaak veel historische data hebben maar geen directe beloningen kunnen meten voor nieuwe opties. Het maakt het mogelijk om deze "gratis" voorspellingen te gebruiken zonder het risico van slechte prestaties.
• Theoretische doorbraak: Het toont aan dat je geen perfecte voorspellingen nodig hebt om bandit-problemen te verbeteren; zelfs bevooroordeelde maar gecorreleerde voorspellingen kunnen de variantie van schatters drastisch verlagen en zo de exploratie-efficiëntie verhogen.
• Toekomstperspectief: De methode is breed toepasbaar, van klinische proeven (waar lange-termijn uitkomsten worden gesurrogeerd door korte-termijn markers) tot marketing en aanbevelingssystemen. De auteurs wijzen erop dat dit ook uitbreidbaar is naar contextuele bandits.

Kortom, MLA-UCB biedt een robuust, theoretisch onderbouwd en praktisch bewezen middel om de "koude start" van bandit-algoritmen te overwinnen door slim gebruik te maken van ML-voorspellingen, zelfs wanneer die voorspellingen imperfect zijn.