Riepilogo Tecnico: Multinomial Logistic Bandit Efficiente tramite Frequent Directions

Definizione del Problema

Il documento affronta la sfida dei Multinomial Logistic Bandits (MLogB), un framework di decision-making sequenziale in cui un agente seleziona un'azione $x_t \in \mathbb{R}^d$ e osserva un feedback categorico $y_t \in \{0, \dots, K\}$. La distribuzione di probabilità degli esiti segue un modello logistico multinomiale parametrizzato da una matrice ignota $W^* \in \mathbb{R}^{K \times d}$. L'obiettivo è minimizzare il regret cumulativo, definito come la differenza tra il reward atteso dell'azione ottimale e l'azione scelta dall'agente.

Sebbene gli algoritmi allo stato dell'arte esistenti come OFUL-MLogB [Zhang e Sugiyama, 2023] raggiungano regimi di regret quasi ottimali di $\tilde{O}(Kd\sqrt{T})$, essi soffrono di costi computazionali proibitivi in contesti ad alta dimensionalità. Nello specifico, OFUL-MLogB si basa sul mantenimento e sulla manipolazione di una matrice Hessiana completa $Kd \times Kd$ per la stima dei parametri (tramite Online Newton Step) e la costruzione di reward ottimistici. Ciò comporta:

• Complessità Temporale: $O(|A_t|K^3d^2 + K^3d^3)$ per round.
• Complessità Spaziale: $O(K^2d^2)$ per round.

Questi costi rendono l'algoritmo impraticabile per spazi di azione ad alta dimensione ($d$) o grandi set di esiti ($K$).

Metodologia: EOFD-MLogB

Gli autori propongono EOFD-MLogB (Efficient Optimism via Frequent Directions), un algoritmo che integra lo sketching matriciale Frequent Directions (FD) nel framework OFUL-MLogB per ridurre la complessità computazionale preservando al contempo le garanzie teoriche.

1. Mantenimento Spettrale tramite FD Adattata

Inve Alternatively di memorizzare la piena Hessiana $H_t$, EOFD-MLogB mantiene una decomposizione spettrale a basso rango di una Hessiana schematizzata $Z_t$:
$$Z_t = \lambda I_{Kd} + V_t \Lambda_t V_t^\top$$
dove $V_t \in \mathbb{R}^{Kd \times m}$ ha colonne ortonormali, $\Lambda_t \in \mathbb{R}^{m \times m}$ è diagonale, e $m \ll d$ è la dimensione dello sketch.

• Aggiornamento Block FD: Poiché l'aggiornamento della Hessiana in MLogB è una matrice di rango-$K$ ($\nabla^2 \ell_t = \nabla \sigma(W_t x_t) \otimes x_t x_t^\top$), l'algoritmo esegue un aggiornamento block FD. Esso fattorizza l'aggiornamento di rango-$K$ in $B_t B_t^\top$ e appende $B_t$ allo sketch corrente $[V_t \Lambda_t^{1/2}, B_t]$. Viene calcolata una SVD, e le prime $m$ direzioni singolari vengono mantenute, scartando le restanti in un termine di errore di sketching cumulativo $\rho_{1:t}$.

2. Aggiornamento Efficiente dei Parametri

L'aggiornamento dei parametri in OFUL-MLogB comporta un problema di programmazione quadratica con vincoli (QCQP) su un ellissoide definito dalla Hessiana.

• Riduzione alla Ricerca di Radici: Utilizzando la forma spettrale della Hessiana surrogata $\tilde{Z}_t$, il problema di proiezione ad alta dimensione viene ridotto alla ricerca di una radice $\nu$ di una funzione scalare monotona $f(\nu) = S^2$. Ciò consente di calcolare la proiezione in modo efficiente senza una decomposizione in autovettori completa, sfruttando l'identità di Woodbury per l'inversione matriciale.

3. Costruzione Efficiente del Reward Ottimistico

