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

Résumé Technique : Optimalité Asymptotique de Thompson Sampling pour les Bandits Averses au Risque avec Récompenses Sub-Gaussiennes

Énoncé du Problème
L'article traite du problème des Bandits Multi-Bras (MAB) sous des objectifs d'aversion au risque. Contrairement aux contextes MAB standards qui maximisent l'espérance de la récompense, les contextes d'aversion au risque visent à optimiser des fonctionnelles de risque $\rho$ générales (par exemple, la Valeur à Risque Conditionnelle (CVaR), la moyenne-variance, le ratio de Sharpe ou les mesures de risque de distorsion). Le défi spécifique abordé est l'analyse théorique de $\rho$-NPTS (un algorithme de Thompson Sampling non paramétrique proposé par Chang et Tan [2022]). Bien que Chang et Tan aient prouvé l'optimalité de l'instance pour un compagnon paramétrique ($\rho$-MTS), ils ont laissé l'optimalité du $\rho$-NPTS non paramétrique comme un problème ouvert.

L'obstacle fondamental est que $\rho$-NPTS construit un postérieur de Dirichlet dont la taille effective de l'alphabet croît avec le nombre d'observations ($N_k$). L'application directe des résultats existants sur les bornes de queue produit un préfacteur super-exponentiel de $(N_k)^{N_k/2}$, ce qui empêche la preuve de bornes de regret logarithmiques. De plus, les résultats antérieurs nécessitaient souvent des conditions fortes telles que la condition de « dominance » (pour les méthodes paramétriques) ou la continuité de Lipschitz de la fonctionnelle de risque (pour les algorithmes de type UCB), excluant des fonctionnelles importantes non-Lipschitziennes comme le ratio de Sharpe.

Méthodologie
Les auteurs introduisent le $\rho$-NPTSSG, une variante sans ancrage (anchor-free) de l'algorithme de Thompson Sampling non paramétrique, conçue pour les distributions avec une densité bornée et des queues sub-gaussiennes ($P(B, \sigma)$). L'innovation technique centrale est un lemme de discrétisation (et son analogue tronqué pour les queues sub-gaussiennes) qui projette le postérieur de Dirichlet à alphabet croissant sur une grille fixe.

1. Discrétisation et Agrégation :
   L'article définit une grille fixe $G_M$ de taille $M$. Pour toute séquence de récompenses observée, la mesure empirique est projetée sur cette grille en agrégeant les poids de Dirichlet correspondant aux observations tombant dans le même intervalle (bin) de la grille.

   • Insight Clé : Grâce à la propriété d'agrégation de la distribution de Dirichlet, les poids projetés sur les intervalles occupés suivent une distribution de Dirichlet avec une dimension fixe ($M^+ \le M$), indépendamment de la taille de l'échantillon $N_k$.
   • Conséquence : Cette projection plafonne le préfacteur polynomial dans les bornes de queue au degré $(M-1)/2$, qui est indépendant de $N_k$. Cela brise la barrière super-exponentielle qui bloquait les preuves antérieures.

