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

Technische Samenvatting: Asymptotische Optimaliteit van Thompson Sampling voor Risico-aversieve Bandits met Sub-Gaussische Beloningen

Probleemstelling
Het artikel behandelt het Multi-Armed Bandit (MAB) probleem onder risico-averse doelstellingen. In tegenstelling tot standaard MAB-instellingen die de verwachte beloning maximaliseren, richten risico-averse instellingen zich op het optimaliseren van algemene risicofunctionalen $\rho$ (bijv. Conditional Value-at-Risk (CVaR), gemiddelde-variantie, Sharpe-ratio, of distortierisico-maten). De specifieke uitdaging die wordt aangepakt, is de theoretische analyse van $\rho$-NPTS (een niet-parametrische Thompson Sampling algoritme voorgesteld door Chang en Tan [2022]). Hoewel Chang en Tan instantiële optimaliteit bewezen voor een parametrische metgezel ($\rho$-MTS), lieten zij de optimaliteit van de niet-parametrische $\rho$-NPTS als een open probleem staan.

De fundamentele hindernis is dat $\rho$-NPTS een Dirichlet-posterior construeert waarbij de effectieve alfabetgrootte groeit met het aantal observaties ($N_k$). Directe toepassing van bestaande staartgrenzen (tail bounds) resulteert in een super-exponentiële prefactor van $(N_k)^{N_k/2}$, wat het bewijs van logaritmische regret-bounds blokkeert. Verder vereisten eerdere resultaten sterke voorwaarden zoals de "dominantie"-conditie (voor parametrische methoden) of Lipschitz-continuïteit van de risicofunctie (voor UCB-type algoritmen), wat belangrijke niet-Lipschitz functies zoals de Sharpe-ratio uitsluit.

Methodologie
De auteurs introduceren $\rho$-NPTSSG, een anchor-vrije variant van het niet-parametrische Thompson Sampling algoritme, ontworpen voor distributies met een begrensde dichtheid en sub-Gaussische staarten ($P(B, \sigma)$). De kern van de technische innovatie is een discretisatie-lemma (en de getrunceerde analogon hiervan voor sub-Gaussische staarten) die de groeiende-alfabet Dirichlet-posterior projecteert op een vaste raster (grid).

1. Discretisatie en Aggregatie:
   Het artikel definieert een vast raster $G_M$ van grootte $M$. Voor elke geobserveerde beloningssequentie wordt de empirische maat geprojecteerd op dit raster door Dirichlet-gewichten te aggregeren die overeenkomen met observaties binnen hetzelfde raster-vak (bin).

   • Kerninzicht: Door de aggregatie-eigenschap van de Dirichlet-distributie volgen de geprojecteerde gewichten op de bezette vakken een Dirichlet-distributie met een vaste dimensie ($M^+ \le M$), ongeacht de steekproefgrootte $N_k$.
   • Gevolg: Deze projectie begrenst de polynomiale prefactor in de staartgrenzen tot graad $(M-1)/2$, die onafhankelijk is van $N_k$. Dit doorbreekt de super-exponentiële barrière die eerdere bewijzen blokkeerde.

2. Algoritme Varianten:

   • $\rho$-NPTS (Begrensde Support): Werkt op distributies met support in $[0, 1]$ en een begrensde dichtheid. Het gebruikt een vaste anchor (het rechter eindpunt) en een uniform raster.
   • $\rho$-NPTSSG (Sub-Gaussisch): Werkt op distributies op $\mathbb{R}$ met een begrensde dichtheid en sub-Gaussische staarten. Het verwijdert de vaste anchor (door round-robin initialisatie te gebruiken) en hanteert een getrunceerde discretisatie lemma. Dit lemma gebruikt een raster gecentreerd rond het empirische gemiddelde met een breedte die krimpt naarmate de steekproefgrootte groeit, terwijl de staarten worden afgekapt (getrunceerd) om de overflow-waarschijnlijkheid te controleren.

3. Regret Analyse:
   Het bewijs volgt een standaard decompositie van regret naar termen waarbij het algoritme een suboptimale arm trekt met een "hoge" Thompson-score versus een "lage" score.

   • Bovengrens (Upper Bound): Maakt gebruik van de discretisatie-lemma om de staartgrenzen van Chang en Tan [2022] toe te passen op de projectie op het vaste raster. De continuïteit van $\rho$ (specifiek $D_\infty$-continuïteit) zorgt ervoor dat het risico van de geprojecteerde maat de ware risico benadert.
   • Ondergrens (Lower Bound): Komt overeen met de instantiële afhankelijke ondergrens vastgesteld door Chang en Tan [2022], die steunt op het Kullback-Leibler (KL) divergentie minimalisatieprobleem $K^\rho_{\inf}$.

