Learning in Matching Games with Bandit Feedback

Sintesi Tecnica: Apprendimento in Giochi di Accoppiamento con Feedback Bandit

Formulazione del Problema
Questo articolo introduce un nuovo problema di apprendimento situato all'intersezione tra i mercati di accoppiamento bilaterale (two-sided matching) e la teoria dei giochi. L'ambiente coinvolge un mercato generalizzato con due distinti set di agenti, $P$ e $A$, che vengono accoppiati da una piattaforma centrale su un orizzonte temporale $T$. A differenza dei tradizionali problemi di accoppiamento in cui gli agenti possiedono preferenze statiche e note, o degli standard setting Multi-Armed Bandit (MAB) in cui gli agenti ricevono payoff stocastici diretti, questo framework postula che, una volta accoppiati, gli agenti intraprendano un gioco a somma zero a due giocatori (ZSG) con una matrice di payoff inizialmente ignota.

In questo scenario, gli agenti devono apprendere simultaneamente la dinamica sottostante del gioco e derivare le proprie preferenze dagli esiti di queste interazioni. In ogni istante temporale $t$:

1. Una piattaforma centrale genera un accoppiamento $m_t$ basato sulle preferenze stimate degli agenti.
2. Gli agenti accoppiati selezionano le strategie (azioni miste) e campionano azioni specifiche.
3. Gli agenti ricevono feedback stocastico (ricompense) e osservano le azioni del loro partner accoppiato.
4. Gli agenti aggiornano le loro stime delle matrici di payoff e le loro preferenze per il round successivo.

La sfida centrale è apprendere un Equilibrio di Accoppiamento (Matching Equilibrium), un concetto di soluzione definito in [10] dove l'accoppiamento è stabile (assenza di coppie bloccanti) e gli agenti giocano un Equilibrio di Nash (NE) con i loro partner assegnati. La difficoltà deriva dal fatto che gli agenti non conoscono a priori le matrici di gioco e devono esplorare per formare le preferenze, mentre il meccanismo di accoppiamento (tipicamente Gale-Shapley) si affida a tali preferenze per garantire la stabilità.

Metodologia e Algoritmo
Per affrontare questo problema, gli autori propongono UCB-MG, un algoritmo basato sul principio dell' "ottimismo di fronte all'incertezza". La metodologia opera come segue:

• Stime Ottimistiche: Gli agenti mantengono limiti superiori di confidenza (UCB) per le matrici di payoff dei potenziali accoppiamenti. Nello specifico, per una coppia $(p, a)$, la matrice di payoff stimata $\bar{A}_{p,a}$ viene costruita aggiungendo un bonus di confidenza alla media empirica delle ricompense osservate.
• Formazione delle Preferenze: Sulla base di queste matrici di payoff ottimistiche, gli agenti calcolano il valore ottimistico del gioco ($\bar{V}^*$) assumendo un gioco ottimale (strategie minimax) contro ciascun potenziale partner. Gli agenti classificano quindi le proprie preferenze in base a questi valori di gioco ottimistici.
• Accoppiamento: La piattaforma centrale raccoglie queste preferenze riportate ed esegue l'algoritmo di Gale-Shapley (GS) per generare un accoppiamento stabile per il round corrente.
• Esecuzione della Strategia: Una volta accoppiati, gli agenti selezionano le azioni basandosi sulle strategie minimax derivate dalle loro matrici di payoff ottimistiche, campionano le azioni e ricevono il feedback per aggiornare le loro stime.

Formulazione del Regret: Instabilità dell'Accoppiamento
Un contributo critico del paper è la definizione di una metrica di regret appropriata, denominata Instabilità dell'Accoppiamento (Matching Instability, MI). Le definizioni standard di regret dai MAB o dalla teoria dei giochi sono insufficienti perché l'obiettivo è convergere a un equilibrio congiunto di accoppiamento e strategia.

Gli autori definiscono la MI come il minimo sussidio totale richiesto per stabilizzare il mercato dato un attuale accoppiamento $m$ e un profilo di strategia $X$. Matematicamente, è la soluzione di un programma lineare che minimizza i sussidi $s_a$ soggetti a:

