Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

Technische Samenvatting: Leren van Ordinale Responsbeleid in Ranggebaseerde Stochastische Prijsverzamelingsspellen

1. Probleemdefinitie

Het artikel behandelt de beperkingen van het Team Orienteering Problem (TOP) in multi-agent systemen. Hoewel TOP een verenigd kader biedt voor coöperatieve routing (bijv. last-mile bezorging, surveillance) waarbij agenten een collectieve nut maximaliseren onder reisbudgetten, slaagt het er niet in om scenario's te modelleren die betrokken zijn bij zelfbelanghebbende agenten die concurreren in omgevingen met schaarse middelen. In dergelijke settings geven agenten (bijv. concurrerende bezorgvloten of crowdsourced chauffeurs) prioriteit aan individuele beloningen boven collectieve winst, en wordt hun interactie beheerst door stochastische transities en energiebeperkingen.

Om dit gat te overbruggen, stellen de auteurs het Stochastic Prize-Collecting Orienteering Game (SPCOG) voor. In een SPCOG:

• Opereren agenten op een gewogen graaf met stochastische prijsverdelingen bij knopen.
• Hebben agenten individuele reisbudgetten en streven zij naar het maximaliseren van hun eigen cumulatieve beloningen.
• Conflictresolutie: Wanneer meerdere agenten tegelijkertijd dezelfde knoop bezoeken, geldt een ranggebaseerde regel: de agent met de hoogste globale rang (laagste index) claimt de prijs volledig; anderen ontvangen nul.
• Doelstelling: Het vinden van convergerende beleidsregels voor onafhankelijke agenten om individuele beloningen te maximaliseren, waarbij erkend wordt dat de totale teambeloning lager kan zijn dan het coöperatieve TOP-optimum door competitie.

2. Methodologie

Theoretische Analyse van Evenwichten
De auteurs analyseren eerst het bestaan van een Pure Nash Equilibrium (PNE) in SPCOGs:

• Volledige Grafen: Ze bewijzen dat voor volledige grafen een uniek PNE bestaat onder ranggebaseerde conflictresolutie. In dit evenwicht kiest de $i$-de gerangschikte agent de $i$-de grootste beschikbare prijs. De totale beloning in dit PNE komt overeen met de optimale oplossing van een equivalente coöperatieve TOP.
• Ster-grafen: Een vergelijkbaar uniek PNE bestaat waarbij agenten zich in alternerende stadia naar de $i$-de grootste prijs bewegen.
• Willekeurige Grafen: Het artikel toont via een tegenvoorbeeld (een specifiek scenario met twee agenten) aan dat een PNE niet noodzakelijkerwijs bestaat voor willekeurige grafstructuren wanneer agenten simultaan bewegen, wat de complexiteit van het oplossen van deze spellen benadrukt vergeleken met Stackelberg (leider-volger) formuleringen.

Concept van Ordinale Rang (OR)
Om de uitdaging van gedeeltelijke observeerbaarheid en de exponentiële toestandsruimte in algemene grafen aan te pakken, introduceren de auteurs Ordinale Rang (OR):

• Directe Tegenstanders: Agenten worden gegroepeerd in "gelokaliseerde stadia-spellen" op basis van een "scheidende graaf" waar randen agenten verbinden met overlappende bereikbare verzamelingen.
• Definitie: De OR van een agent wordt gedefinieerd als $1 +$ het aantal agenten met een hogere globale rang (lagere index) binnen zijn directe nabijheid (verbonden component).
• Betekenis: OR vat de meest invloedrijke lokale competitie samen. De auteurs hypothetiseren dat het conditioneren van beleidsregels op OR, in plaats van de globale toestand of globale rang, fungeert als een sterke inductieve bias, waardoor agenten het beste antwoord kunnen leren op directe tegenstanders zonder dat zij globale informatie nodig hebben.

Fictitious Ordinal Response Learning (FORL)
De auteurs stellen FORL voor, een entropie-gereguleerd leeralgoritme ontworpen voor onafhankelijk multi-agent reinforcement learning (MARL):

