Giochi stocastici

Più agenti, uno stato che evolve nel tempo, e ognuno con la propria utilità: il framework formale di tutto il multi-agent reinforcement learning.

Perché questo capitolo

Negli ultimi sedici capitoli abbiamo costruito due metà di una stessa scacchiera. Da un lato i giochi statici, da giochi-definizione a dilemma-prigioniero: più giocatori che decidono in modo simultaneo, payoff fissi, niente tempo. Dall’altro l’apparato del decision making sequenziale, da markov-decision-process a ppo-trpo: un agente che impara a navigare un ambiente stocastico una mossa alla volta. Manca il pezzo che le unisce.

Il pezzo si chiama gioco stocastico, o equivalentemente Markov game. È il framework matematico che descrive ciò che succede quando più agenti, ognuno con la propria utilità, decidono ripetutamente dentro un ambiente che cambia probabilisticamente in funzione delle loro scelte congiunte. È la lingua franca con cui sono formalizzati AlphaStar (StarCraft II), OpenAI Five (Dota 2), Cicero (Diplomacy), gran parte della ricerca su cooperative AI, l’analisi teorica delle GAN e — meno esplicitamente, ma di fatto — i framework multi-agent LLM come AutoGen e CrewAI.

Ci sono tre ragioni per fermarsi qui prima di proseguire verso il MARL applicato. La prima è che senza questo framework non esiste un linguaggio comune per parlare di “agenti che giocano contro o con altri agenti nel tempo”. La seconda è che il framework rende immediatamente visibili le difficoltà strutturali — non-stationarity, equilibrium selection, joint action curse — che separano il single-agent RL dal multi-agent. La terza è che molte intuizioni di GAN, self-play e league training, che oggi sembrano trucchi ingegneristici scollegati, sono in realtà istanze concrete di problemi matematici già posti e parzialmente risolti negli anni Cinquanta.

Contesto

Il concetto nasce nel 1953, in un articolo di sei pagine sui Proceedings of the National Academy of Sciences. L’autore è Lloyd Shapley, matematico americano, allora trentenne, futuro Premio Nobel per l’Economia 2012. Shapley introduce il gioco stocastico zero-sum a due giocatori con probabilità di terminazione, dimostra che il valore esiste ed è unico, e propone un algoritmo iterativo per calcolarlo. È il primo lavoro a unire la teoria dei giochi (ferma alla forma normale e a quella estesa) e la programmazione dinamica (Bellman, lavoro coevo).

Per quarant’anni il gioco stocastico resta uno strumento prevalentemente economico-matematico. Riemerge nel 1994 in un articolo ICML di Michael Littman, informatico di Brown University: “Markov games as a framework for multi-agent reinforcement learning”. Littman ribattezza l’oggetto Markov game (lo stesso oggetto, nome diverso, audience diversa: ML invece di econ), introduce minimax-Q come variante model-free dell’iterazione di Shapley, e dimostra convergenza per il caso zero-sum due giocatori. Da quel momento il framework diventa standard nel multi-agent RL.

I lavori successivi estendono in due direzioni. Junling Hu e Michael Wellman (Università del Michigan) propongono nel 2003 Nash-Q-learning per il caso general-sum: a ogni passo si calcola il Nash dello stage game corrente e lo si usa come bootstrap. La convergenza è dimostrata, ma sotto condizioni così restrittive che in pratica raramente vale. Eric Maskin e Jean Tirole (economisti, Premi Nobel 2007 e 2014) introducono nei loro lavori sui mercati dinamici il concetto di Markov perfect equilibrium, l’analogo subgame-perfect per giochi stocastici. Jakob Foerster (Oxford, ex-OpenAI) costruisce nel 2018 LOLA — Learning with Opponent-Learning Awareness — un policy gradient che modella esplicitamente l’apprendimento dell’avversario.

Vale anche la pena chiarire una distinzione tassonomica spesso trascurata. Stochastic game (termine di Shapley) e Markov game (termine di Littman) sono lo stesso oggetto matematico. Dec-POMDP (Decentralized POMDP) è un caso particolare cooperative con osservabilità parziale. POSG (Partially Observable Stochastic Game) è la versione completamente generale con osservabilità parziale e payoff arbitrari. La gerarchia è: MDP ⊂ stochastic game ⊂ POSG, e in parallelo MDP cooperativo ⊂ Dec-POMDP ⊂ POSG cooperativo. La maggior parte della ricerca pratica vive nel POSG; la teoria pulita vive nel stochastic game completamente osservabile.

Prima di proseguire vale la pena fissare la differenza con i due vicini di outline. I capitoli 113-118 erano giochi statici: un solo round, niente stato, decisione simultanea. I capitoli 122-128 erano MDP e algoritmi di RL: un solo agente, stato dinamico, decisione sequenziale. Il gioco stocastico è la generalizzazione che aggiunge entrambi gli assi insieme: più agenti e stato dinamico. Ne segue che (lo argomenteremo formalmente) un gioco stocastico con un solo giocatore è esattamente un MDP, e un gioco stocastico con un solo stato è esattamente un gioco normal-form ripetuto.

L’intuizione

Primo angolo: l’MDP popolato

