Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards

1. Il Problema

Il problema affrontato riguarda il Multi-Armed Bandit (MAB), un framework fondamentale per il processo decisionale sequenziale sotto incertezza. Nella configurazione classica, un decisore deve bilanciare l'esplorazione (provare azioni diverse per stimarne i ricavi) e lo sfruttamento (scegliere l'azione attualmente migliore) basandosi esclusivamente sui dati raccolti online durante l'esecuzione.

Tuttavia, in molti scenari pratici (es. trial clinici, raccomandazione di contenuti, selezione di modelli di linguaggio), esistono dati ausiliari offline ricchi (come le caratteristiche degli utenti o i parametri storici) disponibili prima di iniziare l'interazione online.
Il paper introduce un nuovo setting in cui:

• Si utilizzano modelli di Machine Learning (ML) pre-addestrati per convertire queste informazioni offline in ricompense surrogate ($\hat{R}$).
• Le ricompense surrogate sono correlate con le vere ricompense ($R$), ma possono essere fortemente distorte (bias) e non preservare necessariamente il ranking delle azioni ottimali.
• L'obiettivo è sfruttare la correlazione tra ricompense vere e surrogate per ridurre la varianza degli stimatori, anche in presenza di un bias arbitrario, senza richiedere la conoscenza a priori della matrice di covarianza o del bias stesso.

2. Metodologia: L'algoritmo MLA-UCB

Gli autori propongono l'algoritmo MLA-UCB (Machine Learning-Assisted Upper Confidence Bound). La metodologia si basa su tre pilastri principali:

A. Stimatore della media assistito da ML

Invece di utilizzare semplicemente la media campionaria delle ricompense vere, l'algoritmo costruisce uno stimatore che corregge la media osservata online utilizzando la differenza tra le ricompense surrogate online e quelle offline.
Lo stimatore $\hat{\mu}^{MLA}_{k,n}$ è definito come:
$$\hat{\mu}^{MLA}_{k,n} = \bar{R}_{k,n} - \hat{\lambda}_{k,n} (\bar{\hat{R}}_{k,n} - \bar{\hat{R}}^{off}_{k})$$
Dove:

• $\bar{R}_{k,n}$ è la media delle ricompense vere online.
• $\bar{\hat{R}}_{k,n}$ e $\bar{\hat{R}}^{off}_{k}$ sono le medie delle ricompense surrogate (online e offline).
• $\hat{\lambda}_{k,n}$ è un coefficiente stimato che minimizza la varianza (equivalente al coefficiente angolare in una regressione OLS).

Questo approccio è ispirato alla Prediction-Powered Inference (PPI), permettendo di ridurre la varianza dello stimatore sfruttando la correlazione $\rho_k$ tra $R$ e $\hat{R}$, anche se i valori medi $\mu_k$ e $\tilde{\mu}_k$ sono arbitrariamente diversi.

B. Costruzione degli Intervalli di Confidenza

A differenza degli algoritmi UCB classici che assumono varianze note o parametri sub-Gaussiani fissi, MLA-UCB:

• Non richiede la conoscenza della varianza delle ricompense vere o surrogate.
• Utilizza una versione adattiva del test t di Student.
• Costruisce i limiti di confidenza superiori invertendo un test t con una stima della varianza specifica e un livello di significatività dipendente dal round.
• La varianza dello stimatore viene decomposta in due componenti indipendenti (basate su proprietà di ortogonalità della regressione), permettendo di derivare limiti di confidenza validi per campioni finiti.

C. Estensione a Dati Non-Gaussiani e Batched

Il framework viene esteso a scenari in cui:

• Le ricompense non seguono una distribuzione Gaussiana.
• Le decisioni vengono prese su batch di individui (es. aggiornamento prezzi per gruppi di utenti).
  In questo caso, l'algoritmo sfrutta il Teorema del Limite Centrale e i limiti di deviazione moderata auto-normalizzati (self-normalized moderate deviation bounds) per garantire la validità degli intervalli di confidenza anche con distribuzioni generali, purché i batch siano sufficientemente grandi.