• Sequentiële Updates: Agenten updaten hun beleidsregels sequentieel op basis van hun rang. Hoger gerangschikte agenten updaten eerst, uitgaande van het feit dat lager gerangschikte agenten een willekeurig of stationair beleid volgen.
• Bootstrapping: De hoogst gerangschikte agent leert eerst om het onderliggende stochastische single-agent probleem op te lossen. Zodra het beleid van deze agent een vertrouwensdrempel bereikt (gemeten via entropie), worden de parameters met anderen gedeeld.
• Fictitious Play: Vervolgende agenten updaten hun beleidsregels door te spelen tegen de "stationaire" beleidsregels van hoger gerangschikte agenten.
• Entropie Regulatie: Het algoritme gebruikt een afnemende entropiedrempel ($H_{stop}$) om convergentie te garanderen. Als een PNE bestaat, convergeert het algoritme naar een zuivere strategie (entropie $\to$ 0); anders biedt het betrouwbaarheidsgrenzen op de kwaliteit van de mixed-strategy beleidsregel.
• Beleidsarchitectuur: Beleidsregels worden gemodelleerd met een Transformer-gebaseerde architectuur (TRXL-I) en zijn geconditioneerd op lokale observaties die zijn uitgebreid met de OR. Action masking wordt gebruikt om grafenbeperkingen af te dwingen.

3. Belangrijkste Bijdragen

1. SPCOG Formulering: Introductie van een speltheoretische variant van de TOP voor zelfbelanghebbende agenten in stochastische, energiebeperkte omgevingen.
2. Theoretische Garanties: Bewijs van een uniek PNE op volledige grafen en ster-grafen die overeenkomt met de optimale TOP-oplossing, en een tegenvoorbeeld dat de niet-existentie van PNE's op willekeurige grafen aantoont.
3. Ordinale Rang (OR): Voorstel van OR als een beknopte, lokale representatie van de competitieve positie van een agent, die dient als een sterke inductieve bias voor het leren.
4. FORL Algoritme: Ontwikkeling van een entropie-gereguleerd, door fictitious-play geïnspireerd algoritme dat convergerende beleidsregels oplevert in onafhankelijke leeromgevingen.
5. Empirische Validatie: Demonstratie dat met OR geconditioneerde beleidsregels superieur zijn aan global-rank geconditioneerde beleidsregels wat betreft generaliseerbaarheid, schaalbaarheid en trainingsefficiëntie.

4. Experimentele Resultaten

Experimenten werden uitgevoerd op echte wegennetwerken (Stockholm en Manhattan) met statische en dynamische prijsverdelingen.

• Prestaties vs. TOP: In volledige grafen bereikten met OR geconditioneerde beleidsregels 95% van de optimale TOP-beloning. In incomplete grafen bereikte het slechtste evenwicht 87% van de optimale oplossing.
• Generaliseerbaarheid: Beleidsregels getraind met FORL en OR-conditionering vertoonden superieure "zero-shot" transfercapaciteiten naar ongebalanceerde, door vraag gedreven prijsverdelingen vergeleken met Independent Policy Learning (IPL) en parameter-sharing methoden geconditioneerd op de globale toestand.
• Schaalbaarheid: Bij het opschalen naar teams van maximaal 25 agenten vertoonden met OR geconditioneerde beleidsregels (PS-OR) een lineaire schaling in totale beloning met een lage variantie. In tegenstelling hiertoe vertoonden met globale rang geconditioneerde beleidsregels (PS-GR) sublineaire winsten en een significant hogere variantie.
• Efficiëntie: De FORL-methode had 1,56x tot 2,2x minder trainingstijd nodig om vergelijkbare beloningsprofielen te bereiken vergeleken met standaard parameter-sharing en onafhankelijke leerbaselines.

5. Betekenis en Claims

Het artikel beweert dat het concept van Ordinale Rang effectief de noodzaak voor globale toestandinformatie ontkoppelt in multi-agent routing games. Door zich te concentreren op de lokale "directe tegenstanders" en hun relatieve rangen, kunnen agenten robuuste strategieën leren die goed generaliseren naar grotere teamgroottes en onbekende omgevingen.

De auteurs stellen dat FORL een praktisch mechanisme biedt voor het verkrijgen van convergerende beleidsregels in competitieve, stochastische routing games waar traditionele coöperatieve aannames falen. Het werk suggereert dat in ranggebaseerde conflictscenario's lokale informatie geconditioneerd op ordinale positie een effectiever leersignaal is dan de globale toestand of globale rang, wat een schaalbare oplossing biedt voor heterogene, zelfbelanghebbende robotvloten.