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

Resumen Técnico: DAGs Cociente para Evaluación Fuera de Política

Enunciado del Problema

La evaluación fuera de política (OPE) estima el rendimiento de una política objetivo $\pi$ utilizando datos recopilados por una política de comportamiento $\beta$. El muestreo por importancia (IS) estándar repondera las trayectorias registradas mediante el producto de los ratios de probabilidad de acción de objetivo a comportamiento. Sin embargo, este enfoque a menudo trata detalles del proceso de generación como significativos incluso cuando el objetivo de evaluación los ignora.

Un caso principal de este problema surge en la recomendación de listas (slates), donde los generadores modernos a menudo construyen listas (conjuntos de elementos) de forma autoregresiva, exponiendo probabilidades por paso a lo largo de un orden específico. Sin embargo, la recompensa y los estimadores aguas abajo a menudo dependen únicamente de la lista desordenada. El IS de trayectoria estándar asigna un ratio de verosimilitud a una ruta ordenada específica, creando una "brecha de propensión conjunta": el registrador expone una probabilidad de ordenamiento, mientras que el estimador requiere la probabilidad total de la lista desordenada. Calcular esta propensión desordenada exacta típicamente requiere sumar sobre todos los $K!$ órdenes de generación, lo cual es computacionalmente intratable para tamaños de listas moderados. Además, tratar el ordenamiento como significativo introduce varianza de molestia cuando la recompensa es invariante al orden de generación.

Metodología

El artículo introduce una visión de DAG-Cociente para abordar estos problemas. La idea central es cocientar el árbol de despliegue de prefijos de historial mediante una relación de equivalencia suficiente para el objetivo de evaluación.

1. DAG Cociente y Flujo Forward:

   • El árbol de despliegue se colapsa fusionando prefijos de historial que son equivalentes para el objetivo de evaluación (por ejemplo, prefijos que contienen el mismo conjunto de elementos seleccionados, independientemente del orden).
   • Esto forma un Grafo Acíclico Dirigido (DAG) en capas donde los nodos representan clases de equivalencia (estados cociente).
   • En lugar de ponderar por el ratio de una única trayectoria realizada, el método asigna pesos utilizando el ratio de flujo forward $F_\pi(z)/F_\beta(z)$, donde $F_\mu(z)$ es la masa de probabilidad que alcanza el nodo $z$ bajo la política $\mu$.
   • Este enfoque generaliza los métodos existentes: el IS por decisión (per-decision), el IS marginalizado y el MIS de abstracción conocida son casos especiales que corresponden a diferentes elecciones de relaciones de equivalencia.

2. Muestreo por Importancia de Flujo Forward (FF-IS):

   • Para OPE de horizonte finito general, el estimador reemplaza el ratio de prefijo muestreado en el IS por decisión (PDIS) con el ratio de verosimilitud cociente.
   • El análisis teórico muestra que, para retornos medibles cociente en el terminal, esta ponderación elimina la discrepancia objetivo-comportamiento "dentro de la clase", proporcionando una expresión exacta de la brecha de varianza que cuantifica la reducción de la varianza de molestia.

3. Forward-DP para OPE de Listas:

   • El artículo especializa este marco a la generación autoregresiva de listas bajo una interfaz suficiente de conjunto (Definición 1). Una política es suficiente de conjunto si la probabilidad de seleccionar el siguiente elemento depende únicamente del contexto y del conjunto de elementos ya seleccionados, no de su orden.
   • Bajo suficiencia de conjunto, el cociente de permutación corresponde a un DAG de subconjuntos, donde los nodos son subconjuntos del catálogo y las aristas añaden elementos no seleccionados.
   • Algoritmo Forward-DP: Un algoritmo de programación dinámica calcula la propensión exacta de lista desordenada $F_\mu(S|x)$ sumando sobre subconjuntos en lugar de permutaciones.
     • Complejidad: $O((M + K) \cdot 2^K)$, donde $M$ es el tamaño del catálogo y $K$ es el tamaño de la lista. Esto evita la enumeración $K!$.
     • Optimalidad: El artículo demuestra que cualquier algoritmo determinista que calcule propensiones desordenadas exactas para políticas suficientes de conjunto debe consultar cada subconjunto propio de la lista en el peor caso, estableciendo a Forward-DP como óptimo en consultas hasta factores constantes.

