Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Résumé Technique : Bandits Contextuels pour Appareils à Ressources Limitées utilisant l'Apprentissage Probabiliste

Énoncé du Problème
Les bandits contextuels (BC) sont fondamentaux pour la prise de décision séquentielle en ligne dans des services adaptatifs tels que les recommandations personnalisées et l'informatique en périphérie (edge computing). Cependant, le déploiement d'agents BC directement sur des appareils à ressources limitées (par exemple, mobiles, wearables, dispositifs aériens) présente des défis significatifs. Les algorithmes BC linéaires standards, bien qu'efficaces, nécessitent le maintien de matrices de covariance qui évoluent de manière quadratique avec la dimensionnalité du contexte ($O(Nd^2)$ en mémoire) et impliquent des opérations d'algèbre linéaire coûteuses en calcul ($O(d^3)$ en complexité), les rendant inadaptés aux appareils soumis à des contraintes strictes de mémoire, de calcul et d'énergie.

Des travaux récents ont introduit les Bandits Contextels Hyperdimensionnels (HD-BC), qui exploitent l'Informatique Hyperdimensionnelle (HDC) pour résoudre des problèmes de BC dans des espaces de haute dimension en utilisant des opérations vectorielles légères. Bien que HD-BC offre une complexité temporelle linéaire et une évolutivité améliorée, son implémentation standard repose sur des mises à jour par accumulation où les composantes des vecteurs d'action croissent indéfiniment. Cela nécessite des types numériques de haute précision (par exemple, des flottants 32 bits) pour éviter les débordements, annulant ainsi les gains d'efficacité mémoire. Une variante précédente à faible précision, HD-BCBIN, a résolu le débordement en binarisant périodiquement les vecteurs et en réinitialisant les compteurs. Cependant, cette binarisation déterministe élimine les informations de magnitude accumulées, entraînant une dégradation des performances, en particulier dans des régimes bruyants ou à faible disponibilité de données.

Méthodologie : HD-BC Probabiliste (HD-BCPROB)
Cet article propose HD-BCPROB, une variante à faible précision de HD-BC qui remplace l'accumulation déterministe par une règle de mise à jour probabiliste. L'innovation centrale consiste à borner l'apprentissage par conception plutôt que par des réinitialisations périodiques.

1. Composantes Entières Bornées : Au lieu de permettre aux composantes vectorielles de croître indéfiniment, HD-BCPROB contraint chaque composante à une plage d'entiers prédéfinie $[-\kappa, +\kappa]$. Cela permet l'utilisation de compteurs entiers saturés de faible précision (par exemple, 2, 3 ou 4 bits).
2. Règle de Mise à Jour Probabiliste : Pour permettre l'apprentissage dans ces limites strictes sans perdre d'information, l'algorithme remplace la mise à jour basée sur la magnitude par une mise à jour basée sur la fréquence. À chaque pas de temps $t$, seule une sous-ensemble aléatoire des composantes vectorielles est mise à jour en fonction d'une probabilité décroissante dans le temps $\alpha_t$.
   • La probabilité de mise à jour est définie comme $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • Pour chaque composante $i$, une valeur aléatoire $m_{t,i} \sim U(0, 1)$ est échantillonnée. Une mise à jour n'a lieu que si $m_{t,i} \leq \alpha_t$.
   • Lorsqu'une mise à jour se produit, la composante est incrémentée ou décrémentée de $\pm 1$ (basé sur la liaison des vecteurs hyperréels du contexte et de la récompense) puis limitée à la plage $[-\kappa, +\kappa]$.
3. Mécanisme : Cette approche implémente efficacement une "marche aléatoire saturante". En contrôlant la fréquence des mises à jour plutôt que la magnitude des valeurs stockées, l'agent conserve les informations historiques avec une haute fidélité même dans des composantes de faible précision. Cela élimine le besoin de compteurs auxiliaires et d'étapes de binarisation périodiques requis par HD-BCBIN.

Contributions Clés

• Innovation Algorithmique : Introduction d'une règle de mise à jour probabiliste pour HD-BC permettant l'utilisation de composantes entières saturées de faible précision sans perte périodique d'information.
• Efficacité des Ressources : La méthode réduit l'empreinte mémoire en éliminant le besoin de compteurs auxiliaires et de copies binarisées séparées des vecteurs requis par les variantes précédentes à faible précision. Elle réduit également le coût computationnel car le nombre attendu de mises à jour diminue au fil du temps en raison de la probabilité décroissante $\alpha_t$.
• Préservation des Performances : L'approche maintient la qualité de classement des actions en préservant les informations de magnitude via la fréquence des mises à jour, évitant ainsi la dégradation associée à la binarisation stricte.

Résultats Expérimentaux
Les auteurs ont évalué HD-BCPROB en utilisant une évaluation hors politique sur des benchmarks synthétiques standardisés de BC via le Pipeline de Bandits Ouverts (OBP), en le comparant à :

1. LinEPS : BC linéaire standard (référence).
2. HD-BCREAL : HD-BC à valeurs réelles.
3. HD-BCBIN : HD-BC binarisé avec réinitialisations périodiques.
4. HD-BCPROB : La variante probabiliste proposée.

Les principales conclusions incluent :

• Supériorité sur les Variantes Binarisées : HD-BCPROB surpasse systématiquement HD-BCBIN à des niveaux de précision égaux sur toutes les configurations testées (variations de la dimensionnalité du contexte $d$ et du nombre d'actions $N$). Plus précisément, une implémentation HD-BCPROB à 3 bits a amélioré les récompenses cumulées d'environ 5,8 % par rapport à une implémentation HD-BCBIN à 3 bits.
• Approche des Performances à Valeurs Réelles : Une configuration HD-BCPROB à 3 bits (avec un seuil de saturation $\kappa=3$) a atteint des performances approchant la référence HD-BCREAL à valeurs réelles, avec un écart moyen de seulement 2,5 %.
• Rendements Décroissants sur la Précision : L'augmentation de la précision de 3 à 4 bits a produit des rendements décroissants ou légèrement négatifs pour HD-BCPROB, suggérant que 3 bits suffisent à capturer la qualité des actions dans ces paramètres synthétiques.
• Efficacité Mémoire : HD-BCPROB nécessite strictement moins de mémoire que HD-BCBIN à la même largeur de bits car il ne nécessite pas de mécanismes auxiliaires (compteurs et copies binarisées temporaires). Contrairement au BC linéaire, son empreinte mémoire reste constante par rapport à la dimensionnalité du contexte.

Signification et Revendications
L'article revendique que le HD-BC probabiliste résout le compromis entre l'empreinte mémoire et la perte d'information inhérent aux approches hyperdimensionnelles précédentes. En passant de l'accumulation basée sur la magnitude aux mises à jour probabilistes basées sur la fréquence, la méthode permet le déploiement d'agents adaptatifs et autonomes sur des appareils disposant de budgets stricts en énergie, mémoire et calcul. Les auteurs positionnent HD-BCPROB comme une alternative convaincante pour l'intelligence en périphérie, offrant un moyen d'atteindre des performances de prise de décision quasi optimales avec des exigences de ressources considérablement réduites par rapport aux algorithmes linéaires standards et aux variantes hyperdimensionnelles à faible précision existantes.

Les travaux futurs identifiés par les auteurs incluent l'évaluation de l'approche sur des ensembles de données de bandits réels enregistrés, des tests sous des distributions de récompenses plus complexes, et l'obtention de mesures directes de latence et d'énergie sur du matériel embarqué pour étayer les revendications de déploiement en périphérie.