Semi-Markov Reinforcement Learning for City-Scale EV Ride-Hailing with Feasibility-Guaranteed Actions An Nguyena,∗ , Hoang Nguyena , Phuong Lea , Hung Phama , Cuong Doa,b,∗ and Laurent El Ghaouia,b a College of Engineering and Computer Science, VinUniversity, Hanoi, Vietnam
arXiv:2604.25848v1 [cs.AI] 28 Apr 2026
b Center for Environmental Intelligence, VinUniversity, Hanoi, Vietnam
ARTICLE INFO
ABSTRACT
Keywords: Reinforcement learning Distributionally robust optimization Graph neural networks Constrained decision making Electric vehicle fleet management
We study city-scale control of electric-vehicle (EV) ride-hailing fleets where dispatch, repositioning, and charging decisions must respect charger and feeder limits under uncertain, spatially correlated demand and travel times. We formulate the problem as a hex-grid semi-Markov decision process (semiMDP) with mixed actions—discrete (serve, reposition, charge) and continuous (charging power)—and variable action durations. To guarantee physical feasibility at both training and deployment, we learn over intentions produced by a masked, temperature-annealed policy. These intentions are projected, at every decision step, through a time-limited rolling mixed-integer linear program (MILP) that strictly enforces state-of-charge, port, and feeder constraints. To mitigate distributional shifts, we optimize a Soft Actor–Critic (SAC) agent against a true Wasserstein-1 ambiguity set, employing a graphaligned Mahalanobis ground metric to capture spatial correlations. The robust backup utilizes the Kantorovich–Rubinstein dual with a projected subgradient inner loop and a primal–dual risk budget update. Our architecture combines a two-layer Graph Convolutional Network (GCN) encoder, twin critics, and a value network driving the adversary. Experiments on a large-scale EV fleet simulator built from NYC taxi data show that PD–RSAC achieves the highest net profit, reaching $1.22M, compared with $0.58M–$0.70M for strong heuristic, single-agent RL, and multi-agent RL baselines, including Greedy, SAC, MAPPO, and MADDPG, while maintaining zero feeder-limit violations.
1. Introduction Electric-vehicle (EV) ride-hailing fleets are increasingly crucial for urban mobility, requiring operators to continuously assign vehicles to requests, reposition idle units, and schedule charging. These decisions must strictly adhere to state-of-charge (SoC) safety limits, charger-port capacities, and power caps, all while maintaining high service quality. However, demand and travel times vary stochastically over space and time, exhibiting correlated and nonstationary patterns. Consequently, fleet control represents a challenging constrained, sequential decision-making problem under uncertainty. Optimization vs. Learning. Early efforts in fleet coordination primarily relied on optimization-based techniques. For instance, [1] formulated a bilevel optimization model for multimodal transit, while [2] addressed user fairness via integer programming. Similarly, [3] proposed recedinghorizon control (RHC) for dispatching based on real-time sensing. While these approaches explicitly encode operational constraints, they rely heavily on accurate forecasts and suffer from scalability issues as system size increases. Conversely, Reinforcement Learning (RL) has been adopted to improve scalability and efficiency. Recent works optimize dispatching [4, 5, 6, 7], vehicle repositioning [8, 9], and dynamic pricing [10, 11] using Deep Q-Networks or Actor– Critic methods. A closely related study by [12] combines ∗ Corresponding author
[email protected] (A. Nguyen); [email protected] (C. Do); [email protected] (L.E. Ghaoui) ORCID (s): 0009-0001-3971-7557 (A. Nguyen); 0000-0003-4785-4524 (C. Do); 0000-0002-0499-5610 (L.E. Ghaoui)
A. Nguyen et al.: Preprint submitted to Elsevier
MAPPO with binary linear programming for Shared Autonomous EV scheduling. Graph-based multi-agent reinforcement learning has also been explored for structured coordination; for example, Hu et al. [13] propose a decentralized graph-based MARL framework using reward machines. Despite their empirical success, standard RL methods typically fail to guarantee hard constraints (e.g., grid limits) and remain brittle to distributional shifts between training and deployment. The Challenge of Feasibility. Ensuring safety in RL is a longstanding challenge. Approaches like Constrained Policy Optimization [14] or Lagrangian relaxation satisfy constraints only in expectation, which is insufficient for gridconstrained operations where a single violation can trip a feeder. While differentiable optimization layers like OptNet [15] and CvxpyLayers [16] can project actions into feasible sets, they are limited to convex problems. Related efforts on safe and constrained reinforcement learning include the control-barrier-function-based framework of Liu et al. [17], which studies affine nonlinear systems with state constraints and input saturation. Our domain involves discrete decisions (dispatch modes) and non-convex dynamics, necessitating a mixed-integer projection. Unlike prior works using heuristic repairs, we propose embedding a time-limited rolling MILP directly into the decision loop to guarantee physical feasibility. Decision Making Under Uncertainty. Furthermore, standard RL assumes identical training and testing dynamics. To address performance degradation under distributional shifts, robust MDPs optimize worst-case performance. Early works [18, 19] used KL-divergence or rectangular
Page 1 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
ambiguity sets, often leading to overly conservative policies. More recently, Wasserstein-based ambiguity sets have been incorporated into robust MDPs and reinforcement learning [20, 21], enabling principled robustness against distributional perturbations with provable guarantees. Foundational studies in Distributionally Robust Optimization (DRO) demonstrate that Wasserstein balls can effectively capture geometric perturbations in data distributions [22] and establish a close connection between DRO and adversarial training [23]. However, standard Wasserstein approaches mainly focus on unconstrained settings with continuous state spaces and typically rely on Euclidean ground metrics (𝐿2 distance), which ignore the underlying graph topology and fail to capture network-induced spatial interactions in transportation systems. In this work, we introduce a graphaligned ground metric and integrate Wasserstein DRO with mixed-integer feasibility guarantees for spatially structured transportation grids. Contributions. We develop a planning-aware, distributionally robust RL framework for controlling EV fleets on a hexagonal grid. Instead of executing actions directly, our policy outputs intentions that are projected through a rolling MILP. To address uncertainty, we optimize a Soft Actor– Critic (SAC) [24] agent against a Wasserstein-1 ambiguity set equipped with a graph-aligned Mahalanobis metric. Our contributions are threefold: (i) A semi-MDP formulation with duration-aware backups; (ii) A feasible-action architecture embedding a rolling MILP projection; and (iii) A graph-aligned Wasserstein-1 robust RL method that mitigates spatially correlated uncertainty.
2. System Model and WDRO Objective Figure 1 illustrates the city-scale EV ride-hailing setting considered in this work, including the hex-grid partition, the main fleet decisions, and the key operational constraints. We consider a discrete-time horizon 𝑡 ∈ {0, 1, … , 𝑇 − 1} with step size Δ𝑡 > 0. The service region is discretized into a hexagonal grid = {1, … , 𝑚}, where each hex ℎ has a set of neighbors (ℎ). The fleet comprises 𝑁 electric vehicles = {1, … , 𝑁}. Charging infrastructure is distributed across a subset of hexes ⊆ . Each station 𝑠 ∈ is characterized by: port
• 𝐶𝑠 : total number of physical charging plugs (ports) available. • 𝑃𝑠max : maximum charging power per vehicle at station
Figure 1: Illustration of the city-scale EV ride-hailing problem on a hexagonal grid.
2.1. Hex discretization and exogenous scenarios At each step 𝑡, the system environment is driven by an exogenous scenario 𝜉𝑡 = (𝐷𝑡 , 𝑇𝑡 ). Here, 𝐷𝑡 ∈ ℝ𝑚×𝑚 + represents the Origin-Destination (OD) demand intensity, where 𝐷𝑡 (ℎ1 , ℎ2 ) is the expected number of requests from hex ℎ1 to ℎ2 . 𝑇𝑡 ∈ ℕ𝑚×𝑚 denotes the discrete travel time field in multiples of Δ𝑡, with 𝑇𝑡 (ℎ1 , ℎ2 ) ≥ 1. These parameters are stochastic and spatially correlated.
2.2. Aggregated system state To enable scalable learning, we adopt an aggregate state representation 𝑠𝑡 that captures fleet dynamics at a hex-level granularity rather than tracking individual vehicles: ) ( (1) 𝑠𝑡 = 𝑋𝑡fleet , 𝑋𝑡demand , 𝑋𝑡infra , 𝑡 . Specifically: busy
(𝑏) }ℎ∈ summarizes the counts • 𝑋𝑡fleet = {𝑛idle , 𝑛ℎ,𝑡 , 𝐸̄ ℎ,𝑡 ℎ,𝑡 of idle/busy vehicles and the average SoC of busy vehicles in each zone.
• 𝑋𝑡demand = {𝐷𝑡 (ℎ, ⋅), 𝐷𝑡 (⋅, ℎ)}ℎ∈ summarizes the demand outflow and inflow for each hex. max • 𝑋𝑡infra = {𝑢𝑠,𝑡 , 𝑞𝑠,𝑡 , 𝑝elec 𝑠,𝑡 }𝑠∈ ∪{𝑃feed } captures station utilization 𝑢, queue length 𝑞, dynamic electricity price max . 𝑝elec , and the feeder limit 𝑃feed
2.3. Scheduling objective under distributional uncertainty Given a stationary policy 𝜋, the (episode) discounted return along a scenario sequence 𝜉 = (𝜉0 , … , 𝜉𝑇 −1 ) is
𝑠. max : total power capacity of the local grid feeder • 𝑃feed supplying the station set.
Vehicle 𝑖 is modeled by its current battery energy (SoC) 𝐸𝑖,𝑡 ∈ [0, 𝐸𝑖max ], charging efficiency 𝜂𝑐 ∈ (0, 1], and energy consumption rate 𝜂drv > 0 per √ unit distance. For 𝑄 ≻ 0, we use the shorthand ‖𝑥‖𝑄 ∶= 𝑥⊤ 𝑄𝑥. A. Nguyen et al.: Preprint submitted to Elsevier
𝑅(𝜉; 𝜋) = 𝔼
[𝑇 −1 ∑
] 𝑡
𝛾 𝑟𝑡 ,
𝑡=0
where 𝑟𝑡 is the reward at decision epoch 𝑡 (defined in Sec. 3), and 0 < 𝛾 < 1 is a discount factor. Let 𝑃̂ denote the empirical distribution of scenarios obtained from historical data. To hedge against distributional shifts, we optimize a distributionally robust objective over Page 2 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
a Wasserstein-1 ball of radius 𝜌 > 0 (under a metric 𝑑𝑄 defined later in Sec. 5): max 𝜋
inf
(2)
𝔼𝜉∼𝑃 [𝑅(𝜉; 𝜋)] .
𝑑
𝑃 ∶ 𝑊1 𝑄 (𝑃 ,𝑃̂ )≤𝜌
The robust backup used in our semi-MDP implementation is a sample-based approximation of (2), given in Sec. 5.
3. Hex Semi-MDP Formulation Since transportation tasks (trips) and charging sessions have variable durations that may span multiple time steps Δ𝑡, we model the control problem as a Semi-Markov Decision Process (semi-MDP).
where 𝑚𝑖,𝑡 ∈ {serve, reb, chg} is a high-level mode. These “soft” intentions are then passed to the MILP projection layer (Sec. 4) to be converted into physically feasible “hard” actions.
3.3. Reward We retain exactly four components to balance revenue, costs, and service quality: ∑ ∑ pu 𝑟𝑡 (𝑠𝑡 , 𝑎𝑡 ) = 𝑅𝑡 (ℎ𝑜 , ℎdo 𝑐 drv 𝑑𝑖,𝑡 𝑜 )−
chg 𝑖,𝑡
orders
trip revenue
driving/ops cost
∑
𝑝elec 𝑝 Δ𝑡 𝑠(𝑖),𝑡 𝑖,𝑡
(8)
⏟⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏟ electricity
∑
− 𝜆wait
(3)
∪ (ℎ𝑖,𝑡 ) ∪ . ⏟⏟⏟ ⏟⏟⏟ ⏟⏟⏟ reposition
⏟⏞⏞⏞⏟⏞⏞⏞⏟
𝑖∈
For vehicle 𝑖 at hex ℎ𝑖,𝑡 with SoC 𝐸𝑖,𝑡 , the set of valid candidate actions 𝑖,𝑡 includes: 𝑖,𝑡 =
⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ −
3.1. Per-vehicle actions and SoC Guard
serve 𝑖,𝑡
𝑖∈
𝑜∈served𝑡
𝑜∈𝑡
| | wait 𝑜 + 𝜆drop |dropped𝑡 | | |
⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟
stations
pu However, before an order 𝑜 = (ℎ𝑜 → ℎdo 𝑜 ) is considered a
customer service. pu drv is Here, 𝑅𝑡 (ℎ𝑜 , ℎdo 𝑜 ) is the revenue from trip 𝑜, 𝑐
valid candidate, it must pass a State-of-Charge (SoC) guard ensuring the vehicle has enough energy to reach the pickup point, complete the trip, and maintain a safety buffer 𝐸𝑖min : ) ( pu pu ) + 𝐸𝑖min . (4) 𝐸𝑖,𝑡 ≥ 𝜂drv 𝑒pk (ℎ𝑖,𝑡 , ℎ𝑜 ) + 𝑒trip (ℎ𝑜 , ℎdo 𝑜
the per-distance driving cost, 𝑑𝑖,𝑡 is the distance traveled by is the electricity price at station 𝑠(𝑖), wait 𝑜 vehicle 𝑖, 𝑝elec 𝑠(𝑖),𝑡 is the waiting time for order 𝑜, |dropped𝑡 | is the number of dropped orders, and 𝜆wait , 𝜆drop are weighting coefficients.
Here 𝑒pk (ℎ1 , ℎ2 ) and 𝑒trip (ℎ1 , ℎ2 ) denote the energy required for pickup and trip legs, respectively. If this condition fails, the order is masked out from the vehicle’s action space. The per-vehicle action 𝑎𝑖,𝑡 is a mixed tuple of discrete assignments and continuous power: ) ( 𝑎𝑖,𝑡 = {𝑥𝑖𝑜 }𝑜∈serve , {𝑦𝑖𝑔 }𝑔∈ (ℎ𝑖,𝑡 ) , {𝑧𝑖𝑠 }𝑠∈ chg , 𝑝𝑖,𝑡 , (5)
3.4. Semi-MDP dynamics and physics
subject to the constraints:
Charging is modeled as a 1-step action (Δchg = 1) to allow frequent re-evaluation of power levels, whereas trips are atomic actions spanning multiple steps. The physical state update equations are:
𝑖,𝑡
𝑖,𝑡
𝑥𝑖𝑜 , 𝑦𝑖𝑔 , 𝑧𝑖𝑠 ∈ {0, 1}, ∑ ∑ ∑ 𝑦𝑖𝑔 + 𝑧𝑖𝑠 = 1, 𝑥𝑖𝑜 + 𝑜
0 ≤ 𝑝𝑖,𝑡 ≤
𝑔
∑
𝑠
(6)
𝑠
Here, 𝑥, 𝑦, 𝑧 are binary variables indicating the choice of serving, repositioning, or charging, respectively. The con∑ ∑ ∑ straint 𝑥 + 𝑦 + 𝑧 = 1 ensures exactly one task is chosen per vehicle.
3.2. Policy parameterization (intentions) Instead of outputting the final action 𝑎𝑖,𝑡 directly (which requires satisfying complex global constraints like feeder limits), our neural policy samples intentions 𝑎̃𝑖,𝑡 . The policy factorizes into discrete mode selection and continuous power control: 𝜋𝜃 (𝑎𝑖,𝑡 |𝑠𝑡 ) = 𝜋𝜃 (𝑚𝑖,𝑡 |𝑠𝑡 ) ⋅ 𝜋𝜃 (𝑝𝑖,𝑡 |𝑚𝑖,𝑡 = chg, 𝑠𝑡 ), A. Nguyen et al.: Preprint submitted to Elsevier
pu
pu
Δserve = 𝑇𝑡 (ℎ𝑖,𝑡 , ℎ𝑜 ) + 𝑇𝑡 (ℎ𝑜 , ℎdo 𝑜 ), (9)
Δreb = 𝑇𝑡 (ℎ𝑖,𝑡 , 𝑔), Δchg = 1.
Serve: ℎ𝑖,𝑡+Δserve = ℎdo 𝑜 ,
( ) 𝐸𝑖,𝑡+Δserve = 𝐸𝑖,𝑡 − 𝜂drv 𝑒pk + 𝑒trip ,
𝑃𝑠max 𝑧𝑖𝑠 .
⋅ 𝜋𝜃 (target𝑖,𝑡 |𝑚𝑖,𝑡 , 𝑠𝑡 )
The system evolution is governed by the variable duration Δ(𝑎𝑡 ) of the selected action:
(7)
Reposition: ℎ𝑖,𝑡+Δreb = 𝑔,
(10)
𝐸𝑖,𝑡+Δreb = 𝐸𝑖,𝑡 − 𝜂drv 𝑒rb (ℎ𝑖,𝑡 , 𝑔),
Charge: ℎ𝑖,𝑡+1 = ℎ𝑖,𝑡 , 𝐸𝑖,𝑡+1 = min{𝐸𝑖max , 𝐸𝑖,𝑡 + 𝜂𝑐 𝑝𝑖,𝑡 Δ𝑡}. Here 𝑒rb (ℎ1 , ℎ2 ) denotes the energy required for a reposition leg from ℎ1 to ℎ2 . Longer charging sessions are represented by repeating the charge action across multiple consecutive steps. Aggregated idle vehicle counts 𝑛idle evolve according to ℎ,𝑡 a hex-level flow conservation principle balancing departures and arrivals from serving, repositioning, and completed charging; in the simulator, these counts are updated by explicitly tracking vehicles. Page 3 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
3.5. Duration-aware soft backup In a standard MDP, future rewards are discounted by 𝛾. In our semi-MDP, the discount factor depends on the action duration Δ(𝑎𝑡 ), leading to the non-robust soft target [ 𝑦𝑡 = 𝑟𝑡 + 𝛾 Δ(𝑎𝑡 ) 𝔼𝑎′ ∼𝜋 min 𝑄𝜓̄ 𝑘 (𝑠𝑡+Δ(𝑎𝑡 ) , 𝑎′ ) 𝑘 (11) ] ′ − 𝛼 log 𝜋(𝑎 |𝑠𝑡+Δ(𝑎𝑡 ) ) , where (𝑄𝜓̄ 𝑘 ) are slowly updated target critics. This ensures that longer trips are discounted more heavily, correctly reflecting the time value of money and opportunity cost.
4. Feasible-Action Projection via Rolling MILP Standard RL policies may output actions that violate complex coupled constraints (e.g., total power of all vehicles exceeding the grid feeder limit). To guarantee safety, we introduce a feasible-action projection layer Πfeas . Given the intention vector 𝑎̃𝑡 from the policy, we compute the closest feasible action 𝑎𝑡 by solving a mixed-integer linear program (MILP).
4.1. Time-limited MILP formulation Let 𝑣 stack all decision variables. The MILP objective seeks to maximize revenue while staying close to the policy’s intention: max
∑
𝑣
𝑅𝑡 (𝑜)𝑥𝑖𝑜 −
∑
𝑐 drv 𝑑𝑖,𝑡 −
𝑝elec 𝑠,𝑡 𝑝𝑖,𝑠 Δ𝑡−𝜇‖𝑣−𝑎̃𝑡 ‖1 . (12)
This maximization is subject to critical operational constraints: 1. Assignment logic: Each vehicle performs exactly one task, and each order is served by at most one vehicle: ∑ ∑ ∑ ∑ 𝑥𝑖𝑜 ≤ 1. (13) 𝑥𝑖𝑜 + 𝑦𝑖𝑔 + 𝑧𝑖𝑠 = 1, 𝑜
𝑔
𝑠
𝑖
2. Infrastructure limits: The number of charging veport hicles cannot exceed port capacity 𝐶𝑠 , and the aggregate max : charging power must respect the feeder limit 𝑃feed ∑
port
𝑧𝑖𝑠 ≤ 𝐶𝑠
,
∑
𝑖
𝑖,𝑠
1: Initialize empty action vector 𝑎𝑡 2: Initialize state 𝑠𝑡 , intention 𝑎̃𝑡 , residual feeder capacity
max 𝑃rem ← 𝑃feed 3: Sort vehicles by increasing SoC 𝐸𝑖,𝑡 4: for each vehicle 𝑖 do 5: Construct feasible action set 𝐶𝑖,𝑡 6: if exists feasible serving order then 7: Select order with highest immediate reward 8: else if exists feasible charging station with 𝑃𝑟𝑒𝑚 ≥ 𝑝𝑚𝑖𝑛 then 9: Select nearest station 𝑠 with available port 10: Allocate power 𝑝𝑖,𝑠 ← min(𝑃𝑠max , 𝑃rem ) 11: 𝑃rem ← 𝑃rem − 𝑝𝑖,𝑠 12: else 13: Select best energy-feasible reposition or idle action 14: end if 15: end for 16: return assembled action vector 𝑎𝑡
for order 𝑜 (pickup plus trip) if served by vehicle 𝑖, and 𝑒rb 𝑖𝑔 the distance for reposition from ℎ𝑖,𝑡 to 𝑔. We enforce ∑ ∑ 𝑒rb 𝑒od 𝐸𝑖,𝑡+1 = 𝐸𝑖,𝑡 − 𝜂drv 𝑖𝑔 𝑦𝑖𝑔 𝑖𝑜 𝑥𝑖𝑜 − 𝜂drv 𝑔
𝑜
+ 𝜂𝑐
∑
𝑝𝑖,𝑠 Δ𝑡,
(16)
𝑠
𝑖,𝑠
𝑖
𝑖,𝑜
∑
Algorithm 1 Greedy Fallback Projection
max 𝑝𝑖,𝑠 ≤ 𝑃feed ,
0 ≤ 𝑝𝑖,𝑠 ≤ 𝑃𝑠max 𝑧𝑖𝑠 . (14)
The feeder constraint couples all vehicles across stations. 3. Positive charging: If a vehicle chooses to charge (𝑧𝑖𝑠 = 1), it must draw a minimum non-zero power 𝑝min to prevent “fake” charging actions: 𝑝𝑖,𝑠 ≥ 𝑝min 𝑧𝑖𝑠 .
(15)
4. Energy feasibility: The SoC at the next step must remain within safety bounds [𝐸 min , 𝐸 max ] after accounting for consumption or charging. Let 𝑒od 𝑖𝑜 denote the total distance A. Nguyen et al.: Preprint submitted to Elsevier
𝐸𝑖min ≤ 𝐸𝑖,𝑡+1 ≤ 𝐸𝑖max .
∑ The projected total charging power is 𝑝𝑖 = 𝑠 𝑝𝑖,𝑠 . Solving this MILP at every step guarantees that the deployed action 𝑎𝑡 is physically valid. The projection operator is defined as 𝑎𝑡 = Πfeas (𝑠𝑡 , 𝑎̃𝑡 ), where the MILP is solved using a branch-and-bound solver under a fixed time limit 𝜏𝑚𝑎𝑥 . During the search, the solver maintains an incumbent, defined as the best feasible solution found so far. If at least one feasible solution is identified before timeout, the current incumbent is returned; otherwise, a greedy fallback rule is applied to ensure that a feasible action is always produced.
4.2. Greedy Fallback Projection In rare cases where the MILP solver fails to identify any feasible solution within the time limit, no incumbent is available. To ensure that a valid action is always produced, we activate a deterministic greedy fallback procedure. The fallback assigns decisions sequentially to vehicles in ascending order of state-of-charge (SoC), prioritizing energy-critical vehicles. For each vehicle, the algorithm selects the best feasible action subject to remaining infrastructure and energy constraints. We assume that a stay-idle action with zero energy consumption is always available in the feasible action set, which guarantees that at least one valid action exists for every vehicle at each decision step. Specifically, the procedure operates as Algorithm 1. Page 4 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
4.3. Feasibility Guarantee By construction, the projection operator Πfeas returns either (i) a MILP incumbent satisfying constraints (13)– (16), or (ii) a solution generated by the greedy fallback that explicitly enforces these constraints. Therefore, Πfeas always produces a physically admissible action.
5. Graph-Aligned Wasserstein Robustness The transition dynamics of our semi-MDP depend on the exogenous scenario 𝜉 = (𝐷, 𝑇 ) introduced in Sec. 2. To prevent the policy from overfitting to the empirical training distribution 𝑃̂ of such scenarios, we optimize its performance against a worst-case distribution 𝑃 within a Wasserstein ambiguity set.
5.1. Graph-aligned Mahalanobis ground metric Standard Wasserstein DRO uses the Euclidean distance ‖𝜉 − 𝜉 ′ ‖2 (e.g., [22]), which treats all scenario dimensions equally. In a city grid, perturbations should respect the spatial topology (e.g., demand shifting to a neighboring hex is more likely than shifting to a distant one). We define a graph-aligned metric 𝑑𝑄 : ‖ ‖ 𝑑𝑄 (𝜉, 𝜉 ′ ) = ‖𝑄1∕2 (𝜉 − 𝜉 ′ )‖ = ‖ 𝜉 − 𝜉′‖ ‖𝑄 , ‖ ‖2 ‖
(17)
where the precision matrix 𝑄 is constructed as 𝑄 = diag(𝑤) + 𝛽 𝑄graph . Here, diag(𝑤) scales features by their inverse variance, and 𝑄graph is a Laplacian-based matrix encoding the hex grid and OD graph structure. This metric penalizes spatially disjoint perturbations more heavily than smooth, local variations.
5.2. Wasserstein ambiguity set We define the ambiguity set 𝜌 (𝑃̂ ) as the set of all distributions 𝑃 that are within a Wasserstein-1 distance 𝜌 from the empirical distribution 𝑃̂ : 𝑑
𝜌 (𝑃̂ ) = { 𝑃 ∈ (ℝ𝑞 ) ∶ 𝑊1 𝑄 (𝑃 , 𝑃̂ ) ≤ 𝜌 }.
(18)
5.3. Robust backup via Kantorovich–Rubinstein dual Given a pre-decision state 𝑠𝑡 and projected action 𝑎𝑡 = Πfeas (𝑠𝑡 , 𝑎̃𝑡 ), we denote by 𝑠′ (𝜉) and Δ(𝜉) the successor state and action duration obtained by simulating the semi-MDP dynamics in Sec. 3 under scenario 𝜉 (so 𝑠′ (𝜉̂𝑡 ) = 𝑠𝑡+Δ(𝑎𝑡 ) and Δ(𝜉̂𝑡 ) = Δ(𝑎𝑡 )). The robust value target at a transition evaluates the worst-case expected value: [ ] 𝑦rob 𝔼𝑃 𝛾 Δ(𝜉) 𝑉𝜑 (𝑠′ (𝜉)) . (19) 𝑡 = 𝑟𝑡 + inf 𝑃 ∈𝜌 (𝑃̂ )
By utilizing the identity inf (𝑉 ) = − sup(−𝑉 ) and applying the Kantorovich–Rubinstein dual representation of the
A. Nguyen et al.: Preprint submitted to Elsevier
Wasserstein-1 ball to the cost −𝑉 (see, e.g., [22, 23]), we obtain the exact dual formulation: { [ ( Δ(𝜉) 𝑦rob 𝛾 𝑉𝜑 (𝑠′ (𝜉)) 𝑡 = 𝑟𝑡 + sup − 𝜆𝜌 + 𝔼𝑃̂ inf 𝜉 𝜆≥0 (20) )]} ̂ + 𝜆 𝑑𝑄 (𝜉, 𝜉) . Our WDRO analysis assumes that the discounted value function is locally Lipschitz under 𝑑𝑄 . In our implementation, scenarios 𝜉 are restricted to a compact set , inputs are normalized, and 𝑉𝜑 utilizes Lipschitz-continuous activations, ensuring this condition is practically satisfied. In practice, we adopt a penalized, sample-based variant with a time-varying dual variable 𝜆𝑡 and a bounded support set around each empirical sample 𝜉̂𝑡 , yielding the practical robust target: [ Δ(𝜉) ] 𝑦rob 𝑉𝜑 (𝑠′ (𝜉)) + 𝜆𝑡 𝑑𝑄 (𝜉, 𝜉̂𝑡 ) . (21) 𝑡 = 𝑟𝑡 − 𝜆𝑡 𝜌 + min 𝛾 𝜉∈
5.4. Inner minimization via projected (sub)gradient descent To solve the inner minimization in (21), we use projected (sub)gradient descent over 𝜉. Let 𝑓 (𝜉) = 𝛾 Δ(𝜉) 𝑉𝜑 (𝑠′ (𝜉)) + 𝜆𝑡 𝑑𝑄 (𝜉, 𝜉̂𝑡 ). We treat Δ(𝜉) as piecewise constant with respect to 𝜉 and ignore ∇𝜉 𝛾 Δ(𝜉) in practice, leading to the update ) ( 𝑘 𝜉 𝑘+1∕2 = 𝜉 𝑘 − 𝜂 𝛾 Δ(𝜉 ) ∇𝜉 𝑉𝜑 (𝑠′ (𝜉 𝑘 )) + 𝜆𝑡 𝑔𝑑 (𝜉 𝑘 ) , where ∇𝜉 𝑉𝜑 is obtained via backpropagation through the value network, and 𝑔𝑑 is the subgradient of the Wasserstein distance term: 𝑄(𝜉 − 𝜉̂𝑡 ) ⎧ , 𝜉 ≠ 𝜉̂𝑡 , ⎪ ‖ ‖ 𝑔𝑑 (𝜉) = ⎨ max{𝜀, ‖𝜉 − 𝜉̂𝑡 ‖ } ‖ ‖𝑄 ⎪ ⎩any 𝑔 ∶ ‖𝑔‖𝑄−1 ≤ 1, 𝜉 = 𝜉̂𝑡 . We then project 𝜉 𝑘+1∕2 back to the support set : 𝜉 𝑘+1 = Proj (𝜉 𝑘+1∕2 ), e.g., via closed-form projection for 𝑄-balls. Starting from 𝜉 0 = 𝜉̂𝑡 and iterating 𝐾 steps yields an approximate maximizer 𝜉 ⋆ used in (21).
5.5. Primal–dual risk-budget tracking To control the effective adversarial radius realized by the inner maximization, we track 𝜌̂𝑡 = 𝑑𝑄 (𝜉𝑡⋆ , 𝜉̂𝑡 ),
(22)
and update the dual variable 𝜆𝑡 toward a prescribed risk budget 𝜌target ∈ (0, 𝜌]: [ ( )] 𝜂 𝜆𝑡+1 = 𝜆𝑡 + 𝜂𝑡 𝜌̂𝑡 − 𝜌target , 𝜂𝑡 = √0 , (23) + 𝑡 where [ ⋅ ]+ denotes projection onto ℝ+ . This primal–dual rule penalizes the adversary when the realized radius exceeds 𝜌target and relaxes it otherwise. Theorem 3 (Sec. 7) shows that the average budget violation vanishes as 𝑡 → ∞ under mild conditions. Page 5 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
Figure 2: Overall PD–RSAC architecture. The simulator produces the aggregate hex-grid state, which is encoded by a shared GCN. The actor outputs mixed discrete–continuous intentions, which are projected by a rolling MILP into feasible actions before execution in the semi-MDP environment. Transitions are stored in a replay buffer. During training, the value network and Wasserstein adversary construct robust targets, while the twin critics and the primal–dual update refine the policy under distributional robustness.
6. Learning Architecture and Training At each decision epoch, the simulator produces the aggregated hex-grid state 𝑠𝑡 and scenario 𝜉̂𝑡 , as illustrated in Fig. 2. A shared hex-graph GCN encoder maps per-hex features to embeddings that are consumed by the actor, twin critics, and value network. The actor samples per-vehicle intentions, and a rolling MILP projection layer enforces SoC, portcapacity, and feeder constraints to obtain a feasible system action 𝑎𝑡 = Πfeas (𝑠𝑡 , 𝑎̃𝑡 ), which is executed in the semi-MDP environment. The resulting transitions are stored in a replay buffer and reused off-policy. For each sampled transition, the value network and Wasserstein adversary run the inner KR-dual loop to construct a worst-case scenario 𝜉 ⋆ , yielding robust targets 𝑦rob 𝑡 that update the critics and the actor, while the dual variable 𝜆 is adapted to track the desired risk budget.
6.1. Hex-graph encoder (GCN) We use a Graph Convolutional Network (GCN) [25] to extract spatial features. Let 𝐴 be the adjacency of the hex ∑ graph (with self-loops), 𝐴̃ = 𝐴 + 𝐼, 𝐷̃ = diag( 𝑗 𝐴̃ 𝑖𝑗 ), and 𝐴̂ = 𝐷̃ −1∕2 𝐴̃ 𝐷̃ −1∕2 . The node features Φ (vehicle counts, demand, infra features, time encodings) are processed as ( ) 𝐻 (1) = 𝜎 𝐴̂ Φ 𝑊0 + 𝟏𝑏⊤ , 0 ( ) (2) (1) ̂ 𝐸 = 𝐻 = 𝜎 𝐴 𝐻 𝑊1 + 𝟏𝑏⊤ , (24) 1
yielding hex embeddings 𝐸 that inform both the actor and critics. In our implementation, 𝜎 is the SiLU activation.
6.2. Actor with Gumbel–Softmax and squashed Gaussian To allow backpropagation through the discrete action selection, we use the Gumbel–Softmax reparameterization [26]. For a set of logits (𝑢𝑘 ), the discrete intention 𝑧̃ is sampled as: ( ) exp (𝑢𝑘 + 𝑔𝑘 )∕𝜏 𝑧̃ 𝑘 = ∑ ( ), (25) 𝑗 exp (𝑢𝑗 + 𝑔𝑗 )∕𝜏 𝑔𝑘 ∼ Gumbel(0, 1), A. Nguyen et al.: Preprint submitted to Elsevier
where 𝜏 > 0 is a temperature annealed during training. For the continuous charging power 𝑝, ̂ we use a squashed chg Gaussian head conditioned on a charging context ℎ𝑖 : chg
(𝜇𝑖 , log 𝜎𝑖 ) = MLP(ℎ𝑖 ), 𝑢 ∼ (𝜇𝑖 , 𝜎𝑖2 ),
𝑝̂ =
𝑃𝑠max ( 2
) 1 + tanh 𝑢 . (26)
The log-density includes the standard change-of-variables correction due to the tanh squashing. The actor outputs an intention 𝑎̃𝑡 built from discrete Gumbel–Softmax samples and continuous 𝑝. ̂
6.3. Critics and value network Twin critics 𝑄𝜓1 , 𝑄𝜓2 consume a state embedding (from the GCN) and an action embedding constructed from the projected system action 𝑎𝑡 = Πfeas (𝑠𝑡 , 𝑎̃𝑡 ). A separate value network 𝑉𝜑 shares the GCN encoder and outputs 𝑉𝜑 (𝑠′ (𝜉)) used by the Wasserstein adversary in (21) as well as in the soft value definition below.
6.4. Soft value and training losses Following the SAC formulation of [24], the entropyregularized value is defined as [ ] 𝑉𝜑 (𝑠) = 𝔼𝑎∼𝜋𝜃 (⋅|𝑠) min 𝑄𝜓𝑘 (𝑠, Πfeas (𝑠, 𝑎))−𝛼 log 𝜋𝜃 (𝑎|𝑠) . 𝑘=1,2
(27) With the robust target 𝑦rob 𝑡 from (21), we train the critics by minimizing [ ] 2 𝑄 (𝜓𝑘 ) = 𝔼 (𝑄𝜓𝑘 (𝑠𝑡 , 𝑎𝑡 ) − 𝑦rob 𝑘 = 1, 2, (28) 𝑡 ) , and the actor by the SAC-style [24]: [ ( )] 𝜋 (𝜃) = 𝔼𝑠,𝑎∼𝜋 ̃ 𝑄𝜓𝑘 𝑠, Πfeas (𝑠, 𝑎) ̃ , ̃ 𝜃 𝛼 log 𝜋𝜃 (𝑎|𝑠)−min 𝑘
(29) Page 6 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
Algorithm 2 PD–RSAC with Graph-Aligned 𝑊1 and MILP Projection 1: Initialize actor 𝜃, critics 𝜓1 , 𝜓2 , value network 𝜑, dual
𝜆 ≥ 0, replay buffer .
2: for each environment step 𝑡 do 3: Observe 𝑠𝑡 . 4: Sample intention 𝑎̃𝑡 ∼ 𝜋𝜃 (⋅|𝑠𝑡 ) via (7), (25), (26). 5: Project: 𝑎𝑡 ← Πfeas (𝑠𝑡 , 𝑎̃𝑡 ) via MILP (12)–(16). 6: Execute 𝑎𝑡 in the semi-MDP, observe 𝑟𝑡 , 𝑠𝑡+Δ , 𝜉̂𝑡 .
Store (𝑠𝑡 , 𝑎̃𝑡 , 𝑎𝑡 , 𝑟𝑡 , 𝑠𝑡+Δ , 𝜉̂𝑡 ) in . Sample minibatch of transitions from . for each transition in minibatch do Initialize 𝜉 0 ← 𝜉̂𝑡 . for 𝑘 = 0 to 𝐾 − 1 do 𝑘 𝑔 ← 𝛾 Δ(𝜉 ) ∇𝜉 𝑉𝜑 (𝑠′ (𝜉 𝑘 )). 13: ℎ ← 𝑔𝑑 (𝜉 𝑘 ) as in (17). 14: 𝜉 𝑘+1∕2 ← 𝜉 𝑘 − 𝜂(𝑔 + 𝜆𝑡 ℎ). 15: 𝜉 𝑘+1 ← Proj (𝜉 𝑘+1∕2 ). 16: end for 17: 𝜉⋆ ← 𝜉𝐾 . 18: Compute robust target 𝑦rob 𝑡 via (21). 19: Update critics by minimizing (28). 20: Update actor by minimizing (29). 21: Update 𝜆 via the primal–dual rule (23). 22: end for 23: end for 7: 8: 9: 10: 11: 12:
where gradients through the projection Πfeas are handled by a straight-through estimator (STE): in the forward pass we use 𝑎 = Πfeas (𝑠, 𝑎), ̃ while in the backward pass we approximate 𝜕𝑎∕𝜕 𝑎̃ ≈ 𝐼 along selected components. The composition of Πfeas with the robust backup preserves the contraction property of the Bellman operator (Theorem 1).
7.1. Contraction of the robust-soft Bellman operator For a fixed dual variable 𝜆 ≥ 0, define the operator [ (rob 𝑉 )(𝑠) = 𝔼𝑎∼𝜋(⋅|𝑠) 𝑟(𝑠, 𝑎) ̂ − 𝛼 log 𝜋(𝑎|𝑠) ̂ (30) ( )] ̂ . + sup 𝛾 Δ(𝜉) 𝑉 (𝑠′ (𝜉)) − 𝜆𝑑𝑄 (𝜉, 𝜉) 𝜉∈
with 𝑎̂ = Πfeas (𝑠, 𝑎) and Δ(𝜉) ≥ 1 almost surely. The following property holds. Theorem 1 (Contraction of robust Bellman operator). Under Assumption 1, for any 𝑉1 , 𝑉2 , ‖rob 𝑉1 − rob 𝑉2 ‖ ≤ 𝛾 ‖𝑉1 − 𝑉2 ‖ . ‖∞ ‖ ‖∞ ‖ Thus, rob is a 𝛾-contraction in the 𝐿∞ norm and admits a unique fixed point. Proof. Rewards and entropy terms cancel in the difference (rob 𝑉1 − rob 𝑉2 ). Using sup 𝑓 − sup 𝑔 ≤ sup(𝑓 − 𝑔) and the fact that 𝛾 Δ(𝜉) ≤ 𝛾 for all 𝜉 yields |(rob 𝑉1 )(𝑠) − (rob 𝑉2 )(𝑠)| ≤ 𝛾 ‖𝑉1 − 𝑉2 ‖ | | ‖ ‖∞ for all 𝑠, proving the result. 𝑑
7.2. Lipschitz robustness bound for 𝑊1 𝑄
We recall a standard Lipschitz robustness bound for Wasserstein balls [22], specialized to 𝑑𝑄 . Theorem 2 (KR Lipschitz robustness bound). Let 𝑔 ∶ ℝ𝑞 → ℝ be 𝐿𝑊 -Lipschitz under 𝑑𝑄 , i.e., ||𝑔(𝜉) − 𝑔(𝜉 ′ )|| ≤ 𝐿𝑊 𝑑𝑄 (𝜉, 𝜉 ′ ). For the ambiguity set 𝜌 (𝑃̂ ), inf
𝑃 ∈𝜌 (𝑃̂ )
𝔼𝑃 [𝑔] ≥ 𝔼𝑃̂ [𝑔] − 𝐿𝑊 𝜌.
6.5. Training algorithm: PD–RSAC The full training loop, named Primal–Dual Robust SAC (PD–RSAC), is summarized in Algorithm 2. Note that the primal–dual update (23) is already defined in Sec. 5 and is simply invoked here.
7. Theoretical Results We briefly summarize the theoretical properties underpinning PD–RSAC. Assumption 1 (Boundedness & discount). Rewards satisfy |𝑟𝑡 | ≤ 𝑅max < ∞, and 0 < 𝛾 < 1. | | Assumption 2 (Feasible projection). For every state 𝑠 and intention 𝑎, ̃ the projection operator Πfeas (𝑠, 𝑎) ̃ returns a feasible action. This is guaranteed by combining the time-limited MILP (12)–(16) with a “safe” greedy fallback. Assumption 3 (Lipschitz regularity under 𝑑𝑄 ). On the relevant domain, 𝑉𝜑 (𝑠′ (⋅)) is 𝐿𝑊 -Lipschitz under 𝑑𝑄 (⋅, ⋅).
A. Nguyen et al.: Preprint submitted to Elsevier
In particular, the worst-case expected value over 𝜌 (𝑃̂ ) is lower-bounded by the empirical expectation minus 𝐿𝑊 𝜌. 𝑑
Proof. By Kantorovich–Rubinstein duality for 𝑊1 𝑄 , 𝑑 𝑊1 𝑄 (𝑃 , 𝑃̂ ) =
sup
‖𝑓 ‖Lip(𝑑𝑄 ) ≤1
(𝔼𝑃 [𝑓 ] − 𝔼𝑃̂ [𝑓 ]).
Setting 𝑓 = 𝑔∕𝐿𝑊 shows that for any 𝑃 , 𝑑 𝔼𝑃 [𝑔] − 𝔼𝑃̂ [𝑔] ≥ −𝐿𝑊 𝑊1 𝑄 (𝑃 , 𝑃̂ ) ≥ −𝐿𝑊 𝜌.
Taking the infimum over 𝑃 ∈ 𝜌 (𝑃̂ ) yields the claim. Theorem 2 provides the theoretical motivation for the Wasserstein-robust design adopted in Section 5. In particular, it shows that, whenever the value surrogate is Lipschitz under the graph-aligned metric 𝑑𝑄 , the degradation of the worst-case expected value over the ambiguity set 𝜌 (𝑃̂ ) is controlled linearly by the radius 𝜌. This justifies using 𝜌 as an explicit robustness budget in the practical robust target (21) and in the primal–dual update (23). Page 7 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
8. Experiments
service region is tessellated into a hexagonal grid using the H3 library [29]; at resolution 8 this yields 3824 active hexes, each has the area of 0.73 km2 and the radius of 0.46 km. There are 13,485,528 trips available, each trip is mapped to an origin and destination hex by its pickup and drop-off coordinates. To match the fleet size of 𝑁 = 1000 vehicles, we sample 20% of the daily trip data, leaving 2,045,463 trips for training and 651,643 trips eval for evaluation. For every Δ𝑡 = 5 minutes, we aggregate trips into an OD tensor 𝐷𝑡 (ℎ1 , ℎ2 ) and estimate a discrete travel-time field 𝑇𝑡 (ℎ1 , ℎ2 ) from empirical median durations. The hex adjacency used by the GCN encoder is obtained from H3 neighbor relationships. Charging stations are placed at the || = 150 hexes using a demand-aware, spatially-spaced selection rule: hexes are ranked in descending order of historical pickup intensity and greedily selected subject to a 4-hop exclusion radius that enforces minimum spacing between stations, with any remaining slots filled by descending demand if the spacing constraint prevents port reaching the target count, each with port capacity 𝐶𝑠 = 5. max = 7000 is imposed on the total A global feeder limit 𝑃feed charging power. Unless otherwise stated, the fleet consists of 𝑉 = 1000 homogeneous EVs with maximum capacity 𝐸 max = 50 kWh and initial SoCs drawn uniformly from [0.5, 0.9]𝐸 max . To evaluate the performance of our algorithm, the first 24 days of the dataset are used for training and the remaining 7 days are held out as the testing set, ensuring that the evaluation is conducted on unseen demand patterns. Each episode consists of 144 decision steps spanning 12. The reward function adopts net profit as the primary performance metric, defined as trip revenue minus driving and electricity costs, where driving cost is $0.30 km and electricity cost is $0.18 kWh; dropped-order and waitingtime penalties are weighted by 𝜆drop = 0.1 and 𝜆wait = 0.5, respectively. The actor, twin critics, and value network are trained with the Adam optimizer using learning rates of 5 × 10−5 (actor), 1 × 10−4 (twin critics), and 1 × 10−4 (value network), a discount factor of 𝛾 = 0.995, a replay buffer capacity of 100,000, and a mini-batch size of 128. For the distributionally robust backup, the Wasserstein ambiguity radius is set to 𝜌 = 0.3 with a target risk budget of 𝜌target = 0.2, the graph-aligned precision matrix 𝑄 uses 𝛽 = 0.3 to weight the Laplacian term, the primal–dual update on 𝜆 is driven by an initial step size 𝜂0 = 0.01, while the MILP projection layer is solved using Gurobi under a time limit of 𝜏max = 3.0 seconds per decision epoch. The simulation experiments are conducted via Python 3.11 and Pytorch source machine learning library. All simulation experiments are conducted on NVIDIA GeForce RTX 2080 Ti GPUs. For reproducibility, the full codebase and implementation details are available at https://github.com/anthe8105/PD-RSAC.git.
8.1. Experimental Setup
8.2. Compared Methods
7.3. No-regret risk-budget tracking Theorem 3 (No-regret tracking of the risk budget). Consider the primal–dual update [ ] 𝜆𝑡+1 = 𝜆𝑡 + 𝜂𝑡 𝑔𝑡 + ,
𝑔𝑡 = 𝜌̂𝑡 − 𝜌target ,
𝜂 𝜂𝑡 = √0 , 𝑡
where [ ⋅ ]+ denotes projection onto ℝ+ . Assume that 𝜌̂𝑡 is bounded on the compact support , so that |𝑔𝑡 | ≤ 𝐺 for some constant 𝐺 > 0. Then the average budget violation satisfies 1∑ (𝑔 ) = (𝑇 −1∕2 ), 𝑇 𝑡=1 𝑡 + 𝑇
so that the average positive deviation of 𝜌̂𝑡 above 𝜌target vanishes at rate (𝑇 −1∕2 ). Proof. The proof follows the standard projected subgradient argument for online convex optimization [27], adapted to (23). Let 𝜆∗ be an optimal dual variable. By non-expansiveness of the projection [ ⋅ ]+ , |𝜆𝑡+1 − 𝜆∗ |2 ≤ |𝜆𝑡 + 𝜂𝑡 𝑔𝑡 − 𝜆∗ |2 . Expanding and rearranging gives 2𝜂𝑡 𝑔𝑡 (𝜆∗ − 𝜆𝑡 ) ≤ |𝜆𝑡 − 𝜆∗ |2 − |𝜆𝑡+1 − 𝜆∗ |2 + 𝜂𝑡2 𝑔𝑡2 . Summing over 𝑡 = 1, … , 𝑇 yields 𝑇 |𝜆1 − 𝜆∗ |2 1 ∑ 2 𝜂𝑔 . 𝑔𝑡 (𝜆 − 𝜆𝑡 ) ≤ + 2𝜂𝑇 2 𝑡=1 𝑡 𝑡 𝑡=1
𝑇 ∑
∗
Since |𝑔𝑡 | ≤ 𝐺, we have 𝑇 ∑
|𝜆1 − 𝜆∗ |2 𝐺2 ∑ + 𝜂. 2𝜂𝑇 2 𝑡=1 𝑡 𝑇
𝑔𝑡 (𝜆∗ − 𝜆𝑡 ) ≤
𝑡=1
√ √ ∑ With 𝜂𝑡 = 𝜂0 ∕ 𝑡, both 𝜂𝑇−1 and 𝑇𝑡=1 𝜂𝑡 are ( 𝑇 ), so the √ right-hand side is ( 𝑇 ). Dividing by 𝑇 gives an average violation bound of order (𝑇 −1∕2 ), proving the claim. Intuitively, Theorem 3 guarantees that the primal–dual update on 𝜆 automatically calibrates the strength of the Wasserstein penalty: when the adversary tends to exceed the desired radius 𝜌target , the dual variable grows and pushes the realized radius back, and vice versa. As a result, the effective robustness level remains close to 𝜌target over the course of training.
We evaluate PD–RSAC on a city-scale EV ride-hailing task built from the New York City Taxi and Limousine Commission (TLC) Trip Record Data [28]. Trips are filtered for valid coordinates and timestamps and restricted to central New York City (Manhattan and nearby boroughs). The A. Nguyen et al.: Preprint submitted to Elsevier
We evaluate four methods for EV fleet management under the same simulator, hex discretization, state representation, action space, network architecture, reward function, and training budget to ensure a fair comparison. Page 8 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
Figure 3: Net profit comparison across methods. PD–RSAC achieves the highest net profit among all baselines, substantially outperforming Greedy, SAC, MAPPO, and MADDPG.
• PD–RSAC (Proposed Method). Our proposed method integrates Soft Actor-Critic with Wasserstein distributionally robust optimization and MILP-based feasibleaction projection. This design combines learning-based policy optimization with optimization-based constraint enforcement to improve robustness under distributional uncertainty. • Greedy Heuristic. A rule-based deterministic matching algorithm without learning. At each decision epoch, vehicles are assigned to trips by maximizing immediate profit under a maximum pickup distance constraint. Vehicles with state-of-charge below 20% are prioritized for charging. An iterative greedy matching strategy is applied to maximize the number of served trips while satisfying energy and assignment constraints. • SAC (Soft Actor-Critic) [24]. A standard off-policy actor–critic algorithm without the MILP-based feasibleaction projection or Wasserstein distributionally robust optimization components. • MAPPO (Multi-Agent Proximal Policy Optimization) [30]. An on-policy multi-agent extension of PPO under the centralized training with decentralized execution paradigm. Each vehicle is modeled as an agent that learns a decentralized stochastic policy from local observations, while a centralized critic uses global fleet and grid information during training. The policy is optimized with PPOstyle clipped surrogate objectives to improve training stability in cooperative multi-agent settings. • MADDPG (Multi-Agent Deep Deterministic Policy Gradient) [31]. An off-policy multi-agent extension of DDPG under the centralized training with decentralized execution paradigm. Each vehicle is modeled as an agent that makes charging and dispatch decisions based on local observations. A deterministic actor produces decentralized actions, while a centralized critic takes joint observations and actions to estimate agent-specific value functions and mitigate non-stationarity during training. The policy is trained with replay-buffer-based updates and target networks to support stable learning in continuous control settings. A. Nguyen et al.: Preprint submitted to Elsevier
Figure 4: Relative improvement of PD–RSAC over baselines. The proposed method consistently improves both net profit and revenue across all compared baselines.
Figure 5: Revenue and cost breakdown across methods. PD– RSAC generates the highest total revenue, while its driving and charging costs remain within the same overall range as competing methods, yielding the best net profit.
8.3. Main Evaluation For PD–RSAC, the evaluation takes 10260 seconds for a week of simulation (2016 steps), which averages to approximately 5 seconds per 5-minute decision step. Although the per-step cost is dominated by the rolling MILP projection and the 𝐾-iteration inner loop of the Wasserstein adversary, this runtime remains well below the Δ𝑡 = 300-second decision interval. This leaves ample headroom for realtime deployment and suggests that enforcing hard feasibility and distributional robustness does not compromise practical scalability at city scale. Figure 3 reports the net profit of all methods. PD–RSAC achieves the strongest overall economic performance, reaching $1.22M, substantially outperforming Greedy ($0.58M), SAC ($0.63M), MAPPO ($0.67M), and MADDPG ($0.70M). The gap is large across all baselines, indicating that the proposed method consistently yields a more effective operational policy than both heuristic and learning-based alternatives. To understand the source of this gain, Figure 5 shows the revenue and cost decomposition. PD–RSAC attains the highest total revenue, $2.32M, again exceeding all baselines by a wide margin. Although its driving cost and charging cost are not the lowest, the additional cost remains modest Page 9 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
Figure 6: Grid safety analysis under different controllers. (a) Compared with SAC, PD–RSAC eliminates feeder-limit violations by clipping charging peaks below the 7 MW constraint. (b) Compared with MAPPO, PD–RSAC remains safe while utilizing substantially more of the available feeder capacity, demonstrating a better safety–efficiency trade-off.
relative to the increase in revenue. This is an important observation: PD–RSAC does not win merely by suppressing cost, but by generating substantially more revenue through better dispatching and charging decisions. In other words, the proposed method converts available fleet and charging resources into profitable service more effectively than the baselines. Figure 4 further summarizes the relative improvement of PD–RSAC over each baseline. In terms of net profit, PD– RSAC improves over Greedy, SAC, MAPPO, and MADDPG by 111.1%, 94.0%, 82.8%, and 74.9%, respectively. The corresponding revenue improvements are 52.0%, 39.5%, 87.6%, and 37.6%. These gains are not isolated to one particular comparison, but remain consistent across heuristic, single-agent RL, and multi-agent RL baselines. Taken together, Figures 3–4 show that PD–RSAC delivers the best overall economic outcome and that its advantage is driven primarily by stronger revenue generation rather than by aggressive cost reduction alone. Beyond aggregate profit, we also examine whether this improved performance is obtained in a safe and operationally meaningful manner. Figure 6 compares grid power load profiles under different controllers. In Figure 6(a), SAC produces substantial feeder-limit violations, with a peak charging demand of approximately 14,465 kW under a 7,000 kW feeder limit. By contrast, PD– RSAC keeps the charging load below the limit throughout the day, with a peak of 6,999 kW. This demonstrates that the proposed method can enforce the grid safety constraint effectively even under high-demand operating conditions. Figure 6(b) provides a complementary comparison against MAPPO. Although MAPPO also remains within the feeder limit, its peak charging demand is only about 3,000 kW, corresponding to 42.9% of the available capacity. PD–RSAC, in contrast, safely utilizes nearly the full feeder capacity while still avoiding violations. Hence, PD–RSAC is not only safe, A. Nguyen et al.: Preprint submitted to Elsevier
Figure 7: Training reward progression of PD–RSAC. Although the per-episode reward is noisy, the 100-episode moving average exhibits a clear upward trend, indicating stable policy improvement over time.
but also less conservative and more efficient in exploiting available grid resources. This safety–efficiency trade-off is a central advantage of the proposed method: it avoids the unsafe behavior observed in SAC while also avoiding the excessive under-utilization exhibited by MAPPO. For completeness, we also inspect the training dynamics of PD–RSAC. Figure 7 shows that, although the per-episode reward is noisy, the 100-episode moving average exhibits a clear upward trend over training, indicating stable policy improvement. In addition, Figure 8 plots the evolution of the dual variable 𝜆𝑡 and the realized radius 𝜌̂𝑡 . The dual variable decreases smoothly, while the realized radius increases in the early phase and then gradually stabilizes. This behavior suggests that the WDRO mechanism remains active and well-behaved during training, adaptively calibrating the uncertainty set rather than collapsing to a trivial solution or oscillating uncontrollably.
Page 10 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
Figure 8: Evolution of the WDRO-specific variables during training. The dual variable 𝜆𝑡 decreases smoothly, while the realized radius 𝜌̂𝑡 increases in the early phase and then stabilizes, indicating a stable and meaningful robust training process.
Overall, the main evaluation results support a consistent conclusion: PD–RSAC achieves the highest economic performance among all evaluated methods, learns stably during training, and enforces feeder-level safety constraints without becoming overly conservative. The method therefore offers a strong combination of profitability, robustness, and operational safety.
8.4. Ablation Study To isolate the contributions of individual components, we conduct an ablation study by progressively removing the MILP projection layer, the Wasserstein robustness module, and the graph-aligned ground metric. Specifically, we consider the following variants: • w/o Graph: replaces the graph-aligned 𝑄-metric with the identity matrix, resulting in an unstructured Wasserstein ground cost. • w/o WDRO: disables the Wasserstein robustness module and trains the agent using standard SAC without distributional robustness. • w/o MILP: removes the MILP-based feasibility projection while retaining the robustness module and the graph-aligned 𝑄-metric. • Full: the complete PD-RSAC framework with MILP projection, Wasserstein DRO, and graph-aligned 𝑄metric. For fair comparison, all variants are trained under identical hyperparameter settings and share the same ambiguity set radius. Figure 9 summarizes the ablation results in terms of net profit and total revenue. The full model achieves the best performance on both metrics, confirming that the final gains of PD–RSAC do not come from a single module alone. Rather, feasibility refinement, distributional robustness, and graph-aware geometry each contribute to the final result. Among all ablations, removing the MILP layer causes the largest degradation. Without MILP projection, net profit drops from $1.22M to $0.66M, and total revenue decreases A. Nguyen et al.: Preprint submitted to Elsevier
from $2.32M to $1.61M. This sharp decline indicates that the MILP module is a core component of the system. Its role is not merely post-processing or safety filtering; instead, it materially improves the realizability and quality of fleet decisions under charging and infrastructure constraints. These results suggest that feasibility-aware refinement is essential for translating policy outputs into high-quality operational actions. Removing the graph component also reduces performance. The w/o Graph variant reaches $1.14M net profit and $2.24M revenue, both below the full model. This shows that incorporating relational and spatial structure into the robustness mechanism is beneficial. Using an unstructured identity cost weakens the quality of the transportation-aware uncertainty model, whereas the graph-aligned metric provides more meaningful perturbation geometry for the decision problem. Similarly, disabling WDRO leads to a measurable performance drop. The w/o DRO variant attains $1.18M net profit and $2.22M revenue, again below the full model. Although this degradation is smaller than that caused by removing MILP, it is still consistent and non-trivial. This indicates that Wasserstein distributional robustness provides additional gains beyond nominal learning, improving the economic quality of the learned policy under uncertainty. Taken together, the ablation results confirm that all three components contribute positively, with the MILP module having the largest impact and the graph-aware representation and WDRO regularization providing complementary improvements. Therefore, the strong performance of PD– RSAC is best understood as the result of a tightly integrated design rather than a single dominant heuristic or architectural choice. Beyond effectiveness, it is also important to understand the computational overhead introduced by each component. To this end, Table 1 reports the training time of all ablation
Page 11 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
Figure 9: Ablation results for PD–RSAC. The full model achieves the best performance in both net profit and total revenue. Removing MILP causes the largest degradation, while removing WDRO or the graph-aligned metric also leads to consistent performance drops.
Table 1 Training time comparison (seconds) across model variants. Variant w/o Graph w/o WDRO w/o MILP Full
Training time (s) 516154.4 496485.0 87898.1 600499.2
variants, complementing the performance comparison in Fig. 9. Table 1 and Fig. 8 together show a clear efficiency– performance trade-off. Among all variants, w/o MILP is the fastest to train, requiring only 87898.1 s versus 600499.2 s for the full model, i.e., about 6.83× less training time. This indicates that the MILP projection layer is the primary source of computation cost of the framework. However, the same variant also suffers the largest drop in net profit and total revenue, showing that the extra computational cost of MILP is closely tied to its strong contribution to feasibility refinement and overall decision quality.
9. Conclusion We studied city-scale EV ride-hailing control as a constrained sequential decision-making problem in which dispatching, repositioning, and charging decisions must remain feasible under battery, station, and grid limitations. To address this challenge, we proposed PD–RSAC, a unified framework that combines semi-Markov reinforcement learning, rolling MILP-based action projection, and Wasserstein distributional robustness on a graph-structured transportation domain. In contrast to nominal learning pipelines, the proposed method integrates policy learning, feasibility refinement, and robustness within a single control loop.
A. Nguyen et al.: Preprint submitted to Elsevier
Our results show that this integration is practically important. PD–RSAC achieves the highest net profit ($1.22M) among all evaluated baselines while maintaining safe operation under feeder-capacity constraints. The ablation study further clarifies the role of each component: the MILP layer provides the largest contribution to profit by turning raw policy outputs into executable infrastructure-aware decisions, while the Wasserstein robustness module and graphaligned metric provide complementary gains under uncertainty. Taken together, these findings suggest that effective EV fleet control requires not only strong learning capability, but also explicit treatment of physical feasibility and uncertainty within the decision loop itself. More broadly, the paper highlights a useful design principle for large-scale cyber-physical decision systems: when actions are tightly constrained by infrastructure, learning alone is often insufficient, and performance improves substantially when optimization-based feasibility correction and robustness mechanisms are embedded directly into the control architecture. In this sense, PD–RSAC provides a concrete example of how reinforcement learning and mathematical programming can be combined to achieve both safety and profitability at scale. An important direction for future work is to replace the current rolling MILP projection with a lighter feasibility module that achieves comparable decision quality at a much lower computational cost. Developing such a mechanism would make the framework more scalable without sacrificing the main economic benefits brought by feasibility-aware refinement.
Page 12 of 13
Semi-Markov RL for City-Scale EV Ride-Hailing
References [1] K. Wei, V. Vaze, A. Jacquillat, Transit planning optimization under ride-hailing competition and traffic congestion, Transportation Science https://doi.org/10.1287/trsc.2021.106856 (2021) 725–749. [2] Y. Cao, S. Wang, J. Li, The optimization model of ride-sharing route for ride hailing considering both system optimization and user fairness, Sustainability https://doi.org/10.3390/su1302090213 (2021) 2728. [3] F. Miao, S. Han, S. Lin, J. A. Stankovic, D. Zhang, S. Munir, H. Huang, T. He, G. J. Pappas, Taxi dispatch with real-time sensing data in metropolitan areas: A receding horizon control approach, IEEE Transactions on Automation Science and Engineering https://doi.org/10.1145/2735960.273596113 (2015) 463–478. [4] Y. Liu, F. Wu, C. Lyu, S. Li, J. Ye, X. Qu, Deep dispatching: A deep reinforcement learning approach for vehicle dispatching on online ride-hailing platform, Transportation Research Part E: Logistics and Transportation Review https://doi.org/10.1016/j.tre.2022.102694161 (2022) 102694. [5] Z. Qin, X. Tang, Y. Jiao, F. Zhang, Z. Xu, H. Zhu, J. Ye, Ride-hailing order dispatching at didi via reinforcement learning, INFORMS Journal on Applied Analytics https://doi.org/10.1287/inte.2020.104750 (2020) 272–286. [6] X. Yue, Y. Liu, F. Shi, S. Luo, C. Zhong, M. Lu, Z. Xu, An endto-end reinforcement learning based approach for micro-view orderdispatching in ride-hailing, Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, 2024, pp. 321–330. https://doi.org/10.1145/3627673.3680013. [7] J. Wang, Q. Hao, W. Huang, X. Fan, Q. Zhang, Z. Tang, B. Wang, J. Hao, Y. Li, Coopride: Cooperate all grids in city-scale ride-hailing dispatching with multi-agent reinforcement learning, Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025, pp. 1–10. https://doi.org/10.1145/3690624.3709205. [8] Y. Jiao, X. Tang, Z. Qin, S. Li, F. Zhang, H. Zhu, J. Ye, Realworld ride-hailing vehicle repositioning using deep reinforcement learning, Transportation Research Part C: Emerging Technologies https://doi.org/10.1016/j.trc.2021.103289130 (2021) 103289. [9] J. Li, V. Allan, Where to go: Agent guidance with deep reinforcement learning in a city-scale online ride-hailing service, Proceedings of the IEEE International Conference on Intelligent Transportation Systems (ITSC), 2022, pp. 182–189. https://doi.org/10.1109/ITSC55140.2022.9921747. [10] J. Huang, L. Huang, M. Liu, H. Li, Q. Tan, X. Ma, J. Cui, D.-S. Huang, Deep reinforcement learning-based trajectory pricing on ride-hailing platforms, ACM Transactions on Intelligent Systems and Technology https://doi.org/10.1145/347484113 (2022) 1–19. [11] K. Jin, Z. Feng, X. Li, F. Zhang, Ride-hailing service pattern recognition and demand prediction, IEEE Transactions on Intelligent Transportation Systems https://doi.org/10.1109/TITS.2025.355827426 (2025) 1–10. [12] J. Tian, H. Jia, G. Wang, Q. Huang, R. Wu, H. Gao, C. Liu, Optimal scheduling of shared autonomous electric vehicles with multi-agent reinforcement learning: A mappo-based approach, Neurocomputing https://doi.org/10.1016/j.neucom.2025.129343622 (2025) 129343. [13] J. Hu, Z. Xu, W. Wang, G. Qu, Y. Pang, Y. Liu, Decentralized graphbased multi-agent reinforcement learning using reward machines, Neurocomputing https://doi.org/10.1016/j.neucom.2023.126974564 (2024) 126974. [14] J. Achiam, D. Held, A. Tamar, P. Abbeel, Constrained policy optimization, Proceedings of the 34th International Conference on Machine Learning (ICML), 2017, pp. 22–31. https://doi.org/10.48550/arXiv.1705.10528. [15] B. Amos, J. Z. Kolter, Optnet: Differentiable optimization as a layer in neural networks, Proceedings of the 34th International Conference on Machine Learning (ICML), 2017, pp. 152–161. https://doi.org/10.48550/arXiv.1703.00443.
A. Nguyen et al.: Preprint submitted to Elsevier
[16] A. Agrawal, S. Barratt, S. Boyd, E. Busseti, Differentiable convex optimization layers, Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019, pp. 1–10. https://doi.org/10.48550/arXiv.1910.12430. [17] S. Liu, X. Yang, Z. Zhang, F. L. Lewis, Safe reinforcement learning for affine nonlinear systems with state constraints and input saturation using control barrier functions, Neurocomputing https://doi.org/10.1016/j.neucom.2022.11.006518 (2023) 562–576. [18] G. N. Iyengar, Robust dynamic programming, Mathematics of Operations Research https://doi.org/10.1287/moor.1040.012930 (2005) 257–280. [19] A. Nilim, L. El Ghaoui, Robust control of markov decision processes with uncertain transition matrices, Operations Research https://doi.org/10.1287/opre.1050.021653 (2005) 780–798. [20] J. Grand-Clément, C. Kroer, First-order methods for wasserstein distributionally robust mdps, Proceedings of the International Conference on Learning Learning (ICML), volume 139, 2021, pp. 1–10. https://doi.org/10.48550/arXiv.2009.06790. [21] A. B. Kordabad, R. Wisniewski, S. Gros, Safe reinforcement learning using wasserstein distributionally robust mpc and chance constraint, IEEE Access https://doi.org/10.1109/ACCESS.2022.322892210 (2022) 1–10. [22] P. Mohajerin Esfahani, D. Kuhn, Data-driven distributionally robust optimization using the wasserstein metric, Mathematical Programming https://doi.org/10.1007/s10107-017-1172-1171 (2018) 115–166. [23] A. Sinha, H. Namkoong, J. Duchi, Certifying some distributional robustness with principled adversarial training, Proceedings of the International Conference on Learning Representations (ICLR), 2018, pp. 1–10. https://doi.org/10.48550/arXiv.1710.10571. [24] T. Haarnoja, A. Zhou, P. Abbeel, S. Levine, Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor, Proceedings of the 35th International Conference on Machine Learning (ICML), 2018, pp. 1861–1870. https://doi.org/10.48550/arXiv.1801.01290. [25] T. N. Kipf, M. Welling, Semi-supervised classification with graph convolutional networks, Proceedings of the International Conference on Learning Representations (ICLR), 2017, pp. 1–10. https://doi.org/10.48550/arXiv.1609.02907. [26] E. Jang, S. Gu, B. Poole, Categorical reparameterization with gumbel-softmax, Proceedings of the International Conference on Learning Representations (ICLR), 2017, pp. 1–10. https://doi.org/10.48550/arXiv.1611.01144. [27] S. Shalev-Shwartz, Online learning and online convex optimization, Foundations and Trends in Machine Learning https://doi.org/10.1561/22000000184 (2012) 107–194. [28] NYC Taxi and Limousine Commission, Tlc trip record data, https: //www.nyc.gov/site/tlc/about/tlc-trip-record-data.page, 2025. Accessed: 2025-09-01. [29] Uber Technologies, Inc., H3: A hexagonal hierarchical geospatial indexing system, https://h3geo.org, 2025. Accessed: 2025-09-01. [30] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, Y. Wu, The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games, Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 35, 2022, pp. 24611–24624. https://doi.org/10.48550/arXiv.2103.01955. [31] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, I. Mordatch, Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments, Proc. Advances in Neural Information Processing Systems (NIPS), 2017, pp. 1–10. https://doi.org/10.48550/arXiv.1706.02275.
Page 13 of 13