Self-Concordant Perturbations for Linear Bandits

Riepilogo Tecnico: Perturbazioni Auto-concordanti per i Bandit Lineari

Impostazione del Problema
Il documento affronta il problema dei bandit lineari avversari, un contesto di ottimizzazione online in cui un agente seleziona sequenzialmente le azioni $a_t$ da un corpo convesso $K \subset \mathbb{R}^d$. Ad ogni round, l'agente subisce una perdita $\langle y_t, a_t \rangle$ determinata da un vettore di perdita ignoto $y_t$, ricevendo solo questo feedback scalare. L'obiettivo è minimizzare il regret, definito come la differenza tra la perdita cumulativa dell'agente e la perdita cumulativa della migliore azione fissa nel passato (in hindsight).

Esistono due famiglie primarie di algoritmi: Follow-the-Regularized-Leader (FTRL) e Follow-the-Perturbed-Leader (FTPL). Sebbene un quadro unificato (GBPA) le connetta nel contesto dell'informazione completa, la distinzione è critica nei bandit: FTRL richiede espliciti meccanismi di esplorazione stocastica, mentre FTPL è intrinsecamente stocastico, selezionando azioni dai punti estremi dell'insieme delle azioni. Gli algoritmi esistenti con tassi ottimali spesso si affidano a complessi pre-processing o schemi di esplorazione specifici per il dominio (ad esempio, ellissoidi spazianti) piuttosto che derivare naturalmente dal framework delle barriere auto-concordanti utilizzato nell'algoritmo SCRIBLE. SCRIBLE raggiunge un regret di $O(d^{3/2}\sqrt{n \ln n})$ su corpi convessi generali e $O(d\sqrt{n \ln n})$ sulla palla $\ell_2$, ma soffre di una varianza di esplorazione subottimale sull'ipercubo.

Metodologia: Il Framework SC-FTPL
Gli autori introducono BANDITS-GBPA, un framework unificante che estende il GBPA a informazione completa al setting dei bandit lineari. Questo framework separa l'algoritmo in una funzione di potenziale $\Phi$, uno schema di campionamento $S$ e uno schema di stima $E$.

All'interno di questo framework, il documento propone l'algoritmo Self-Concordant Follow-the-Perturbed-Leader (SC-FTPL). L'innovazione principale è l'introduzione di perturbazioni auto-concordanti.

• Definizione: Una distribuzione di probabilità $D$ su $\mathbb{R}^d$ è una perturbazione $\vartheta$-auto-concordante per un corpo convesso $K$ se esiste una barriera $\vartheta$-auto-concordante $R$ su $K$ tale che il gradiente della coniugata di Fenchel di $R$ sia uguale al valore atteso del gradiente della funzione di supporto di $K$ sotto la perturbazione:
  $$\nabla R^*(\theta) = \mathbb{E}_{\xi \sim D}[\nabla \phi_K(\theta + \xi)]$$
  Questa definizione assicura che la distribuzione di perturbazione $D$ "replica" le proprietà geometriche della barriera auto-concordante $R$ in un contesto FTPL.

• Algoritmo: SC-FTPL mantiene una stima cumulativa delle perdite $\hat{Y}_{t-1}$. Ad ogni passo, campiona una perturbazione $\xi_t \sim D$ e seleziona l'azione:
  $$a_t = \arg \min_{a \in K} \langle a, \eta \hat{Y}_{t-1} - \xi_t \rangle$$
  Il vettore di perdita viene stimato utilizzando lo standard stimatore del secondo momento inverso $\hat{y}_t = Q_t^{-1} a_t \langle y_t, a_t \rangle$, dove $Q_t = \mathbb{E}_{t-1}[a_t a_t^\top]$.

Contributi Chiave

