🤖 machine learning

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

Dit artikel presenteert een gestabiliseerde Best-of- $K$ trainingsextensie voor Neural Combinatorial Optimization die de binaire Leader Reward vervangt door een ranggebaseerd signaal, waarmee bescheiden verbeteringen in Best-of-8 prestaties op TSP-100 worden aangetoond terwijl expliciet wordt afgezien van het claimen van universele superioriteit of state-of-the-art status.

Oorspronkelijke auteurs: Melveena Jolly, Midhun Xavier

Gepubliceerd 2026-08-04

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Melveena Jolly, Midhun Xavier

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een enorme, verwarde knoop van een touw te ontwarren, maar je kunt niet in één oogopslag het hele plaatje zien. Je moet aan één uiteinde trekken, zien waar het naartoe gaat, en dan opnieuw proberen. Dit is de dagelijkse strijd van "Neural Combinatorial Optimization", een vakgebied waar informaticus kunstmatige intelligentie leren complexe puzzels op te lossen zoals het Handelsreizigersprobleem (het vinden van de kortste route om veel steden te bezoeken). Het doel is simpel: het perfecte pad vinden. Maar het pad is verborgen, en de computer moet gokken.

Om beter te worden in gokken, gebruiken deze computers een techniek genaamd "Reinforcement Learning". Denk aan het trainen van een hond. Als de hond zit, krijgt hij een traktatie (een beloning). Als hij springt, krijgt hij niets. Na verloop van tijd leert de hond om vaker te zitten. In de wereld van AI is de "hond" een neuraal netwerk, en de "traktatie" is een score gebaseerd op hoe goed zijn oplossing is. Een populaire methode genaamd POMO (Policy Optimization with Multiple Optima) werkt door de AI vanuit veel verschillende startpunten tegelijkertijd de puzzel te laten oplossen, alsof je tien verschillende ontdekkingsreizigers uitzendt om het kortste pad te vinden. Meestal leert de AI van de gemiddelde prestaties van al deze ontdekkingsreizigers. Echter, een nieuwer idee genaamd "Leader Reward" suggereerde dat de AI extra aandacht moet besteden aan de enkelvoudig beste ontdekkingsreiziger in de groep, door die "leider" als de ster van de show te behandelen.

Stel je nu voor dat je een team ontdekkingsreizigers inhuurt om een puzzel op te lossen, maar je hebt een strikte regel: je houdt alleen de beste kaart die ze meebrengen. Een nieuw experiment stelt een fascinerende vraag: als je weet dat je slechts de top 8 kaarten uit 100 zult houden, moet je je team dan trainen om gewoon de beste te zijn, of moet je ze trainen om iedereen te zijn die potentieel in de top 8 kan voorkomen? Dit is de kern van een recente studie door onafhankelijke onderzoekers Melveena Jolly en Midhun Xavier. Ze hebben geen nieuw type ontdekkingsreiziger uitgevonden of een nieuwe puzzel; in plaats daarvan hebben ze de trainingsregels van een bestaande AI aangepast om te zien of een "Top 8"-mentaliteit het team slimmer maakt wanneer ze daadwerkelijk worden ingezet.

Het Experiment: Trainen voor de "Best of Eight"

De onderzoekers namen een standaard AI-opstelling die getraind is op een klassieke puzzel genaamd TSP-100 (het bezoeken van 100 steden) en voerden een specifieke test uit. Ze wilden zien of het veranderen van de manier waarop de AI uit haar fouten leert, zou helpen wanneer de AI gevraagd wordt om meerdere oplossingen te genereren en de beste te kiezen.

Op de oude manier (genoemd "Leader Reward"), werd de AI getraind om geobsedeerd te zijn door de enkelvoudig beste oplossing die zij in een batch van 100 pogingen vond. Het was alsof een coach schreeuwde: "Alleen degene die als eerste finisht doet ertoe! De rest kan naar huis!" De nieuwe methode, die de auteurs "Stabilized Best-of-K" noemen, veranderde de stem van de coach. In plaats van iedereen te negeren behalve de winnaar, zei de nieuwe coach: "Als je in de top 8 zit, krijg je een traktatie! Als je 9e of lager bent, krijg je niets." De "K" in de naam staat voor dit aantal 8. De onderzoekers voegden ook een "stabilizer" toe, een wiskundig vangnet om ervoor te zorgen dat de trainingscijfers niet gek werden of te veel ruis kregen.

Wat ze vonden: Het hangt af van het spel

De resultaten waren een mix van "goed nieuws" en "het hangt ervan af".

Eerst controleerden de onderzoekers of hun nieuwe systeem de oude methode zelfs kon evenaren bij het spelen van het standaardspel. Wanneer ze de oude "100 starts, kies de beste" methode gebruikten met een specif kind type decoding (een manier om het antwoord van de AI te lezen), presteerde het nieuwe systeem bijna exact hetzelfde als de oude methode. Het behaalde een score van 7,7662, waarmee het de vorige record van 7,766 evenaarde. Dit bewees dat ze volgens dezelfde regels speelden en niets hadden kapotgemaakt.

