Stabilized Best-of-$K$ Training for Neural Combinatorial Optimization

# The question
Source: [https://arxiv.org/html/2608.00296](https://arxiv.org/html/2608.00296)
SUMMARY

Leader Reward modifies POMO training to emphasize the best trajectory produced by repeated inference\. We test a narrow extension: replace its binary leader/non\-leader distinction with a stabilized rank signal indexed by a sampling budgetKK\. With the POMO architecture, 3,050\-epoch schedule, and TSP\-100 test set held fixed, the Leader Reward reimplementation obtains7\.76627\.7662under 100\-start, 8\-augmentation greedy decoding, matching the reported7\.7667\.766at its displayed precision\. Under independent sampling, the stabilizedK=8K=8recipe lowers realized Best\-of\-8 cost in all three paired training seeds:7\.79447\.7944versus7\.81367\.8136\. This observation is estimation\-only and decoder\-specific: three seeds are below the six\-seed testing floor, Leader Reward is better at sampledK=1K=1, and it remains slightly better under its original augmented\-greedy protocol\. We make no unbiased\-estimator, universal superiority, or state\-of\-the\-art claim\.

POMO solves an instance from multiple starting nodes and trains the resulting trajectories with a shared\-baseline policy gradient\(Kwonet al\.,[2020](https://arxiv.org/html/2608.00296#bib.bib1)\)\. Leader Reward\(Wanget al\.,[2024](https://arxiv.org/html/2608.00296#bib.bib3)\)observes that deployment retains the best solution found within an inference budget, whereas the standard POMO update values the entire multi\-start batch\. It increases the current leader’s weight during main training and uses leader\-only fine\-tuning\.

We ask whether training should distinguish not only the current leader, but also trajectories that can become the best member of a size\-KKgroup when deployment draws exactlyKKindependent trajectories\. The motivating target is

JK​\(θ\)=𝔼τ1,…,τK∼iidπθ​\[max1≤j≤K⁡R​\(τj\)\]\.J\_\{K\}\(\\theta\)=\\mathbb\{E\}\_\{\\tau\_\{1\},\\ldots,\\tau\_\{K\}\\stackrel\{\{\\scriptstyle\\mathrm\{iid\}\}\}\{\{\\sim\}\}\\pi\_\{\\theta\}\}\\left\[\\max\_\{1\\leq j\\leq K\}R\(\\tau\_\{j\}\)\\right\]\.\(1\)The experiment changes only the trajectory\-weight rule of the same POMO policy\. It is a reproduction\-and\-extension study of Leader Reward, not a new architecture or inference search method\.

## What changes relative to Leader Reward

### Leader Reward’s update

For one instance, letR1,…,RnR\_\{1\},\\ldots,R\_\{n\}be rewards from thennPOMO starts,R¯=n−1​∑iRi\\bar\{R\}=n^\{\-1\}\\sum\_\{i\}R\_\{i\},ai=Ri−R¯a\_\{i\}=R\_\{i\}\-\\bar\{R\}, andℓ=arg⁡maxi⁡Ri\\ell=\\arg\\max\_\{i\}R\_\{i\}\. With the main\-phase multiplierα=40\\alpha=40, the effective trajectory weights inWanget al\.\([2024](https://arxiv.org/html/2608.00296#bib.bib3)\)are

wiLR=\{ai/α,i≠ℓ,aℓ,i=ℓ\.w\_\{i\}^\{\\mathrm\{LR\}\}=\\begin\{cases\}a\_\{i\}/\\alpha,&i\\neq\\ell,\\\\ a\_\{\\ell\},&i=\\ell\.\\end\{cases\}\(2\)Our implementation uses an additive leader coefficient3939and divides every weight by4040, which is algebraically identical\. In the final two training phases, only the leader receives a nonzero weight\.

### The tested budget\-indexed extension

Our arm retainsn=100n=100POMO starts and fixesK=8K=8\. Sort an instance’s rewards asR\(1\)≤⋯≤R\(n\)R\_\{\(1\)\}\\leq\\cdots\\leq R\_\{\(n\)\}\. Before stabilization, the implemented rank\-gap weight is

u\(i\)=\{0,i<K,\(nK\)−1​∑m=Ki\(m−2K−2\)​\(R\(i\)−R\(m−1\)\),i≥K\.u\_\{\(i\)\}=\\begin\{cases\}0,&i<K,\\\\\[4\.2679pt\] \\displaystyle\\binom\{n\}\{K\}^\{\-1\}\\sum\_\{m=K\}^\{i\}\\binom\{m\-2\}\{K\-2\}\\bigl\(R\_\{\(i\)\}\-R\_\{\(m\-1\)\}\\bigr\),&i\\geq K\.\\end\{cases\}\(3\)This distributes credit by rank and budget rather than assigning a special role only to the current leader\.

Two transformations define the recipe actually tested\. Letδ=0\.01​\(R\(n\)−R\(1\)\)\\delta=0\.01\(R\_\{\(n\)\}\-R\_\{\(1\)\}\)\. Fori≥Ki\\geq K, the summed gap in Equation \([3](https://arxiv.org/html/2608.00296#S2.E3)\) is floored by replacing it with the larger of its observed value andδ​∑m=Ki\(m−2K−2\)\\delta\\sum\_\{m=K\}^\{i\}\\binom\{m\-2\}\{K\-2\}\. The resulting vector𝒖~\\tilde\{\\boldsymbol\{u\}\}is standardized within each instance:

wistab=u~i−u~¯s​\(𝒖~\)\+10−8,ℒstab=−∑i=1nstopgrad⁡\(wistab\)​log⁡πθ​\(τi\)\.w\_\{i\}^\{\\mathrm\{stab\}\}=\\frac\{\\tilde\{u\}\_\{i\}\-\\overline\{\\tilde\{u\}\}\}\{s\(\\tilde\{\\boldsymbol\{u\}\}\)\+10^\{\-8\}\},\\qquad\\mathcal\{L\}\_\{\\mathrm\{stab\}\}=\-\\sum\_\{i=1\}^\{n\}\\operatorname\{stopgrad\}\(w\_\{i\}^\{\\mathrm\{stab\}\}\)\\log\\pi\_\{\\theta\}\(\\tau\_\{i\}\)\.\(4\)The floor and standardization alter the original score weights\. “Stabilized Best\-of\-KK” therefore names an engineering recipe, not an unbiased Max@KKestimator\. POMO also enumerates distinct starting nodes during training, whereas Equation \([1](https://arxiv.org/html/2608.00296#S1.E1)\) and the headline evaluation use independent single\-trajectory samples\. The implemented update is a Best\-of\-KK\-motivated surrogate, not a proof of the exact gradient of Equation \([1](https://arxiv.org/html/2608.00296#S1.E1)\)\.

### Context and attribution

Best\-of\-KKand order\-statistic policy optimization are established ideas\. PKPO\(Walder and Karkhanis,[2025](https://arxiv.org/html/2608.00296#bib.bib4)\)gives pass@KKand continuous\-reward Max@KKestimators with variance reduction; related formulations appear in MaxPO\(Takashiroet al\.,[2026](https://arxiv.org/html/2608.00296#bib.bib5)\)and OrderGrad\(Parmaset al\.,[2026](https://arxiv.org/html/2608.00296#bib.bib6)\)\. Poppy\(Grinsztajnet al\.,[2023](https://arxiv.org/html/2608.00296#bib.bib2)\)uses a winner\-takes\-all objective across a population of policies, a different architectural setting\. Our contribution is the controlled Leader Reward extension and its observed dependence on the deployment budget, not the generic objective or estimator\.

## Evaluation card

For each checkpoint and test instance, evaluation draws a fresh pool of 2,048 independent trajectories\. Separately at eachKK, the pool is partitioned into disjoint size\-KKblocks; the best cost in each block is averaged\. The augmented\-greedy endpoint instead considers 800 structured candidates and is reported as a reproduction check, not an equal\-budget comparison with sampled Best\-of\-KK\.

The fixed instances and within\-instance blocks reduce evaluation noise but are not extra training replications\. We report all three paired rows, their mean, and a descriptive seed\-level BCa interval\. With three nonzero pairs, the smallest attainable one\-sided signed\-rankpp\-value is1/81/8\. All reported outputs are finite and no defensive weight clamp was configured; the missing training telemetry prevents a stronger numerical\-stability statement\.

## Finding 1 — the Leader Reward endpoint reproduces

Under 100\-start, 8\-augmentation greedy decoding, the three\-seed Leader Reward mean is7\.76627\.7662, matching the published7\.7667\.766at its displayed precision\. This is a direct check on the baseline and test protocol\. The stabilized arm obtains7\.76697\.7669and is slightly worse in this regime\.

## Finding 2 — sampled Best\-of\-8 improves in all three seeds

The stabilized arm has lower sampled Best\-of\-8 cost in every paired seed \(Table[1](https://arxiv.org/html/2608.00296#S5.T1)\)\. Its seed mean is7\.79447\.7944, compared with7\.81367\.8136for Leader Reward\. The paired difference, Leader Reward minus stabilized, is\+0\.0193\+0\.0193, with a descriptive BCa interval of\[\+0\.0068,\+0\.0257\]\[\+0\.0068,\+0\.0257\]\. This is a0\.247%0\.247\\%cost reduction relative to Leader Reward\. Relative to the common7\.7657\.765Concorde reference, the remaining gap changes from0\.626%0\.626\\%to0\.378%0\.378\\%, a39\.7%39\.7\\%reduction\. None of these summaries is a confirmatory significance result\.

Table 1:Paired realized Best\-of\-8 sampling cost\. Positive differences favor the stabilized recipe\.
## Finding 3 — the advantage depends on sampling budget

The seed mean favors the stabilized arm fromK=2K=2throughK=128K=128\(Figure[1](https://arxiv.org/html/2608.00296#S6.F1)and Table[2](https://arxiv.org/html/2608.00296#S6.T2)\), but the advantage contracts asKKgrows\. Leader Reward is better atK=1K=1\. AtK=128K=128, the stabilized mean remains lower while seed 1 reverses by0\.00110\.0011\. These secondary results describe the curve; they are not separate confirmatory tests\.

Table 2:Seed\-mean realized Best\-of\-KKsampling cost\. Lower is better\.![Refer to caption](https://arxiv.org/html/2608.00296v1/figures/realized_bestofk_curve.png)Figure 1:Realized sampled Best\-of\-KKTSP\-100 cost\. Points are means over three training seeds; bands show one population standard deviation across seeds\. Lower is better\.
## Finding 4 — the gain does not transfer to every decoder

The stabilized policy improves one greedy trajectory and sampled Best\-of\-8, but Leader Reward is lower for sampled Best\-of\-1 and the original augmented\-greedy protocol \(Table[3](https://arxiv.org/html/2608.00296#S7.T3)\)\. Under augmented greedy, Leader Reward is better in all three seeds by0\.00050\.0005–0\.00090\.0009\. Candidate budgets differ across rows; the rows are distinct deployment questions rather than equal\-compute comparisons\.

Table 3:Seed\-mean TSP\-100 cost under distinct deployment protocols\.
## What this evidence does not establish

CLAIM BOUNDARY

Statistical confirmationThree training seeds establish a repeated observation, not the planned six\-seed confirmatory result\. The BCa interval is fragile at this sample size, and the experiment was not externally preregistered\.GeneralityThe evidence covers one POMO implementation and Euclidean TSP\-100\. It does not cover CVRP, FFSP, other POMO families, or out\-of\-distribution instances\.Estimator identityGap flooring, standardization, and the distinct\-start training law prevent an unbiased\-gradient interpretation\. The experiment does not isolate which stabilizer causes the observed change\.Comparator coverageThe campaign has no newly trained vanilla POMO, objective\-faithful Max@KKarm, or component ablations\.Universal superiorityLeader Reward remains better at sampledK=1K=1and under its original augmented\-greedy protocol\. No NCO state\-of\-the\-art claim is made\.

## Artifacts and reproducibility

The arXiv source package includes the complete per\-seed sampling curve, greedy and augmented\-greedy rows, evaluation runtimes, the figure\-generation script, and an artifact manifest\. Frozen repository artifacts record the checkpoints, configuration, hashes, and per\-instance evaluation outputs\.

BOTTOM LINE

On this three\-seed TSP\-100 study, a stabilizedK=8K=8rank\-gap signal is a promising extension of Leader Reward when deployment samples a modest number of independent candidates\. The result is specific to that deployment regime and is not evidence of a generally better POMO policy\.

## References

- Winner takes it all: training performant RL populations for combinatorial optimization\.InAdvances in Neural Information Processing Systems,Vol\.36\.External Links:2210\.03475Cited by:[§2\.3](https://arxiv.org/html/2608.00296#S2.SS3.p1.3)\.
- Y\. Kwon, J\. Choo, B\. Kim, I\. Yoon, Y\. Gwon, and S\. Min \(2020\)POMO: policy optimization with multiple optima for reinforcement learning\.InAdvances in Neural Information Processing Systems,Vol\.33\.External Links:2010\.16011Cited by:[§1](https://arxiv.org/html/2608.00296#S1.p1.1)\.
- P\. Parmas, Y\. Kim, K\. Matsutani, S\. Takashiro, S\. Nishimori, T\. Kojima, Y\. Iwasawa, and Y\. Matsuo \(2026\)OrderGrad: optimizing beyond the mean with order\-statistic policy gradient estimation\.External Links:2606\.06096Cited by:[§2\.3](https://arxiv.org/html/2608.00296#S2.SS3.p1.3)\.
- S\. Takashiro, S\. Nishimori, P\. Parmas, Y\. Kim, K\. Matsutani, G\. Minegishi, Y\. Iwasawa, T\. Kojima, and Y\. Matsuo \(2026\)On Advantage Estimates for Max@K Policy Gradients\.External Links:2606\.06080Cited by:[§2\.3](https://arxiv.org/html/2608.00296#S2.SS3.p1.3)\.
- C\. Walder and D\. Karkhanis \(2025\)Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems\.InAdvances in Neural Information Processing Systems,Vol\.38\.External Links:2505\.15201Cited by:[§2\.3](https://arxiv.org/html/2608.00296#S2.SS3.p1.3)\.
- C\. Wang, P\. Cheng, J\. Li, and W\. Sun \(2024\)Leader reward for POMO\-based neural combinatorial optimization\.arXiv preprint arXiv:2405\.13947\.External Links:2405\.13947Cited by:[§1](https://arxiv.org/html/2608.00296#S1.p1.1),[§2\.1](https://arxiv.org/html/2608.00296#S2.SS1.p1.6),[§3](https://arxiv.org/html/2608.00296#S3.1.1.1.1.1.1)\.