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

Technisches Resümee: Asymptotische Optimalität von Thompson Sampling für risikoaversen Banditen mit Sub-Gauß-Belohnungen

Problemstellung
Die Arbeit befasst sich mit dem Multi-Armed Bandit (MAB) Problem unter risikoaversen Zielsetzungen. Im Gegensatz zu Standard-MAB-Settings, die den erwarteten Ertrag maximieren, zielen risikoaverse Settings auf allgemeine Risiko-Funktionale $\rho$ ab (z. B. Conditional Value-at-Risk (CVaR), Mittelwert-Varianz, Sharpe-Ratio oder Verzerrungsrisikomaße). Die spezifische Herausforderung liegt in der theoretischen Analyse von $\rho$-NPTS (einem nichtparametrischen Thompson-Sampling-Algorithmus, vorgeschlagen von Chang und Tan [2022]). Während Chang und Tan die instanzoptimale Regret für ein parametrisches Pendant ($\rho$-MTS) nachwiesen, ließen sie die Optimalität des nichtparametrischen $\rho$-NPTS als offenes Problem zurück.

Das grundlegende Hindernis besteht darin, dass $\rho$-NPTS eine Dirichlet-Posterior-Verteilung konstruiert, deren effektive Alphabetgröße mit der Anzahl der Beobachtungen ($N_k$) wächst. Eine direkte Anwendung bestehender Tail-Bounds führt zu einem super-exponentiellen Präfaktor von $(N_k)^{N_k/2}$, was den Beweis von logarithmischen Regret-Schranken verhindert. Darüber hinaus erforderten vorangegangene Ergebnisse oft starke Bedingungen wie die „Dominanz“-Bedingung (für parametrische Methoden) oder Lipschitz-Stetigkeit des Risiko-Funktionals (für UCB-Typ-Algorithmen), was wichtige nicht-Lipschitz-Funktionale wie die Sharpe-Ratio ausschließt.

Methodik
Die Autoren führen $\rho$-NPTSSG ein, eine ankerfreie Variante des nichtparametrischen Thompson-Sampling-Algorithmus, der für Verteilungen mit beschränkter Dichte und Sub-Gauß-Tails ($P(B, \sigma)$) entwickelt wurde. Die zentrale technische Innovation ist ein Diskretisierungs-Lemma (und dessen trunkiertes Analogon für Sub-Gauß-Tails), das die wachsend-alphabetische Dirichlet-Posterior-Verteilung auf ein festes Gitter projiziert.

1. Diskretisierung und Aggregation:
   Das Paper definiert ein festes Gitter $G_M$ der Größe $M$. Für jede beobachtete Belohnungssequenz wird das empirische Maß auf dieses Gitter projiziert, indem die zu den Beobachtungen gehörenden Dirichlet-Gewichte aggregiert werden, die in dieselbe Gitter-Bin fallen.

   • Zentrale Erkenntnis: Durch die Aggregationseigenschaft der Dirichlet-Verteilung folgen die projizierten Gewichte auf den besetzten Bins einer Dirichlet-Verteilung mit einer festen Dimension ($M^+ \le M$), unabhängig von der Stichprobengröße $N_k$.
   • Konsequenz: Diese Projektion begrenzt den polynomischen Präfaktor in den Tail-Bounds auf den Grad $(M-1)/2$, der unabhängig von $N_k$ ist. Dies durchbricht die super-exponentielle Barriere, die bisherige Beweise blockierte.

2. Algorithmus-Varianten:

   • $\rho$-NPTS (Beschränkter Support): Operiert auf Verteilungen mit Support in $[0, 1]$ und beschränkter Dichte. Es verwendet einen festen Anker (den rechten Endpunkt) und ein uniformes Gitter.
   • $\rho$-NPTSSG (Sub-Gauß): Operiert auf Verteilungen auf $\mathbb{R}$ mit beschränkter Dichte und Sub-Gauß-Tails. Es entfernt den festen Anker (verwendet stattdessen Round-Robin-Initialisierung) und nutzt ein trunkiertes Diskretisierungs-Lemma. Dieses Lemma verwendet ein auf den empirischen Mittelwert zentriertes Gitter, dessen Breite mit wachsender Stichprobengröße schrumpft, während die Tails zur Kontrolle der Overflow-Wahrscheinlichkeit trunkiert werden.

3. Regret-Analyse:
   Der Beweis folgt einer Standard-Zerlegung des Regrets in Terme, bei denen der Algorithmus einen suboptimalen Arm mit einem „hohen“ Thompson-Score gegenüber einem „niedrigen“ Score zieht.

   • Obere Schranke (Upper Bound): Nutzt das Diskretisierungs-Lemma, um die Tail-Bounds von Chang und Tan [2022] auf die Projektion auf das feste Gitter anzuwenden. Die Stetigkeit von $\rho$ (speziell $D_\infty$-Stetigkeit) stellt sicher, dass das Risiko des projizierten Maßes das wahre Risiko approximiert.
   • Untere Schranke (Lower Bound): Gleicht die instanzabhängige untere Schranke an, die von Chang und Tan [2022] etabliert wurde und auf dem Kullback-Leibler (KL)-Divergenz-Minimierungsproblem $K^\rho_{\inf}$ basiert.

