ETGL-DDPG: A Deep Deterministic Policy Gradient Algorithm for Sparse Reward Continuous Control

Título: ETGL-DDPG: Um Algoritmo de Gradiente de Política Determinística Profunda para Controle Contínuo com Recompensas Esparsas

1. Problema Abordado

O artigo foca nas limitações do algoritmo DDPG (Deep Deterministic Policy Gradient) em ambientes de Reforço Aprendizado (RL) com recompensas esparsas. Em tarefas de controle contínuo onde a recompensa só é concedida ao atingir um objetivo específico (ex: chegar a um estado meta), o DDPG padrão enfrenta três desafios principais:

1. Falta de Exploração Direcional: Estratégias padrão de exploração (como $\epsilon$-greedy ou ruído aditivo) são ineficazes em grandes espaços de estados esparsos porque não possuem abstração temporal. Elas exploram de forma aleatória e sem direção, dificultando a descoberta de trajetórias raras que levam ao objetivo.
2. Tratamento Uniforme de Transições: O replay buffer (memória de experiência) padrão do DDPG amostra transições uniformemente. Em cenários esparsos, onde a maioria das transições não recebe recompensa, o agente raramente vê exemplos de sucesso, atrasando o aprendizado.
3. Propagação Lenta de Informação: Em episódios bem-sucedidos, apenas a última transição recebe recompensa. No DDPG padrão (atualização de 1 passo), a recompensa leva muito tempo para se propagar de volta para os estados iniciais do episódio, exigindo que o agente atinja o objetivo inúmeras vezes para aprender a política correta.

2. Metodologia e Contribuições Principais

Os autores propõem o ETGL-DDPG, que integra três técnicas ortogonais ao DDPG para superar essas limitações:

A. $\epsilon_t$-greedy: Exploração com Busca em Árvore

• Conceito: Uma versão temporalmente estendida do $\epsilon$-greedy. Com probabilidade $\epsilon$, o agente não executa uma ação aleatória simples, mas sim o primeiro passo de uma "opção" gerada por uma busca local.
• Mecanismo:
  • Utiliza uma função de hash sensível à localização (SimHash) para discretizar o espaço de estados contínuo e estimar contagens de visitas ($n(\phi(s))$) a regiões vizinhas.
  • O agente constrói uma árvore de busca usando transições armazenadas no replay buffer como um modelo aproximado de transição.
  • A busca tem um orçamento de tempo $N$. Se um nó na árvore for encontrado em uma área não visitada ($n=0$), o caminho da raiz até esse nó é retornado como uma opção exploratória.
  • Caso contrário, a busca retorna o caminho até o nó menos visitado na fronteira da árvore.
• Vantagem: Permite exploração direcionada para áreas não exploradas, evitando obstáculos e regiões superexploradas, sem modificar a função de recompensa.
• Garantia Teórica: Os autores provam que o $\epsilon_t$-greedy possui complexidade de amostragem polinomial (é PAC-MDP) sob certas suposições de MDP, garantindo eficiência teórica.

B. GDRB: Goal-conditioned Dual Replay Buffer (Buffer Duplo Condicionado ao Objetivo)

• Conceito: Substitui o único replay buffer por dois buffers distintos com políticas de retenção e amostragem adaptativas.
  • Buffer $D_\beta$ (Exploração): Armazena todas as transições do treinamento. Utiliza Reservoir Sampling para manter a cobertura de dados antigos.
  • Buffer $D_e$ (Exploração/Explotação): Armazena apenas transições de episódios bem-sucedidos (onde o objetivo foi atingido). Utiliza política FIFO (First-In-First-Out).
• Amostragem Adaptativa: A razão de amostragem entre os buffers muda dinamicamente ao longo do treinamento. Inicialmente, amostra-se mais de $D_\beta$; à medida que o agente aprende e gera mais episódios de sucesso, a amostragem de $D_e$ aumenta, priorizando dados de alta qualidade.

C. Longest n-step Return (Retorno n-passos Mais Longo)

• Conceito: Substitui a atualização de 1 passo (TD) padrão por uma atualização baseada no retorno de n-passos para todas as transições de um episódio.
• Mecanismo:
  • Em episódios bem-sucedidos, o retorno é calculado como a soma descontada de todas as recompensas até o objetivo (equivalente a um retorno de Monte Carlo). Isso propaga a recompensa imediatamente para todos os estados anteriores do episódio.
  • Em episódios mal-sucedidos, o retorno é calculado até o limite de tempo, utilizando o valor Q do último estado como bootstrap. Isso ajuda a reduzir o viés de superestimação comum em métodos de múltiplos passos.
• Vantagem: Acelera drasticamente a propagação da recompensa esparsa, permitindo que o agente aprenda a política ótima com menos episódios de sucesso.

3. Resultados Experimentais

O algoritmo foi avaliado em benchmarks padrão de 2D e 3D, incluindo ambientes de navegação (Labirinto de Paredes, Labirinto em U, Empurrar Ponto) e manipulação (Abrir Janela, Futebol, Pressionar Botão).

• Desempenho Geral: O ETGL-DDPG superou consistentemente o DDPG padrão, bem como outros métodos de última geração (SAC, TD3, DOIE) em todos os ambientes testados com recompensas esparsas.
• Taxa de Sucesso: Em ambientes desafiadores como o "Wall-maze" (Labirinto de Paredes), onde métodos como DDPG e TD3 falharam em obter qualquer sucesso (taxa 0), o ETGL-DDPG e o DOIE alcançaram taxas de sucesso próximas a 1.0.
• Cobertura do Ambiente: O $\epsilon_t$-greedy demonstrou uma cobertura de ambiente significativamente superior (até 80-100% em alguns casos) comparado a estratégias como $\epsilon_z$-greedy e motivação intrínseca, provando sua eficácia na exploração direcionada.
• Estudo de Ablação:
  • O $\epsilon_t$-greedy foi identificado como o componente mais crítico, sendo o único capaz de melhorar o DDPG no ambiente mais difícil (Wall-maze).
  • O GDRB melhorou o desempenho na maioria dos ambientes.
  • O retorno n-passos mostrou-se benéfico em tarefas específicas, embora tenha aumentado a variância em outras.
• Custo Computacional: O ETGL-DDPG requer aproximadamente 1,5x mais tempo de treinamento (tempo de parede) que o DDPG padrão, devido principalmente à busca local no $\epsilon_t$-greedy e ao cálculo de retornos n-passos.

4. Significância e Conclusão

O trabalho é significativo por abordar sistematicamente as três falhas fundamentais do DDPG em cenários de recompensa esparsa sem depender de reward shaping (modificação artificial da recompensa), o que muitas vezes é específico do problema e difícil de generalizar.

• Inovação Teórica: A prova de complexidade de amostragem polinomial para a exploração baseada em busca em árvore oferece uma garantia teórica sólida que falta em muitas heurísticas de exploração.
• Eficiência Prática: A combinação de buffers duplos e retornos n-passos maximiza a utilidade de cada episódio de sucesso, tornando o aprendizado viável em tarefas onde o sucesso é extremamente raro.
• Aplicabilidade: O método demonstra robustez em tarefas de manipulação robótica e navegação complexa, sugerindo que a exploração direcionada baseada em modelos aproximados (via replay buffer) é uma estratégia superior para controle contínuo difícil.

Em resumo, o ETGL-DDPG estabelece um novo estado da arte para algoritmos baseados em DDPG em ambientes esparsos, demonstrando que a integração inteligente de busca, gerenciamento de memória e propagação de valor pode superar limitações históricas de algoritmos de gradiente de política.