Online Learning for Traffic Routing under Unknown Preferences
  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(\sqrt{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(\sqrt{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.
