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

Resumo Técnico: DAGs Quociente para Avaliação Off-Policy

Declaração do Problema

A avaliação off-policy (OPE) estima o desempenho de uma política-alvo $\pi$ utilizando dados coletados por uma política de comportamento $\beta$. A amostragem por importância (IS) padrão repondera as trajetórias registradas pelo produto das razões de probabilidade de ação da política-alvo para a de comportamento. No entanto, essa abordagem frequentemente trata detalhes do processo de geração como significativos, mesmo quando o objetivo de avaliação os ignora.

Um caso primário desse problema surge na recomendação de listas (slate), onde geradores modernos frequentemente constroem listas (conjuntos de itens) de forma autoregressiva, expondo probabilidades por passo ao longo de uma ordenação específica. Contudo, a recompensa e os estimadores downstream dependem frequentemente apenas da lista não ordenada. O IS de trajetória padrão atribui uma razão de verossimilhança a um caminho ordenado específico, criando uma "lacuna de propensão conjunta": o registrador expõe uma probabilidade de ordenação, enquanto o estimador requer a probabilidade total da lista não ordenada. Calcular essa propensão não ordenada exata tipicamente requer somar sobre todas as $K!$ ordens de geração, o que é computacionalmente intratável para tamanhos de lista moderados. Além disso, tratar a ordenação como significativa introduz variância de incômodo quando a recompensa é invariante à ordem de geração.

Metodologia

O artigo introduz uma visão de DAG Quociente para abordar esses problemas. A ideia central é quocientar a árvore de simulação de prefixos de histórico por uma relação de equivalência suficiente para o objetivo de avaliação.

1. DAG Quociente e Fluxo Direto:

   • A árvore de simulação é colapsada fundindo prefixos de histórico que são equivalentes para o objetivo de avaliação (por exemplo, prefixos contendo o mesmo conjunto de itens selecionados, independentemente da ordem).
   • Isso forma um Grafo Acíclico Direcionado (DAG) em camadas, onde os nós representam classes de equivalência (estados quociente).
   • Em vez de ponderar pela razão de um único caminho realizado, o método atribui pesos usando a razão de fluxo direto $F_\pi(z)/F_\beta(z)$, onde $F_\mu(z)$ é a massa de probabilidade que atinge o nó $z$ sob a política $\mu$.
   • Essa abordagem generaliza métodos existentes: IS por decisão, IS marginalizado e MIS de abstração conhecida são casos especiais correspondentes a diferentes escolhas de relações de equivalência.

2. Amostragem por Importância de Fluxo Direto (FF-IS):

   • Para OPE de horizonte finito geral, o estimador substitui a razão de prefixo amostrado no IS por Decisão (PDIS) pela razão de verossimilhança quociente.
   • A análise teórica mostra que, para retornos mensuráveis por quociente terminais, essa ponderação remove o desajuste alvo-comportamento "dentro da classe", fornecendo uma expressão exata de lacuna de variância que quantifica a redução na variância de incômodo.

3. Forward-DP para OPE de Listas:

   • O artigo especializa essa estrutura para geração autoregressiva de listas sob uma interface suficiente para conjuntos (Definição 1). Uma política é suficiente para conjuntos se a probabilidade de selecionar o próximo item depender apenas do contexto e do conjunto de itens já selecionados, e não de sua ordem.
   • Sob suficiência para conjuntos, o quociente de permutação corresponde a um DAG de subconjuntos, onde os nós são subconjuntos do catálogo e as arestas adicionam itens não selecionados.
   • Algoritmo Forward-DP: Um algoritmo de programação dinâmica calcula a propensão exata de lista não ordenada $F_\mu(S|x)$ somando sobre subconjuntos em vez de permutações.
     • Complexidade: $O((M + K) \cdot 2^K)$, onde $M$ é o tamanho do catálogo e $K$ é o tamanho da lista. Isso evita a enumeração $K!$.
     • Optimalidade: O artigo prova que qualquer algoritmo determinístico que calcula propensões não ordenadas exatas para políticas suficientes para conjuntos deve consultar cada subconjunto próprio da lista no pior caso, estabelecendo o Forward-DP como ótimo em consultas até fatores constantes.

