MCTS perde 2,88% para reinícios aleatórios no escalonamento de DAGs com o mesmo orçamento

Pesquisadores no arXiv colocaram o Monte Carlo Tree Search e um list scheduler comum com reinícios aleatórios nas mesmas condições: 2048 escalonamentos construídos e avaliados para cada tarefa. A árvore de busca perdeu. Em 72 de 96 instâncias reservadas (held-out), nas quais a solução-base tinha margem para melhorar, o MCTS ficou 2,88% pior em makespan (IC de 95% de −3,62% a −2,15%). O trabalho não prova que o MCTS seja inútil. Mostra, porém, que uma comparação sem um concorrente simples e com o mesmo orçamento diz pouco.

Um protocolo capaz de refutar o MCTS

Os autores partem de uma observação: artigos sobre MCTS no escalonamento de workflows em DAG raramente dão ao método simples a mesma quantidade de computação. Aqui, todos os participantes recebem o mesmo número de escalonamentos candidatos. O participante principal é o método com MCTS, declarado de antemão como o principal. O controle é um list scheduler com reinícios aleatórios e sem árvore. Depois, no mesmo domínio, foi adicionado um terceiro participante: o MCTS com UCT de livro-texto.

O plano de análise foi fixado antes da coleta de dados. Um verificador independente checou todos os 768 escalonamentos da etapa confirmatória: todos são válidos, e os tempos de conclusão foram calculados corretamente.

• Orçamento principal: 2048 escalonamentos avaliados.
• Diferença entre MCTS e reinícios: −2,88%, IC [−3,62%; −2,15%].
• Automelhoria em um pool de exploração separado: reinícios +1,85%, MCTS +0,24%.
• Primeiros resultados do MCTS: 700 de 720 coincidiram com o warm start que lhe foi entregue.
• MCTS com UCT de livro-texto: −0,26%, IC [−0,71%; +0,23%].
• Escala: 8, 16 e 32 tarefas, 2–8 processadores, orçamentos de até 2048.

Por que a árvore não ajudou

A primeira hipótese era que faltou orçamento ao MCTS. Os dados não sustentam isso: no pool de exploração, os reinícios melhoraram a si mesmos em 1,85%, enquanto o MCTS melhorou apenas 0,24%. Além disso, em 700 de 720 casos, o primeiro resultado do MCTS era só a solução inicial que lhe foi entregue. Ou seja, a árvore quase não se afastou do ponto de partida.

Na versão dos autores, a causa está na regra de seleção. Ela fica presa de forma determinística no primeiro filho expandido, e por isso as simulações dentro de um ramo ficam fortemente correlacionadas. Os reinícios escolhem uma trajetória nova a cada vez e aproveitam os ganhos das caudas da distribuição. Os autores tratam a ligação com o makespan como inferência, não como um mecanismo causal comprovado. A hipótese é reforçada por um experimento que troca a regra pelo UCT clássico: a diferença cai para 0,26%, e o intervalo de confiança passa a incluir o zero. Mesmo assim, o sinal continua negativo, de modo que o MCTS não supera os reinícios nem na versão corrigida.

Os autores também montaram um mapa estrutural. Em workflows esparsos e irregulares, os reinícios vencem. Em workflows regulares em camadas, não se veem diferenças. Em grafos densos, quase não há o que melhorar, porque a solução-base já está perto do limite.

O que verificar antes de construir a árvore

Para engenheiros que escalonam tarefas em pipelines de dados, no treinamento de modelos ou em cadeias de agentes, a conclusão é pé no chão. Antes de adotar o MCTS, vale rodar um list scheduler com aleatorização no mesmo número de avaliações. Isso se implementa em uma noite e dá um ponto de referência honesto. Se a árvore não o supera, a complexidade não se justifica.

A segunda verificação é a fração de soluções em que a busca se afastou do warm start. Se quase todos os resultados coincidem com o ponto de partida, o algoritmo praticamente não explora. A terceira é a própria regra de seleção de ramos: dela depende se a árvore será diversificada.

Os próprios autores apontam as limitações do trabalho. O experimento é sintético, os grafos são pequenos (até 32 tarefas) e o orçamento não passa de 2048. Não há conclusões sobre orçamentos maiores nem sobre workflows reais. Ainda assim, como exemplo de disciplina, o trabalho é útil: pré-registro, orçamento igual e verificação independente da validade dos escalonamentos. Em sistemas de agentes, onde planejadores muitas vezes são adotados pelo nome da moda do algoritmo, esse tipo de controle é tão necessário quanto os métodos novos.