Optimal strategies in Markov decision processes with finitely additive evaluations

Questo studio dimostra che, nei processi decisionali di Markov a orizzonte infinito valutati tramite una carica diffusa, non è garantita l'esistenza di una strategia ottimale (né pura né randomizzata) senza assumere il principio del valore temporale del denaro, fornendo un controesempio che risponde negativamente alla questione sollevata da Neyman.

L'essenziale

Ecco una spiegazione semplice e creativa di questo articolo accademico, pensata per chiunque, anche senza una laurea in matematica.

Il Gioco Infinito e il Giudice Strano

Immagina di giocare a un videogioco infinito. Sei in una stanza con delle porte (gli stati) e devi scegliere quale porta aprire (le azioni). Ogni volta che apri una porta, guadagni dei punti (la ricompensa) e finisci nella prossima stanza. Il gioco non finisce mai: è una sequenza infinita di scelte.

In genere, quando pensiamo a come valutare questo gioco, usiamo due metodi classici:

1. La somma scontata: I punti che ottieni oggi valgono molto, quelli di domani valgono un po' meno, e quelli tra un milione di anni valgono quasi zero.
2. La media a lungo termine: Non ci importa se oggi guadagni 100 o 1, ma ci importa quanto guadagni in media dopo un tempo lunghissimo.

Il Problema: Il Giudice "Diffuso"

Gli autori di questo articolo (Flesch, Predtetchinski, Sudderth e Venel) hanno introdotto un nuovo tipo di "Giudice" per valutare il tuo gioco. Questo Giudice non usa la somma scontata né la media semplice. Usa quello che chiamano una "carica diffusa" (o diffuse charge).

L'analogia del Giudice:
Immagina un giudice che guarda l'intera storia infinita del tuo gioco.

• Non si fissa su un singolo momento specifico (perché ogni singolo istante ha peso zero per lui).
• Non guarda solo la media finale.
• È un giudice molto strano che assegna un "valore" a intere sequenze di eventi in modo molto sottile e matematico.

Il grande mistero che gli studiosi volevano risolvere era questo: Esiste sempre una strategia perfetta per vincere contro questo Giudice?

La Scoperta: No, a volte non esiste la strategia perfetta

Per molto tempo, si pensava che se il Giudice fosse "razionale" (rispettasse il principio del valore temporale del denaro, ovvero che un punto oggi vale più di un punto domani), allora esisteva sempre una strategia vincente, anche semplice e fissa.

Ma gli autori hanno detto: "Aspetta, cosa succede se il Giudice è davvero strano?"

Hanno costruito un esempio matematico (chiamato "MDP pari o dispari") che è come un trucco di prestigio. Ecco come funziona il loro esperimento mentale:

1. Il Gioco: Sei in una stanza. Hai due scelte:

   • Opzione A: Guadagni 1 punto adesso, ma 0 punti al turno successivo.
   • Opzione B: Guadagni 0 punti adesso, ma 1 punto al turno successivo.
   • Il gioco si ripete all'infinito.

2. Il Trucco del Giudice:
   Il Giudice che hanno inventato è un "mostro" matematico fatto di due parti:

   • Parte 1: Guarda solo i turni dispari (1, 3, 5...). Se giochi bene qui, ottieni punti.
   • Parte 2: Guarda solo i turni pari (2, 4, 6...), ma in modo molto specifico. Vuole che tu giochi in un certo modo molto spesso, ma non sempre.

3. Il Dilemma:

   • Se giochi sempre l'Opzione A (per fare punti nei turni dispari), il Giudice della Parte 2 ti punisce perché non hai mai fatto l'Opzione B nei turni pari.
   • Se giochi l'Opzione B ogni tanto per accontentare la Parte 2, perdi punti nella Parte 1.
   • Se provi a fare un misto perfetto, il Giudice cambia le regole in modo che tu non possa mai raggiungere il punteggio massimo teorico (che è 1).

La Conclusione: Il Paradosso della Perfezione

La scoperta rivoluzionaria è questa: In questo gioco specifico, non esiste una strategia vincente.

Non importa quanto sei bravo, non importa se giochi in modo casuale o calcolato:

