🔢 mathematics

Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games

Dit artikel introduceert een nieuwe beleidsiteratie-algoritme voor twee-speler stochastische Stackelberg-spellen die monotoon verbetering van de leider garandeert en convergeert naar het Pareto-front wanneer de leider mijnheer is.

Oorspronkelijke auteurs: Mikoto Kudo, Youhei Akimoto

Gepubliceerd 2026-03-17

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mikoto Kudo, Youhei Akimoto

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

De Kern: Een Meester en een Leerling in een Videospel

Stel je een complex videospel voor met twee spelers: De Meester (de leider) en De Leerling (de volger).

De Meester wil het spel zo instellen dat hij zelf zoveel mogelijk punten haalt. Hij kan de regels, de beloningen en de omgeving aanpassen.
De Leerling is slim en wil ook zoveel mogelijk punten voor zichzelf halen. Maar de Leerling reageert altijd op wat de Meester doet. Als de Meester iets verandert, past de Leerling zijn strategie direct aan om daar het beste uit te halen.

Dit noemen we een Stackelberg-spel. Het probleem is dat de Meester niet zomaar kan doen wat hij wil; hij moet rekening houden met hoe de Leerling zal reageren.

Het Probleem: Waarom de oude methoden faalden

Vroeger hadden wetenschappers methoden om de Meester een goede strategie te geven. Maar deze methoden hadden twee grote gebreken:

Ze garandeerden geen verbetering: Soms probeerden ze een nieuwe strategie, maar werd het resultaat juist slechter. Het was alsof je een auto probeert te repareren, maar na elke poging rijdt hij nog slechter.
Ze hoopten op een "perfecte oplossing" die soms niet bestaat: Ze zochten naar één perfecte strategie voor de Meester die altijd het beste resultaat gaf. Maar in sommige situaties bestaat zo'n perfecte oplossing simpelweg niet. Het is alsof je probeert een schoen te vinden die perfect past aan zowel je linkervoet als je rechtervoet, terwijl die voeten heel verschillend zijn. Soms is er gewoon geen enkele schoen die perfect past.

Als er geen perfecte oplossing is, konden de oude methoden vastlopen of een slechte strategie opleveren.

De Oplossing: Een Nieuwe "Stap-voor-Stap" Methode

De auteurs van dit paper (Mikoto Kudo en Youhei Akimoto) hebben een nieuwe manier bedacht om de Meester te helpen. Ze noemen het Pareto-Optimale Policy Iteratie.

Hier is hoe het werkt, in drie simpele stappen:

1. Geen perfecte schoen, maar een betere pasvorm

In plaats van te zoeken naar één perfecte strategie die altijd het beste is (wat soms onmogelijk is), zoeken ze naar een strategie die niet slechter is dan de vorige.

De Analogie: Stel je voor dat je een berg beklimt. De oude methoden probeerden soms in één grote sprong naar de top te gaan, maar vielen dan terug naar beneden. De nieuwe methode zegt: "Zorg dat je bij elke stap een beetje hoger komt dan waar je nu bent." Als je niet hoger kunt komen, weet je dat je op een goed punt zit, zelfs als het niet de allerhoogste top is.

2. De "Beste Antwoord"-Leerling

De methode gaat ervan uit dat de Leerling altijd de slimste keuze maakt die hij kan maken, gegeven wat de Meester doet. De Meester moet dus zijn strategie kiezen op basis van: "Als ik dit doe, wat zal de Leerling dan doen, en is dat goed voor mij?"
De nieuwe methode garandeert dat elke nieuwe strategie van de Meester, gezien de reactie van de Leerling, minstens even goed is als de vorige. Dit heet "monotone verbetering". Je zakt nooit terug.

3. De "Pareto-voorrand" (De beste compromis)

Soms is er geen strategie die op elk moment het allerbeste resultaat geeft. Dan is er een reeks van "beste compromis-punten".

De Analogie: Stel je voor dat je een taart moet verdelen. Je wilt de Meester zoveel mogelijk geven, maar de Leerling moet ook tevreden zijn. Soms moet je de taart iets anders snijden. De nieuwe methode vindt de "rand" van de taart waar je niet meer kunt snijden zonder dat de ander minder krijgt. Dit noemen ze de Pareto-voorrand. De methode beweegt de strategie van de Meester steeds dichter naar deze rand toe.

Waarom is dit belangrijk?

