Abstract
Generalized Nested Rollout Policy Adaptation (GNRPA) is a Monte Carlo search algorithm for optimizing a sequence of choices. We propose to improve on GNRPA by avoiding too deterministic policies that find again and again the same sequence of choices. We do so by limiting the number of repetitions of the best sequence found at a given level. Experiments show that it improves the algorithm for three different combinatorial problems: Inverse RNA Folding, the Traveling Salesman Problem with Time Windows and the Weak Schur problem.
Introduction
Monte Carlo Search algorithms, such as those powering AlphaZero, are essential for navigating massive search spaces in combinatorial optimization. A prominent family of these algorithms is Nested Rollout Policy Adaptation (NRPA) and its generalized version, GNRPA. These algorithms operate by recursively searching and adapting a policy—a set of weights for moves—to favor the best sequences discovered during the search.
However, GNRPA faces a significant "stagnation" challenge. As the policy learns and reinforces the best sequence at a specific search level, it becomes increasingly deterministic. In the later stages of a search, the algorithm often spends substantial computational resources repeatedly finding the exact same "best" sequence rather than exploring alternative branches that might lead to superior global optima. This leads to diminishing returns and inefficient use of search time.
Methodology: GNRPALR
To address the stagnation problem, we introduce GNRPALR (GNRPA with Limited Repetitions). The core modification is simple yet effective: it replaces the fixed-iteration search at each level with a dynamic stopping condition.
In standard GNRPA, each level of the search runs for a fixed number of iterations ($N$). In each iteration, it performs playouts, identifies the best sequence, and updates the policy weights using a softmax function combined with a heuristic bias.
In GNRPALR, the search at a given level continues only until the best score has been repeated a predefined number of times, denoted by the threshold $R$. If the algorithm finds the same "best score" $R$ times, it assumes the policy has become overly deterministic and terminates the search at that level early. This forces the algorithm to backtrack and explore different high-level branches of the search tree, maintaining exploratory pressure.
Experimental Evaluation
The effectiveness of GNRPALR was evaluated across three distinct and challenging combinatorial domains:
1. Inverse RNA Folding (Eterna100)
The Eterna100 benchmark consists of 100 RNA secondary structure puzzles designed by human experts. These puzzles are notoriously difficult for standard algorithms. The goal is to find a sequence of nucleotides that folds into a specific target structure.
2. Traveling Salesman Problem with Time Windows (TSPTW)
We tested the algorithm on the rc204.1 instance from the Solomon test suite. This problem requires finding the shortest path that visits a set of cities within specific time windows, making it significantly more constrained than the standard TSP.
3. Weak Schur Numbers
This mathematical problem involves partitioning consecutive integers into sets such that no set contains the sum of two of its elements. We focused on finding lower bounds for dimension 8.
Results and Discussion
The results across all benchmarks demonstrate that GNRPALR significantly outperforms the standard GNRPA:
- Speedup: In the Inverse RNA Folding task, GNRPALR was 8 times faster than GNRPA, solving 88 out of 100 puzzles in 4,096 seconds compared to 82 solved by the standard version.
- Efficiency: For TSPTW, GNRPA required approximately 8 times more computing time to achieve the same average score as GNRPALR.
- The Role of $R$: The optimal value for the repetition threshold $R$ varied by problem but remained small (typically between 0 and 5). For RNA folding, $R=0$ was found to be optimal, suggesting that the search should immediately move to a different branch as soon as a repeat is detected.
- Scalability: The performance advantage of GNRPALR over GNRPA increases as more search time is allocated. This makes the modification particularly valuable for long-running optimization tasks where exploration is critical.
Conclusion
GNRPALR offers a lightweight and highly effective solution to the stagnation problem in nested Monte Carlo search. By simply limiting the number of repetitions of the best sequence, the algorithm maintains a better balance between exploitation and exploration. The resulting 8x speedup on complex benchmarks highlights the potential of this approach for a wide range of combinatorial optimization problems.
Summary updated