Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

1. Formulação do Problema

O Aprendizado por Reforço (RL) em ambientes de grande escala ou contínuos enfrenta gargalos computacionais severos. Algoritmos tradicionais de minimização de arrependimento baseados em modelo exigem chamadas frequentes a dois tipos de "oráculos":

1. Oráculo de Estimação Estatística: Utilizado para estimar o modelo do ambiente (dinâmicas de transição e recompensas) a partir dos dados.
2. Oráculo de Otimização de Política (Planejamento): Utilizado para calcular a política ótima dado o modelo estimado.

As abordagens existentes sofrem com duas limitações principais:

• Alta Frequência de Chamadas ao Oráculo: A maioria dos algoritmos requer $O(T)$ chamadas a esses oráculos, onde $T$ é o horizonte de tempo, tornando-os computacionalmente proibitivos para $T$ grande.
• Dependência do Tamanho do Espaço de Estados/Ações: A complexidade do planejamento frequentemente escala com a cardinalidade do espaço de estados ($S$) e do espaço de ações ($A$). Isso torna os métodos existentes intratáveis para ambientes com espaços de estados/ações grandes, infinitos ou contínuos (por exemplo, MDPs lineares com estados infinitos).

Embora trabalhos recentes (por exemplo, Qian et al., 2024) tenham alcançado "eficiência de oráculo offline" (poucas chamadas ao oráculo de estimação) para MDPs tabulares, a complexidade de seu oráculo de planejamento ainda escalava com $S$ e $A$ (especificamente $O(HSA \log \log T)$). O artigo aborda a questão em aberto: Podemos projetar um algoritmo que seja eficiente tanto no oráculo de estimação quanto no de planejamento, com complexidade independente de $S$ e $A$, e aplicável a espaços de estados/ações infinitos?

2. Metodologia

Os autores propõem DOERL (Aprendizado por Reforço com Eficiência Dupla de Oráculo), uma nova estrutura algorítmica baseada em regularização de barreira logarítmica e logaritmo do determinante. A inovação central reside na forma como o algoritmo gerencia o compromisso entre exploração e exploração enquanto minimiza as chamadas aos oráculos.

Componentes Técnicos Chave:

1. Aprendizado Baseado em Épocas com Atualizações Truncadas:

   • O processo de interação é dividido em $N$ épocas. Dentro de cada época, o agente executa uma política fixa por um segmento de tempo.
   • Crucialmente, o oráculo de estimação offline é chamado apenas no final de cada época (ou segmento), agregando dados para atualizar o modelo. Isso reduz o número de chamadas de estimação para $O(N)$.
   • O oráculo de planejamento também é invocado apenas no início dos segmentos, reduzindo significativamente a frequência de planejamento.

2. Medidas de Ocupação Confiáveis:

   • Para evitar explorar transições raras ou pouco confiáveis de estado-ação, o algoritmo define um "conjunto de transições confiáveis" $\mathcal{T}_m^h$.
   • As transições são consideradas "confiáveis" apenas se a medida de ocupação estimada multiplicada pela probabilidade de transição exceder um limiar ($1/\zeta_m$).
   • Este conceito, adaptado de Qian et al. (2024), é modificado para ser computável sem iterar sobre todo o espaço de políticas, o que é crítico para a eficiência.

3. Regularização para Exploração:

   • Para MDPs Tabulares: O algoritmo utiliza Regularização de Barreira Logarítmica. O objetivo de otimização da política inclui um termo $\sum \log(\text{ocupação confiável} + \beta)$. Isso incentiva o agente a visitar pares estado-ação que são "confiáveis" mas têm baixa probabilidade, garantindo exploração suficiente sem a necessidade de enumerar todos os estados.
   • Para MDPs Lineares (Espaços Infinitos): O algoritmo introduz Regularização de Logaritmo do Determinante. Em vez de somar sobre estados discretos, ele maximiza o logaritmo do determinante da matriz de covariância de características ponderada pela medida de ocupação confiável: $\log \det(\mathbf{K} + \beta \mathbf{I})$. Isso promove a exploração do espaço de características, garantindo que o agente colete dados diversos para estimar os coeficientes lineares com precisão.

