Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping
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.
Cite
Text
Dang et al. "Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I10.26459Markdown
[Dang et al. "Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/dang2023aaai-warm/) doi:10.1609/AAAI.V37I10.26459BibTeX
@inproceedings{dang2023aaai-warm,
title = {{Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping}},
author = {Dang, Chen and Bazgan, Cristina and Cazenave, Tristan and Chopin, Morgan and Wuillemin, Pierre-Henri},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2023},
pages = {12381-12389},
doi = {10.1609/AAAI.V37I10.26459},
url = {https://mlanthology.org/aaai/2023/dang2023aaai-warm/}
}