Veiligheid: Je weet zeker dat je niet terugvalt in een slechte situatie. Elke stap is een verbetering.
Realiteit: Het werkt ook in situaties waar een "perfecte" oplossing niet bestaat. Het geeft de Meester de best mogelijke strategie die er wel bestaat.
Toepassing: Denk aan een webshop-eigenaar (de Meester) die de website zo instelt dat hij veel winst maakt, terwijl de klant (de Leerling) altijd de beste deal voor zichzelf kiest. Of een game-ontwikkelaar die een level zo ontwerpt dat de speler uitdagingen krijgt, maar de speler zelf het level zo speelt dat hij het snelst klaar is.

Samenvatting in één zin

De auteurs hebben een nieuwe, veilige manier bedacht om een leider (zoals een webshop-eigenaar of game-maker) te leren hoe hij zijn omgeving moet aanpassen, zodat hij steeds beter wordt, zelfs als er geen perfecte oplossing bestaat, door simpelweg te zorgen dat elke nieuwe poging beter is dan de vorige.

Titel: Policy Iteratie voor Twee-Speler Algemene-Som Stochastische Stackelberg Spellen

Auteurs: Mikoto Kudo en Youhei Akimoto (Universiteit van Tsukuba & RIKEN AIP)

1. Probleemstelling