Il bonus ottimistico in MLogB comporta il calcolo di norme spettrali ad alta dimensione, specificamente $\|H_t^{-1/2}(I_K \otimes x)\|_2$.

• Riduzione della Dimensionalità: Gli autori dimostrano (Lemma 1) che l'uso della matrice schematizzata $Z_t$ riduce il calcolo della norma spettrale $Kd \times Kd$ al calcolo della norma spettrale di una matrice simmetrica $K \times K$ denominata $A(x)$. Questo elimina la dipendenza da $d$ nel calcolo della norma spettrale, riducendo il costo da $O(K^3d^2)$ a $O(K^3 + K^2m + Kdm)$.

Contributi Chiave

1. Efficienza Algoritmica: EOFD-MLogB raggiunge una complessità temporale dominante per round di $O(Kd(m+K)^2)$ e una complessità spaziale di $O(Kd(m+K))$. Questo rappresenta un miglioramento significativo rispetto alla dipendenza cubica da $d$ dei metodi precedenti, rendendo l'algoritmo scalabile a contesti ad alta dimensionalità.
2. Garanzie Teoriche: Il documento stabilisce un limite di regret di $\tilde{O}(\Delta_T (Kd \ln \Delta_T + m)\sqrt{T})$, dove $\Delta_T = 1 + \rho_{1:T}/\lambda$ è un fattore di sketching dipendente dall'errore di sketching cumulativo $\rho_{1:T}$.
   • Il termine di errore $\rho_{1:T}$ è limitato dalla coda spettrale troncata di ordine $m$ della Hessiana cumulativa.
   • Quando la Hessiana accumulata è approssimativamente a basso rango (ovvero, la coda spettrale decade rapidamente), $\Delta_T \approx 1$, e il limite di regret si avvicina a quello dell'originale OFUL-MLogB.
3. Applicabilità Generale: Le tecniche di riduzione spettrale (Lemma 1 e Lemma 2) sono mostrate come applicabili ad altri algoritmi MLogB del secondo ordine e ai bandit lineari generalizzati che si basano su aggiornamenti della Hessiana, non solo a OFUL-MLogB.

Risultati Sperimentali

Gli esperimenti sono stati condotti sul dataset MNIST (convertito in un problema di bandit contestuale) e su dati sintetici ad alta dimensione ($d=100, 400$).

• Performance: EOFD-MLogB mantiene performance di regret competitive, ottenendo curve comparabili a OFUL-MLogB sia in contesti multinomiali che binari.
• Efficienza: Il metodo proposto dimostra sostanziali accelerazioni. Su MNIST, ha ridotto il tempo di calcolo per round di circa l'80% pur incorrendo in un overhead di regret di circa il 10%. Sui dati sintetici, le riduzioni di tempo hanno superato il 35% (multinomiale) e l'80% (binario).

Significato e Rivendicazioni

Il documento afferma che EOFD-MLogB affronta con successo i costi "proibitivi" della piena Hessiana degli algoritmi MLogB del secondo ordine esistenti. Sfruttando la tecnica di sketching Frequent Directions, gli autori dimostrano che è possibile:

• Mantenere i benefici teorici dei metodi del secondo ordine (aggiornamenti sensibili alla curvatura e set di confidenza stretti).
• Ridurre drasticamente l'overhead computazionale in regimi ad alta dimensionalità.
• Mantenere garanzie di regret quasi ottimali, a condizione che la struttura della Hessiana sottostante sia approssimativamente a basso rango.

Il lavoro evidenzia come, sebbene le tecniche di sketching standard (come quelle usate nei bandit lineari) non siano direttamente applicabili al contesto non lineare di MLogB a causa della mancanza di riduzioni in forma chiusa, le riduzioni spettrali adattate alla specifica struttura del modello logistico multinomiale possano superare tali colli di bottiglia. Gli autori osservano che il lavoro futuro potrebbe concentrarsi sulla selezione adattiva della dimensione dello sketch $m$ e sullo sviluppo di condizioni per controllare direttamente il fattore di sketching $\Delta_T$.