Technische Samenvatting: Afstandsgestuurde Versterkende Leer in Grote Discrete Actieruimten

Probleemstelling

Versterkende Leer (RL) heeft succes geboekt in continue en kleinschalige discrete domeinen, maar kampt met de "vloek van de kardinaliteit" bij grootschalige besluitvormingsproblemen zoals logistiek, planning en aanbevelingssystemen. Deze toepassingen omvatten vaak actieruimten met kardinaliteiten tot $10^{20}$, die hoge dimensionale discrete componenten, categorische variabelen of hybride discrete-continue parameters bevatten.

Bestaande aanpakken staan voor drie primaire knelpunten:

1. Gradiëntvariatie: Standaard beleidsgradiënten lijden onder een explosie van variatie naarmate de waarschijnlijkheidsmassa $\pi(a|s)$ verdwijnt in grote actieruimten.
2. Berekenbare Hanterbaarheid: Methoden die vertrouwen op uitputtende enumeratie of vooraf berekende zoektabellen (bijv. Wolpertinger) worden onhanteerbaar naarmate de dimensionaliteit toeneemt.
3. Structurele Stijfheid: Benaderingen zoals Dynamic Neighborhood Construction (DNC) vertrouwen op regelmatige roosterstructuren (bijv. numerieke nabijheid) en falen in onregelmatig gespreide of schaarse haalbare gebieden. Bovendien vereisen hybride actieruimten vaak hiërarchische sequenties, wat leidt tot vastlopers bij toewijzing en de training destabiliseert.

Methodologie: Afstandsgestuurde RL (DGRL)

De auteurs stellen Distance-Guided Reinforcement Learning (DGRL) voor, een off-policy actor-critic algoritme ontworpen om te schalen naar actieruimten met tot $10^{20}$ kandidaten. DGRL werkt in een continue relaxatie van de discrete actieruimte en maakt gebruik van een volumetrische projectielus die bestaat uit twee synergetische componenten:

1. Gesteekproefsgewijze Dynamische Buurten (SDN)

SDN adresseert de uitdaging van exploratie in hoge dimensionale discrete ruimten door stochastische volumetrische exploratie uit te voeren rond een continue "proto-actie" $\hat{a}$ gegenereerd door de actor.

• Mechanisme: In plaats van te vertrouwen op stijve roosterlijnen of vooraf berekende tabellen met dichtstbijzijnde buren, construeert SDN een dynamische buurt $B(\hat{a})$ begrensd door een Chebyshev ($L_\infty$) straal $L$.
• Onafhankelijke Coördinatensteekproeven: Om de combinatorische explosie van het enumereren van alle gehele punten in de hyperkubus te vermijden, steekproeft SDN elke dimensie onafhankelijk. Het interpreteert $\hat{a}$ als de modus van een steekproefverdeling en trekt $K$ kandidaat-acties. De kans op het steekproeven van een kandidaat neemt af naarmate de afstand tot $\hat{a}$ toeneemt.
• Dimensionale Invariantie: Door gebruik te maken van de $L_\infty$-metriek blijft het zoekvolume stabiel naarmate de dimensionaliteit $N \to \infty$. Dit zorgt ervoor dat steekproefkansen niet verdwijnen, in tegenstelling tot Euclidische ($L_2$) metrieken waarbij de vereiste straal groeit met $\sqrt{N}$.
• Complexiteit: Deze aanpak reduceert de zoekcomplexiteit van exponentieel $O((2L)^N)$ naar lineair $O(N \cdot K)$, wat schaalbaarheid mogelijk maakt naar dimensies waarbij $N > 100$.

2. Afstandsgestuurde Updates (DBU)

DBU adresseert de problemen van gradiëntvariatie en instabiliteit door beleidsoptimalisatie om te vormen tot een stabiel regressietaken.

• Doelconstructie: Het algoritme pertubeert de proto-actie $\hat{a}$ om $M$ hulpkandidaten te genereren. Het evalueert deze kandidaten met de criticus om Q-waarden te verkrijgen en construeert een doelactie $\bar{a}$ als een softmax-gewogen gemiddelde van deze kandidaten. Dit fungeert als een denoising-filter, wat criticus-overschatting mitigeert en het verlieslandschap gladstrijkt.
• Regressieverlies: De actor wordt bijgewerkt door de afstand tussen de proto-actie $\hat{a}$ en het doel $\bar{a}$ te minimaliseren (bijv. met Huber-verlies).
• Variatieonafhankelijkheid: Theoretisch is de gradiëntvariatie van DBU onafhankelijk van de kardinaliteit van de actieruimte $|A|$. De update hangt alleen af van de geometrie van de gerelaxeerde actieruimte en het vaste aantal gestreepste kandidaten $M$, waardoor gradiëntruis wordt ontkoppeld van de grootte van de actieruimte.

