Résumé Technique : Un Algorithme Conjointement Efficace et Optimal pour les Bandits GLB Hétéroscédastiques avec Corruptions Adversaires

1. Cadre du Problème

Le papier traite du problème des Bandits GLB (Modèles Linéaires Généralisés) Hétéroscédastiques en présence de corruptions adversaires. Ce cadre unifie trois aspects complexes de la prise de décision séquentielle :

1. Modèles Linéaires Généralisés (GLM) : L'espérance de la récompense pour un bras $x_t \in \mathbb{R}^d$ suit un GLM, $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$, où $\mu$ est une fonction de lien inversée connue et $\theta^\star$ est un paramètre inconnu. Ce cadre englobe les bandits logistiques, de Poisson et gaussiens linéaires.
2. Hétéroscédasticité : La variance de la récompense n'est pas constante mais varie selon les bras et les étapes temporelles. Plus précisément, $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$, où $g(\tau_t)$ est un paramètre de dispersion qui peut varier de manière exogène dans le temps (par exemple, dans les bandits gaussiens) ou être déterminé de manière endogène par le choix du bras (par exemple, dans les bandits logistiques/de Poisson).
3. Corruptions Adversaires : Un adversaire adaptatif manipule la récompense observée à chaque étape $t$ en ajoutant une corruption $c_t$, telle que l'apprenant observe $\tilde{r}_t = r_t + c_t$. L'adversaire opère sous une contrainte de budget total $\sum_{t=1}^T |c_t| \le C$.

L'objectif est de minimiser le pseudo-regret cumulé, défini comme la différence entre la récompense espérée du meilleur bras et celle du bras choisi sur $T$ tours.

2. Méthodologie : HCW-GLB-OMD

Les auteurs proposent HCW-GLB-OMD (Hessian-Confidence Weighted GLB-OMD), un algorithme conçu pour être à la fois efficace sur le plan computationnel et optimal sur le plan statistique. L'algorithme intègre deux composantes principales :

A. Estimateur OMD en Ligne (Online Mirror Descent)

Contra�à les approches précédentes qui reposent sur une estimation de maximum de vraisemblance (MLE) par lots, ce qui crée un décalage d'indice temporel entre les poids locaux et les estimations globales, HCW-GLB-OMD utilise un estimateur OMD en ligne. La mise à jour du paramètre à l'étape $t$ est définie par :
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
où $\tilde{\ell}_t$ est une log-vraisemblance négative pondérée. Cette approche en ligne garantit que l'estimateur, le bras et les poids sont alignés au même instant temporel local, facilitant une analyse rigoureuse des impacts de la corruption.

B. Poids de Confiance Basés sur la Hessienne

Pour obtenir une robustesse face aux corruptions, l'algorithme assigne un poids de confiance $w_t$ à chaque observation basé sur la Hessienne locale (courbure) de la fonction de lien et du paramètre de dispersion :
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
Ici, $\|x_t\|_{H_t^{-1}}$ quantifie l'incertitude le long de la direction de $x_t$.

• Mécanisme : Si une direction de bras est hautement incertaine (norme élevée dans la Hessienne inverse) par rapport à la dispersion, le poids $w_t$ est réduit ($<1$). Cela diminue le poids des observations provenant de directions vulnérables à la manipulation adversaire.
• Conscience de la Courbure : Contra contrairement aux méthodes de bandits linéaires qui utilisent une matrice de conception, cette méthode utilise la Hessienne $\nabla^2 \tilde{\ell}_t$, qui incorpore la pente locale $\dot{\mu}$. Cela permet à l'algorithme de s'adapter à la géométrie spécifique du GLM (par exemple, la saturation dans les bandits logistiques).

C. Séquences de Confiance Robustes aux Corruptions

Les auteurs construisent un ensemble de confiance $C_t(\delta)$ qui prend en compte à la fois l'erreur d'estimation et la corruption adversaire. Le rayon de cet ensemble inclut un terme additif proportionnel au budget de corruption $C$ :
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
La preuve de cette séquence repose sur un argument de supermartingale appliqué à un rapport de vraisemblance pondéré, utilisant la concavité de l'application $x \mapsto x^{w_t}$ pour gérer les cas où $w_t < 1$.

