Motstående självspel i tvåspelarspel har levererat imponerande resultat när det används med förstärkning av inlärningsalgoritmer som kombinerar djupa neurala nätverk och trädsökning. Algoritmer som AlphaZero och Expert Iteration lär tabularasa, producerar mycket informativa träningsdata i farten. Självspelsträningsstrategin är dock inte direkt tillämplig på enspelarspel. Nyligen har flera praktiskt taget viktiga kombinatoriska optimeringsproblem, såsom problemet med resande säljare och bin förpackningsproblem, omformulerats som förstärkning inlärningsproblem, vilket ökar vikten av att möjliggöra fördelarna med självspel utöver tvåspelarspel. Vi presenterar rankad belöning (R2) algoritm som åstadkommer detta genom att rangordna de belöningar som erhållits av en enda agent över flera spel för att skapa en relativ prestandamått. Resultat från att tillämpa R2-algoritmen till instanser av en tvådimensionell och tredimensionell bin förpackningsproblem visar att det överträffar generiska Monte Carlo träd sökning, heuristiska algoritmer och heltal programmering lösare. Vi presenterar också en analys av den rangordnade belöningsmekanismen, särskilt effekterna av problemfall med varierande svårigheter och olika rankningströsklar.
I REF, ett permutation-invariant nätverk användes som en förstärkning lärande agent för att lösa bin förpackning problem.
Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization
{'venue': 'Presented at the Thirty-second Conference on Neural Information Processing Systems (NeurIPS 2018), Deep Reinforcement Learning Workshop, Montreal, Canada, December 3-8, 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}