Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

Sintesi Tecnica: Ottimalità Asintotica di Thompson Sampling per Banditi Avversi al Rischio con Ricompense Sub-Gaussiane

Enunciato del Problema
Il saggio affronta il problema dei Multi-Armed Bandit (MAB) sotto obiettivi avversi al rischio. A differenza degli standard MAB che massimizzano la ricompensa attesa, gli scenari avversi al rischio mirano a ottimizzare funzionali di rischio generali $\rho$ (ad esempio, il Valore in Rischio Condizionale (CVaR), media-varianza, Sharpe ratio o misure di distorsione). La sfida specifica affrontata è l'analisi teorica di $\rho$-NPTS (un algoritmo di Thompson Sampling non parametrico proposto da Chang e Tan [2022]). Sebbene Chang e Tan abbiano dimostrato l'ottimalità dell'istanza per un compagno parametrico ($\rho$-MTS), hanno lasciato come problema aperto l'ottimalità del $\rho$-NPTS non parametrico.

L'ostacolo fondamentale è che il $\rho$-NPTS costruisce un posteriore di Dirichlet in cui la dimensione effettiva dell'alfabeto cresce con il numero di osservazioni ($N_k$). L'applicazione diretta dei risultati esistenti sui limiti di coda produce un prefattore super-esponenziale di $(N_k)^{N_k/2}$, il che impedisce la dimostrazione di limiti di regret logaritmici. Inoltre, i risultati precedenti richiedevano spesso condizioni forti come la condizione di "dominanza" (per i metodi parametrici) o la continuità Lipschitziana del funzionale di rischio (per gli algoritmi di tipo UCB), escludendo importanti funzionali non-Lipschitziani come lo Sharpe ratio.

Metodologia
Gli autori introducono $\rho$-NPTSSG, una variante anchor-free dell'algoritmo di Thompson Sampling non parametrico progettata per distribuzioni con densità limitata e code sub-gaussiane ($P(B, \sigma)$). L'innovazione tecnica centrale è un lemma di discretizzazione (e il suo analogo troncato per code sub-gaussiane) che proietta il posteriore di Dirichlet con alfabeto crescente su una griglia fissa.

1. Discretizzazione e Aggregazione:
   Il saggio definisce una griglia fissa $G_M$ di dimensione $M$. Per qualsiasi sequenza di ricompense osservata, la misura empirica viene proiettata su questa griglia aggregando i pesi di Dirichlet corrispondenti alle osservazioni che cadono all'interno dello stesso bin della griglia.

   • Intuizione Chiave: Grazie alla proprietà di aggregazione della distribuzione di Dirichlet, i pesi proiettati sui bin occupati seguono una distribuzione di Dirichlet con una dimensione fissa ($M^+ \le M$), indipendentemente dalla dimensione del campione $N_k$.
   • Conseguenza: Questa proiezione limita il prefattore polinomiale nei limiti di coda al grado $(M-1)/2$, che è indipendente da $N_k$. Ciò rompe la barriera super-esponenziale che bloccava le dimostrazioni precedenti.

2. Varianti dell'Algoritmo:

   • $\rho$-NPTS (Supporto Limitato): Opera su distribuzioni con supporto in $[0, 1]$ e densità limitata. Utilizza un anchor fisso (l'estremo destro) e una griglia uniforme.
   • $\rho$-NPTSSG (Sub-Gaussiano): Opera su distribuzioni su $\mathbb{R}$ con densità limitata e code sub-gaussiane. Rimuove l'anchor fisso (utilizzando l'inizializzazione round-robin) e impiega un lemma di discretizzazione troncata. Questo lemma utilizza una griglia centrata sulla media empirica con una larghezza che si restringe al crescere della dimensione del campione, mentre tronca le code per controllare la probabilità di overflow.

3. Analisi del Regret:
   La dimostrazione segue una decomposizione standard del regret in termini in cui l'algoritmo estrae un braccio subottimale con uno score di Thompson "alto" rispetto a uno score "basso".

   • Limite Superiore (Upper Bound): Utilizza il lemma di discretizzazione per applicare i limiti di coda di Chang e Tan [2022] alla proiezione su griglia fissa. La continuità di $\rho$ (specificamente la continuità $D_\infty$) assicura che il rischio della misura proiettata approssimi il rischio reale.
   • Limite Inferiore (Lower Bound): Corrisponde al limite inferiore dipendente dall'istanza stabilito da Chang e Tan [2022], che si basa sul problema di minimizzazione della divergenza di Kullback-Leibler (KL) $K^\rho_{\inf}$.

