Sintesi Tecnica: Un Algoritmo Congiuntamente Efficiente e Ottimale per Banditi GLM Eteroschedastici con Corruzioni Avversarie

1. Impostazione del Problema

Il documento affronta il problema dei Banditi GLM (Generalized Linear Bandits) Eteroschedastici in presenza di corruzioni avversarie. Questo setting unifica tre aspetti impegnativi del processo decisionale sequenziale:

1. Modelli Lineari Generalizzati (GLM): Il reward atteso per un braccio $x_t \in \mathbb{R}^d$ segue un GLM, $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$, dove $\mu$ è una funzione di link inversa nota e $\theta^\star$ è un parametro ignoto. Questo framework comprende i banditi logistici, di Poisson e gaussiani lineari.
2. Eteroschedasticità: La varianza del reward non è costante ma varia tra i bracci e i passi temporali. Nello specifico, $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$, dove $g(\tau_t)$ è un parametro di dispersione che può variare esogenamente nel tempo (ad esempio, nei banditi gaussiani) o essere determinato endogenamente dalla scelta del braccio (ad esempio, nei banditi logistici o di Poisson).
3. Corruzioni Avversarie: Un avversario adattivo manipola il reward osservato ad ogni passo $t$ aggiungendo una corruzione $c_t$, tale che l'apprendista osserva $\tilde{r}_t = r_t + c_t$. L'avversario opera sotto un vincolo di budget totale $\sum_{t=1}^T |c_t| \le C$.

L'obiettivo è minimizzare il pseudo-regret cumulativo, definito come la differenza tra il reward atteso del braccio ottimale e quello del braccio scelto durante $T$ round.

2. Metodologia: HCW-GLB-OMD

Gli autori propongono HCW-GLB-OMD (Hessian-Confidence Weighted GLB-OMD), un algoritmo progettato per essere sia computazionalmente efficiente che statisticamente ottimale. L'algoritmo integra due componenti primarie:

A. Stimatore Online Mirror Descent (OMD)

A differenza degli approcci precedenti che si affidano alla stima di Massima Verosimiglianza (MLE) in batch, che crea un disallineamento temporale tra i pesi locali e le stime globali, HCW-GLB-OMD utilizza uno stimatore OMD online. L'aggiornamento del parametro al passo $t$ è definito come:
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
dove $\tilde{\ell}_t$ è una log-verosimiglianza negativa pesata. Questo approccio online garantisce che lo stimatore, il braccio e i pesi siano allineati allo stesso passo temporale locale, facilitando un'analisi rigorosa dell'impatto delle corruzioni.

B. Pesi di Confidenza Basati sulla Hessiana

Per ottenere la robustezza contro le corruzioni, l'algoritmo assegna un peso di confidenza $w_t$ a ogni osservazione basandosi sulla Hessiana locale (curvatura) della funzione di link e del parametro di dispersione:
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
Qui, $\|x_t\|_{H_t^{-1}}$ quantifica l'incertezza lungo la direzione di $x_t$.

• Meccanismo: Se una direzione del braccio è altamente incerta (grande norma nella inversa della Hessiana) rispetto alla dispersione, il peso $w_t$ viene ridotto ($<1$). Ciò riduce il peso delle osservazioni provenienti da direzioni vulnerabili alla manipolazione avversaria.
• Consapevolezza della Curvatura: A differenza dei metodi per banditi lineari che utilizzano una matrice di design, questo metodo utilizza la Hessiana $\nabla^2 \tilde{\ell}_t$, che incorpora la pendenza locale $\dot{\mu}$. Ciò consente all'algoritmo di adattarsi alla specifica geometria del GLM (ad esempio, la saturazione nei banditi logistici).

C. Sequenze di Confidenza Robuste alle Corruzioni

Gli autori costruiscono un insieme di confidenza $C_t(\delta)$ che tiene conto sia dell'errore di stima che della corruzione avversaria. Il raggio di questo insieme include un termine additivo proporzionale al budget di corruzione $C$:
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
La prova di questa sequenza si basa su un argomento di supermartingala applicato a un rapporto di verosimiglianza pesato, utilizzando la concavità della mappatura $x \mapsto x^{w_t}$ per gestire i casi in cui $w_t < 1$.