Echter, de echte magie gebeurde toen ze de regels van het spel aanpasten om overeen te komen met de nieuwe training. Wanneer ze de AI vroegen om 8 onafhankelijke oplossingen te genereren en de beste te kiezen (een "Best-of-8" scenario), won de nieuwe "Stabilized Best-of-K" methode. In elke enkele testronde die ze uitvoerden, vond de nieuwe methode een korter pad dan de oude methode. Gemiddeld verminderde de nieuwe methode de kosten (de lengte van het pad) met ongeveer 0,25%. Hoewel dat klein klinkt, is het in de wereld van deze puzzels een grote zaak. Het bracht de prestaties van de AI dichter bij de theoretisch "perfecte" oplossing.

Maar hier komt de twist: de nieuwe methode is geen wondermiddel voor elke situatie.

Als je er slechts één kiest: Als de AI slechts één enkele oplossing mag kiezen (Best-of-1), was de oude "Leader Reward"-methode eigenlijk beter.
Als je er een groot aantal kiest: Als je de AI laat kiezen uit 128 oplossingen, deed de nieuwe methode nog steeds iets beter, maar het voordeel werd kleiner naarmate het aantal keuzes groeide.
Als je een andere decoder gebruikt: Wanneer ze een andere manier gebruikten om de antwoorden van de AI te lezen (genaamd "augmented greedy"), was de oude methode opnieuw iets beter.

De essentie

Dus, wat betekent dit alles? De onderzoekers ontdekten dat als je van plan bent een AI te gebruiken waarbij je een kleine batch opties genereert (zoals 8) en de beste kiest, het een slimme zet is om de AI te trainen om op de "Top 8" te mikken in plaats van alleen op de "Nummer 1". Het is alsof je een sportteam traint om een sterk collectief te zijn in plaats van slechts één superster.

De auteurs zijn echter zeer voorzichtig om niet te veel te overdrijven. Ze stellen expliciet dat dit geen "state-of-the-art" doorbraak is die alles oplost. Het is een specifieke verbetering voor een specifieke opstelling. Ze testten dit op slechts drie verschillende "seeds" (willekeurige startpunten voor de computer), wat genoeg is om een patroon te zien, maar niet genoeg om te bewijzen dat het altijd werkt. Ze geven ook toe dat hun methode eerder een "engineering recept" is dan een perfect wiskundig bewijs.

Kortom, deze studie suggereert dat als je een AI bouwt om routingspuzzels op te lossen en je van plan bent om het een paar keer te laten proberen voordat je de winnaar kiest, je de AI moet leren om een "top-tier medestijder" te zijn in plaats van alleen een "kampioen". Maar als je maar één kans krijgt, of als je een enorm aantal pogingen hebt, is de oude manier misschien nog steeds je beste optie. Het is een genuanceerde, nuttige aanpassing voor een specifiek hoekje van de AI-wereld, geen revolutie die alles verandert.

Technische Samenvatting: Gestabiliseerde Best-of-K Training voor Neurale Combinatorische Optimalisatie

Probleemstelling
Modellen voor Neurale Combinatorische Optimalisatie (NCO), zoals POMO (Kwon et al., 2020), trainen doorgaans op batches trajecten die gegenereerd zijn vanuit meerdere startknopen met behulp van een gedeelde baseline policy gradient. Echter, standaard trainingsupdates waarderen de gehele batch, terwijl bij implementatie vaak alleen de beste oplossing wordt behouden binnen een specifief inferentiebudget. Leader Reward (Wang et al., 2024) pakte dit aan door de training te wijzigen om de nadruk te leggen op het enkele "leader" traject (de beste in de batch), terwijl anderen worden minder zwaar gewogen.

Dit artikel onderzoekt of de training niet alleen de huidige leider moet onderscheiden, maar ook trajecten die het potentieel hebben om het beste lid te worden van een groep van grootte- $K$ , wanneer de implementatie precies $K$ onafhankelijke trajecten trekt. Het motiverende doel is het optimaliseren van de verwachte maximale beloning over $K$ onafhankelijke monsters:
$J_K(\theta) = \mathbb{E}_{\tau_1, \dots, \tau_K \sim \pi_\theta} \left[ \max_{1 \le j \le K} R(\tau_j) \right]$
De studie richt zich op het Traveling Salesman Problem (TSP-100) met behulp van de POMO-architectuur.

Methodologie
De auteurs stellen een "Stabilized Best-of-K" uitbreiding voor op het Leader Reward-framework. In tegenstelling tot Leader Reward, dat slechts één enkel traject een speciale rol toekent, verdeelt deze methode krediet op basis van rang en een vast samplingsbudget $K$ .

