Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

Sintesi Tecnica: Banditi Multi-Agente Robusti con Ricompense Heavy-Tailed e Asimmetria Informativa

Formulazione del Problema
Questo lavoro affronta il problema dei Multi-Armed Bandit (MAB) in un contesto multi-agente decentralizzato in cui le distribuzioni dei premi sono "heavy-tailed" (a coda pesante). A differenza della letteratura standard che assume ricompense sub-gaussiane, questo articolo considera distribuzioni in cui il momento $(1+\epsilon)$-esimo è finito ($E[|X - \mu|^{1+\epsilon}] \le v]$), ma la varianza può essere infinita. Lo studio si concentra su $M$ giocatori che devono coordinarsi per massimizzare le ricompense congiunte senza comunicazione online. Gli autori definiscono tre distinti regimi di asimmetria informativa:

1. Problema A (Ricompense Comuni, Azioni Non Osservate): Tutti i giocatori osservano la stessa realizzazione del premio per un'azione congiunta, ma non possono vedere le singole azioni scelte dagli altri.
2. Problema B (Ricompense Indipendenti, Azioni Osservate): I giocatori osservano l'azione congiunta intrapresa dal gruppo, ma ricevono campioni di premio indipendenti e i.i.d.
3. Problema C (Ricompense Indipendenti, Azioni Non Osservate): I giocatori non osservano né la ricompensa comune né le azioni degli altri; ciascuno riceve solo il proprio campione indipendente.

Metodologia e Algoritmi
Gli autori propongono algoritmi decentralizzati robusti per ogni regime, adattando stimatori robusti della media (specificamente le medie troncate) al contesto multi-agente.

• Problema A (mRUCB-A): Poiché i premi sono condivisi, tutti i giocatori mantengono stime statistiche identiche se seguono una regola deterministica. L'algoritmo impiega un indice Robust Upper Confidence Bound (RUCB). I giocatori concordano su un ordinamento lessicografico per risolvere i casi di parità in modo coerente. Poiché le stime rimangono sincronizzate, il problema si riduce efficacemente a un bandit a singolo agente heavy-tailed sullo spazio delle azioni congiunte, senza incorrere costi aggiuntivi dovuti all'asimmetria delle azioni.
• Problema B (mRUCB-Intervals): Con azioni osservate ma premi indipendenti, le stime dei giocatori divergono. Per prevenire il disallineamento, gli autori sostituiscono la massimizzazione dell'indice con una strategia di eliminazione round-robin. I giocatori mantengono intervalli di confidenza per ogni braccio. Se l'intervallo di un giocatore per un braccio si trova strettamente al di sotto di quello di un altro, lo segnalano deviando dall'azione congiunta programmata (prelevando un braccio individuale diverso). Poiché le azioni sono osservabili, questa deviazione funge da canale di comunicazione implicito a 1 bit, causando l'eliminazione simultanea del braccio subottimale da parte di tutti i giocatori. I round di segnalazione scartano i premi per mantenere l'allineamento statistico.
• Problema C (mHT-DSEE): Nel setting completamente asimmetrico, né i premi condivisi né le azioni osservate permettono la segnalazione implicita o la sincronizzazione delle stime. Gli autori utilizzano uno Schedule Deterministico per Esplorazione ed Exploitation (DSEE). I giocatori seguono uno schema di esplorazione ciclico pre-concordato per una durata determinata da una funzione $w(t)$ (ad esempio, $\lceil \log t \rceil$). Una volta esaurito il budget di esplorazione, i giocatori passano all'exploitation basandosi sui propri indici RUCB calcolati esclusivamente dai campioni di esplorazione. La sincronizzazione è mantenuta perché lo schema dipende solo dall'indice del round $t$.

Contributi Chiave e Risultati Teorici
Il documento deriva limiti di regret che quasi eguagliano i tassi centralizzati heavy-tailed per ogni setting:

• Problema A: Il regret atteso è $O(\log T \sum \Delta_a^{-1/\epsilon})$. Gli agenti decentralizzati non incorrono in costi aggiuntivi rispetto a un apprendista centralizzato, poiché la ricompensa condivisa garantisce una perfetta sincronizzazione.
• Problema B: Il limite di regret è $O(\log T \sum \Delta_a^{-1/\epsilon})$ più termini costanti indipendenti dall'orizzonte $T$. Il meccanismo utilizza le deviazioni dalle azioni come canale di segnalazione implicita; il costo della segnalazione è limitato da $(K^M - 1)\Delta_{\max}$, indipendente da $T$ e dal numero di giocatori $M$.
• Problema C: Il limite di regret è $O(K^M \log^2 T)$. Questo setting richiede uno schema "anytime" pre-impegnato, introducendo un fattore $\log T$ supplementare rispetto agli altri regimi. Gli autori notano che questo fattore deriva dalla mancanza di informazioni condivise per coordinare il passaggio dall'esplorazione all'exploitation.

Validazione Sperimentale
Gli esperimenti sono stati condotti con $M=2$ giocatori, $K=2$ bracci per giocatore, e ricompense distribuite secondo una legge di Pareto (parametro di forma 2, che garantisce una media finita ma una varianza infinita).

• Risultati: Tutti e tre gli algoritmi hanno dimostrato una crescita del regret sublineare, confermando la loro capacità di identificare il braccio ottimale sotto rumore heavy-tailed.
• Trade-off: Sebbene mRUCB-A e mHT-DSEE abbiano mostrato un regret iniziale inferiore, mRUCB-Intervals (Problema B) ha infine raggiunto una crescita del regret pari a zero dopo il collasso dell'insieme attivo, mentre gli altri hanno continuato a esplorare. Gli esperimenti evidenziano che, sebbene i tassi asintotici differiscano, le costanti associate ai meccanismi di coordinamento (ad esempio, il fattore 4 rispetto al 2 nella separazione degli intervalli) influenzano significativamente le prestazioni ad orizzonti moderati.

Significatività e Rivendicazioni
Gli autori affermano che l'apprendimento decentralizzato efficace è realizzabile anche sotto significativa asimmetria informativa e rumore non-sub-gaussiano.

• Le ricompense condivise consentono una sincronizzazione senza costi.
• Le azioni osservate forniscono un canale di segnalazione implicita sufficiente a compensare la perdita di ricompense condivse, con un costo di segnalazione che non scala con l'orizzonte o con il numero di agenti.
• La piena asimmetria necessita di uno schema pre-impegnato, introducendo un costo $\log T$ aggiuntivo, evidenziando il valore anche di una minima osservabilità.

L'articolo conclude che, sebbene i processi proposti siano robusti, essi assumono la conoscenza dei parametri della coda $(\epsilon, v)$. Si suggerisce come lavoro futuro l'adattamento a parametri di pesantezza della coda sconosciuti e la derivazione di limiti inferiori più stretti per il caso completamente asimmetrico.