Resumo Técnico: Emergência da Exploração em Aprendizado por Reforço de Gradiente de Política via Tentativas (Retrying)

1. Definição do Problema

No Aprendizado por Reforço (RL), a exploração é tipicamente impulsionada pela adição de bônus explícitos (ex: entropia, curiosidade ou bônus baseados em contagem) ao sinal de recompensa ou pelo emprego de métodos de amostragem posterior. Os autores postulam um mecanismo distinto: a exploração deve emergir naturalmente da necessidade do agente de maximizar recompensas sob incerteza através de tentativas (retrying).

A intuição central é que, em ambientes onde um agente pode repetir ações ou encontrar estados semelhantes, uma política gulosa (greedy) é subótima se ignorar o potencial de retornos mais altos em tentativas subsequentes. Sem a oportunidade de tentar novamente, a escolha racional é a ação que atualmente se acredita gerar a maior recompensa. Sob incerteza, uma política que se protege contra a incerteza explorando ações alternativas pode alcançar um máximo esperado de retorno superior ao longo de múltiplas tentativas. Métodos existentes frequentemente exigem modelos auxiliares complexos para estimar a incerteza ou construir bônus; este artigo questiona se a exploração pode ser induzida puramente pela otimização de um objetivo baseado em recompensa que formalize o valor de tentar novamente.

2. Metodologia

2.1 O Objetivo ReMax

Os autores propõem o ReMax (Retry Maximum), um objetivo que avalia uma política $\pi$ pelo retorno máximo esperado sobre $M$ amostras independentes (tentativas), em vez do retorno esperado de uma única tentativa.

Em um cenário de bandit com valores de ação $\mu$ e uma distribuição sobre esses valores $\Pi$ (representando a incerteza epistêmica), o objetivo ReMax é definido como:
$$J^M_{\text{ReMax}}(\pi) := \mathbb{E}_{\mu \sim \Pi} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} \mu_{A_m} \mid \mu \right] \right]$$
onde $A^{[M]}$ representa $M$ sorteios independentes da política $\pi$.

• Mecanismo: Ao maximizar o máximo esperado de $M$ sorteios, o objetivo incentiva a política a atribuir massa de probabilidade a ações que podem gerar altas recompensas, mesmo que não sejam o máximo médio estimado atualmente. Isso induz a estocasticidade (exploração) como uma propriedade emergente para se proteger contra a incerteza.
• Caso Determinístico: Mesmo com recompensas fixas, o ReMax remodela a geometria do objetivo. Aumentar o parâmetro de tentativa $M$ achata o gradiente próximo ao ótimo, retardando a convergência e sustentando a exploração, enquanto valores menores de $M$ aceleram as atualizações.

2.2 Extensão para RL (MDPs)

Estender o ReMax para Processos de Decisão de Markov (MDPs) apresenta desafios:

1. Unidade de Incerteza: A incerteza em RL abrange todo o ambiente (recompensas e transições).
2. Viabilidade de Tentativas: Resetar fisicamente um ambiente para tentar várias ações a partir do mesmo estado é frequentemente inviável.

Para abordar isso, os autores definem o objetivo ReMax usando uma função Q $Q^\pi_M(s, a)$, que representa o retorno episódico esperado. O objetivo é formulado como o máximo esperado sobre $M$ sorteios de valores Q no estado $s$:
$$J^M_{\text{ReMax}}(\pi, s, Q) := \mathbb{E}_{Q \sim \mathcal{Q}} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} Q(s, A_m) \right] \right]$$
Aqui, a distribuição $\mathcal{Q}$ captura a incerteza sobre os valores Q (seja via modelagem explícita, como ensembles, ou implicitamente via não-estacionaridade dos críticos profundos).

2.3 Formulação do Gradiente de Política

Para otimizar o ReMax de forma eficiente, os autores derivam um novo estimador de gradiente de política (PG) que é computável a partir de retornos de trajetórias únicas.

• Falha da Abordagem Ingênua: Uma aplicação direta do teorema do gradiente de política exige observar retornos para todas as $M$ ações amostradas simultaneamente, o que é inviável em RL episódico.
• Reformulação de Melhoria Esperada (EI): Os autores introduzem um baseline baseado na "Melhoria Esperada" (emprestada da otimização bayesiana). Eles decompõem o operador de máximo em um termo específico da ação e um baseline que representa o máximo dos outros $M-1$ sorteios ($W_{-m}$).
• Solução de Forma Fechada: Ao ordenar os valores Q, eles derivam uma expressão de forma fechada para o termo de melhoria esperada. Isso permite que o gradiente seja estimado usando um retorno de trajetória única $R(s, a)$ e as estimativas atuais de Q.
• Parâmetro Contínuo $m$: O número inteiro de tentativas $M$ é generalizado para um parâmetro contínuo real $m > 0$. Isso permite o controle refinado do equilíbrio entre exploração e explotação. O termo $(1 - C_j)^{M-1}$ na solução de forma fechada é substituído por $(1 - C_j)^{m-1}$.

2.4 Algoritmo RePPO

Os autores instanciam o ReMax dentro do framework de Otimização de Política Próxima (PPO), criando o ReMax PPO (RePPO).

