The Pulse

Uno studio sui DAG rileva che MCTS resta indietro del 2,88% rispetto alle ripartenze casuali

Uno studio controllato pubblicato su arXiv ha rilevato che, a parità di valutazioni, un algoritmo di schedulazione basato su Monte Carlo Tree Search ha prodotto pianificazioni peggiori del 2,88% rispetto alla schedulazione a lista con ripar

AI.info Team · Scritto con l’IA · 2026-10-12

A parità di 2.048 pianificazioni valutate, un algoritmo di schedulazione basato su Monte Carlo Tree Search (MCTS) ha ottenuto risultati peggiori del 2,88% rispetto a un più semplice metodo con ripartenze casuali, secondo uno studio controllato pubblicato su arXiv l’8 ottobre. Il confronto ha riguardato 72 istanze sintetiche di flussi di lavoro, tenute fuori dalla fase precedente, nelle quali i ricercatori hanno riscontrato margini di miglioramento per ciascuno dei due metodi; l’intervallo di confidenza al 95% riportato indicava risultati peggiori per MCTS compresi tra il 3,62% e il 2,15%. Il risultato mette in discussione le affermazioni su questo specifico algoritmo di schedulazione, non su MCTS nel suo complesso.

Un unico budget, due strategie di ricerca

Yuyu Zhang ha confrontato un algoritmo di schedulazione MCTS con uno basato su liste e ripartenze casuali, che non usa alcun albero di ricerca. A ciascun metodo è stato assegnato lo stesso numero di pianificazioni candidate da costruire e valutare. Il metodo di controllo con ripartenze sceglieva ripetutamente un’attività a caso tra quelle pronte per essere eseguite, poi la assegnava al processore sul quale sarebbe terminata prima.

Secondo l’articolo, il piano di analisi è stato fissato prima della raccolta dei dati e un verificatore indipendente ha controllato tutte le 768 pianificazioni delle esecuzioni nella fase di conferma. I ricercatori hanno confrontato i risultati con un portafoglio, definito per ciascuna istanza, di quattro euristiche di schedulazione: HEFT, CPOP, PEFT e OCT. Hanno escluso dal confronto principale 24 delle 96 istanze tenute fuori dalla fase precedente perché avevano già raggiunto il limite inferiore dello studio, senza lasciare alcun margine di miglioramento misurabile.

«Non sosteniamo che MCTS non possa essere utile nella schedulazione, che questa implementazione rappresenti tutti gli algoritmi di schedulazione MCTS o che questi risultati sintetici si applichino ai flussi di lavoro in produzione.»

Yuyu Zhang, «Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study»

Il vantaggio iniziale derivava dalla soluzione di partenza

Il metodo MCTS partiva da una pianificazione CPOP; il metodo di controllo con ripartenze no. Alla prima pianificazione valutata, questo dava un vantaggio a MCTS, ma l’articolo riferisce che 700 dei 720 primi risultati in un insieme separato usato per l’esplorazione coincidevano semplicemente con la soluzione iniziale fornita. All’aumentare del budget, il metodo di controllo migliorava di più: su quell’insieme, le ripartenze hanno ottenuto un miglioramento dell’1,85% rispetto al punto di partenza, contro lo 0,24% di MCTS.

Gli autori hanno condotto anche un confronto supplementare in cui al metodo di controllo veniva assegnata la stessa soluzione iniziale CPOP. In quel confronto, MCTS è rimasto indietro del 2,93%. L’articolo avverte però che l’esperimento confronta due procedure complete: non isola l’effetto dell’albero in sé, poiché i metodi differiscono anche nel modo in cui effettuano la ricerca e gestiscono l’assegnazione ai processori.

I risultati dipendono dalla struttura del DAG

Le ripartenze casuali hanno prevalso nelle strutture di flusso di lavoro sparse e irregolari, comprese le istanze fork-join e quelle ampie e sparse. Lo studio non ha rilevato differenze nei flussi di lavoro regolari a strati, mentre le istanze dense sono rimaste fuori dal confronto principale perché l’euristica iniziale raggiungeva già il limite inferiore. Gli autori descrivono questo andamento nelle famiglie di istanze esaminate, senza considerarlo una prova che una singola caratteristica strutturale determini il risultato.

Anche la regola di selezione dello studio per MCTS si è comportata diversamente da una ricerca nell’albero che esplora ampiamente le alternative. Gli autori hanno misurato una concentrazione delle visite sul primo nodo figlio espanso; precisano che il legame tra questo comportamento e lo svantaggio nella durata complessiva della pianificazione resta un’inferenza. In una successiva verifica con UCT nella sua formulazione classica, la differenza misurata si è ridotta allo 0,26% a sfavore di MCTS, ma l’intervallo di confidenza comprendeva lo zero: in quel confronto, quindi, lo studio non ha stabilito quale dei due metodi prevalesse.

Un risultato limitato ai test sintetici

Il benchmark ha usato DAG sintetici con 8, 16 o 32 attività e da 2 a 8 processori, con budget di ricerca limitati a 2.048 pianificazioni. L’articolo non avanza conclusioni sui flussi di lavoro in produzione o su budget più ampi, e l’esperimento principale non chiarisce se altre configurazioni MCTS otterrebbero risultati migliori. La conclusione centrale è più circoscritta: in questo benchmark, a parità del numero di pianificazioni valutate previsto dai test, le ripartenze casuali hanno superato la configurazione MCTS studiata nelle istanze con margini di miglioramento.