🤖 machine learning

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

This paper proposes a resource-efficient and interpretable tabular reinforcement learning approach, reformulated as a Non-Markovian Rewards Decision Process with social equity criteria, to solve the Metro Network Expansion Problem with significantly reduced training episodes and carbon emissions compared to Deep RL while maintaining competitive performance in real-world scenarios.

Original authors: Dimitris Michailidis, Sennay Ghebreab, Fernando P. Santos

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dimitris Michailidis, Sennay Ghebreab, Fernando P. Santos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a city planner trying to build a new subway line. Your goal is to connect as many people as possible to jobs, schools, and friends, but you have a limited budget and can't just dig tunnels anywhere. This is a massive puzzle known as the Metro Network Expansion Problem.

For a long time, experts tried to solve this with complex math or by guessing and checking (heuristics). Recently, many researchers started using Deep Reinforcement Learning (Deep RL). Think of Deep RL as a super-intelligent, high-powered robot brain that learns by playing a video game millions of times. It's very good at finding solutions, but it's also like a "black box": it takes a huge amount of electricity, takes a long time to train, and it's hard to understand why it made a specific decision.

This paper argues that for building subway maps, we don't actually need that super-complex robot brain. Instead, the authors propose a "Tabular Reinforcement Learning" approach, which is like using a simple, well-organized spreadsheet instead of a supercomputer.

Here is a breakdown of their ideas using simple analogies:

1. The "Neuron" vs. The "Spreadsheet"

The Old Way (Deep RL): Imagine trying to learn the best route through a city by hiring a genius architect who needs to see every single street corner in the world simultaneously to make a decision. This requires a massive team (computational power) and a lot of coffee (electricity).
The New Way (Tabular RL): The authors realized that subway lines are actually quite simple. They are just straight(ish) lines connecting a few points. You don't need a genius architect; you just need a guidebook.
- Instead of looking at the whole city at once, the agent (the planner) just looks at: "I am currently at Station A. Which of the 8 directions (North, South, East, West, etc.) should I go next?"
- They use a table (like a spreadsheet) to record: "If I am at Station A and go North, I get X points of satisfaction."
- The Result: This method is like swapping a Ferrari for a reliable bicycle. It gets you to the same destination, but it's much faster to build, uses way less fuel, and you can see exactly how the gears work.

2. The "Fairness" Twist

Usually, subway planners just try to help the most people possible (Efficiency). But what if that means only helping rich neighborhoods while ignoring poorer ones?
The authors added a "fairness" feature to their spreadsheet. They tested three different "rules" for the planner:

The "Max Efficiency" Rule: "Help as many people as possible, regardless of who they are."
The "Equal Sharing" Rule: "Make sure every neighborhood gets a roughly equal slice of the pie."
The "Rawlsian" Rule: Named after a philosopher, this rule says, "First, make sure the poorest neighborhood gets the best help possible, then worry about the rest."

The paper shows that their simple spreadsheet method can easily switch between these rules, just like changing a setting on a thermostat, without needing to retrain a massive AI model.

3. The Real-World Test

The team tested their method in two real cities: Xi'an, China and Amsterdam, Netherlands.

Speed: Their simple method needed 18 times fewer training episodes (practice runs) than the complex Deep RL method.
Green Energy: Because it required less computing power, it produced 12 times less carbon emissions (CO2) during the training process.
Performance: Despite being "dumber" and simpler, it found solutions that were just as good as the complex AI.

4. Why "Transparency" Matters

The biggest advantage isn't just speed; it's understanding.

Deep RL is like a magic trick: you put a city in, and a subway map comes out, but you can't see the magician's hands. If a city council asks, "Why did you put the station there?", the AI might not have a clear answer.
Tabular RL is like a clear recipe. Because the decisions are stored in a simple table, a human can look at it and say, "Ah, I see. The computer chose to go North because that specific block had high demand." This makes it much easier for humans to trust and adjust the plan.

The Bottom Line

The paper claims that for specific, structured problems like designing subway lines, we don't need to overcomplicate things with "neural networks" (AI brains). A smart, simple, and transparent approach using tables works just as well, saves a massive amount of energy, and gives humans the control and understanding they need to make fair decisions.

Note on Limitations: The authors admit this "simple spreadsheet" method works great for subway lines because the rules are clear and the space isn't infinite. However, they warn it might not work for problems that are much more chaotic or have huge, unstructured state spaces.

Technical Summary: Smart Transportation Without Neurons – Fair Metro Network Expansion with Tabular Reinforcement Learning

Problem Definition
The paper addresses the Metro Network Expansion Problem (MNEP), a specific subset of the Transport Network Design Problem (TNDP). The objective is to design a new metro line within an existing urban network to maximize captured travel demand, subject to constraints on construction budget ( $B$ ) and the maximum number of stations ( $T$ ). Traditionally, MNEP is modeled as a combinatorial optimization problem where the city is represented as a grid, and the goal is to find a sequence of adjacent cells forming a line that maximizes the sum of satisfied Origin-Destination (OD) demand.