Si parta dall’immagine familiare di un MDP. Un agente sta in uno stato s, sceglie un’azione a, l’ambiente reagisce con una transizione probabilistica P(s'|s,a) e un reward r. La policy è una funzione che a ogni stato associa una distribuzione di probabilità sulle azioni. Tutto il gioco è “io contro un ambiente che è un automa stocastico, ma stazionario”.

Ora si introducano altri agenti dentro l’ambiente. Ognuno vede lo stato (almeno in prima approssimazione), sceglie la propria azione, e l’ambiente reagisce alla joint action — la tupla di tutte le azioni messe insieme. Il reward, però, non è più condiviso: ognuno ha la propria funzione R_i, che può puntare in direzioni opposte (zero-sum), parallele (cooperative), o oblique (general-sum).

Da fuori, dal punto di vista dell’ambiente, niente è cambiato: c’è una transizione che dipende da una joint action e produce nuovi stati e reward. Da dentro, dal punto di vista di un singolo agente, è successa una catastrofe. L’agente non sa cosa faranno gli altri. Se gli altri imparano, l’ambiente effettivo che l’agente vede non è più stazionario. La proprietà markoviana della transizione “vista dal singolo” si rompe — perché la distribuzione condizionata P(s', r | s, a_i), marginalizzata sulle azioni degli altri, dipende dalle policy correnti degli altri, che cambiano nel tempo.

È utile fissare con un’immagine concreta: un MDP è uno stagno con un solo nuotatore; un gioco stocastico è un mare aperto con dieci nuotatori che si vedono e influenzano le onde reciproche. Ogni nuotatore vede uno stato (la propria posizione e quella degli altri) e sceglie una direzione, ma le onde nel mare dipendono da tutti i nuotatori insieme. La proprietà che faceva funzionare lo stagno — l’ambiente è stazionario e prevedibile — sopravvive solo se tutti i nuotatori restano fermi nei propri pattern. Appena uno cambia comportamento, gli altri vedono un mare diverso. Questa è la non-stationarity, prima della formalizzazione.

Secondo angolo: il gioco normal-form ripetuto con stato dinamico

Si parta dall’altra metà della scacchiera. Un gioco statico in forma normale ha una matrice di payoff. I giocatori scelgono, ricevono il payoff, fine. Lo si ripeta più volte: ogni round è identico al precedente. Si ha un gioco ripetuto, oggetto su cui esiste molta letteratura (folk theorems, tit-for-tat, eccetera).

Si aggiunga ora un’idea: il gioco è ancora ripetuto, ma fra un round e l’altro c’è uno stato del mondo che evolve in funzione delle scelte fatte, e in stati diversi i payoff cambiano. Si è passati dal gioco ripetuto al gioco stocastico. La matrice di payoff non è più una sola: ce n’è una per stato. E la transizione tra stati è probabilistica e dipende dalla joint action.

I due angoli convergono allo stesso oggetto. Da una parte un MDP popolato di altri decisori; dall’altra un gioco normal-form arricchito di stato dinamico. Sono lo stesso framework guardato da angoli diversi, ed è questo che lo rende così naturale: cattura la struttura minima necessaria per parlare di “agenti che decidono nel tempo dentro un ambiente stocastico condiviso”.

Una nota pedagogica utile: la novità rispetto all’MDP non è “più giocatori che agiscono insieme”. Quella era già parzialmente catturabile in un MDP single-agent dove un singolo controllore decide tutta la joint action. La novità è che ogni giocatore ha la propria utility, e la propria policy. Questo cambia la natura del problema da ottimizzazione (un MDP risolve un problema di max) a equilibrio (un gioco stocastico risolve un fixed point di best-response). È il salto concettuale.

La meccanica

Definizione

Un gioco stocastico è una tupla

(S, A_1, …, A_N, P, R_1, …, R_N, γ)

dove:

• S è l’insieme degli stati.
• A_i è l’insieme delle azioni del giocatore i. La joint action è a = (a_1, …, a_N) ∈ A_1 × … × A_N.
• P : S × (A_1 × … × A_N) → Δ(S) è la probabilità di transizione, con la cruciale differenza rispetto all’MDP: dipende dalla joint action, non solo dall’azione di un singolo decisore.
• R_i : S × A × S → ℝ è la funzione di reward del giocatore i. Ognuno ha la propria.
• γ ∈ [0, 1) è il fattore di sconto.

Una policy stazionaria del giocatore i è una funzione π_i : S → Δ(A_i) che a ogni stato assegna una distribuzione di probabilità sulle proprie azioni. Si noti l’asimmetria: la policy è privata, dipende solo dallo stato (non dalle azioni altrui), ed è in genere mista. Il profilo è la tupla π = (π_1, …, π_N).

Il valore di stato per il giocatore i sotto un profilo π è il classico ritorno scontato atteso:

V_i^π(s) = E_π [ Σ_{t=0..∞} γ^t R_i(s_t, a_t, s_{t+1}) | s_0 = s ]

La definizione è identica a quella dell’MDP, salvo che l’aspettativa è ora rispetto al profilo congiunto π, non rispetto a una singola policy.

Equivalenze argomentabili

EQUIVALENZA: con N = 1 un gioco stocastico è esattamente un MDP. Si verifichi sostituendo: un solo giocatore, joint action coincide con a_1, transizione P(s'|s, a_1) è la solita transizione MDP, reward unico. La definizione di policy stazionaria coincide. È un’equivalenza, non un’analogia: il framework collassa termine a termine al MDP di markov-decision-process.

EQUIVALENZA: con |S| = 1 un gioco stocastico è esattamente un gioco normal-form ripetuto giocato con policy stazionarie. L’unico stato corrisponde a un unico stage game, replicato all’infinito. È equivalente al gioco ripetuto perché in ogni round la matrice è la stessa; la dinamica nel tempo viene dallo sconto, non dallo stato. Si ricollega a giochi-definizione e dilemma-prigioniero per il caso particolare |A_1|=|A_2|=2.

Queste due equivalenze formalizzano il senso in cui il gioco stocastico è “il prodotto cartesiano di MDP e gioco statico”.

L’iterazione di Shapley per zero-sum a due giocatori

Nel caso zero-sum a due giocatori, R_1 = -R_2, e si può definire un unico valore dello stato. Shapley introduce l’operatore

(T V)(s) = max_{π_1 ∈ Δ(A_1)} min_{π_2 ∈ Δ(A_2)} Σ_{a_1, a_2} π_1(a_1) π_2(a_2) [ R(s, a) + γ Σ_{s’} P(s’|s, a) V(s’) ]

dove R(s,a) è il reward del giocatore 1 (e -R del 2). Riga per riga:

• max_{π_1} min_{π_2} è il classico minimax sulle distribuzioni miste, non sulle azioni pure. Vale qui per gli stessi motivi del minimax di von Neumann (minimax): in giochi a strategie miste l’equilibrio max-min coincide con min-max.
• L’argomento del max-min è l’aspettativa del reward immediato più il valore scontato dello stato successivo, mediati sulle policy correnti.
• Il Σ_{s'} P(s'|s, a) V(s') è la classica continuation value alla Bellman.

Shapley dimostra che T è una γ-contrazione in norma sup. Per il teorema di Banach (contrazione su spazio metrico completo) esiste un unico fixed point V*, e iterando V_{k+1} = T V_k da qualunque punto iniziale si converge a V*. È esattamente la value iteration di value-iteration-policy-iteration con un max-min al posto del max.

TEOREMA (Shapley 1953): in un gioco stocastico zero-sum a due giocatori, scontato con γ < 1, il valore esiste, è unico, e coincide con il fixed point di T. Le strategie ottime esistono e sono in generale miste stazionarie.

Il max-min interno, ad ogni stato, è un piccolo programma lineare (LP):

max v s.t. Σ_{a_1} π_1(a_1) Q(s, a_1, a_2) ≥ v ∀ a_2 Σ_{a_1} π_1(a_1) = 1, π_1(a_1) ≥ 0

dove Q(s, a_1, a_2) = R(s, a) + γ Σ_{s'} P(s'|s, a) V(s') è il “Q-value bimanuale”. L’LP ha |A_1| + 1 variabili e |A_2| + |A_1| + 1 vincoli. Risolverlo è banale per piccoli |A_i|.

Equilibri

Un Markov perfect equilibrium (Maskin-Tirole) è un profilo di policy stazionarie π* = (π_1*, …, π_N*) tale che, per ogni giocatore i e per ogni stato s, π_i*(s) è best response al profilo degli altri giocatori, calcolato sotto il valore continuation indotto da π*. È una versione subgame-perfect del Nash, vincolata a policy stazionarie funzioni del solo stato corrente.

TEOREMA (Fink 1964; Takahashi 1964): in un gioco stocastico general-sum a N giocatori, scontato con γ < 1, finite S e A_i, esiste almeno un Markov perfect equilibrium in policy stazionarie miste. La dimostrazione è un argomento di punto fisso alla Kakutani sul prodotto dei simplessi Δ(A_1)^|S| × … × Δ(A_N)^|S|, che è compatto convesso, applicato alla best-response correspondence (grafico chiuso, valori convessi non vuoti).

Il problema, come nei giochi statici, non è l’esistenza ma l’unicità e la selezione. Un gioco stocastico tipico ammette molti Markov perfect equilibria, e quale verrà appreso dipende dall’algoritmo, dall’inizializzazione, e dal regime di self-play.

Minimax-Q (Littman 1994)

Versione model-free di Shapley iteration. L’agente non conosce P né R ma osserva tuple (s, a_1, a_2, r, s') interagendo con l’ambiente. Mantiene una stima Q_1(s, a_1, a_2) per ogni tripletta. Aggiornamento:

V(s’) ← max_{π_1} min_{a_2} Σ_{a_1} π_1(a_1) Q_1(s’, a_1, a_2) [LP] Q_1(s, a_1, a_2) ← (1 - α) Q_1(s, a_1, a_2) + α (r + γ V(s’))

Si noti la sottigliezza: il min interno della Shapley iteration (che è su distribuzioni miste π_2) qui è sostituito da un min su azioni pure a_2. È equivalente per il computo di V(s') perché contro una π_1 fissata l’avversario zero-sum trova un best response puro, e perché il valore minimax sulle miste coincide per teorema con quello calcolato come max_{π_1} min_{a_2}.

TEOREMA (Littman 1994): minimax-Q converge alla value function di Shapley sotto le solite ipotesi Robbins-Monro su α (non sommabile, sommabile al quadrato) e visite infinite di tutte le triplette (s, a_1, a_2).

Una traccia operativa di Shapley iteration

Vale la pena vedere all’opera una manciata di iterazioni su un esempio piccolo. Supponiamo S = {s_0, s_1} con |A_1| = |A_2| = 2, transizioni:

• in s_0, joint action (C, C) → s_0 con prob 1; (C, D) → s_1 con prob 1; (D, C) → s_1 con prob 1; (D, D) → s_0 con prob 1.
• in s_1, qualunque joint action → s_1 con prob 1 (assorbente).

Reward del giocatore 1 in s_0: matrice di matching pennies R_0 = [[+1, -1], [-1, +1]]. In s_1: reward sempre 0.

Init V_0(s_0) = V_0(s_1) = 0. Iterazione 1:

Q_1(s_0, a_1, a_2) = R_0(a_1, a_2) + 0.9 · 0 = R_0. LP minimax su R_0 dà π_1 = (0.5, 0.5), valore 0. Quindi V_1(s_0) = 0. V_1(s_1) = 0.

Iterazione 2: identica, V_2 = V_1 = 0. La sequenza è già al fixed point. Verifica: il valore di matching pennies è zero, e la dinamica non aggiunge nulla perché tutte le transizioni preservano lo stesso valore continuation. È una verifica di sanità: l’iterazione di Shapley collassa alla soluzione del gioco statico quando la dinamica è “neutra” rispetto al valore.

Si modifichi ora il problema rendendo s_1 ricco: reward +0.5 in ogni step a favore del giocatore 1 in s_1. Ora V*(s_1) è la somma geometrica scontata 0.5 / (1 - 0.9) = 5. La dinamica diventa “interessata”: il giocatore 1 ora preferisce le joint action che mandano in s_1, cioè (C, D) e (D, C). Il giocatore 2 preferisce (C, C) e (D, D). La matrice effettiva Q_1(s_0) diventa R_0 + 0.9 · [[0, 5], [5, 0]] = [[+1, +3.5], [+3.5, +1]]. Il minimax LP su questa matrice ha valore 2.25 con strategia mista non più simmetrica. La dinamica ha cambiato il gioco. È il senso preciso in cui un gioco stocastico è “più ricco” di un gioco ripetuto.

Pseudocodice in numpy (gridworld 4x4 zero-sum)

Due agenti su una griglia 4×4, “tagger” e “runner”. Il tagger riceve +1 se occupa la stessa cella del runner; il runner riceve il negativo dello stesso reward. Azioni: nord, sud, est, ovest. Lo stato è (pos_tagger, pos_runner), quindi |S| = 16 × 16 = 256 e |A_1| = |A_2| = 4.

import numpy as np
from scipy.optimize import linprog

S, A = 256, 4
Q = np.zeros((S, A, A))      # Q-table del tagger
alpha, gamma, eps = 0.1, 0.95, 0.2

def minimax_value(Qs):
    # max_{pi_1} min_{a_2} sum_{a_1} pi_1(a_1) Qs(a_1, a_2)
    # Variabili: [v, pi_1(0), pi_1(1), pi_1(2), pi_1(3)]
    c = np.array([-1.0, 0, 0, 0, 0])              # massimizza v
    A_ub = np.hstack([np.ones((A, 1)), -Qs.T])    # v - sum pi_1 * Qs <= 0 per ogni a_2
    b_ub = np.zeros(A)
    A_eq = np.array([[0, 1, 1, 1, 1]])            # sum pi_1 = 1
    b_eq = np.array([1.0])
    bounds = [(None, None)] + [(0, 1)] * A
    res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds)
    v = -res.fun
    pi_1 = res.x[1:]
    return v, pi_1

def step(s, a1, a2):
    # transizione deterministica della griglia + reward del tagger
    # (omessa per brevità; restituisce s_next, r)
    ...

for episode in range(20_000):
    s = reset_state()
    for t in range(50):
        _, pi_1 = minimax_value(Q[s])
        a1 = np.random.choice(A, p=pi_1) if np.random.rand() > eps else np.random.randint(A)
        a2 = np.random.randint(A)        # avversario casuale per semplicità
        s_next, r = step(s, a1, a2)
        v_next, _ = minimax_value(Q[s_next])
        Q[s, a1, a2] = (1 - alpha) * Q[s, a1, a2] + alpha * (r + gamma * v_next)
        s = s_next

Otto chiamate a linprog per step (una per Q[s], una per Q[s_next]) sono accettabili per spazi piccoli; per spazi grandi si carica un solver dedicato o si batchiano gli LP.

ANALOGIA pedagogica: il loop principale è strutturalmente identico a quello di Q-learning di q-learning. La sola differenza operativa è la sostituzione di max_a Q(s', a) con minimax(Q(s', :, :)). È la differenza tra “io contro la natura” e “io contro un avversario razionale”.

Tipologie da non confondere. Vale la pena distinguere chiaramente quattro casi che si presentano sotto bandiera “stochastic game”:

• Zero-sum a due giocatori — R_1 = -R_2. Il caso classico di Shapley. Esiste valore unico, esistono strategie ottime miste, minimax-Q converge. È il caso in cui la teoria è completa.
• General-sum a N giocatori — payoff arbitrari, possibilmente anche cooperative-competitive misto. Esiste Markov perfect equilibrium ma non unico. La teoria garantisce poco in fatto di algoritmi.
• Cooperative / team game — R_1 = R_2 = … = R_N. Tecnicamente collassa a un MDP “dal punto di vista di un controllore centralizzato” che vede tutto e decide la joint action; in pratica gli agenti sono decentralizzati e devono coordinarsi senza un controllore unico, da cui la complessità reale.
• Stackelberg games — un giocatore (leader) commit a una strategia per primo, gli altri (followers) rispondono. Cattura security games, principal-agent (vedi ponte-gioco-principal-agent), molti scenari economici. Tecnicamente non è un Markov perfect equilibrium ma un Stackelberg equilibrium, e gli algoritmi sono diversi.

Friend-or-Foe Q e WoLF (compromessi pratici)

Friend-or-Foe Q-learning (Littman 2001) è un compromesso onesto. L’agente sa, per ogni avversario nel gioco, se è “friend” — il cui Q va massimizzato come fosse cooperativo — o “foe” — il cui Q va minimizzato come fosse zero-sum. La distinzione è data esternamente, non scoperta. Il backup combina max e min in funzione delle etichette. Converge sotto condizioni più ragionevoli di Nash-Q (che richiede l’unicità del Nash globale), e in pratica funziona quando il gioco è “etichettabile” cleanly. Per Diplomacy, ad esempio, le etichette friend/foe cambiano nel tempo, il che spinge fuori dall’ipotesi di Friend-or-Foe Q.

WoLF — Win or Learn Fast (Bowling-Veloso 2002) è un policy gradient con learning rate variabile. Idea: se l’agente sta vincendo (rispetto a una baseline equilibrium), aggiorna lentamente; se sta perdendo, aggiorna velocemente. L’argomento di stabilità è elegante. Gli agenti “win-stable” non perturbano l’equilibrio (l’altra parte non ha incentivo a deviare); gli agenti “losing-fast” inseguono la best response, escono dal disequilibrio. Empiricamente robusto in self-play di giochi semplici, base di vari refinement successivi.

ANALOGIA con il livello di apprendimento umano: WoLF formalizza l’idea di “se va bene non cambiare la formula, se va male cerca veloce”. È utile come intuizione, ma è davvero un teorema di stabilità sui flussi nei giochi, non una metafora vaga.

Nash-Q-learning (cenno con cautela)

Per giochi general-sum, Hu e Wellman propongono di mantenere Q_i(s, a_1, …, a_N) per ogni giocatore, e di aggiornarli con

Q_i(s, a) ← (1 - α) Q_i(s, a) + α (r_i + γ NashValue_i(s’))

dove NashValue_i(s') è il payoff del giocatore i in un Nash equilibrium del gioco statico con matrice di payoff (Q_1(s', :), …, Q_N(s', :)). Calcolare un Nash a ogni step è costoso (PPAD-completo nel caso peggiore, vedi equilibrio-nash). E la convergenza è dimostrata solo se ogni stage game ha un Nash unico globale, o se tutti i Nash sono “equivalenti e coordinabili”: condizione che nei giochi reali quasi mai è verificata. Importante storicamente, ma raramente usato in pratica.

CTDE e MADDPG: il pattern moderno

Il pattern dominante in MARL pratico è Centralized Training, Decentralized Execution (CTDE). Durante il training, un componente centrale (tipicamente il critic) ha accesso alla joint action e alla joint observation di tutti gli agenti. Durante l’execution, ogni agente decide solo dalla propria osservazione locale. Il vantaggio è duplice. Il critic centralizzato vede un ambiente “stazionario” — perché vede direttamente la joint action, non deve marginalizzare sulle policy correnti degli avversari. L’actor decentralizzato è deployabile in scenari realistici, dove la joint observation è costosa o impossibile da ottenere a runtime.

MADDPG (Lowe et al., NeurIPS 2017) è la concretizzazione actor-critic di CTDE. Ogni agente ha un actor decentralizzato μ_i(o_i; θ_i) e un critic centralizzato Q_i(s, a_1, …, a_N; φ_i). L’actor si aggiorna con un policy gradient che usa il critic. Il critic si aggiorna con un Bellman residual standard. Il pattern è generalizzato a innumerevoli varianti: COMA per il counterfactual baseline cooperativo (Foerster et al. 2018), MAAC con attention sul critic (Iqbal-Sha 2019), QMIX per cooperative con value decomposition monotonica (Rashid et al. 2018).

L’osservazione importante è che CTDE è una scelta architetturale, non un teorema. Non garantisce convergenza. Funziona perché riduce la non-stationarity dal punto di vista del critic, ed empiricamente questo basta a stabilizzare il training in molti casi pratici. AlphaStar e OpenAI Five sono varianti di CTDE su scala industriale, con popolazioni di agenti che aggiungono diversità al training distribution.

flowchart LR
    A[Environment / simulator] -->|joint observation| B[Agente 1: actor]
    A -->|joint observation| C[Agente N: actor]
    B -->|azione a1| A
    C -->|azione aN| A
    A -->|traiettorie| D[Replay buffer]
    D --> E[Critic centralizzato<br/>vede joint action]
    E -->|advantage| B
    E -->|advantage| C
    F[Sampler self-play / league] -->|policy avversarie| A

Figura 5 — loop di training MARL stile CTDE con actor decentralizzati, critic centralizzato che vede la joint action e league sampler per le policy avversarie

LOLA, opponent shaping e oltre

Una linea di ricerca più recente affronta direttamente il problema fondante di MARL: come fare in modo che l’apprendimento di un agente influenzi l’apprendimento degli altri in modo voluto. LOLA (Foerster et al. 2018) modella esplicitamente la dinamica di apprendimento dell’avversario. Il gradiente del giocatore i non è più

∇_θ_i E[ R_i ]

ma include un termine che predice come θ_{-i} cambierà in risposta a θ_i:

∇θ_i E[ R_i ( θ_i, θ{-i} + α ∇θ{-i} E[ R_{-i} ] ) ]

In dilemma del prigioniero iterato, due agenti LOLA cooperano dove due agenti naive policy gradient cadono in defezione mutua. È una piccola rivoluzione concettuale: la policy non massimizza solo il proprio reward, ma anche la propria influenza sull’apprendimento dell’altro. Lavori successivi (M-FOS, opponent shaping con meta-gradient) generalizzano l’idea ma il principio resta lo stesso: in MARL non si è dentro un’ottimizzazione, si è dentro una dinamica.

Esempi

Esempio 1 — Matching pennies stocastico (numerico)

Due stati S = {s_0, s_1}. Azioni A_1 = A_2 = {C, D}. Reward del giocatore 1 (zero-sum):

In s_0:

	C	D
C	+1	-1
D	-1	+1

In s_1: reward sempre 0, stato assorbente.

Transizioni: in s_0, qualunque sia la joint action, prob 0.5 si resta in s_0, prob 0.5 si va in s_1. In s_1 si resta sempre. γ = 0.9.

Calcolo a mano: V*(s_1) = 0 (assorbente con reward zero). Per s_0 la matrice dei Q(s_0, a_1, a_2) = R + γ · 0.5 · V*(s_0) + γ · 0.5 · 0 è proporzionale alla matrice di reward, perché la continuation aggiunge la stessa costante a tutte le entry (la transizione non dipende dalle azioni). Si tratta quindi del classico matching pennies, equilibrio strettamente misto π_1 = π_2 = (0.5, 0.5). Valore V*(s_0) = 0 + 0.9 · 0.5 · V*(s_0), da cui V*(s_0) = 0.

Banale, ma illustra perfettamente la meccanica generale: ad ogni stato si risolve un gioco statico misto in cui i payoff sono “reward immediato più continuation value scontato”. L’iterazione di Shapley itera questa risoluzione finché V converge.

Esempio 2 — Gridworld 4x4 con minimax-Q (codice)

Il pseudocodice sopra è un esempio completo. Allenando con avversario casuale per 20.000 episodi e poi testando contro un avversario greedy che minimizza istantaneamente, si osserva il pattern tipico: minimax-Q produce una policy mista che ruota sulle azioni con probabilità dipendenti dalla configurazione. Q-learning ingenuo, che marginalizza l’azione avversaria assumendo distribuzione uniforme, viene sfruttato sistematicamente: l’avversario impara una controstrategia pura e Q-learning non sa ribilanciarsi perché non rappresenta nemmeno l’azione avversaria nella sua tabella. È esattamente il punto di Littman 1994, gridworld “soccer”.

Esempio 3 — AlphaStar e OpenAI Five (scenari reali)

AlphaStar (Vinyals et al., Nature 2019) gioca StarCraft II al livello Grandmaster. Il paper inquadra esplicitamente il problema come gioco stocastico parzialmente osservabile (POSG): due o più giocatori, stato gigantesco (mappa, unità, risorse, fog of war), azioni continue strutturate, durata di partita lunga. Architettura agente: LSTM con auto-attenzione, pointer e scatter. Training: league self-play prioritizzato con tre tipi di agente — main agents (massimizzano la win rate), main exploiters (esposti solo ai main, cercano i loro buchi), league exploiters (esposti a tutti, mantengono diversità). Il sampler dell’avversario non è uniforme: privilegia avversari da cui l’agente sta perdendo, una forma di curriculum auto-generato. L’algoritmo on-policy è IMPALA con correzione off-policy V-trace. Filiazione esplicita: nel paper Vinyals scrive che “we frame the multi-agent reinforcement learning problem as a stochastic game”. Non analogia, filiazione documentata.

OpenAI Five (Berner et al., 2019) gioca Dota 2 a livello professionistico in modalità 5v5. Il problema è un gioco stocastico mixed cooperative-competitive: cooperazione interna alla squadra, competizione tra squadre. Scelta architetturale: un singolo network condiviso fra i cinque eroi, parametricamente identico ma con osservazioni diverse. La cooperazione emerge senza comunicazione esplicita, semplicemente perché tutti cinque massimizzano la stessa funzione di reward (vittoria). Algoritmo: PPO scalato su 256 GPU e 128.000 CPU, 180 anni di gioco simulato al giorno per agente. Battuta OG, campioni del mondo 2018, in show-match. Anche qui filiazione esplicita: il framework è stochastic game, l’algoritmo è MARL.

Esempio 3-bis — Self-play, league e popolazioni

Vale la pena soffermarsi un attimo sul perché il self-play, oggi onnipresente, sia tutt’altro che una scelta scontata. La forma più ingenua di self-play è “prendi due copie identiche dell’agente e fagliele giocare contro”. Funziona magnificamente per giochi zero-sum simmetrici e simmetria del payoff: AlphaZero usa esattamente questa idea per scacchi e Go. Ma in giochi stocastici non simmetrici, o general-sum, il self-play ingenuo cade in patologie note:

• Cycling: l’agente impara una strategia, l’avversario (sé stesso) impara un controattacco, l’agente impara un contro-controattacco che reintroduce la prima strategia originale. Loop di Rock-Paper-Scissors strategici.
• Overfitting all’avversario corrente: la policy diventa fragilissima rispetto a strategie storiche dimenticate.
• Convergenza a un equilibrio cooperativo subottimale: in giochi general-sum, due copie dello stesso agente possono “implicitamente collaborare” producendo un risultato non robusto a un avversario diverso.

Le mitigazioni sono tutte forme di popolazione: invece di una singola policy che gioca contro sé stessa, si mantiene un insieme di policy storiche (“fictitious play prioritizzato”), o un’intera ecologia (“league” di AlphaStar), oppure si campiona da una distribuzione di Nash sulla popolazione (PSRO, Lanctot 2017). È un’idea che ricorre: la robustezza in giochi stocastici nasce dalla diversità del training distribution, non dall’ottimizzazione contro un singolo avversario.

Esempio 4 — Cicero (general-sum + linguaggio)

Cicero (FAIR/Meta, Science 2022) è un agente per il gioco da tavolo Diplomacy. Sette giocatori, general-sum, alleanze e tradimenti, con la peculiarità che la metà del gioco si svolge in negoziazione in linguaggio naturale. Cicero combina due moduli: un policy network strategico, addestrato in self-play in una versione “no-press” del gioco (senza chat), e un LLM fine-tuned che genera messaggi consistenti con la policy strategica. Il gioco si formalizza come stochastic game general-sum dove l’azione di un giocatore include sia mosse di unità sia messaggi a tutti gli altri sette. È il primo agente human-level in un gioco general-sum con comunicazione linguistica. La connessione con i framework multi-agent LLM moderni è diretta: i messaggi sono parte dell’azione, lo stato include la storia delle conversazioni.

Applicazioni pratiche

L’utilità del framework si vede meglio enumerando concretamente dove ricorre. Ne basta una manciata.

Multi-agent reinforcement learning industriale. AlphaStar, OpenAI Five, Cicero sono i tre esempi paradigmatici, ma il pattern si replica in campi più tranquilli: traffic light coordination su scala urbana (Shanghai, Hangzhou hanno deployment reali di MARL), trading algoritmico multi-strategia, energy grid balancing con prosumer multipli, robot warehouse coordination (Amazon Robotics ha sostituito l’orchestrazione gerarchica con MARL su parti del fleet).

Multi-agent LLM frameworks. AutoGen (Microsoft), CrewAI, LangGraph multi-agent, AutoGPT — ANALOGIA: questi sistemi sono giochi stocastici informali. Lo stato è il thread di messaggi più il filesystem più la memoria condivisa. Le azioni sono chiamate a tool, scrittura di messaggi, delega ad altri agenti. Il reward è implicito nel successo del task. Le policy sono prompt più modello. La non-stationarity esiste ed è osservabile: cambiare un agente a metà pipeline cambia la distribuzione di input per quelli a valle, e le loro performance ne soffrono. Empiricamente la maggior parte delle implementazioni ignora la formalizzazione, ma capire che si è dentro un gioco stocastico aiuta a diagnosticare i bug “strani” (loop, deadlock, sabotaggio cooperativo).

GAN long-horizon e adversarial training. FILIAZIONE: la formulazione minimax di Goodfellow 2014 colloca le GAN come gioco stocastico zero-sum a due giocatori (G vs D) con stato implicito (parametri) e dinamica (gradiente). Le instabilità di training (mode collapse, vanishing gradient) sono manifestazioni della non-convergenza di gradient descent in giochi a somma non zero (anche zero-sum non-convex), problema noto già negli anni Cinquanta. Si lega al rigore di gan (in preparazione) e al ponte cooperativo di dilemma-prigioniero.

Cooperative AI e sequential social dilemmas. Il programma di Cooperative AI (Dafoe et al. 2020) ha come oggetto agenti che cooperano tra loro e con umani. Sequential social dilemmas (Leibo et al. 2017) estendono dilemma del prigioniero a stochastic games spazialmente estesi: cooperazione su risorse comuni, punizione, segregazione. Si collega direttamente a dilemma-prigioniero.

Mean-field MARL. Per N molto grande (mercati, traffico macroscopico, swarm) ogni agente vede solo la distribuzione media del comportamento aggregato. Riduce un gioco N-player a un gioco a due (rappresentativo + media). Assume omogeneità degli agenti, assunzione spesso violata.

Security games e adversarial planning. Pattugliamento aeroportuale, anti-bracconaggio, cybersecurity. Tipicamente formalizzati come stochastic games zero-sum o di Stackelberg; equilibri risolti con LP o approssimazioni.

Competing LLM agents in marketplaces. Scenari emergenti: LLM agents che negoziano per conto di utenti, fanno offerte in aste multi-round, contrattano contratti. Il framework è stochastic game. La ricerca pratica è agli inizi.

Emergent communication. Foerster 2016 e Lazaridou 2017 mostrano agenti che imparano a comunicare in canali discreti per coordinarsi. È un caso speciale di stochastic game cooperative con azioni di “speaking”. I protocolli emergenti hanno proprietà strane: a volte sono compositionalmente puliti, a volte sono codici idiosincratici comprensibili solo dalla coppia che li ha imparati. Il collegamento concettuale con il linguaggio LLM cooperativo (agenti che si scambiano informazioni in linguaggio naturale) è diretto, anche se la transizione “discrete protocol → LLM-as-channel” non è ancora ben formalizzata.

Auto-curricula. Una conseguenza interessante dei giochi stocastici cooperative-competitive: la difficoltà del task cresce automaticamente con la skill degli agenti, perché gli avversari sono altri agenti che migliorano. Questo elimina parzialmente il problema del curriculum design: l’ambiente “diventa più difficile” man mano che gli agenti diventano più bravi. È il motivo per cui AlphaStar e OpenAI Five funzionano nonostante i loro spazi di stato gigantesci: il self-play crea un curriculum implicito.

Dove si rompe

Il framework è elegante. La pratica è dura. Vale la pena distinguere ciò che si sa risolvere da ciò che si sa solo aggirare.

L’esistenza non basta. Shapley garantisce che il valore esiste e Fink che il Markov perfect equilibrium esiste. Calcolare entrambi è in generale intractable per spazi grandi. La value iteration è polinomiale in |S| · |A_1| · … · |A_N|, ma il prodotto delle azioni esplode esponenzialmente nel numero di giocatori. Per N = 5 con |A_i| = 100 (Dota 2) la joint action ha 10^10 voci per stato. Nessuno calcola Q-table. Si approssima con reti neurali e si paga in convergenza.

Non-stationarity dal punto di vista del singolo. Se gli avversari imparano, la distribuzione P(s', r | s, a_i) marginalizzata sulle policy correnti degli altri cambia nel tempo. Q-learning ingenuo, che assume ambiente stazionario, può ciclare o divergere. Le mitigazioni standard sono tre: (a) self-play sincronizzato (tutti aggiornano insieme, ambiente “globalmente” stazionario), (b) centralized training decentralized execution (CTDE: il critic vede la joint action, riducendo non-stationarity dal punto di vista del critic), (c) opponent modeling esplicito (LOLA, M-FOS, eccetera).

Equilibri multipli e selezione. Anche quando un Nash o un Markov perfect equilibrium esiste, ne esistono in genere molti. Quale viene appreso dipende dall’algoritmo, dall’inizializzazione, dal sampler di self-play, dal curriculum. Non c’è un modo universale per garantire la convergenza all’equilibrio “buono” (per qualunque definizione di buono). Nei giochi cooperativi spesso si ottiene un equilibrio Pareto-dominato; nei giochi general-sum spesso si ottiene defezione dove sarebbe possibile cooperare (vedi dilemma-prigioniero).

Convergenza di Nash-Q solo sotto condizioni rare. Hu-Wellman dimostrano la convergenza ma le ipotesi (Nash unico globale per ogni stage game, o tutti Nash equivalenti e coordinabili) sono quasi mai soddisfatte in giochi non triviali. Il risultato pratico: Nash-Q raramente funziona out-of-the-box.

Credit assignment cooperativo. Quando il reward è di squadra, chi del team ha contribuito? Il problema esplode in MARL perché il reward è funzione della joint action, non delle singole. Tecniche standard: counterfactual baseline (COMA, Foerster 2018), value decomposition (VDN, QMIX). Nessuna è una bullet definitiva.

Partial observability. Nei casi reali (StarCraft, Dota, Diplomacy) gli agenti non vedono lo stato globale. Si passa al POSG — Partially Observable Stochastic Game — che è NEXP-completo nel caso peggiore (Bernstein et al. 2002). Tutti gli agenti devono inferire lo stato dalla sequenza di osservazioni, e devono modellare cosa stanno inferendo gli altri. Belief over belief over belief. In pratica si tratta con belief states approssimati e LSTM.

Mean-field assume omogeneità. Quando N è grande la riduzione mean-field richiede agenti scambiabili. In molte applicazioni reali (traffico misto auto-pedoni-bici, mercati con tipologie diverse di trader) gli agenti sono eterogenei e mean-field perde affidabilità.

LLM-as-agent: stato non veramente Markov. Nei framework multi-agent LLM lo “stato” è il prompt più la conversazione. La proprietà markoviana (transizione dipende solo dallo stato corrente, non dalla storia) si tiene solo se tutta la storia rilevante è nel prompt. Quando si introducono memorie esterne, riassunti compressi, retrieval condizionato, lo stato apparente non è più sufficiente a predire la transizione, e tutti i teoremi di esistenza-convergenza sui giochi stocastici saltano. ASSUMPTION: si tratta come stochastic game informale e si misura empiricamente; non c’è alternativa pulita allo stato attuale.

Reward design per cooperative. Nel cooperative MARL il reward globale è spesso non Markov rewards (non scrivibile come R(s, a, s')): dipende da invarianti aggregati lungo l’orizzonte, dalla qualità del processo, dall’uso di risorse condivise nel tempo. Il Markov reward theorem (Abel et al. 2021) applica al singolo agente; nel multi-agent la tassonomia dei reward diventa più scivolosa.

Equilibrium selection cooperazione vs defezione. Si ricollega esplicitamente a dilemma-prigioniero: nello stochastic game iterato il dilemma riemerge a ogni stato, e il rischio di cadere in equilibri di defezione è strutturale. LOLA (Foerster 2018) e successori (M-FOS, opponent shaping) sono tentativi parziali; non c’è una soluzione universale.

Non-convergence di gradient descent in giochi. Anche zero-sum, anche concavo-convesso, gradient descent ingenuo può ciclare attorno all’equilibrio invece di convergere. Le tecniche pratiche (extragradient, optimistic gradient, exponentially-weighted updates) aiutano ma non sempre. È il lato matematico delle instabilità GAN.

Joint policy con vincoli di equilibrio: nessun ottimizzatore standard. Anche in casi piccoli, il problema “trova un Markov perfect equilibrium” non è un problema di ottimizzazione standard. Non si massimizza un’unica funzione; si cerca un punto fisso di un sistema di best-response. Gradient descent sulla somma dei reward porta a soluzioni totalmente diverse dall’equilibrio. Nessuna libreria di ottimizzazione classica risolve il problema fuori dallo zero-sum a due giocatori.

Comunicazione e linguaggio fanno saltare lo spazio di azione. Cicero illustra il fenomeno: l’azione include un messaggio in linguaggio naturale, lo spazio di azione effettivo è continuo e gigantesco. La formalizzazione come stochastic game tiene, ma gli algoritmi standard non si applicano: serve un decoupling fra strategia e linguaggio (Cicero usa due moduli separati). Generalizzare a più agenti LLM cooperanti è ricerca aperta.

Approximation con reti neurali rompe le garanzie. I teoremi di esistenza e convergenza assumono Q-table tabulari. Sostituendo Q(s, a_1, a_2) con una rete neurale Q_θ(s, a_1, a_2) si perdono tutte le garanzie pulite. La rete può estrapolare male su coppie joint-action mai viste, e l’errore si propaga attraverso il bootstrap di Bellman amplificandosi. Tutte le tecniche stabilizzanti note nel single-agent (target networks, replay buffer, double-Q) si trasportano a MARL ma con efficacia ridotta a causa della non-stationarity.

Sample complexity peggiore del single-agent. Anche zero-sum tabulare richiede più sample del corrispondente MDP perché l’agente deve esplorare congiuntamente lo spazio joint action. Bound noti (Bai-Jin 2020, Liu 2021) sono polinomiali ma con costanti grosse; in pratica il numero di episodi è ordini di grandezza maggiore.

Hierarchical e recursive credit assignment. Quando una squadra cooperativa ha sotto-team, il problema del credit assignment si annida: il reward globale va attribuito al sotto-team, e dentro il sotto-team al singolo agente. Algoritmi di value decomposition (VDN, QMIX) gestiscono il caso piatto; la versione gerarchica è ricerca aperta.

Adversarial robustness vs equilibrium robustness. Nei giochi stocastici reali si incontrano due tipi diversi di robustezza: (a) robustezza all’avversario peggiore possibile dentro lo spazio di azioni del gioco — è il caso classico minimax, (b) robustezza a perturbazioni delle policy degli avversari fuori dal modello — fragile rispetto a strategie che non vivono nel modello formale (per esempio, exploit sociali in negoziazione). AlphaStar aveva entrambi i problemi: i league exploiters cercavano la prima, i bug umani exploitati nella fase pubblica del torneo cadevano nella seconda.

In sintesi, il gioco stocastico è una bella mappa per capire dove si è. Non è una ricetta per risolvere il problema. Tutto il MARL moderno è un compromesso tra rigore (che paga garanzie ma non scala) e ingegneria (che scala ma rinuncia a garanzie). AlphaStar e OpenAI Five sono prevalentemente sul lato ingegneria. Cooperative AI è ricerca attiva su come costruire garanzie più realistiche.

Collegamenti

• probabilita-base — il valore atteso e le distribuzioni miste sono i mattoni del framework.
• bias-varianza — pertinente ai limiti di approssimazione delle Q-function multi-azione in spazi grandi.
• giochi-definizione — il caso |S|=1 del gioco stocastico.
• somma-zero-non-zero — la dicotomia che separa Shapley iteration (zero-sum) da Nash-Q (general-sum).
• equilibrio-nash — il concetto di equilibrio che, lifted a policy stazionarie, dà il Markov perfect equilibrium.
• minimax — il calcolo max-min su distribuzioni miste è il cuore di Shapley iteration.
• giochi-cooperativi — i team game e cooperative MARL si appoggiano qui per credit assignment.
• dilemma-prigioniero — il dilemma riemerge a ogni stato nel gioco stocastico iterato; LOLA e affini lo affrontano.
• markov-decision-process — il caso N=1 del gioco stocastico.
• equazione-bellman — Shapley iteration è Bellman con max-min al posto di max.
• value-iteration-policy-iteration — Shapley iteration come variante minimax della value iteration.
• q-learning — minimax-Q sostituisce max_a Q con minimax(Q) lasciando il resto invariato.
• policy-gradient — base per gradient descent in MARL e per LOLA.
• actor-critic — schema CTDE con critic centralizzato è actor-critic adattato.
• ppo-trpo — PPO è l’algoritmo di OpenAI Five; vincoli di trust region aiutano a domare la non-stationarity.
• ponte-gioco-principal-agent — alignment come stochastic game asimmetrico in informazione.

Curiosità storiche e numeri

Una piccola nota di gusto. Il termine “minimax-Q” è di Littman e illustra in due token la fusione concettuale: minimax (von Neumann 1928, teorema fondante della teoria dei giochi) più Q (Watkins 1989, fondamenti di Q-learning) uguale stochastic game RL. Il nome è breve e contiene mezzo secolo di storia.

Vale la pena chiudere con qualche numero che dà il senso della scala. Shapley pubblica Stochastic Games a trent’anni; il paper PNAS è di sei pagine, contiene la definizione, il teorema di esistenza e l’algoritmo iterativo. Nessuno dei tre elementi è stato superato in oltre settant’anni: la definizione è canonica, il teorema è il bedrock, l’iterazione di Shapley resta usabile per spazi piccoli.

AlphaStar, in fase di league training, ha consumato circa duecento anni-partita di gioco StarCraft per ciascun agente principale, in un cluster con migliaia di TPU. La pipeline complessiva ha simulato decine di migliaia di anni di gioco. OpenAI Five ha simulato circa centottanta anni di gioco al giorno, per dieci mesi consecutivi. Cicero ha richiesto un dataset di 125.000 partite umane di Diplomacy commentate, più una fase di self-play “no-press” parallela.

Il rapporto fra eleganza teorica e brute force ingegneristico è quasi imbarazzante. Ma la teoria fa una cosa che la brute force non sa fare: spiega perché il brute force funziona quando funziona, e perché smette di funzionare quando smette. Per chi costruisce agenti, è il framework concettuale in cui mettere ordine alla pratica.

Una nota sull’agentic future

La tesi corrente del libro è che gli agenti del prossimo decennio saranno sempre più giochi stocastici, con sempre meno ambienti single-agent puri. Il motivo è semplice: gli agenti utili interagiscono con il mondo, e il mondo contiene altri agenti — umani, AI, sistemi misti. Un agente che ottimizza ignorando gli altri è già obsoleto al momento del deploy.

Tre conseguenze pratiche, da tenere in mente prima di passare al MARL applicato e al ponte principal-agent.

Primo, la valutazione di un agente in scenari multi-agente è più scivolosa di quanto sembri. Un agente può performare benissimo contro un avversario debole e crollare contro uno forte. Senza una popolazione di valutatori (popolazione che a sua volta cambia nel tempo) i numeri di benchmark sono fragili. AlphaStar, OpenAI Five e Cicero hanno tutti benchmark contro umani professionisti perché era l’unico modo di misurare onestamente.

Secondo, la safety in scenari multi-agente non si riduce alla safety single-agent. Un agente “allineato” rispetto ai propri reward può manipolare altri agenti per estrarne valore (rilevanza diretta per ponte-gioco-principal-agent). Le proprietà di sicurezza sono ora proprietà del profilo congiunto, non del singolo. Cooperative AI è il programma di ricerca esplicito su come progettare profili sicuri.

Terzo, l’economia di sistemi multi-agente AI è diversa da quella di sistemi single-agent. Pricing dinamico, contrattazione, allocazione di risorse fra agenti AI con utility diverse — tutti scenari in cui i framework di stochastic games e mechanism design (meccanismi-aste) si fondono.

Tenere a mente, in tutto il resto del libro: ogni volta che si parla di “agente che fa cose”, ci si chieda chi altro c’è nel sistema. Quasi sempre la risposta è “altri agenti”. E allora si è dentro un gioco stocastico, che lo si sappia o no.

Per andare oltre

• Shapley, L. S. (1953). Stochastic Games. PNAS 39(10), 1095-1100. Sei pagine, fondazione del campo.
• Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. ICML. Il paper che porta i giochi stocastici nel mondo del RL.
• Filar, J., & Vrieze, K. (1996). Competitive Markov Decision Processes. Springer. Trattato matematico di riferimento.
• Shoham, Y., & Leyton-Brown, K. (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, capitoli 6-7.
• Vinyals, O. et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350-354. AlphaStar nel dettaglio.
• Berner, C. et al. (2019). Dota 2 with Large Scale Deep Reinforcement Learning. arXiv:1912.06680. OpenAI Five.
• FAIR (Meta) Diplomacy team (2022). Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science 378(6624), 1067-1074. Cicero, general-sum con linguaggio naturale come canale.
• Hu, J., & Wellman, M. P. (2003). Nash Q-learning for general-sum stochastic games. JMLR 4, 1039-1069. Estensione e suoi limiti documentati.
• Foerster, J. et al. (2018). Learning with Opponent-Learning Awareness. AAMAS. LOLA e l’opponent shaping.
• Lowe, R. et al. (2017). Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. NeurIPS. MADDPG e CTDE.
• Dafoe, A. et al. (2020). Open Problems in Cooperative AI. arXiv:2012.08630. La mappa del campo cooperative AI.
• Leibo, J. Z. et al. (2017). Multi-agent Reinforcement Learning in Sequential Social Dilemmas. AAMAS. Ponte concettuale tra dilemma del prigioniero e MARL.
• Bowling, M., & Veloso, M. (2002). Multiagent learning using a variable learning rate. Artificial Intelligence 136(2), 215-250. WoLF e l’idea win-or-learn-fast.
• Lanctot, M. et al. (2017). A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (PSRO). NeurIPS. Policy-space response oracle, base teorica delle league moderne.