Abstract
Nested Rollout Policy Adaptation (NRPA) is a powerful Monte Carlo search algorithm for combinatorial optimization, yet it often suffers from poor initializations and premature convergence. This paper introduces Meta-NRPA, a novel framework that applies optimal stopping theory—specifically the "Secretary Problem" logic—to identify and "warm-start" only the most promising search paths. By pruning mediocre runs early and incorporating advanced exploration techniques such as $\epsilon$-greedy moves and dynamic learning rates, Meta-NRPA significantly outperforms standard NRPA. Experimental results demonstrate new world records for the Snake-in-the-Box problem and substantial performance gains in network routing and scheduling benchmarks.
Introduction
Combinatorial optimization problems, such as minimizing network congestion or optimizing delivery routes, are typically NP-hard, featuring search spaces of astronomical size. Nested Rollout Policy Adaptation (NRPA) has emerged as a popular heuristic for these tasks, learning through repeated "rollouts" to favor moves that yield higher scores. However, NRPA is prone to two significant pitfalls: "bad starts," where the algorithm wastes computational resources on suboptimal local minima, and "premature convergence," where it stops exploring before finding the global optimum.
To address these issues, we propose a "warm-starting" mechanism that treats the selection of search paths as an optimal stopping problem. This allows the algorithm to focus its computational budget on elite candidates, effectively bypassing the dead-ends that plague standard NRPA.
Methodology: The Meta-NRPA Framework
The core innovation of this work is Meta-NRPA, which utilizes the mathematical principles of the "Secretary Problem" to manage search initialization. In the classic Secretary Problem, one must decide whether to hire a candidate immediately after an interview without knowing the quality of future applicants. Meta-NRPA applies this to search levels: it executes a "lightweight" lower-level search and compares its performance against a historical distribution.
If an early run's performance exceeds a mathematically derived threshold (the top tier of candidates), the algorithm "warm-starts" a full-scale, higher-level search from that state. Otherwise, the run is terminated immediately. This pruning strategy allows for discarding 70-90% of mediocre runs, concentrating resources on high-potential paths.
Exploratory Enhancements
To further combat premature convergence, Meta-NRPA incorporates three exploratory techniques:
- $\epsilon$-greedy NRPA: Introduces stochasticity by occasionally selecting random moves.
- Forced Exploration: Prevents the algorithm from re-evaluating previously discovered solutions.
- Dynamic Learning Rate: Adjusts the learning pace based on the frequency of improvements, maintaining search "curiosity" over longer durations.
Experimental Setup
The effectiveness of Meta-NRPA was evaluated on three challenging benchmarks:
- Minimum Congestion Shortest Path Routing (MCSPR): Optimizing traffic flow across large-scale telecommunication topologies (IGen and Inet).
- Traveling Salesman Problem with Time Windows (TSPTW): Specifically the "rc204.1" instance, a notoriously difficult benchmark.
- Snake-in-the-Box (SITB): A problem in coding theory focused on finding the longest non-self-intersecting path in a multi-dimensional hypercube.
Key Results and Discussion
The Meta-NRPA approach yielded significant improvements across all tested domains. Most notably, the algorithm established new world records for the Snake-in-the-Box problem in dimensions 10 through 13. In Dimension 13, the best-known path length was increased from 2687 to 2709.
In network routing tasks, Meta-NRPA consistently achieved lower congestion scores than standard NRPA. As shown in the comparative analysis across various graph instances, Meta-NRPA not only finds better solutions but also exhibits significantly lower variance, indicating a more robust and reliable search process.
The success of this method hinges on the observation that early-stage performance is a strong statistical predictor of final solution quality. By leveraging this correlation, Meta-NRPA transforms the search process from a blind exploration into a targeted, elite-focused optimization.
Conclusion and Future Work
Meta-NRPA demonstrates that optimal stopping theory can be a powerful tool for enhancing Monte Carlo search algorithms. While the method requires some parameter tuning (e.g., the $\epsilon$ in $\epsilon$-greedy) and assumes a correlation between early and late-stage performance, its ability to break long-standing records highlights its potential. Future research will explore applying these techniques to other search variants and broader classes of combinatorial problems in logistics and bioinformatics.
Summary updated