Sintesi Tecnica: Q-Learning sotto Criterio di Costo Medio per MDP Continui

1. Formulazione del Problema

Questo articolo affronta la sfida di risolvere i Processi Decisionali di Markov (MDP) con spazi di stato e di azione continui sotto il criterio del costo medio a orizzonte infinito. Il modello è definito da una terna $(X, U, \mathcal{T}, c)$, dove $X$ e $U$ sono spazi Borel standard (spazi metrici completi e separabili), $\mathcal{T}$ è il kernel di transizione e $c$ è la funzione di costo. L'obiettivo è trovare una politica $\pi$ che minimizzi il costo medio a lungo termine:
$$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$$

Gli autori evidenziano come, mentre i problemi a orizzonte finito e a costo scontato per spazi continui siano ben studiati utilizzando le proprietà di contrazione degli operatori di Bellman, i problemi a costo medio presentino difficoltà uniche. Nello specifico, l'assenza di un fattore di sconto rimuove la contrazione immediata della mappatura, richiedendo assunzioni alternative di stabilità ed ergodicità. Inoltre, la letteratura esistente sul reinforcement learning (RL) a costo medio si concentra principalmente su spazi finiti o impone ipotesi strutturali restrittive (ad esempio, dinamiche lineari, politiche Lipschitziane) che ne limitano l'applicabilità a spazi continui generali.

2. Metodologia

Il documento impiega un approccio a due fronti: approssimazione finita tramite quantizzazione e algoritmi di reinforcement learning progettati per tali approssimazioni.

2.1 Discretizzazione e Approssimazione

La metodologia centrale consiste nel costruire un MDP approssimato a stati e azioni finiti quantizzando gli spazi continui.

