Resumo Técnico: Avaliação de Razão de Ocupação Ajustada sem Completude de Bellman

Declaração do Problema

A avaliação de política offline (OPE) visa estimar o desempenho de uma política alvo $\pi$ utilizando dados coletados de uma política de comportamento. Um desafio central é corrigir o deslocamento de distribuição entre a distribuição dos dados offline $\nu$ e a medida de ocupação de estado-ação descontada da política alvo $d_{\pi,\gamma}$.

Os métodos existentes geralmente se dividem em duas categorias:

1. Métodos baseados em valor (ex: Avaliação Q-Ajustada ou FQE): Estes estimam a função de valor iterativamente regredindo alvos de Bellman sobre uma classe de funções. No entanto, as garantias teóricas para FQE geralmente exigem completude de Bellman (a imagem de Bellman de qualquer função na classe deve estar contida na classe) ou estabilidade do operador de Bellman projetado. Sem isso, a composição do operador de Bellman e a projeção (sob a distribuição offline) pode não ser contrativa, levando à instabilidade.
2. Métodos baseados em razão (ex: Primal-Dual, Minimax): Estes estimam a razão de ocupação $\omega_{\pi,\gamma} = d d_{\pi,\gamma} / d\nu$ impondo momentos de equilíbrio sobre uma classe de críticos. Essas abordagens normalmente exigem realizabilidade dual ou completude de Bellman adjacente (a classe do crítico deve ser rica o suficiente para detectar resíduos gerados pela classe da razão), deslocando o ônus da aproximação para um par acoplado de classes.

O artigo aborda a lacuna onde nem a completude da função de valor nem a completude dual ocorrem, mas a própria razão de ocupação alvo é bem aproximada por uma classe de hipóteses.

Metodologia: Avaliação de Razão de Ocupação Ajustada (FORE)

Os autores propõem a Avaliação de Razão de Ocupação Ajustada (FORE), um método de ponto fixo ajustado que estima a razão de ocupação descontada através de uma ** recursão de Bellman adjacente**.

Mecanismo Central

1. Identificação de Bellman Adjacente: A razão de ocupação descontada satisfaz a equação de ponto fixo $\omega_{\pi,\gamma} = B^\pi_\gamma \omega_{\pi,\gamma}$, onde $B^\pi_\gamma$ é o operador de Bellman adjacente. Diferente dos operadores de Bellman padrão, $B^\pi_\gamma$ atua sobre densidades.
2. Iteração Projetada por KL: Em vez de resolver um problema de ponto de sela minimax, o FORE itera o mapa de Bellman adjacente. Em cada etapa $k$, dada uma estimativa $\omega^{(k)}$, o método calcula a próxima estimativa $\omega^{(k+1)}$ projetando a imagem de Bellman exata $B^\pi_\gamma \omega^{(k)}$ sobre uma classe de hipóteses $\mathcal{W}$ (de log-razões normalizadas) usando a divergência de Kullback–Leibler (KL):
   $$\omega^{(k+1)} = \Pi^{\text{KL}}_{\mathcal{W}} (B^\pi_\gamma \omega^{(k)})$$
3. Objetivo de Nível Único: Crucialmente, a projeção KL da imagem de Bellman adjacente pode ser computada via um objetivo de razão de densidade de nível único (Lema 3.2). Isso evita a necessidade de uma classe de crítico separada. O objetivo envolve:
   • O momento do estado inicial $E_{d_0}[h(X)]$.
   • O momento de transição de um passo $E_\nu[\omega(X)h(X^+)]$.
   • Um termo de normalização de log-partição.
     Isso permite a implementação usando aprendizes supervisionados padrão (ex: árvores de decisão baseadas em gradiente, redes neurais).

Fundamentação Teórica

A estabilidade do FORE baseia-se na geometria da divergência KL:

• Contração KL: O operador de Bellman adjacente não projetado é uma contração em entropia relativa (divergência KL) com fator $\gamma$ (Lema 3.1).
• Projeção Compatível: Como a projeção é realizada na mesma geometria KL, o operador projetado herda essa propriedade de contração.
• Condição de Aproximação: O requisito central é meramente a realizabilidade (ou aproximação) da razão de ocupação descontada alvo pela classe de hipóteses. O método não exige que a classe seja fechada sob o operador de Bellman adjacente (ou seja, não é necessária a completude de Bellman adjacente).

Lidar com Cobertura Limitada

Quando a política alvo visita pares estado-ação não suportados pelos dados offline (violando a continuidade absoluta), a razão total não é identificável. Os autores introduzem o FORE com Parada de Cobertura (Coverage-Stopped FORE):

• Ele visa a ocupação descontada acumulada antes do primeiro par estado-ação não coberto.
• Emprega um classificador de cobertura aprendido para identificar e descartar o componente singular da atualização de Bellman.
• Utiliza clipping (recorte) para regularizar a estimativa em regiões de cobertura fraca.
• A estimativa de valor resultante serve como um limite inferior conservador para o verdadeiro valor da política alvo para recompensas não negativas.

