Finding the Time to Think: Learning Planning Budgets in Real-Time RL

Resumo Técnico: Encontrando o Tempo para Pensar: Orçamentos de Planejamento em Aprendizado por Reforço em Tempo Real

Definição do Problema: RL em Tempo Real com Atraso Variável

O Aprendizado por Reforço (RL) padrão e os Processos de Decisão de Markov (MDPs) operam sob a premissa de que o ambiente espera indefinidamente para que o agente compute uma ação; portanto, a deliberação não acarreta custo. Em configurações de tempo real, essa premissa falha: o ambiente progride continuamente, independentemente do tempo de computação do agente. Uma ação perfeita executada com atraso é frequentemente inferior a uma ação subótima, porém oportuna.

Embora o trabalho anterior (Ramstedt & Pal, 2019) tenha formalizado o RL em tempo real com um atraso fixo (por exemplo, exatamente um passo de tempo para computar), este artigo introduz o RL em Tempo Real com Atraso Variável. Neste framework, o agente não é uma função estática, mas um procedimento que roda no tempo. O agente deve decidir quanto tempo deliberar em cada ponto de decisão. O custo da deliberação é "pago" como progresso ambiental (ou depleção de relógio em jogos de tabuleiro) enquanto o agente computa. Isso cria um desafio de meta-raciocínio: o agente deve equilibrar a qualidade da ação planejada contra a degradação do estado causada pelo tempo gasto no planejamento. Planejar ingenuamente quanto tempo planejar corre o risco de um paradoxo onde a própria meta-decisão incorre nos mesmos custos de tempo real que o planejamento que ela busca otimizar.

Metodologia

Os autores propõem uma solução baseada em um Processo de Decisão de Markov Semi-Marcoviano (SMDP) sobre opções orçamentadas, desacoplando o algoritmo de planejamento da decisão de quanto planejar.

1. Componentes da Arquitetura:

   • Política de Reflexo ($\pi_{reflex}$): Uma política leve e rápida (por exemplo, a cabeça de política de um modelo AlphaZero sem MCTS) que roda em muito menos de um frame. Ela fornece ações imediatas para o ambiente enquanto o planejador executa em segundo plano.
   • Computações de Refinamento de Ação de Tempo Contínuo ($\{c_k\}$): Um conjunto finito de computações indexadas por duração discreta $k$. Neste trabalho, elas são instanciadas como execuções de Monte Carlo Tree Search (MCTS) por $k$ frames. Execuções mais longas ($c_k$) produzem ações de maior qualidade, mas levam mais tempo.
   • Opções Orçamentadas ($o_k$): Cada opção $o_k$ envolve uma computação $c_k$. Ao ser iniciada, o agente compromete-se a executar $k-1$ ações extraídas de $\pi_{reflex}$ enquanto $c_k$ roda. No $k$-ésimo frame, a ação refinada de $c_k$ é executada.
   • Política de Portão ($\pi_{gate}$): Uma rede neural leve treinada via Proximal Policy Optimization (PPO) que atua como uma meta-política. Ela observa o estado atual (observação do jogo, características do planejador e estimativas de valor) e seleciona o orçamento $k$ (a duração da opção) para o próximo meta-passo.

2. Protocolo de Treinamento:

   • Treinamento em Duas Fases: Primeiro, planejadores baseados em AlphaZero são treinados para ambientes específicos. Esses planejadores são então congelados. Segundo, a política de portão é treinada sobre o planejador congelado.
   • Formulação de Meta-MDP: A política de portão resolve um problema de controle discreto onde as ações são a seleção de opções orçamentadas. A recompensa é o retorno cumulativo ao longo dos $k$ frames da opção, descontado por $\gamma^k$.
   • GAE Adaptado: Como os meta-passos têm durações variáveis ($k$), os autores adaptam a Estimativa de Vantagem Generalizada (GAE) para carregar o desconto por meta-passo $\gamma^k$ através do cálculo da vantagem.

3. Instanciações de Ambiente:

   • Ambientes de Ação Comprometida (Pac-Man, Tetris em Tempo Real, Snake): O ambiente progride continuamente. O agente executa $k-1$ ações de reflexo enquanto planeja. O custo do planejamento é a mudança do estado do mundo durante a computação.
   • Ambientes de Relógio (Speed Hex, Speed Go): O tabuleiro é estático, mas um relógio compartilhado se esgota com o tempo de pensamento. A política de reflexo emite "no-ops" durante a janela de planejamento. O custo é a redução do orçamento de tempo restante.

