Résumé Technique : Algorithmes de GNEP Distribués sans Partage de Multiplicateurs et Applications à la Coordination Multi-Robots et à l'Apprentissage Actif Basé sur les Bandits Contextuels

1. Énoncé du Problème

La thèse traite de deux défis distincts mais significatifs dans l'optimisation distribuée et l'apprentissage automatique :

Partie I : Problèmes d'Équilibre de Nash Généralisé (GNEP)
Dans de nombreux systèmes multi-agents (par exemple, les réseaux électriques, le routage de trafic, la coordination multi-robots), les agents doivent minimiser des fonctions de coût locales soumises à la fois à des contraintes individuelles et à des contraintes de couplage partagées. Cette formulation conduit au Problème d'Équilibre de Nash Généralisé (GNEP). Les algorithmes distribués existants pour résoudre les GNEP reposent généralement sur l'imposition d'un consensus entre les multiplicateurs de Lagrange associés aux contraintes partagées. Cette exigence nécessite l'échange de variables auxiliaires et de multiplicateurs entre les agents, ce qui augmente la surcharge de communication et peut compromettre la confidentialité. De plus, la plupart des méthodes existantes sont limitées au calcul des Équilibres de Nash Généralisés variationnels (v-GNE), une sous-classe spécifique d'équilibres, plutôt qu'à l'ensemble complet des Équilibres de Nash Généralisés (GNE).

Partie II : Apprentissage Actif Basé sur les Bandits Contextuels
L'apprentissage actif vise à réduire le coût d'étiquetage dans l'apprentissage supervisé en interrogeant sélectivement les points de données les plus informatifs. Bien que de nombreuses stratégies façonnées à la main existent (par exemple, l'échantillonnage par incertitude, l'échantillonnage par diversité), leurs performances dépendent fortement de la distribution sous-jacente des données, qui est souvent inconnue. Les cadres adaptatifs existants qui combinent ces stratégies utilisent souvent des algorithmes de bandits adverses. Ces méthodes sont excessivement conservatrices, maintenant une exploration persistante sans tirer parti du contexte environnemental, ce qui entraîne souvent des performances similaires à une sélection aléatoire.

2. Méthodologie

Partie I : Algorithmes Entièrement Distribués pour les GNEP

L'auteur propose un algorithme de temps continu entièrement distribué basé sur la dynamique primal-dual qui élimine la nécessité du partage de multiplicateurs.

• Dynamique Primal-Dual : L'algorithme modélise le système comme un Système Dynamique Projeté (PDS). Les agents mettent à jour leurs variables de décision ($z_v$) et leurs multiplicateurs locaux ($\lambda_v, \mu_v$) en utilisant uniquement des informations locales et des données échangées avec les voisins via des graphes d'interaction spécifiques (graphe des fonctions de coût et graphe des contraintes partagées).
• Transformation des Multiplicateurs : Une innovation théorique clé est la transformation des multiplicateurs partagés. Au lieu d'imposer un consensus ($\lambda_v = \lambda_u$), la méthode décompose les multiplicateurs en un état de référence commun et un terme de déviation ($\Delta_v$). La dynamique des termes de déviation est montrée comme étant constante ou non croissante au fil du temps, selon le type de contrainte (égalité vs inégalité).
• Analyse de Convergence :
  • Contraintes d'Égalité : Pour les jeux avec des applications de coût fortement monotones et des contraintes d'égalité linéaires partagées, l'auteur prouve la stabilité asymptotique globale. Les variables primales convergent vers un v-GNE unique, tandis que les variables duales convergent vers un ensemble de multiplicateurs valides. L'équilibre limite dépend de l'initialisation des termes de déviation.
  • Contraintes d'Inégalité : Pour les contraintes d'inégalité partagées avec des coûts convexes quadratiques, l'analyse utilise des arguments de type Borné-Entrée Bornée-Sortie (BIBO) et la bornitude des trajectoires pour prouver la convergence vers un GNE, même lorsque la dynamique primal-dual induite n'est pas monotone.
• Discrétisation : Pour permettre une mise en œuvre pratique, la thèse développe trois schémas de discrétisation :
  1. Pas de Taille Diminuante : Imite asymptotiquement les dynamiques continues mais converge lentement ($O(1/\sqrt{k})$).
  2. Euler Arrière (Résolvant) : Utilise un pas de taille fixe et nécessite de résoudre un Problème d'Équilibre de Nash (NEP) interne à chaque étape. Il atteint un taux de convergence de $o(1/k)$.
  3. Division Avant-Arrière (Forward-Backward Splitting) : Un schéma hybride qui évite l'exigence du solveur interne en traitant certaines parties de l'opérateur de manière explicite et d'autres de manière implicite. Il nécessite un pas de taille convenu globalement mais offre un équilibre entre le coût computationnel et le taux de convergence.

Partie II : Apprentissage Actif Adaptatif Contextuel (CAAL)

La seconde partie introduit l'Apprentissage Actif Adaptatif Contextuel (CAAL), un cadre de méta-stratégie qui utilise les bandits contextuels pour sélectionner dynamiquement la meilleure stratégie d'apprentissage actif façonnée à la main.

