Riepilogo Tecnico: Dueling Bandits Lineari e Neurali con Feedback Ritardato

1. Definizione del Problema

Il documento affronta il problema dei Contextual Dueling Bandits (CDB) in condizioni di Feedback Ritardato Stocastico. Nei contesti CDB standard, un agente seleziona una coppia di bracci (candidati) e riceve un feedback binario immediato sulla preferenza (ad esempio, $x_1 \succ x_2$) per apprendere una funzione di ricompensa latente. Tuttavia, in applicazioni reali come l'allineamento dei Modelli Linguistici di Grande Dimensione (LLM), l'ottimizzazione dei prompt e la pubblicità display, il feedback è spesso asincrono.

Il contesto specifico formalizzato in questo lavoro assume:

• Ritardi Stocastici: Il feedback per un'azione intrapresa al round $s$ arriva dopo un ritardo casuale $D_s$.
• Soglia Rigida: Esiste una finestra di osservazione massima $M$. Se $D_s > M$, il feedback è trattato come mancante (censurato).
• Probabilità di Osservazione: La probabilità che il feedback arrivi entro la finestra è $\rho = P(D_s \le M)$.
• Sfida del Bias: A differenza dei bandit lineari, dove gli stimatori hanno soluzioni in forma chiusa (ad esempio, regressione ridge), i dueling bandits si basano sulla Massima Verosimiglianza (MLE) sotto il modello Bradley-Terry-Luce (BTL). Questa mancanza di soluzioni in forma chiusa significa che adattamenti ingenui delle tecniche standard per feedback ritardati (come l'imputazione semplice o l'ignorare i dati mancanti) introducono un bias sistematico che non può essere facilmente limitato o corretto.

2. Metodologia

Gli autori propongono due nuovi algoritmi progettati per gestire questi ritardi senza imputazione euristica: Linear Dueling Bandits with Delayed Feedback (LDB-DF) e Neural Dueling Bandits with Delayed Feedback (NDB-DF).

Meccanismo Principale: Ponderazione Inversa della Probabilità (IPW)

L'innovazione centrale è l'integrazione di un meccanismo di Ponderazione Inversa della Probabilità (IPW) direttamente nella funzione di perdita.

• Strategia di Ponderazione: Per un'istanza di feedback $y_s$ osservata al round $t$ (dove $s < t$), l'algoritmo assegna un peso $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$.
• Correzione Non Distorta: Scalando il contributo del feedback osservato per $1/\rho$, il gradiente atteso della perdita surrogata diventa uno stimatore non distorto del gradiente vero, neutralizzando efficacemente il bias introdotto dal meccanismo di osservazione stocastico e dai dati mancanti.

Algoritmo 1: LDB-DF (Impostazione Lineare)

• Modello: Assume una funzione di ricompensa lineare $f(x) = \theta^\top \phi(x)$.
• Stima: Minimizza una perdita logistica regolarizzata con IPW utilizzando solo il feedback "arrivato".
• Esplorazione: Utilizza una strategia Upper Confidence Bound (UCB). Il primo braccio è selezionato in modo greedy in base alla stima corrente $\theta_t$. Il secondo braccio è selezionato per massimizzare il UCB della differenza di preferenza rispetto al primo braccio, incorporando un raggio di confidenza $\beta_t$ che tiene conto sia del rumore stocastico che dell'incertezza indotta dai ritardi.
• Matrice delle Informazioni: Aggiornata immediatamente utilizzando i vettori di caratteristica delle coppie selezionate, indipendentemente dalla latenza del feedback.

Algoritmo 2: NDB-DF (Impostazione Neurale)

• Modello: Approssima la funzione di ricompensa non lineare utilizzando una rete neurale completamente connessa $h(x; \theta)$ con attivazioni ReLU.
• Stima: Addestra la rete online utilizzando la stessa perdita di entropia incrociata ponderata con IPW, apprendendo solo dal sottoinsieme di feedback che è arrivato entro la finestra valida.
• Quadro Teorico: L'analisi è condotta nel regime del Neural Tangent Kernel (NTK). L'algoritmo assume che la rete sia sufficientemente larga ($m$) da comportarsi approssimativamente come una funzione lineare nello spazio delle caratteristiche del gradiente all'inizializzazione.
• Esplorazione: Simile al caso lineare, impiega una strategia UCB. Il bonus di esplorazione è derivato dallo spazio delle caratteristiche NTK, quantificando l'incertezza epistemica nella differenza di preferenza.

