Robust Learning for Congestion-Aware Routing

Abstract

We consider the problem of routing users through a network with unknown congestion functions over an infinite time horizon. On each time step t, the algorithm receives a routing request and must select a valid path. For each edge e in the selected path, the algorithm incurs a cost c_e^t = f_e(x_e^t) + _e^t, where x_e^t is the flow on edge e at time t, f_e is the congestion function, and _e^t is a noise sample drawn from an unknown distribution. The algorithm observes c_e^t, and can use this observation in future routing decisions. The routing requests are supplied adversarially. We present an algorithm with cumulative regret O(|E| t^2/3), where the regret on each time step is defined as the difference between the total cost incurred by our chosen path and the minimum cost among all valid paths. Our algorithm has space complexity O(|E| t^1/3) and time complexity O(|E| t). We also validate our algorithm empirically using graphs from New York City road networks.

Tasks

Reproductions