An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Sintesi Tecnica: Un Algoritmo Migliorato per i Bandit Contestuali Lineari Avversariali tramite Riduzione

Definizione del Problema

Il documento affronta il problema dei bandit contestuali lineari avversariali. In questo scenario, un avversario oblivo seleziona una sequenza di vettori di perdita nascosti $\theta_t \in \mathbb{R}^d$ prima dell'inizio dell'interazione. In ogni round $t$, un insieme di azioni $A_t \subset \mathbb{R}^d$ viene estratto i.i.d. da una distribuzione $\mathcal{D}$ fissa ma ignota e rivelato all'apprendista (learner). L'apprendista deve selezionare un'azione $a_t \in A_t$ e subisce una perdita $\ell_t$ con aspettativa $\mathbb{E}[\ell_t] = a_t^\top \theta_t$. L'obiettivo è minimizzare il regret rispetto alla migliore politica fissa $\pi$, dove una politica mappa qualsiasi insieme di azioni osservato $A$ in un punto del suo inviluppo convesso $\text{conv}(A)$.

Questo scenario generalizza i classici bandit lineari permettendo agli insiemi di azioni (contesti) di variare stocasticamente nel tempo, mentre le perdite rimangono avversariali. Una sfida critica è che la distribuzione $\mathcal{D}$ è ignota e l'apprendista non ha accesso a un simulatore che possa generare campioni gratuiti da $\mathcal{D}$. Inoltre, il numero di possibili azioni $K$ può essere esponenzialmente grande rispetto alla dimensione $d$ (ad esempio, in problemi combinatori come il cammino minimo), rendendo impraticabili gli algoritmi con complessità polinomiale in $K$.

Metodologia

Il contributo principale è una riduzione computazionalmente efficiente che trasforma il problema dei bandit contestuali lineari avversariali in un problema di bandit lineari avversariali robusto alla misspecificazione con un insieme di azioni fisso.

1. Riduzione a Insiemi di Azioni Fissi:
   Gli autori definiscono una mappatura $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$, che mappa una politica $\pi$ alla sua azione media. Poiché $\mathcal{D}$ è ignota, il vero insieme di azioni medie $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$ non può essere accessibile direttamente. Invece, l'algoritmo costruisce un'approssimazione empirica $\hat{\Omega}$ utilizzando $N$ campioni i.i.d. di insiemi di azioni estratti da $\mathcal{D}$.

   • $\hat{\Omega}$ è definito come la somma di Minkowski degli inviluppi convessi degli insiemi di azioni campionati: $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$.
   • La riduzione si basa sul fatto che, per le politiche di classificatore lineare, la differenza tra la perdita attesa sulla vera distribuzione e quella sulla distribuzione empirica è piccola (convergenza uniforme), a condizione che $N$ sia sufficientemente grande.

2. Gestione della Discrepanza tramite Robustezza alla Misspecificazione:
   Poiché l'apprendista opera su $\hat{\Omega}$ anziché su $\Omega$, il feedback ricevuto dall'algoritmo sottostante del bandit lineare è "misspecified" (errato nella specifica). Nello specifico, la perdita attesa osservata dall'algoritmo del bandit lineare differisce dalla vera perdita attesa per un termine di errore limitato $\epsilon$.

   • Gli autori utilizzano un algoritmo di bandit lineare avversariale $\alpha$-misspecification-robust come black box. Questo algoritmo garantisce un basso regret anche quando il feedback soddisfa $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$.
   • Per eseguire un punto $y_t \in \hat{\Omega}$ suggerito dall'algoritmo del bandit lineare, l'apprendista utilizza una decomposizione basata su Frank-Wolfe (Algoritmo 2) per esprimere $y_t$ come una combinazione convessa di punti sul confine di $\hat{\Omega}$. Questi punti di confine corrispondono a politiche di classificatore lineare $\pi_\phi$, che possono essere eseguite utilizzando un oracolo di ottimizzazione lineare per i singoli insiemi di azioni $A_t$.