Het paper adresseert twee-speler stochastische Stackelberg spellen (SSG's) met een algemene som (general-sum) structuur. In dit speltype zijn er twee agenten: een leider (leader) en een volger (follower).

Doel: De leider kiest een stationair beleid om zijn verwachte cumulatieve beloning te maximaliseren, wetende dat de volger altijd reageert met zijn beste antwoord (best response) op het beleid van de leider.
Uitdaging: In algemene-som settingen bestaat een Stationair Stackelberg Evenwicht (SSE) niet altijd. Bestaande methoden, zoals policy gradient en waarde-iteratie gebaseerd op dynamische programmering, garanderen geen monotoon verbeteren van het beleid van de leider. Als de limiet van deze algoritmen geen SSE is (wat vaak het geval is), is de prestatie van de leider niet gegarandeerd en kunnen ze convergeren naar inferieure oplossingen.
Aannames: De omgeving is bekend, de overgangsfuncties zijn bekend, en de beste reactie van de volger is voor de leider berekenbaar. De volger wordt verondersteld een "best-response follower" te zijn (altijd optimaal reagerend op het huidige beleid van de leider).

2. Methodologie

De auteurs ontwikkelen een nieuw Policy Iteratie-algoritme dat gebaseerd is op een nieuw afgeleid policy improvement theorem specifiek voor SSG's.

A. Analyse van Bestaande Dynamische Programmering (DP) Operators

De auteurs analyseren de bestaande DP-operatoren (zoals gebruikt door Bucarey et al., 2022). Ze tonen aan dat het vaste punt (fixed point) van deze operatoren weliswaar een evenwicht vormt onder de aanname van de volger, maar dat dit vaste punt niet noodzakelijk leidt tot een optimale strategie voor de leider als er geen SSE bestaat. De prestatie van de leider bij dit vaste punt kan willekeurig laag zijn omdat er geen garantie is op monotoon verbeteren.

B. Pareto-Optimaliteit als Nieuw Doel

Omdat een SSE niet altijd bestaat, introduceren de auteurs het concept van Pareto-optimaliteit als een uitgebreide definitie van optimaliteit.

In plaats van te zoeken naar één beleid dat alle staten optimaliseert (wat onmogelijk kan zijn), zoeken ze naar een beleid dat een Pareto-optimale waarde-functie realiseert.
Een Pareto-optimale waarde-functie is een punt op de grens van de bereikbare waarde-ruimte waar geen andere beleid bestaat dat in alle staten strikt beter presteert.
Als een SSE bestaat, valt deze samen met de Pareto-optimale oplossing. Als er geen SSE is, convergeert het algoritme naar de Pareto-front.

C. Policy Improvement Theorem voor SSG's

De kern van de methode is een nieuw Policy Improvement Theorem (Theorema 8). Dit theorem stelt voorwaarden op aan een Q-functie ( $Q^{f'}_A$ ) die het mogelijk maakt om te bepalen of een nieuw beleid $f$ beter is dan een bestaand beleid $f'$ zonder de volledige waarde-functie van $f$ te hoeven berekenen.

Het theorem houdt rekening met het feit dat de volger zijn beleid aanpast aan het nieuwe beleid van de leider.
Het definieert een verzameling van verbeterbare beleidsstrategieën $W_{\succeq}(f_t)$ waaruit het volgende beleid wordt geselecteerd.

D. Het Algoritme (Pareto-Optimal Policy Iteration)

Het voorgestelde algoritme (Algorithm 1) werkt als volgt:

Initialisatie: Start met een willekeurig beleid voor de leider.
Waarde-berekening: Bereken de waarde-functie van de leider onder het huidige beleid en de daaropvolgende beste reactie van de volger.
Selectie: Zoek een nieuw beleid dat voldoet aan de verbeteringsvoorwaarde (gebaseerd op de Q-functie en de huidige waarde).
Scalarisatie: Om de zoekruimte te navigeren, wordt een "Pareto-compliant scalarisatie" (bijv. een gewogen som) gebruikt om een specifiek nieuw beleid te selecteren dat de waarde monotoon verbetert.
Convergentie: Het algoritme herhaalt dit tot er geen beleid meer gevonden kan dat de waarde strikt verbetert.

3. Belangrijkste Bijdragen

Analyse van DP-Operators: Het paper onthult dat de vaste punten van bestaande DP-operatoren in SSG's niet noodzakelijk leiden tot goede strategieën voor de leider als er geen SSE bestaat.
Nieuw Policy Improvement Theorem: Een theoretisch fundament dat monotoon verbeteren van de leider's prestaties garandeert onder een best-response volger.
Nieuw Algoritme: Een policy iteratie-algoritme dat convergeert naar Pareto-optimale beleidsstrategieën.
Convergentiegarantie: Het bewijst dat het algoritme monotoon convergeert naar de Pareto-front.
- Specifiek: Als de leider kortzichtig is ( $\gamma_A = 0$ ), is er een garantie dat het algoritme convergeert naar een Pareto-optimale oplossing. Dit is de eerste theoretische garantie voor algemene-som SSG's met een kortzichtige leider.
Uitbreiding naar Praktische Toepassingen: Het paper biedt strategieën (zoals het splitsen van de zoekruimte en backtracking) om het algoritme toepasbaar te maken in situaties met grote beleidsruimtes.

4. Resultaten en Theoretische Bevindingen

Monotoon Verbetering: In tegenstelling tot bestaande methoden, garandeert het voorgestelde algoritme dat de waarde-functie van de leider in elke iteratie niet verslechtert ( $V_{t+1} \succeq V_t$ ).
Convergentie: De reeks van waarde-functies convergeert naar een limiet $v_\infty$ $v_{\infty}$ .
- Voor $\gamma_A > 0$ : De limiet ligt op de rand van de waarde-ruimte ( $\partial V$ ), maar is niet noodzakelijk Pareto-optimaal (hoewel het zeer dichtbij ligt).
- Voor $\gamma_A = 0$ : De limiet is gegarandeerd Pareto-optimaal ( $v_\infty \in PV$ ).
Afwezigheid van SSE: Het algoritme blijft functioneel en levert een "redelijke" oplossing op, zelfs in spellen waar een SSE niet bestaat (zoals geïllustreerd in het voorbeeld met twee staten in Sectie 3).

5. Significantie en Toepassingsgebied

Dit onderzoek is significant omdat het een fundamentele beperking van bestaande RL-methoden voor Stackelberg-spellen oplost: het gebrek aan convergentiegaranties en prestatiegaranties wanneer een perfect evenwicht niet bestaat.

Praktische Toepassingen:

E-commerce: Een platformeigenaar (leider) die de interface aanpast om de winst te maximaliseren, terwijl gebruikers (volgers) optimaal reageren op hun eigen voorkeuren.
Beleidsonderwijs (Policy Teaching): Het sturen van het gedrag van een ander agent door de overgangsfuncties van de omgeving te manipuleren (bijv. in cyberveiligheid of robotica), waarbij de "slachtoffer" of "leerling" een optimale agent is.
Decentrale Systemen: Toepasbaar in systemen waar de leider de enige controle heeft over de omgeving, maar de reacties van de volger complex en niet-kortzichtig zijn.

Kortom, het paper biedt de eerste robuuste theoretische basis voor het leren van optimale strategieën in complexe, niet-coöperatieve multi-agent systemen waar traditionele evenwichtsconcepten falen.