Stochastic Linear Bandits with Parameter Noise

Résumé technique : Bandits linéaires stochastiques avec bruit de paramètre

Définition du problème
Ce travail examine le modèle des bandits linéaires stochastiques avec bruit de paramètre. Dans ce cadre, un apprenant interagit avec un environnement sur un horizon temporel $T$ en sélectionnant des actions $a_t$ à partir d'un ensemble d'actions $\mathcal{A} \subseteq \mathbb{R}^d$. Contrairement au modèle de bruit additif standard où la récompense est $X_t = a_t^\top \theta^\star + \eta_t$ (avec $\theta^\star$ fixe et un bruit $\eta_t$), le modèle de bruit de paramètre suppose que la récompense est donnée par $X_t = a_t^\top \theta_t$, où $\theta_t$ est échantillonné de manière i.i.d. à partir d'une distribution fixe et inconnue $\nu$ ayant pour moyenne $\theta^\star$ et pour matrice de covariance $\Sigma$.

L'article met en évidence une distinction clé : dans le modèle de bruit de paramètre, l'apprenant peut influencer la variance de la récompense. Plus précisément, $\text{Var}(X_t) = a_t^\top \Sigma a_t$, alors que dans le modèle de bruit additif, la variance est déterminée uniquement par l'environnement. Les auteurs notent que, bien que le modèle de bruit de paramètre soit un relâchement du modèle de bandits linéaires adversariaux (où $\theta_t$ est choisi par un adversaire), il présente des propriétés structurelles uniques permettant potentiellement des bornes de regret plus serrées que le modèle de bruit additif dans certains contextes géométriques.

Méthodologie et algorithmes
Les auteurs proposent deux algorithmes adaptés à différentes géométries d'ensembles d'actions :

1. VASE (Variance Aware Optimal Design Successive Elimination) :

   • Cible : Ensembles d'actions finis généraux (et ensembles infinis via des arguments de recouvrement).
   • Mécanisme : Un algorithme d'élimination successive qui exploite l'information sur la variance. À chaque phase, il calcule une conception G-optimale $\pi_\ell$ pour sélectionner les actions. Il estime explicitement la variance des actions dans le support de la conception en utilisant un algorithme de règle d'arrêt (SR).
   • Innovation clé : L'algorithme utilise les variances estimées de deux manières : pour réduire le nombre d'échantillons nécessaires à l'exploration et comme poids dans un estimateur des moindres carrés pondérés. Ce pondération garantit que la covariance de l'estimateur reste contrôlée même avec moins d'échantillons, conduisant à des bornes de regret dépendantes de la variance.

2. VALEE (Variance Aware Linear Explore-Exploit) :

   • Cible : Boules unitaires $\ell_p$ où $p \in (1, 2]$ (et leurs normes duales $q \ge 2$).
   • Mécanisme : Un algorithme simple d'exploration-exploitation.
     • Exploration : L'algorithme joue les vecteurs de base standards $e_i$. Il estime le vecteur moyen $\theta^\star$ composante par composante en utilisant la technique de la médiane des moyennes (MoM). Si la matrice de covariance $\Sigma$ est inconnue, il estime d'abord les variances des vecteurs de base.
     • Exploitation : Une fois que l'erreur d'estimation est suffisamment petite par rapport à la variance et à l'horizon temporel, l'algorithme se fixe sur une action $\hat{a}$ dérivée de la moyenne estimée $\hat{\theta}$, spécifiquement $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • Innovation clé : L'analyse exploite la géométrie de la boule $\ell_p$ et la structure du bruit de paramètre. Les auteurs montrent que l'exploration des vecteurs de base produit une erreur d'estimation proportionnelle à $\sqrt{\sigma^2(e_i)}$, ce qui est plus serré que la borne standard $\epsilon$ dans les modèles de bruit additif. Cela permet à l'algorithme d'atteindre des bornes de regret optimales dépendant de la structure de variance de la distribution de récompense.

Résultats clés
L'article établit à la fois des bornes supérieures et inférieures, démontrant que les algorithmes proposés sont optimaux au sens minimax (à des facteurs logarithmiques près) pour des configurations spécifiques.

• Ensembles d'actions finis généraux ($K$ actions) :

  • Borne supérieure : VASE atteint un regret de $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$, où $M_\sigma$ est une quantité dépendante de la variance bornée par $\max_a \sigma^2(a)$.
  • Borne inférieure : Une borne inférieure de $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ est prouvée, montrant que la borne supérieure est serrée à des facteurs logarithmiques près lorsque $\log(K) \approx d$.

• Boules unitaires $\ell_p$ ($p \le 2$) :

  • Covariance connue : VALEE atteint un regret de $\tilde{O}(d + \sqrt{dT \sigma^2_q})$, où $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. Cela est démontré comme optimal via une borne inférieure correspondante de $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$.
  • Covariance inconnue : VALEE incorpore un terme additif supplémentaire, résultant en un regret de $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$. Les auteurs notent que ce terme additif provient de la phase d'estimation de la variance.

• Boules unitaires $\ell_p$ ($p > 2$) :

  • L'article fournit une borne inférieure de $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, correspondant aux bornes inférieures connues pour le cadre adversarial dans ces géométries.

Signification et affirmations
L'article prétend résoudre un « cas curieux » concernant les bandits linéaires où le modèle de bruit additif produit souvent des bornes de regret pires ($d\sqrt{T}$) que le modèle adversarial ($\sqrt{dT}$) pour des ensembles d'actions spécifiques comme la boule unitaire $\ell_2$. Les auteurs démontrent que le modèle de bruit de paramètre s'aligne davantage sur l'intuition selon laquelle les modèles stochastiques devraient être plus faciles que les modèles adversariaux.

• Bornes plus serrées : Pour les boules $\ell_p$ avec $p \le 2$, le modèle de bruit de paramètre permet des bornes de regret de l'ordre de $\sqrt{dT \sigma^2_q}$, qui peuvent être significativement plus petites que la borne $d\sqrt{T}$ typique des modèles de bruit additif lorsque la variance est faible.
• Avantage structurel : Les résultats soulignent que la linéarité de la réalisation (et non seulement de l'espérance) et la capacité de l'apprenant à influencer la variance sont cruciales pour atteindre ces bornes améliorées.
• Simplicité : De manière surprenante, le regret optimal pour les boules $\ell_p$ ($p \le 2$) est atteignable en utilisant un algorithme d'exploration-exploitation très simple (VALEE), contrairement aux algorithmes de conception optimale complexes souvent requis dans les contextes de bruit additif.

Les auteurs concluent que, bien que leurs résultats pour $p \le 2$ soient optimaux (à des termes logarithmiques près) lorsque la covariance est connue, le cas de covariance inconnue laisse un écart ouvert (le terme $T^{1/3}$) que les travaux futurs pourraient traiter. Ils laissent également la conception d'un algorithme correspondant à la borne inférieure pour $p > 2$ comme une question ouverte.