Resumo Técnico: Sobre a Complexidade de Aprendizado por Reforço Offline com Aproximação de $Q^\star$ e Cobertura Parcial

Declaração do Problema

Este trabalho investiga os limites teóricos do Aprendizado por Reforço (RL) Offline sob o cenário de $Q^\star$-realizabilidade e cobertura parcial. Neste paradigma, um agente aprende uma política a partir de um conjunto de dados fixo e pré-coletado sem interação adicional com o ambiente. O conjunto de dados é gerado por uma política de comportamento que pode não cobrir todo o espaço estado-ação (cobertura parcial).

A questão central aberta abordada é se a $Q^\star$-realizabilidade (a verdadeira função Q ótima reside dentro de uma classe de funções conhecida) combinada com a completude de Bellman (o operador de Bellman mapeia a classe de funções para um superconjunto) e a cobertura parcial são suficientes para um aprendizado eficiente em amostras. Embora essas condições permitam a construção de um conjunto de confiança contendo a verdadeira $Q^\star$, o artigo questiona se isso é suficiente para garantir uma seleção de política robusta.

Metodologia

1. Limite Inferior de Informação Teórica

Os autores estabelecem primeiro que as condições mencionadas são insuficientes para o aprendizado eficiente em amostras. Eles constroem uma família de Processos de Decisão de Markov (MDPs) onde:

• $Q^\star$-realizabilidade e completude de Bellman são mantidas.
• A cobertura da política ótima é constante ($\Theta(1)$).
• Apesar de a verdadeira função de valor estar bem localizada dentro da classe de funções, o aprendiz não consegue distinguir entre políticas que levam a erros catastróficos e aquelas que são seguras.
• A complexidade de amostra necessária escala como $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$, onde $\Delta$ é o gap de valor. Isso indica que, mesmo com um pequeno gap, a complexidade de amostra pode ser proibitivamente alta, e a dificuldade provém não apenas de estimar $Q^\star$, mas de tomar decisões robustas dentro do conjunto de ambiguidade.

2. Estrutura de Decomposição Decisão-Estimativa

Para abordar a lacuna identificada, os autores introduzem uma estrutura geral de decisão-estimativa inspirada no Coeficiente de Decisão-Estimativa (DEC) de RL online. Eles decompõem a subotimalidade do RL offline em dois componentes modulares:

1. Complexidade de Decisão: A dificuldade de selecionar uma política robusta a partir de um conjunto de confiança de modelos plausíveis.
2. Erro de Estimativa: O erro incorrido na estimativa da função de valor ou dos parâmetros do modelo a partir dos dados offline.

Eles definem o Coeficiente de Decisão-Estimativa Robusto Offline ($Ordec$):
$$Ordec\text{-}OD_\gamma(F_{conf}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{conf}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in F_{conf}} D_\pi(f \| M) \right]$$
Onde:

• $F_{conf}$ é o conjunto de confiança das funções $Q^\star$ plausíveis.
• $\mathcal{M}_{conf}$ é o conjunto induzido de modelos plausíveis.
• $\rho$ é uma distribuição sobre políticas.
• $D_\pi(f \| M)$ é uma medida de discrepância (ex: erro de Bellman) entre uma função e um modelo, avaliada sob a política ótima do candidato modelo $\pi_M$ (ao contrário do DEC online que utiliza a política do aprendiz).

A estrutura propõe um algoritmo (E2D.OR) que produz uma política de mistura $\hat{\pi}$ satisfazendo:
$$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq Ordec + \text{Erro de Estimativa}$$

Contribuições Principais

1. Resultado Negativo sobre Suficiência

O artigo fornece um limite inferior de informação teórica provando que $Q^\star$-realizabilidade, cobertura parcial e completude de Bellman não são suficientes para o aprendizado de RL offline eficiente em amostras. Isso destaca que o desafio central nos cenários de cobertura parcial é o problema de "decisão" — distinguir políticas seguras de inseguras dentro do conjunto de confiança — e não apenas o problema de "estimativa".

2. Estrutura Unificada e Limites Melhorados

A estrutura $Ordec$ proposta unifica e melhora resultados existentes:

