When and why randomised exploration works (in linear bandits)

Sintesi Tecnica: Quando e perché l'esplorazione randomizzata funziona (nei bandit lineari)

Impostazione del Problema
Il documento affronta il problema dei bandit lineari, un contesto di decision-making sequenziale in cui un agente seleziona azioni $X_t$ da un sottoinsieme chiuso $\mathcal{X}$ della palla euclidea unitaria in $\mathbb{R}^d$. L'agente riceve una ricompensa $Y_t$ con media $\langle X_t, \theta^\star \rangle$, dove $\theta^\star$ è un vettore di parametri sconosciuto. L'obiettivo è minimizzare il regret a $n$ passi, definito come la differenza cumulativa tra la ricompensa dell'azione ottimale e le azioni intraprese.

Sebbene gli algoritmi ottimisti (ad esempio, Upper Confidence Bound) abbiano stabilito limiti di regret frequentisti di $O(d\sqrt{n} \log n)$ per i bandit lineari, gli algoritmi di esplorazione randomizzata come il Thompson sampling sono stati storicamente più difficili da analizzare in questo contesto. Le precedenti analisi frequentiste dei metodi randomizzati spesso si sono basate sull' "ottimismo forzato" o sull' "inflazione della distribuzione a posteriori" (posterior inflation): la modifica dell'algoritmo per gonfiare artificialmente la varianza della distribuzione a posteriori al fine di garantire l'ottimismo con alta probabilità. Queste modifiche hanno tipicamente prodotto limiti di regret subottimali, come $O((d \log n)^{3/2}\sqrt{n})$, introducendo un fattore $\sqrt{d}$ extra rispetto agli algoritmi ottimisti. Inoltre, recenti limiti inferiori (Hamidi e Bayati, 2023; Zhang, 2022) hanno dimostrato che il Thompson sampling non modificato può incorriare in un regret lineare in specifici scenari patologici, suggerendo che l'esplorazione randomizzata non è universalmente ottimale senza assunzioni strutturali.

Metodologia e Assunzioni
Gli autori propongono un nuovo framework di analisi che evita di modificare l'algoritmo randomizzato (ovvero, nessun ottimismo forzato o inflazione della distribuzione a posteriori). Inveve, l'analisi si basa su specifiche proprietà geometriche dell'insieme delle azioni $\mathcal{X}$.

1. Framework Algoritmico: Il documento considera una classe di algoritmi randomizzati dove, ad ogni passo $t$, un parametro $\theta_t$ viene campionato come $\theta_t = \hat{\theta}_{t-1} + V_{t-1}^{-1/2}\eta_t$, dove $\hat{\theta}_{t-1}$ è la stima dei minimi quadrati regolarizzata, $V_{t-1}$ è la matrice di design, e $\eta_t$ è una perturbazione rotazionalmente invariante. L'azione è selezionata come $X_t = \arg\max_{x \in \mathcal{X}} \langle x, \theta_t \rangle$.
2. Assunzioni sulle Perturbazioni: Le perturbazioni $\eta_t$ sono assunte essere variabili casuali indipendenti e rotazionalmente invarianti con momenti secondo e quarto limitati (ad esempio, Gaussiane o uniformi su una sfera).
3. Assunzioni sull'Insieme delle Azioni (Smoothness e Forte Convessità): Il nucleo del contributo teorico risiede nell'Assunzione 4.2, che richiede che l'insieme delle azioni $\mathcal{X}$ sia un sottoinsieme chiuso e assorbente della palla unitaria tale che il quadrato della sua funzione di supporto, $J_{\mathcal{X}}^2$, sia sia $m$-fortemente convesso che $M$-smooth rispetto a una specifica norma $\|\cdot\|_*$.
   • Forte Convessità: Garantisce che la funzione di supporto non abbia regioni "piatte", assicurando che piccoli cambiamenti nello spazio dei parametri si traducano in cambiamenti significativi nello spazio delle azioni.
   • Smoothness (Regolarità): Garantisce che il gradiente della funzione di supporto (che mappa i parametri alle azioni) sia Lipschitziano, impedendo grandi salti nel regret a causa di piccole perturbazioni dei parametri.
   • Esempi: Questa classe include le $p$-palle $\ell_q$ riscalate per $q \in (1, \infty)$.