3. Contributi Teorici

Il documento fornisce limiti di rimpianto rigorosi per entrambe le impostazioni, caratterizzando esplicitamente l'impatto dei parametri di ritardo ($M$ e $\rho$).

• Limite di Rimpianto Lineare: Il rimpianto cumulativo per LDB-DF è stabilito come $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$.

  • Il termine $\frac{M}{\rho}$ agisce come una penalità moltiplicativa. Una probabilità di osservazione $\rho$ più piccola (meno campioni) e una soglia $M$ più grande (ritardi potenziali più lunghi) aumentano linearmente il rimpianto.
  • Quando $\rho=1$ e $M=1$ (nessun ritardo), il limite recupera lo stato dell'arte $\tilde{O}(d\sqrt{T})$ per i dueling bandit lineari standard.

• Limite di Rimpianto Neurale: Il rimpianto cumulativo per NDB-DF è stabilito come $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$, dove $\tilde{d}$ è la dimensione effettiva della matrice NTK.

  • La prova si basa su una nuova tecnica di decomposizione "aggiungi e sottrai" per separare il rumore delle martingale dal bias sistematico indotto dai ritardi.
  • L'analisi conferma che la difficoltà fondamentale del problema (compromesso tra probabilità di osservazione e magnitudine del ritardo) persiste anche con complessi approssimatori di funzioni non lineari.

4. Risultati Sperimentali

Gli autori valutano LDB-DF e NDB-DF rispetto a baseline che ignorano i ritardi o utilizzano imputazione euristica.

• Baseline:
  • Ignora: Utilizza la stessa architettura del modello ma scarta il feedback in sospeso fino all'arrivo senza ponderazione.
  • Euristica: Imputa il feedback mancante utilizzando la preferenza prevista dal modello corrente (proxy distorto).
• Dataset:
  • Sintetici: Funzioni di ricompensa lineari, quadratiche e cubiche con ritardi geometrici stocastici.
  • Reali: Ottimizzazione automatizzata dei prompt utilizzando il benchmark InstructZero (29 task di induzione di istruzioni).
• Risultati:
  • Entrambi gli algoritmi proposti superano significativamente le baseline in termini di rimpianto cumulativo.
  • In contesti non lineari, la baseline Euristica spesso converge verso regioni subottimali a causa di errori di previsione auto-rinforzanti (allucinazioni), mentre la baseline Ignora soffre di scarsità di dati.
  • LDB-DF e NDB-DF dimostrano robustezza alla latenza del feedback, navigando efficacemente nello spazio di ricerca nei task di ottimizzazione dei prompt.

5. Significato e Affermazioni

Il documento afferma di colmare un divario critico nell'apprendimento basato sulle preferenze fornendo il primo quadro unificato che gestisce simultaneamente:

1. Feedback di Preferenza (Dueling): Risultati relativi binari anziché ricompense assolute.
2. Approssimazione Non Lineare (Neurale): Paesaggi di ricompensa complessi tramite reti neurali.
3. Ritardi Stocastici/Dati Mancanti: Latenza e censura del feedback realistiche.

Gli autori sottolineano che il loro approccio si discosta dall'imputazione euristica, offrendo una soluzione principiale e non distorta tramite IPW. L'analisi teorica stabilisce i primi limiti di rimpianto per questa specifica impostazione, dimostrando che il degrado delle prestazioni è prevedibile e dipende linearmente dalle caratteristiche del ritardo ($M/\rho$). Il lavoro è posizionato come un passo fondazionale per migliorare l'apprendimento asincrono basato sulle preferenze nei sistemi con intervento umano, in particolare per l'allineamento degli LLM e l'ottimizzazione dei prompt.