1. Framework Unificato (BANDITS-GBPA): Gli autori formalizzano un framework che comprende sia gli approcci FTRL che FTPL per i bandit lineari, estendendo l'analisi GBPA dall'informazione completa al feedback dei bandit. A differenza del setting a informazione completa, FTPL non è strettamente un sottoinsieme di FTRL qui, ma il framework permette una struttura analitica comune.
2. Perturbazioni Auto-concordanti: Il documento identifica e analizza una famiglia di distribuzioni di perturbazione che replicano le proprietà delle barriere auto-concordanti. Ciò colma il divario tra le proprietà di regolarizzazione di SCRIBLE e l'esplorazione intrinseca di FTPL.
3. Costruzioni Esplicite: Gli autori costruiscono perturbazioni auto-concordanti specifiche per due insiemi di azioni canonici:
   • Ipercubo $[-1, 1]^d$: Utilizzando la barriera entropica, derivano una perturbazione con marginali indipendenti.
   • Palla $\ell_2$ $B_d$: Utilizzando la barriera logaritmica, costruiscono una perturbazione basata su una distribuzione $t$ multivariata scalata.

Risultati e Bound di Regret
Il documento fornisce garanzie di regret per SC-FTPL sull'ipercubo e sulla palla $\ell_2$, assumendo tassi di apprendimento e condizioni sull'orizzonte appropriati ($n/\ln n$ sufficientemente grande rispetto alla dimensione).

• Ipercubo: SC-FTPL raggiunge un bound di regret di $O(d\sqrt{n \ln n})$.

  • Questo eguaglia il limite minimax stabilito da Dani et al. (2007) salvo fattori logaritmici.
  • Rappresenta un miglioramento di $\sqrt{d}$ rispetto all'algoritmo SCRIBLE (che raggiunge $O(d^{3/2}\sqrt{n \ln n})$ sull'ipercubo).
  • Il miglioramento deriva dallo schema di campionamento FTPL che si concentra sui punti estremi, riducendo la varianza dello stimatore del vettore di perdita nella norma locale rispetto al campionamento dell'ellissoide di Dikin usato da SCRIBLE.
  • La complessità computazionale per round è $O(d)$.

• Palla $\ell_2$: SC-FTPL raggiunge un bound di regret di $O(d\sqrt{n \ln n})$.

  • Questo eguaglia le prestazioni di SCRIBLE sulla palla $\ell_2$.
  • L'analisi per questo caso è più complessa perché la norma locale dello stimatore non ammette un limite quasi-sicuro uniforme indipendente dalla stima della perdita cumulativa. Gli autori impiegano un argomento innovativo che coinvolge un supermartingala e argomenti di tempo di arresto (usando l'ineguaglianza di Ville) per controllare la crescita dello stimatore cumulativo e gestire la mancanza di limiti uniformi.
  • La complessità computazionale per round è anch'essa $O(d)$.

Significatività e Rivendicazioni
Il documento sostiene che SC-FTPL fornisce un approccio unificato, basato sulle perturbazioni, per i bandit lineari che recupera i benefici della regolarizzazione auto-concordante senza richiedere i meccanismi di esplorazione espliciti, spesso complessi, dei metodi basati su FTRL.

• Ottimalità sull'Ipercubo: La significatività primaria risiede nel raggiungere il tasso ottimale sull'ipercubo senza schemi di campionamento specifici per il dominio, migliorando l'algoritmo allo stato dell'arte SCRIBLE di un fattore $\sqrt{d}$.
• Ponte Teorico: Il lavoro dimostra che FTPL può essere analizzato rigorosamente utilizzando la strumentazione delle barriere auto-concordanti, a patto che le perturbazioni siano scelte per replicare la geometria della barriera.
• Modestia sulla Generalizzazione: Gli autori osservano che, sebbene costruiscano perturbazioni per l'ipercubo e la palla $\ell_2$, l'esistenza di perturbazioni auto-concordanti per corpi convessi generali rimane una questione aperta. Riconoscono anche che il bound di regret sulla palla $\ell_2$ eguaglia SCRIBLE ma non lo migliora, e che l'analisi ha richiesto strumenti tecnici aggiuntivi (tempi di arresto) non necessari per l'ipercubo.

Il documento conclude identificando direzioni aperte, tra cui determinare se il tasso $O(d\sqrt{n \ln n})$ è stretto per FTPL sulla palla $\ell_2$ per qualsiasi schema di perturbazione, e investigare se la barriera entropica (una barriera auto-concordante universale) ammetta una corrispondente distribuzione di perturbazione per corpi convessi generali.