Sintesi Tecnica: Algoritmi GNEP Distribuiti senza Scambio di Moltiplicatori e Applicazioni alla Coordinazione Multi-Robot e all'Apprendimento Attivo Basato su Contextual Bandit

1. Definizione del Problema

La tesi affronta due sfide distinte ma significative nella ottimizzazione distribuita e nell'apprendimento automatico:

Parte I: Problemi di Equilibrio di Nash Generalizzato (GNEP)
In molti sistemi multi-agente (ad es., reti elettriche, instradamento del traffico, coordinazione multi-robot), gli agenti devono minimizzare le funzioni di costo locali soggette sia a vincoli individuali che a vincoli di accoppiamento condivisi. Questa formulazione porta al Problema di Equilibrio di Nash Generalizzato (GNEP). Gli algoritmi distribuiti esistenti per risolvere i GNEP si basano tipicamente sull'imposizione del consenso tra i moltiplicatori di Lagrange associati ai vincoli condivisi. Questo requisito richiede lo scambio di variabili ausiliarie e moltiplicatori tra gli agenti, aumentando l'overhead di comunicazione e potenzialmente compromettendo la privacy. Inoltre, la maggior parte dei metodi esistenti è limitata al calcolo degli Equilibri di Nash Generalizzati variazionali (v-GNE), una sottoclasse specifica di equilibri, piuttosto che all'intero insieme di Equilibri di Nash Generalizzati (GNE).

Parte II: Apprendimento Attivo Basato su Contextual Bandit
L'apprendimento attivo mira a ridurre il costo di etichettatura nel supervised learning selezionando i punti dati più informativi. Sebbene esistano numerose strategie artigianali (ad es., campionamento dell'incertezza, campionamento della diversità), le loro prestazioni dipendono fortemente dalla distribuzione sottostante dei dati, che è spesso sconosciuta. Gli schemi adattivi esistenti che combinano queste strategie utilizzano spesso algoritmi bandit avversari. Tali metodi sono eccessivamente conservativi, mantenendo un'esplorazione persistente senza sfruttare il contesto ambientale, risultando spesso con prestazioni simili alla selezione casuale.

2. Metodologia

Parte I: Algoritmi Completamente Distribuiti per i GNEP

L'autore propone un algoritmo completamente distribuito in tempo continuo basato sulla dinamica primal-dual che elimina la necessità di scambio di moltiplicatori.

• Dinamica Primal-Dual: L'algoritmo modella il sistema come un Sistema Dinamico Proiettato (PDS). Gli agenti aggiornano le loro variabili decisionali ($z_v$) e i loro moltiplicatori locali ($\lambda_v, \mu_v$) utilizzando solo informazioni locali e dati scambiati con i vicini attraverso grafi di interazione specifici (grafo delle funzioni di costo e grafo dei vincoli condivisi).
• Trasformazione dei Moltiplicatori: Una chiave innovazione teorica è la trasformazione dei moltiplicatori condivisi. Invece di imporre il consenso ($\lambda_v = \lambda_u$), il metodo decompone i moltiplicatori in uno stato di riferimento comune e un termine di deviazione ($\Delta_v$). Si dimostra che la dinamica dei termini di deviazione è costante o non crescente nel tempo, a seconda del tipo di vincolo (uguaglianza vs disuguaglianza).
• Analisi della Convergenza:
  • Vincoli di Uguaglianza: Per giochi con mapping di costo fortemente monotoni e vincoli di uguaglianza lineari condivisi, l'autore dimostra la stabilità asintotica globale. Le variabili primali convergono a un GNE unico, mentre le variabili duali convergono a un insieme di moltiplicatori validi. L'equilibrio limite dipende dall'inizializzazione dei termini di deviazione.
  • Vincoli di Disuguaglianza: Per i vincoli di disuguaglianza condivisi con costi convessi quadratici, l'analisi utilizza argomenti di input limitato e output limitato (BIBO) e la limitatezza delle traiettorie per dimostrare la convergenza a un GNE, anche quando le dinamiche primal-dual indotte non sono monotone.
• Discretizzazione: Per consentire l'implementazione pratica, la tesi sviluppa tre schemi di discretizzazione:
  1. Step Size Decrescente: Mimica le dinamiche continue asintoticamente ma converge lentamente ($O(1/\sqrt{k})$).
  2. Backward Euler (Resolvent): Utilizza un passo fisso e richiede la risoluzione di un problema interno di Equilibrio di Nash (NEP) ad ogni step. Raggiunge un tasso di convergenza di $o(1/k)$.
  3. Forward-Backward Splitting: Uno schema ibrido che evita la necessità del solver interno trattando parte dell'operatore in modo esplicito e altre parti in modo implicito. Richiede un passo concordato globalmente ma offre un equilibrio tra costo computazionale e tasso di convergenza.

Parte II: Contextual Adaptive Active Learning (CAAL)

La seconda parte introduce il Contextual Adaptive Active Learning (CAAL), un framework di meta-strategia che utilizza i contextual bandit per selezionare dinamicamente la migliore strategia di apprendimento attivo artigianale.

• Framework: Il problema è modellato come un contextual bandit dove le "braccia" sono diverse strategie di apprendimento attivo artigianali (ad es, K-Center, Informative Diversity).
• Contesto e Reward: A differenza degli approcci bandit avversari, CAAL incorpora il contesto esterno (ad es, la dimensione attuale del dataset etichettato) per prevedere i reward. Il reward è definito come il miglioramento relativo nelle prestazioni del modello (ad es, variazione della ROC-AUC) tra le iterazioni, piuttosto che sulle prestazioni assolute, per affrontare la non-stazionarietà.
• Algoritmo: Il metodo impiega un algoritmo linear Upper Confidence Bound (LinUCB) non stazionario (specificamente Sliding Window LinUCB) per stimare la funzione di reward $\theta_a^\top c_k$. Ciò consente all'agente di sfruttare la prevedibilità dei reward basata sul contesto, riducendo la natura conservativa tipica dei metodi bandit avversari.

