Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning

Technische Samenvatting: Slimme Transformatie zonder Neuronen – Rechtvaardige Expansie van Metro-netwerken met Tabulaire Reinforcement Learning

Probleemdefinitie
Het artikel behandelt het Metro Network Expansion Problem (MNEP), een specifieke subset van het Transport Network Design Problem (TNDP). Het doel is om een nieuwe metrolijn te ontwerpen binnen een bestaand stedelijk netwerk om de gevangen reisvraag te maximaliseren, onderworpen aan beperkingen op het bouwbudget ($B$) en het maximale aantal stations ($T$). Traditioneel wordt MNEP gemodelleerd als een combinatorisch optimalisatieprobleem waarbij de stad wordt gerepresenteerd als een raster, en het doel is om een sequentie van aangrenzende cellen te vinden die een lijn vormt en de som van de vervulde Origin-Destination (OD) vraag maximaliseert.

Een kritische kloof in de literatuur is de afhankelijkheid van Deep Reinforcement Learning (Deep RL) voor deze problemen. Hoewel Deep RL succes heeft getoond bij complexe sequentiële besluitvorming, is het computationeel duur, milieubelastend en fungeert het vaak als een "black box", wat een gebrek aan interpreteerbaarheid met zich meebrengt. De auteurs stellen dat MNEP fundamenteel een statisch optimalisatieprobleem is met beperkte inputkenmerken en inherente schaalbaarheidsbeperkingen (bijv. vaste station-afstand), wat suggereert dat complexe neurale netwerken niet noodzakelijk zijn. Bovendien geven bestaande benaderingen vaak de voorkeur aan efficiëntie (utilitarisme) boven sociale rechtvaardigheid, waardoor ze er niet in slagen de rechtvaardige verdeling van transportvoordelen over verschillende sociaaleconomische groepen adequaat aan te pakken.

Methodologie
De auteurs stellen een nieuw framework voor dat een herformulering van het probleem combineert met een Tabular Reinforcement Learning (Tabular RL) benadering, waarbij expliciet rekening wordt gehouden met sociale rechtvaardigheidscriteria.

1. Probleemherformulering (NMRDP):
   Het MNEP wordt geherformuleerd als een Non-Markovian Reward Decision Process (NMRDP). In tegen tegenovergestelde van eerdere Deep RL-benaderingen die elke gridcel als een potentiële actie behandelen (wat resulteert in een actieruimte die lineair schaalt met de gridgrootte, $O(n \times m)$), ontkoppelt de voorgestelde methode het proces in twee fasen:

• Initiële Toestandsselectie: De agent selecteert een startcel voor de metrolijn.
• Sequentiële Navigatie: De agent beweegt door het raster door een van acht discrete richtingen te kiezen (N, Z, O, W en vier diagonalen).
  Dit reduceert de actieruimte tot een constante grootte van 8 (ongeacht de griddimensies) voor alle stappen na de initiële selectie, waardoor de tijdscomplexiteit wordt gereduceerd tot $O(1)$ per stap. De toestand wordt vereenvoudigd tot de huidige locatie van de agent. Omdat de beloning afhangt van de geschiedenis van de bezochte stations (om directe vraag en overstapdraag te berekenen), schendt dit proces de strikte Markov-eigenschap, vandaar de NMRDP-formulering.

2. Algoritme (Monte Carlo Tabular RL):
   De auteurs maken gebruik van een Monte Carlo-gebaseerd Tabular RL-algoritme. De agent onderhoudt twee tabellen:

• $V_{start}(S_0)$: Schat de verwachte return voor het selecteren van een specifieke cel als startpunt.
• $Q(S, A)$: Schat de waarde van het nemen van een specifieke directionele actie vanuit een huidige toestand.
  De agent gebruikt een $\epsilon$-greedy strategie voor exploratie en exploitatie. Updates worden uitgevoerd aan het einde van elke episode met behulp van Monte Carlo-schatting van de totale return $J$, waarbij de $V$- en $Q$-waarden worden aangepast op basis van het verschil tussen de geschatte en de werkelijke returns.

3. Integratie van Sociale Rechtvaardigheid:
   De beloningsfunctie wordt uitgebreid voorbij eenvoudige vraagmaximalisatie om sociale rechtvaardigheid te bevatten. De auteurs definiëren groepen ($G$) op basis van sociaaleconomische indicatoren (specifiek huizenprijsindices als proxy voor ontwikkeling). Drie beloningsformuleringen worden getest:

