Technische Samenvatting: Gedistribueerde GNEP-algoritmen zonder vermenigvuldigerdeling en toepassingen op multi-robotcoördinatie en Contextual Bandit-gebaseerde actieve leerprocessen

1. Probleemstelling

De thesis behandelt twee afzonderlijke maar significante uitdagingen in gedistribueerde optimalisatie en machine learning:

Deel I: Generalized Nash Equilibrium Problems (GNEPs)
In veel multi-agentsystemen (bijv. elektriciteitsnetten, verkeersrouting, multi-robotcoördinatie) moeten agenten hun lokale kostenfuncties minimaliseren onderhevig aan zowel individuele beperkingen als gedeelde koppelingsbeperkingen. Deze formulering leidt tot het Generalized Nash Equilibrium Problem (GNEP). Bestaande gedistribueerde algoritmen voor het oplossen van GNEP's vertrouwen doorgaans op het afdwingen van consensus tussen Lagrange-vermenigvuldigers die behoren tot gedeelde beperkingen. Deze vereiste noodzaakt de uitwisseling van hulpvariabelen en vermenigvuldigers tussen agenten, wat de communicatieoverhead verhoogt en potentieel de privacy in gevaar brengt. Bovendien zijn de meeste bestaande methoden beperkt tot het berekenen van variationele Generalized Nash Equilibria (v-GNE's), een specifieke subklasse van evenwichten, in plaats van de volledige verzameling van Generalized Nash Equilibria (GNE's).

Deel II: Contextual Bandit-gebaseerde actieve leerprocessen
Actief leren (active learning) beoogt de kosten voor labeling in supervised learning te verminderen door de meest informatieve datapunten selectief op te vragen. Hoewel talrijke handmatig ontworpen strategieën bestaan (bijv. onzekerheids-sampling, diversiteits-sampling), is hun prestatie sterk afhankelijk van de onderliggende datadistributie, die vaak onbekend is. Bestaande adaptieve frameworks die deze strategieën combineren, maken vaak gebruik van adversarial bandit-algoritmen. Deze methoden zijn overdreven conservatief en handhaven een persistente exploratie zonder gebruik te maken van de omgevingscontext, wat vaak resulteert in een prestatie die vergelijkbaar is met willekeurige selectie.

2. Methodologie

Deel I: Volledig gedistribueerde algoritmen voor GNEP's

De auteur stelt een volledig gedistribueerd continu-tijd algoritme voor op basis van primal-dual dynamica dat de noodzaak voor het delen van vermenigvuldigers elimineert.

• Primal-Dual Dynamica: Het algoritme modelleert het systeem als een Projected Dynamical System (PDS). Agenten updaten hun beslissingsvariabelen ($z_v$) en lokale vermenigvuldigers ($\lambda_v, \mu_v$) met behulp van uitsluitend lokale informatie en gegevens die met buren worden uitgewisseld via specifieke interactiegrafen (kostenfunctie-graaf en gedeelde beperkingsgraaf).
• Vermenigvuldiger-transformatie: Een belangrijke theoretische innovatie is de transformatie van gedeelde vermenigvuldigers. In plaats van consensus af te dwingen ($\lambda_v = \lambda_u$), deelt de methode vermenigvuldigers op in een gemeenschappelijke referentietoestand en een afwijkingsterm ($\Delta_v$). De dynamica van de afwijkingstermen blijkt constant of niet-toenemend te zijn over de tijd, afhankelijk van het type beperking (gelijkheid versus ongelijkheid).
• Convergentieanalyse:
  • Gelijkheidsbeperkingen: Voor spellen met sterk monotone kostenmappings en lineaire gedeelde gelijkheidsbeperkingen bewijst de auteur globale asymptotische stabiliteit. De primaire variabelen convergeren naar een uniek GNE, terwijl de duale variabelen convergeren naar een verzameling geldige vermenigvuldigers. Het limiterende evenwicht hangt af van de initialisatie van de afwijkingstermen.
  • Ongelijkheidbeperkingen: Voor gedeelde ongelijkheidsbeperkingen met kwadratische convexe kosten maakt de analyse gebruik van bounded-input bounded-output (BIBO) argumenten en trajectbegrenzing om convergentie naar een GNE te bewijzen, zelfs wanneer de geïnduceerde primal-dual dynamica niet monotoon zijn.
• Discretisatie: Om praktische implementatie mogelijk te maken, ontwikkelt de thesis drie discretisatieschema's:
  1. Afnemende stapgrootte (Diminishing Step Size): Bootst continu dynamica asymptotisch na maar convergeert traag ($O(1/\sqrt{k})$).
  2. Backward Euler (Resolvent): Gebruikt een vaste stapgrootte en vereist het oplossen van een intern Nash Equilibrium Problem (NEP) bij elke stap. Het bereikt een convergentiesnelheid van $o(1/k)$.
  3. Forward-Backward Splitting: Een hybride schema dat de vereiste van de interne solver vermijdt door delen van de operator expliciet en andere impliciet te behandelen. Het vereist een globaal overeengekomen stapgrootte maar biedt een balans tussen computationele kosten en convergentiesnelheid.

Deel II: Contextual Adaptive Active Learning (CAAL)

Het tweede deel introduceert Contextual Adaptive Active Learning (CAAL), een meta-strategie framework dat contextual bandits gebruikt om de beste handmatig ontworpen actieve leerstrategie dynamisch te selecteren.

• Framework: Het probleem wordt gemodelleerd als een contextual bandit waarbij de "armen" verschillende handmatig ontworpen actieve leerstrategieën zijn (bijv. K-Center, Informative Diversity).
• Context en Beloning: In tegenstelling tot adversarial bandit benaderingen, incorporeert CAAL externe context (bijv. de huidige grootte van de gelabelde dataset) om beloningen te voorspellen. De beloning wordt gedefinieerd als de relatieve verbetering in modelprestaties (bijv. verandering in ROC-AUC) tussen iteraties, in plaats van absolute prestaties, om non-stationariteit aan te pakken.
• Algoritme: De methode maakt gebruik van een non-stationair lineair Upper Confidence Bound (LinUCB) algoritme (specifiek Sliding Window LinUCB) om de beloningsfunctie $\theta_a^\top c_k$ te schatten. Dit stelt de agent in staat om de voorspelbaarheid van beloningen op basis van context te exploiteren, waardoor de conservativiteit die inherent is aan adversarial bandit methoden wordt verminderd.

3. Belangrijkste Bijdragen

Voor GNEP's:

1. Eerste Vermenigvuldiger-vrije Gedistribueerde Algoritme: Naar weten van de auteur is dit het eerste gedistribueerde algoritme dat GNE's berekent zonder de noodzaak van consensus of de uitwisseling van Lagrange-vermenigvuldigers. Dit vermindert de communicatieoverhead aanzienlijk (met ongeveer een derde in specifieke grafensettings) en verbetert de privacy.
2. Algemene GNE Convergentie: De voorgestelde methode is niet beperkt tot variationele-GNE's. Het convergeert naar algemene GNE's, waarbij het specifieke bereikte evenwicht afhangt van de initialisatie. Dit adresseert de beperking van bestaande methoden die alleen unieke v-GNE's nastreven.
3. Nieuwe Bewijstechnieken: De thesis ontwikkelt bewijstechnieken om niet-monotone geïnduceerde dynamica en niet-unieke evenwichten te behandelen, met behulp van Lyapunov-stabiliteitsanalyse en trajectbegrenzing.

Voor Actief Leren:

1. Contextuele Adaptatie: Het werk stelt voor om contextuele informatie in te voegen in bandit-gebaseerd actief leren om de conservativiteit van adversarial bandit frameworks te verminderen.
2. Focus op Batch Selectie: In tegen tegenstelling tot veel voorgaande werken die zich richten op single-sample selectie, legt deze benadering de nadruk op robuustheid over verschillende batchgroottes, wat meer in lijn is met industriële toepassingen.
3. Meta-Learner Benadering: De methode richt zich op meta-learner-gebaseerde selectie in plaats van deep active learning, wat het geschikter maakt voor tabelvormige data, die de meerderheid van de industriële datasets domineert.

4. Resultaten

GNEP Simulaties:

• Multi-Robot Coördinatie: Het algoritme werd getest op multi-robot plaatsings- en half-space covering problemen. De resultaten toonden convergentie naar GNE's vanuit diverse initialisaties, wat de non-uniciteit van oplossingen benadrukt. De forward-backward discretisatie (Algoritme 4.10) vertoonde convergentiesnelheden die vergelijkbaar zijn met consensus-gebaseerde methoden, maar met aanzienlijk minder communicatie per iteratie.
• Cournot Competitie: De methode werd toegepast op een Cournot-spel met 20 agenten en 7 markten. Het algoritme convergeerde succesvol naar een GNE voor elke initialisatie, waarbij de privacy van de agenten behouden bleef en de schaalbaarheid werd aangetoond.

Active Learning Experimenten:

• Datasets: Experimenten werden uitgevoerd op publieke datasets (ILPD, I vs J, Australian Credit, German Credit) met behulp van logistische regressie als basisclassifier.
• Prestaties: CAAL werd vergeleken met de state-of-the-art adaptieve baseline (ALBL) en handmatig ontworpen strategieën (K-Center, Informative Diversity).
  • CAAL presteerde beter dan ALBL en individuele strategieën op de meeste datasets, met name voor batchgroottes groter dan 5.
  • De "Reward Prediction" analyse toonde aan dat het lineaire regressiemodel in staat was om belonings-trends op basis van context nauwkeurig te voorspellen, wat de aanname van lokale lineariteit valideert.
  • De "Pull History" analyse gaf aan dat CAAL erin slaagde de optimale strategie te identificeren en te exploiteren na een initiële exploratiefase, terwijl ALBL de neiging had om armen met bijna gelijke waarschijnlijkheid te selecteren vanwege zijn conservatieve aard.
• Implementatie: Het framework is ingezet in Amazon's interne productiesystemen, hoewel resultaten van interne datasets zijn weggelaten vanwege vertrouwelijkheid.

5. Betekenis en Claims

De thesis claimt kritische hiaten te overbruggen in zowel gedistribueerde speltheorie als adaptieve machine learning:

• In Gedistribueerde Optimalisatie: Door de vereiste voor het delen van vermenigvuldigers weg te nemen, biedt het voorgestelde framework een schaalbaardere en privacy-bewarende oplossing voor grootschalige multi-agent systemen. Het vermogen om naar algemene GNE's te convergeren in plaats van enkel v-GNE's, breidt de toepasbaarheid van gedistribueerde evenwichtsberekening uit naar scenario's waarin uniforme prijsstelling of gecentraliseerde coördinatie niet haalbaar is.
• In Actief Leren: Het werk demonstreert dat het benutten van contextuele informatie de adaptiviteit van actieve leerstrategieën aanzienlijk kan verbeteren ten opzichte van puur adversarial benaderingen. Het voorgestelde CAAL-framework biedt een praktische, industrie-vriendelijke oplossing voor batch-mode actief leren dat zich aanpast aan onbekende datadistributies zonder deep learning architecturen te vereisen.

De auteur merkt op dat hoewel de continu-tijd analyse sterke theoretische garanties biedt, de discretisatieschema's specifieke aannames introduceren (bijv. Lipschitz-continuïteit, compactheid) die vereist zijn voor convergentie. Tevens, voor het actieve leercomponent, hangt de exploratiecomplexiteit af van het aantal kandidaat-strategieën (armen), en vertrouwt het framework momenteel op domeinkennis om de initiële set van handmatig ontworpen strategieën te definiëren. Toekomstig werk wordt voorgesteld om de GNEP-algoritmen uit te breiden naar meer algemene convexe beperkingen en om de theoretische analyse van het contextuele bandit-framework te verfijnen.