Contextual Online Routing in Congested Networks with Background Flow

We study contextual online routing in congested networks. In each round, a platform observes context and trip requests and routes divisible flow before observing the background flow of outside users. Edge costs are affine in total load, and noisy cost feedback comes only from used edges, with precision increasing with routed flow. Routing thus determines both congestion and where and how precisely costs are learned. Standard ellipsoidal optimism makes routing nonconvex. We propose RectCOR (Rectangularized Contextual Optimistic Routing), which retains a convex quadratic routing problem by using the lower corner of the bounding rectangle of each projected confidence ellipse. Its statistical price is governed by the intercept–slope correlation of this ellipse and can cause linear regret when observed loads concentrate. Residual variation in background flow prevents this degeneracy uniformly over time and for any routing rule, yielding a high-probability $\tilde{O}(\sqrt{T})$ regret bound without forced exploration. Background-flow variation is thus not only a source of uncertainty but also of excitation. In experiments, greater background-flow variation closes the regret gap between RectCOR and ellipsoidal optimism, after which RectCOR outperforms it at roughly one-tenth the computation; it also attains sublinear regret on the Sioux Falls network.