Unificatie van Hybride Ruimten

DGRL behandelt hybride actieruimten $A \subset \mathbb{Z}^N \times \mathbb{R}^M$ door een gezamenlijke proto-actie $(\hat{a}_d, \hat{a}_c)$ uit te voeren. Zowel SDN als DBU werken gelijktijdig op de volledige vector. Dit maakt gezamenlijke optimalisatie mogelijk waarbij discrete en continue componenten elkaar informeren via gedeelde representatielagen, waardoor de "regret floor" wordt vermeden die typerend is voor hiërarchische methoden waarbij hoog-niveau keuzes laag-niveau optimalisatie beperken.

Belangrijkste Bijdragen

1. Algoritmisch Kader: Introductie van DGRL, dat SDN en DBU combineert om efficiënte RL mogelijk te maken in ruimten met tot $10^{20}$ acties.
2. Theoretische Garanties:
   • Bewijs dat Chebyshev-gebaseerde steekproeven een stabiel zoekvolume handhaven naarmate de dimensionaliteit toeneemt (Propositie 4.1).
   • Bewijs dat de gradiëntvariatie van DBU onafhankelijk is van de actiekardinaliteit $|A|$ (Stelling 4.2).
   • Vestiging van garanties voor lokale waardeverbetering in gestructureerde taken onder Lipschitz-continuïteitsaannames (Propositie 4.5).
3. Schaalbaarheid: Aantonen dat DGRL lineair schaalt met dimensionaliteit $N$ in plaats van exponentieel met kardinaliteit $|A|$, en zich op natuurlijke wijze generaliseert naar onregelmatig gestructureerde en hybride actieruimten.

Experimentele Resultaten

De auteurs evalueerden DGRL over twaalf variaties van vier omgevingen: 2D Labyrinten, Job Shop Planning, Gezamenlijke Voorraadhervulling en Aanbevelingssystemen. Deze omvatten zowel gestructureerde (regelmatige) als onregelmatig gestructureerde topologieën, met actieruimten variërend van $5^4$ tot $343^{10}$.

• Prestaties: DGRL presteerde beter dan state-of-the-art benchmarks (waaronder Wolpertinger, DNC, Cacla en LAR) met tot 66% in discrete omgevingen en 129% in hybride omgevingen.
• Robuustheid: In tegenstelling tot DNC, dat instortte in hoge dimensionale onregelmatige ruimten, behield DGRL stabiliteit en prestaties. Het toonde ook aanzienlijk lagere variatie en snellere convergentie in vergelijking met DDPG-gebaseerde baselines.
• Berekenings-efficiëntie: DGRL vertoonde bijna constante tijdstappen ten opzichte van de grootte van de actieruimte, terwijl methoden die vertrouwen op zoektabellen (Wolpertinger, LAR) berekeningsmatig onhaalbaar werden en de tijdstappen van DNC degradeerden met de dimensionaliteit.
• Ablatiestudies: Resultaten bevestigden dat zowel SDN (voor volumetrische exploratie) als DBU (voor stabiele regressie-updates) essentieel zijn; het verwijderen van een van beide componenten leidde tot prestatiedegradatie of instabiliteit.

Betekenis en Claims

Het artikel claimt dat DGRL een fundamentele aanpak biedt voor metrisch-bewuste RL, wat suggereert dat het benutten van probleemstructuur en afstandsgestuurde steekproeven categorische representaties kan vervangen in grootschalige besluitvorming.

De auteurs stellen dat DGRL de schaalbaarheidskloof in RL succesvol overbrugt door:

1. Gradiëntvariatie te ontkoppelen van de kardinaliteit van de actieruimte.
2. Volumetrische exploratie mogelijk te maken die robuust is voor onregelmatige structuren van de actieruimte.
3. Gezamenlijke optimalisatie in hybride ruimten te faciliteren zonder de instabiliteit van hiërarchische decompositie.

Het werk wordt gepresenteerd als een oplossing voor de "vloek van de kardinaliteit", die een berekenbaar hanteerbaar alternatief biedt voor uitputtend zoeken en een stabieler alternatief voor beleidsgradiëntmethoden in massale discrete en hybride actieruimten.