Résumé Technique : DAL : Un cadre pratique et sans a priori (prior-free) de type boîte noire pour les bandits par morceaux stationnaires

1. Définition du Problème

Le papier traite du problème des Bandits par Morceaux Stationnaires (Piecewise Stationary - PS), une classe spécifique d'environnements non stationnaires (NS) où la distribution des récompenses reste constante pendant des intervalles de temps mais subit des changements brusques et inconnus aux points de rupture (change-points). L'objectif est de minimiser le regret dynamique, défini comme la différence entre la récompense cumulative de la politique de l'agent et la récompense cumulative de la meilleure politique possible a posteriori pour chaque intervalle de temps spécifique.

Bien qu'une littérature importante existe sur les bandits stationnaires et diverses configurations non stationnaires (incluant les dérives graduelles), les solutions existantes font face à des limitations critiques :

• Les méthodes basées sur un a priori (ex: fenêtres glissantes, pondération par décroissance) nécessitent la connaissance des paramètres de non-stationnarité (comme le nombre de changements ou les taux de dérive), ce qui est rarement disponible en pratique.
• Les méthodes sans a priori (prior-free) reposent souvent sur la détection de violations des bornes de regret stationnaire (ex: MASTER). Bien que théoriquement optimales en termes d'ordre, ces méthodes sont souvent peu pratiques ; par exemple, MASTER nécessite un horizon de milliards d'étapes avant de pouvoir théoriquement déclencher un redémarrage, ce qui la rend inefficace pour les applications réelles.
• Écarts empiriques : La plupart des méthodes théoriquement optimales manquent de validation empirique complète, particulièrement sur des jeux de données réels et à travers diverses variantes de bandits (Linéaires, GLM, Auto-concordants, à Noyaux et Contextuels).

2. Méthodologie : Le Cadre DAL

Les auteurs proposent le Detection Augmented Learning (DAL), un cadre pratique, sans a priori et de type boîte noire, conçu pour transformer n'importe quel algorithme de bandit stationnaire optimal en ordre en un algorithme de bandit par morceaux stationnaire optimal en ordre.

Architecture Centrale

DAL fonctionne via une structure modulaire comprenant trois composants :

1. Algorithme de Bandit Stationnaire ($B$) : Tout algorithme qui atteint un regret optimal dans des contextes stationnaires (ex: LinUCB, GLM-UCB, SquareCB).
2. Détecteur de Changement ($D$) : Un mécanisme pour identifier les décalages dans la distribution des récompenses. Contrairement aux méthodes sans a priori qui vérifient les violations des bornes de regret, DAL emploie un paradigme de « détection du modèle ». Il surveille des séquences spécifiques d'observations de récompenses pour détecter des décalages de moyenne via des tests statistiques, spécifiquement les tests de Rapport de Vraisemblance Généralisé (GLR) et de Shiryaev-Roberts Généralisé (GSR).
3. Schéma d'Exploration Forcée : Pour garantir que le détecteur reçoive suffisamment de données, DAL force l'exploration sur un ensemble de couverture ($A_e$) fini d'actions.
   • Dans les Bandits Paramétriques (PB), $A_e$ est un sous-ensemble maximal linéairement indépendant d'actions.
   • Dans les Bandits à Noyaux (KB), $A_e$ est construit à partir d'une couverture $\delta_T$ de l'espace d'actions.
   • Dans les Bandits Contextuels (CB), si l'espace d'actions est fini, $A_e$ est défini comme l'ensemble complet des actions $A$.

Logique Opérationnelle (Algorithme 1)

Le cadre fonctionne par cycles (rounds). À chaque étape $t$ :

