Stochastic Linear Bandits with Parameter Noise

Riepilogo Tecnico: Banditi Lineari Stocastici con Rumore Parametrico

Definizione del Problema
Questo lavoro indaga il modello dei banditi lineari stocastici con rumore parametrico. In questo contesto, un apprendista interagisce con un ambiente su un orizzonte temporale $T$ selezionando azioni $a_t$ da un insieme di azioni $\mathcal{A} \subseteq \mathbb{R}^d$. A differenza del modello di rumore additivo standard, in cui la ricompensa è $X_t = a_t^\top \theta^\star + \eta_t$ (con $\theta^\star$ fisso e rumore $\eta_t$), il modello di rumore parametrico assume che la ricompensa sia data da $X_t = a_t^\top \theta_t$, dove $\theta_t$ è campionato in modo i.i.d. da una distribuzione fissa e sconosciuta $\nu$ con media $\theta^\star$ e matrice di covarianza $\Sigma$.

Il documento evidenzia una distinzione chiave: nel modello di rumore parametrico, l'apprendista può influenzare la varianza della ricompensa. Nello specifico, $\text{Var}(X_t) = a_t^\top \Sigma a_t$, mentre nel modello di rumore additivo la varianza è determinata esclusivamente dall'ambiente. Gli autori notano che, sebbene il modello di rumore parametrico sia un rilassamento del modello dei banditi lineari avversariali (dove $\theta_t$ è scelto da un avversario), presenta proprietà strutturali uniche che permettono potenzialmente limiti di rimpianto più stretti rispetto al modello di rumore additivo in determinati contesti geometrici.

Metodologia e Algoritmi
Gli autori propongono due algoritmi adattati a diverse geometrie dell'insieme di azioni:

1. VASE (Variance Aware Optimal Design Successive Elimination):

   • Obiettivo: Insiemi di azioni finiti generali (e insiemi infiniti tramite argomenti di copertura).
   • Meccanismo: Un algoritmo di eliminazione successiva che sfrutta le informazioni sulla varianza. In ogni fase, calcola un disegno G-ottimale $\pi_\ell$ per selezionare le azioni. Stima esplicitamente la varianza delle azioni nel supporto del disegno utilizzando un algoritmo di regola di arresto (SR).
   • Innovazione Chiave: L'algoritmo utilizza le varianze stimate in due modi: per ridurre il numero di campioni richiesti per l'esplorazione e come pesi in un stimatore dei minimi quadrati pesati. Questa ponderazione garantisce che la covarianza dello stimatore rimanga controllata anche con meno campioni, portando a limiti di rimpianto dipendenti dalla varianza.

2. VALEE (Variance Aware Linear Explore-Exploit):

   • Obiettivo: Sfere unitarie $\ell_p$ con $p \in (1, 2]$ (e le loro norme duali $q \ge 2$).
   • Meccanismo: Un semplice algoritmo esplora-sfrutta.
     • Esplorazione: L'algoritmo gioca i vettori della base standard $e_i$. Stima il vettore medio $\theta^\star$ coordinata per coordinata utilizzando la tecnica della Mediana delle Medie (MoM). Se la matrice di covarianza $\Sigma$ è sconosciuta, stima prima le varianze dei vettori della base.
     • Sfruttamento: Una volta che l'errore di stima è sufficientemente piccolo rispetto alla varianza e all'orizzonte temporale, l'algoritmo si impegna su un'azione $\hat{a}$ derivata dalla media stimata $\hat{\theta}$, specificamente $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • Innovazione Chiave: L'analisi sfrutta la geometria della sfera $\ell_p$ e la struttura del rumore parametrico. Gli autori dimostrano che l'esplorazione dei vettori della base produce un errore di stima proporzionale a $\sqrt{\sigma^2(e_i)}$, che è più stretto del limite standard $\epsilon$ nei modelli di rumore additivo. Ciò permette all'algoritmo di raggiungere limiti di rimpianto ottimali che dipendono dalla struttura di varianza della distribuzione delle ricompense.

Risultati Chiave
Il documento stabilisce sia limiti superiori che inferiori, dimostrando che gli algoritmi proposti sono minimassimalmente ottimali (a meno di fattori logaritmici) per contesti specifici.

• Insiemi di Azioni Fini Generali ($K$ azioni):

  • Limite Superiore: VASE raggiunge un rimpianto di $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$, dove $M_\sigma$ è una quantità dipendente dalla varianza limitata da $\max_a \sigma^2(a)$.
  • Limite Inferiore: Viene dimostrato un limite inferiore di $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, mostrando che il limite superiore è stretto a meno di fattori logaritmici quando $\log(K) \approx d$.

• Sfere Unitarie $\ell_p$ ($p \le 2$):

  • Covarianza Nota: VALEE raggiunge un rimpianto di $\tilde{O}(d + \sqrt{dT \sigma^2_q})$, dove $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. Ciò è dimostrato essere ottimale tramite un limite inferiore corrispondente di $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$.
  • Covarianza Sconosciuta: VALEE sostiene un termine additivo aggiuntivo, risultando in un rimpianto di $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$. Gli autori notano che questo termine additivo deriva dalla fase di stima della varianza.

• Sfere Unitarie $\ell_p$ ($p > 2$):

  • Il documento fornisce un limite inferiore di $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, che corrisponde ai limiti inferiori noti per il contesto avversariale in queste geometrie.

Significato e Affermazioni
Il documento afferma di risolvere un "caso curioso" riguardante i banditi lineari, in cui il modello di rumore additivo spesso produce limiti di rimpianto peggiori ($d\sqrt{T}$) rispetto al modello avversariale ($\sqrt{dT}$) per insiemi di azioni specifici come la sfera unitaria $\ell_2$. Gli autori dimostrano che il modello di rumore parametrico si allinea più da vicino all'intuizione secondo cui i modelli stocastici dovrebbero essere più semplici di quelli avversariali.

• Limiti più Stretti: Per le sfere $\ell_p$ con $p \le 2$, il modello di rumore parametrico permette limiti di rimpianto dell'ordine $\sqrt{dT \sigma^2_q}$, che possono essere significativamente più piccoli del limite $d\sqrt{T}$ tipico dei modelli di rumore additivo quando la varianza è piccola.
• Vantaggio Strutturale: I risultati evidenziano che la linearità della realizzazione (non solo dell'aspettativa) e la capacità dell'apprendista di influenzare la varianza sono cruciali per raggiungere questi limiti migliorati.
• Semplicità: Sorprendentemente, il rimpianto ottimale per le sfere $\ell_p$ ($p \le 2$) è ottenibile utilizzando un algoritmo esplora-sfrutta molto semplice (VALEE), in contrasto con gli algoritmi complessi di disegno ottimale spesso richiesti nei contesti di rumore additivo.

Gli autori concludono che, sebbene i loro risultati per $p \le 2$ siano ottimali (a meno di logaritmi) quando la covarianza è nota, il caso di covarianza sconosciuta lascia un divario aperto (il termine $T^{1/3}$) che futuri lavori potrebbero affrontare. Lasciano inoltre come questione aperta la progettazione di un algoritmo che corrisponda al limite inferiore per $p > 2$.