Principais Contribuições

1. Formulação Algorítmica: Caracterização da razão de ocupação descontada como o ponto fixo único de uma recursão de Bellman adjacente e a introdução do FORE, que estima isso através de objetivos repetidos de razão de densidade KL de nível único.
2. Teoria Populacional: Desenvolvimento de uma teoria de aproximação baseada diretamente na realizabilidade da razão de ocupação. O operador de Bellman adjacente projetado por KL contrai em entropia relativa em direção à razão verdadeira, até um erro de aproximação determinado pela classe de log-razão, sem exigir completude de Bellman adjacente.
3. Garantias de Amostra Finita: Prova de limites de regret de amostra finita para a recursão ajustada empírica. O erro de KL generalizado decompõe-se em um termo de inicialização que decai geometricamente, um termo de aproximação KL populacional e um termo estatístico governado pela complexidade de Rademacher local das classes de log-razão e de multiplicadores induzidos.
4. Aplicações de Avaliação de Política:
   • Reponderação de Recompensa: Estimativa direta de valor usando a razão ajustada.
   • Estimativa Doubly Robust: Um limite de erro em forma de produto combinando a razão ajustada com uma função Q ajustada.
   • FQE com Peso FORE: Uso da razão ajustada como peso de projeção no FQE para estabilizar a recursão de Bellman sem as suposições de completude de Bellman na classe de valor.
5. Extensão de Parada de Cobertura: Uma extensão para cenários de cobertura limitada que produz limites inferiores conservadores e diagnostica a cobertura efetiva.

Resultados

Resultados Teóricos

• Convergência: Sob realizabilidade da razão de ocupação, a recursão populacional converge geometricamente em divergência KL.
• Limites de Erro: O limite de erro de amostra finita escala com o erro de aproximação da classe de razão e a complexidade estatística (raio crítico) da classe de hipóteses. Notavelmente, o termo de erro de aproximação escala como $\sqrt{\epsilon_{KL}/(1-\gamma)}$, o que é mais favorável do que a escala $(1-\gamma)^{-1}$ frequentemente vista em limites de função de valor sob completude de Bellman aproximada.
• Estabilidade: O método estabiliza o FQE quando usado como mecanismo de ponderação, mesmo que a classe da função de valor não seja completa de Bellman.

Experimentos Numéricos

O artigo valida a teoria através de três experimentos:

1. MRP Finito Estilo Baird: Demonstra que o FQE linear pode ser instável (expansivo) sob a distribuição de dados offline, enquanto o FORE permanece estável e converge para a razão verdadeira. O FQE reponderado pelo FORE também estabiliza a estimativa de valor.
2. Avaliação de Política Gaussiana Linear: Em um cenário contínuo onde a classe de valor não é completa de Bellman, o FQE linear falha (multiplicador > 1). O FORE converge rapidamente (multiplicador $\approx 0,086$), e o FQE reponderado pelo FORE restaura a contração. O FORE alcança erro de razão de densidade menor e RMSE de valor competitivo em comparação com métodos minimax (MWL, DualDICE).
3. FORE com Parada de Cobertura: Sob cobertura insuficiente de dados, o FORE padrão e o clipping pós-hoc falham em visar a medida de subprobabilidade correta. O FORE com parada de cobertura recupera com sucesso a razão de ocupação de parada de cobertura e fornece limites inferiores precisos sobre o valor, superando as bases tanto em erro de razão quanto de valor.

Significância e Alegações

O artigo afirma identificar a realizabilidade da razão de ocupação descontada como uma condição suficiente para a avaliação de política offline, removendo a necessidade de:

• Completude de Bellman de uma classe de valor.
• Completude de Bellman adjacente de uma classe de razão.
• Completude dual de uma classe de crítico.

A significância reside em deslocar o ônus da aproximação de condições de fechamento complexas (que são frequentemente restritivas e difíceis de verificar) para a representabilidade direta do deslocamento de distribuição. Ao alavancar a geometria KL, o FORE alcança estabilidade e garantias de convergência que são estruturalmente distintas e frequentemente mais fracas do que as suposições exigidas pelos métodos de FQE ou minimax. Os autores posicionam isso como uma alternativa fundamental aos métodos baseados em valor e de razão minimax, particularmente em configurações onde a razão de ocupação é bem aproximada, mas as classes de função de valor ou de crítico carecem das propriedades de completude necessárias.

O artigo mantém-se modesto quanto às limitações: a recuperação da razão total ainda exige cobertura (continuidade absoluta) e, em configurações de alta dimensão ou quase determinísticas, estimar a razão pode ser tão difícil quanto estimar a função de valor. A extensão de parada de cobertura aborda isso ao mudar o estimando para um limite inferior conservador em vez de extrapolar para regiões não suportadas.