Résumé Technique : Bandits Non Linéaires avec Bruit à Queue Lourde

Définition du Problème

Cet article traite du défi de la prise de décision séquentielle dans les Bandits Linéaires Généralisés (GLB) et les Bandits Non Linéaires (NB) sous des conditions de bruit à queue lourde. Les algorithmes de bandits traditionnels supposent souvent des distributions de récompense à queue légère (par exemple, sub-gaussiennes), qui échouent dans des scénarios réels comme les marchés financiers, les recommandations personnalisées et les traitements médicaux où les récompenses présentent des queues lourdes (par exemple, des distributions de Pareto ou de Student's t).

Le problème central implique qu'un apprenant sélectionne une action $X_t$ dans un ensemble faisable à chaque tour $t$ pour maximiser la récompense espérée cumulée. Le modèle de récompense est défini par :
$$r_t = \mu(\langle X_t, \theta^* \rangle) + \varepsilon_t$$
où $\mu$ est une fonction de lien, $\theta^*$ est un paramètre inconnu, et $\varepsilon_t$ est un bruit possédant des moments $(1+\epsilon)$ bornés ($\epsilon \in (0, 1]$), plutôt qu'une variance bornée. L'objectif est de minimiser le regret cumulé $R(T)$ tout en maintenant l'efficacité computationnelle et la robustesse face aux valeurs aberrantes.

L'article étend cette investigation à deux contextes plus complexes :

1. GLB par morceaux (Piecewise GLB) : Où le paramètre inconnu $\theta^*$ est constant par morceaux à travers différentes régions de l'espace des actions.
2. Bandits Non Linéaires Généraux : Où la fonction de récompense $b(X)$ est une fonction non linéaire générale, non restreinte à une structure de fonction de lien spécifique, nécessitant potentiellement un « lever affine » (affine lifting) pour être projetée dans un espace linéaire de dimension supérieure.

Méthodologie

Les auteurs proposent une série d'algorithmes basés sur le cadre de la Descente de Miroir en Ligne (OMD - Online Mirror Descent), utilisant une Perte de Huber Étendue pour gérer le bruit à queue lourde.

1. GLB-EHM (Generalized Linear Bandit with Extended Huber Method)

• Mécanisme Central : L'algorithme remplace l'Estimation du Maximum de Vraisemblance (MLE) standard par une fonction de perte de Huber étendue. Cette perte combine le comportement quadratique de la perte $L_2$ pour les petites erreurs et le comportement linéaire de la perte $L_1$ pour les grandes erreurs, offrant ainsi une robustesse contre les valeurs aberrantes.
• Mise à jour en un seul passage (One-Pass Update) : Une caractéristique clé est le mécanisme de mise à jour en un seul passage. L'algorithme met à jour les paramètres en utilisant la formule de Sherman-Morrison et la décomposition de projection, atteignant une complexité computationnelle de $O(1)$ par tour par rapport à l'horizon temporel $T$ (spécifiquement $O(d^3)$ par étape, indépendamment de $T$).
• Élimination de Paramètre : La méthode introduit un réglage de paramètre spécifique pour éliminer la dépendance vis-à-vis du paramètre sensible $\kappa$ (borne inférieure de la dérivée de la fonction de lien) dans le terme de tête du regret, une dépendance présente dans les travaux antérieurs.

2. PGLB-EHM (Piecewise GLB-EHM)

• Adaptation : Pour les scénarios où la caractéristique contextuelle $\theta^*$ est constante par morceaux, l'algorithme maintient des estimations séparées pour chaque région $A_i$.
• Stratégie : Il emploie une approche de « distinction et exploitation ». En garantissant que la région optimale produit une récompense significativement plus élevée (par une constante $a$) que les régions sous-optimales, l'algorithme identifie la zone optimale avec un coût temporel borné et se concentre sur l'exploration de celle-ci.

3. NB-EHM (Nonlinear Bandit with Extended Huber Method)

• Méthode de Bisection : Pour gérer les fonctions de récompense non linéaires générales $b(X)$, l'algorithme emploie une méthode de bisection pour affiner récursivement l'espace faisable (boule unité) en sous-régions plus petites.
• Restriction de l'Exploration : Un composant critique est la limite de temps $T(A) \propto 1/d(A)^2$ assignée à chaque région $A$, où $d(A)$ est la largeur de la région. À mesure que les régions deviennent plus fines, le temps d'exploration autorisé augmente, permettant à l'erreur d'estimation de diminuer automatiquement.
• Levée Affine (Affine Lifting) : Pour les fonctions non linéaires générales qui ne s'ajustent pas naturellement à la structure par morceaux, l'article utilise une approche de levée affine. Cela transforme le problème en un espace de dimension supérieure où la fonction peut être traitée de manière similaire au cas non linéaire spécial, permettant l'application du cadre NB-EHM.

Contributions Clés

1. Algorithme de GLB Robuste (GLB-EHM) : L'article introduit le premier algorithme pour les GLB sous bruit à queue lourde qui atteint un ordre de regret presque optimal de $\tilde{O}(T^{\frac{1}{1+\epsilon}})$ tout en maintenant une complexité computationnelle de $O(1)$ par tour. Il améliore les méthodes existantes en supprimant la dépendance au paramètre $\kappa$ dans le coefficient principal.
2. Extensions Piecewise et Non Linéaires : Les auteurs étendent avec succès le cadre robuste aux GLB par morceaux et à une classe spéciale de Bandits Non Linéaires. Ils prouvent que l'ordre du regret reste sous-linéaire ($\tilde{O}(T^\alpha)$ avec $\alpha < 1$) même lorsque la structure sous-jacente est constante par morceaux ou non linéaire lisse.
3. Garanties Théoriques : L'article fournit une analyse théorique rigoureuse, établissant des bornes de confiance à haute probabilité pour l'estimation des paramètres et dérivant des bornes supérieures de regret qui correspondent aux bornes inférieures connues (à un facteur logarithmique près) pour le cas linéaire.
4. Efficacité Computationnelle : Contrairement aux approches basées sur les noyaux (kernels) ou les réseaux de neurones pour les bandits non linéaires qui souffrent souvent de coûts de $O(T^2)$ ou $O(T^3)$, les méthodes proposées maintiennent une faible complexité computationnelle adaptée aux applications à grande échelle.

Résultats

• Bornes Théoriques :
  • Pour GLB-EHM, le regret est borné par $\tilde{O}(d(1+KS)\nu T^{\frac{1}{1+\epsilon}})$, ce qui est presque optimal par rapport à la borne inférieure $\Omega(dT^{\frac{1}{1+\epsilon}})$.
  • Pour PGLB-EHM, l'ordre du regret reste $\tilde{O}(T^{\frac{1}{1+\epsilon}})$, avec des constantes dépendant du nombre de morceaux $m$ et de l'écart $a$.
  • Pour NB-EHM, le regret est borné par $\tilde{O}(T^\alpha)$, où $\alpha = \frac{\gamma+1}{\gamma+2} + \frac{(d+2)(1-\epsilon)}{2(\gamma+2)(1+\epsilon)}$ et $\gamma = (d+2)(C_2-1)+1$. Sous des conditions spécifiques ($\epsilon > \frac{d}{d+4}$), cela garantit un regret sous-linéaire.
• Performances Empiriques : Des simulations numériques ont été menées pour tous les algorithmes proposés.
  • GLB-EHM a été testé sur un modèle logit avec un bruit de type Student's t, démontrant une performance robuste avec un temps d'exécution moyen de 11,25 secondes.
  • Les simulations de NB-EHM ont montré une convergence vers le point optimal et une croissance de regret sous-linéaire, validant l'analyse théorique.

Signification et Revendications

L'article affirme que sa principale importance réside dans le pont jeté entre l'efficacité statistique et la complexité computationnelle dans le contexte des bandits non linéaires à queue lourde.

• Robustesse : Il démontre que la robustesse au bruit à queue lourde peut être obtenue sans sacrifier les garanties de regret sous-linéaire typiques des contextes à queue légère.
• Généralité : En allant au-delà des hypothèses restrictives des Modèles Linéaires Généralisés (GLM), des Espaces de Hilbert à Noyau Reproduisant (RKHS) ou des Noyaux de Tangente de Neurones (NTK), le NB-EHM proposé offre un cadre plus général pour les bandits non linéaires.
• Scalabilité : La complexité de $O(1)$ par tour (par rapport à $T$) rend ces algorithmes scalables pour de longs horizons temporels, répondant à un goulot d'étranglement majeur des méthodes de bandits non linéaires existantes.

Les auteurs concluent que bien qu'ils aient établi des bornes de regret sous-linéaires, des travaux futurs sont nécessaires pour établir des bornes inférieures de regret pour le cas non linéaire général et pour assouplir les hypothèses telles que la continuité de Lipschitz vers la continuité de Hölder.