A critical gap identified in the literature is the reliance on Deep Reinforcement Learning (Deep RL) for these problems. While Deep RL has shown success in complex sequential decision-making, it is computationally expensive, environmentally costly, and often functions as a "black box," lacking interpretability. The authors argue that MNEP is fundamentally a static optimization problem with limited input features and inherent scalability constraints (e.g., fixed station spacing), suggesting that complex neural networks may be unnecessary. Furthermore, existing approaches often prioritize efficiency (utilitarianism) over social equity, failing to adequately address the fair distribution of transport benefits across different socioeconomic groups.

Methodology
The authors propose a novel framework that combines a reformulation of the problem with a Tabular Reinforcement Learning (Tabular RL) approach, explicitly incorporating social equity criteria.

Problem Reformulation (NMRDP):
The MNEP is reformulated as a Non-Markovian Reward Decision Process (NMRDP). Unlike previous Deep RL approaches that treat every grid cell as a potential action (resulting in an action space scaling linearly with grid size, $O(n \times m)$ ), the proposed method decouples the process into two stages:
- Initial State Selection: The agent selects a starting cell for the metro line.
- Sequential Navigation: The agent moves through the grid by choosing one of eight discrete directions (N, S, E, W, and four diagonals).
  This reduces the action space to a constant size of 8 (regardless of grid dimensions) for all steps after the initial selection, reducing time complexity to $O(1)$ per step. The state is simplified to the agent's current location. Because the reward depends on the history of visited stations (to calculate direct and transfer demand), the process violates the strict Markov property, hence the NMRDP formulation.
Algorithm (Monte Carlo Tabular RL):
The authors employ a Monte Carlo-based Tabular RL algorithm. The agent maintains two tables:
- $V_{start}(S_0)$ : Estimates the expected return for selecting a specific cell as the starting point.
- $Q(S, A)$ : Estimates the value of taking a specific directional action from a current state.
  The agent uses an $\epsilon$ -greedy strategy for exploration and exploitation. Updates are performed at the end of each episode using Monte Carlo estimation of the total return $J$ , adjusting the $V$ and $Q$ values based on the difference between the estimated and actual returns.
Social Equity Integration:
The reward function is extended beyond simple demand maximization to include social equity. The authors define groups ( $G$ ) based on socioeconomic indicators (specifically house price indices as a proxy for development). Three reward formulations are tested:
- Utilitarian (Max Efficiency): Maximizes total satisfied demand.
- Equal Sharing (Horizontal Equity): Uses the Generalized Gini Index (GGI) to minimize disparities in benefits across groups.
- Rawlsian Justice (Vertical Equity): Maximizes the benefit for the most disadvantaged group (lowest house price quintile).

Key Contributions

Problem Reformulation: The paper demonstrates that reformulating MNEP as an NMRDP with a decoupled action space allows for the use of simple tabular methods, drastically reducing the search space complexity without restricting the solution space.
Algorithmic Efficiency: The proposal of a Monte Carlo Tabular RL algorithm that achieves competitive performance with significantly fewer training episodes compared to Deep RL.
Equity-Aware Framework: The integration of diverse social good objectives (utilitarian, egalitarian, and Rawlsian) into the RL framework, providing a flexible mechanism to balance efficiency and fairness in transport planning.
Interpretability: The use of tabular methods provides inherent interpretability, allowing decision-makers to visualize optimal policies, reward distributions, and Q-values directly, unlike the latent representations of Deep RL.

Experimental Results
The method was evaluated in two real-world environments: Xi'an, China, and Amsterdam, Netherlands.

Performance: TabularMNEP achieved performance comparable to state-of-the-art Deep RL methods across all reward functions (Efficiency, GGI(2), GGI(4), and Rawls). In some cases, it slightly underperformed Deep RL but remained within confidence intervals, while significantly outperforming Genetic Algorithms and Greedy Search baselines.
Efficiency: The Tabular approach required only 25,000 training episodes, an 18-fold reduction compared to the 448,000 episodes required by the Deep RL baseline.
Environmental Impact: Due to the reduced training time and lack of GPU dependency (though tested on GPU nodes for fairness in comparison), the Tabular method reduced estimated carbon emissions by a factor of 12 on average.
Equity Outcomes: The experiments confirmed that different reward functions successfully shifted the network design. Max Efficiency favored high-demand areas (often wealthier), while GGI and Rawlsian rewards successfully redistributed benefits to lower-income groups, though at varying costs to overall efficiency.

Significance and Claims
The paper claims that complex, black-box Deep Learning models are not always necessary for combinatorial optimization problems like MNEP. By carefully reformulating the problem to reduce the action space, simpler, resource-efficient, and interpretable tabular methods can yield state-of-the-art results. The authors emphasize that this approach offers a "replicable, modular, interpretable, and resource-efficient solution."

The work highlights the importance of considering social equity in automated transport planning, demonstrating that RL can be tuned to optimize for fairness without sacrificing too much efficiency. However, the authors maintain a modest stance regarding scalability, acknowledging that while tabular methods work well for MNEP due to constrained state spaces, they may not generalize to problems with inherently massive state representations. They also caution that without careful reward design and human oversight, automated decision-making in urban planning risks reinforcing existing biases.