Traffic platforms and road operators hold large logs of how real drivers route. Those drivers differ in how much they will pay to save time, known as their value of time (VOT). They also route selfishly, so the logs record an inefficient equilibrium in which no driver can do better alone but the network as a whole is congested. If you train a policy to copy these logs, which is imitation learning, it reproduces that inefficiency by construction. If you instead learn tolls or routing through online trial and error, you need thousands of rounds of live experimentation on a real road network.
This note proposes a third route. Use the logs to learn why each class of driver chose what it did, meaning a small set of driver types each with its own VOT. Then design tolls that move the whole population toward the system optimum. The intervention is computed by a change of variables that makes the design problem convex, so it does not stall at a mediocre local optimum.
The central observation is that congestion breaks the usual escape from the imitation ceiling. In offline reinforcement learning, "trajectory stitching" splices the best pieces of different demonstrations together, and it assumes the environment's response is fixed. On a road network a route is fast only because few people take it, so a stitched policy that sends everyone down the best logged route destroys the very thing that made it good. The demonstrations therefore have to be read as samples from an equilibrium-generating process, not as trajectories to splice. Once the process is modeled, three things follow. Heterogeneity can be identified. The design problem can be posed over traffic flows, where it is convex, instead of over toll prices, where it is not. Sample cost becomes the number of distinct toll regimes the operator must ever deploy, not the number of learning episodes.
Core Claim
Nonatomic multi-class congestion games, where each driver is too small to matter alone, have the following structure. Let $x_e^k$ be the flow of driver class $k$ on edge $e$, $x_e=\sum_k x_e^k$ the total flow, $l_e$ an increasing edge latency, $\tau_e$ the toll, and $v_k$ the VOT of class $k$. If drivers minimize time plus toll divided by their VOT, then the equilibrium flows minimize the potential
$$ \Phi(x;\tau,v)=\sum_e \int_0^{x_e} l_e(s)\,ds+\sum_k\sum_e \frac{\tau_e\, x_e^k}{v_k} $$
over feasible multi-class flows. This objective is convex, so for fixed tolls and types the follower equilibrium can be computed with global guarantees. In the preference parameterization $\eta_i$ used by Toll-Based Learning for Minimising Congestion under Heterogeneous Preferences, the same structure holds after rescaling.
Two inverse problems inherit useful structure. The first is learning types from logs. The equilibrium conditions say that every used path's generalized cost equals the cheapest cost for that class and origin-destination pair. These conditions are linear in the unknowns $1/v_k$ and the per-class cheapest costs, given observed travel times and tolls. Recovering types is therefore a convex inverse-optimization problem when class membership is known, and a mixture problem solved by alternating assignment and convex refits when it is not.
The second is designing tolls. Directly optimizing social cost as a function of $\tau$, by differentiating through the equilibrium, is non-convex and in our view will stall at stationary points. We instead fix the target to the system-optimal aggregate flow, which solves the convex problem of minimizing $\sum_e x_e l_e(x_e)$ under standard BPR latencies. We then solve a linear feasibility problem for tolls and a class split that make that flow an equilibrium for the learned types. If the learned type model is right and the feasibility problem is solvable, the result is the global optimum of the modeled design problem. No Polyak-Łojasiewicz-type condition needs to be verified along the way.
The claim to test is that this pipeline beats imitation by roughly the network's Price of Anarchy, the ratio of selfish-equilibrium cost to optimal cost. It should match online toll learning while deploying orders of magnitude fewer toll regimes, and it should reach better designs than toll-space gradient methods given the same learned model.
Relation to Prior Work
The heterogeneity motivation comes from congestion economics. Competition and Efficiency in Congested Markets argues that efficiency bounds derived under identical delay sensitivities do not transfer to diverse populations. Cost-Balancing Tolls for Atomic Network Congestion Games and Demand-Independent Tolls show that toll designs tuned to uniform users become fragile when sensitivities differ. Strategic Interactions in Multi-modal Mobility Systems shows VOT-driven sorting across modes. These papers motivate modeling types explicitly. None of them learns the types from data, which is the step we add.
The closest existing method is GTQ-learning in Toll-Based Learning for Minimising Congestion under Heterogeneous Preferences. It shows that marginal-cost tolling fails under heterogeneous $\eta_i$. It then uses decentralized online Q-learning, with tolls that make drivers behave as if neutral, budget redistribution, and misreporting penalties, to reach near system-optimal travel times on Sioux Falls, Anaheim and Eastern-Massachusetts. It relies on reported preferences and many online episodes. We differ in three ways: we infer types from revealed route choices under logged tolls, we use no online learning loop, and we compute tolls in closed form via the convex flow-space problem.
Distributed Learning for Dynamic Congestion Games supplies the evidence that selfish logs are badly suboptimal: myopic routing yields a Price of Anarchy of at least 2.0. That paper explicitly leaves user heterogeneity open. Its fix is information design rather than pricing, so it complements this work rather than competing with it.
On the imitation ceiling, Large Decision Models and Curriculum Offline Imitating Learning argue that likelihood-based cloning cannot exceed the data. Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes shows value-based stitching can. Our position constrains that remedy rather than reusing it: stitching presumes dynamics that do not depend on the policy, which fails when the "dynamics" are other drivers.
On the inverse side, two papers supply ideas and also mark the gap. Balancing Sample Efficiency and Suboptimality in Inverse Reinforcement Learning shapes recovered rewards for finite-sample forward learning. Proximal Point Imitation Learning convexifies imitation through the linear-programming view of decision processes and obtains an $\mathcal{O}(1/K)$ rate. Both are single-agent and aim to match the expert. We borrow the convexify-then-optimize stance but apply it to a population equilibrium, and we aim to exceed the expert.
On convergence, Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition shows how a gradient-dominance condition makes stationary points global. A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding shows block-wise schemes still stall at joint stationary points. Rather than proving a condition like PL for the toll landscape, which is hard to verify, we remove the non-convexity by changing variables. We then measure empirically how often toll-space descent stalls.
Research Program
The work has four parts. First, a demonstration generator on standard networks, described under Proposed Experiments. Second, a type-identification module that fits $K$ latent classes with VOT $v_k$ and population masses. It uses inverse optimization on equilibrium residuals and mixture assignment over drivers or origin-destination cohorts, and it is regularized for noisy, logit-like route choice. Third, a flow-space design module: compute the system-optimal flow, then solve the linear program for tolls and class splits supporting it, with a minimum-revenue or budget-balance objective. Fourth, an analysis of identification and sample cost.
The aggregate edge flows at equilibrium are unique when latencies are strictly increasing, but the split of flow across classes generally is not. Identification must therefore come from individual route observations, from variation in tolls across regimes, or both. Each toll regime contributes linear constraints on the vector of inverse VOTs, so we expect the number of regimes needed to scale with $K$ rather than with network size. We will state this precisely and test it as a hypothesis by varying the number of logged regimes.
We will also characterize what happens under model error. If the learned types are wrong, the deployed tolls induce a different equilibrium than intended. We measure the resulting gap to the true optimum as a function of VOT estimation error. We also test a cheap fix: one or two corrective rounds in which the deployed regime's outcome is added to the logs and the model is refit.
Baselines
The naive reference is the logged selfish equilibrium itself, with no tolls. Alongside it we run type-conditioned behavior cloning: a route-choice network conditioned on oracle or estimated type, trained on the same logs. Its cost relative to the system optimum shows the imitation ceiling directly. Beating it means closing most of the Price of Anarchy gap.
Marginal-cost tolling computed under a single pooled VOT is the textbook homogeneous design. It is shown to fail under heterogeneity by Toll-Based Learning for Minimising Congestion under Heterogeneous Preferences, and it uses the same logs to fit the one VOT.
The strongest competitor is GTQ-learning from the same paper. We run it with its published settings on the same networks and the same $\eta_i\sim U[0,1]$ preferences, and we count every online episode as a deployed toll regime. That paper reports average travel times "very close to the system optimum (e.g., 1.002 x 10^-4 for the average across networks with uniform preferences and no redistribution)". The file does not make clear whether this is a relative gap or another quantity. It also reports no numeric figure for the heterogeneous case beyond stating that performance "did not significantly degrade". We will therefore re-measure GTQ in our harness. Beating it means equal or lower total travel time relative to the system optimum while deploying at least an order of magnitude fewer toll regimes, without relying on self-reported preferences.
An offline value-based stitching baseline follows Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes. It is a conservative Q-learner for per-driver routing trained on the same logs and evaluated when all drivers adopt it.
Two ablations isolate the key ingredients, and both share the learned model so the comparison is fair. The first replaces flow-space design with toll-space gradient descent through the convex equilibrium solver, using multiple random initializations and the same compute. The second forces $K=1$, which tests whether learning heterogeneity is what matters.
All methods get the same logs, an equal hyperparameter search budget, and a cap of 50 tuning trials each.
Why not just…?
Why not just condition behavior cloning on driver type? Conditioning fixes the averaging problem, where one policy serves no class well. It does not fix the ceiling: each class's cloned policy reproduces its selfish choice, so the aggregate outcome is the logged equilibrium again. The argument in Curriculum Offline Imitating Learning predicts this, and the type-conditioned baseline above measures it directly. We expect it to sit at the untolled cost.
Why not just run offline reinforcement learning, which is known to stitch beyond the data? Stitching is valid when other agents' behavior is fixed. Here the evaluation that matters is when every driver adopts the learned policy, and that changes congestion on every link. We expect the offline Q-policy to look good when scored against logged traffic and to collapse toward or below the selfish equilibrium when everyone deploys it. Reporting both evaluations makes this visible. If it does not collapse, that is a genuine threat to our framing, and we will report it as such.
Why not just run GTQ-learning or another online multi-agent learner? If live experimentation is free, as in simulation, GTQ is a strong answer, and we do not claim to beat it on final travel time. The question is cost. Each episode is a toll regime imposed on real drivers. GTQ also depends on drivers reporting preferences, with penalties for lying. Our method uses revealed choices instead. The decisive comparison is the curve of efficiency against the number of deployed toll regimes.
Why not just differentiate social cost through the equilibrium and descend on tolls? This is the natural bilevel approach and it may often work. The ablation tests it under matched compute, measuring the spread of final costs across initializations against the flow-space solution. If toll-space descent reliably finds the same optimum, the convexification is a convenience rather than a contribution, and we will say so.
Proposed Experiments
The testbeds are the networks used by Toll-Based Learning for Minimising Congestion under Heterogeneous Preferences: Sioux Falls, Anaheim, Eastern-Massachusetts, and its synthetic B and BB networks. On each, we generate demonstrations by solving multi-class equilibria with heterogeneous VOT under a small number of historical toll regimes, from one to twenty, and sampling individual routes with logit noise.
The primary metric is total system travel time divided by the system-optimal value. The secondary metrics are the number of deployed toll regimes, VOT recovery error, toll revenue, and per-class travel cost, the last to check whether low-VOT drivers bear the gains.
Robustness runs cover four stresses: continuous $\eta$ fitted with discrete $K$; logs from only one or two regimes; misspecified latency functions; and partial observation, where only aggregate link counts are available.
Three checks decide the claim. First, with oracle types, the flow-space design must reach the system optimum on every network, and toll-space descent must show a measurable spread of stationary outcomes. Second, with learned types, efficiency must degrade gracefully as the number of logged regimes falls, and the point where it breaks down must track $K$. Third, against GTQ, we must match its efficiency with far fewer deployed regimes. Failing the first check would mean the convexification adds nothing. Failing the second would mean revealed-preference identification is too weak to replace reported preferences.
References
- Toll-Based Learning for Minimising Congestion under Heterogeneous Preferences
- Competition and Efficiency in Congested Markets
- Cost-Balancing Tolls for Atomic Network Congestion Games
- Demand-Independent Optimal Tolls
- Strategic Interactions in Multi-Modal Mobility Systems: A Game-Theoretic Perspective
- Distributed Learning for Dynamic Congestion Games
- Large Decision Models
- Curriculum Offline Imitating Learning
- Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes
- Balancing Sample Efficiency and Suboptimality in Inverse Reinforcement Learning
- Proximal Point Imitation Learning
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
- A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding