AAAI 2026technical0 citations
Nested Depth Search
Junkang Li, Tristan Cazenave, Swann Legras, Arthur Queffelec, Veronique Ventos
Abstract
Nested Monte Carlo Search (NMCS) has numerous applications, ranging from chemical retrosynthesis to quantum circuit design. We propose a generalization of NMCS that we named Nested Depth Search (NDS), in which a fixed depth search is used during a higher-level playout to generate the states sent to lower-level exploration. We establish the runtime of NDS and provide algorithms to compute the exact probability distribution of sequences generated by NDS. Experiments with the Set Cover problem and the Multiple Sequence Alignment problem show that NDS outperforms NMCS with the same time budget.
BibTeX
@inproceedings{aaai2026_nesteddepthsearc,
title = {Nested Depth Search},
author = {Junkang Li and Tristan Cazenave and Swann Legras and Arthur Queffelec and Veronique Ventos},
booktitle = {AAAI 2026},
year = {2026}
}