Contributi Chiave e Analisi
Il documento fornisce un'analisi del regret frequentista che non dipende dal framework "ottimismo di fronte all'incertezza". Invece, analizza direttamente la dinamica del processo di esplorazione e l'evoluzione degli insiemi di confidenza.

• Decomposizione del Regret: Gli autori decompongono il regret atteso in due componenti: i passi in cui l'algoritmo è "ottimista" (il parametro campionato produce un valore superiore all'ottimo reale) e i passi in cui non lo è.
• Esplorazione Non Ottimistica: Un'intuizione critica è che anche quando un campione non è ottimista, esso fornisce comunque informazioni preziose che restringono l'insieme di confidenza. Gli autori utilizzano una formulazione della divergenza di Bregman per il regret per singolo passo, $r_t = D_{J_{\mathcal{X}}}(\theta^\star, \theta_t)$, e sfruttano la forte convessità e la regolarità di $J_{\mathcal{X}}^2$ per limitare questa divergenza.
• Crescita dell'Informazione: La dimostrazione stabilisce un limite inferiore sulla crescita della matrice di design $V_t$ collegando il guadagno di informazione atteso $\mathbb{E}_{t-1}[X_t X_t^\top]$ alla geometria degli ellissoidi di confidenza. Questo collega la "dimensione" dello spazio dei parametri (misurata da $V_t^{-1/2}$) all'esplorazione effettiva compiuta.
• Evitare l'Inflazione: A differenza dei lavori precedenti, questa analisi non richiede di gonfiare la varianza della distribuzione di campionamento. Dimostra che la naturale casualità dell'algoritmo, combinata con le proprietà geometriche di $\mathcal{X}$, è sufficiente a guidare l'esplorazione e a controllare il regret.

Risultati Principali
Sotto le assunzioni dichiarate, gli autori dimostrano che qualsiasi algoritmo randomizzato che soddisfi le condizioni di perturbazione raggiunge un limite di regret frequentista di:
$$R_n \lesssim O(d\sqrt{n} \log n)$$
Nello specifico, il Teorema 4.1 fornisce un limite dell'ordine $O(d\sqrt{n} \log n)$ (ignorando i fattori logaritmici in $n$ e $\delta$). Ciò corrisponde al limite inferiore noto per i bandit lineari (Rusmevichientong e Tsitsiklis, 2010) salvo i fattori logaritmici.

Significato e Rivendicazioni
Il documento sostiene di risolvere una importante questione aperta riguardante la dipendenza dalla dimensione del Thompson sampling nei bandit lineari.

• Dipendenza Ottimale dalla Dimensione: Dimostra per la prima volta che il Thompson sampling non modificato (non inflato) può raggiungere una dipendenza dimensionale ottimale ($O(d)$) in contesti di bandit lineari strutturati, specificamente quando lo spazio delle azioni è liscio e fortemente convesso.
• Meccanismo di Successo: Il lavoro elucida perché l'esplorazione randomizzata funziona in questi contesti: le proprietà geometriche dell'insieme delle azioni garantiscono che le perturbazioni nello spazio dei parametri esplorino efficacemente lo spazio delle azioni senza richiedere un ottimismo artificiale.
• Limitazioni e Ambito: Gli autori riconoscono che i loro risultati non contraddicono i limiti inferiori esistenti che mostrano un regret lineare per il Thompson sampling in spazi di azione non regolari o non assorbenti (ad esempio, quelli con braccia "trappola"). Il successo del metodo è subordinato al fatto che l'insieme delle azioni soddisfi le assunzioni di regolarità e forte convessità. Il documento non sostiene che queste condizioni siano necessarie, ma che sono sufficienti per raggiungere tassi ottimali senza modifiche algoritmiche.

In sintesi, il documento stabilisce che per una vasta classe di insiemi di azioni ben comportati (incluse le $p$-palle $\ell_q$), gli algoritmi di esplorazione randomizzata raggiungono naturalmente tassi di regret ottimali, eliminando la necessità delle tecniche di inflazione della varianza precedentemente ritenute necessarie per le garanzie teoriche.