🤖 machine learning

Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

Questo articolo introduce un framework quotient-DAG e l'algoritmo Forward-DP per eliminare la varianza di disturbo e abilitare il calcolo esatto delle propensioni di slate non ordinati per una valutazione off-policy efficiente nei sistemi di raccomandazione autoregressivi.

Autori originali: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

Pubblicato 2026-05-29

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di essere uno chef che cerca di valutare quanto sarebbe buona una nuova ricetta (la Policy Target), ma non puoi effettivamente cucinarla nella tua cucina perché è troppo costosa o rischiosa. Invece, hai un quaderno pieno di ricette cucinate in passato da uno chef diverso (la Policy Comportamentale). Il tuo obiettivo è stimare quanto sarebbe deliziosa la nuova ricetta utilizzando solo quel vecchio quaderno. Questo è il problema centrale della Valutazione Off-Policy (OPE).

Il Problema: Contare le Cose Sbagliate

Di solito, per giudicare la nuova ricetta, guardi ogni singolo passo compiuto dallo chef precedente. Dici: "Ok, hanno aggiunto sale, poi pepe, poi aglio". Calcoli un punteggio basato su quella sequenza esatta.

Ma ecco il punto critico: a volte l'ordine in cui si aggiungono gli ingredienti non cambia effettivamente il sapore del piatto finale.

Lo Scenario: Immagina un "foglio" di elementi (come una playlist di 5 brani o un vassoio di 5 antipasti). Il cliente si cura solo di quali 5 elementi ci sono sul vassoio, non dell'ordine in cui lo chef li ha disposti.
L'Errore: Il vecchio quaderno registra l'ordine (Brano A, poi B, poi C...). Se calcoli il tuo punteggio basandoti su quell'ordine specifico, stai trattando l'"ordine" come importante. Ma poiché al cliente non importa, stai aggiungendo "rumore" al tuo calcolo.
Il Risultato: Questo rumore crea un'enorme quantità di confusione (varianza). È come cercare di indovinare il peso di una valigia pesando ogni singolo calzino al suo interno individualmente, invece di pesare semplicemente la valigia nel suo complesso. Ottieni molte risposte diverse a seconda di come hai contato i calzini.

