Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets

Technische Samenvatting: Bellman–Taylor Score Decoding voor MDP's met Toestandsafhankelijke Toelaatbare Actiesets

1. Probleemstelling

Veel sequentiële besluitvormingsproblemen in operations research (OR), zoals voorraadbeheer, wachtrijnetwerkbeheer en resourceallocatie, kunnen worden geformuleerd als Markov Decision Processes (MDP's). Een cruciale uitdaging bij het toepassen van Deep Reinforcement Learning (DRL) op deze problemen is de actie-interface.

Standaard DRL-algoritmen (bijv. DQN, PPO) gaan doorgaans uit van een vaste eindige catalogus of een eenvoudige Euclidische ruimte voor acties. Echter, in veel OR-modellen is de verzameling toelaatbare acties $A(s)$ toestandsafhankelijk, hoogdimensionaal en impliciet gedefinieerd door complexe operationele beperkingen (bijv. capaciteitslimieten, integrale eigenschappen en combinatorische koppeling). Deze beperkingen maken het moeilijk om acties te enumereren voor waardegebaseerde methoden of om eenvoudige waarschijnlijkheidsverdelingen voor beleidsgebaseerde methoden te definiëren. Bestaande oplossingen, zoals action masking, projectielagen of differentieerbare optimalisatielagen, vereisen vaak probleem-specifieke engineering, gespecialiseerde trainingspipelines of vertrouwen op expliciete actiekatalogen die mogelijk prohibitief groot zijn.

2. Methodologie: Bellman–Taylor Score Decoding

De auteurs stellen Bellman–Taylor Score Decoding voor, een framework dat het leren van beleid ontkoppelt van de handhaving van toelaatbaarheid. De kernidee is om het leerdoel te verschuiven van de onregelmatige, beperkte natuurlijke actieruimte naar een regelmatige, onbeperkte Euclidische "score"-ruimte.

Kerncomponenten:

• Structurele Representatie: De methode gaat ervan uit dat de MDP een structurele transitie-representatie toelaat waarbij de volgende toestand $s'$ wordt bepaald door een post-actie configuratie $\phi_s(a)$ en een exogene verstoring $\xi_s$ via een bekende transitiefunctie $\Xi_s$.
• Taylor-expansie Motivatie: De optimale actiewaarde-functie $Q^*(s, a)$ wordt benaderd met behulp van een eerste-orde Taylor-expansie van de continuatie-waarde-functie $G^*_s(x)$ rond een referentie post-actie configuratie. Dit levert een lineaire surrogaat op:
  $$Q^*(s, a) \approx \alpha(s) + \psi_s(a) + \langle z^*(s), \phi_s(a) \rangle$$
  waarbij $z^*(s)$ de marginale waarde (gradiënt) van de post-actie configuratie vertegenwoordigt.
• Latente-Score MDP: In plaats van direct een beleid $\pi(a|s)$ te leren, leert de agent een beleid $\pi(z|s)$ dat een latente scorevector $z$ output in een Euclidische ruimte.
• Actie-Decoder: Een deterministische decoder $\Gamma(s, z)$ brengt de score $z$ naar een toelaatbare natuurlijke actie door een optimalisatieprobleem op te lossen over de oorspronkelijke toestandsafhankelijke toelaatbare verzameling:
  $$\Gamma(s, z) = \arg\max_{a \in A(s)} \{ \psi_s(a) + \langle z, \phi_s(a) \rangle \}$$
  Deze decoder handhaaft alle operationele beperkingen (integrale eigenschappen, capaciteit, etc.) exact.
• Training: Het DRL-algoritme (bijv. PPO) optimaliseert het scorebeleid op de geïnduceerde latente-score MDP. Cruciaal is dat de decoder niet deel uitmaakt van de differentieerbare computationele graaf. De beleidsgradiënt-updates hangen alleen af van de scoreverdeling, niet van de afgeleide van de optimalisatiestap van de decoder. Dit voorkomt de problemen geassocieerd met het differentiëren door integer programma's of niet-gladde optimalisatoren.
• Generalisatie: Het framework ondersteunt hogere-orde Taylor-expansies (tot orde $K$), waarbij de decoder optimaliseert over hogere-orde feature-kaarten van de post-actie configuratie om niet-lineariteiten in de continuatie-waarde te vangen.

3. Theoretische Bijdragen

Het paper biedt een prestatiegarantie die de optimaliteitskloof van het geleerde beleid ontleedt in twee afzonderlijke termen:

1. Structurele Approximatiefout: Deze term meet de residuele variatie in de Bellman-continuatie-waarde die niet verklaard kan worden door de lineaire (of hogere-orde) score-approximatie. De auteurs tonen aan dat deze begrensd wordt door de lokale kromming van de waardefunctie en de afwijking van toelaatbare post-actie configuraties van het referentiepunt. Zij laten zien dat exacte actiekeuze mogelijk is als deze residuele oscillatie kleiner is dan de lokale Bellman actie-gap.
2. Algoritmische Leerfout: Deze term vertegenwoordigt de fout die wordt veroorzaakt door het DRL-algoritme (bijv. PPO) bij het oplossen van de geïnduceerde latente-score MDP, inclusief eindige-steekproef- en functie-approximatiefouten.

Deze analyse verduidelijkt dat de beperkte klasse van score-decoding beleidsregels goed kan benaderen van Bellman-greedy beslissingen wanneer de continuatie-waarde lokaal glad is en de Taylor-restterm klein is.

4. Empirische Resultaten

Het framework werd geëvalueerd op twee probleemdomeinen:

• Voorraadbeheer (Sanity Check): Een multi-locatie voorraadprobleem met cross-transshipment en niet-lineaire ontvangstverliezen.

  • Bevindingen: De eerste-orde decoder presteerde goed wanneer de systeemdynamica bijna lineair was. Naarmate de niet-lineariteit (congestie/verlies) toenam, degradeerde de prestatie van de eerste-orde decoder, maar de tweede-orde decoder behield een bijna optimale prestatie, wat het nut van hogere-orde expansies voor complexe dynamica aantoont.

• Wachtrijnetwerkbeheer (Case Study): Een multi-class, multi-pool dynamisch routeringsprobleem waarbij acties bestaan uit integer dispatching-matrices die beperkt zijn door wachtrijlengtes en servercapaciteiten.

  • Kleine schaal: In een $2 \times 2$ netwerk waar de optimale policy exact berekend kon worden, bereikte het voorgestelde BTSD-PPO algoritme kosten binnen 1,1% tot 2,5% van het exacte optimum.
  • Gemiddelde schaal: In een $5 \times 5$ netwerk presteerde BTSD-PPO significant beter dan state-of-the-art benchmarks, inclusief klassieke index-gebaseerde heuristieken (c$\mu$, max-weight), een atomische-actie PPO (die acties sequentieel deelt) en een MIP-gebaseerd waarde-lookahead algoritme. De verbeteringen varieerden van 4,0% tot 23,7% ten opzichte van de beste benchmark.
  • Ablatieonderzoek: Het toepassen van de BTSD-interface op verschillende DRL-backbones (PPO, SAC, DQN) verbeterde consequent de prestaties ten opzichte van hun "vanilla" tegenhangers (die action masking/projectie gebruikten), wat bevestigt dat de winst voortkomt uit de actie-interface en niet uit de specifieke optimizer.

5. Betekenis en Claims

Het paper claimt dat Bellman–Taylor score decoding een generaal, plug-and-play interface biedt voor het toepassen van standaard off-the-shelf DRL-algoritmen op MDP's met complexe, toestandsafhankelijke toelaatbare actiesets.

• Scheiding van Zorgen: Het scheidt het leren van waarde-gradiënten (behandeld door standaard DRL in een Euclidische ruimte) van het afdwingen van operationele beperkingen (behandeld door een vaste optimalisatie-decoder).
• Geen Differentiabele Optimalisatie: In tegenstelling tot differentiabele optimalisatielagen, vereist deze methode niet dat de decoder differentieerbaar is, wat het geschikt maakt voor problemen met integer of combinatorische beperkingen waar gradiënten ongedefinieerd of moeilijk te benaderen zijn.
• Geleerde Indexregels: In de wachtrijcontext leert de methode effectief een toestandsafhankelijke, max-weight-type dispatching regel, waardoor optimale indices automatisch worden ontdekt zonder handmatige specificatie.
• Bescheiden Omvang: De auteurs erkennen dat de aanpak computationele overhead introduceert (het oplossen van een optimalisatieprobleem per actiekeuze) en dat de beleidsklasse beperkt wordt door de Taylor-benadering. Zij merken op dat het framework momenteel een bekende transitie-dynamiek en een specifieke structurele representatie van de post-actie toestand veronderstelt, wat de directe toepassing op puur data-gedreven settings kan beperken zonder verdere aanpassing.

Het paper concludeert dat dit framework de kloof overbrugt tussen standaard continue-actie DRL-solvers en de complexe, beperkte actieruimtes die gangbaar zijn in operations research, en biedt een pad naar bijna-optimale controle zonder uitgebreide probleem-specifieke algoritmische engineering.