• Cadre : Le problème est modélisé comme un bandit contextuel où les "bras" sont différentes stratégies d'apprentissage actif façonnées à la main (par exemple, K-Center, Diversité Informative).
• Contexte et Récompense : Contra-irement aux approches de bandits adverses, CAAL incorpore un contexte externe (par exemple, la taille actuelle de l'ensemble de données étiquetées) pour prédire les récompenses. La récompense est définie comme l'amélioration relative de la performance du modèle (par exemple, le changement de l'AUC-ROC) entre les itérations, plutôt que la performance absolue, afin de traiter la non-stationnarité.
• Algorithme : La méthode emploie un algorithme de limite supérieure de confiance linéaire non stationnaire (LinUCB) (spécifiquement Sliding Window LinUCB) pour estimer la fonction de récompense $\theta_a^\top c_k$. Cela permet à l'agent d'exploiter la prévisibilité des récompenses basée sur le contexte, réduisant ainsi le caractère conservateur inhérent aux méthodes de bandits adverses.

3. Contributions Clés

Pour les GNEP :

1. Premier Algorithme Distribué Sans Multiplicateur : À la connaissance de l'auteur, il s'agit du premier algorithme distribué qui calcule des GNE sans nécessiter de consensus ou d'échange de multiplicateurs de Lagrange. Cela réduit considérablement la surcharge de communication (d'environ un tiers dans des configurations de graphes spécifiques) et améliore la confidentialité.
2. Convergence GNE Générale : La méthode proposée n'est pas restreinte aux v-GNE. Elle converge vers des GNE généraux, l'équilibre spécifique atteint dépendant de l'initialisation. Cela répond à la limitation des méthodes existantes qui ne visent que le v-GNE unique.
3. Nouvelles Techniques de Preuve : La thèse développe des techniques de preuve pour gérer les dynamiques induites non monotones et les équilibres non uniques, en utilisant l'analyse de stabilité de Lyapunov et les arguments de trajectoire bornée.

Pour l'Apprentissage Actif :

1. Adaptation Contextuelle : Le travail propose d'incorporer des informations contextuelles dans l'apprentissage actif basé sur les bandits pour réduire le caractère conservateur des cadres de bandits adverses.
2. Focus sur la Sélection par Lot (Batch) : Contrairement à de nombreux travaux antérieurs se concentrant sur la sélection d'un échantillon unique, cette approche met l'accent sur la robustesse à travers différentes tailles de lots, ce qui est plus aligné avec les applications industrielles.
3. Approche de Méta-Apprenant : La méthode se concentre sur la sélection par méta-apprenant plutôt que sur l'apprentissage profond actif, ce qui la rend plus adaptée aux données tabulaires, qui dominent les ensembles de données industriels.

4. Résultats

Simulations GNEP :

• Coordination Multi-Robots : L'algorithme a été testé sur des problèmes de placement de multi-robots et de couverture d'un demi-espace. Les résultats ont démontré une convergence vers les GNE à partir de diverses initialisations, soulignant la non-unicité des solutions. La discrétisation avant-arrière (Algorithme 4.10) a montré des taux de convergence comparables aux méthodes basées sur le consensus, mais avec une communication nettement réduite par itération.
• Compétition de Cournot : La méthode a été appliquée à un jeu de Cournot avec 20 agents et 7 marchés. L'algorithme a réussi à converger vers un GNE pour toute initialisation, préservant la confidentialité des agents et démontrant la scalabilité.

Expériences d'Apprentissage Actif :

• Jeux de Données : Des expériences ont été menées sur des jeux de données publics (ILPD, I vs J, Australian Credit, German Credit) en utilisant la régression logistique comme classificateur de base.
• Performance : CAAL a été comparé à la base adaptative de pointe (ALBL) et aux stratégies façonnées à la main (K-Center, Diversité Informative).
  • CAAL a surpassé ALBL et les stratégies individuelles sur la plupart des jeux de données, particulièrement pour des tailles de lots supérieures à 5.
  • L'analyse de la "Prédiction de Récompense" a montré que le modèle de régression linéaire pouvait prédire avec précision les tendances de récompense basées sur le contexte, validant l'hypothèse de linéarité locale.
  • L'analyse de l'historique de tirage ("Pull History") a indiqué que CAAL a réussi à identifier et exploiter la stratégie optimale après une phase d'exploration initiale, là où ALBL avait tendance à sélectionner les bras avec une probabilité quasi égale en raison de sa nature conservatrice.
• Déploiement : Le cadre a été déployé dans les systèmes de production internes d'Amazon, bien que les résultats sur les jeux de données internes soient omis pour des raisons de confidentialité.

5. Signification et Revendications

La thèse prétend combler des lacunes critiques tant dans la théorie des jeux distribués que dans l'apprentissage automatique adaptatif :

• En Optimisation Distribuée : En supprimant l'exigence de partage de multiplicateurs, le cadre proposé offre une solution plus scalable et respectueuse de la vie privée pour les systèmes multi-agents à grande échelle. La capacité de converger vers des GNE généraux plutôt que vers de simples v-GNE étend l'applicabilité du calcul d'équilibre distribué à des scénarios où une tarification uniforme ou une coordination centralisée n'est pas réalisable.
• En Apprentissage Actif : Le travail démontre que l'exploitation des informations contextuelles peut améliorer considérablement l'adaptabilité des stratégies d'apprentissage actif par rapport aux approches purement adverses. Le cadre CAAL propose une solution pratique et adaptée à l'industrie pour l'apprentissage actif en mode lot, qui s'adapte aux distributions de données inconnues sans nécess avoir recours à des architectures de deep learning.

L'auteur note que si l'analyse en temps continu fournit de solides garanties théoriques, les schémas de discrétisation introduisent des hypothèses spécifiques (par exemple, la continuité de Lipschitz, la compacité) nécessaires à la convergence. De même, pour la composante d'apprentissage actif, la complexité de l'exploration dépend du nombre de stratégies candidates (bras), et le cadre repose actuellement sur l'expertise du domaine pour définir l'ensemble initial de stratégies façonnées à la main. Des travaux futurs sont proposés pour étendre les algorithmes GNEP à des contraintes convexes plus générales et pour affiner l'analyse théorique du cadre de bandit contextuel.