MCTS pierde un 2,88% frente a reinicios aleatorios en planificación de DAG con el mismo presupuesto

Investigadores en arXiv colocaron a Monte Carlo Tree Search y a un list scheduler corriente con reinicios aleatorios en condiciones idénticas: 2048 planificaciones construidas y evaluadas por cada tarea. El árbol de búsqueda perdió. En 72 de las 96 instancias reservadas (held-out) en las que la solución base tenía margen de mejora, MCTS quedó un 2,88% peor en makespan (IC del 95%: de −3,62% a −2,15%). El trabajo no demuestra que MCTS sea inútil. Lo que sí muestra es que una comparación sin un competidor simple con el mismo presupuesto dice muy poco.

Un protocolo capaz de refutar a MCTS

Los autores parten de una observación: los artículos sobre MCTS en planificación de workflows DAG rara vez dan al método simple la misma cantidad de cómputo. Aquí todos los participantes reciben el mismo número de planificaciones candidatas. El participante principal es el método basado en MCTS, declarado de antemano como el protagonista. El control es un list scheduler con reinicios aleatorizados y sin árbol. Más tarde se añadió un tercer participante sobre el mismo dominio: MCTS con UCT de libro de texto.

El plan de análisis se fijó antes de recopilar los datos. Un verificador independiente comprobó las 768 planificaciones de la fase de confirmación: todas son válidas y los tiempos de finalización están bien calculados.

• Presupuesto principal: 2048 planificaciones evaluadas.
• Diferencia entre MCTS y los reinicios: −2,88%, IC [−3,62%; −2,15%].
• Automejora en un pool de exploración aparte: reinicios +1,85%, MCTS +0,24%.
• Primeros resultados de MCTS: 700 de 720 coincidieron con el warm start que se le entregó.
• MCTS con UCT de libro de texto: −0,26%, IC [−0,71%; +0,23%].
• Escala: 8, 16 y 32 tareas, de 2 a 8 procesadores, presupuestos de hasta 2048.

Por qué el árbol no ayudó

La primera hipótesis era que a MCTS simplemente le faltó presupuesto. Los datos no la respaldan: en el pool de exploración los reinicios se mejoraron a sí mismos un 1,85%, mientras que MCTS solo un 0,24%. Además, en 700 de los 720 casos el primer resultado de MCTS fue únicamente la solución inicial que se le había entregado. Es decir, el árbol apenas se alejaba del punto de partida.

Según los autores, la causa está en la regla de selección. Esta se queda fijada de forma determinista en el primer hijo expandido, de modo que las simulaciones dentro de una rama están muy correlacionadas. Los reinicios, en cambio, eligen una trayectoria nueva cada vez y obtienen su ventaja de las colas de la distribución.

Los autores presentan la relación con el makespan como una inferencia, no como un mecanismo causal demostrado. La hipótesis se ve respaldada por un experimento que sustituye la regla por el UCT clásico: la diferencia se reduce a 0,26% y el intervalo de confianza ya incluye el cero. Pero el signo sigue siendo negativo, así que MCTS no supera a los reinicios ni siquiera en la versión corregida.

Por separado, los autores elaboraron un mapa estructural. En workflows dispersos e irregulares ganan los reinicios. En los regulares y estratificados no se observan diferencias. En grafos densos casi no hay nada que mejorar, porque la solución base ya está cerca del límite.

Qué comprobar antes de construir el árbol

Para los ingenieros que planifican tareas en pipelines de datos, entrenamiento de modelos o cadenas de agentes, la conclusión es práctica. Antes de implantar MCTS conviene ejecutar un list scheduler aleatorizado con el mismo número de evaluaciones. Se implementa en una tarde y ofrece un punto de referencia honesto. Si el árbol no lo supera, su complejidad no está justificada.

La segunda comprobación es la proporción de soluciones en las que la búsqueda se alejó del warm start. Si casi todos los resultados coinciden con el punto de partida, el algoritmo apenas explora. La tercera es la propia regla de selección de ramas: de ella depende que el árbol sea diverso.

Los autores señalan las limitaciones del trabajo. El experimento es sintético, los grafos son pequeños (hasta 32 tareas) y el presupuesto no supera 2048. No hay conclusiones sobre presupuestos mayores ni sobre workflows reales. Aun así, como ejemplo de disciplina metodológica el trabajo es útil: preregistro, presupuesto igual y verificación independiente de la validez de las planificaciones. En los sistemas de agentes, donde los planificadores se introducen a menudo por el nombre de moda de un algoritmo, este tipo de control hace falta tanto como los métodos nuevos.