Minimax-Optimal Policy Regret in Partially Observable Markov Games

Sintesi Tecnica: Regret della Politica Minimax-Ottimale in Giochi di Markov Parzialmente Osservabili

Formulazione del Problema
Questo articolo affronta il processo decisionale sequenziale in ambienti parzialmente osservabili contro avversari strategici e adattivi, modellati come Giochi di Markov Parzialmente Osservabili (POMG). La sfida centrale risiede nell'apprendere la dinamica latente del mondo da osservazioni parziali, affrontando al contempo un avversario il cui comportamento si adatta alla strategia dell'apprendista. Le nozioni standard di regret esterno sono inadeguate in questo contesto perché la risposta dell'ambiente dipende dalle azioni passate dell'apprendista, creando dipendenze controfattuali. Di conseguenza, l'articolo adotta il regret della politica (policy regret) come metrica di prestazione, che confronta la ricompensa cumulativa dell'apprendista con la migliore politica fissa $\pi^*$, assumendo che l'avversario sarebbe eventualmente confluito in una risposta stazionaria $R_\infty(\pi^*)$ qualora l'apprendista si fosse impegnato in $\pi^*$ sin dall'inizio.

Il setting coinvolge due giocatori: un apprendista e un avversario, entrambi operanti sotto osservabilità parziale. L'apprendista osserva i segnali $o^A$ e l'avversario osserva $o^B$, mentre le transizioni dello stato latente si basano sulle azioni di entrambi i giocatori. Si assume che l'avversario sia limitato nella memoria di ordine $m$ (m-memory bounded), il che significa che la sua risposta in ogni episodio dipende solo dalle politiche dell'apprendista negli $m$ episodi più recenti.

Metodologia e Framework Algoritmico
Gli autori propongono un algoritmo di Stima della Massima Verosimiglianza (MLE) ottimistica basata su epoche (Algoritmo 1) per minimizzare il regret della politica. La metodologia si basa su diversi componenti strutturali chiave:

1. Decomposizione Causale: Un contributo teorico centrale è la decomposizione dell'operatore osservabile $J_{\xi,\pi}^h$ in due componenti distinte:

   • Un canale del mondo $W_h^\theta$, che dipende esclusivamente dalle dinamiche del mondo (kernel di transizione ed emissione) ed è indipendente dal modello di risposta dell'avversario.
   • Un operatore di aggregazione dell'avversario $G_{\Phi,\pi}^h$, che dipende dalla funzione di risposta dell'avversario e dalla politica dell'apprendista, ma è indipendente dal parametro del mondo $\theta$.
     Questa fattorizzazione permette all'algoritmo di separare la stima delle dinamiche del mondo dal controllo delle risposte dell'avversario.

