Riepilogo Tecnico: Q-MMR: Valutazione Off-Policy tramite Ripesatura Ricorsiva e Corrispondenza dei Momenti

1. Enunciato del Problema

Il lavoro affronta la Valutazione Off-Policy (OPE) in Processi Decisionali di Markov (MDP) a orizzonte finito. L'obiettivo è stimare il rendimento atteso $J(\pi)$ di una politica target $\pi$ utilizzando un dataset raccolto da una politica di comportamento $\pi_D$. Il contesto coinvolge l'Approssimazione Funzionale Generale (GFA), dove una classe di funzioni $\mathcal{F}$ è utilizzata per modellare la funzione Q della politica target, $Q^\pi$.

Gli autori identificano due principali lacune teoriche nella letteratura esistente sull'OPE:

1. Dipendenza dalla Dimensione: Le analisi standard per la GFA (ad esempio, Fitted-Q Evaluation, FQE) producono tipicamente limiti di errore che dipendono dalla complessità statistica della classe di funzioni (ad esempio, $\log |\mathcal{F}|$ o numeri di copertura). Questa dipendenza è spesso lasca, specialmente in contesti on-policy dove le stime Monte-Carlo sono prive di dipendenza dalla dimensione.
2. Incoerenza con le Analisi Lineari/Tabulari: Garanzie raffinate e prive di dipendenza dalla dimensione esistono per contesti lineari e tabulari (spesso sotto la sola realizzabilità), ma questi risultati non si estendono naturalmente a classi di funzioni generali. Inoltre, le analisi lineari spesso si basano su condizioni più deboli (realizzabilità) rispetto alle assunzioni di completezza di Bellman richieste per le analisi GFA generali.

2. Metodologia: Q-MMR

Gli autori propongono Q-MMR (Ripesatura Basata sui Momenti della Funzione Q), un nuovo framework algoritmico che apprende un insieme di pesi scalari, uno per ogni punto dati, in modo induttivo in senso top-down.

Panoramica dell'Algoritmo

Dati $n$ traiettorie i.i.d. e una classe di funzioni $\mathcal{F} = \{\mathcal{F}_h\}_{h=1}^H$:

1. Inizializzazione: Impostare i pesi $w^{(i)}_0 \equiv 1$ per tutti i punti dati $i$ (poiché la coppia stato-azione iniziale è fissa).
2. Ripesatura Ricorsiva: Per ogni passo temporale $h = 1$ a $H$, l'algoritmo apprende un vettore di pesi $w^{[n]}_h = \{w^{(i)}_h\}_{i=1}^n$ risolvendo un problema di ottimizzazione minimax:
   $$\hat{w}^{[n]}_h = \arg\min_{w^{[n]}_h} \sup_{f \in \mathcal{F}_h} \left| \frac{1}{n} \sum_{i=1}^n w^{(i)}_h f(s^{(i)}_h, a^{(i)}_h) - \frac{1}{n} \sum_{i=1}^n \hat{w}^{(i)}_{h-1} f(s^{(i)}_h, \pi) \right|$$
   Questo obiettivo minimizza la discrepanza (tramite una Metrica di Probabilità Integrale) tra la distribuzione ripesata delle coppie stato-azione correnti e la distribuzione ripesata del prossimo stato sotto la politica target.
3. Stima: La stima finale del rendimento è la somma ripesata delle ricompense:
   $$\hat{J}(\pi) = \frac{1}{n} \sum_{i=1}^n \sum_{h=1}^H w^{(i)}_h r^{(i)}_h$$

Scelte Chiave di Progettazione

• Pesi Non Parametrici: A differenza dei metodi di Campionamento per Importanza Marginalizzato (MIS) che apprendono una funzione parametrica per i pesi, Q-MMR apprende uno scalare distinto per ogni punto dati.
• Principio del Secondo Momento Minimo: Poiché il minimizzatore della perdita di corrispondenza non è generalmente unico, l'algoritmo seleziona la soluzione con il secondo momento empirico minimo ($\|w^{[n]}_h\|_{[n]}$) per controllare la varianza.
• Induzione Top-Down: I pesi sono calcolati livello per livello da $h=0$ a $H$, facendo affidamento sui pesi del passo precedente.

3. Contributi Chiave e Risultati Teorici

A. Garanzia a Campione Finito Senza Dipendenza dalla Dimensione

Il contributo teorico principale è il Teorema 1, che fornisce un limite a campione finito dipendente dai dati per l'errore OPE. Sotto la standard Assunzione di Realizzabilità ($Q^\pi \in \mathcal{F}$), con probabilità almeno $1-\delta$:
$$|\hat{J}(\pi) - J(\pi)| \leq \sum_{h=1}^H \hat{L}_h(\hat{w}^{[n]}_h; \hat{w}^{[n]}_{h-1}) + \sum_{h=0}^H \epsilon^{\text{stat}}_h$$
dove:

• $\hat{L}_h$ è la perdita di corrispondenza empirica ottenuta dall'algoritmo.
• $\epsilon^{\text{stat}}_h \propto \| \hat{w}^{[n]}_h \|_{[n]} \sqrt{\frac{\log(1/\delta)}{n}}$.

Significato:

• Senza Dipendenza dalla Dimensione: Il limite non dipende esplicitamente dalla complessità statistica di $\mathcal{F}$ (ad esempio, nessun termine $\log |\mathcal{F}|$) nell'ordine principale. Questo è ottenuto evitando limiti di unione sulla classe di funzioni e facendo affidamento invece su argomenti di concentrazione specifici per i pesi realizzati.
• WYSIWYG (Ciò che Vedi è Ciò che Ottieni): Il limite è direttamente calcolabile dai dati, poiché dipende dalla perdita di corrispondenza osservata e dal secondo momento dei pesi appresi.
• Assunzioni Più Deboli: La garanzia vale sotto la sola Realizzabilità, senza richiedere la più forte assunzione di completezza di Bellman tipicamente necessaria per la GFA.

B. Connessione con Metodi Esistenti

Il lavoro stabilisce che Q-MMR unifica e recupera risultati noti in casi speciali:

• Contesti Lineari e Tabulari: Quando specializzato per classi di funzioni lineari (con matrice di covarianza campionaria invertibile) o contesti tabulari, Q-MMR coincide rispettivamente con FQE Lineare e FQE Tabulare (o equivalenza certa basata su modello).
• Recupero di Limiti Finemente Granulari: In questi casi speciali, l'analisi Q-MMR recupera i tassi privi di dipendenza dalla dimensione, $O(1/\sqrt{n})$, trovati nella letteratura precedente lineare/tabulare (ad esempio, Duan et al., 2020; Yin e Wang, 2021), colmando il divario tra analisi generali e lineari.
• Monte-Carlo e Campionamento per Importanza: In contesti on-policy, impostando i pesi a 1 si recupera lo stimatore Monte-Carlo. Con modifiche specifiche, può anche recuperare il campionamento per importanza passo-passo.

C. Approfondimenti sulla Copertura

Il lavoro fornisce una comprensione teorica più profonda della copertura nell'RL offline:

• Magnitudine del Peso come Copertura: Il termine $\|w^{[n]}_h\|_{[n]}$ (e il suo corrispettivo di popolazione $\|w^\star_h\|_{2, d_D}$) agisce come un parametro di copertura empirico.
• Natura della Copertura: Attraverso un'ulteriore analisi (Sezione 4), gli autori mostrano che la "copertura" richiesta non è meramente la copertura dell'occupazione delle caratteristiche della politica target $E_{d^\pi}[\phi]$, ma piuttosto la copertura di un vettore definito da un specifico sistema dinamico lineare (analogo a $\psi_h$ nelle analisi lineari).
• Completezza di Bellman: Sotto la completezza di Bellman, i pesi di popolazione $w^\star_h$ recuperano perfettamente la distribuzione target $d^\pi_h$, e il termine di stabilità che controlla l'esplosione dei pesi è limitato da 1. Senza completezza, la stabilità dipende dalla norma dell'operatore degli operatori di transizione proiettati, il che può portare a una crescita esponenziale dei pesi se il sistema è instabile.

4. Significato e Affermazioni

Il lavoro afferma di fornire un framework teorico unificato che risolve la tensione tra approssimazione funzionale generale e analisi lineari/tabulari nell'OPE.

• Unificazione: Dimostra che le proprietà "senza dipendenza dalla dimensione" osservate in contesti lineari/tabulari non sono artefatti della linearità, ma possono essere ottenute in contesti generali sotto realizzabilità, a condizione che si utilizzi un approccio di corrispondenza dei momenti con pesi non parametrici.
• Novità dell'Analisi: L'analisi è descritta come "semplice in modo netto", evitando complessi limiti di unione sulla classe di funzioni. Sfrutta la natura telescopica dell'equazione di Bellman e la struttura specifica dell'obiettivo di corrispondenza dei momenti.
• Implicazioni Pratiche: Il limite dipendente dai dati offre un meccanismo integrato per la quantificazione dell'incertezza, poiché il limite di errore è calcolabile dal dataset senza bisogno di conoscere la vera complessità della classe di funzioni.

Gli autori notano limitazioni, inclusa la necessità di dati di traiettoria i.i.d. (che si rompe nella raccolta adattiva) e la natura greedy e locale dell'ottimizzazione dei pesi (che non tiene conto esplicitamente degli effetti a valle, sebbene questo sia un compromesso per evitare problemi di doppio campionamento trovati in altri metodi MIS).

In sintesi, Q-MMR offre un approccio teoricamente rigoroso e privo di dipendenza dalla dimensione all'OPE che generalizza le proprietà favorevoli dei metodi lineari a classi di funzioni generali, basandosi solo sulla realizzabilità.