3. Componenti Algoritmiche:

   • Algoritmo 1: Il framework principale che interagisce con l'ambiente, decompone il suggerimento del bandit lineare in una miscela di politiche lineari e alimenta la perdita risultante all'algoritmo del bandit lineare.
   • Algoritmo 3 (Misspecification-Robust Continuous Exponential Weights): Un'istanza specifica dell'algoritmo del bandit lineare robusto. Adatta il metodo dei pesi esponenziali continui troncati (Ito et al., 2020) aggiungendo un "termine bonus" $b_t$ allo stimatore della perdita. Questo bonus incoraggia l'esplorazione e compensa l'overhead di regret causato dalla misspecificazione.
   • Doubling Trick: Per gestire la dimensione ottimale di campionamento $N$ sconosciuta, l'algoritmo impiega un doubling trick, riavviando il processo alle epoche $2, 4, 8, \dots$ e utilizzando tutti i campioni di contesto accumulati per raffinare $\hat{\Omega}$.

Contributi Chiave

• Algoritmo Efficiente per Oracolo: Il documento presenta il primo algoritmo per i bandit contestuali lineari avversariali con insiemi di azioni stocastici che ottiene limiti di regret indipendenti dal numero di azioni $K$ nella sua complessità computazionale. Richiede solo un oracolo di ottimizzazione lineare per i singoli insiemi di azioni in ogni round.
• Applicabilità Combinatoria: Il metodo è il primo a raggiungere un regret di $\text{poly}(d)\sqrt{T}$ in tempo polinomiale per i bandit combinatori con insiemi di azioni stocastici e perdite avversariali. Gli algoritmi precedenti richiedevano o feedback semi-bandit o avevano una complessità computazionale che scalava polinomialmente con $K$ (che è esponenziale in $d$ per molti problemi).
• Nuova Riduzione: Il lavoro stabilisce una riduzione polinomiale dai bandit contestuali lineari avversariali ai bandit lineari robusti alla misspecificazione. A differenza delle riduzioni precedenti (ad es., Hanna et al., 2023) che si concentravano su setting stocastici o mancavano di implementazioni in tempo polinomiale, questa riduzione opera sotto perdite avversariali ed è computazionalmente efficiente.

Risultati

L'algoritmo raggiunge i seguenti limiti di regret (ignorando i fattori logaritmici):

• Senza Simulatore: $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$.
  • Questo risolve una questione aperta di Liu et al. (2023) riguardante se un regret di $\text{poly}(d)\sqrt{T}$ sia ottenibile in tempo polinomiale indipendentemente da $K$.
  • La complessità computazionale è $\text{poly}(d, T)$ più $\text{poly}(d, T)$ chiamate all'oracolo di ottimizzazione lineare.
• Con Simulatore: Se l'apprendista ha accesso a un simulatore che può generare contesti gratuiti, il limite di regret migliora a $\tilde{O}(d\sqrt{L^*})$, dove $L^*$ è la perdita cumulativa della migliore politica. Questo è un limite di primo ordine che si adatta alla difficoltà dell'istanza del problema.

Significato e Rivendicazioni

Gli autori affermano che questo lavoro fornisce un framework generale che amplia significativamente l'applicabilità dei bandit contestuali lineari avversariali a problemi con spazi di azioni esponenzialmente grandi (ad es., cammino minimo, flusso, matching bipartito) senza richiedere la conoscenza della distribuzione del contesto o un simulatore.

Il documento nota esplicitamente che, sebbene il limite $\tilde{O}(d^2\sqrt{T})$ sia un miglioramento rispetto ai precedenti risultati in tempo polinomiale dipendenti da $K$, rimane una questione aperta se il limite quasi-ottimale $\tilde{O}(d\sqrt{T})$ possa essere raggiunto senza un simulatore in tempo polinomiale. Gli autori sottolineano inoltre che il loro approccio rimuove l'assunzione irrealistica di distribuzioni di contesto log-concave richiesta da alcuni lavori precedenti (Olkhovskaya et al., 2023) quando specializzata in determinate formulazioni. Infine, suggeriscono che il framework di riduzione potrebbe essere applicabile ad altri setting, come i MDP lineari con transizioni fisse e perdite avversariali.