Sharp analysis of linear ensemble sampling

Résumé Technique : Analyse Précise de l'Échantillonnage d'Ensemble (Ensemble Sampling)

Configuration du Problème
Cet article étudie l'Échantillonnage d'Ensemble (ES) dans le cadre des bandits linéaires stochastiques. Dans ce cadre, un apprenant interagit avec un environnement sur $n$ tours, sélectionnant des actions $X_t$ issues d'un ensemble fermé $\mathcal{X} \subset \mathbb{R}^d$ (typiquement la boule unité) afin de maximiser la récompense cumulée. La récompense suit un modèle linéaire $Y_t = \langle X_t, \theta^* \rangle + \eta_t$, où $\theta^*$ est un paramètre inconnu et $\eta_t$ est un bruit subgaussien. L'objectif est de minimiser le pseudo-regret à $n$ étapes, défini comme la différence entre la récompense cumulée d'une politique optimale et celle de l'apprenant.

Bien que le Thompson Sampling (TS) soit la référence pour l'exploration dans ce contexte, atteignant un regret de haute probabilité de $\tilde{O}(d^{3/2}\sqrt{n})$, l'ES a historiquement accusé un retard. Les analyses précédentes de l'ES dans les bandits linéaires exigeaient soit des tailles d'ensemble proportionnelles au nombre d'actions (ce qui les rendait inadaptées aux ensembles d'actions infinis), soit obtenaient des bornes de regret sous-optimales de $\tilde{O}(d^{5/2}\sqrt{n})$, même avec des tailles d'ensemble proportionnelles à $O(d \log n)$.

Méthodologie
Les auteurs analysent l'ES avec des perturbations gaussiennes standards. L'algorithme maintient un ensemble de $m$ modèles de régression ridge. Chaque modèle $j$ est entraîné sur l'historique des actions et des récompenses, mais avec deux modifications clés :

1. Prior Perturbé : La cible de régularisation est un vecteur aléatoire $\zeta^j$ tiré d'une distribution a priori plutôt que de zéro.
2. Données Perturbées : Les récompenses observées sont gonflées par un bruit gaussien indépendant $\xi^j_t$.

L'apprenant sélectionne un seul modèle uniformément au hasard parmi l'ensemble à chaque tour et choisit l'action maximisant la récompense prédite sous ce modèle.

Le défi technique central abordé est la dépendance induite par l'adaptation : bien que le bruit injecté dans les modèles soit indépendant, les modèles sont couplés car ils sont entraînés sur des données collectées par les propres sélections d'actions de l'ensemble.

Pour surmonter cela, les auteurs emploient une approche d'immersion en temps continu :

1. Représentation par Martingale : Ils identifient les processus de bruit pilotant les paramètres des modèles comme des transformations de martingales diagonales prévisibles de la forme $S_t = \sum D_s \xi_s$, où $D_s$ sont des matrices diagonales prévisibles.
2. Immersion Brownienne : En exploitant la nature gaussienne des perturbations, ils prouvent un lemme de représentation (Théorème 5.3) montrant que ces transformations de martingales en temps discret peuvent être représentées exactement comme des mouvements browniens standards indépendants évalués à des instants aléatoires déterminés par la variation quadratique prévisible de la transformation.
3. Excès Temporel Uniforme : Cette immersion réduit le problème du contrôle du regret à l'analyse des fréquences d'excès uniformes dans le temps de $m$ mouvements browniens indépendants. Plus précisément, ils établissent qu'une fraction suffisante de ces mouvements browniens doit rester au-dessus d'une frontière courbe $c\sqrt{t}$ uniformément au cours du temps. Ceci est réalisé à l'aide d'outils d'analyse stochastique, incluant les changements de temps de Dambis–Dubins–Schwarz, les processus d'Ornstein–Uhlenbeck et les estimations de franchissement de frontière.

Contributions Clés

1. Borne de Regret Précise : L'article établit qu'avec une taille d'ensemble de $m = \Theta(d \log n)$, l'ES atteint une borne de regret de haute probabilité de $\tilde{O}(d^{3/2}\sqrt{n})$. Cela correspond au taux de regret canonique du Thompson Sampling.
2. Efficacité Computationnelle : Contrairement aux résultats précédents qui exigeaient des tailles d'ensemble proportionnelles au nombre d'actions (par exemple, $m = \Omega(k \log n)$), ce résultat maintient une taille d'ensemble qui ne dépend que linéairement de la dimension $d$, ce qui est adapté aux ensembles d'actions infinis (comme la boule unité) sans coûts de discrétisation exponentiels.
3. Borne Inférieure Théorique : Les auteurs prouvent que si la taille de l'ensemble $m \le d/2$, il existe des instances de bandits linéaires où l'ES subit un regret linéaire, démontrant que l'échelle en $O(d)$ est nécessaire.
4. Nouvelle Perspective Analytique : Le travail introduit une « lentille de temps continu » pour analyser les algorithmes discrets adaptatifs. En immergeant les martingales discrètes dans des mouvements browniens indépendants, les auteurs isolent l'adaptativité dans les « horloges » (changements de temps), permettant une analyse traitable du problème d'excès auto-normalisé qui était auparavant intraitable avec des méthodes purement discrètes.

Résultats

• Théorème 4.1 : Pour $m \ge 2000 d \log(n/\delta)$ et des paramètres de réglage spécifiques, le regret à $n$ étapes $R_n$ est borné par $\tilde{O}(d^{3/2}\sqrt{n})$ avec une probabilité d'au moins $1 - 4\delta$.
• Théorème 4.2 : Si $m \le d/2$, l'ES échoue à atteindre un regret sous-linéaire pour certaines instances de problèmes, confirmant la robustesse de l'exigence de taille d'ensemble.
• Comparaison : Les résultats comblent l'écart entre l'ES et le TS en termes d'échelle de regret tout en maintenant un surcoût computationnel (coût par tour) comparable aux autres méthodes, à condition que $m = \tilde{O}(d)$.

Signification et Revendications
L'article affirme que sa principale contribution est de combler l'écart de performance entre l'Échantillonnage d'Ensemble et le Thompson Sampling dans le cadre des bandits linéaires stochastiques. Les auteurs soulignent que leur technique de preuve offre une nouvelle perspective sur l'exploration randomisée, en réduisant un problème complexe d'adaptation en temps discret à un problème d'excès temporel uniforme de mouvements browniens indépendants.

Ils déclarent explicitement qu'ils ne connaissent pas d'autre voie pour obtenir une borne précise de l'ES, soulignant la nouveauté de l'utilisation d'outils de temps continu (spécifiquement l'immersion brownienne exacte) pour résoudre un problème purement en temps discret. Les auteurs font preuve de modestie quant à la portée de leurs outils, notant que bien qu'ils conjecturent que des résultats similaires puissent s'appliquer à d'autres distributions de perturbation (par exemple, Rademacher), prouver cela nécessiterait des outils différents (tels que les immersions de Skorokhod) et reste une direction ouverte. Ils notent également que leur approche repose actuellement sur la structure diagonale des transformations de bruit (multiples scalaires de l'identité), ce qui simplifie l'analyse par rapport aux cas diagonaux généraux.