• Puoi avvicinarvi al punteggio perfetto (es. 0,999999).
• Puoi sempre trovare una strategia leggermente migliore di quella precedente.
• Ma non esiste mai una strategia che ti dia il punteggio massimo assoluto.

È come se fossi in una gara di corsa contro un orologio che scatta all'infinito: puoi correre sempre più veloce, avvicinandoti alla velocità della luce, ma non potrai mai raggiungerla.

Perché è importante?

Questo studio ci dice che quando le regole di valutazione sono molto complesse e "strane" (come quelle definite da queste cariche matematiche), la nostra intuizione ci inganna. Pensiamo che se c'è un obiettivo, ci deve essere un modo per raggiungerlo. Invece, in certi mondi matematici infiniti, l'obiettivo perfetto è irraggiungibile.

È una lezione profonda sulla natura delle decisioni: a volte, cercare la soluzione "perfetta" è inutile perché, per la natura stessa del problema, la perfezione non esiste. Devi accontentarti di fare "il meglio possibile", sapendo che c'è sempre un margine di miglioramento, ma mai un punto di arrivo definitivo.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "Optimal strategies in Markov decision processes with finitely additive evaluations" di János Flesch, Arkadi Predtetchinski, William Sudderth e Xavier Venel.

1. Problema e Contesto

Il paper si occupa di Processi Decisionali di Markov (MDP) a orizzonte infinito con spazi di stati e azioni finiti. La novità fondamentale risiede nel modo in cui il decisore valuta le strategie.

• Scenario Standard: Solitamente, le prestazioni di una strategia sono valutate tramite la somma scontata (discounted sum) o la media a lungo termine (long-term average) delle ricompense attese.
• Scenario del Paper: L'aggregazione della sequenza infinita di ricompense attese non avviene tramite un limite classico o uno sconto esponenziale, ma mediante una carica diffusa (diffuse charge).
  • Una carica è una misura di probabilità finitamente additiva definita sull'insieme dei numeri naturali $\mathbb{N}$.
  • Una carica è diffusa se assegna misura zero a ogni singolo istante (ogni stadio $n$ ha peso 0).
  • Il payoff di una strategia $\sigma$ è definito come l'integrale rispetto a questa carica $\mu$ della sequenza delle ricompense attese: $u_\mu(\sigma) = \int_{t \in \mathbb{N}} \mathbb{E}_\sigma[r_t] \, \mu(dt)$.

Il problema centrale è determinare se, in ogni MDP con una qualsiasi carica di aggregazione $\mu$, esista una strategia ottimale (una strategia che massimizza il payoff).

2. Metodologia e Strumenti Matematici

Gli autori utilizzano strumenti avanzati di teoria della misura e analisi funzionale:

• Teoria delle Cariche: Si lavora con l'insieme $\Delta_f$ delle cariche su $\mathbb{N}$ e il suo sottoinsieme $\Delta_d$ delle cariche diffuse.
• Topologia della Convergenza Puntuale: Lo spazio delle cariche è dotato della topologia della convergenza puntuale, rendendolo uno spazio compatto di Hausdorff (ma non metrizzabile). Questo permette di utilizzare argomenti di punti di accumulazione per sequenze di cariche.
• Principio del Valore Temporale del Denaro (TVM): Viene richiamato il lavoro di Neyman [2023], che dimostra l'esistenza di strategie ottimali pure e stazionarie se la carica soddisfa il principio TVM (che implica una certa "regolarità" rispetto alle frequenze limite).
• Costruzione di Controesempi: La metodologia principale per la negazione dell'esistenza è la costruzione esplicita di un MDP e di una carica $\mu$ "delicatamente costruita" che crea un conflitto irrisolvibile tra diverse componenti della carica stessa.

3. Risultati Chiave

A. Il Teorema di Neyman (Riferimento)

Il paper cita il risultato di Neyman [2023]: se la carica di aggregazione soddisfa il principio del valore temporale del denaro (equivalente a essere compresa tra il limite inferiore e superiore delle frequenze), allora in ogni MDP esiste una strategia pura stazionaria che è ottimale per tutte le cariche di quella classe.

B. Il Risultato Principale: Non Esistenza di Strategie Ottimali

