Resumo Técnico: Q-MMR: Avaliação Off-Policy via Reponderação Recursiva e Correspondência de Momentos

1. Declaração do Problema

O artigo aborda a Avaliação Off-Policy (OPE) em Processos de Decisão de Markov (MDPs) de horizonte finito. O objetivo é estimar o retorno esperado $J(\pi)$ de uma política-alvo $\pi$ utilizando um conjunto de dados coletado a partir de uma política de comportamento $\pi_D$. O cenário envolve Aproximação Funcional Geral (GFA), onde uma classe de funções $\mathcal{F}$ é utilizada para modelar a função-Q da política-alvo, $Q^\pi$.

Os autores identificam duas lacunas teóricas primárias na literatura existente de OPE:

1. Dependência Dimensional: Análises padrão para GFA (por exemplo, Fitted-Q Evaluation, FQE) tipicamente produzem limites de erro que dependem da complexidade estatística da classe de funções (por exemplo, $\log |\mathcal{F}|$ ou números de cobertura). Essa dependência é frequentemente frouxa, particularmente em cenários on-policy onde estimativas de Monte-Carlo são livres de dimensão.
2. Inconsistência com Análises Lineares/Tabulares: Garantias refinadas e livres de dimensão existem para cenários lineares e tabulares (muitas vezes sob realizabilidade apenas), mas esses resultados não se estendem naturalmente para classes de funções gerais. Além disso, análises lineares frequentemente dependem de condições mais fracas (realizabilidade) em comparação com as suposições de completude de Bellman necessárias para análises gerais de GFA.

2. Metodologia: Q-MMR

Os autores propõem o Q-MMR (Reponderação com Correspondência de Momentos baseada em Função-Q), um novo framework algorítmico que aprende um conjunto de pesos escalares, um para cada ponto de dados, de forma indutiva em uma ordem de cima para baixo.

Visão Geral do Algoritmo

Dadas $n$ trajetórias i.i.d. e uma classe de funções $\mathcal{F} = \{\mathcal{F}_h\}_{h=1}^H$:

1. Inicialização: Defina pesos $w^{(i)}_0 \equiv 1$ para todos os pontos de dados $i$ (uma vez que o par estado-ação inicial é fixo).
2. Reponderação Recursiva: Para cada passo de tempo $h = 1$ a $H$, o algoritmo aprende um vetor de pesos $w^{[n]}_h = \{w^{(i)}_h\}_{i=1}^n$ resolvendo um problema de otimização 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|$$
   Este objetivo minimiza a discrepância (via uma Métrica de Probabilidade Integral) entre a distribuição reponderada dos pares estado-ação atuais e a distribuição reponderada do próximo estado sob a política-alvo.
3. Estimação: A estimativa final do retorno é a soma reponderada das recompensas:
   $$\hat{J}(\pi) = \frac{1}{n} \sum_{i=1}^n \sum_{h=1}^H w^{(i)}_h r^{(i)}_h$$

Escolhas de Design Chave

• Pesos Não-Paramétricos: Diferentemente de métodos de Amostragem por Importância Marginalizada (MIS) que aprendem uma função paramétrica para os pesos, o Q-MMR aprende um escalar distinto para cada ponto de dados.
• Princípio do Segundo Momento Mínimo: Como o minimizador da perda de correspondência geralmente não é único, o algoritmo seleciona a solução com o menor segundo momento empírico ($\|w^{[n]}_h\|_{[n]}$) para controlar a variância.
• Indução de Cima para Baixo: Os pesos são computados nível por nível de $h=0$ a $H$, dependendo dos pesos do passo anterior.

3. Contribuições Chave e Resultados Teóricos

A. Garantia de Amostra Finita Livre de Dimensão

A contribuição teórica primária é o Teorema 1, que fornece um limite de amostra finita dependente dos dados para o erro de OPE. Sob a Suposição de Realizabilidade padrão ($Q^\pi \in \mathcal{F}$), com probabilidade de pelo menos $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$$
onde:

• $\hat{L}_h$ é a perda de correspondência empírica alcançada pelo algoritmo.
• $\epsilon^{\text{stat}}_h \propto \| \hat{w}^{[n]}_h \|_{[n]} \sqrt{\frac{\log(1/\delta)}{n}}$.

