Sintesi Tecnica: Multi-User Dueling Bandits: Un Approccio Equo utilizzando il Nash Social Welfare

Definizione del Problema

Il documento affronta il problema del Fair Multi-User Dueling Bandit, un contesto in cui un agente apprende da dati di preferenza a coppie forniti da $D$ utenti distinti su un orizzonte temporale $T$ con $K$ bracci (arms). A differenza dei classici dueling bandit che assumono un singolo modello di preferenza o aggregano le preferenze in un'unica matrice, questo lavoro considera uno scenario in cui ogni utente $d$ possiede una matrice di preferenza potenzialmente distinta $P_d$.

La sfida centrale è apprendere una policy che bilanci gli interessi di questi utenti eterogenei senza marginalizzare i gruppi minoritari. Gli approcci standard che ottimizzano per il benessere medio (utilitaristico) spesso favoriscono la maggioranza statistica, portando a esiti iniqui per gli utenti con preferenze divergenti. Per affrontare questo, gli autori definiscono l'obiettivo utilizzando il Nash Social Welfare (NSW), che massimizza il prodotto delle utilità degli utenti. Questo obiettivo penalizza intrinsecamente la disuguaglianza, garantendo che l'utilità di nessun singolo utente venga portata a zero.

Un ostacolo tecnico critico in questo contesto è la mancanza di ricompense assolute; il feedback è puramente relativo (risultati binari che indicano quale di due bracci sia preferito). Per definire l'utilità in questo contesto relativo, gli autori assumono l'esistenza di un vincitore di Condorcet per ogni utente (un braccio che batte ogni altro braccio con probabilità $>0.5$). L'utilità dell'utente è quindi definita come un punteggio derivato dalla probabilità che un braccio batta il particolare vincitore di Condorcet di quell'utente.

Metodologia

Framework Teorico

Gli autori formalizzano il problema definendo una funzione di punteggio $s_d(i) = 2P_{d, i, a^*_d}$, dove $a^*_d$ è il vincitore di Condorcet per l'utente $d$. L'utilità di una policy $\pi$ per l'utente $d$ è il punteggio atteso $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$. L'obiettivo globale è il Nash Social Welfare:
$$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$$
L'obiettivo è minimizzare il regret cumulativo atteso rispetto alla policy ottimale $\pi^*$ che massimizza questo prodotto.

Analisi della Complessità (Hardness)

Il documento stabilisce un limite inferiore di regret fondamentale di $\Omega(T^{2/3} \min(K, D)^{1/3})$. Questo risultato dimostra che il requisito di massimizzare il NSW tra utenti con vincitori di Condorcet contrastanti introduce una difficoltà significativa rispetto ai classici dueling bandit (che tipicamente raggiungono un regret di $O(\log T)$). La difficoltà deriva dal fatto che l'algoritmo deve giocare "cattivi" vincitori di Condorcet (ottimali per un utente ma che producono un'utilità vicina allo zero per altri) per distinguerli dai vincitori "buoni", creando un compromesso tra costi di esplorazione e regret istantaneo.

Algoritmi

Vengono proposti due algoritmi per raggiungere questo obiettivo, entrambi incorporando una fase di identificazione del vincitore di Condorcet:

1. Fair-Explore-Then-Commit (Fair-ETC):

   • Fase 1 (Identificazione): Utilizza un algoritmo Dvoretzky-Kiefer-Wolfowitz Tournament (DKWT) modificato per identificare l'insieme dei vincitori di Condorcet $\hat{A}^*$ per tutti i $D$ utenti. Questa fase sfrutta le interazioni condivise per aggiornare simultaneamente i margini empirici per tutti gli utenti.
   • Fase 2 (Esplorazione): Stima i punteggi di tutti i bracci rispetto ai vincitori di Condorcet identificati.
   • Fase 3 (Impegno/Commitment): Calcola la policy $\hat{\pi}$ che massimizza l'empirico NSW e si impegna su di essa per il resto dell'orizzonte.

2. Fair-$\epsilon$-Greedy:

   • Questo algoritmo alterna esplorazione ed esploitazione durante tutto l'orizzonte.
   • Inizia con la stessa fase di identificazione del vincitore di Condorcet.
   • Ad ogni passo $t$, con probabilità $\epsilon_t$, esplora giocando coppie che coinvolgono i vincitori di Condorcet stimati (usando un programma round-robin) per raffinare le stime dei punteggi.
   • Con probabilità $1-\epsilon_t$, sfrutta la policy che massimizza l'attuale NSW empirico.
   • Il tasso di esplorazione $\epsilon_t$ decade nel tempo per garantire la convergenza.