• Quantizzazione dello Stato: Lo spazio degli stati $X$ è partizionato in bin disgiunti $\{B_i\}_{i=1}^M$ con stati rappresentativi $y_i$. Viene definita una mappatura $q: X \to Y$ (dove $Y$ è l'insieme finito dei rappresentanti).
• Quantizzazione dell'Azione: Lo spazio delle azioni $U$ è approssimato da un insieme finito $\Lambda$.
• Costruzione del Modello Approssimato: Il modello approssimato $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ è definito utilizzando una misura di peso $\mu$ (spesso la misura invariante del processo di stato). I kernel di costo e di transizione approssimati sono medie delle funzioni originali sui bin di quantizzazione:
  $$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$$
• Rilassamento delle Condizioni di Continuità: Un significativo spostamento metodologico è il rilassamento della condizione di continuità della Variazione Totale (TV), standard nella letteratura di approssimazione precedente (ad es., Saldi et al., 2018). Gli autori stabiliscono risultati di approssimazione sotto:
  1. Continuità Debole (Feller): Sufficiente per la convergenza asintotica degli errori al diminuire delle dimensioni della griglia.
  2. Continuità Wasserstein: Sufficiente per stabilire tassi di convergenza espliciti (limiti di errore) al diminuire delle dimensioni della griglia.

2.2 Algoritmi di Reinforcement Learning

Il documento propone algoritmi di Quantized Q-Learning per apprendere la politica ottimale per il modello approssimato direttamente dai dati.

• Algoritmo Sincrono (Algoritmo 1): Aggiorna i valori Q per tutte le coppie stato-azione nella griglia finita simultaneamente. Si basa sul campionamento degli stati da ogni bin secondo una misura predeterminata.
• Algoritmo Asincrono (Algoritmo 2): Aggiorna i valori Q basandosi su una singola traiettoria del processo continuo originale. Questo è più pratico ma introduce un termine di rumore non-Markoviano poiché il processo quantizzato $q(X_t)$ non è una catena di Markov (è un MDP parzialmente osservabile dal punto di vista dello stato quantizzato).
• Meccanismo di Convergenza: Per gestire il criterio del costo medio e la mancanza di limitatezza delle iterazioni Q (a differenza dei casi scontati), gli autori utilizzano:
  • Semi-norme Span per gli aggiornamenti sincroni.
  • Assunzioni di Ergodicità: La politica di esplorazione deve indurre una misura invariante unica con supporto completo su tutti i bin quantizzati.
  • Aggiornamenti Spostati (Shifted Updates): L'algoritmo asincrono sottrae un valore di riferimento (basato su un bin specifico) per stabilizzare l'iterazione, trattando il processo quantizzato come un POMDP.

3. Contributi Chiave

Il documento apporta tre contributi primari, facendo avanzare lo stato dell'arte nel controllo a spazio continuo:

1. Teoria dell'Approssimazione con Condizioni Più Deboli:

   • Gli autori forniscono limiti di errore per le approssimazioni finite sotto continuità debole e continuità Wasserstein, rilassando la rigorosa continuità della Variazione Totale richiesta dai lavori precedenti (ad es., Saldi et al., 2018).
   • Stabiliscono che, sotto continuità Wasserstein (con una costante di contrazione $K_T < 1$), l'errore nel costo medio ottimale decade a un tasso proporzionale all'errore di quantizzazione (specificamente $L_X^\delta$).
   • Sotto sola continuità debole, dimostrano la convergenza asintotica del costo della politica approssimata al costo ottimale al diminuire della discretizzazione.

2. Convergenza del Quantized Q-Learning:

   • Il documento stabilisce la convergenza quasi certa sia degli algoritmi di Q-learning sincroni che asincroni per spazi continui.
   • Fondamentalmente, dimostrano che questi algoritmi convergono ai valori Q ottimali del modello finito approssimato costruito, non solo al modello continuo originale. Questa distinzione è vitale perché il processo quantizzato non è strettamente Markoviano.
   • L'analisi generalizza i risultati precedenti (ad es., Kara e Yüksel, 2023) dai costi scontati al più complesso criterio del costo medio, richiedendo una nuova analisi tecnica per gestire le iterazioni Q non limitate.

3. Garanzie di Quasi-Ottimalità:

   • Combinando i limiti di errore di approssimazione con la convergenza degli algoritmi di apprendimento, il documento dimostra che le politiche apprese tramite il quantized Q-learning sono quasi-ottimali per l'MDP continuo originale.
   • La perdita di prestazione è esplicitamente limitata in termini di risoluzione della quantizzazione e delle costanti Lipschitz dei kernel di costo e di transizione.

4. Risultati Chiave e Teoremi

• Teoremi 1 & 2 (Limiti di Approssimazione): Stabiliscono limiti superiori sulla differenza tra il costo medio ottimale del modello originale ($\rho$) e quello del modello approssimato ($\hat{\rho}$).
  • Sotto continuità Wasserstein: $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$, dove $L_X$ è l'errore di quantizzazione.
  • Sotto continuità debole: $\lim_{n \to \infty} \rho(\pi_n) = \rho$.
• Teoremi 5 & 6 (Convergenza dell'Algoritmo): Dimostrano che le iterazioni di Q-learning sincrone e asincrone convergono ai valori Q ottimali del modello finito approssimato. La convergenza asincrona si basa sull'ergodicità del processo di stato sotto la politica di esplorazione.
• Corollario 1: Combina i risultati di approssimazione e apprendimento per mostrare che la politica appresa $\hat{\pi}$ soddisfa $\rho(\hat{\pi}) - \rho \leq \epsilon$, dove $\epsilon$ svanisce al diminuire della dimensione della griglia di discretizzazione.

5. Significato e Rivendicazioni

Gli autori posizionano questo lavoro come una soluzione a problemi aperti nella letteratura riguardante il reinforcement learning per MDP a costo medio con spazi continui.

• Rilassamento delle Assunzioni: Il documento rivendica un avanzamento teorico significativo passando dalla continuità della Variazione Totale, spesso troppo restrittiva per i modelli pratici, alla continuità debole e Wasserstein. Ciò amplia la classe di sistemi (ad esempio, quelli con rumore additivo o dinamiche specifiche) per i quali è possibile fornire garanzie teoriche.
• Colmare il Divario tra Teoria e Pratica: Dimostrando che il Q-learning converge alla soluzione di una ben definita approssimazione finita, il documento fornisce una giustificazione rigorosa per l'uso del RL basato sulla discretizzazione in contesti di costo medio continuo. Chiarisce che la "quasi-ottimalità" è una diretta conseguenza della qualità dell'approssimazione, non un artefatto dell'algoritmo di apprendimento.
• Gestione della Quantizzazione Non-Markoviana: Il documento affronta esplicitamente la difficoltà tecnica per cui il processo di stato quantizzato è un POMDP, non un MDP, e fornisce una prova di convergenza per l'apprendimento asincrono in questo contesto sotto il criterio del costo medio, un vuoto precedentemente evidenziato nella letteratura (ad es., Wan et al., 2021).

Il documento conclude con uno studio numerico su un problema di controllo continuo, dimostrando la convergenza delle funzioni valore e la riduzione del regret all'aumentare del tasso di quantizzazione, validando i limiti teorici.