Robust Learning for Congestion-Aware Routing
Sreenivas Gollapudi, Kostas Kollias, Benjamin Plaut, Ameya Velingker · 2021
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 cet=fe(xet)+ηet, where xet is the flow on edge e at time t, fe is the congestion function, and ηet is a noise sample drawn from an unknown distribution. The algorithm observes cet, and can use this observation in future routing decisions. The routing requests are supplied adversarially. We present an algorithm with cumulative regret O~(|E|t2/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|t1/3) and time complexity O(|E|logt). We also validate our algorithm empirically using graphs from New York City road networks.