# Online Learning for Traffic Routing under Unknown Preferences

arXiv: https://arxiv.org/abs/2203.17150 · HTML: https://mlsanity.com/paper/2203.17150/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 59 references that are in the map.
- First posted on arXiv 31 Mar 2022.

## Builds on (most cited first, 18 of 18)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Watch and Learn: Optimizing from Revealed Preferences Feedback](https://mlsanity.com/paper/1504.01033/) (2015)
- [Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment](https://mlsanity.com/paper/2104.00098/) (2021)
- [Opportunities for Price Manipulation by Aggregators in Electricity Markets](https://mlsanity.com/paper/1606.06510/) (2016)
- [Traffic Optimization For a Mixture of Self-interested and Compliant Agents](https://mlsanity.com/paper/1709.09569/) (2017)
- [Social welfare and profit maximization from revealed preferences](https://mlsanity.com/paper/1711.02211/) (2017)
- [Distributed Mechanism Design for Multicast Transmission](https://mlsanity.com/paper/1803.08111/) (2018)
- [Fisher Markets with Linear Constraints: Equilibrium Properties and Efficient Distributed Algorithms](https://mlsanity.com/paper/2106.10412/) (2021)
- [Markets for Efficient Public Good Allocation with Social Distancing](https://mlsanity.com/paper/2005.10765/) (2020)
- [Joint Estimation of OD Demands and Cost Functions in Transportation Networks from Data](https://mlsanity.com/paper/1909.00941/) (2019)
- [When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes](https://mlsanity.com/paper/2106.10407/) (2021)

## Built on by (most cited first, 4 of 4)

- [Expert with Clustering: Hierarchical Online Preference Learning Framework](https://mlsanity.com/paper/2401.15062/) (2024)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Online Learning for Equilibrium Pricing in Markets under Incomplete Information](https://mlsanity.com/paper/2303.11522/) (2023)
- [Personalized Collaborative Learning with Affinity-Based Variance Reduction](https://mlsanity.com/paper/2510.16232/) (2025)

## Abstract (arXiv)

In transportation networks, users typically choose routes in a decentralized and self-interested manner to minimize their individual travel costs, which, in practice, often results in inefficient overall outcomes for society. As a result, there has been a growing interest in designing road tolling schemes to cope with these efficiency losses and steer users toward a system-efficient traffic pattern. However, the efficacy of road tolling schemes often relies on having access to complete information on users' trip attributes, such as their origin-destination (O-D) travel information and their values of time, which may not be available in practice. Motivated by this practical consideration, we propose an online learning approach to set tolls in a traffic network to drive heterogeneous users with different values of time toward a system-efficient traffic pattern. In particular, we develop a simple yet effective algorithm that adjusts tolls at each time period solely based on the observed aggregate flows on the roads of the network without relying on any additional trip attributes of users, thereby preserving user privacy. In the setting where the O-D pairs and values of time of users are drawn i.i.d. at each period, we show that our approach obtains an expected regret and road capacity violation of O(√T), where T is the number of periods over which tolls are updated. Our regret guarantee is relative to an offline oracle that has complete information on users' trip attributes. We further establish a Omega(√T) lower bound on the regret of any algorithm, which establishes that our algorithm is optimal up to constants. Finally, we demonstrate the superior performance of our approach relative to several benchmarks on a real-world transportation network, thereby highlighting its practical applicability.