• Exploration Forcée : Si l'étape actuelle se situe dans une fenêtre d'exploration forcée (déterminée par la taille de l'ensemble de couverture $N_e$ et la fréquence $\alpha_k$), l'agent joue une action de $A_e$ et enregistre la récompense.
• Détection : Le détecteur $D$ analyse l'historique des récompenses pour les actions d'exploration forcée. Si un changement est détecté (c'est-à-dire qu'un décalage de moyenne statistiquement significatif est identifié), le cadre déclenche un redémarrage (restart) :
  • L'algorithme de bandit stationnaire $B$ est réinitialisé.
  • Tous les historiques de récompenses sont effacés.
  • Le compteur de points de rupture est incrémenté.
• Apprentissage Standard : Si aucun changement n'est détecté, l'agent exécute normalement l'algorithme stationnaire $B$, en intercalant potentiellement des étapes d'exploration forcée.

Propriétés Théoriques

Les auteurs établissent que si le détecteur satisfait une propriété de latence spécifique (Propriété 4.1, où la latence de détection suit une échelle en $O(\log T)$), DAL atteint un regret optimal en ordre dans les environnements PS. Plus précisément, la borne de regret correspond à la borne inférieure minimax $\tilde{\Omega}(\sqrt{N_T T})$ (où $N_T$ est le nombre de changements), transférant de manière fluide les garanties de regret stationnaire de l'algorithme $B$ entrant vers le contexte non stationnaire.

3. Contributions Clés

1. Premier Cadre Pratique Sans A Priori de Type Boîte Noire : DAL est présenté comme le premier cadre pour les bandits PS généraux qui soit à la fois sans a priori et pratiquement applicable, évitant les horizons prohibitifs des méthodes comme MASTER.
2. Paradigme « Détecter le Modèle » : Le papier introduit un changement fondamental, passant de la détection de « violations de bornes de regret » à la détection de « changements réels dans le modèle de récompense ». Cette approche est démontrée comme étant empiriquement supérieure et théoriquement solide.
3. Modularité et Polyvalence : Le cadre est agnostique vis-à-vis de l'algorithme stationnaire sous-jacent, permettant son application aux bandits Linéaires (LB), GLM (GLB), Auto-concordants (SCB), à Noyaux (KB) et Contextuels (CB).
4. Validation Empirique Complète : Les auteurs fournissent des évaluations étendues sur des benchmarks synthétiques ainsi que sur neuf jeux de données réels (incluant le pré-chargement d'architecture micro, les marchés boursiers, les essais cliniques et la recommandation publicitaire), une rareté pour les méthodes de bandits non stationnaires optimales en ordre.
5. Améliorations Théoriques : Le papier fournit des bornes de regret qui correspondent à l'état de l'art pour les PS-LBs, PS-GLBs et PS-CBs, tout en améliant les meilleures bornes connues pour les PS-SCBs et PS-KBs.

4. Résultats Expérimentaux

Les auteurs ont évalué DAL contre des bases de référence (baselines) de pointe, incluant des méthodes sans a priori (MASTER, ADA-OPKB, ADA-ILTCB+) et des méthodes avec a priori (WeightUCB, WGP-UCB).

• Benchmarks Synthétiques : Dans les scénarios PS et de dérive (Linéaire, GL, SC, Noyau et Contextuel), DAL a systématiquement obtenu le regret dynamique le plus bas. Il a nettement surpassé MASTER (qui échoue souvent à déclencher un signal) et d'autres méthodes sans a priori.
• Jeux de Données Réels : Sur des jeux de données allant des logs de clics de Yahoo! aux essais cliniques COVID-NMA et au choix de pré-chargeur micro, DAL a démontré une performance supérieure tant en regret dynamique qu'en récompense cumulative par rapport à toutes les bases de référence.
• Efficacité : Malgré l'ajout du mécanisme de détection, le temps d'exécution de DAL est resté compétitif par rapport aux bases de référence les plus rapides et était sensiblement plus rapide que MASTER.
• Environnements de Dérive : Bien que principalement conçu pour la stationnarité par morceaux, les auteurs ont observé que DAL fonctionne également bien dans les environnements à dérive lente (où le paramètre $\delta$ est petit), car la dérive peut être absorbée dans le terme de bruit, bien que la performance se dégrade à mesure que le taux de dérive augmente.

5. Signification et Revendications

Le papier affirme que DAL comble le fossé entre l'optimalité théorique et l'efficacité pratique dans les bandits non stationnaires.

• Praticité : En s'appuyant sur la détection de changement plutôt que sur les violations de bornes de regret, DAL devient viable pour des applications réelles où les horizons sont finis et la non-stationnarité est inconnue.
• Scalabilité : La nature "boîte noire" permet au cadre de tirer parti des dernières avancées des algorithmes de bandits stationnaires sans nécessiter d'adaptations non stationnaires personnalisées pour chaque variante.
• Robustesse : Les résultats empiriques à travers divers domaines suggèrent que DAL est une solution robuste pour les systèmes d'ingénierie (ex: recommandation, tarification dynamique, essais cliniques) où les conditions évoluent de manière abrupte.

Les auteurs concluent que bien que DAL fasse progresser à la fois la théorie et la pratique, des travaux futurs sont nécessaires pour étendre les garanties de regret aux environnements de dérive et pour assouplir les hypothèses de séparation des points de rupture requises pour les preuves théoriques actuelles.