MCTS battu de 2,88% par des redémarrages aléatoires dans la planification de DAG, à budget égal

Des chercheurs ont placé sur arXiv Monte Carlo Tree Search et un list scheduler ordinaire à redémarrages aléatoires dans des conditions identiques : 2048 plannings construits et évalués pour chaque tâche. L'arbre de recherche a perdu. Sur 72 des 96 instances de test (hold-out) où la solution de base avait une marge d'amélioration, MCTS a obtenu un makespan moins bon de 2,88% (IC à 95% de −3,62% à −2,15%). Ce travail ne prouve pas que MCTS soit inutile. En revanche, il montre qu'une comparaison sans concurrent simple doté du même budget n'apprend pas grand-chose.

Un protocole qui pouvait réfuter MCTS

Les auteurs partent d'un constat : les articles sur MCTS appliqué à la planification de workflows DAG donnent rarement autant de calcul à la méthode simple. Ici, tous les participants reçoivent le même nombre de plannings candidats. Le participant principal est la méthode MCTS, déclarée d'avance comme la méthode phare. Le contrôle est un list scheduler à redémarrages randomisés, sans arbre. Un troisième participant a été ajouté plus tard sur le même domaine : MCTS avec UCT de manuel.

Le plan d'analyse a été fixé avant la collecte des données. Un vérificateur indépendant a contrôlé les 768 plannings de la phase de confirmation : tous sont valides, et les temps d'achèvement sont correctement calculés.

• Budget principal : 2048 plannings évalués.
• Écart entre MCTS et les redémarrages : −2,88%, IC [−3,62%; −2,15%].
• Auto-amélioration sur un pool d'exploration distinct : redémarrages +1,85%, MCTS +0,24%.
• Premiers résultats de MCTS : 700 sur 720 coïncident avec le warm start qu'on lui a transmis.
• MCTS avec UCT de manuel : −0,26%, IC [−0,71%; +0,23%].
• Échelle : 8, 16 et 32 tâches, 2 à 8 processeurs, budgets jusqu'à 2048.

Pourquoi l'arbre n'a pas aidé

Première hypothèse : MCTS manquerait simplement de budget. Les données ne la soutiennent pas : sur le pool d'exploration, les redémarrages se sont améliorés de 1,85%, contre seulement 0,24% pour MCTS. De plus, dans 700 cas sur 720, le premier résultat de MCTS n'était que la solution de départ qu'on lui avait fournie. Autrement dit, l'arbre s'écartait à peine de son point de départ.

Selon les auteurs, la cause tient à la règle de sélection. Elle reste figée de façon déterministe sur le premier enfant développé, si bien que les essais au sein d'une branche sont fortement corrélés. Les redémarrages choisissent à chaque fois une nouvelle trajectoire et tirent leur gain des queues de la distribution. Les auteurs présentent le lien avec le makespan comme une inférence, non comme un mécanisme causal démontré. Une expérience remplaçant la règle par l'UCT classique appuie cette lecture : le retard se réduit à 0,26%, et l'intervalle de confiance inclut désormais zéro. Mais le signe reste négatif : même dans sa version corrigée, MCTS ne dépasse pas les redémarrages.

Les auteurs ont aussi établi une cartographie structurelle. Sur les workflows clairsemés et irréguliers, les redémarrages gagnent. Sur les workflows réguliers en couches, aucune différence n'apparaît. Sur les graphes denses, il reste presque rien à améliorer, car la solution de base est déjà proche de la limite.

Ce qu'il faut vérifier avant de construire un arbre

Pour les ingénieurs qui planifient des tâches dans des pipelines de données, pour l'entraînement de modèles ou dans des chaînes d'agents, la conclusion est terre à terre. Avant de déployer MCTS, mieux vaut lancer un list scheduler randomisé avec le même nombre d'évaluations. Cela s'implémente en une soirée et fournit un point de référence honnête. Si l'arbre ne le bat pas, sa complexité n'est pas justifiée.

Deuxième vérification : la part des solutions où la recherche s'est écartée du warm start. Si presque tous les résultats coïncident avec le point de départ, l'algorithme n'explore presque pas. Troisième point : la règle de sélection des branches elle-même, car c'est elle qui détermine si l'arbre sera diversifié.

Les auteurs énoncent eux-mêmes les limites de leur travail. L'expérience est synthétique, les graphes sont petits (jusqu'à 32 tâches) et le budget ne dépasse pas 2048. Aucune conclusion n'est tirée sur les budgets plus grands ni sur les workflows réels. Mais comme modèle de rigueur, le travail est utile : préenregistrement du protocole, budget égal et vérification indépendante de la validité des plannings. Pour les systèmes d'agents, où l'on introduit souvent des planificateurs pour le seul nom à la mode de l'algorithme, un tel contrôle est aussi nécessaire que les nouvelles méthodes.