Entrambi gli algoritmi sono dimostrati raggiungere un limite superiore di regret di $\tilde{O}(T^{2/3})$, che corrisponde alla dipendenza del limite inferiore dall'orizzonte temporale $T$ salvo fattori logaritmici.

Contributi Chiave

1. Formulazione del Problema: La prima formalizzazione del problema Fair Multi-User Dueling Bandit, modellando le utilità distinte degli utenti basate sui loro singoli vincitori di Condorcet e adottando il NSW come obiettivo di equità.
2. Limite Inferiore di Regret: La derivazione di un limite inferiore di regret di $\Omega(T^{2/3} \min(K, D)^{1/3})$, che gli autori sostengono essere il primo risultato a quantificare il costo dell'equità nei dueling bandit con preferenze eterogenee.
3. Soluzioni Algoritmiche: La proposta degli algoritmi Fair-ETC e Fair-$\epsilon$-Greedy, accompagnati da limiti superiori di regret teorici che corrispondono alla dipendenza del limite inferiore da $T$.
4. Validazione Empirica: Simulazioni estese che dimostrano come i processi proposti superino i baselines utilitaristici in termini di metriche di equità (coefficiente di Gini, utilità minima dell'utente) mantenendo un regret cumulativo competitivo.

Risultati Sperimentali

Gli autori hanno valutato i loro algoritmi sia su preferenze generate casualmente che su dati reali (il dataset Sushi, raggruppati in utenti macroscopici).

• Preferenze Casuali: In varie configurazioni di utenti ($D$) e bracci ($K$), sia Fair-ETC che Fair-$\epsilon$-Greedy hanno dimostrato un regret sublineare, superando costantemente i baselines utilitaristici e un baseline uniforme sugli utenti.
• Metriche di Equità: Gli algoritmi proposti hanno ottenuto il Nash Social Welfare più elevato e coefficienti di Gini significativamente più bassi rispetto agli approcci utilitaristici. Hanno anche mantenuto un'utilità minima dell'utente più alta, indicando una migliore protezione per le preferenze delle minoranze.
• Preferenze Raggruppate (Clustered): In scenari con cluster distinti di maggioranza e minoranza (simulando preferenze polarizzate), gli algoritmi utilitaristici hanno favorito la maggioranza, portando a un'alta disuguaglianza. I processi equi proposti hanno bilanciato con successo gli interessi, mantenendo bassi i coefficienti di Gini e un'alta utilità minima.
• Dataset Sushi: Sui dati reali, i metodi proposti hanno ottenuto il minor regret cumulativo sia nell'impostazione $D=5$ che in quella $D=10$. Sebbene un baseline uniforme abbia mostrato un'equità leggermente migliore nel caso altamente frammentato $D=10$, esso ha sofferto di un regret decisamente inferiore.

Significato e Rivendicazioni

Il documento sostiene di essere il primo lavoro a quantificare il costo dell'equità nei dueling bandit con preferenze eterogenee, stabilendo un limite inferiore di regret fondamentale di $\Omega(T^{2/3})$. Gli autori posizionano il loro lavoro come un passo necessario verso un machine learning incentrato sull'uomo, dove ottimizzare per la preferenza media è insufficiente e potenzialmente dannoso per i gruppi minoritari.

Integrando l'obiettivo del Nash Social Welfare nel framework dei dueling bandit, il lavoro fornisce una base teorica e algoritmica per apprendere policy che bilanciano efficienza ed equità. Gli autori osservano che il loro approccio è distinto dai precedenti lavori sui multi-agent bandit (ad esempio, Hossain et al., 2021; Jones et al., 2023) perché opera in un contesto di preferenza relativa piuttosto che con ricompense assolute, richiedendo tecniche di stima dell'utilità fondamentalmente diverse.

Il documento si conclude con modestia, riconoscendo che i lavori futuri potrebbero estendere questo framework ai dueling bandit contestuali, agli spazi di azione continui e ai casi in cui l'assunzione del vincitore di Condorcet non è valida (potenzialmente utilizzando punteggi Copeland o Borda).