Principais Contribuições

1. Framework de RL em Tempo Real com Atraso Variável: Uma generalização de frameworks de atraso fixo onde o agente escolhe seu próprio tempo de deliberação, tratando a seleção de atraso como um problema aprendível em vez de uma restrição imposta pelo sistema.
2. Caracterização Empírica de Trocas de Planejamento: Os autores estabelecem que a qualidade do planejamento e a latência de inferência escalam conjuntamente com as contagens de simulação do MCTS. Esse escalonamento conjunto motiva a necessidade de alocação adaptativa em vez de orçamentos fixos.
3. Portão Adaptativo sobre Planejadores Congelados: Um método para aprender orçamentos de planejamento dependentes do estado usando uma política de portão leve treinada sobre um planejador AlphaZero congelado. Isso evita o paradoxo do "planejamento sobre o planejamento", pois um único passo de propagação do portão é ordens de magnitude mais barato que uma execução de MCTS.
4. Validação de Hardware no Mundo Real: O método é validado em uma implantação assíncrona de duas GPUs (uma GPU para o ambiente/reflexo, outra para o MCTS) sem alterações arquiteturais ou retreinamento, demonstrando que a política treinada em simulação transfere-se efetivamente para execução separada por hardware.

Resultados

A política de portão foi avaliada em cinco ambientes: Pac-Man, Real-Time Tetris, Snake, Speed Hex e Speed Go.

• Desempenho vs. Baselines: A política de portão adaptativa superou consistentemente:
  • Políticas de Orçamento Fixo: Agentes limitados a um único $k$ (ex: sempre planejando para 1, 2, 3 ou 4 frames).
  • Baselines Heurísticos: Incluindo "Greedy" (sempre o máximo de simulações) e "Midpeak" (alocação em curva de sino comum em motores de jogos).
  • Baselines Aleatórios: A seleção aleatória de orçamentos teve desempenho significativamente inferior, confirmando que quando alocar computação é tão crítico quanto quanto alocar.
• Ganhos Específicos:
  • Pac-Man: +10,3% de melhoria sobre o melhor orçamento fixo.
  • Real-Time Tetris: +65% de melhoria sobre o melhor orçamento fixo.
  • Snake: +10,9% de melhoria.
  • Speed Hex/Go: A política de portão alcançou pontuações esperadas mais altas do que tanto os orçamentos fixos quanto as heurísticas sob várias restrições de relógio.
• Análise Comportamental: A política de portão aprendeu a alocar planejamento profundo (maior $k$) em estados de alto risco ou restritos (ex: fantasmas próximos no Pac-Man, tabuleiros densos no Tetris, baixa alcançabilidade no Snake) e reagiu rapidamente (baixo $k$) em estados seguros ou abertos. Também demonstrou generalização para diferentes orçamentos de relógio em Speed Hex/Go sem retreinamento.
• Transferência de Hardware: Em uma configuração assíncrona de duas GPUs (H100, A100, A40), as políticas transferiram-se limpam de simulação para hardware real. A latência permaneceu dentro do orçamento em H100 e A100, e os retornos aproximaram-se dos seus equivalentes de simulação.

Significância e Alegações

O artigo afirma abordar um descompasso fundamental entre o RL padrão e a interação em tempo real ao formalizar o tempo de deliberação como um recurso que deve ser gerenciado dinamicamente. A significância reside em:

• Escapar do Paradoxo do Meta-Raciocínio: Ao usar um portão leve sobre um planejador congelado, o sistema evita o overhead computacional de planejar como planejar, tornando a abordagem prática para implantação em tempo real.
• Alocação de Recursos Dependente do Estado: Os resultados demonstram que um orçamento de planejamento fixo é subótimo; o valor da computação é altamente dependente do estado.
• Escalabilidade para Hardware Assíncrono: O protocolo de treinamento de "ação comprometida" modela com sucesso a dinâmica de execução assíncrona, permitindo que políticas treinadas em simulação sejam implantadas em hardware separado (ambiente vs. planejador) sem modificação.

Limitações Reconhecidas:

• O framework assume um simulador de ambiente perfeito para os passos comprometidos (o MCTS deve prever com precisão as $k-1$ ações de reflexo).
• A política de portão é treinada em um planejador congelado; a otimização conjunta do planejador e do portão é deixada como trabalho futuro.
• O conjunto de orçamento $\mathcal{K}$ é calibrado manualmente e discreto; vocabulários de computação contínuos ou mais ricos são sugeridos como extensões futuras.