Inoltre, calcolare la "vera" probabilità di ottenere un gruppo specifico di 5 elementi (ignorando l'ordine) è un incubo matematico. Se hai 5 elementi, ci sono 120 modi diversi (5 fattoriale) in cui potrebbero essere stati scelti. Fare questi calcoli per ogni singola voce nel tuo quaderno è computazionalmente impossibile per gruppi grandi.

La Soluzione: Il "Quotient DAG" (La Mappa di Raggruppamento)

Gli autori propongono un nuovo modo intelligente di guardare i dati. Invece di guardare ogni singolo percorso compiuto dallo chef, suggeriscono di raggruppare tutti i percorsi che portano allo stesso risultato.

L'Analogia: Immagina un albero gigante dove ogni ramo rappresenta un diverso ordine di aggiunta degli ingredienti.
- Vecchio Modo: Cammini lungo ogni singolo ramo, misuri il peso e cerchi di farne la media.
- Nuovo Modo (Quotient DAG): Ti rendi conto che tutti i rami che finiscono con lo stesso insieme di ingredienti sono in realtà lo stesso "nodo" nella tua mappa. Collassi tutti quei rami in un singolo punto.
- La Mappa: Questo crea un "Grafo Aciclico Diretto" (DAG)—una mappa in cui ti importa solo dell'insieme di elementi scelti finora, non dell'ordine.

Il Trucco Magico: Campionamento per Importanza a Flusso Avanti

Una volta ottenuta questa mappa semplificata, devi sapere quanto è probabile che lo chef nuovo raggiunga un determinato "insieme" rispetto allo chef vecchio.

Vecchio Modo: Dovresti sommare le probabilità di tutti i 120 ordini diversi per ottenere la risposta.
Nuovo Modo (Forward-DP): Gli autori hanno inventato un metodo chiamato Forward-DP (Programmazione Dinamica). Immagina questo come una calcolatrice intelligente che costruisce la risposta passo dopo passo.
- Inizia con un vassoio vuoto (probabilità 1).
- Chiede: "Se ho 1 elemento, qual è la probabilità di aggiungerne un 2°?"
- Chiede: "Se ho 2 elementi, qual è la probabilità di aggiungerne un 3°?"
- Continua a costruire la probabilità dell'intero insieme senza mai aver bisogno di elencare tutti i 120 ordini.

Questo metodo è esatto (non indovina) e veloce. Invece di richiedere anni per il calcolo (tempo fattoriale), richiede una quantità di tempo gestibile (esponenziale nella dimensione del vassoio, ma polinomiale nella dimensione del menu).

Perché Questo È Importante

Meno Rumore: Ignorando i dettagli irrilevanti dell'"ordine", la matematica diventa molto più pulita. Le stime sono più accurate e stabili.
Fattibilità: Rende possibile valutare sistemi di raccomandazione complessi (come "mostrami 10 film") che in precedenza erano troppo difficili da calcolare esattamente.
Test nel Mondo Reale: Gli autori hanno testato questo metodo su:
- Dati Medici: Simulando trattamenti per la sepsi (infezione del sangue). Il loro metodo ha fornito previsioni molto più accurate degli esiti dei pazienti rispetto ai metodi più vecchi.
- Dati di Raccomandazione: Utilizzando un dataset chiamato KuaiRec (raccomandazioni video). Hanno dimostrato che il loro metodo poteva calcolare la probabilità "vera" di un gruppo di video raccomandati in pochi secondi, mentre il vecchio metodo avrebbe richiesto giorni o sarebbe stato impossibile.

Riepilogo

Il paper introduce un modo per smettere di sovra-analizzare il "come" (l'ordine delle azioni) e concentrarsi sul "cosa" (l'insieme finale degli elementi). Raggruppando percorsi equivalenti e utilizzando un metodo di calcolo intelligente e passo-passo (Forward-DP), possono valutare nuove strategie in modo molto più accurato ed efficiente, specialmente in campi come l'assistenza sanitaria e i motori di raccomandazione, dove testare nuove idee nella realtà è troppo pericoloso o costoso.

Riepilogo Tecnico: DAG Quoziente per la Valutazione Fuori Politica

Enunciato del Problema

La valutazione fuori politica (OPE) stima le prestazioni di una politica target $\pi$ utilizzando dati raccolti da una politica comportamentale $\beta$ . Il campionamento per importanza (IS) standard ripesa le traiettorie registrate mediante il prodotto dei rapporti di probabilità tra azioni target e comportamentali. Tuttavia, questo approccio spesso tratta i dettagli del processo di generazione come significativi, anche quando l'obiettivo della valutazione li ignora.

Un caso primario di tale problema si riscontra nella raccomandazione a schede (slate), dove i generatori moderni costruiscono spesso le schede (insiemi di elementi) in modo autoregressivo, esponendo le probabilità passo-passo lungo un ordinamento specifico. Eppure, la ricompensa e gli stimatori a valle dipendono spesso solo dalla scheda non ordinata. L'IS standard sulle traiettorie assegna un rapporto di verosimiglianza a un percorso ordinato specifico, creando un "divario di propensione congiunta": il registratore espone una probabilità di ordinamento, mentre lo stimatore richiede la probabilità totale della scheda non ordinata. Calcolare questa propensione non ordinata esatta richiede tipicamente la somma su tutti gli $K!$ ordini di generazione, il che è computazionalmente intrattabile per dimensioni di scheda moderate. Inoltre, trattare l'ordinamento come significativo introduce varianza di disturbo quando la ricompensa è invariante rispetto all'ordine di generazione.

Metodologia

Il documento introduce una visione a DAG Quoziente per affrontare questi problemi. L'idea centrale è quozientare l'albero di espansione dei prefissi storici mediante una relazione di equivalenza sufficiente per l'obiettivo di valutazione.

DAG Quoziente e Flusso Avanti:
- L'albero di espansione viene collassato fondendo i prefissi storici che sono equivalenti per l'obiettivo di valutazione (ad esempio, prefissi contenenti lo stesso insieme di elementi selezionati, indipendentemente dall'ordine).
- Questo forma un Grafo Aciclico Diretto (DAG) stratificato in cui i nodi rappresentano classi di equivalenza (stati quoziente).
- Invece di pesare con il rapporto di un singolo percorso realizzato, il metodo assegna pesi utilizzando il rapporto di flusso avanti $F_\pi(z)/F_\beta(z)$ , dove $F_\mu(z)$ è la massa di probabilità che raggiunge il nodo $z$ sotto la politica $\mu$ .
- Questo approccio generalizza i metodi esistenti: l'IS per decisione singola, l'IS marginalizzato e l'MIS con astrazione nota sono casi speciali corrispondenti a diverse scelte di relazioni di equivalenza.
Campionamento per Importanza a Flusso Avanti (FF-IS):
- Per l'OPE generale a orizzonte finito, lo stimatore sostituisce il rapporto di prefisso campionato nell'IS per decisione singola (PDIS) con il rapporto di verosimiglianza quoziente.
- L'analisi teorica mostra che, per ritorni misurabili al quoziente terminali, questo pesatura rimuove il disallineamento target-comportamento "entro-classe", fornendo un'espressione esatta del divario di varianza che quantifica la riduzione della varianza di disturbo.
Forward-DP per la Valutazione Fuori Politica delle Schede:
- Il documento specializza questo framework alla generazione autoregressiva di schede sotto un'interfaccia sufficiente per l'insieme (Definizione 1). Una politica è sufficiente per l'insieme se la probabilità di selezionare l'elemento successivo dipende solo dal contesto e dall'insieme degli elementi già selezionati, non dal loro ordine.
- In condizioni di sufficienza per l'insieme, il quoziente di permutazione corrisponde a un DAG di sottoinsiemi, dove i nodi sono sottoinsiemi del catalogo e gli archi aggiungono elementi non selezionati.
- Algoritmo Forward-DP: Un algoritmo di programmazione dinamica calcola la propensione esatta della scheda non ordinata $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ sommando su sottoinsiemi anziché su permutazioni.
  - Complessità: $O((M + K) \cdot 2^K)$ , dove $M$ è la dimensione del catalogo e $K$ è la dimensione della scheda. Questo evita l'enumerazione $K!$ .
  - Ottimalità: Il documento dimostra che qualsiasi algoritmo deterministico che calcola propensioni non ordinate esatte per politiche sufficienti per l'insieme deve interrogare ogni sottoinsieme proprio della scheda nel caso peggiore, stabilendo Forward-DP come ottimale in termini di interrogazioni fino a fattori costanti.

Contributi Chiave

Framework Teorico: Una visione unificata a DAG Quoziente per l'OPE che deriva rapporti di verosimiglianza esatti come rapporti di flusso avanti su uno spazio campionario più grezzo.
Innovazione Algoritmica: L'algoritmo Forward-DP, che calcola propensioni esatte di schede non ordinate per registri autoregressivi dipendenti dal contesto e sufficienti per l'insieme in tempo polinomiale nella dimensione del catalogo ed esponenziale nella dimensione della scheda (trattabile a parametro fisso in $K$ ).
Riduzione della Varianza: Una prova formale che la pesatura quoziente rimuove il componente di varianza derivante da ordini di generazione irrilevanti (varianza di disturbo da ordinamento), in particolare quando le ricompense sono invarianti rispetto alla sequenza di generazione della scheda.
Primitive per la Valutazione Fuori Politica delle Schede: L'introduzione di Forward-DP come primitiva che abilita la valutazione basata su propensioni esatte e la selezione del modello per raccomandatori a scheda basati su transformer, colmando il divario per registri dipendenti dal contesto dove le formule fisse di Plackett-Luce non sono applicabili.

Risultati Sperimentali

Gli autori valutano il metodo su benchmark MDP a orizzonte finito e compiti di raccomandazione a schede:

MDP a Orizzonte Finito (Sepsis & ICU-Sepsis):
- L'IS a Flusso Avanti (FF-IS) riduce significativamente l'Errore Quadratico Medio (RMSE) rispetto all'IS standard sulle traiettorie e ad altre baseline (ad esempio, DualDICE, GenDICE).
- Sul benchmark Sepsis, FF-WIS ha ridotto l'RMSE da 0,291 (WIS) a 0,0568.
- Questi guadagni sono stati ottenuti utilizzando solo le traiettorie registrate senza adattare un modello di transizione.
Esperimenti su Schede KuaiRec:
- Efficienza Computazionale: Forward-DP calcola le propensioni esatte con ordini di grandezza più velocemente rispetto all'enumerazione $K!$ . Per $K=8$ , l'enumerazione ha richiesto ~97.108 secondi, mentre Forward-DP ha richiesto ~8,94 secondi. Per $K=12$ , l'enumerazione è non fattibile, mentre Forward-DP si completa in ~13,7 secondi.
- Valutazione Fuori Politica a Valle: Gli stimatori che utilizzano pesi Forward-DP (FF-OIS, FF-DR) hanno costantemente superato le loro controparti pesate sulle traiettorie (OIS, DR) per tutte le dimensioni di scheda ( $K \in \{4, 6, 8\}$ ) in termini di RMSE.
- Selezione del Modello: Nella selezione del modello fuori politica tra raccomandatori transformer autoregressivi, gli stimatori che utilizzano Forward-DP (ad esempio, Tree-DR, DP-OPCB-DR) hanno raggiunto una precisione Top-1 superiore, una correlazione di Spearman più alta e un rimpianto inferiore rispetto ai metodi basati su traiettorie.

Significato e Affermazioni

Il documento afferma che il framework proposto fornisce una Rao-Blackwellizzazione dell'IS per decisione singola. Quozientando l'albero di espansione sotto relazioni di equivalenza sufficienti, il metodo elimina la varianza di disturbo associata a dettagli storici irrilevanti (come l'ordine di generazione nella raccomandazione a schede).

Specificamente per la raccomandazione a schede, il documento afferma che Forward-DP fornisce la primitiva OPE mancante per registri autoregressivi dipendenti dal contesto. A differenza dei metodi precedenti che si basano su assunzioni di punteggio fisso (dove i punteggi degli elementi non cambiano con la scheda parziale) o approssimazioni Monte Carlo, Forward-DP gestisce il caso in cui il softmax dell'elemento successivo dipende dalla scheda parziale, calcolando la propensione congiunta esatta senza enumerazione fattoriale. Questo abilita una valutazione pratica e basata su propensioni esatte e la selezione del modello per i moderni raccomandatori basati su transformer.

Gli autori notano limitazioni, inclusa la necessità dell'assunzione di sufficienza per l'insieme (che potrebbe richiedere la canonizzazione dell'insieme selezionato durante la distribuzione) e la scalabilità esponenziale con la dimensione della scheda $K$ , sebbene sostengano che ciò sia pratico per le dimensioni tipiche delle schede ( $K \le 10$ ) dove $K!$ è intrattabile.