MCTS przegrywa z prostszym algorytmem w szeregowaniu DAG

Nowe badanie podważa popularne przekonanie, że Monte Carlo Tree Search (MCTS) to skuteczna metoda szeregowania zadań w grafach DAG (directed-acyclic-graph workflows). Autor pracy, Yuyu Zhang, przeprowadził kontrolowany eksperyment, w którym porównał MCTS z dużo prostszym algorytmem – randomizowanym planerem listowym z restartami, bez drzewa przeszukiwań – przy identycznym budżecie obliczeniowym. Wynik jest jednoznaczny: prostsza metoda wygrywa.

Jak zauważa autor, większość dotychczasowych prac proponujących MCTS do szeregowania przepływów pracy nigdy nie przeprowadziła testu, który mógłby tę metodę obalić – czyli nie dała prostszej metodzie takiego samego wysiłku poszukiwawczego. Praca wypełnia tę lukę.

Kluczowe wnioski

• Przy budżecie 2048 ocenianych harmonogramów MCTS wypadł o 2,88% gorzej niż randomizowany planer z restartami (95% CI [-3,62%, -2,15%]), na 72 z 96 testowanych instancji z dodatnim potencjałem poprawy względem punktu odniesienia.
• Deficyt wydajności MCTS nie wynika z braku budżetu: na osobnej puli eksploracyjnej restarty samodzielnie poprawiły wynik o 1,85%, podczas gdy MCTS zyskał jedynie 0,24%.
• Aż 700 z 720 pierwszych wyników MCTS to po prostu „ciepły start”, który metoda otrzymała na wejściu, a nie efekt własnego przeszukiwania.
• Zamiana reguły selekcji na klasyczny algorytm UCT z podręcznika niemal całkowicie usunęła deficyt (-0,26%, 95% CI [-0,71%, +0,23%]), choć nie odwróciła jego znaku.
• Niezależny kontroler zweryfikował wszystkimi 768 harmonogramów z etapu potwierdzającego – wszystkie okazały się poprawne, z prawidłowym czasem zakończenia (makespan).

Jak przeprowadzono porównanie

Badanie zostało zaprojektowane jako preregistrowany eksperyment z zamkniętym przed zbieraniem danych planem analizy – metodologia zapożyczona z nauk eksperymentalnych, rzadko spotykana w publikacjach o algorytmach heurystycznych. Trzy metody rywalizowały na równych zasadach:

• metoda szeregowania oparta na MCTS, zgłoszona jako główne ramię eksperymentu,
• randomizowany planer listowy z restartami, bez drzewa przeszukiwań, jako grupa kontrolna,
• klasyczna implementacja UCT (podręcznikowy wariant MCTS) jako zarejestrowane ramię uzupełniające badane na tej samej domenie.

Wszystkie trzy warianty otrzymały identyczny budżet – tę samą liczbę zbudowanych i ocenionych kandydackich harmonogramów. To kluczowy element metodologii: w typowych publikacjach promujących MCTS porównania z prostszymi metodami rzadko są prowadzone przy ściśle równym nakładzie obliczeniowym, co ułatwia wykazanie przewagi bardziej skomplikowanego podejścia. Tutaj taka przewaga się nie pojawiła.

Domena testowa obejmowała syntetyczne grafy zadań o rozmiarach N równym 8, 16 lub 32 węzły, uruchamiane na 2–8 procesorach, przy budżetach sięgających do 2048 ocenianych harmonogramów.

Dlaczego MCTS traci do prostszego algorytmu

Analiza strukturalna wskazuje konkretny mechanizm porażki. Badana reguła selekcji w MCTS deterministycznie „zamyka się” na pierwszym rozwiniętym dziecku w drzewie, co sprawia, że kolejne próby pozostają ze sobą skorelowane. Tymczasem randomizowany planer z restartami czerpie zyski z „ogonów” rozkładu – czyli z rzadkich, ale lepszych rozwiązań, które pojawiają się dzięki niezależnym próbom losowym. Autor zaznacza przy tym ostrożnie, że bezpośredni związek przyczynowy między tym mechanizmem selekcji a finalnym czasem wykonania (makespan) pozostaje wnioskiem, nie dowodem w ścisłym sensie.

Co istotne, problem nie wynika z niedostatecznego budżetu obliczeniowego dla MCTS – na osobnej puli eksploracyjnej, gdzie metodzie dano więcej przestrzeni na samodoskonalenie, restarty i tak poprawiały się szybciej (1,85% vs 0,24% dla MCTS). Dodatkowo analiza wykazała, że przytłaczająca większość (700 z 720) pierwszych wyników generowanych przez MCTS to w praktyce jedynie punkt startowy, jakim metoda została zasilona, a nie rezultat jej własnego przeszukiwania drzewa.

Badanie zawiera też mapę strukturalną pokazującą, gdzie dokładnie drzewo przeszukiwań przestaje się opłacać:

• na rzadkich, nieregularnych przepływach pracy wygrywają restarty,
• na regularnych, warstwowych grafach zadań różnica między metodami jest niewykrywalna,
• na gęstych grafach nie ma w ogóle miejsca na poprawę wyniku, niezależnie od metody.

Gdy autor zastąpił badaną regułę selekcji klasycznym algorytmem UCT z podręcznika, większość deficytu MCTS zniknęła (-0,26%, przedział ufności obejmujący zero: [-0,71%, +0,23%]) – jednak znak różnicy nie został odwrócony na korzyść MCTS. Sugeruje to, że konkretna implementacja reguły selekcji ma istotne znaczenie dla wyników, choć nawet standardowy wariant nie pozwolił MCTS przewyższyć prostszej metody.

Znaczenie wyników i ich ograniczenia

Autor wyraźnie zastrzega, że wyniki ograniczają się do kontrolowanej, syntetycznej domeny testowej – grafów zadań o rozmiarach 8, 16 i 32 węzłów, na 2–8 procesorach, przy budżetach nieprzekraczających 2048 ocenianych harmonogramów. Praca nie formułuje żadnych twierdzeń dotyczących zachowania metod przy większych budżetach obliczeniowych.

Niemniej jednak wynik ma charakter preregistrowanego negatywnego rezultatu z otwartym protokołem ewaluacji – co jest rzadkością w badaniach nad algorytmami heurystycznymi, gdzie dominują publikacje pokazujące pozytywne wyniki nowej metody. Materiały towarzyszące pracy, w tym dane i kod, zostały zarchiwizowane na platformie Zenodo. Liczące 19 stron opracowanie zawiera 4 ryciny ilustrujące strukturalną mapę przewagi poszczególnych metod w zależności od typu grafu zadań.

Badanie wpisuje się w szerszy trend krytycznego podejścia do stosowania zaawansowanych metod przeszukiwania w planowaniu zadań obliczeniowych – podobnie jak w przypadku innych prac rewidujących podejścia do harmonogramowania zasobów w systemach rozproszonych, takich jak zmiany w schedulerze GPU wprowadzane przez Ai2.

Podsumowując, kontrolowane porównanie przy równym budżecie obliczeniowym pokazało, że popularna metoda MCTS może przegrywać z dużo prostszym randomizowanym planerem listowym na zadaniach szeregowania DAG – a różnica ta wynika ze specyfiki reguły selekcji, nie z braku zasobów obliczeniowych.