Performance-Driven Environment Abstraction with Multi-Timescale Learning

Resumo Técnico: Abstração de Ambiente Orientada ao Desempenho com Aprendizado de Múltiplas Escalas Temporais

Formulação do Problema
O artigo aborda o desafio da tomada de decisão em Processos de Decisão de Markov (MDPs) de larga escala, onde o planejamento diretamente no espaço de estados original é computacionalmente inviável. Enquanto as abordagens existentes frequentemente dependem de compressão informacional ou heurísticas estruturais que preservam propriedades geométricas ou topológicas, este trabalho argumenta que a abstração apropriada é inerentemente dependente da tarefa. Os autores propõem um framework de abstração de estado orientada ao desempenho. O objetivo central é encontrar uma agregação de estados (particionando o espaço de estados em "superestados") e uma política correspondente que maximizem a qualidade da decisão enquanto minimizam a complexidade da representação.

Uma restrição crítica nesta formulação é a restrição de Mesma Distribuição de Ações (Same-Action-Distribution - SAD): todos os estados dentro de um único superestado agregado devem compartilhar a mesma distribuição de ações. Embora isso reduza o espaço de busca da política, introduz erros de aproximação. O artigo busca equilibrar o compromisso entre a complexidade da abstração (número de superestados) e a perda de desempenho induzida pela restrição SAD e pela aproximação da função de valor.

Metodologia
A solução proposta é um framework de aprendizado por reforço de múltiplas escalas temporais que adapta conjuntamente a política e uma abstração de ambiente estruturada em árvore.

1. Fundamentação Teórica:

   • Os autores derivam um limite de desempenho para a tomada de decisão sob uma agregação fixa. Este limite separa a subotimalidade total em duas fontes distintas:
     • Erro de aproximação da função de valor ($\epsilon_\Gamma$): O erro decorrente da representação da função de valor ótima com valores constantes por partes sobre os superestados.
     • Perda de compartilhamento de ação ($\delta_\Gamma$): A perda de desempenho especificamente induzida pela restrição SAD, resultante da não comutatividade da maximização e da média (ou seja, forçar uma única distribuição de ações para um grupo de estados que poderiam otimamente exigir ações diferentes).
   • Um limite superior computável é derivado com base no desajuste do resíduo de Bellman, que serve como um substituto (proxy) para a função de valor ótima desconhecida.

2. Agregação Adaptativa Baseada em Árvore:

   • O espaço de estados é representado por uma árvore hierárquica (especificamente quadtrees nos experimentos). As folhas da árvore definem os atuais superestados.
   • Estimativa de Q: Para guiar mudanças estruturais, o algoritmo mantém estimativas de valores-Q nos nós folha. Crucialmente, ele também mantém estimativas para os filhos prospectivos dos nós expansíveis. Isso permite que o sistema avalie o benefício potencial de refinar uma região sem se comprometer totalmente com a expansão.
   • Critérios de Expansão e Colapso:
     • Expansão (Refinamento): Um nó folha é expandido se o ganho estimado no desempenho de valor-Q (ao permitir que os filhos adotem distribuições de ações distintas) exceder um limiar determinado pelo parâmetro de regularização $\lambda$ e pelo fator de desconto $\beta$.
     • Colapso (Agrupamento/Coarsening): Um nó pai é colapsado se a fusão de seus filhos não resultar em uma queda significativa de desempenho em relação ao custo de manter nós separados.
   • Aprendizado de Múltiplas Escalas Temporais: O framework opera em três escalas temporais:
     • Mais rápida: O Actor-Critic agregado atualiza a política e a função de valor para a partição atual fixa.
     • Intermediária: As estimativas de Q para atualizações estruturais são refinadas.
     • Mais lenta: A estrutura da árvore (partição) é atualizada com base nas estimativas de Q. Isso garante que a política converja sob uma abstração quase estática antes que a estrutura mude.

Principais Contribuições
O artigo identifica três contribuições primárias:

1. Limite de Desempenho: Um limite teórico para a tomada de decisão sob abstração de ambiente que separa explicitamente o erro de aproximação de valor da perda causada pela restrição SAD.
2. Critério Guiado por Valor-Q: Um critério fundamentado para refinar e agregar abstrações baseadas em árvores, derivado da análise teórica e implementado via discrepâncias de valor-Q.
3. Algoritmo de Múltiplas Escalas Temporais: Um algoritmo de aprendizado unificado que adapta conjuntamente a política e a estrutura de abstração, permitindo a reestruturação contínua do espaço de estados para equilibrar desempenho e complexidade.

Resultos
O método foi avaliado em tarefas de navegação discretas (grid worlds, labirintos, mapas de terreno de Marte) e uma tarefa de controle contínuo (Mountain Car), comparando-o com Actor-Critic plano, Hierarchical Actor-Critic baseado em quantização e Árvores de Abstração Condicional (CAT).

• Compressão de Estado: O algoritmo alcançou compressão de estado substancial (por exemplo, reduzindo 1024 estados para 232 superestados em um labirinto 32x32) enquanto preservava estruturas topológicas relevantes para a tarefa.
• Eficiência de Amostragem e Velocidade: A variante Tree-AC-Replan proposta (iniciada com uma abstração previamente aprendida) demonstrou convergência e capacidades de replanejamento significativamente mais rápidas em comparação com as bases, particularmente quando os parâmetros da tarefa (como localizações de objetivos) mudavam.
• Adaptabilidade: O sistema adaptou-se com sucesso a novas tarefas ao refinar regiões próximas a novos objetivos e agrupar regiões que não exigiam mais alta resolução.
• Compromissos (Trade-offs): Experimentos revelaram uma relação em forma de U entre a profundidade inicial da árvore e o número de episódios necessários para atingir uma taxa de sucesso alvo, indicando uma granularidade intermediária ideal para inicialização. A análise da fronteira de Pareto mostrou que o método equilibra efetivamente o tamanho da abstração versus o desempenho da política.

Significância e Alegações
O artigo afirma que a construção automática de representações hierárquicas é um componente fundamental da inteligência. Ao se afastar de abstrações que preservam a geometria em direção a abstrações orientadas ao desempenho, o framework proposto aborda a lacuna na literatura existente, onde as abstrações são frequentemente específicas de um domínio ou carecem de otimização explícita para o desempenho da tarefa subsequente.

Os autores enfatizam que sua abordagem fornece garantias teóricas em relação à perda de desempenho, algo que os métodos anteriores baseados em heurísticas careciam. A capacidade de aprender conjuntamente a política e a estrutura de abstração permite que agentes gerenciem tarefas complexas enquanto permanecem adaptáveis a ambientes em evolução. O trabalho sugere que este framework é um passo em direção à autonomia escalável onde o planejamento no espaço de estados original é inviável, oferecendo um mecanismo para ajustar dinamicamente a "resolução" do modelo de mundo do agente com base nas necessidades imediatas de desempenho.