Vi presenterar ett nytt tillvägagångssätt för att identifiera ungefärlig rollsymmetrisk Nash jämvikt i stora simuleringsbaserade spel. Vår metod använder neurala nätverk för att lära sig en kartläggning från blandade-strategi profiler till avvikelse payoffs-de förväntade värdena av att spela ren strategi avvikelser från dessa profiler. Denna inlärning kan generaliseras från data om en liten bråkdel av ett spel resultat, tillåter dragbar analys av exponentiellt stora normala-form spel. Vi ger ett förfarande för iterativt förfina den lärda modellen med nya data som produceras genom provtagning i närheten av varje kandidat Nash jämvikt. I förhållande till den befintliga tekniken, avvikelse payoff lärande dramatiskt förenklar uppgiften att datorjämvikt och mer effektivt adresserar spelare asymmetrier. Vi demonstrerar empiriskt att avvikelse payoff learning identifierar bättre ungefärlig jämvikt än tidigare metoder och kan hantera svårare inställningar, inklusive spel med många fler spelare, strategier och roller. Samtidigt flytta spel är bland de mest allmänna verktygen för resonemang om incitament i multi-agent system. Den vanliga matematiska representationen av ett simultant flytta spel är den normala formen payoff matris. Den beskriver incitament i ett multiagentsystem genom att lista de strategier som är tillgängliga för varje agent och lagra, för varje kombination av strategier som agenterna gemensamt kan välja, den resulterande nytta för varje agent. Denna tabell representation växer exponentiellt: payoff matris för en normal form spel med n spelare och m strategier per spelare lagrar verktyg för var och en av m n ren strategi profiler. Som ett resultat, explicita normalform representationer används vanligtvis endast för spel med ett mycket litet antal spelare och strategier. För att studera större spel, är det vanligt att ersätta den explicita payoff tabellen med en mer kompakt representation av verktygsfunktionen, från vilken payoff värden kan beräknas på begäran. Dock är ren strategi allmännyttiga funktioner i allmänhet inte tillräckliga för att beräkna Nash equilibria. Istället, Nash-finding algoritmer är vanligtvis beroende av en eller flera av följande mängder är effektivt beräkningsbar: bästa svar på profiler av blandade strategier, avvikelse utdelningar av blandade strategiska profiler (den förväntade nyttan av att avvika från en ren strategi, hålla andra agenters blandade strategier fast), Detta innebär att analysera stora spel normalt kräver noggrant välja en kompakt representation av nyttofunktionen som stöder effektiv beräkning av blandad strategi avvikelse utdelningar. För vissa klasser, som actiongraf spel (Jiang, Leyton-Brown, och Bhat 2011), dessa representationer är kända, men i andra fall, ingen sådan representation finns tillgänglig. Det kan dessutom vara svårt att identifiera en sådan kompakt struktur, även när den existerar. I detta dokument utforskar vi en maskininlärningsmetod för att effektivt approximera avvikelser och deras derivat, under hypotesen att tillräckligt nära approximation av dessa mängder kommer att tendera att ge -Nash equilibria. Kärnan i tillvägagångssättet är tanken att de förväntade vinsterna av en blandad strategiprofil kan uppskattas av utbetalningarna av rena strategiska profiler som provtagits från den blandade strategiprofilen. Sådan provtagning är extremt bullriga, men genom provtagning från många olika blandade-strategi profiler och använder maskininlärning algoritmer som generaliserar över relaterade blandade strategier, kan vi uppskatta en avvikelse payoff funktion för hela spelet. Våra metoder är tillämpliga i miljöer där en specifik kompakt struktur inte är känd i förväg, men där vinstberäkningar för godtyckliga ren strategiprofiler kan förvärvas. Denna inställning är vanlig i simuleringsbaserade spel ) och andra multi-agent förstärkning inlärningsinställningar inklusive sekventiella sociala dilemman (Leibo et al. Kommissionens genomförandeförordning (EU) nr 668/2014 av den 13 juni 2014 om tillämpningsföreskrifter för Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1). Många av dessa tillämpningar kan omfatta ett stort antal symmetriska aktörer och skulle dra nytta av analyser som skalar effektivt och exakt genom att utnyttja dessa symmetrier. Mycket senaste framsteg i spel-teoretiska inställningar har uppnåtts genom tillämpning av maskininlärning till stora omfattande-form spel. I Go och poker, är den omfattande formen väldefinierad, men är alldeles för stor för att konstrueras explicit, så hög nivå spela Moravčík et al. 2017) och ungefärlig jämviktsanalys (Heinrich, Lanctot och Silver 2015) har krävt hjälp av maskininlärning baserade algoritmer. Dessa algoritmer kör simuleringar för att uppskatta vinster för olika speltillstånd och använda inlärning för att generalisera till outforskade delar av spelet träd. Vårt arbete använder ett liknande tillvägagångssätt, generera observationer genom simulering och göra generaliseringar genom maskininlärning endast i samband med normal-form avvikelse payoffs, i stället för omfattande-form tillstånd eller tillstånd-aktion värden. I samband med simultant flytta spel, en mängd olika spelmodeller mer kompakt än den normala formen payoff matris har utforskats. Grafiska spel (Kearns 2007) utnyttja oberoende bland spelare, action-graf spel (Jiang, Leyton-Brown, och Bhat 2011) utnyttja självständighet eller partiell självständighet bland strategier, och resursografi spel (Jiang, Chan, och Leyton-Brown 2017) utnyttja självständighet bland delbeslut som omfattar strategier. Alla dessa modeller kan, i särskilda sammanhang, exponentiellt minska storleken på spelet representation. Men de kräver alla detaljerad kunskap om ett spel struktur, vilket är osannolikt att vara tillgänglig i inställningen av simuleringsbaserade spel. Om en exakt kompakt modell inte är känd i förväg kan det fortfarande vara möjligt att inducera parametrarna för en sådan modell från simulerade eller observerade data. Duong m.fl. (2009) skapa grafiska spel från payoff data, och Honorio och Ortiz (2015) konstruera linjär påverkan spel från beteendedata. En fördel med dessa metoder är att de resulterande modellerna kan erbjuda strukturell insikt som kan generalisera till andra relaterade inställningar. De lider emellertid av betydande begränsningar genom att endast den särskilt riktade typen av struktur kan läras. Så dessa metoder är bara användbara när analytikern har förkunskaper om lönestrukturen. Däremot, avvikelse payoff lärande är agnostic till den detaljerade strukturen av payoff funktioner, vilket gör det tillämpligt på ett mycket bredare utbud av simuleringsbaserade spel. Vi är medvetna om två dokument som har tagit upp problemet med att lära sig generiska modeller av simultant flytta spel från simuleringsbaserade data. Den första lär sig payoff funktioner som generaliserar över kontinuerliga strategi utrymmen (Vorobeychik, Wellman, och Singh 2007). Regressionen tar som ingång en enkel-parameter beskrivning av en spelares strategi och en enda-parameter sammanfattning av profilen för motståndare strategier och utgångar ett verktyg. För alla utom de enklaste regressionsmetoderna kräver jämviktsberäkning att man använder de inlärda funktionerna för att fylla i en payoff-matris för en diskretisering av strategiutrymmet. Denna matris växer exponentiellt med antalet spelare, förbjuder analys av stora spel med komplexa payoff funktioner. Närmsta till det nuvarande arbetet, Wiedenbeck, Yang och Wellman (2018) lära sig payoff funktioner symmetriska spel. För varje strategi, en regressator tar som ingång en ren strategi motståndare-profil och outputs ett verktyg. De ger en approximationsmetod för avvikelseutbetalningar som gör det möjligt att beräkna rollsymmetrisk -Nash equilibria. Detta tillvägagångssätt kan lära sig komplicerade payoff funktioner och skalor väl i antalet spelare. approximationsmetoden, som endast är giltig för fullt symmetriska spel inlärda via RBF-kärnan Gaussian process regression, är oöverkomligt dyr, och därmed begränsad till små datauppsättningar från spel med ett litet antal rena strategier. Vi jämför mot denna metod i våra experiment och visa gynnsamma resultat för avvikelse-payoff lärande.
Därefter, Sokota et al. REF ger ett framsteg jämfört med tidigare arbete, med hjälp av neurala nätverk för att approxima nyttofunktionen (istället för GPs) och ger ett sätt att styra provtagning för att fokusera den på grannskapet av kandidatjämviktspunkter.
Learning Deviation Payoffs in Simulation-Based Games
{'venue': 'AAAI', 'journal': None, 'mag_field_of_study': ['Computer Science']}