Contribuciones Clave

• Marco Teórico: Una visión unificada de DAG-cociente para OPE que deriva ratios de verosimilitud exactos como ratios de flujo forward en un espacio muestral más grueso.
• Innovación Algorítmica: El algoritmo Forward-DP, que calcula propensiones exactas de listas desordenadas para registradores autoregresivos dependientes del contexto y suficientes de conjunto en tiempo polinomial en el tamaño del catálogo y exponencial en el tamaño de la lista (tratable en parámetros fijos en $K$).
• Reducción de Varianza: Una prueba formal de que la ponderación cociente elimina el componente de varianza que surge de órdenes de generación irrelevantes (varianza de molestia de ordenamiento), particularmente cuando las recompensas son invariantes a la secuencia de generación de la lista.
• Primitivas para OPE de Listas: La introducción de Forward-DP como una primitiva que permite la evaluación basada en propensión exacta y la selección de modelos para recomendadores de listas basados en transformadores, cerrando la brecha para registradores dependientes del contexto donde no se aplican las fórmulas Plackett-Luce de puntuación fija.

Resultados Experimentales

Los autores evalúan el método en benchmarks de MDP de horizonte finito y tareas de recomendación de listas:

1. MDPs de Horizonte Finito (Sepsis & ICU-Sepsis):

   • El IS de Flujo Forward (FF-IS) reduce significativamente el Error Cuadrático Medio (RMSE) en comparación con el IS de trayectoria estándar y otros puntos de referencia (por ejemplo, DualDICE, GenDICE).
   • En el benchmark de Sepsis, FF-WIS redujo el RMSE de 0.291 (WIS) a 0.0568.
   • Estas mejoras se lograron utilizando únicamente trayectorias registradas sin ajustar un modelo de transición.

2. Experimentos de Listas KuaiRec:

   • Eficiencia Computacional: Forward-DP calcula propensiones exactas órdenes de magnitud más rápido que la enumeración $K!$. Para $K=8$, la enumeración tardó ~97.108 segundos, mientras que Forward-DP tardó ~8.94 segundos. Para $K=12$, la enumeración es inviable, mientras que Forward-DP se completa en ~13.7 segundos.
   • OPE Aguas Abajo: Los estimadores que utilizan pesos Forward-DP (FF-OIS, FF-DR) superaron consistentemente a sus contrapartes ponderadas por trayectoria (OIS, DR) en todos los tamaños de lista ($K \in \{4, 6, 8\}$) en términos de RMSE.
   • Selección de Modelos: En la selección de modelos fuera de política entre recomendadores transformadores autoregresivos, los estimadores que utilizan Forward-DP (por ejemplo, Tree-DR, DP-OPCB-DR) lograron una precisión Top-1 superior, correlación de Spearman y menor arrepentimiento en comparación con los métodos basados en trayectorias.

Significado y Afirmaciones

El artículo afirma que el marco propuesto proporciona una Rao–Blackwellización del IS por decisión. Al cocientar el árbol de despliegue bajo relaciones de equivalencia suficientes, el método elimina la varianza de molestia asociada con detalles de historial irrelevantes (como el orden de generación en la recomendación de listas).

Específicamente para la recomendación de listas, el artículo afirma que Forward-DP suministra la primitiva OPE faltante para registradores autoregresivos dependientes del contexto. A diferencia de los métodos anteriores que se basan en suposiciones de puntuación fija (donde las puntuaciones de los elementos no cambian con la lista parcial) o aproximaciones de Monte Carlo, Forward-DP maneja el caso donde el softmax del siguiente elemento depende de la lista parcial, calculando la propensión conjunta exacta sin enumeración factorial. Esto permite una evaluación y selección de modelos basada en propensión exacta y práctica para recomendadores modernos basados en transformadores.

Los autores señalan limitaciones, incluido el requisito de la asunción de suficiencia de conjunto (que puede requerir la canonización del conjunto seleccionado en la implementación) y la escalabilidad exponencial con el tamaño de la lista $K$, aunque argumentan que esto es práctico para tamaños de lista típicos ($K \le 10$) donde $K!$ es intratable.