Contribuições Principais

• Estrutura Teórica: Uma visão unificada de DAG quociente para OPE que deriva razões de verossimilhança exatas como razões de fluxo direto em um espaço amostral mais grosseiro.
• Inovação Algorítmica: O algoritmo Forward-DP, que calcula propensões exatas de lista não ordenada para registradores autoregressivos dependentes de contexto e suficientes para conjuntos em tempo polinomial no tamanho do catálogo e exponencial no tamanho da lista (tratável em parâmetro fixo em $K$).
• Redução de Variância: Uma prova formal de que a ponderação por quociente remove o componente de variância decorrente de ordens de geração irrelevantes (variância de incômodo de ordenação), particularmente quando as recompensas são invariantes à sequência de geração da lista.
• Primitivas para OPE de Listas: A introdução do Forward-DP como uma primitiva que permite avaliação baseada em propensão exata e seleção de modelos para recomendadores de listas baseados em transformadores, fechando a lacuna para registradores dependentes de contexto onde fórmulas fixas de Plackett-Luce não se aplicam.

Resultados Experimentais

Os autores avaliam o método em benchmarks de MDPs de horizonte finito e tarefas de recomendação de listas:

1. MDPs de Horizonte Finito (Sepse & Sepse-UCI):

   • O IS de Fluxo Direto (FF-IS) reduz significativamente o Erro Quadrático Médio (RMSE) comparado ao IS de trajetória padrão e outras linhas de base (por exemplo, DualDICE, GenDICE).
   • No benchmark de Sepse, o FF-WIS reduziu o RMSE de 0,291 (WIS) para 0,0568.
   • Esses ganhos foram alcançados usando apenas trajetórias registradas sem ajustar um modelo de transição.

2. Experimentos de Listas KuaiRec:

   • Eficiência Computacional: O Forward-DP calcula propensões exatas ordens de magnitude mais rápido que a enumeração $K!$. Para $K=8$, a enumeração levou ~97.108 segundos, enquanto o Forward-DP levou ~8,94 segundos. Para $K=12$, a enumeração é inviável, enquanto o Forward-DP completa em ~13,7 segundos.
   • OPE Downstream: Estimadores usando pesos Forward-DP (FF-OIS, FF-DR) superaram consistentemente seus equivalentes ponderados por trajetória (OIS, DR) em todos os tamanhos de lista ($K \in \{4, 6, 8\}$) em termos de RMSE.
   • Seleção de Modelo: Na seleção de modelos off-policy entre recomendadores autoregressivos baseados em transformadores, estimadores utilizando Forward-DP (por exemplo, Tree-DR, DP-OPCB-DR) alcançaram superioridade em precisão Top-1, correlação de Spearman e menor arrependimento comparado a métodos baseados em trajetória.

Significado e Alegações

O artigo alega que a estrutura proposta fornece uma Rao–Blackwellização do IS por decisão. Ao quocientar a árvore de simulação sob relações de equivalência suficientes, o método elimina a variância de incômodo associada a detalhes de histórico irrelevantes (como a ordem de geração na recomendação de listas).

Especificamente para recomendação de listas, o artigo afirma que o Forward-DP fornece a primitiva OPE faltante para registradores autoregressivos dependentes de contexto. Diferentemente de métodos anteriores que dependem de suposições de pontuação fixa (onde as pontuações dos itens não mudam com a lista parcial) ou aproximações de Monte Carlo, o Forward-DP lida com o caso onde o softmax do próximo item depende da lista parcial, calculando a propensão conjunta exata sem enumeração fatorial. Isso permite avaliação prática e exata baseada em propensão e seleção de modelos para recomendadores modernos baseados em transformadores.

Os autores notam limitações, incluindo a exigência da suposição de suficiência para conjuntos (que pode requerer a canonização do conjunto selecionado na implantação) e a escala exponencial com o tamanho da lista $K$, embora argumentem que isso é prático para tamanhos de lista típicos ($K \le 10$) onde $K!$ é intratável.