Rank-Gap Weging: Voor een batch van $n=100$ POMO-starts met gesorteerde beloningen $R_{(1)} \le \dots \le R_{(n)}$ , wijst de methode gewichten toe aan trajecten met rang $i \ge K$ . Het gewicht wordt berekend als een som van de gaten tussen de huidige beloning van het traject en lager gerangschikte trajecten, gewogen door combinatorische coëfficiënten. Dit vervangt de binaire leider/niet-leider distinctie door een continu signaal geïndexeerd door $K$ .
Stabilisatie: Om trainingsinstabiliteit te voorkomen, worden twee transformaties toegepast:
- Gap Flooring: De gesommeerde gap in de gewichtsberekening wordt ondergrensd (gefloord) door een kleine waarde $\delta = 0.01(R_{(n)} - R_{(1)})$ .
- Standardisatie: De resulterende gewichtsvector wordt binnen elke instantie gestandaardiseerd.
Implementatie details: De studie gebruikt de RL4CO POMO-implementatie met 100 starts per instantie, een batchgrootte van 64, en een vast schema van 3.050 epochs. Het samplingsbudget is vastgesteld op $K=8$ . De trainings-seeds zijn gepaard {0, 1, 2}.

Belangrijkste Bijdragen

Gecontroleerde Uitbreiding: Dit is een reproductie-en-uitbreidingsstudie van Leader Reward, geen nieuwe architectuur of inferentiezoekmethode. Het isoleert het effect van het vervangen van het binaire leider-signaal door een gestabiliseerd rank-gap signaal.
Engineering Recept: De auteurs verduidelijken dat "Stabilized Best-of-K" een engineering recept is (waarbij flooring en standaardisatie worden gebruikt) in plaats van een onbevooroordeelde schatter van de exacte gradiënt van Vergelijking (1).
Evaluatieprotocol: De studie introduceert een rigoureus evaluatieprotocol waarbij voor elk checkpoint 2.048 onafhankelijke trajecten worden getrokken. Deze worden verdeeld in disjuncte blokken van grootte $K$ om de gerealiseerde Best-of- $K$ kosten te meten.

Resultaten
De experimenten werden uitgevoerd op Euclidean TSP-100 met 10.000 testinstanties.

Reproductie van Baseline: De reimplementatie van Leader Reward behaalde een gemiddelde kosten van 7.7662 onder 100-start, 8-augmentatie greedy decoding, wat overeenkomt met de gerapporteerde 7.766 van Wang et al. (2024).
Verbetering in Gesamplede Best-of-8: Onder onafhankelijke sampling met $K=8$ behaalde de Stabilized Best-of-K methode een lagere gemiddelde kosten (7.7944) vergeleken met Leader Reward (7.8136) over alle drie de trainings-seeds. Dit vertegenwoordigt een kostenreductie van 0,247% ten opzichte van Leader Reward.
Budget Afhankelijkheid: Het voordeel van de Stabilized methode is afhankelijk van het samplingsbudget $K$ . Het presteert beter dan Leader Reward voor $K \in \{2, \dots, 128\}$ , maar Leader Reward presteert beter bij $K=1$ (enkel traject) en onder het oorspronkelijke augmented-greedy protocol.
Decoder Specificiteit: De verbetering is niet universeel overdraagbaar. Hoewel de gestabiliseerde policy de gesamplede Best-of-8 verbetert, is deze iets slechter dan Leader Reward voor een enkel gesampled traject ( $K=1$ ) en onder het 100-start, 8-augmented greedy decoding protocol.

Claims en Betekenis
Het paper houdt een bescheiden reikwijdte aan met betrekking tot de claims:

Geen Universele Superioriteit: De auteurs stellen expliciet dat er geen claim wordt gemaakt van state-of-the-art status. Leader Reward blijft superieur in specifieke regimes (bijv. $K=1$ en augmented-greedy).
Alleen Estimatie: De resultaten zijn gebaseerd op drie trainings-seeds, wat volgens de auteurs onder de drempel van zes seeds ligt die vereist is voor bevestigende statistische toetsing. De geobserveerde verbeteringen zijn beschrijvende observaties in plaats van statistisch bevestigde significantie.
Specifieke Toepasbaarheid: De bevindingen zijn specifiek voor de POMO-architectuur en Euclidean TSP-100. Het paper claimt geen generaliseerbaarheid naar andere problemen (zoals CVRP) of andere NCO-families.
Conclusie: Het gestabiliseerde $K=8$ rank-gap signaal is een "veelbelovende uitbreiding" van Leader Reward, specifiek wanneer de implementatie bestaat uit het samplen van een bescheiden aantal onafhankelijke kandidaten. Het is geen bewijs voor een algemeen betere POMO-policy.

Het Experiment: Trainen voor de "Best of Eight"

Wat ze vonden: Het hangt af van het spel

De essentie

Meer zoals dit