Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games

Titolo: Iterazione delle Politiche per Giochi Stocastici di Stackelberg a Somma Generale con Due Giocatori

1. Problema e Contesto

Il lavoro affronta i giochi stocastici di Stackelberg (SSG) a due giocatori e a somma generale. In questo scenario:

• Esiste un Leader (giocatore A) e un Follower (giocatore B).
• Il Follower risponde sempre alla strategia del Leader adottando una migliore risposta (best-response) rispetto alla propria funzione di ricompensa.
• L'obiettivo del Leader è ottimizzare la propria politica considerando il fatto che il Follower reagirà in modo ottimale alle sue azioni.

Limitazioni degli approcci esistenti:

• Gli attuali metodi basati su gradiente delle politiche o iterazione del valore non garantiscono un miglioramento monotono delle prestazioni del Leader quando il Follower è una migliore risposta.
• In contesti a somma generale, l'Equilibrio di Stackelberg Stazionario (SSE) non sempre esiste.
• Gli algoritmi precedenti (es. Bucarey et al., 2022; Zhang et al., 2020a) convergono verso punti fissi di operatori di programmazione dinamica che, sebbene stabili, non garantiscono che la politica risultante sia ottimale per il Leader o che corrisponda a un SSE, portando potenzialmente a politiche di bassa qualità.

2. Metodologia Proposta

Gli autori propongono un nuovo algoritmo di Iterazione delle Politiche (Policy Iteration) basato su un teorema di miglioramento delle politiche specifico per gli SSG.

Concetti Chiave:

1. Analisi degli Operatori DP: Gli autori dimostrano che il punto fisso degli operatori di programmazione dinamica usati in lavori precedenti non coincide necessariamente con la funzione di valore dell'Equilibrio di Stackelberg (SE). Il punto fisso massimizza il valore del Leader solo rispetto a una specifica risposta del Follower (definita dal punto fisso stesso), non rispetto alla migliore risposta reale del Follower per ogni possibile politica del Leader.
2. Ottimalità Pareto (Pareto-Optimality): Poiché un SSE unico potrebbe non esistere (specialmente quando ci sono trade-off tra i valori in diversi stati), gli autori introducono l'Ottimalità Pareto come obiettivo esteso.
   • Una funzione di valore è Pareto-ottima se non esiste un'altra funzione di valore raggiungibile che la domini strettamente in tutti gli stati.
   • Se un SSE esiste, esso corrisponde a un punto Pareto-ottimo. Se non esiste, l'algoritmo converge verso il "fronte di Pareto".
3. Teorema di Miglioramento delle Politiche: Viene derivato un teorema (Teorema 8) che estende il classico teorema di miglioramento delle politiche degli MDP a un agente singolo al contesto SSG. Questo teorema permette di verificare se una nuova politica $f$ è migliore di una politica di base $f'$ senza dover calcolare esplicitamente la funzione di valore completa per $f$, utilizzando una funzione Q definita come:
   $$Q^{f'\dagger}_A(s, f) := r_A(s, f(s), R^*_B(s, f)) + \gamma_A \mathbb{E}[V^{f'\dagger}_A(s')]$$
   dove $R^*_B$ è la migliore risposta del Follower.

L'Algoritmo (Pareto-Optimal Policy Iteration):
L'algoritmo (Algorithm 1) procede iterativamente:

1. Calcola il valore della politica corrente del Leader sotto la migliore risposta del Follower.
2. Identifica l'insieme di politiche candidate che soddisfano la condizione di miglioramento (dove la nuova Q-value domina o è uguale al valore attuale).
3. Seleziona la prossima politica da questo insieme, massimizzando una scalarizzazione Pareto-compliant (es. una somma pesata dei valori negli stati).
4. Ripete il processo fino a convergenza.

Per gestire spazi di ricerca grandi, viene proposta una strategia di splitting dello spazio delle politiche (Appendice G), che divide lo spazio in sottoinsiemi dove la migliore risposta del Follower è costante, rendendo l'ottimizzazione più efficiente.

3. Risultati Teorici e Garanzie

Il paper fornisce garanzie teoriche rigorose:

• Miglioramento Monotono: L'algoritmo garantisce che il valore dello stato del Leader non diminuisca mai durante l'iterazione ($V_{t+1} \succeq V_t$).
• Convergenza: La sequenza di funzioni di valore converge a un limite $v_\infty$.
• Convergenza al Fronte di Pareto:
  • Il limite $v_\infty$ appartiene al bordo dell'insieme dei valori raggiungibili ($\partial V$).
  • Caso Myopic (Leader con $\gamma_A = 0$): Se il Leader è miope (non considera il futuro, $\gamma_A = 0$), l'algoritmo garantisce la convergenza a una politica Pareto-ottima. Questo è il primo risultato teorico di questo tipo per SSG a somma generale con leader miope.
  • Caso Generale ($\gamma_A > 0$): Il limite soddisfa una condizione di vicinanza al fronte di Pareto, garantendo che non esistano politiche che lo dominino significativamente.

4. Contributi Principali

1. Derivazione del Punto Fisso: Analisi esplicita che rivela come i punti fissi degli operatori DP esistenti non garantiscano prestazioni ottimali per il Leader in assenza di un SSE.
2. Teorema di Miglioramento: Derivazione di un teorema di miglioramento delle politiche specifico per giochi di Stackelberg stocastici a somma generale con follower a migliore risposta.
3. Nuovo Algoritmo: Proposta di un algoritmo di iterazione delle politiche che garantisce il miglioramento monotono e la convergenza verso soluzioni Pareto-ottime.
4. Estensione dell'Ottimalità: Introduzione dell'ottimalità Pareto come soluzione robusta quando l'SSE non esiste, dimostrando che le politiche Pareto-ottime esistono sempre e coincidono con l'SSE se quest'ultimo è presente.

5. Significato e Applicazioni

Questo lavoro è significativo perché risolve un problema fondamentale nella teoria dei giochi multi-agente e nell'apprendimento per rinforzo: la mancanza di garanzie di convergenza e qualità delle politiche in giochi stocastici complessi dove l'equilibrio classico non esiste.

Applicazioni Pratiche:

• Progettazione di Piattaforme E-commerce: Un proprietario di un sito (Leader) può configurare dinamiche di pagina, pubblicità e bonus per massimizzare il profitto a lungo termine, anticipando le risposte ottimali degli utenti (Follower).
• Policy Teaching e Attacchi di Avvelenamento: Il modello può essere usato per "insegnare" a un agente (Follower) a comportarsi in un certo modo modificando le probabilità di transizione dell'ambiente, o per analizzare la vulnerabilità di sistemi RL a manipolazioni esterne.
• Giochi Decentralizzati: Fornisce un metodo per prendere decisioni ottimali in ambienti dove un attore principale deve guidare il comportamento di altri agenti razionali senza che questi ultimi siano necessariamente cooperativi o miope.

In sintesi, il paper offre un framework teorico solido e un algoritmo pratico per ottimizzare le strategie in scenari competitivi/cooperativi complessi, superando le limitazioni delle metodologie attuali basate su gradienti o operatori di programmazione dinamica tradizionali.