🤖 machine learning

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

Dit artikel presenteert het eerste positieve resultaat voor gedecentraliseerd en privaat PAC-leren in beurtgebaseerde stochastische spellen met bereikbaarheidsdoelstellingen door een speltheoretische generalisatie van de Expected Conditional Distance-parameter te introduceren om polynomiale steekproefcomplexiteitsgrenzen vast te stellen zonder dat gedeelde informatie of algoritmen vereist zijn.

Oorspronkelijke auteurs: Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

Gepubliceerd 2026-07-17

📖 8 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

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 twee rivaliserende videogame-personages een nieuw, mysterieus bordspel te leren spelen. Eén personage, laten we hem "Max" noemen, wil zo snel mogelijk een schatkist bereiken. De andere, "Min", wil hem tegenhouden, misschien door hem in een val te lokken of hem voor eeuwig in cirkels te laten dwalen. Dit is niet zomaar een simpel spel van geluk; het is een strijd van verstand waarbij elke zet de kansen verandert. In de wereld van de informatica wordt dit een "Turn-Based Stochastic Game" genoemd. Dat is een chique manier om een situatie te beschrijven waarin twee tegenstanders om de beurt beslissingen nemen, maar de uitkomst van die beslissingen afhangt van een worp met de dobbelstenen.

Normaal gesproken, wanneer we computers leren om spellen te spelen, gaan we ervan uit dat ze alles kunnen zien: de regels, het bord en wat de andere speler denkt. Maar in de echte wereld is het rommeliger. Vaak kent de computer de regels helemaal niet; hij moet ze leren door te spelen, fouten te maken en te zien wat er gebeurt. Dit wordt "Reinforcement Learning" genoemd. Het doel is om een strategie te vinden die "Probably Approximately Correct" (PAC) is. Dat is een mondvol, maar het betekent simpelweg: "Kunnen we een leermethode ontwerpen die, na een redelijke hoeveelheid oefening, bijna zeker een strategie vindt die bijna net zo goed is als de best mogelijke?"

Het lastige deel is dat voor bepaalde soorten doelen — zoals "uiteindelijk de schat bereiken" — leren wiskundig onmogelijk is als het spel eeuwig kan doorgaan en de spelers echt vijandig zijn. Als de tegenstander probeert je te misleiden, kan hij doen alsof hij je helpt leren, om je later in een val te lokken. Dit artikel pakt een specifieke, moeilijke versie van dit probleem aan: Kunnen twee spelers dit spel goed leren spelen als ze niet met elkaar kunnen praten, elkaars zetten niet kunnen zien en de regels niet kennen?

Het Grote Verstopspel met Dobbelstenen

In dit artikel nemen de auteurs — Ali Asdi, Krishnendu Chatterjee en Pavol Kebis — een uitdaging aan die op een paradox lijkt. Ze willen twee rivaliserende spelers, Max en Min, leren hoe ze een spel spelen waarbij Max een doel wil bereiken en Min hem wil tegenhouden. Het addertje onder het gras? Ze spelen in het donker. Ze kennen de regels van het bord niet, ze kunnen geen aantekeningen met elkaar delen en ze weten zelfs niet wat de andere speler op een gegeven moment doet.

In veel eerdere pogingen om dit op te lossen, deden onderzoekers twee grote, onrealistische aannames. Ten eerste namen ze aan dat de spelers een "openbaar notitieblok" konden delen waar ze alles wat ze leerden opschreven. Ten tweede namen ze aan dat de spelers precies hetzelfde leeralgoritme gebruikten, zoals twee studenten die van hetzelfde tekstboek kopiëren. De auteurs van dit artikel zeggen: "Wacht eens even, dat is niet hoe de echte wereld werkt." In werkelijkheid hebben spelers vaak privé-informatie en gebruiken ze verschillende methoden om te leren. Ze wilden weten: Kunnen we nog steeds goed leren spelen als iedereen zijn eigen geheimen bewaart en zijn eigen brein gebruikt?

Het "Wachtspel"-probleem

Om te begrijpen waarom dit zo moeilijk is, stel je een spel voor waarbij de schat verborgen is achter een deur die slechts één keer per miljoen jaar opengaat. Als de spelers alleen maar gokken, kunnen ze eeuwig wachten. In de wereld van de wiskunde wordt dit een "infinite horizon"-probleem genoemd. Als het spel eeuwig kan doorgaan en de tegenstander slim genoeg is om de afloop te vertragen, kun je nooit zeker weten of je het juiste aan het leren bent of dat je alleen maar wacht op een wonder dat misschien nooit zal gebeuren.

