Resumo Técnico: Limites Melhorados para Exploração Agnóstica a Recompensas e Exploração Livre de Recompensas

Formulação do Problema

Este artigo aborda o desafio da exploração em Processos de Decisão de Markov (MDPs) tabulares episódicos de horizonte finito, onde o agente opera sem observar sinais de recompensa externos durante a fase de coleta de dados. Os autores estudam dois frameworks específicos:

1. Exploração Livre de Recompensas (RFE): O agente explora um ambiente desconhecido sem qualquer sinal de recompensa. O objetivo é produzir uma política que seja $\epsilon$-ótima para qualquer função de recompensa arbitrária revelada após a fase de exploração.
2. Exploração Agnóstica a Recompensas (RAE): Similar ao RFE, mas a função de recompensa é extraída de uma classe finita pequena e pré-definida (tamanho polinomial em $|S|, |A|, H$). O objetivo é encontrar uma política $\epsilon$-ótica para a recompensa específica extraída dessa classe.

A dificuldade central reside em coletar dados suficientes para estimar com precisão a dinâmica de transição estado-ação sem a orientação de um sinal de recompensa, garantindo que o modelo resultante suporte o cálculo de políticas quase ótimas para tarefas a jusante.

Metodologia

A abordagem proposta substitui a dependência em múltiplos sub-rotinas independentes sem arrependimento encontradas em trabalhos anteriores por um procedimento unificado de aprendizado online. O algoritmo (Algoritmo 1) opera em três etapas:

1. Criação da Política de Exploração

Em vez de executar múltiplos algoritmos estocásticos sem arrependimento (como feito por Jin et al., 2020b; Li et al., 2024b), os autores empregam uma única execução de um algoritmo de Descida Espelhada Online (OMD) sobre uma sequência de funções de recompensa auxiliares cuidadosamente construídas.

• Mecanismo: O algoritmo gera uma sequência de recompensas $\{\lambda_t\}$ projetada para direcionar o agente para pares estado-ação menos visitados. A recompensa no passo $t$ é inversamente proporcional à contagem de visitação do par estado-ação (mais uma constante $c$ para lidar com visitas de baixa probabilidade).
• Perspectiva de Otimização: Este processo é enquadrado como a solução aproximada de um problema de otimização convexa sobre o espaço de medidas de ocupação válidas. Especificamente, visa minimizar o objetivo de barreira logarítmica negativa $f(\mu) = -\sum \log \mu_h(s,a)$.
• Significado: Ao utilizar um único algoritmo de MDP online (adaptado de Rosenberg & Mansour, 2019) em vez de iterações no estilo Frank-Wolfe, o método reduz significativamente os termos de complexidade de amostra de baixa ordem. Ele reutiliza amostras ao longo do processo de aprendizado para construir uma "cobertura de políticas" que garante uma exploração quase uniforme de triplas estado-ação significativas.

2. Estimativa de Dinâmica

Usando a política de exploração gerada na Etapa 1, o agente coleta $N$ trajetórias. Para lidar com as correlações temporais inerentes aos dados de trajetória, os autores utilizam um framework de subamostragem dupla (Li et al., 2024a). Esta técnica divide o conjunto de dados em um conjunto principal e um conjunto auxiliar para induzir independência estatística, permitindo a construção de um kernel de transição empírico $\hat{P}$ com garantias rigorosas de concentração.

3. Estimativa de Política

Uma vez que a função de recompensa verdadeira é revelada, o algoritmo calcula uma política $\epsilon$-ótica usando pessimismo diante da incerteza.

• O algoritmo constrói um MDP empírico usando $\hat{P}$ e a recompensa revelada.
• Ele aplica um termo de penalidade $b_h(s,a)$ derivado de desigualdades de concentração estilo Bernstein às estimativas de valor-Q. Esta penalidade escala com a variância empírica e as contagens de visitação, desencorajando a política de visitar pares estado-ação mal cobertos.
• A política final $\hat{\pi}$ é a política ótima para este MDP empírico pessimista.

Contribuições e Resultados Chave

1. Complexidade de Amostra Melhorada para Exploração Agnóstica a Recompensas (RAE)

O artigo apresenta um novo algoritmo que alcança a complexidade de amostra de alta ordem ótima para RAE, igualando o limite inferior para Identificação da Melhor Política (BPI).

• Resultado: A complexidade de amostra é $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$.
• Melhoria: Embora trabalhos anteriores (Li et al., 2024b) tenham alcançado o termo de alta ordem ótimo $O(|S||A|H^3/\epsilon^2)$, seu limite sofreu com um termo de baixa ordem de alta complexidade que tornava o limite ótimo apenas para $\epsilon$ extremamente pequeno. O método proposto reduz significativamente este termo de baixa ordem, tornando o algoritmo aplicável a uma faixa mais ampla de parâmetros de precisão.

2. Limite Inferior Apertado para Exploração Livre de Recompensas (RFE)

Os autores provam um limite inferior apertado para a complexidade de amostra de RFE em MDPs não homogêneos no tempo.

• Resultado: Qualquer algoritmo RFE requer $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ trajetórias em expectativa.
• Significado: Isso resolve uma conjectura de Li et al. (2024b) de que o limite inferior minimax para RFE não homogênea no tempo é um fator de $H$ maior do que o caso homogêneo no tempo. Isso estabelece que os limites superiores existentes (por exemplo, M´enard et al., 2021) são ótimos até fatores logarítmicos.

3. Framework Teórico

O artigo fornece uma perspectiva técnica novel ao vincular a criação da política de exploração à minimização de um objetivo de barreira logarítmica sobre medidas de ocupação. Ele demonstra que uma abordagem de descida espelhada online pode aproximar essa solução de forma mais eficiente do que métodos anteriores baseados em Frank-Wolfe, reduzindo assim a dependência das dimensões do problema nos termos de baixa ordem.

Significado e Alegações

O artigo alega avançar a compreensão teórica da exploração sem recompensas ao:

1. Desvendar Exploração e Exploração: Clarifica a complexidade de amostra intrínseca da exploração em MDPs de horizonte finito.
2. Praticidade do RAE: Ao relaxar os requisitos restritivos sobre o parâmetro de precisão $\epsilon$ encontrados em limites ótimos anteriores, o método proposto torna a exploração agnóstica a recompensas prática mesmo em regimes de precisão moderada.
3. Completude da Caracterização: A combinação do novo limite superior para RAE e do limite inferior apertado para RFE fornece uma caracterização minimax completa da complexidade de amostra para esses problemas (até fatores logarítmicos).

Os autores afirmam explicitamente que seu foco é a análise teórica de MDPs tabulares de horizonte finito, deixando MDPs não tabulares e resultados empíricos como caminhos para trabalhos futuros. Eles não alegam aplicação imediata a domínios reais específicos como robótica ou medicina, mas sim enfatizam as melhorias teóricas fundamentais que permitem tais aplicações.