Riepilogo Tecnico: Identificazione di Agenti Vulnerabili nell'Apprendimento per Rinforzo Multi-Agente su Larga Scala

1. Formulazione del Problema

Il documento affronta il problema dell'Identificazione di Agenti Vulnerabili (VAI) nei sistemi di Apprendimento per Rinforzo Multi-Agente (MARL) su larga scala. Man mano che i sistemi si espandono fino a migliaia di agenti (ad esempio, sciami di robot, reti elettriche), i guasti parziali degli agenti diventano inevitabili a causa di errori hardware, pericoli ambientali o controlli avversari. La sfida principale consiste nell'identificare il sottoinsieme specifico di $K$ agenti il cui compromesso porta al peggioramento nel caso peggiore delle prestazioni dell'intero sistema.

Gli autori inquadrano questo come un problema di Controllo Decentralizzato Gerarchico Avversario a Campo Medio (HAD-MFC):

• Livello Superiore: Un compito di ottimizzazione combinatoria per selezionare gli $K$ agenti più vulnerabili tra un totale di $N$ agenti. Gli autori dimostrano che questo sottoproblema è NP-difficile riducendolo al problema generalizzato della copertura massima.
• Livello Inferiore: Un compito MARL a campo medio in cui una politica avversaria viene addestrata per gli $K$ agenti selezionati per minimizzare la ricompensa attesa del sistema, assumendo che gli agenti rimanenti seguano una politica cooperativa fissa e ben addestrata.

La difficoltà principale risiede nell'accoppiamento di questi due livelli: risolvere il livello superiore richiede la valutazione del livello inferiore per ogni sottoinsieme candidato, il che è computazionalmente intrattabile per grandi valori di $N$.

2. Metodologia

Per risolvere il problema accoppiato HAD-MFC, gli autori propongono una strategia di decomposizione che disaccoppia il processo gerarchico e trasforma il compito di selezione NP-difficile in un Processo Decisionale di Markov (MDP) trattabile.

2.1 Disaccoppiamento tramite Trasformata di Fenchel-Rockafellar

Gli autori eliminano la necessità di addestrare un avversario nel caso peggiore a livello inferiore per ogni insieme candidato durante la fase di selezione. Invece, derivano un operatore di Bellman a campo medio regolarizzato ($B^R_{\epsilon_i, \xi}$).

• Applicando la trasformata di Fenchel-Rockafellar all'insieme di incertezza indotto dalle perturbazioni avversarie, convertono il problema min-max in una stima della funzione di valore regolarizzata.
• Questo operatore stima il potenziale valore nel caso peggiore utilizzando esclusivamente traiettorie cooperative. Introduce termini di regolarizzazione basati sul budget di perturbazione dell'agente ($\epsilon_i$) e sulla perturbazione a campo medio ($\xi$), catturando le vulnerabilità individuali e sistemiche senza un addestramento avversario esplicito nella fase di selezione.
• Gli autori dimostrano che questa trasformazione è senza perdita (esatta) sotto l'assunzione di un insieme di incertezza convesso, proprio e semicontinuo inferiormente.

2.2 Riformulazione come MDP

Il problema combinatorio di livello superiore viene riformulato come un MDP con ricompense dense:

• Stato: L'insieme corrente di agenti vulnerabili selezionati e i loro budget di perturbazione.
• Azione: Selezionare il prossimo agente da aggiungere all'insieme di attacco.
• Ricompensa: Definita come la riduzione del valore atteso del sistema quando un nuovo agente viene aggiunto all'insieme di attacco, calcolata efficientemente utilizzando la funzione di valore regolarizzata derivata nel passaggio 2.1.

2.3 Algoritmi

Vengono proposti due algoritmi per risolvere questo MDP:

1. VAI-Greedy: Un algoritmo greedy che seleziona sequenzialmente l'agente che massimizza la ricompensa immediata (riduzione del valore).
2. VAI-RL: Un approccio di Apprendimento per Rinforzo (utilizzando Q-learning/DQN) che impara una politica per selezionare gli agenti considerando i ritorni a lungo termine e le interazioni tra agenti.