4. Estratégia de Agregação:

   • O algoritmo agrega estimativas por camada (kernels de transição e recompensas) do oráculo offline em um único modelo global para a próxima época, em vez de atualizar o modelo a cada passo individual.

3. Contribuições Principais

1. Eficiência de Oráculo Duplo:

   • O artigo apresenta o primeiro algoritmo que alcança tanto eficiência no oráculo de estimação estatística quanto no oráculo de otimização de política.
   • Complexidade de Chamadas ao Oráculo: O algoritmo requer apenas $O(H \log \log T)$ chamadas a ambos os oráculos quando $T$ é conhecido (e $O(H \log T)$ quando desconhecido).
   • Independência das Dimensões: Crucialmente, essa complexidade é estritamente independente do tamanho do espaço de estados ($S$) e do tamanho do espaço de ações ($A$).

2. Extensão para Espaços Infinitos:

   • A estrutura é generalizada para MDPs Lineares com espaços de estados infinitos e espaços de ações arbitrários.
   • É o primeiro algoritmo eficiente em oráculo offline a alcançar arrependimento sublinear neste cenário, superando a "maldição da dimensionalidade" que aflige métodos tabulares.

3. Limites de Arrependimento Ótimos:

   • MDPs Tabulares: Alcança o limite ótimo de arrependimento $O(\sqrt{T})$.
   • MDPs Lineares: Alcança um limite de arrependimento sublinear de $O(T^{4/5})$ (com fatores logarítmicos), o que é significativo para configurações de dimensão infinita sob as restrições de oráculo dadas.

4. Resultados

Garantias teóricas são estabelecidas para ambos os cenários finito (tabular) e infinito (linear):

• MDPs Tabulares:

  • Arrependimento: $O(\sqrt{T})$ (ótimo).
  • Chamadas ao Oráculo: $O(H \log \log T)$ para ambos estimação e planejamento.
  • Comparação: Melhora significativamente Qian et al. (2024), que exigia $O(HSA \log \log T)$ chamadas de planejamento.

• MDPs Lineares (Estado/Ação Infinitos):

  • Arrependimento: $O(T^{4/5} \cdot \text{polylog}(T))$.
  • Chamadas ao Oráculo: $O(H \log \log T)$ para ambos os oráculos.
  • Significado: Antes deste trabalho, não existia nenhum algoritmo capaz de resolver MDPs de estado infinito com chamadas de oráculo de tão baixa frequência enquanto mantinha arrependimento sublinear.

5. Significado e Impacto

• Ponte entre Teoria e Prática: Ao desacoplar a complexidade computacional do tamanho dos espaços de estados/ações, este trabalho torna o RL baseado em modelo teoricamente viável para aplicações complexas do mundo real, como robótica e sistemas autônomos, onde $S$ e $A$ são efetivamente infinitos.
• Eficiência em Sistemas de Grande Escala: A redução nas chamadas ao oráculo de $O(T)$ ou $O(SA)$ para $O(\log \log T)$ representa uma redução massiva na sobrecarga computacional, permitindo o uso de estimadores offline caros (como redes neurais profundas) em loops de RL onde anteriormente eram excessivamente custosos.
• Novo Paradigma para Exploração: A integração de regularização de barreira logarítmica e logaritmo do determinante com medidas "confiáveis" fornece um mecanismo teórico robusto para exploração que escala graciosamente com a dimensionalidade, oferecendo um roteiro para futuros algoritmos em controle de alta dimensão.

Em resumo, este artigo avança fundamentalmente o estado da arte em Aprendizado por Reforço ao provar que arrependimento ótimo pode ser alcançado com sobrecarga computacional mínima (independente do tamanho do ambiente) através de uma combinação inovadora de aprendizado baseado em épocas, medidas confiáveis e regularização baseada em determinante.