Generalized Nested Rollout Policy Adaptation with Limited Repetitions

Tristan Cazenave

TL;DR

Standard Generalized Nested Rollout Policy Adaptation (GNRPA) wastes computational budget in its later iterations when the learned playout policy becomes overly deterministic and repeatedly generates the same solution. GNRPALR (GNRPA with Limited Repetitions) replaces fixed iteration loops with an early-stopping rule triggered when the current best score repeats too many times, delivering roughly an 8× speedup over GNRPA on long-horizon combinatorial optimization benchmarks.

What Problem Does This Paper Address?

Nested Rollout Policy Adaptation (NRPA) and its generalized variant (GNRPA) are recursive Monte Carlo search methods that optimize sequential decision problems by iteratively reinforcing weights on actions that lead to good solutions. At each recursion level, standard GNRPA executes a fixed number of iterations ($N$).

However, as the policy adapts, action probabilities rapidly peak around the best-found sequence. In later iterations of a level, the policy becomes too deterministic: lower-level searches repeatedly regenerate the exact same sequence rather than exploring alternative branches. As a result, the search gets trapped in local optima and wastes substantial computation.

Methods

The author introduces GNRPALR (Generalized Nested Rollout Policy Adaptation with Limited Repetitions):

  • Dynamic Stopping Condition: Replaces the outer for loop (which runs for a static $N$ iterations per level) with a while repetitions ≤ R loop.
  • Score Repetition Counter: Tracks how many times lower-level recursive calls return a solution matching bestScore.
  • If a returned solution equals bestScore, repetitions is incremented by 1.
  • If a strictly better score is found (score > bestScore), bestScore updates, and repetitions resets to 0.
  • Once repetitions exceeds a predefined threshold $R$, search at that level terminates early and passes control back up the recursion tree.
  • Heuristic Bias & Play: Retains GNRPA’s softmax-based move selection with prior bias $\beta_m$ ($p_m \propto e^{w_m + \beta_m}$) and online gradient-like policy weight adaptation.

Datasets

The algorithm was evaluated on three classic combinatorial search domains:

  1. Eterna100: A benchmark of 100 RNA secondary structure puzzles used for Inverse RNA Folding. A Transformer policy network pre-trained on the Rfam dataset provided the prior bias ($\beta_m$).
  2. TSPTW (Solomon Test Suite): Evaluated on instance rc204.1, widely regarded as the hardest benchmark instance in the test suite for the Traveling Salesman Problem with Time Windows.
  3. Weak Schur Problem: Finding maximal partitions of consecutive integers without additive triples ($x + y = z$) in the same subset, evaluated for dimension $n = 8$.

No new datasets were introduced.

Key Insights and Ideas

  • Repetition as an Exploration Metric: The author tested complex metrics like policy entropy to measure whether the search had collapsed into determinism. Counterintuitively, simply counting consecutive identical best-score returns was easier to tune and yielded better empirical performance.
  • Extreme Repetition Thresholds: In massive search spaces like Inverse RNA Folding or Weak Schur partitions, the chance of hitting the exact same score by accident during genuine exploration is vanishingly small. Setting $R = 0$ (stopping on the very first score repetition) provided the best results for those domains.
  • Time-Scaling Speedup: The speedup of GNRPALR over GNRPA is not constant—it grows with search time. As more time is allotted, standard GNRPA wastes increasingly larger fractions of its time trapped in converged policies, while GNRPALR exits converged levels and redirects budget to active exploration.

Key Results

  • Inverse RNA Folding (Eterna100): Using $R = 0$, GNRPALR solved 88 out of 100 puzzles within 4,096 seconds, whereas baseline GNRPA solved only 82. Across the benchmark, GNRPALR ran approximately 8× faster.
  • TSPTW (rc204.1): Using $R = 5$, GNRPALR achieved average path scores after ~1,250 seconds that baseline GNRPA required ~10,000 seconds to find, also demonstrating an ~8× speedup over 100 random seeds.
  • Weak Schur Problem ($n = 8$): Using $R = 0$, GNRPALR found higher-scoring partitions much faster than GNRPA over 100 runs. At 10,000 seconds of search time, the speedup over standard GNRPA was again roughly 8×.

Limitations and Future Work

  • Manual Hyperparameter Tuning: The repetition threshold $R$ currently requires empirical tuning per problem domain (e.g., $R=0$ for RNA folding and Weak Schur vs. $R=5$ for TSPTW).
  • Uniform Threshold Across Levels: The current formulation uses a single static $R$ across all nesting levels. Because higher nesting levels are exponentially more expensive than lower levels ($2^L$ scaling), the author suggests that level-dependent tuning (e.g., smaller $R$ at high levels to keep them exploratory, similar to Stabilized NRPA) could further improve efficiency.

Summary updated

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.
BibTeX
@inproceedings{cazenave2024generalized,
  author = {Tristan Cazenave},
  title = {{Generalized Nested Rollout Policy Adaptation with Limited Repetitions}},
  booktitle = {EWRL17},
  year = {2024},
  url = {https://openreview.net/forum?id=56VV0qxgyI},
}

Loading related content...

Figure