Zentrale Beiträge

1. Lösung des offenen Problems: Das Paper beweist, dass $\rho$-NPTSSG einen instanzoptimalen Regret von $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ für jedes kontinuierliche Risiko-Funktional $\rho$ auf der Klasse der Verteilungen mit beschränkter Dichte und Sub-Gauß-Tails erreicht.
2. Schwächere Bedingungen: Das Ergebnis erfordert lediglich die Stetigkeit des Risiko-Funktionals $\rho$ (speziell bezüglich der Lévy–Prokhorov-Metrik). Dies ist strikt schwächer als:
   • Die „Dominanz“-Bedingung, die für das parametrische $\rho$-MTS erforderlich ist.
   • Die Lipschitz-Bedingung, die für UCB-Typ-Algorithmen erforderlich ist.
     Dies ermöglicht die ersten instanzoptimalen Garantien für nicht-Lipschitz-Funktionale wie die Sharpe-Ratio, ohne parametrische Belohnungsverteilungen vorauszusetzen.
3. Diskretisierungs-Lemma: Das Paper führt ein technisches Lemma ein, das eine wachsend-alphabetische Dirichlet-Posterior-Verteilung bei einer festen Auflösung kontrolliert. Dieses Lemma ist potenziell unabhängig von Interesse für jedes Problem, das mit Dirichlet-Prozessen mit wachsendem Support zu tun hat.
4. Sub-Gauß-Erweiterung: Die Autoren erweitern die Ergebnisse mit beschränktem Support auf die breitere Klasse der Sub-Gauß-Verteilungen (einschließlich Gauß-Armen) mittels eines trunkierten Diskretisierungs-Ansatzes, wodurch die Notwendigkeit eines vordefinierten Support-Intervalls entfällt.

Ergebnisse

• Theorem 1 (Beschränkter Support): Belegt die asymptotische Optimalität für $\rho$-NPTS auf $P(B)$ unter alleiniger Stetigkeit.
• Theorem 2 (Sub-Gauß): Belegt die asymptotische Optimalität für $\rho$-NPTSSG auf $P(B, \sigma)$.
• Experimentelle Validierung: Das Paper präsentiert vier Experimente zur Validierung der Theorie:
  1. $\rho$-NPTS folgt der instanzoptimalen unteren Schranke für CVaR bei Beta-Armen und übertrifft die Risk-LCB-Baseline (die eine $\log^2 n$ Garantie hat).
  2. $\rho$-NPTS erreicht einen Regret von $O(\log n)$ für die Sharpe-Ratio bei Trunkated-Normal-Armen – ein Fall, für den zuvor kein Algorithmus Garantien liefern konnte, aufgrund der Nicht-Lipschitzheit.
  3. Der Algorithmus handhabt zusammengesetzte Funktionale (z. B. $0.5 \text{CVaR} + 0.5 \text{Sharpe}$) ohne Modifikation.
  4. $\rho$-NPTSSG konvergiert gegen die instanzoptimale untere Schranke für Gauß-Arme und erreicht die Performance des spezialisierten Normal-Gamma Thompson-Sampling-Algorithmus (Shah et al. [2025]), ohne Gauß-Belohnungen vorauszusetzen.

Bedeutung und Behauptungen
Das Paper behauptet, den theoretischen Status des nichtparametrischen Thompson-Samplings für risikoaverse Banditen geklärt zu haben. Es zeigt, dass diese Algorithmen nicht bloß empirische Heuristiken sind, sondern beweisbar asymptotisch optimal sind.

Die Bedeutung liegt in der Lockerung der Annahmen:

• Praktiker können Rohbeobachtungen verwenden, ohne ein Belohnungs-Gitter vorzugeben oder eine Alphabet-Größe zu tunen.
• Die Methode ist anwendbar auf eine strikt breitere Klasse von Risiko-Funktionalen (einschließlich der Sharpe-Ratio) und Verteilungsklassen (Sub-Gauß) als bisherige optimale Methoden.
• Das Ergebnis subsumiert die gleichzeitige Arbeit von Shah et al. [2025], indem es eine schärfere, instanzoptimale Konstante für die Sharpe-Ratio liefert, ohne konjugierte Priors oder parametrische Annahmen zu erfordern.

Die Autoren merken an, dass die Annahme der beschränkten Dichte für die Bin-Wahrscheinlichkeits-Bounds im Beweis notwendig ist und nicht für Verteilungen mit Punktmassen (z. B. Bernoulli) gilt, für die das parametrische $\rho$-MTS die komplementäre Lösung darstellt. Als zukünftige Forschungsrichtungen werden kontextuelle Banditen, Heavy-Tailed-Belohnungen und diskrete Verteilungen genannt.