• Utilitaristisch (Maximale Efficiëntie): Maximaliseert de totale vervulde vraag.
• Gelijke Verdeling (Horizontale Rechtvaardigheid): Gebruikt de Generalized Gini Index (GGI) om discrepanties in voordelen tussen groepen te minimaliseren.
• Rawlsiaanse Rechtvaardigheid (Verticale Rechtvaardigheid): Maximaliseert het voordeel voor de meest benadeelde groep (laagste huizenprijskwintiel).

Belangrijkste Bijdragen

• Probleemherformulering: Het artikel demonstreert dat het herformuleren van MNEP als een NMRDP met een ontkoppelde actieruimte het gebruik van eenvoudige tabulaire methoden mogelijk maakt, wat de zoekruimte drastisch verkleint zonder de oplossingsruimte te beperken.
• Algoritmische Efficiëntie: Het voorstel van een Monte Carlo Tabular RL-algoritme dat concurrerende prestaties levert met aanzienlijk minder trainings-episodes vergeleken met Deep RL.
• Rechtvaardigheidsbewust Framework: De integratie van diverse sociale welzijnsdoelstellingen (utilitaristisch, egalitair en Rawlsiaans) in het RL-framework, wat een flexibel mechanisme biedt om efficiëntie en rechtvaardigheid in transportplanning te balanceren.
• Interpreteerbaarheid: Het gebruik van tabulaire methoden biedt inherente interpreteerbaarheid, waardoor besluitvormers optimale beleidsregels, beloningsverdelingen en Q-waarden direct kunnen visualiseren, in tegen tegenovergestelde van de latente representaties van Deep RL.

Experimentele Resultaten
De methode werd geëvalueerd in twee echte omgevingen: Xi'an, China, en Amsterdam, Nederland.

• Prestaties: TabularMNEP behaalde prestaties die vergelijkbaar zijn met state-of-the-art Deep RL-methoden over alle beloningsfuncties (Efficiëntie, GGI(2), GGI(4) en Rawls). In sommige gevallen presteerde het licht onder Deep RL, maar bleef het binnen de betrouwbaarheidsintervallen, terwijl het significant beter presteerde dan Genetic Algorithms en Greedy Search baselines.
• Efficiëntie: De Tabulaire benadering vereiste slechts 25.000 trainings-episodes, een 18-voudige reductie vergeleken met de 448.000 episodes die nodig waren voor de Deep RL-baseline.
• Milieu-impact: Door de verminderde trainingstijd en het gebrek aan GPU-afhankelijkheid (hoewel getest op GPU-nodes voor een eerlijke vergelijking), verminderde de Tabulaire methode de geschatte koolstofemissies met een factor 12 gemiddeld.
• Rechtvaardigheid uitkomsten: De experimenten bevestigden dat verschillende beloningsfuncties het netwerkontwerp succesvol hebben verschoven. Maximaal Efficiëntie gaf de voorkeur aan gebieden met een hoge vraag (vaak welvarender), terwijl GGI en Rawlsiaanse beloningen de voordelen succesvol herverdeelden naar lagere inkomensgroepen, zij het met variërende kosten voor de algehele efficiëntie.

Betekenis en Claims
Het artikel beweert dat complexe, black-box Deep Learning-modellen niet altijd noodzakelijk zijn voor combinatorische optimalisatieproblemen zoals MNEP. Door het probleem zorgvuldig te herformuleren om de actieruimte te verkleinen, kunnen eenvoudigere, hulpbron-efficiënte en interpreteerbare tabulaire methoden state-of-the-art resultaten opleveren. De auteurs benadrukken dat deze benadering een "reproduceerbare, modulaire, interpreteerbare en hulpbron-efficiënte oplossing" biedt.

Het werk benadrukt het belang van het overwegen van sociale rechtvaardigheid in geautomatiseerde transportplanning, en laat zien dat RL kan worden afgestemd om te optimaliseren voor rechtvaardigheid zonder te veel op te offeren aan efficiëntie. De auteurs houden echter een bescheiden standpunt aan met betrekking tot schaalbaarheid, waarbij ze erkennen dat hoewel tabulaire methoden goed werken voor MNEP vanwege beperkte toestandsrepresentaties, ze mogelijk niet generaliseren naar problemen met inherent enorme toestandsrepresentaties. Ze waarschuwen ook dat zonder zorgvuldige beloningsontwerp en menselijk toezicht, geautomatiseerde besluitvorming in stedelijke planning het risico loopt bestaande vooroordelen te versterken.