De auteurs realiseerden zich dat voor leren een vangnet nodig was. Ze introduceerden een concept genaamd de Expected Conditional Distance (ECD). Denk hierbij aan een "geduldsmeter" voor het spel. Het meet: "Als het doel bereikbaar is, hoe lang duurt het dan gemiddeld voordat je er bent?" Als de ECD klein is, betekent dit dat het spel niet eeuwig voortsleept; de schat wordt meestal relatief snel gevonden. Als de ECD enorm groot is, betekent dit dat het spel in een lus kan blijven hangen van wachten op een ongelooflijk lange tijd.

Het artikel bewijst dat als deze "geduldsmeter" begrensd is (wat betekent dat het spel niet eeuwig duurt om te eindigen), leren wel mogelijk is, zelfs in het donker. Ze lieten zien dat door dit getal te kennen, je het oneindige spel effectief kunt omzetten in een eindig spel, zoals het spel afkappen na een bepaald aantal zetten omdat je weet dat de schat tegen die tijd wel gevonden zou zijn. Het is belangrijk om op te merken dat zonder een dergelijke aanname (zoals ECD, of andere soortgelijke beperkingen gevonden in eerdere literatuur), leren in het algemeen onmogelijk is voor dit soort spellen. Het artikel beweert niet dat ECD de enig mogelijke manier is, maar het is de specifieke sleutel die zij gebruikten om het probleem in deze nieuwe setting te ontgrendelen.

De Geheime Saus: Leren in Fasen

Dus, hoe leren ze de spelers dit eigenlijk? De auteurs ontwierpen een slim paar leeralgoritmen (één voor Max, één voor Min) die werken als een team ontdekkingsreizigers die een grot in kaart brengen.

De Kaartuitbreiding: In plaats van alleen te denken aan "Toestand A" of "Toestand B", stellen de spelers zich een 3D-kaart voor waarbij de derde dimensie "Tijd" is. Ze breken het spel af in "Toestand-Stap"-paren. Het is alsoكzeggen: "Bij stap 1 ben ik in de keuken; bij stap 2 ben ik in de gang." Dit helpt hen om achterstevoren vanaf het einde te plannen.
De "Best Arm"-truc: Bij elke plek op hun kaart moeten de spelers een actie kiezen. Ze gebruiken een techniek uit een vakgebied genaamd "Bandit Learning" (stel je een gokker voor die probeat de beste gokautomaat te vinden). Ze proberen verschillende zetten, zien welke het beste werkt, en houden zich daaraan. Maar ze doen dit met een hoog vertrouwen, zodat ze zeker weten dat ze niet gewoon geluk hebben.
De Exploratie-lus: De spelers beginnen met het verkennen van de "onverkende" delen van de kaart. Ze behandelen deze onbekende plekken als nieuwe "schatten" om te vinden. Zodra ze de beste zet voor een specifieke plek hebben ontdekt, markeren ze deze als "verkend" en gaan ze verder. Ze blijven dit doen, waarbij ze stap voor stap een strategie opbouwen, totdat ze een plan hebben voor het hele spel.
De Privé-overeenkomst: Hier is de magie. Hoewel ze nooit met elkaar praten, volgen ze beiden een vergelijkbaar ritme. Ze blijven spelen totdat ze beiden het gevoel hebben dat ze genoeg verkend hebben. Wanneer geen van beide spelers meer nieuwe "onverkende" plekken kan vinden in hun eigen privézicht, geven ze beiden een signaal aan de spelsimulator: "We zijn klaar! Hier is onze strategie."

Het Resultaat: Een Nieuwe Soort Leren

De belangrijkste bevinding van het artikel is een luidruchtig "Ja". Ze hebben bewezen dat de spelers met deze methode een strategie kunnen leren die bijna perfect is (binnen een minuscule foutmarge) met een hoge slaagkans. Cruciaal is dat het aantal keren dat ze het spel moeten spelen (de "sample complexity") op een beheersbare, polynomiale manier groeit. Dit betekent dat de leertijd niet naar oneindig explodeert; het blijft redelijk, zelfs als het spel groter wordt.

Dit is een grote zaak omdat het de eerste keer is dat iemand heeft aangetoond dat je deze complexe, vijandige spellen kunt leren spelen in een gedecentraliseerde (geen gedeeld brein) en private (geen gedeelde aantekeningen) setting. Voorheen dachten mensen dat je informatie moest delen om effectief te leren. De auteurs toonden aan dat je, door de "geduldsmeter" (ECD) en een slimme strategie van achterwaarts plannen te gebruiken, in het donker kunt leren.