2. Variantes d'Algorithmes :

   • $\rho$-NPTS (Support Borné) : Opère sur des distributions dont le support est dans $[0, 1]$ avec une densité bornée. Il utilise un ancrage fixe (l'extrémité droite) et une grille uniforme.
   • $\rho$-NPTSSG (Sub-Gaussien) : Opère sur des distributions sur $\mathbb{R}$ avec une densité bornée et des queues sub-gaussiennes. Il supprime l'ancrage fixe (en utilisant une initialisation par tour de rôle/round-robin) et emploie un lemme de discrétisation tronquée. Ce lemme utilise une grille centrée sur la moyenne empirique avec une largeur qui rétrécit à mesure que la taille de l'échantillon augmente, tout en tronquant les queues pour contrôler la probabilité de débordement.

3. Analyse du Regret :
   La preuve suit une décomposition standard du regret en termes où l'algorithme tire un bras sous-optimal avec un score de Thompson « élevé » versus un score « faible ».

   • Borne Supérieure : Utilise le lemme de discrétisation pour appliquer les bornes de queue de Chang et Tan [2022] à la projection sur grille fixe. La continuité de $\rho$ (spécifiquement la continuité $D_\infty$) garantit que le risque de la mesure projetée approxime le risque réel.
   • Borne Inférieure : Correspond à la borne inférieure dépendante de l'instance établie par Chang et Tan [2022], qui repose sur le problème de minimisation de la divergence de Kullback-Leibler (KL) $K^\rho_{\inf}$.

Contributions Clés

1. Résolution du Problème Ouvert : L'article prouve que $\rho$-NPTSSG atteint un regret d'optimalité d'instance de $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ pour toute fonctionnelle de risque continue $\rho$ sur la classe des distributions avec densité bornée et queues sub-gaussiennes.
2. Conditions Plus Faibles : Le résultat requiert uniquement la continuité de la fonctionnelle de risque $\rho$ (spécifiquement par rapport à la métrique de Lévy–Prokhorov). C'est strictement plus faible que :
   • La condition de « dominance » requise pour le $\rho$-MTS paramétrique.
   • La condition de Lipschitz requise pour les algorithmes de type UCB.
     Cela permet les premières garanties d'optimalité d'instance pour des fonctionnelles non-Lipschitziennes, telles que le ratio de Sharpe, sans supposer de distributions de récompenses paramétriques.
3. Lemme de Discrétisation : L'article introduit un lemme technique qui contrôle un postérieur de Dirichlet à alphabet croissant à une résolution fixe. Ce lemme est d'un intérêt potentiellement indépendant pour tout problème impliquant des processus de Dirichlet avec un support croissant.
4. Extension Sub-Gaussienne : Les auteurs étendent les résultats de support borné à la classe plus large des distributions sub-gaussiennes (incluant les bras gaussiens) via une approche de discrétisation tronquée, supprimant le besoin d'un intervalle de support pré-spécifié.

Résultats

• Théorème 1 (Support Borné) : Établit l'optimalité asymptotique pour $\rho$-NPTS sur $P(B)$ sous la seule condition de continuité.
• Théorème 2 (Sub-Gaussien) : Établit l'optimalité asymptotique pour $\rho$-NPTSSG sur $P(B, \sigma)$.
• Validation Expérimentale : L'article présente quatre expériences validant la théorie :
  1. $\rho$-NPTS suit la borne inférieure d'optimalité d'instance pour la CVaR sur des bras de type Beta, surpassant la base de référence Risk-LCB (qui possède une garantie de $\log^2 n$).
  2. $\rho$-NPTS atteint un regret de $O(\log n)$ pour le ratio de Sharpe sur des bras de type normale tronquée, un cas où aucun algorithme préalable ne fournissait de garanties en raison de la non-Lipschitzianité.
  3. L'algorithme gère des fonctionnelles composites (ex: $0.5 \text{CVaR} + 0.5 \text{Sharpe}$) sans modification.
  4. $\rho$-NPTSSG converge vers la borne inférieure d'optimalité d'instance pour les bras gaussiens, égalant les performances de l'algorithme spécialisé Normal-Gamma Thompson Sampling (Shah et al. [2025]) sans supposer des récompenses gaussiennes.

Signification et Revendications
L'article prétend régler le statut théorique du Thompson Sampling non paramétrique pour les bandits averses au risque. Il démontre que ces algorithmes ne sont pas seulement des heuristiques empiriques mais sont prouvables et asymptotiquement optimaux.

La signification réside dans l'assouplissement des hypothèses :

• Les praticiens peuvent utiliser les observations brutes sans pré-spécifier une grille de récompense ou ajuster une taille d'alphabet.
• La méthode s'applique à une classe strictement plus large de fonctionnelles de risque (incluant le ratio de Sharpe) et de classes de distribution (sub-gaussiennes) que les méthodes optimales précédentes.
• Le résultat subsume le travail concomitant de Shah et al. [2025] en fournissant une constante d'optimalité d'instance plus fine pour le ratio de Sharpe sans nécessiter de priors conjugués ou d'hypothèses paramétriques.

Les auteurs notent que l'hypothèse de densité bornée est nécessaire pour les bornes de probabilité de bin utilisées dans la preuve et n'est pas tenue pour les distributions avec des masses ponctuelles (ex: Bernoulli), pour lesquelles le $\rho$-MTS paramétrique reste la solution complémentaire. Les directions de travaux futurs identifiées incluent les bandits contextuels, les récompenses à queues lourdes et les distributions discrètes.