On the Role of Computation in Reinforcement Learning

Sumário Técnico: Sobre o Papel da Computação no Aprendizado por Reforço

Definição do Problema
A visão padrão no Aprendizado por Reforço (RL) trata as políticas como funções estáticas que mapeiam estados para ações, gastando uma quantidade fixa de computação independentemente da complexidade da decisão necessária. Esse paradigma confunde o número de parâmetros (memória) com a quantidade de computação (tempo). Embora o escalonamento da contagem de parâmetros (Lei de Moore) tenha sido uma estratégia comum, a computação necessária para tomar decisões ótimas pode variar em ordens de magnitude entre diferentes estados. Políticas massivas e estáticas são frequentemente ineficientes, e políticas computacionalmente limitadas podem falhar ao generalizar para tarefas de horizonte mais longo, aprendendo, em vez disso, heurísticas que sofrem overfitting às distribuições de treinamento. O artigo aborda a falta de uma linguagem formal para distinguir entre computação e parâmetros em RL e investiga se políticas com parâmetros fixos podem se beneficiar de um tempo de computação variável e aumentado.

Metodologia
O artigo aborda o problema através de duas lentes complementares: formalização teórica e validação empírica.

1. Estrutura Teórica:

   • Os autores formalizam as políticas de RL como modelos de computação limitados usando máquinas de Turing.
   • Eles definem políticas limitadas pelo tempo ($\Pi_t$) como aquelas implementáveis por uma máquina de Turing que para dentro de $t(|s|)$ passos.
   • Eles introduzem o Teorema da Hierarquia de Políticas, provando que para funções construtíveis em tempo $g(n) \in o(t(n)/\log t(n))$, existem Processos de Decisão de Markov (MDPs) onde políticas com orçamentos de computação maiores ($\Pi_t$) performam arbitrariamente melhor do que aquelas com orçamentos menores ($\Pi_g$).
   • Eles provam ainda o Teorema de Generalização de Longo Horizonte, demonstrando que políticas de baixa computação podem sofrer overfitting em tarefas de treinamento (correspondendo à função de valor ótima nos dados de treinamento), mas falham em generalizar para tarefas de teste de horizonte mais longo, enquanto políticas de alta computação conseguem resolver essas tarefas estendidas.

2. Proposta Arquitetural:

   • Para testar essas teorias, os autores propõem uma arquitetura recorrente mínima chamada Unidade de Interpolação Recorrente (IRU).
   • A IRU é uma variante simplificada de blocos LSTM/GRU, consistindo em duas camadas lineares (Forget e Input) que interpolam entre o estado anterior da célula e um novo cálculo local.
   • A arquitetura aplica este bloco $N$ vezes durante um passo de propagação direta (forward pass) (passos recorrentes), permitindo que a política utilize uma quantidade variável de computação ($N$) enquanto mantém uma contagem fixa de parâmetros.
   • A rede completa (IRU-$N$) inclui uma camada linear inicial, $N$ blocos recorrentes com conexões de salto (skip connections) e um cabeçalho de saída final.

3. Configuração Experimental:

   • Experimentos foram conduzidos em 31 tarefas abrangendo domínios discretos (Boxpick, Lightsout) e contínuos (OGBench), incluindo configurações de RL online e offline.
   • Os baselines incluíram Redes Feedforward Padrão (MLP) e Redes Residuais (ResNet). Crucialmente, o baseline ResNet foi desenhado para ter uma profundidade efetiva (computação) semelhante (mais parâmetros — até 5x mais), enquanto o MLP teve parâmetros similares, mas menos computação.
   • O estudo avaliou o desempenho em tarefas de treinamento e, criticamente, em tarefas de teste de horizonte mais longo não vistas para medir a generalização.

Principais Contribuições

• Formalização de Políticas Limitadas pela Computação: O artigo fornece a primeira prova formal de que aumentar o tempo de computação (distinto da contagem de parâmetros) permite que políticas resolvam problemas e generalizem para horizontes mais longos que são teoricamente impossíveis para políticas de menor computação.
• Arquitetura Recorrente Mínima: A introdução da IRU, uma arquitetura leve capaz de escalar a computação via passos recorrentes sem aumentar a contagem de parâmetros.
• Métrica do Valor da Computação: Uma medida numérica proposta, o Valor da Computação (VoC), análoga ao Valor da Informação em POMDPs. Esta métrica estima o ganho ou perda de valor quando um agente aumenta temporariamente seu orçamento de computação por um número específico de passos.
• Desvinculação de Computação e Parâmetros: Evidência empírica mostrando que os ganhos de desempenho advêm do aumento da expressividade (computação) e não apenas do aumento da capacidade do modelo (parâmetros).

Resultos

• Escalonamento de Desempenho: Em ambientes discretos e contínuos, aumentar o número de passos recorrentes ($N$) de 1 para 10 melhorou significativamente as taxas de sucesso. Em tarefas desafiadoras como Boxpick e OGBench, o desempenho aumentou em até 10 vezes.
• Generalização: Políticas IRU treinadas em tarefas de curto horizonte generalizaram significativamente melhor para tarefas de longo horizonte não vistas em comparação com MLPs e ResNets. Notavelmente, a IRU superou ResNets com 5 vezes mais parâmetros em tarefas de avaliação de longo horizonte.
• Eficiência de Amostragem: Arquiteturas IRU demonstraram maior eficiência de amostragem, convergindo para um desempenho assintótico mais alto com menos passos de ambiente.
• Fonte de Melhoria: Experimentos "Yoked" (treinar um agente passivo em dados coletados por um agente ativo) revelaram que o principal benefício da computação adicional provém da expressividade da política (sua capacidade de aprender soluções complexas a partir dos dados) e não de uma melhor exploração ou qualidade de dados. O agente passivo treinado em dados de um agente ativo de baixa computação performou mal, a menos que ele próprio utilizasse alta computação.
• Ablação: A arquitetura IRU superou LSTMs padrão e Redes Residuais Recorrentes em termos de velocidade e eficiência de parâmetros, sugerindo que mecanismos de portão (gating) específicos são necessários para aproveitar efetivamente os benefícios da computação adicional.

Significância e Alegações
O artigo afirma mudar a perspectiva do RL de aproximação de função estática para uma visão computacional onde tempo e memória são eixos distintos. Os autores argumentam que:

1. A computação é um recurso distinto: Aumentar o tempo de computação pode provadamente melhorar o desempenho e a generalização sem aumentar o tamanho da classe de hipóteses (parâmetros), evitando assim os problemas de overfitting associados a modelos estáticos maiores.
2. Generalização via Iteração: A computação iterativa permite que as políticas aprendam soluções algorítmicas que se extrapolam para horizontes mais longos, um fenômeno observado em modelos de linguagem, mas anteriormente subexplorado em RL sem pré-treinamento ou currículos multitarefa.
3. Limitações de Visões Estáticas: Os resultados sugerem que as suposições padrão de MDP (por exemplo, a existência de uma política ótima determinística) podem não se sustentar sob restrições computacionais, o que pode explicar por que políticas não-Markovianas são às vezes necessárias mesmo em tarefas totalmente observáveis.

Os autores concluem que, embora seu trabalho utilize uma arquitetura mínima para isolar esses efeitos, os achados sugerem que futuros sistemas de RL devem considerar estratégias de computação adaptativa, onde a quantidade de computação é escalada dinamicamente com base na dificuldade do estado atual.