3. Contributions Clés et Résultats

A. Borne Supérieure de Regret

Le papier établit une borne supérieure de regret pour HCW-GLB-OMD sous l'hypothèse que la fonction de lien $\mu$ est auto-concordante (Hypothèse 3). Avec une probabilité d'au moins $1-\delta$, le regret est borné par :
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
Où :

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ est la pente de la fonction de lien au meilleur bras.
• $g_{\max} = \max_t g(\tau_t)$ est la dispersion maximale.
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ est le paramètre de courbure.
• $C$ est le budget total de corruption.

Signification de la Borne :

• Optimalité Instance-Wise : Le terme principal $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ dépend de la pente réelle au meilleur bras, plutôt que de la courbure de pire cas $\kappa$. Cela correspond à la borne inférieure minimax pour les GLB sans corruption.
• Robustesse à la Corruption : Le terme de corruption passe linéairement avec $C$ (spécifiquement $d(g_{\max} + \kappa)C$), ce qui est minimax optimal à un facteur de courbure $\kappa$ près.
• Unification : La borne récupère simultanément les résultats de pointe pour les bandits linéaires hétéroscédastiques, les bandits logistiques et les bandits de Poisson.

B. Borne Inférieure Unifiée de Regret

Les auteurs prouvent une borne inférieure unifiée pour tout GLB hétéroscédastique auto-concordant avec corruptions adversaires :
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
Cette borne inférieure :

• Englobe les bornes inférieures spécifiques existantes pour les bandits logistiques, les bandits linéaires hétéroscédastiques et les bandits linéaires corrompus.
• Confirme que le terme principal de l'algorithme est minimax optimal par instance.
• Démontre que le terme de corruption $dC$ est inévitable, bien que la borne supérieure inclue actuellement un facteur $\kappa$ supplémentaire dans le terme de corruption ($d\kappa C$).

C. Efficacité Computationnelle

Une contribution critique est l'efficacité de l'algorithme. En utilisant la mise à jour OMD en ligne et les mises à jour récursives de la Hessienne, HCW-GLB-OMD atteint une complexité d'espace et de temps de $O(1)$ par itération. Cela contraste avec les algorithmes précédents robustes aux corruptions pour les GLM (par exemple, CR-Eluder-UCB, GAdaOFUL) qui nécessitent souvent une complexité de $O(t)$ en raison du traitement par lots ou de la construction complexe d'ensembles de confiance.

4. Signification et Revendications

Le papier affirme fournir le premier algorithme conjointement efficace et optimal pour les GLB hétéroscédastiques sous corruptions adversaires. Sa principale importance réside dans :

1. Combler le fossé : Il résout le compromis entre efficacité computationnelle et optimalité statistique dans les GLB corrompus. Les travaux précédents soit atteignaient l'optimalité avec un coût computationnel élevé, soit l'efficacité avec des bornes de regret sous-optimales (souvent dépendantes de la courbure de pire cas $\kappa$).
2. Optimalité Instance-Wise : L'algorithme atteint des bornes de regret qui s'adaptent à la difficulté spécifique de l'instance (via $\dot{\mu}_{t,\star}$) plutôt que de reposer sur des hypothèses de pire cas, même en présence de corruptions.
3. Cadre Unifié : Il offre un cadre théorique unique couvrant un large spectre de problèmes de bandits (linéaires, logistiques, de Poisson, hétéroscédastiques) sans nécessiter de modifications algorithmiques spécifiques au problème.

Les auteurs notent un écart restant : le terme de corruption dans la borne supérieure passe à l'échelle de $d\kappa C$, alors que la borne inférieure est de $dC$. Ils conjecturent que le facteur $\kappa$ dans le terme de corruption est un artefact de l'analyse et qu'une borne $O(dC)$ est atteignable, mais cela reste un problème ouvert. De plus, l'analyse actuelle suppose que le paramètre de dispersion $\tau_t$ est connu de l'apprenant ; la gestion d'un $\tau_t$ inconnu est identifiée comme une direction future.