3. Contributi Chiave

Per i GNEP:

1. Primo Algoritmo Distribuito Senza Moltiplicatori: Per quanto ne sa l'autore, questo è il primo algoritmo distribuito che calcola i GNE senza richiedere il consenso o lo scambio di moltiplicatori di Lagrange. Ciò riduce significativamente l'overhead di comunicazione (di circa un terzo in specifici setting di grafo) e migliora la privacy.
2. Convergenza GNE Generale: Il metodo proposto non è limitato ai v-GNE. Converge a GNE generali, con l'equilibrio specifico raggiunto che dipende dall'inizializzazione. Ciò affronta il limite dei metodi esistenti che mirano solo all'unico v-GNE.
3. Nuove Tecniche di Dimostrazione: La tesi sviluppa tecniche di dimostrazione per gestire dinamiche indotte non monotone ed equilibri non unici, utilizzando l'analisi della stabilità di Lyapunov e argomenti di traiettoria limitata.

Per l'Apprendimento Attivo:

1. Adattamento Contestuale: Il lavoro propone l'integrazione di informazioni contestuali nel processo di apprendimento attivo basato su bandit per ridurre la natura conservativa dei framework bandit avversari.
2. Focus sulla Selezione di Batch: A differenza di molti lavori precedenti focalizzati sulla selezione di un singolo campione, questo approccio enfatizza la robustezza attraverso diversi batch, il che è più allineato alle applicazioni industriali.
3. Approccio Meta-Learner: Il metodo si concentra sulla selezione basata su meta-learner piuttosto che sul deep active learning, rendendolo più adatto ai dati tabulari, che dominano i dataset industriali.

4. Risultati

Simulazioni GNEP:

• Coordinazione Multi-Robot: L'algoritmo è stato testato su problemi di posizionamento multi-robot e copertura di semispazi. I risultati hanno dimostrato la convergenza ai GNE da varie inizializzazioni, evidenziando la non unicità delle soluzioni. La discretizzazione forward-backward (Algoritmo 4.10) ha mostrato tassi di convergenza comparabili ai metodi basati sul consenso, ma con una comunicazione significativamente ridotta per iterazione.
• Competizione di Cournot: Il metodo è stato applicato a un gioco di Cournot con 20 agenti e 7 mercati. L'algoritmo è riuscito a convergere a un GNE per qualsiasi inizializzazione, preservando la privacy degli agenti e dimostrando scalabilità.

Esperimenti di Apprendimento Attivo:

• Dataset: Gli esperimenti sono stati condotti su dataset pubblici (ILPD, I vs J, Australian Credit, German Credit) utilizzando la regressione logistica come classificatore base.
• Prestazioni: CAAL è stato confrontato con il baseline adattivo allo stato dell'arte (ALBL) e con le strategie artigianali (K-Center, Informative Diversity).
  • CAAL ha superato ALBL e le singole strategie nella maggior parte dei dataset, in particolare per batch di dimensioni superiori a 5.
  • L'analisi della "Previsione del Reward" ha mostrato che il modello di regressione lineare poteva prevedere accuratamente i trend dei reward basandosi sul contesto, validando l'assunto di linearità locale.
  • L'analisi della "Storia di Pull" ha indicato che CAAL ha identificato con successo ed esploso la strategia ottimale dopo una fase iniziale di esplorazione, mentre ALBL tendeva a selezionare le braccia con probabilità quasi uguali a causa della sua natura conservativa.
• Deployment: Il framework è stato implementato nei sistemi di produzione interni di Amazon, sebbene i risultati sui dataset interni siano omessi per motivi di riservatezza.

5. Significatività e Rivendicazioni

La tesi sostiene di colmare lacune critiche sia nella teoria dei giochi distribuita che nell'apprendimento automatico adattivo:

• Nella Ottimizzazione Distribuita: Rimuovendo il requisito dello scambio di moltiplicatori, il framework proposto offre una soluzione più scalabile e che preserva la privacy per i grandi sistemi multi-agente. La capacità di convergere a GNE generali anziché solo a v-GNE espande l'applicabilità del calcolo dell'equilibrio distribuito a scenari in cui la determinazione di un prezzo uniforme o la coordinazione centralizzata non sono fattibili.
• Nell'Apprendimento Attivo: Il lavoro dimostra che sfruttare le informazioni contestuali può migliorare significativamente l'adattabilità delle strategie di apprendimento attivo rispetto agli approcci puramente avversari. Il framework CAAL proposto fornisce una soluzione pratica e adatta all'industria per l'apprendimento attivo in modalità batch, che si adatta a distribuzioni di dati sconosciute senza richiedere architetture di deep learning.

L'autore osserva che, sebbene l'analisi in tempo continuo fornisca forti garanzie teoriche, gli schemi di discretizzazione introducono specifici assunti (ad es, continuità Lipschitz, compattezza) necessari per la convergenza. Allo stesso modo, per la componente di apprendimento attivo, la complessità dell'esplorazione dipende dal numero di strategie candidate (braccia), e il framework attualmente si affida all'esperienza del dominio per definire l'insieme iniziale di strategie artigianali. Si propone come lavoro futuro l'estensione degli algoritmi GNEP a vincoli convessi più generali e il raffinamento dell'analisi teorica del framework del contextual bandit.