Il contributo centrale del paper è il Teorema 3, che risponde negativamente alla domanda se un'ottima strategia esista sempre, anche senza assumere il principio TVM.

• Affermazione: Esiste un MDP e una carica diffusa $\mu$ tale che non esiste alcuna strategia ottimale, né pura né randomizzata.
• Il Controesempio (Even-or-Odd MDP):
  • Struttura: Stati $\{1, 2, 3\}$. Stato iniziale 1.
    • Stato 1: Scelta tra azione $T$ (ricompensa 1, transizione a 2) e $B$ (ricompensa 0, transizione a 3).
    • Stati 2 e 3: Unica azione disponibile, ricompense 0 e 1 rispettivamente, transizione deterministica allo stato 1.
  • Dinamica: Il gioco si svolge in blocchi di due stadi. In ogni stadio dispari, il decisore sceglie se ottenere 1 subito e 0 dopo, oppure 0 subito e 1 dopo.
  • Costruzione della Carica $\mu$:
    1. Si definisce una carica $\mu_0$ concentrata sugli stadi dispari (tramite una carica di frequenza $\phi$).
    2. Si definisce una sequenza di cariche $\mu_n$ concentrate su insiemi $E_n$ (multipli di $2^n$).
    3. Si prende un punto di accumulazione $\mu^*$ della sequenza $\{\mu_n\}$ nella topologia puntuale.
    4. La carica finale è la media: $\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$.
  • Il Paradosso:
    • Per massimizzare il payoff rispetto a $\mu_0$, il decisore dovrebbe scegliere l'azione $T$ (ricompensa 1) il più spesso possibile negli stadi dispari.
    • Per massimizzare il payoff rispetto a $\mu^*$, il decisore deve scegliere l'azione $B$ con una frequenza positiva negli stadi pari (poiché $\mu^*$ assegna misura 1 agli insiemi $E_n$ che contengono molti stadi pari).
    • Conflitto: Qualsiasi strategia che gioca $T$ con frequenza 1 ottiene 1 contro $\mu_0$ ma solo 0.5 contro $\mu^*$ (payoff totale 0.75). Qualsiasi strategia che gioca $B$ con frequenza positiva riduce il payoff contro $\mu_0$.
    • Dimostrazione: Il valore supremo del gioco è $v_\mu = 1$. Tuttavia, per ogni strategia $\sigma$, il payoff $u_\mu(\sigma)$ è strettamente minore di 1. Quindi, il supremo non è raggiunto.

C. Osservazioni Aggiuntive

• Strategie Stazionarie: Anche in casi dove esiste una strategia ottimale (pura), questa potrebbe non essere stazionaria (es. Esempio 4).
• Cariche Non Diffuse: Se la carica non è diffusa (contiene una parte additiva numerabile), l'esistenza di strategie ottimali pure è garantita (caso C1) o può fallire se c'è una combinazione di sconto e media (caso C2, Esempio 5).

4. Significato e Implicazioni

1. Limiti della Stazionarietà: Il lavoro dimostra che l'ipotesi del "valore temporale del denaro" è cruciale. Senza di essa, la struttura semplice delle strategie stazionarie (o anche puramente randomizzate) non è sufficiente a garantire l'ottimalità.
2. Natura dell'Aggregazione: Mostra come la scelta della misura di aggregazione (la carica) possa alterare radicalmente la teoria dell'ottimizzazione dinamica. Una carica "patologica" (costruita tramite punti di accumulazione) può creare situazioni in cui il decisore è in un paradosso di scelta: può avvicinarsi arbitrariamente al valore ottimo, ma non può mai raggiungerlo.
3. Impatto sulla Teoria degli MDP: Questo risultato chiude una questione aperta sollevata da Neyman [2023], fornendo una risposta negativa definitiva all'esistenza universale di strategie ottimali in MDP con valutazioni finitamente additive arbitrarie.

In sintesi, il paper stabilisce che in un contesto di MDP con valutazioni basate su cariche diffuse generali, l'ottimalità non è garantita, e la ricerca di strategie ottimali può fallire completamente a causa della natura non misurabile o "sfuggente" della carica di aggregazione rispetto alla dinamica del processo decisionale.