Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping

Chen Dang, Cristina Bazgan, Tristan Cazenave, Morgan Chopin, Pierre-Henri Wuillemin

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.

Meta-NRPA execution flow using optimal stopping to warm-start promising runs.

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:

  1. $\epsilon$-greedy NRPA: Introduces stochasticity by occasionally selecting random moves.
  2. Forced Exploration: Prevents the algorithm from re-evaluating previously discovered solutions.
  3. 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.

Comparison of congestion levels between standard NRPA and Meta-NRPA across various network topologies.

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

Abstract

Nested Rollout Policy Adaptation (NRPA) is an approach using online learning policies in a nested structure. It has achieved a great result in a variety of difficult combinatorial optimization problems. In this paper, we propose Meta-NRPA, which combines optimal stopping theory with NRPA for warm-starting and significantly improves the performance of NRPA. We also present several exploratory techniques for NRPA which enable it to perform better exploration. We establish this for three notoriously difficult problems ranging from telecommunication, transportation and coding theory namely Minimum Congestion Shortest Path Routing, Traveling Salesman Problem with Time Windows and Snake-in-the-Box. We also improve the lower bounds of the Snake-in-the-Box problem for multiple dimensions.
BibTeX
@inproceedings{dang2023warm,
  author = {Chen Dang and Cristina Bazgan and Tristan Cazenave and Morgan Chopin and Pierre-Henri Wuillemin},
  title = {{Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26459},
}
Figure