Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Problematica
Il documento affronta il problema del bandit lineare-gaussiano, un contesto di decision-making sequenziale in cui un giocatore seleziona azioni $A_t \in \mathcal{A} \subset \mathbb{R}^d$ per massimizzare i premi cumulativi. Il premio al tempo $t$ è generato da $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$, dove $\theta_\star$ è un vettore di parametri sconosciuto e $W_{t+1}$ è un rumore gaussiano i.i.d. con varianza $\sigma^2$. L'obiettivo è minimizzare il regret bayesiano, definito come la differenza attesa tra il premio dell'azione ottimale e l'azione scelta su un orizzonte $T$, assumendo una distribuzione a priori $\rho$ su $\theta_\star$. Nello specifico, gli autori si concentrano sul caso in cui $\theta_\star \sim \mathcal{N}(\mu_0, \Sigma_0)$ e l'insieme delle azioni è una palla $\ell_2$ scalata di raggio $r$.

Metodologia
Gli autori analizzano il Thompson sampling, un algoritmo di campionamento della posteriore che estrae una stima del parametro $\hat{\theta}_t$ dalla distribuzione a posteriori data la storia $H_t$ e seleziona l'azione che massimizza il premio atteso sotto $\hat{\theta}_t$.

Per derivare i limiti del regret, gli autori impiegano una decomposizione del regret istantaneo in due termini:

1. Termine (I): Il regret incursito quando il parametro campionato $\hat{\theta}_t$ è vicino al vero parametro $\theta_\star$ (all'interno di un evento ad alta probabilità definito dalla matrice di precisione a posteriori).
2. Termine (II): Il regret incursito quando il parametro campionato è lontano dal vero parametro.

L'innovazione tecnica centrale risiede nell'analisi del Termine (I). Gli autori introducono un lemma del potenziale ellittico generalizzato (Lemma 3). A differenza dei classici lemma del potenziale ellittico utilizzati nella letteratura sui bandit lineari (ad es., Abeille & Lazaric, 2017; Dani et al., 2008), che tipicamente richiedono che la matrice di precisione iniziale sia limitata lontano dallo zero (ad es., $V_0 \succeq I$) e limitano gli errori quadratici, questo nuovo lemma:

• Permette alla matrice di precisione iniziale $V_0$ di essere arbitrariamente piccola (o persino zero nel limite), accogliendo priori diffuse.
• Introduce un esponente flessibile $p \in [0, 1]$ nella sommatoria delle norme.
• Separa esplicitamente il limite in un termine di determinante logaritmico (che cattura il guadagno di informazione a lungo termine) e un termine di traccia che coinvolge la precisione iniziale (che cattura il costo di "burn-in" iniziale).

L'analisi del Termine (II) si basa su standard disuguaglianze di concentrazione per distribuzioni gaussiane per limitare la probabilità di grandi deviazioni tra $\hat{\theta}_t$ e $\theta_\star$.

Contributi Chiave e Risultati
Il contributo primario è un nuovo limite del regret bayesiano per il Thompson sampling nel contesto lineare-gaussiano che decupla il termine di "burn-in" dipendente dalla prior dal tasso di minimax del regret.

1. Limite del Regret Migliorato: Gli autori dimostrano che il Thompson sampling raggiunge un regret di:
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   Qui, $\sigma d \sqrt{T}$ rappresenta il tasso minimax asintotico, mentre $d r \sqrt{\text{Tr}(\Sigma_0)}$ rappresenta il costo iniziale di riduzione dell'incertezza dalla scala della prior alla scala del rumore.

2. Decoupling dei Termini: I limiti precedenti (ad es., Kalkanli & Özgür, 2020) esibivano una dipendenza moltiplicativa, tale che $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$, dove la diffusività della prior $\sqrt{\text{Tr}(\Sigma_0)}$ scalava l'intero tasso minimax. Il nuovo risultato mostra che, fino ai fattori logaritmici, la diffusività della prior aggiunge solo una costante additiva al regret, indipendente dall'orizzonte temporale $T$.

3. Limiti Inferiori: Il documento stabilisce un limite inferiore per qualsiasi policy in questo contesto, dimostrando che il termine di burn-in $d r \sqrt{\text{Tr}(\Sigma_0)}$ è inevitabile per le prior gaussiane. Ciò conferma che la struttura additiva del limite superiore è stretta (fino ai fattori logaritmici) e che la diffusività della prior non può essere eliminata interamente dal regret.

4. Generalizzazione: Gli autori osservano che i loro risultati possono essere estesi a prior fortemente log-concave e distribuzioni di rumore, non limitandosi strettamente al caso gaussiano.

Significatività
Il documento sostiene che i suoi risultati risolvono una imprecisione (looseness) nei limiti esistenti del regret per il Thompson sampling. Dimostrando che il termine dipendente dalla prior è additivo anziché moltiplicativo, il lavoro chiarisce il ruolo della diffusività della prior: essa agisce come un costo di "burn-in" una tantum necessario per ridurre l'incertezza al livello del rumore di osservazione, dopo il quale le prestazioni dell'algoritmo sono governate esclusivamente dalla varianza del rumore $\sigma$ e dalla dimensione $d$. L'introduzione del lemma del potenziale ellittico generalizzato è presentata come uno strumento che consente un'analisi più flessibile dei problemi di ottimizzazione stocastica in cui l'incertezza iniziale può essere illimitata.