Contributi Chiave

1. Risoluzione del Problema Aperto: Il saggio dimostra che $\rho$-NPTSSG raggiunge un regret di ottimalità d'istanza di $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ per qualsiasi funzionale di rischio continuo $\rho$ sulla classe di distribuzioni con densità limitata e code sub-gaussiane.
2. Condizioni Più Deboli: Il risultato richiede solo la continuità del funzionale di rischio $\rho$ (specificamente rispetto alla metrica di Lévy–Prokhorov). Questo è strettamente più debole della:
   • Condizione di "dominanza" richiesta per il $\rho$-MTS parametrico.
   • Condizione Lipschitziana richiesta per gli algoritmi di tipo UCB.
     Questa proprietà permette le prime garanzie di ottimalità d'istanza per funzionali non-Lipschitziani, come lo Sharpe ratio, senza assumere distribuzioni di ricompensa parametriche.
3. Lemma di Discretizzazione: Il saggio introduce un lemma tecnico che controlla un posteriore di Dirichlet con alfabeto crescente a una risoluzione fissa. Questo lemma è di potenziale interesse indipendente per qualsiasi problema che coinvolga processi di Dirichlet con supporto crescente.
4. Estensione Sub-Gaussian: Gli autori estendono i risultati a supporto limitato alla classe più ampia di distribuzioni sub-gaussiane (incluse le braccia gaussiane) tramite un approccio di discretizzazione troncata, rimuovendo la necessità di un intervallo di supporto pre-specificato.

Risultati

• Teorema 1 (Supporto Limitato): Stabilisce l'ottimalità asintotica per $\rho$-NPTS su $P(B)$ sotto la sola continuità.
• Teorema 2 (Sub-Gaussiano): Stabilisce l'ottimalità asintotica per $\rho$-NPTSSG su $P(B, \sigma)$.
• Validazione Sperimentale: Il saggio presenta quattro esperimenti che validano la teoria:
  1. $\rho$-NPTS segue il limite inferiore di ottimalità d'istanza per il CVaR su braccia Beta, superando la baseline Risk-LCB (che ha una garanzia di $\log^2 n$).
  2. $\rho$-NPTS raggiunge un regret di $O(\log n)$ per lo Sharpe ratio su braccia normali troncate, un caso in cui nessun algoritmo precedente forniva garanzie a causa della non-Lipschitzianità.
  3. L'algoritmo gestisce funzionali compositi (ad esempio, $0.5 \text{CVaR} + 0.5 \text{Sharpe}$) senza modifiche.
  4. $\rho$-NPTSSG converge al limite inferiore di ottimalità d'istanza per le braccia Gaussiane, eguagliando le prestazioni dell'algoritmo specializzato Normal-Gamma Thompson Sampling (Shah et al. [2025]) senza assumere ricompense gaussiane.

Significato e Rivendicazioni
Il saggio sostiene di aver risolto lo status teorico del Thompson Sampling non parametrico per i banditi avversi al rischio. Dimostra che questi algoritmi non sono semplici euristiche empiriche ma sono provabilmente ottimali asintoticamente.

La significatività risiede nel rilassamento delle assunzioni:

• I praticanti possono utilizzare osservazioni grezze senza pre-specificare una griglia di ricompensa o calibrare la dimensione di un alfabeto.
• Il metodo si applica a una classe di funzionali di rischio (incluso lo Sharpe ratio) e classi di distribuzione (sub-gaussiane) strettamente più ampia rispetto ai metodi ottimali precedenti.
• Il risultato assorbe il lavoro concorrente di Shah et al. [2025] fornendo una costante più acuta e di ottimalità d'istanza per lo Sharpe ratio senza richiedere prior coniugati o assunzioni parametriche.

Gli autori osservano che l'assunzione di densità limitata è necessaria per i limiti di probabilità dei bin utilizzati nella dimostrazione e non vale per le distribuzioni con masse puntuali (ad esempio, Bernoulli), per le quali il $\rho$-MTS parametrico rimane la soluzione complementare. Le direzioni di ricerca futura identificate includono i bandit contestuali, le ricompense con code pesanti (heavy-tailed) e le distribuzioni discrete.