Online Learning and Equilibrium Computation with Ranking Feedback

1. Il Problema

Il lavoro si concentra sul apprendimento online in ambienti arbitrari e potenzialmente avversari, dove l'agente (o il learner) non riceve feedback numerici diretti (utilità o ricompense scalari) dopo aver intrapreso un'azione. Invece, l'agente osserva solo un ranking (una permutazione) di un insieme di azioni proposte.

Questo scenario è rilevante in diverse applicazioni reali:

• Apprendimento con Feedback Umano (RLHF): È spesso più facile per gli umani classificare le risposte di un modello linguistico che assegnare punteggi numerici calibrati.
• Privacy: In alcune piattaforme, i valori di utilità reali potrebbero essere nascosti per motivi di sicurezza o privacy, rendendo disponibili solo le preferenze relative.
• Calcolo dell'Equilibrio nei Giochi: In giochi ripetuti a forma normale, i giocatori possono fornire solo classifiche delle strategie degli avversari.

Il paper analizza due meccanismi di generazione del ranking basati sul modello Plackett-Luce (PL):

1. InstUtil Rank: Il ranking è basato sull'utilità istantanea al timestep corrente $t$.
2. AvgUtil Rank: Il ranking è basato sull'utilità media nel tempo fino al timestep corrente $t$.

L'obiettivo è minimizzare il rimpianto esterno (external regret) e, nel contesto dei giochi, calcolare un Equilibrio Correlato Grossolano (CCE).

2. Metodologia e Risultati Teorici

2.1 Risultati di Impossibilità (Lower Bounds)

Gli autori stabiliscono prima dei limiti fondamentali, dimostrando che il rimpianto sublineare (no-regret) non è sempre ottenibile:

• InstUtil Rank: Per qualsiasi temperatura $\tau$ costante (non troppo piccola), è impossibile ottenere un rimpianto sublineare in generale, sia in setting full-information che bandit. L'ambiente avversario può cambiare le utilità così rapidamente da rendere il ranking non informativo.
• AvgUtil Rank: Se il modello di ranking è troppo deterministico (cioè $\tau \to 0^+$), anche con feedback basato sulla media temporale, il rimpianto rimane lineare. Questo perché il feedback perde informazioni sulle differenze di utilità tra le azioni.

2.2 Assunzioni per Risultati Positivi

Per superare questi limiti, il paper introduce l'Assunzione 5.2: la sequenza dei vettori di utilità deve avere una variazione totale sublineare nel tempo ($P(T) = \sum ||u(t) - u(t-1)|| \le O(T^q)$ con $q < 1$).

• In contesti di gioco, se tutti i giocatori usano algoritmi no-regret standard, questa condizione è naturalmente soddisfatta.

2.3 Algoritmi Proposti

Sotto l'assunzione di variazione sublineare, gli autori sviluppano nuovi algoritmi che stimano le utilità numeriche dai ranking osservati:

• Stima dell'Utilità (Utility Estimation): Utilizzano una finestra scorrevole delle permutazioni recenti per stimare i vettori di utilità. Sfruttano la struttura logistica del modello Plackett-Luce decomponendo il ranking in confronti a coppie (pairwise comparisons) per invertire la funzione sigmoide e recuperare le utilità.
• Algoritmo per InstUtil Rank (Algoritmo 2):
  • Stima l'utilità istantanea $u(t)$ dai ranking.
  • Utilizza un oracolo di apprendimento no-regret standard (es. FTRL, PGD) come "scatola nera" alimentata dalle utilità stimate.
  • Nel setting bandit, introduce un'esplorazione forzata (miscelando la strategia dell'oracolo con una distribuzione uniforme) per garantire che ogni azione venga proposta con probabilità positiva.
• Algoritmo per AvgUtil Rank (Algoritmo 3):
  • Stima l'utilità media $u_{avg}(t)$.
  • Nel setting full-information, dimostra che l'assunzione di variazione sublineare può essere rimossa se $\tau$ è costante. La stabilità degli algoritmi FTRL permette di gestire l'errore di stima senza vincoli sulla variazione delle utilità.
  • Nel setting bandit, richiede l'assunzione di variazione sublineare con $q < 1/3$. Utilizza una tecnica di "blocchi" (blocking) per stimare l'utilità media riducendo la varianza dell'estimatore.

2.4 Calcolo dell'Equilibrio

Quando tutti i giocatori in un gioco a forma normale seguono questi algoritmi:

• Il rimpianto esterno di ogni giocatore è sublineare.
• Di conseguenza, la strategia media temporale congiunta converge a un Equilibrio Correlato Grossolano (CCE) approssimato.

3. Contributi Chiave

1. Modellazione Unificata: Analisi sistematica del learning online con feedback di ranking in ambienti non stocastici e avversari, distinguendo tra utilità istantanea e media temporale.
2. Limiti di Impossibilità: Dimostrazione che il rimpianto sublineare è impossibile in generale per InstUtil Rank e per AvgUtil Rank con $\tau$ molto piccolo, evidenziando la necessità di vincoli sulla variazione delle utilità o su $\tau$.
3. Algoritmi Nuovi: Sviluppo di algoritmi che trasformano il problema di ranking in un problema di apprendimento con utilità numeriche stimate, garantendo rimpianto sublineare sotto l'assunzione di variazione limitata.
4. Rimozione dell'Assunzione: Dimostrazione che per AvgUtil Rank in setting full-information, l'assunzione di variazione sublineare non è necessaria se $\tau$ è costante.
5. Validazione Sperimentale: Applicazione a un task di routing di Large Language Models (LLM), dove il sistema deve selezionare il modello migliore basandosi solo sui ranking degli utenti.

4. Risultati Sperimentali

Gli esperimenti simulano un sistema di routing per LLM (es. GPT-4o, Llama-3, Qwen) dove gli utenti classificano le risposte.

• Setup: Feedback di tipo bandit (solo un sottoinsieme di modelli proposto) con ranking basato sull'utilità media (AvgUtil Rank).
• Risultati: L'Algoritmo 3 mostra una diminuzione del rimpianto medio nel tempo, convergendo verso le prestazioni del modello fisso migliore in hindsight.
• Robustezza: Gli algoritmi funzionano bene per diversi valori di temperatura $\tau$ e numeri di azioni proposte $K$, confermando la validità pratica anche quando i parametri teorici (come $q < 1/3$) vengono leggermente violati.

5. Significato e Implicazioni

Questo lavoro è significativo perché:

• Colma un Gap Teorico: Estende la teoria dell'apprendimento online (tipicamente basata su feedback numerici) al dominio del feedback di ranking, cruciale per l'interazione uomo-macchina.
• Fornisce Garanzie di Equilibrio: Collega direttamente l'apprendimento con ranking alla teoria dei giochi, garantendo che l'interazione ripetuta porti a soluzioni di equilibrio stabili (CCE), anche senza feedback numerici espliciti.
• Applicabilità Reale: Offre una soluzione teorica solida per problemi pratici come il RLHF, il matching su piattaforme (dating, ride-sharing) e la raccomandazione personalizzata, dove i dati numerici sono spesso assenti o inaffidabili.

In sintesi, il paper dimostra che, sebbene il feedback di ranking sia intrinsecamente più informativo rispetto ai numeri, è possibile ottenere prestazioni ottimali (no-regret) e convergenza all'equilibrio, a patto di gestire correttamente l'incertezza del modello di ranking (temperatura $\tau$) e la dinamicità dell'ambiente (variazione delle utilità).