Abstract
In single-player deterministic path search, the objective is to find the single best solution rather than an average outcome. Traditional Monte-Carlo Tree Search (MCTS) variants, designed for stochastic or adversarial environments, often struggle in this context due to "distribution drift" and a focus on mean values. We present PL-MCTS, a novel version of MCTS tailored for single-player optimization. By replacing standard value-based selection with the Plackett-Luce model—a probabilistic ranking model—the algorithm identifies branches likely to yield extreme values. Our evaluation across complex scheduling, routing, and puzzle domains demonstrates that PL-MCTS consistently outperforms state-of-the-art methods.
Introduction
Finding the optimal path through a massive, complex tree of possibilities is a fundamental challenge in artificial intelligence. Applications range from software product line configuration to industrial job scheduling. While Monte-Carlo Tree Search (MCTS) is a standard tool for such problems, its original design for games like Go or Chess emphasizes the average outcome of a move. In single-player optimization, however, the goal is to find the "needle in the haystack"—the single best leaf node.
Standard MCTS variants like UCT (Upper Confidence Bound applied to Trees) often fail in these scenarios. As the search progresses, the scores returned from a branch change, a phenomenon known as distribution drift. Quantitative models that rely on averaging these scores can become "confused," leading to inefficient exploration. This paper proposes a shift from quantitative value estimation to qualitative ranking using the Plackett-Luce model.
Methodology: The Plackett-Luce Tree Policy
The core innovation of PL-MCTS is the replacement of numeric value estimation with a probabilistic ranking model. Instead of asking "what is the expected value of this node?", the algorithm asks "what is the probability that this node is the best among its siblings?"
The Plackett-Luce (PL) Model
The PL model is a statistical framework for rankings that assigns a "skill parameter" to each child node. The probability of a node being ranked first is proportional to its skill. By leveraging Extreme Value Theory (EVT), the authors demonstrate that if potential improvements in a branch follow a Gumbel distribution, the selection criteria naturally simplifies to the Plackett-Luce model.
Implementation Details
To populate the PL model, the algorithm uses a bootstrapping technique. It takes sub-samples of past observations for each child node, calculates a statistic (such as the mean or minimum), and ranks the children based on these samples. Furthermore, a resource-aware exploration function ($\gamma$) is introduced to control the influence of the PL model over time, ensuring broad initial exploration followed by commitment to promising branches as the computational budget depletes.
Experimental Evaluation
The performance of PL-MCTS was evaluated on three challenging deterministic domains where informative heuristics are typically unavailable:
- Timed TSP with Breaks (TTSPB): A Traveling Salesperson Problem with time-varying travel costs and mandatory rest breaks.
- Job Scheduling with Variable Release Dates (VRDJS): Minimizing weighted flowtime across multiple machines with flexible job arrival times.
- SameGame: A classic single-player tile-matching puzzle.
Results
PL-MCTS was compared against seven state-of-the-art algorithms, including UCT, SP-UCT, and TAG. The results, summarized in the table below, highlight the algorithm's robustness and efficiency.
In the TTSPB and VRDJS benchmarks, PL-MCTS (specifically the PL-MCTS-MEAN variant) consistently achieved the best relative scores, often by a significant margin. In the SameGame domain, PL-MCTS variants remained highly competitive, with PL-MCTS-MEAN emerging as the top-performing MCTS-based approach on $15 \times 15$ boards.
Discussion and Key Insights
The success of PL-MCTS stems from several key factors:
- Qualitative Robustness: By focusing on rankings rather than absolute scores, the algorithm is immune to the scale of the cost function, eliminating the need for arbitrary normalization.
- Extreme-Value Orientation: Unlike "mean-oriented" MCTS variants, PL-MCTS explicitly searches for the branch with the highest probability of containing the global minimum.
- Handling Drift: Relative rankings are inherently more robust to the distribution drift found in evolving search trees than absolute value estimates.
While the computational cost of fitting the Plackett-Luce model via Maximum Likelihood Estimation is higher than simple averaging, the performance gains in complex domains justify the overhead. Future work may involve extending this ranking-based approach to standard Markov Decision Processes (MDPs) and exploring automated methods for selecting preference kernels.
Conclusion
PL-MCTS represents a significant advancement in single-player MCTS. By shifting the focus from average values to probabilistic rankings, it provides a more effective mechanism for navigating complex search spaces to find optimal solutions. Its dominance in scheduling and routing tasks underscores its potential for real-world optimization problems.
Summary updated