3. Contributi Chiave e Risultati

A. Limite Superiore del Regret

Il documento stabilisce un limite superiore del regret per HCW-GLB-OMD sotto l'assunzione che la funzione di link $\mu$ sia auto-concordante (Assunzione 3). Con probabilità almeno $1-\delta$, il regret è limitato da:
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
Dove:

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ è la pendenza della funzione di link al braccio ottimale.
• $g_{\max} = \max_t g(\tau_t)$ è la dispersione massima.
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ è il parametro di curvatura.
• $C$ è il budget totale di corruzione.

Significato del Limite:

• Ottimalità Instance-Wise: Il termine principale $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ dipende dalla reale pendenza al braccio ottimale, piuttosto che dalla curvatura peggiore $\kappa$. Ciò corrisponde al limite inferiore minimax per i GLM privi di corruzione.
• Robustezza alla Corruzione: Il termine di corzione scala linearmente con $C$ (specificamente $d(g_{\max} + \kappa)C$), il che è minimax ottimale salvo un fattore di curvatura $\kappa$.
• Unificazione: Il limite recupera simultaneamente i risultati allo stato dell'arte per i banditi lineari eteroschedastici, i banditi logistici e i banditi di Poisson.

B. Limite Inferiore Unificato del Regret

Gli autori dimostrano un limite inferiore unificato per qualsiasi GLM eteroschedastico auto-concordante con corruzioni avversarie:
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
Questo limite inferiore:

• Include i limiti esistenti specifici per problemi come i banditi logistici, i banditi lineari eteroschedastici e i banditi lineari corrotti.
• Conferma che il termine principale dell'algoritmo è minimax ottimale rispetto all'istanza.
• Dimostra che il termine di corruzione $dC$ è inevitabile, sebbene il limite superiore includa attualmente un ulteriore fattore $\kappa$ nel termine di corruzione ($d\kappa C$).

C. Efficienza Computazionale

Un contributo critico è l'efficienza dell'algoritmo. Utilizzando l'aggiornamento OMD online e gli aggiornamenti ricorsivi della Hessiana, HCW-GLB-OMD raggiunge una complessità di spazio e tempo per iterazione pari a $O(1)$. Ciò contrasta con gli algoritmi precedenti robusti alle corruzioni per i GLM (ad esempio, CR-Eluder-UCB, GAdaOFUL) che spesso richiedono una complessità di $O(t)$ a causa dell'elaborazione in batch o di complesse costruzioni di insiemi di confidenza.

4. Significato e Rivendicazioni

Il documento sostiene di fornire il primo algoritmo congiuntamente efficiente e ottimale per i GLM eteroschedastici sotto corruzioni avversarie. La sua importanza primaria risiede nel:

1. Colmare il Divario: Risolve il compromesso tra efficienza computazionale e ottimalità statistica nei GLM corrotti. I lavori precedenti erano o ottimali con alto costo computazionale o efficienti con limiti di regret subottimali (spesso scalanti con la curvatura peggiore $\kappa$).
2. Ottimalità Instance-Wise: L'algoritmo raggiunge limiti di regret che si adattano alla difficoltà specifica dell'istanza (tramite $\dot{\mu}_{t,\star}$) invece di fare affidamento su assunzioni peggiori (worst-case), anche in presenza di corruzioni.
3. Framework Unificato: Offre un singolo framework teorico che copre un ampio spettro di problemi di banditi (lineari, logistici, di Poisson, eteroschedastici) senza richiedere modifiche algoritmiche specifiche per il problema.

Gli autori notano un divario rimanente: il termine di corruzione nel limite superiore scala con $d\kappa C$, mentre il limite inferiore è $dC$. Essi ipotizzano che il fattore $\kappa$ nel termine di corzione sia un artefatto dell'analisi e che un limite $O(dC)$ sia raggiungibile, ma questo rimane un problema aperto. Inoltre, l'analisi attuale assume che il parametro di dispersione $\tau_t$ sia noto all'apprendista; la gestione di $\tau_t$ ignoto è identificata come una direzione futura.