• Arquitetura: Um método actor-critic on-policy usando um crítico Q.
• Objetivo de Substitutos (Surrogate): O RePPO modifica o substituto padrão do PPO substituindo a vantagem padrão por uma vantagem baseada em EI.
  $$A^+(t) = R^+(t) - b^+(s_t)$$
  onde $R^+(t) = \text{EIm}(R^\lambda_t, \pi_\theta, Q_\phi(s_t, \cdot))$ e $b^+$ é o valor esperado dos valores Q transformados por EI.
• Estratégia de Substituição de Q: Para evitar que o crítico superestime a melhoria da ação amostrada (devido à subestimação do valor Q), os autores substituem o valor Q da ação amostrada pelo retorno real da trajetória ao computar o termo de EI. Isso garante que a "melhoria" seja medida contra o retorno real, não contra uma estimativa potencialmente enviesada.

3. Principais Contribuições

1. Objetivo ReMax: Um novo objetivo de RL que induz exploração via maximização de recompensa gulosa sob incerteza (tentativas) sem bônus de exploração explícitos.
2. Derivação Teórica: Uma nova formulação de gradiente de política para o ReMax que é estimável a partir de retornos de trajetórias únicas, utilizando uma expressão de forma fechada para o máximo esperado sobre $M$ sorteios.
3. Controle Contínuo: A generalização do número de tentativas discreto $M$ para um parâmetro contínuo $m$, permitindo o ajuste preciso da taxa de exploração.
4. Algoritmo RePPO: Um algoritmo de aprendizado profundo de RL prático (RePPO) que implementa o ReMax dentro de um framework PPO, demonstrando que a exploração pode emergir do próprio objetivo de função.

4. Resultados Experimentais

4.1 Experimentos de Bandit

• Estocasticidade: Em um bandit de dois braços, o ReMax induz políticas estocásticas para $M \ge 2$, enquanto o RL padrão ($M=1$) gera políticas determinísticas.
• Adaptabilidade: O ReMax adapta a exploração à magnitude da incerteza da recompensa. À medida que a variância aumenta, a política ReMax ótima aumenta a exploração para capturar resultados de alta recompensa raros, ao contrário do softmax com regularização de entropia, que permanece fixo com base na média.
• Regret (Arrependimento): Em cenários de bandit posterior (Beta-Bernoulli e Gaussian-Gaussian), o ReMax exibe um regret cumulativo empiricamente sublinear, comparável ao Thompson Sampling e UCB, e superior ao baseline de Softmax.

4.2 Benchmarks MinAtar

Avaliado em quatro jogos (Breakout, Asterix, Freeway, Space Invaders):

• Performance: O RePPO (com $m \in [1.2, 1.4]$) superou variantes padrão do PPO (PPO-V, PPO-Q) e o PPO com bônus de entropia ou bônus de Redes Neurais de Distilação Aleatória (RND).
• Exploração: O RePPO manteve uma entropia de política mais alta durante o treinamento em comparação ao PPO com um bônus de entropia explícito, apesar de não possuir tal bônus.
• Sensibilidade de Parâmetros: A performance atingiu o pico em torno de $m=1.2$ a $1.4$. Valores maiores de $m$ retardaram o decaimento da entropia (sustentando a exploração), enquanto valores menores levaram a uma convergência mais rápida, porém com performance inferior.
• Ablação: Remover o baseline independente de ação ou a estratégia de substituição de Q degradou significativamente a performance, confirmando sua necessidade.

4.3 Benchmark Craftax

Avaliado no Craftax, um ambiente de RL de larga escala e open-ended:

• Performance: O RePPO ($m=1.2$) alcançou performance competitiva (11.87% da recompensa máxima) comparado às variantes de PPO com bônus de entropia e RND (11.66% e 11.68%), e superou o PPO sem bônus.
• Escalabilidade: O RePPO manteve uma entropia mais alta sem bônus explícitos, demonstrando que o mecanismo escala para tarefas complexas de longo horizonte.

5. Significância e Alegações

O artigo afirma que o ReMax oferece uma alternativa promissora aos métodos tradicionais de exploração ao:

• Eliminar a necessidade de bônus explícitos: A exploração emerge naturalmente do objetivo de maximizar o retorno máximo esperado sobre as tentativas.
• Simplificar o design do algoritmo: Evita o overhead computacional e a complexidade de projetar bônus de curiosidade ou manter modelos de posterior explícitos (embora possa utilizar estes para estimativa de incerteza).
• Fornecer controle refinado: O parâmetro contínuo $m$ permite o ajuste preciso do equilíbrio entre exploração e explotação.

Os autores observam que, embora seus experimentos de deep RL tenham demonstrado primariamente exploração estocástica (aumento da entropia da política), o framework teórico suporta a exploração profunda (coerência temporal na coleta de informações) se combinado com modelagem de incerteza explícita (ex: ensembles). Eles posicionam o ReMax como um princípio geral aplicável a domínios onde o "tentar novamente" é valioso, incluindo tarefas de raciocínio com Large Language Models (LLMs), traçando paralelos com objetivos do tipo pass@K nesta área.

O trabalho é modesto em suas alegações teóricas, observando que limites de regret formais para o cenário de deep RL são deixados para trabalhos futuros, e que os resultados atuais são demonstrações empíricas de eficácia.