Gli autori dimostrano che questa decomposizione preserva la soluzione ottimale dell'HAD-MFC originale.

3. Contributi Chiave

1. Definizione del Problema: La formalizzazione della VAI nel MARL su larga scala come problema HAD-MFC e la dimostrazione della sua NP-difficoltà.
2. Decomposizione Teorica: L'introduzione di un metodo per disaccoppiare il problema gerarchico utilizzando la trasformata di Fenchel-Rockafellar, risultando in un operatore di Bellman regolarizzato che permette un apprendimento indipendente a ciascun livello.
3. Soluzione Algoritmica: La formulazione della selezione di livello superiore come un MDP con ricompense dense, risolvibile tramite metodi greedy o RL, con garanzie teoriche di preservazione dell'ottimalità.
4. Validazione Empirica: Dimostrazione che il metodo identifica efficacemente le vulnerabilità critiche sia negli ambienti MARL su larga scala sia nei sistemi basati su regole.

4. Risultati Sperimentali

Il metodo è stato valutato su tre ambienti: Battle (piattaforma MAGENT), Taxi Matching e Vicsek (un sistema basato su regole).

• Prestazioni: I metodi VAI proposti (VAI-Greedy e VAI-RL) hanno superato cinque baseline (Random, Degree Centrality, Bi-level RL, PIANO e RTCA) in 17 compiti su 18.
• Confronto:
  • I metodi euristici (ad es. Degree Centrality) hanno fallito nel MARL su larga scala perché si basano su strutture grafiche che non catturano le interazioni non lineari e apprese degli agenti MARL.
  • I metodi esistenti basati sull'apprendimento (ad es. RTCA, Bi-level RL) hanno faticato a causa della complessità computazionale del problema gerarchico accoppiato.
  • VAI-RL vs. VAI-Greedy: VAI-RL ha generalmente superato VAI-Greedy, in particolare negli scenari con un numero maggiore di attaccanti, poiché modella meglio i ritorni a lungo termine e le interazioni sinergiche tra agenti.
• Efficienza: Sebbene VAI richieda un addestramento una tantum della funzione di valore regolarizzata (~1 ora), il processo di selezione successivo è altamente efficiente. Il costo computazionale complessivo è comparabile o inferiore rispetto alle baseline come RTCA, che soffre di un elevato sovraccarico dovuto alla ricerca evolutiva.
• Accuratezza Predittiva: La funzione di valore regolarizzata ha mostrato una forte correlazione di Pearson ($R=0.97$ per Battle, $R=0.91$ per Taxi) con la ricompensa effettiva ottenuta eseguendo attacchi avversari completi a livello inferiore, validandone l'uso come proxy.

5. Significato e Affermazioni

Il documento afferma che il suo contributo principale è fornire uno strumento diagnostico per sviluppatori e amministratori di sistemi per identificare i "punti deboli" nei sistemi MARL su larga scala.

• Valutazione della Robustezza: Identificando gli agenti più vulnerabili, i praticanti possono valutare la robustezza nel caso peggiore del sistema e potenzialmente rafforzare questi specifici agenti.
• Scalabilità: Il metodo affronta il collo di bottiglia della scalabilità dei precedenti lavori avversari sul MARL, che erano limitati a sistemi su piccola scala.
• Applicabilità: L'approccio è applicabile non solo alle politiche MARL apprese, ma anche a sistemi basati su regole (come il modello Vicsek), a condizione che le regole possano essere approssimate tramite funzioni di valore.

Gli autori mantengono una posizione modesta riguardo alle implicazioni di sicurezza, notando che, sebbene gli attaccanti potrebbero teoricamente utilizzare questo metodo, il requisito di accesso alle traiettorie del sistema lo rende più accessibile ai difensori per irrobustire i sistemi che agli attaccanti per sfruttarli. Il lavoro suggerisce direzioni future nell'estendere la VAI a domini reali complessi come le reti sociali e i modelli basati su agenti economici.