3. Contributi Chiave

1. Nuovo Setting MAB: Formalizzazione del problema MAB con ricompense surrogate generate da ML, che possono essere distorte ma correlate.
2. Algoritmo MLA-UCB: Un algoritmo che integra dati offline e online senza richiedere conoscenza del bias o della matrice di covarianza.
3. Analisi Teorica Rigorosa:
   • Derivazione di un limite superiore al regret cumulativo sotto assunzioni Gaussiane congiunte.
   • Dimostrazione che il regret migliora rispetto all'UCB classico quando la correlazione $\rho_k \neq 0$, anche se il bias è infinito.
   • Dimostrazione dell'ottimalità asintotica: il limite inferiore del regret per qualsiasi politica "uniformemente buona" corrisponde al limite superiore ottenuto da MLA-UCB.
4. Robustezza: L'algoritmo mantiene prestazioni superiori anche quando le assunzioni Gaussiane non sono soddisfatte (dati non-Gaussiani) o in setting batched.

4. Risultati

Risultati Teorici

• Riduzione del Regret: Il termine principale del limite superiore del regret per MLA-UCB è scalato da un fattore proporzionale a $(1 - \rho_k^2)$. Se la correlazione è alta, il regret si riduce drasticamente.
• Ottimalità: L'algoritmo raggiunge il limite inferiore teorico (lower bound) per problemi MAB con ricompense surrogate, confermando che non ci sono strategie migliori nella classe delle politiche uniformemente buone.
• Indipendenza dal Bias: La riduzione del regret è ottenuta attraverso la riduzione della varianza, non aggregando direttamente i dati (che sarebbe distorto). Quindi, anche se la media delle surrogate è completamente sbagliata, l'algoritmo funziona.

Risultati Sperimentali

• Simulazioni Gaussiane: Dimostrano che all'aumentare della dimensione del campione offline ($N$) e della correlazione ($\rho$), il regret di MLA-UCB converge a un limite inferiore rispetto all'UCB classico.
• Simulazioni con ML Reale: Utilizzando modelli ML reali (Regressione Lineare, SVR, Reti Neurali, Decision Tree) su dati non-Gaussiani, l'algoritmo riduce significativamente il regret rispetto all'UCB, anche quando i modelli ML hanno prestazioni variabili.
• Studi di Caso Reali:
  • Selezione di Modelli Linguistici (LLM): Utilizzando modelli open-source come surrogate per modelli proprietari costosi, MLA-UCB ha identificato più rapidamente il modello migliore riducendo il regret.
  • Raccomandazione Video: Su un dataset reale (KuaiRec), l'uso di predizioni ML basate su caratteristiche utente ha migliorato l'engagement rispetto alle strategie standard.

5. Significato e Impatto

Questo lavoro è significativo perché colma il divario tra l'uso di grandi modelli di ML (che generano predizioni abbondanti ma potenzialmente distorte) e la necessità di prendere decisioni sequenziali ottimali in scenari con dati reali limitati.

• Efficienza dei Costi: Permette di ridurre drasticamente il numero di interazioni online costose (es. test clinici, click su annunci, chiamate API a LLM costosi) sfruttando dati storici o simulazioni economiche.
• Robustezza Pratica: A differenza di metodi precedenti che richiedono assunzioni rigide sul bias o sulla conoscenza della distribuzione, MLA-UCB è robusto e non richiede parametri di calibrazione complessi.
• Generalità: L'approccio è applicabile a qualsiasi modello di predizione e qualsiasi forma di dati ausiliari, rendendolo uno strumento versatile per l'industria e la ricerca operativa.

In sintesi, il paper dimostra che l'integrazione intelligente di predizioni ML (surrogate) nei processi di esplorazione-sfruttamento può portare a guadagni di efficienza sostanziali, trasformando dati "rumorosi" o distorti in un asset prezioso per l'ottimizzazione decisionale.