Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping - Sorbonne Université
Conference Papers Year : 2023

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.

Dates and versions

hal-04163811 , version 1 (17-07-2023)

Identifiers

Cite

Chen Dang, Cristina Bazgan, Tristan Cazenave, Morgan Chopin, Pierre-Henri Wuillemin. Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping. 37th AAAI Conference on Artificial Intelligence, Feb 2023, Washington, D.C., United States. pp.12381-12389, ⟨10.1609/aaai.v37i10.26459⟩. ⟨hal-04163811⟩
58 View
0 Download

Altmetric

Share

More