• Cenário de Value-Gap: Recupera os resultados de Chen e Jiang (2022), mas remove a necessidade de conhecer o valor do gap ou realizar interações online adicionais. O limite adapta-se automaticamente ao gap real.
• Cenário Regularizado: Melhora o limite de complexidade de amostra para o Soft Q-learning sob cobertura parcial de $\epsilon^{-4}$ (Uehara et al., 2023) para $\epsilon^{-2}$. Isso é alcançado via um novo lema de diferença de performance de segunda ordem para MDPs regularizados.
• Fronteira de Decisão Curva: Introduz um novo cenário aprendível baseado na curvatura da fronteira de decisão em espaços de ação contínuos, abordando preocupações práticas sobre a estrita suposição de value-gap.

3. Novos Regimes Aprendíveis para Erro de Estimativa

O artigo caracteriza o papel das suposições estruturais no controle do termo de erro de estimativa:

• Completude de Bellman: Fornece a primeira análise de complexidade de amostra para o Conservative Q-Learning (CQL) sob aproximação de função geral (previamente limitada a casos tabulares).
• Baixo Rank de Bellman: Investiga a aprendibilidade offline de MDPs de baixo rank de Bellman (um cenário canônico de RL online). Os autores mostram que, sob suposições de dados padrão, o baixo rank de Bellman é insuficiente para o aprendizado offline. Eles introduzem duas condições necessárias para a aprendibilidade neste regime:
  1. Amostragem Dupla de Política: Os dados devem ser gerados amostrando uma política e, em seguida, duas transições independentes.
  2. Cobertura de Características de Política: Uma condição de cobertura específica no espaço de características das políticas.
     Relaxar qualquer uma dessas condições quebra a garantia de complexidade de amostra polinomial.

Resumo de Resultados

• Limite Inferior: Demonstrado que $Q^\star$-realizabilidade + completude de Bellman + cobertura parcial $\nRightarrow$ aprendizado de RL offline eficiente em amostras.
• Limite Superior: Estabelecido um limite geral de subotimalidade decomposto em $Ordec$ (complexidade de decisão) e erro de estimativa.
• Limites Específicos:
  • Não Regularizado (Value Gap): $\tilde{O}(\frac{H^2}{\gamma \Delta^2} + \gamma \frac{C_{\pi^\star}}{n})$. Adapta-se a gaps desconhecidos.
  • Regularizado: $\tilde{O}(\sqrt{\frac{C_{\pi^\star}}{n}})$, resultando em uma complexidade de amostra de $\epsilon^{-2}$.
  • CQL: Primeira garantia de aproximação de função geral para CQL sob cobertura parcial.
  • Baixo Rank de Bellman: Provada a impossibilidade sob suposições padrão; identificou a amostragem dupla de política e a cobertura de características de política como necessárias para a aprendibilidade.

Significância e Alegações

O artigo alega fornecer uma compreensão mais abrangente do potencial e das limitações do RL offline sob aproximação de $Q^\star$ e cobertura parcial. Sua significância reside em:

1. Esclarecer a Fonte da Dificuldade: Desloca o foco teórico dos erros de estimativa puramente para a complexidade de decisão inerente aos cenários de cobertura parcial, mostrando que mesmo com uma estimativa perfeita, a tomada de decisão robusta pode ser impossível sem suposições estruturais adicionais.
2. Unificação: Oferece uma estrutura modular que recupera, melhora e estende resultados anteriores (Chen e Jiang, 2022; Uehara et al., 2023) ao separar as complexidades de decisão e de estimativa.
3. Relevância Prática: Ao analisar o CQL sob aproximação de função geral e identificar os requisitos estruturais específicos para problemas de baixo rank de Bellman, o trabalho une algoritmos práticos e garantias teóricas em cenários anteriormente considerados intratáveis ou mal compreendidos.
4. Novidade em Cenários: Estabelece as primeiras condições de aprendibilidade para MDPs de baixo rank de Bellman no RL offline e fornece o primeiro limite de $\epsilon^{-2}$ para o soft Q-learning regularizado sob cobertura parcial.

Os autores observam que, embora a estrutura seja teoricamente sólida, resolver exatamente o algoritmo minimax é computacionalmente difícil, embora possa ser aproximado via métodos de ator-crítico. O trabalho serve primariamente para identificar novos regimes aprendíveis e caracterizar as condições estruturais necessárias para eles.