Technische Samenvatting: Regret Minimization met Adaptieve Tegenstanders in Herhaalde Spelen

Probleemstelling

Het artikel behandelt de uitdaging van regret-minimalisatie in herhaalde spelen waarbij tegenstanders adaptief zijn, wat betekent dat zij hun strategieën kunnen aanpassen op basis van de geschiedenis van het spel. De auteurs stellen dat de standaardmetriek van external regret in online leren onvoldoend is voor deze setting. External regret gaat ervan uit dat verliessequenties functies zijn van tijdstappen alleen, wat impliciet tegenstanders als niet-adaptief behandelt. In speltheoretische settings kan een reactie van een tegenstander op de actie van een speler echter de toekomstige verliezen veranderen. Bijgevolg leidt het minimaliseren van external regret in herhaalde spelen vaak tot suboptimale evenwichten (bijv. de "defect-defect" uitkomst in het Iterated Prisoner's Dilemma) en slaagt het er niet in om effectieve coöperatieve strategieën zoals "tit-for-tat" te vatten, die ondanks hogere utiliteiten toch last kunnen hebben van lineaire external regret.

Bestaande alternatieven, zoals Policy Regret (die rekening houdt met geheugen in verliesfuncties) of Response Regret (die rekening houdt met historie-afhankelijke gemengde strategieën), kampen met aanzienlijke beperkingen. Policy Regret leunt vaak op restrictieve $m$-gebonden geheugenaannames die niet standhouden in herhaalde spelen waar vroege afwijkingen langetermijneffecten kunnen hebben. Response Regret, hoewel theoretisch solide, vereist een exponentieel grote strategieruimte, wat het computationeel onuitvoerbaar maakt.

Methodologie

1. Repeated Policy Regret (RP-Regret)

De auteurs introduceren Repeated Policy Regret (RP-Regret), een nieuwe prestatiemetriek die inherent is aan herhaalde spelen.

• Definitie: RP-Regret meet het verschil tussen de gerealiseerde cumulatieve utiliteit en de beste cumulatieve utiliteit in hindsight, uitgaande van het feit dat alle spelers (inclusief de tegenstander) adaptief reageren op de geschiedenis van het spel.
• Cruciaal onderscheid: In tegenstelling tot external regret beïnvloedt een afwijking naar een comparator-strategie op tijdstip $t$ niet alleen het verlies op $t$, maar ook alle daaropvolgende verliezen, omdat de adaptieve tegenstanders hun strategieën veranderen als reactie op de nieuwe geschiedenis.
• Noodzakelijke voorwaarden: Het artikel stelt vast dat het bereiken van sublineaire RP-Regret onmogelijk is zonder specifieke beperkingen. Er worden twee noodzakelijke voorwaarden geïdentificeerd:
  1. Sublineaire Variatie: De comparator-strategie mag niet te snel over de tijd veranderen.
  2. Imperfect Recall: Spelers (en de comparator) kunnen geen perfect geheugen hebben van de volledige geschiedenis. Specifiek stellen de auteurs Exponential Decay Memory (EDM) voor, waarbij de invloed van de geschiedenis op de huidige strategie exponentieel afneemt. Dit voorkomt "state passing" via acties en zorgt ervoor dat de effectieve geheugenlengte slechts logaritmisch groeit met de nauwkeurigheidseisen.

2. Minimalisatie-algoritmen

Omdat de objectieffunctie voor RP-Regret niet-convex is vanwege het product van strategieën over de tijd, stelt het artikel drie benaderingen voor om dit te minimaliseren:

• Oracle-gebaseerde benadering: Uitgaande van toegang tot een niet-convexe optimalisatie-oracle (zoals in eerder werk over online niet-convexe leerprocessen), tonen de auteurs aan dat sublineaire RP-Regret haalbaar is onder de noodzakelijke voorwaarden (Sublinear Variation en EDM). Dit dient als een theoretische baseline.
• Local Repeated Policy Regret (LRP-Regret): Om computationele uitvoerbaarheid te garanderen, stellen de auteurs een surrogaatmetriek voor, LRP-Regret. Deze metriek beperkt afwijkingen tot een enkel tijdstap (lokale afwijking) in plaats van een globale verandering van de strategie.
  • Convexificatie: Het verwachte verlies op een specifiek tijdstip wordt, wanneer dit wordt beschouwd als een functie van een eenstaps-afwijking, lineair (en dus convex) ten opzichte van de strategie op dat tijdstip.
  • Algoritme: De auteurs stellen een Projected Gradient Descent (PGD) algoritme voor om LRP-Regret te minimaliseren. Theoretische garanties tonen aan dat, indien tegenstanders voldoen aan de EDM-conditie, het algoritme sublineaire LRP-Regret bereikt.
• Markov Game Herformulering: Voor het geval dat tegenstanders ook langzaam van strategie veranderen (voldoen aan Sublinear Variation), herformuleren de auteurs het herhaalde spel met begrensde geheugen als een oneindig-horizontaal Markov Game.
  • Occupancy Measures: In plaats van de strategie direct te optimaliseren, optimaliseert het algoritme de occupancy measure (bezoekfrequenties van state-action paren). Dit transformeert het niet-convexe probleem naar een convex probleem in de occupancy measure-ruimte.
  • Constraints: Het algoritme gaat om met tijdvariërende beperkingen om te garanderen dat de occupancy measure overeenkomt met een valide product-strategieprofiel tegen de adaptieve tegenstanders.
  • Resultaat: Deze benadering minimaliseert direct de oorspronkelijke RP-Regret (niet alleen de surrogaat) en bereikt sublineaire regret.

Belangrijkste Resultaten

1. Hardheidsresultaten: Het artikel bewijst dat zonder de voorwaarden van sublinear variation en imperfect recall (specifiek EDM), het minimaliseren van RP-Regret onmogelijk is (resulterend in lineaire regret).
2. Algoritmische Garanties:
   • Het LRP-Regret minimalisatie-algoritme bereikt een regret-bound van $\tilde{O}(|A|^{m+1}\sqrt{P_T/T})$, waarbij $P_T$ de variatie van de comparator is en $m$ de geheugenlengte.
   • Het Markov Game-gebaseerde algoritme bereikt sublineaire RP-Regret wanneer tegenstanders langzaam van strategie veranderen.
3. Evenwichtsberekening: De auteurs leggen een theoretische link tussen het minimaliseren van deze regret-begrippen en het berekenen van evenwichten.
   • Indien alle spelers RP-Regret (of LRP-Regret) minimaliseren, convergeren de tijdgemiddelde strategieën naar een benaderend Subgame Perfect Nash Equilibrium (SPNE) of Subgame Perfect Coarse Correlated Equilibrium (SPCCE) met begrensde afwijking.
   • Specifiek convergeert de trajectorie voor oneindig herhaalde spelen naar een evenwicht dat robuust is tegen afwijkingen binnen een bepaald variatiebudget.
4. Experimentele Validatie: Experimenten op het Stag-Hunt spel laten zien dat het minimaliseren van LRP-Regret spelers in staat stelt om vaker naar het coöperatieve evenwicht (Stag-Stag) te convergeren met een hogere utiliteit dan methoden die external regret minimaliseren, die vaak blijven steken in het risico-dominante maar lager-utilitaire evenwicht (Hare-Hare).

Betekenis en Claims

Het artikel claimt een natuurlijke en intrinsieke regret-metriek te bieden voor herhaalde spelen die rekening houdt met de adaptiviteit van tegenstanders, zonder de restrictieve bounded-memory aannames van eerder Policy Regret werk of de computationele onuitvoerbaarheid van Response Regret op te leggen.

• Theoretische Bijdrage: Het identificeert de fundamentele grenzen (noodzakelijke voorwaarden) voor leren in adaptieve omgevingen en biedt de eerste bewijsbare algoritmen voor het minimaliseren van een speltheoretische regret-metriek die dynamische comparators en adaptieve tegenstanders toestaat.
• Praktische Implicatie: Door RP-Regret (of de convexe surrogaat LRP-Regret) te minimaliseren, kunnen spelers leren coöpereren in spelen zoals het Iterated Prisoner's Dilemma en Stag-Hunt, waardoor zij hogere utiliteiten behalen dan die bepaald door de standaard Nash-evenwichten in one-shot spelen.
• Evenwichtselectie: Het werk suggereert dat regret-minimalisatie in herhaalde spelen een mechanisme kan dienen voor het selecteren van betere evenwichten (bijv. coöperatieve) die niet noodzakelijkerwijs het unieke Nash-evenwicht van het onderliggende one-shot spel zijn.

De auteurs blijven bescheiden over de computationele complexiteit en erkennen dat de niet-convexe aard van het probleem over het algemeen oracles of specifieke structurele aannames (zoals langzaam veranderende tegenstanders) vereist om uitvoerbaar te zijn. Zij presenteren hun werk als een opening naar nieuw onderzoek naar zwakkere evenwichtsconcepten en evenwichtselectie via regret-minimalisatie.