# Pareto-NRPA: A Novel Monte-Carlo Search Algorithm for Multi-Objective Optimization

arXiv: https://arxiv.org/abs/2507.19109 · HTML: https://mlsanity.com/paper/2507.19109/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 25 Jul 2025.

## Builds on (most cited first, 11 of 11)

- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search](https://mlsanity.com/paper/2001.00326/) (2020)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [pymoo: Multi-objective Optimization in Python](https://mlsanity.com/paper/2002.04504/) (2020)
- [Efficient Multi-objective Neural Architecture Search via Lamarckian Evolution](https://mlsanity.com/paper/1804.09081/) (2018)
- [Urban Driving with Multi-Objective Deep Reinforcement Learning](https://mlsanity.com/paper/1811.08586/) (2018)
- [Generalized Nested Rollout Policy Adaptation](https://mlsanity.com/paper/2003.10024/) (2020)
- [Pareto Monte Carlo Tree Search for Multi-Objective Informative Planning](https://mlsanity.com/paper/2111.01825/) (2021)
- [Stabilized Nested Rollout Policy Adaptation](https://mlsanity.com/paper/2101.03563/) (2021)
- [Generalized Nested Rollout Policy Adaptation with Limited Repetitions](https://mlsanity.com/paper/2401.10420/) (2024)
- [Solving the HP model with Nested Monte Carlo Search](https://mlsanity.com/paper/2301.09533/) (2023)

## Abstract (arXiv)

We introduce Pareto-NRPA, a new Monte-Carlo algorithm designed for multi-objective optimization problems over discrete search spaces. Extending the Nested Rollout Policy Adaptation (NRPA) algorithm originally formulated for single-objective problems, Pareto-NRPA generalizes the nested search and policy update mechanism to multi-objective optimization. The algorithm uses a set of policies to concurrently explore different regions of the solution space and maintains non-dominated fronts at each level of search. Policy adaptation is performed with respect to the diversity and isolation of sequences within the Pareto front. We benchmark Pareto-NRPA on two classes of problems: a novel bi-objective variant of the Traveling Salesman Problem with Time Windows problem (MO-TSPTW), and a neural architecture search task on well-known benchmarks. Results demonstrate that Pareto-NRPA achieves competitive performance against state-of-the-art multi-objective algorithms, both in terms of convergence and diversity of solutions. Particularly, Pareto-NRPA strongly outperforms state-of-the-art evolutionary multi-objective algorithms on constrained search spaces. To our knowledge, this work constitutes the first adaptation of NRPA to the multi-objective setting.