Résumé Technique : Algorithme Pratique et Optimal pour les Bandits Contextuels Linéaires à Mises à Jour de Paramètres Rares

1. Cadre du Problème

Cet article traite du problème des bandits contextuels linéaires stochastiques sous la contrainte de mises à jour de paramètres rares. Dans ce cadre, un agent sélectionne séquentiellement des actions (bras) à partir d'un ensemble variable de $K$ bras, chacun caractérisé par un vecteur de caractéristiques de dimension $d$. La récompense est générée par un modèle linéaire inconnu $\theta^*$ plus un bruit.

La contrainte centrale est que l'apprenant ne peut incorporer le retour de la récompense dans son estimation de paramètre (par exemple, via une régression ridge ou le MLE) qu'à un petit nombre de moments de mise à jour, $B$, sur un horizon $T$. Crucialement, les auteurs distinguent cela des cadres strictement par lots (batched). Bien que les récompenses soient retardées jusqu'à la fin d'un intervalle, les auteurs soutiennent que, dans les déploiements pratiques, les contextes sont observés en ligne avant que les actions ne soient choisies. Par conséquent, l'apprenant devrait être autorisé à effectuer des mises à jour sans récompense au sein de l'intervalle (par exemple, mettre à jour les matrices de Gram ou les ensembles d'élimination sur la base des contextes observés), même si le réentraînement lourd des paramètres est différé. Cette distinction comble le fossé entre les méthodes entièrement séquentielles et les méthodes strictement par lots qui interdisent l'adaptativité intra-intervalle.

L'objectif est de concevoir des algorithmes qui :

1. Atteignent un regret minimax-optimal dans les régimes à petit $K$ ($K \le O(ed)$) et à grand $K$ ($K \ge \Omega(ed)$).
2. Opèrent avec seulement $O(\log \log T)$ mises à jour de paramètres.
3. Évitent les sous-programmes coûteux en calcul, spécifiquement le plan G-optimal (G-optimal design), qui constitue un goulot d'étranglement pour les algorithmes optimaux précédents strictement par lots.

2. Méthodologie

Le papier propose deux algorithmes principaux pour les bandits contextuels linéaires et une extension pour les bandits linéaires généralisés.

BLCE-G (Bandit Contextuel Linéaire à Feedback par Lots avec Élimination et Plan G-optimal)

Cet algorithme combine l'élimination de bras avec une stratégie de plan G-optimal proche de l'optimalité.

• Structure : Il opère sur une grille statique d'intervalles.
• Mécanisme : Au sein de chaque intervalle, les tours sont divisés en phases. La première phase utilise un plan G-optimal proche pour échantillonner les bras, garantissant un gain d'information suffisant. Les phases suivantes impliquent la sélection de la direction la plus informative par rapport à la matrice de Gram actuelle, puis une sélection gourmande basée sur la dernière estimation.
• Élimination : Les bras sous-optimaux sont éliminés de manière itérative en utilisant les estimations des intervalles précédents.
• Complexité : Il conserve la rigueur théorique du plan G-optimal mais relaxe le calcul exact vers une version quasi-optimale calculable en $O(Kd^3)$, mise à jour via Sherman-Morrison.

BLCE (Bandit Contextuel Linéaire à Feedback par Lots avec Élimination)

Cet algorithme supprime entièrement l'étape de plan G-optimal pour améliorer l'efficacité computationnelle.

• Structure : Similaire à la grille statique et au cadre d'élimination de bras de BLCE-G.
• Mécanisme : Au lieu du plan G-optimal, BLCE repose sur une exploration pilotée par l'incertitude (sélection du bras ayant la norme maximale dans l'inverse de la matrice de Gram) combinée à l'élimination de bras. La phase d'exploration est prolongée pour compenser l'absence de plan explicite.
• Signification : C'est le premier algorithme de bandit contextuel linéaire avec mises à jour rares à atteindre l'optimalité minimax sans dépendre du plan G-optimal, réduisant la complexité temporelle à $O(Kd^2 T \log \log T)$.

BGLE (Bandit Contextuel Linéaire Généralisé à Feedback par Lots avec Élimination)

Cette extension applique les principes de BLCE aux récompenses linéaires généralisées (distributions de la famille exponentielle).

• Mécanisme : Il utilise l'Estimation du Maximum de Vraisemblance (MLE) aux limites des intervalles et emploie une matrice de Gram pondérée pendant l'exploration pour gérer la non-linéarité.
• Caractéristique clé : Les bornes de regret sont indépendantes du paramètre de courbure maximal $\kappa$, qui peut diverger en cas de saturation, s'appuyant plutôt sur la courbure inverse moyenne $\hat{\kappa}$.

3. Contributions Clés

Le papier apporte les contributions spécifiques suivantes :

