Stabilized Best-of-K Training for Combinatorial Optimization.

Neural combinatorial optimization often uses techniques like Leader Reward to improve training by emphasizing the best trajectories found during inference. This research introduces a subtle but effective extension to this approach. Instead of a simple binary distinction between "leader" and "non-leader" trajectories, the new method employs a stabilized rank signal, indexed by a sampling budget K. Using the POMO architecture and a fixed training schedule on the TSP-100 test set, the stabilized K=8 recipe demonstrated a reduction in realized Best-of-8 cost across all three paired training seeds compared to the Leader Reward baseline. However, the authors emphasize that this observation is specific to estimation and the decoder used, noting that Leader Reward performed better at sampled K=1 and under its original augmented-greedy protocol. The paper explicitly avoids claims of universal superiority or state-of-the-art performance, focusing on this specific observation.