몬테카를로 트리 탐색(MCTS)은 인공지능 분야, 특히 게임 AI나 복잡한 의사결정 문제 해결에 널리 사용되는 강력한 알고리즘입니다. 이러한 성공에 힘입어, MCTS는 데이터 처리 파이프라인이나 클라우드 컴퓨팅 작업과 같은 복잡한 방향성 비순환 그래프(DAG) 워크플로우 스케줄링에도 자주 제안되어 왔습니다. 그러나 최근 위위 장(Yuyu Zhang)의 연구는 이러한 통념에 도전하며, MCTS가 동일한 탐색 예산(동일한 수의 후보 스케줄 생성 및 평가) 하에서 훨씬 단순한 무작위 재시작 리스트 스케줄링(Randomized-Restart List Scheduling) 방식보다 오히려 비효율적일 수 있다는 충격적인 결과를 발표했습니다.
이 연구는 엄격하게 통제된 프로토콜 하에 세 가지 스케줄링 방법을 비교했습니다. 주된 비교 대상은 MCTS 기반 스케줄링 방법과 탐색 트리가 없는 무작위 재시작 리스트 스케줄러였습니다. 추가적으로 교과서적인 UCT(Upper Confidence Bound 1 applied to Trees) MCTS 방식도 포함되었습니다. 분석 계획은 데이터 수집 전에 확정되었고, 독립적인 검증을 거쳐 모든 768개의 스케줄이 유효함을 확인했습니다. 핵심 결과는 2048개의 스케줄 평가 예산에서 MCTS가 무작위 재시작 방식보다 2.88% 더 나쁜 성능을 보였다는 것입니다. 이는 단순히 예산 부족 때문이 아니었습니다. 별도의 탐색 풀에서 무작위 재시작 방식이 1.85% 개선되는 동안 MCTS는 0.24%만 개선되었고, MCTS의 초기 결과 대부분은 단순히 주어진 웜 스타트(warm start)에 불과했습니다. 연구는 MCTS의 특정 선택 규칙이 첫 번째 확장된 자식 노드에 결정론적으로 고정되어 탐색의 다양성을 저해하는 반면, 무작위 재시작은 더 넓은 범위에서 이득을 얻는다고 지적합니다. 또한, MCTS가 희소하고 불규칙한 워크플로우에서는 무작위 재시작에 비해 불리하며, 규칙적인 계층형 워크플로우에서는 차이가 없었고, 밀집된 워크플로우에서는 개선의 여지가 거의 없었습니다. 표준 UCT 규칙으로 변경했을 때는 성능 저하가 대부분 사라졌지만(–0.26%), 여전히 무작위 재시작보다 우수하지는 않았습니다.
이 연구 결과는 DAG 워크플로우 스케줄링에 MCTS를 적용할 때 신중해야 함을 시사합니다. 단순히 복잡한 알고리즘이 더 나을 것이라는 가정 대신, 문제의 특성과 탐색 예산을 고려하여 더 단순하고 효율적인 방법을 선택하는 것이 중요할 수 있습니다. 특히, MCTS의 탐색 전략이 특정 유형의 워크플로우나 제한된 예산 환경에서는 오히려 독이 될 수 있음을 보여줍니다. 이는 학계와 산업계 모두에서 MCTS의 적용 범위를 재평가하고, 각 문제에 최적화된 스케줄링 알고리즘을 탐색하는 데 중요한 통찰을 제공할 것입니다. 복잡한 시스템의 효율성을 극대화하기 위해서는 알고리즘의 본질적인 특성과 문제 도메인 간의 깊이 있는 이해가 필수적입니다.