2. Assunzioni Strutturali:

   • Avversario Posterior-Lipschitz: La risposta dell'avversario varia in modo fluido rispetto alla politica dell'apprendista. Fondamentalmente, questa fluidità è definita rispetto a una misura di riferimento fissa $\mu_{ref}$ (indipendente dalla strategia effettiva dell'avversario) per evitare dipendenze circolari nella definizione.
   • Debole Rivelazione Multi-step: Le osservazioni sono sufficientemente informative riguardo agli stati latenti su una finestra di $\kappa$ passi, garantendo che le discrepanze nelle dinamiche del mondo siano rilevabili.
   • Dimensione di Eluder: La complessità della classe di modelli congiunti mondo-avversario è misurata dalla dimensione di Eluder aggregata uniforme ($d_E$).

3. Esecuzione Basata su Epoche: L'algoritmo divide il tempo in epoche a crescita geometrica ($T_e = 2^e$). All'interno di ogni epoca:

   • Viene selezionata una singola politica $\pi_e$ in modo ottimistico da un insieme di confidenza costruito cumulativamente da tutti i dati passati.
   • Una fase di warm-up ($m-1$ episodi) permette all'avversario con memoria $m$ di stabilizzarsi alla sua risposta stazionaria per la politica corrente.
   • La politica viene eseguita per $T_e$ episodi di raccolta dati.
     Questa struttura assicura che l'apprendista dispieghi solo $O(\log T)$ politiche distinte su $T$ episodi, il che è critico per controllare il costo di confronto delle risposte dell'avversario tra diverse politiche.

Risultati Chiave
L'articolo stabilisce un limite superiore di minimax-ottimalità sul regret della politica e un limite inferiore corrispondente.

• Limite Superiore: Sotto le assunzioni dichiarate, l'algoritmo raggiunge un regret della politica di:
  $$PR(T) \leq C \left( H \sqrt{\bar{\beta}_T \cdot d_E \cdot T} + mH \log T \right)$$
  dove $\bar{\beta}_T = H\beta_T + H^2 \log T$. Il termine $H^2 \log T$ rappresenta il "costo di trasporto" del confronto tra le risposte dell'avversario attraverso le $O(\log T)$ politiche distinte dispiegate. La dipendenza $\sqrt{T}$ è ottenuta tramite la struttura delle epoche geometriche; l'impiego di $O(\sqrt{T})$ politiche (come nel caso del flat batching) risulterebbe in un tasso di regret $T^{3/4}$ dovuto all'accumulo dei costi di trasporto.

• Limite Inferiore: Gli autori dimostrano un limite inferiore di $\Omega(\sqrt{d_E T})$ per qualsiasi algoritmo, anche in POMG pienamente rivelatori con avversari privi di memoria. Ciò conferma che la dipendenza $\sqrt{T}$ e $d_E$ nel limite superiore è ottimale salvo fattori dipendenti dal problema o logaritmici.

• Estensioni: Il framework è esteso per gestire:

  • Orizzonti Sconosciuti: L'algoritmo si adatta a $T$ sconosciuto senza modifiche.
  • Avversari con Memoria Decadente: I risultati valgono per avversari con memoria che decade geometricamente, con il costo di warm-up che scala come $O(\frac{H \log^2 T}{1-\gamma})$.
  • Settings Tabulari: Sono derivati limiti espliciti in termini di dimensioni degli spazi di stato, azione e osservazione.

Significatività e Rivendicazioni
L'articolo sostiene di fornire un trattamento teorico completo della minimizzazione del regret della politica nei POMG contro avversari adattivi. La sua importanza primaria risiede nel dimostrare che un apprendimento efficiente (con regret $\sqrt{T}$) è possibile in questo scenario complesso, a condizione che la risposta dell'avversario sia fluida (Posterior-Lipschitz) e le osservazioni siano debolmente rivelatrici.

Gli autori evidenziano due innovazioni tecniche specifiche che permettono questo risultato:

1. Formulazione Non Circolare: Definendo la condizione Posterior-Lipschitz rispetto a una misura di riferimento fissa, evitano i problemi di circolarità presenti nelle formulazioni precedenti in cui la metrica di fluidità dipendeva dall'essere l'avversario vincolato.
2. Costo di Trasporto Logaritmico: Limitando l'apprendista a $O(\log T)$ politiche distinte tramite la struttura basata su epoche, assicurano che il costo del trasporto degli errori di risposta dell'avversario rimanga logaritmico, preservando il tasso ottimale $\sqrt{T}$. Ciò contrasta con gli approcci di flat-batching che, secondo gli autori, portano a tassi subottimali $T^{3/4}$ a causa della crescita polinomiale dei costi di trasporto.

Il lavoro è presentato come un passo fondamentale per la progettazione di algoritmi di apprendimento con garanzie di prestazione affidabili in ambienti multi-agente dove gli agenti sono sia parzialmente osservabili che strategicamente adattivi. Gli autori notano che, sebbene le garanzie statistiche siano stabilite, la trattabilità computazionale del passo di pianificazione ottimistica rimane una direzione aperta per il lavoro futuro, in particolare per classi di modelli generali.