1. Bornes de Regret les plus Serrées sous Mises à Jour Rares : Les auteurs introduisent BLCE-G, qui atteint un regret minimax-optimal (à des facteurs polylogarithmiques près) dans les régimes à petit $K$ et à grand $K$ en utilisant seulement $O(\log \log T)$ mises à jour de paramètres. Cela correspond aux bornes inférieures minimax connues $\Omega(\sqrt{dT} \log K)$ et $\Omega(d\sqrt{T})$.
2. Optimalité sans Plan G-Optimal : BLCE est présenté comme le premier algorithme atteignant un regret minimax-optimal dans le cadre des mises à jour rares sans recourir à l'étape coûteuse du plan G-optimal, offrant la plus faible complexité temporelle connue parmi les algorithmes optimaux.
3. Redéfinition du Paysage de l'Adaptativité : Le papier catégorise et distingue explicitement trois contextes opérationnels :
   • Entièrement Séquentiel : Pleine adaptativité à chaque tour.
   • Strictement par Lots (Strictly Batched) : Aucune adaptativité intra-intervalle pour les contextes (les règles d'action sont fixées au début de l'intervalle).
   • Mises à Jour de Paramètres Rares : Restreint les mises à jour dépendantes des récompenses mais permet une adaptativité intra-intervalle sans dépendance à la récompense.
     Les auteurs soutiennent que le régime des "Mises à jour de paramètres rares" est le cadre pratique qui évite les goulots d'étranglement computationnels du traitement par lots strict tout en maintenant l'efficacité statistique.
4. Extension Linéaire Généralisée : L'extension aux bandits linéaires généralisés (BGLE) fournit des garanties de regret quasi-optimales qui sont indépendantes du paramètre de courbure maximal $\kappa$, une amélioration significative par rapport aux travaux antérieurs où les termes transitoires dépendaient de $\kappa$.
5. Supériorité Pratique : Les résultats expérimentaux démontrent que les algorithmes proposés surpassent systématiquement les bases de référence de pointe (ex: RS-OFUL, BatchLinUCB-DG, SoftBatch) en termes de regret et de temps d'exécution, particulièrement dans les configurations à haute dimension ou à grand $K$ où les méthodes optimales précédentes souffrent d'une complexité exponentielle ou de haute puissance polynomiale.

4. Résultats

• Bornes de Regret :
  • BLCE-G : $O(\sqrt{dT}(\sqrt{\log(KT)} \wedge \sqrt{d} + \log T)\sqrt{\log d \log \log T})$.
  • BLCE : $O(\sqrt{dT}(\sqrt{\log(KT)} \wedge \sqrt{d} + \log T)\sqrt{\log T \log \log T})$.
  • BGLE : Terme principal $O(RS\sqrt{d(d+\log T)T \log T \log \log T / \hat{\kappa}})$.
• Mises à Jour de Paramètres : Tous les algorithmes opèrent avec $O(\log \log T)$ mises à jour.
• Complexité Temporelle :
  • BLCE-G : $O(Kd^2 T (d + \log \log T))$.
  • BLCE : $O(Kd^2 T \log \log T)$.
  • BGLE : $O(Kd^2 T \log \log T + C_{opt}^{tot})$.
• Performance Empirique : Dans les expériences avec $T=10\,000$, BLCE et BLCE-G ont obtenu le regret cumulé le plus bas sur diverses paires $(K, d)$. BLCE a démontré le temps d'exécution le plus rapide, souvent comparable aux bases de référence sous-optimales, tandis que les méthodes par lots strictement optimales (comme celles dépendant du plan G-optimal) affichaient un temps d'exécution "Exponentiel" ou des coûts nettement plus élevés.

5. Signification et Revendications

Le papier affirme que ses résultats unifient la théorie et la pratique dans les bandits contextuels linéaires et linéaires généralisés. La principale signification réside dans la démonstration que une adaptativité limitée aux récompenses n'impose pas une exploration pré-planifiée coûteuse en calcul. En permettant un traitement léger et sans dépendance à la récompense des contextes au sein des intervalles, les auteurs montrent qu'il est possible de :

• Conserver l'optimalité statistique des algorithmes à mises à jour rares.
• Éliminer le goulot d'étranglement computationnel dominant (plan G-optimal) qui a entravé le déploiement des méthodes par lots strictes.
• Fournir des algorithmes qui sont à la fois théoriquement solides (minimax-optimaux) et pratiquement efficaces (faible temps d'exécution), les rendant adaptés aux pipelines du monde réel où le réentraînement du modèle est coûteux mais l'observation du contexte est continue.

Les auteurs restent modestes quant aux bornes théoriques, notant que bien que BLCE-G possède une borne de regret minimax strictement plus petite en théorie, les résultats empiriques montrent que BLCE est souvent comparable ou supérieur dans des environnements stochastiques bénins, suggérant qu'une exploitation gourmande peut être extrêmement efficace même avec des mises à jour rares.