Ze hebben ook verduidelijkt dat het leren van dit type spel zonder aanvullende aannames (zoals de ECD-grens) in het algemeen onmogelijk is. Als het spel eeuwig kan voortduren zonder limiet aan hoe lang het duurt om het doel te bereiken, kan geen enkel leeralgoritme succes garanderen. Het artikel is heel duidelijk: je hebt die grens op tijd nodig om de wiskunde te laten kloppen.

Waarom zou je dit moeten weten?

Je vraagt je misschien af: "Wie geeft erom dat twee spelers dobbelstenen gooien in een theoretisch spel?" Nou, dit gaat niet alleen over bordspellen. Dit soort wiskunde vormt de ruggengraat van hoe we veilige AI bouwen voor zaken als zelfrijdende auto's, netwerkbeveiliging en geautomatiseerde handel. In die echte scenario's interageren verschillende systemen (of hackers) voortdurend met elkaar, vaak zonder volledige kennis van wat de ander doet.

Dit artikel geeft ons een nieuw instrumentarium. Het vertelt ons dat zelfs als we niet alle AI-agenten kunnen dwingen om hun geheimen te delen, en zelfs als ze proberen elkaar te slim af te zijn, we ze nog steeds kunnen leren om slim en veilig te zijn, mits we weten dat de "slechte dingen" niet na een oneindige tijd zullen gebeuren. Het is een stap naar het bouwen van AI die in staat is om door een chaotische, onzekere wereld te navigeren zonder een centrale baas nodig te hebben om hen te vertellen wat ze moeten doen.

Kortom, de auteurs hebben een probleem aangepakt dat onmogelijk leek — het leren van een spel in het donker met een rivaal — en hebben een manier gevonden om het licht stap voor stap aan te doen, met behulp van een slimme maatstaf voor geduld en veel achterwaarts denken.

Technische Samenvatting: PAC-leren in Turn-Based Stochastic Games met Reachability-doelstellingen

Probleemstelling
Het artikel behandelt het probleem van Probably Approximately Correct (PAC) leren voor Turn-Based Stochastic Games (TBSGs) met reachability-doelstellingen (bereikbaarheidsdoelstellingen). In TBSGs interageren twee tegenstanders (Max en Min) over een eindige toestandsruimte met stochastische overgangen. Het doel is dat Max de waarschijnlijkheid maximaliseert en Min de waarschijnlijkheid minimaliseert om uiteindelijk een doelset van toestanden te bereiken.

De auteurs benadrukken een fundamenteel hardheidsresultaat: PAC-leren voor reachability-doelstellingen is in TBSGs (en zelfs in Markov Decision Processes) over het algemeen onmogelijk zonder aanvullende aannames. Deze onmogelijkheid komt voort uit het feit dat reachability een onbegrensde eigenschap is, en adversarieel gedrag tijdens de leerfase kan het leren zinloos maken (bijvoorbeeld: een tegenstander kan een suboptimale actie kiezen die het doel direct bereikt, waardoor de werkelijke optimale strategie wordt gemaskeerd).

Eerdere positieve resultaten voor TBSGs vertrouwden op twee sterke aannames:

Publieke Informatie: Beide spelers delen alle informatie (toestanden, acties, overgangen).
Gecentraliseerd Leren: Beide spelers maken gebruik van hetzelfde leeralgoritme.

Dit werk beoogt deze aannames te versoepelen om te leren in een gedecentraliseerde setting waar spelers verschillende algoritmen gebruiken en beschikken over private informatie (specifiek: de huidige toestand is alleen bekend aan de speler die eigenaar is van die toestand).

Methodologie
De voorgestelde aanpak omvat een twee-fasen reductie en een nieuw leeralgoritme:

Generalisatie van Expected Conditional Distance (ECD):
De auteurs introduceren een speltheoretische generalisatie van de Expected Conditional Distance (ECD) parameter, oorspronkelijk gedefinieerd voor MDP's.
- Definitie: De ECD van een spel wordt gedefinieerd als het supremum over alle Min-strategieën van het infimum over de best-responses van Max van de verwachte tijd om het doel te bereiken, geconditioneerd op het bereiken van het doel.
- Rationale: Verschillende natuurlijke generalisaties van ECD naar games bleken te falen (bijvoorbeeld: ze konden klein zijn, zelfs wanneer de vereiste horizon voor benadering groot was). De voorgestelde definitie zorgt ervoor dat als de ECD begrensd is door $L$ , het oneindige-horizon reachability-probleem kan worden gereduceerd tot een eindig-horizon probleem met horizon $H \approx 2(L+1)/\epsilon$ . Deze afkapprocedure zet het onhandelbare oneindige-horizon probleem om in een handelbaar eindig-horizon probleem.
Finite-Horizon Expansie:
Om het finite-horizon reachability-probleem op te lossen, definiëren de auteurs een geëxpandeerd spel $G'$ . Dit spel ontvouwt de tijdshorizon in de toestandsruimte, waardoor state-step paren $(s, \ell)$ ontstaan waarbij $\ell$ de huidige stap vertegenwoordigt. Deze transformatie maakt het gebruik van backward induction mogelijk, aangezien het spel gelijkwaardig wordt aan een eindig-horizon MDP-achtige structuur waarbij positionele strategieën voldoende zijn.
Decentraal Leeralgoritme (LeTuReGa):
Het artikel presenteert een paar algoritmen, LeTuReGaMax en LeTuReGaMin, ontworpen voor de gedecentraliseerde private setting.
- Mechanisme: De algoritmen werken in fasen. In elke fase construeert een speler een strategie middels backward induction vanaf de horizon $L$ naar stap 0.
- Lokaal Leren: In elke state-step $(s, \ell)$ gebruikt de speler een Best-Arm Identification (BAI) routine om met hoge betrouwbaarheid een $\epsilon$ -optimale actie te identificeren. Dit voorkomt de noodzaak om de volledige overgangskansen te schatten (wat onhaalbaar is in private settings) en richt zich in plaats daarvan direct op het identificeren van optimale acties.
- Exploratie: De algoritmen houden een verzameling "niet-verkende" state-steps bij. Deze niet-verkende verzamelingen fungeren als hulpdoelsets om spelers te stimuleren nieuwe delen van de state-step ruimte te bezoeken.
- Terminatie: Het leerproces eindigt wanneer beide spelers een strategieprofiel aan de simulator voorstellen, wat gebeurt wanneer geen van beide spelers nieuwe state-steps kan ontdekken met hun huidige strategie.

Belangrijkste Bijdragen

Decentraal Private PAC-RL: Dit werk levert het eerste positieve resultaat voor PAC-leren in TBSGs met reachability-doelstellingen onder gedecentraliseerde en private informatie settings. Spelers delen geen algoritmen of staat-informatie.
ECD Generalisatie: Het artikel vestigt een subtiele en correcte generalisatie van de ECD-parameter naar TBSGs, waarbij wordt bewezen dat een begrensde ECD het mogelijk maakt om infinite-horizon reachability te reduceren tot finite-horizon reachability.
Polynomiale Sample Complexiteit: De auteurs stellen een polynomiale sample complexiteit aan band voor de voorgestelde algoritmen. De complexiteit is polynomiaal afhankelijk van het aantal toestanden ( $|S|$ ), acties ( $|A|$ ), de ECD-parameter ( $L$ ), en de inversen van de fouttolerantie ( $1/\epsilon$ ) en de faalkans ( $1/p$ ).
Algoritmisch Ontwerp: De introductie van een leerprocedure die backward induction, best-arm identification en dynamische exploratie van state-steps combineert zonder dat het schatten van overgangskansen vereist is.

Resultaten
Het belangrijkste theoretische resultaat (Corollary 16) stelt dat het paar algoritmen (LeTuReGaMax, LeTuReGaMin) PAC-RL is voor reachability-doelstellingen onder de ECD-aanname. De sample complexiteit is:
$O\left( \frac{|S|^3 L^7 |A| \log(|S|^2 L^2 / (p \epsilon^2))}{\epsilon^{10}} \right)$
waarbij $L$ de bovengrens is van de ECD-parameter.

Het bewijs berust op het aantonen dat:

De leer-simulatie binnen $|S'|$ fasen termineert (waarbij $S'$ de verzameling van geëxpandeerde toestanden is).
Met hoge waarschijnlijkheid het geconstrueerde strategieprofiel $\epsilon$ -optimaal is voor het finite-horizon spel.
Door de ECD-grens de $\epsilon$ -optimaliteit in het finite-horizon spel vertaalt naar $\epsilon$ -optimaliteit in het originele infinite-horizon spel.

Betekenis
Het artikel claimt met name significant te zijn door de sterke aannames van eerder werk te versoepelen. Eerdere PAC-leerresultaten voor TBSGs vereisten publieke informatie en gecentraliseerd leren. Dit werk demonstreert dat leren mogelijk is, zelfs wanneer spelers onafhankelijk handelen en over private staat-informatie beschikken, mits de ECD-parameter begrensd is. Bovendien, in tegen tegenstelling tot eerdere "anytime" algoritmen voor TBSGs die een gebrek aan sample complexiteit guarantees hadden, biedt dit werk expliciete polynomiale grenzen. De auteurs merken op dat dit het eerste positieve resultaat is voor gedecentraliseerde private informatie PAC-RL in TBSGs met reachability-doelstellingen.