Significado:

• Livre de Dimensão: O limite não depende explicitamente da complexidade estatística de $\mathcal{F}$ (por exemplo, nenhum termo $\log |\mathcal{F}|$) na ordem principal. Isso é alcançado evitando limites da união sobre a classe de funções e, em vez disso, dependendo de argumentos de concentração específicos para os pesos realizados.
• WYSIWYG (O Que Você Vê é o Que Você Obtém): O limite é diretamente computável a partir dos dados, pois depende da perda de correspondência observada e do segundo momento dos pesos aprendidos.
• Suposições Mais Fracas: A garantia vale sob Realizabilidade apenas, sem exigir a suposição mais forte de completude de Bellman tipicamente necessária para GFA.

B. Conexão com Métodos Existentes

O artigo estabelece que o Q-MMR unifica e recupera resultados conhecidos em casos especiais:

• Cenários Lineares e Tabulares: Quando especializado para classes de funções lineares (com covariância amostral invertível) ou cenários tabulares, o Q-MMR coincide com FQE Linear e FQE Tabular (ou equivalência de certeza baseada em modelo), respectivamente.
• Recuperação de Limites Granulares: Nestes casos especiais, a análise do Q-MMR recupera as taxas livres de dimensão, $O(1/\sqrt{n})$, encontradas na literatura linear/tabular anterior (por exemplo, Duan et al., 2020; Yin e Wang, 2021), fechando a lacuna entre análises gerais e lineares.
• Monte-Carlo e Amostragem por Importância: Em cenários on-policy, definir pesos como 1 recupera o estimador de Monte-Carlo. Com modificações específicas, também pode recuperar a amostragem por importância passo a passo.

C. Insights sobre Cobertura

O artigo fornece uma compreensão teórica mais profunda da cobertura em RL offline:

• Magnitude do Peso como Cobertura: O termo $\|w^{[n]}_h\|_{[n]}$ (e seu contraparte populacional $\|w^\star_h\|_{2, d_D}$) atua como um parâmetro de cobertura empírico.
• Natureza da Cobertura: Através de análise adicional (Seção 4), os autores mostram que a "cobertura" necessária não é meramente a cobertura da ocupação de características da política-alvo $E_{d^\pi}[\phi]$, mas sim a cobertura de um vetor definido por um sistema dinâmico linear específico (análogo a $\psi_h$ em análises lineares).
• Completude de Bellman: Sob completude de Bellman, os pesos populacionais $w^\star_h$ recuperam perfeitamente a distribuição-alvo $d^\pi_h$, e o termo de estabilidade que controla a explosão dos pesos é limitado por 1. Sem completude, a estabilidade depende da norma do operador dos operadores de transição projetados, o que pode levar a um crescimento exponencial dos pesos se o sistema for instável.

4. Significado e Alegações

O artigo alega fornecer um framework teórico unificado que resolve a tensão entre aproximação funcional geral e análises lineares/tabulares em OPE.

• Unificação: Demonstra que as propriedades "livres de dimensão" observadas em cenários lineares/tabulares não são artefatos da linearidade, mas podem ser alcançadas em cenários gerais sob realizabilidade, desde que se utilize uma abordagem de correspondência de momentos com pesos não-paramétricos.
• Novidade da Análise: A análise é descrita como "estritamente simples", evitando limites de união complexos sobre a classe de funções. Ela aproveita a natureza telescópica da equação de Bellman e a estrutura específica do objetivo de correspondência de momentos.
• Implicações Práticas: O limite dependente dos dados oferece um mecanismo embutido para quantificação de incerteza, pois o limite de erro é computável a partir do conjunto de dados sem necessidade de conhecer a complexidade real da classe de funções.

Os autores notam limitações, incluindo a exigência de dados de trajetória i.i.d. (o que falha em coleta adaptativa) e a natureza gananciosa e local da otimização de pesos (que não leva em conta explicitamente efeitos a jusante, embora isso seja uma compensação para evitar problemas de dupla amostragem encontrados em outros métodos MIS).

Em resumo, o Q-MMR oferece uma abordagem teoricamente rigorosa e livre de dimensão para OPE que generaliza as propriedades favoráveis dos métodos lineares para classes de funções gerais, dependendo apenas da realizabilidade.