Belangrijkste Bijdragen

1. Oplossing van het Open Probleem: Het artikel bewijst dat $\rho$-NPTSSG een instantiële optimale regret bereikt van $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ voor elke continue risicofunctie $\rho$ op de klasse van distributies met begrensde dichtheid en sub-Gaussische staarten.
2. Zwakker Vereisten: Het resultaat vereist enkel de continuïteit van de risicofunctie $\rho$ (specifiek met betrekking tot de Lévy–Prokhorov metriek). Dit is strikt zwakker dan:
   • De "dominantie"-conditie vereist voor de parametrische $\rho$-MTS.
   • De Lipschitz-conditie vereist voor UCB-type algoritmen.
     Dit maakt de eerste instantiële optimale garanties voor niet-Lipschitz functies mogelijk, zoals de Sharpe-ratio, zonder de aanname van parametrische beloningsdistributies.
3. Discretisatie-lemma: Het artikel introduceert een technisch lemma dat een groeiend-alfabet Dirichlet-posterior controleert bij een vaste resolutie. Dit lemma is van potentieel onafhankelijk belang voor elk probleem dat te maken heeft met Dirichlet-processen met een groeiende support.
4. Sub-Gaussische Uitbreiding: De auteurs breiden de resultaten met begrensde support uit naar de bredere klasse van sub-Gaussische distributies (inclusclusief Gaussische armen) via een getrunceerde discretisatie-aanpak, waardoor de noodzaak voor een vooraf gespecificeerd support-interval vervalt.

Resultaten

• Theorem 1 (Begrensde Support): Vestigt de asymptotische optimaliteit voor $\rho$-NPTS op $P(B)$ onder continuïteit alleen.
• Theorem 2 (Sub-Gaussisch): Vestigt de asymptotische optimaliteit voor $\rho$-NPTSSG op $P(B, \sigma)$.
• Experimentele Validatie: Het artikel presenteert vier experimenten die de theorie valideren:
  1. $\rho$-NPTS volgt de instantiële optimale ondergrens voor CVaR op Beta-armen, waarbij het de Risk-LCB baseline (die een $\log^2 n$ garantie heeft) overtreft.
  2. $\rho$-NPTS bereikt $O(\log n)$ regret voor de Sharpe-ratio op truncated-normal armen, een geval waar geen enkel vorig algoritme garanties bood vanwege de niet-Lipschitzheid.
  3. Het algoritme handelt samengestelde functies af (bijv. $0.5 \text{CVaR} + 0.5 \text{Sharpe}$) zonder aanpassingen.
  4. $\rho$-NPTSSG convergeert naar de instantiële optimale ondergrens voor Gaussische armen, waarbij het de prestaties van het gespecialiseerde Normal-Gamma Thompson Sampling algoritme (Shah et al. [2025]) evenaart zonder een parametrische aanname voor de beloningen te vereisen.

Betekenis en Claims
Het artikel claimt de theoretische status van niet-parametrische Thompson Sampling voor risico-averse bandits te hebben beslecht. Het demonstreert dat deze algoritmen niet louter empirische heuristieken zijn, maar bewijsbaar asymptotisch optimaal zijn.

De betekenis ligt in de versoepeling van de aannames:

• Praktici kunnen ruwe observaties gebruiken zonder een vooraf gespecificeerd beloningsraster of een alfabetgrootte te tunen.
• De methode is toepasbaar op een strikt bredere klasse van risicofuncties (inclusief de Sharpe-ratio) en distributieklassen (sub-Gaussisch) dan eerdere optimale methoden.
• Het resultaat omvat het gelijktijdige werk van Shah et al. [2025] door een scherpere, instantiële optimale constante voor de Sharpe-ratio te bieden zonder dat er conjugaat-priors of parametrische aannames nodig zijn.

De auteurs merken op dat de aanname van begrensde dichtheid noodzakelijk is voor de bin-waarschijnlijkheidsgrenzen die in het bewijs worden gebruikt, en niet geldt voor distributies met puntmassa's (zoals Bernoulli), waarvoor de parametrische $\rho$-MTS de complementaire oplossing blijft. Toekomstige onderzoeksrichtingen die worden geïdentificeerd zijn contextuele bandits, heavy-tailed beloningen en discrete distributies.