1. Assenza di Coppie Bloccanti: Garantire che nessuna coppia $(p, a)$ possa migliorare la propria utilità deviando, date le strategie attuali.
2. Razionalità Individuale: Garantire che gli agenti preferiscano il proprio accoppiamento rispetto all'essere non accoppiati.
3. Garanzia di Valore: Garantire che gli agenti ricevano un'utilità almeno uguale al valore minimax del loro gioco (una rilassazione della stretta condizione di Nash per facilitare un'analisi trattabile).

Il regret cumulativo $R_T$ è definito come la somma dell'Instabilità dell'Accoppiamento sull'orizzonte $T$.

Contributi Chiave

1. Definizione del Probleo di Apprendimento: Il paper formalizza il primo setting di apprendimento in cui gli agenti in un mercato bilaterale devono apprendere giochi a somma zero ignoti per formare preferenze per l'accoppiamento.
2. Metrica di Regret: Introduce l'Instabilità dell'Accoppiamento, estendendo il concetto di Instabilità di Sottoinsieme [8, 17] a contesti in cui gli agenti accoppiati giocano giochi. Questa metrica quantifica la distanza da un Equilibrio di Accoppiamento.
3. Design dell'Algoritmo: Gli autori propongono un algoritmo basato su UCB (UCB-MG) che integra la stima ottimistica del valore di gioco con il meccanismo di Gale-Shapley.
4. Garanzie Teoriche: Il paper dimostra che l'algoritmo proposto raggiunge un limite di regret sublineare e indipendente dall'istanza di $\tilde{O}(\sqrt{Tmkpa})$, dove $T$ è l'orizzonte, $m$ e $k$ sono il numero di azioni per agente, e $p$ e $a$ sono il numero di agenti per lato.
5. Generalizzazione: Il limite teorico unifica i risultati esistenti. Quando $m=k=1$, recupera il limite per l'accoppiamento bilaterale classico ($\tilde{O}(\sqrt{Tpa})$). Quando $p=a=1$, recupera il limite per l'auto-gioco (self-play) nei giochi a somma zero ($\tilde{O}(\sqrt{Tmk})$).

Risultati ed Evidenza Empirica
Gli autori forniscono una validazione empirica utilizzando istanze sintetiche in cui le matrici di payoff sono campionate da una distribuzione normale. Confrontano tre scenari:

• Self-Play: Entrambi i lati seguono l'algoritmo UCB-MG.
• Nash-Response: Un lato conosce le vere matrici di gioco e gioca la strategia di Equilibrio di Nash, mentre l'altro apprende.
• Best-Response: Un lato conosce le vere matrici e le strategie dell'avversario, giocando la migliore risposta.

I risultati indicano che il sistema apprende un esito stabile in tutti gli scenari, mostrando una crescita sublineare del regret. Come previsto, lo scenario Nash-Response produce il regret più basso. Interessante è che, sebbene lo scenario Best-Response superi inizialmente il Self-Play, le sue prestazioni degradano all'aumentare della dimensione del mercato (numero di agenti e azioni), probabilmente a causa della complessità introdotta dal fatto che un lato sfrutta l'altro.

Significatività e Direzioni Future
Il paper rivendica la sua importanza come primo passo verso la comprensione dell'apprendimento in ambienti in cui gli agenti ricevono payoff solo dopo l'interazione attraverso azioni in un gioco, piuttosto che ricevere segnali di preferenza diretti. Dimostra che esiti stabili possono essere appresi efficientemente in tali contesti complessi e accoppiati.

Gli autori inquadrano modestamente questo lavoro come una fondazione per la ricerca futura. Identificano diverse direzioni aperte:

• Estendere il modello dai giochi a somma zero ai giochi a somma generale.
• Integrare algoritmi di apprendimento senza regret (come Exp3) nel framework di accoppiamento per gestire la dinamica a somma non nulla.
• Rilassare l'assunzione che gli agenti osservino le azioni del partner.
• Esplorare modelli di gioco alternativi (giochi di Markov, giochi di Stackelberg) e strutture di accoppiamento (mercati many-to-one).
• Investigare contesti decentralizzati in cui gli agenti selezionano sia gli accoppiamenti che le strategie senza un coordinatore centrale.