acceptodds
Under review as a conference paper at ICLR 2027

Contextual Online Routing in Congested Networks with Background Flow

Abstract

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 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.

Primary area:
learning theory
Keywords:
online routing, contextual semi-bandits, congested networks, online learning, regret analysis

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_hPk2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper investigates the problem of contextual online routing in congested networks, where a centralized routing platform (such as a GPS navigation app) must route divisible flows of its users before observing the background traffic flow of outside users. The authors propose RECTCOR (Rectangularized Contextual Optimistic Routing), which projects each 2D confidence ellipsoid of intercept and slope onto the current context, and then extracts the lower corner of its bounding rectangle.

The authors evaluate RECTCOR on a small synthetic network (5 nodes, 7 edges) and the standard Sioux Falls transportation network (24 nodes, 76 edges, 10 OD pairs). On the synthetic network, RECTCOR’s cumulative regret decreases as background flow variance increases, matching or outperforming non-convex ellipsoidal optimism (Naive UCB) while running 8 to 16 times faster (0.30 ms vs. 2.97 ms per round).

Critical strengths
  1. Using the background flow as source of excitation of learning costs. This excitation arises after the decision and guarantees covariate diversity in observed loads, which stabilizes parameter estimation.

  2. Sound theoretical analysis - The paper provides a clean theoretical framework, including a high-probability O~(T)\tilde{O}(\sqrt{T}) regret bound (Theorem 1) and a constructive counterexample (Proposition 4) showing that without load/background-flow variation, regularized optimistic routing can degrade to linear regret.

Critical weaknesses

My main concern with the proposed formulation is how the authors treat the 'background flows'. Specifically, I have reservations about two assumptions in their model:

  1. The platform routes divisible flow before background flow is revealed on every edge. The background costs don't always change drastically to make this condition necessary. The routing app always has a reasonable estimate of the edge cost from the times it observes from the traffic it controls. As a corollary to this statement, their dependence on the residual variation of the background flow (to achieve sub-linear regret) does not always lead to the desired regrets. e.g., In real-world urban networks, background flow during peak hours can be highly predictable (fully explained by context such as time-of-day or weather) with negligible residual variance. If v_* → 0, the algorithm risks suffering linear regret, as shown in the authors' own failure analysis.

  2. The feedback model assumes that the platform only observes noisy costs on edges that carry its own routed flow (n_(t,e) > 0). In modern Intelligent Transportation Systems (ITS), platforms can often access aggregate network-wide travel times, loop-detector data, or purchase GPS probe data from non-platform users. Presuming a strict semi-bandit structure may overly restrict the platform's learning capability relative to what is practically available.

Finally, their assumption of the app controlling significant fraction of the traffic to effect the travel times for all users of the network is not correct.

Questions for authors
  1. In Proposition 4, you demonstrate that without residual load variation, RECTCOR can suffer linear regret. In real-world networks, traffic on key arterial roads can be highly predictable with very little residual variance v_*. If a platform detects that certain edges have near-zero residual variance, could RECTCOR be modified to introduce a small, controlled amount of active perturbation (forced exploration) to restore sublinear regret, and what would be the impact on network congestion?

  2. Your current theoretical framework relies on affine edge costs. If we extend the algorithm to highly non-linear cost functions—such as the 4th-power polynomial BPR function—how does the "price of rectangularization" scale?

  3. In Remark 1, you discuss a platform-centric objective where background flow U_t is assumed to be exogenous. If a platform routes a large share of traffic (needs to be verified), the background users will dynamically adapt their routes in response to the platform's choices, establishing a Wardrop equilibrium. How would such strategic, non-exogenous background flow behavior affect the "excitation" dynamics and the stability of RECTCOR's learning process?

5 comments

We thank the reviewer for engaging with the model in detail. We are glad that they find the use of background flow as a source of excitation valuable, and the theoretical analysis including a high-probability O~(T)\widetilde{O}(\sqrt{T}) regret bound sound and clean.

Below we respond to the main concern about model assumptions in detail.

1. Routing before the background flow is revealed, and the risk of linear regret as v\*→0v_\*\to0.

A predictable background flow is a case of our model, not an exception. The platform routes on a prediction of the background flow, and observes the realization afterwards. An accurate prediction simply means a small residual of the prediction.

We agree that the platform often has a good estimate of current travel times. But a travel time observed at current load does not tell how the cost changes when the platform moves its own flow. For that it must learn the slope of the cost, and the slope is identified only if the loads vary. What our analysis needs is therefore variation of the loads, not a drastic change in the costs.

Besides, a vanishing residual does not by itself cause linear regret. The experiment on Sioux Falls as submitted has a residual of 0.01% of the mean background flow, and RectCOR's regret grows no faster than the T\sqrt{T} rate. Because context and demand vary the loads, the regret grows sublinearly even with a very small residual. Linear regret can arise when repeated loads cause the confidence geometry to degenerate, as in Proposition 4. However, a small residual alone does not imply such failure, since context and demand variation can also maintain compatibility. we examine this case, and what a perturbation can do about it, in our answer to Question 1 below (Table 3).

2. Semi-bandit cost feedback when data from non-platform users are available.

The semi-bandit structure concerns only the cost reports, and our method may extend to the other data the reviewer lists. RectCOR already uses counts of the background flow on every edge, which is what loop detectors provide, while its cost reports come only from its own users on the edges they use. Travel times from non-platform users, such as probe data, are not part of the algorithm, but they can be added to the same regression as further observations, with the routing rule and the confidence radius unchanged.

We modified RectCOR to also use such additional data, and tested the effect of additional data from background users on Sioux Falls. Within each round, the platform receives one more report for every edge in a given subset: the travel time on that edge averaged over its background users, with the same noise model as the platform's own reports. The report enters the cost regression of that edge as one more observation, weighted by its precision. We gave such reports on a quarter, half or all of the edges, since purchased probe data rarely cover every edge. The certainty-equivalent greedy baseline receives the same reports.

Here RectCOR runs with a radius scale η0=0.025\eta_0=0.025 instead of the 0.1 of the submitted paper. In the experiments, RectCOR's confidence radius is the theoretical radius times a scale η0<1\eta_0 < 1, as described in the appendix of the submitted paper (Appendix D). An additional experiment that varies this scale shows that 0.025 is the best value on Sioux Falls.

Travel-time reports onno edgea quarterhalfevery edge
RectCOR, η0=0.025\eta_0=0.025102806845
Greedy119957951

[Table 1. Regret on Sioux Falls by the share of edges with travel-time reports from background users (T=10,000T=10{,}000; averaged over 20 seeds).]

We can see that RectCOR's regret falls steadily as the coverage grows. The reports sharpen the estimates on the edges that the platform already uses, and they inform it about edges that its own reports can reveal only by routing there.

What our semi-bandit model provides is a guarantee for the case with limited data: Theorem 1 needs only the platform's own reports. Extending the guarantee to the regression with the extra reports would be a natural next step, which we leave for future work.

3. The assumption that the platform controls enough traffic to affect travel times.

A platform does not need to control a large share of the traffic to affect travel times. In field experiments in ten US cities [1], rerouting under 2% of the trips of a navigation app raised speeds on the targeted congested segments by about 2%. Even a change of this size in a platform's flow moves travel times measurably, and a platform that routes all of its users controls far more flow than that. Our model does not assume a large share either. The cost of an edge depends on its total load (the platform's flow plus the background flow), and the theorem has no share threshold.

(1/3)

Response to R3 (Reviewer hPk2) - Part 2/3

3. The assumption that the platform controls enough traffic to affect travel times (continued).

We provide an additional Sioux Falls experiment with the platform's share of the traffic reduced from 66% down to 5%. We moved platform demand into the background flow, so that the total load is unchanged.

Platform share66%30%20%10%5%
RectCOR, η0=0.025\eta_0=0.025102959688107
  added in the last 1,000 rounds1.93.03.73.35.6
Greedy119185253263214
  added in the last 1,000 rounds1.93.56.710.98.5

[Table 2. Regret on Sioux Falls at different platform shares (T=10,000T=10{,}000; averaged over 20 seeds). The indented rows show the regret added over the last 1,000 rounds.]

RectCOR with η0=0.025\eta_0=0.025 works at such small shares. Over the 10,000 rounds, RectCOR's regret stays between 88 and 107 as the share falls, and it stays below greedy's on all 20 seeds at every share. The regret added late in the horizon grows as the platform's share falls, from 1.9 to 5.6 per 1,000 rounds (indented rows). At a 5% share the smaller radius scale η0=0.01\eta_0=0.01 keeps it falling, with an average regret of 126 at T=10,000T=10{,}000. We note that with the submitted η0=0.1\eta_0=0.1 the regret rises as the share falls and grows linearly at a 5% share within this horizon (2,777, against 214 for greedy).

We now turn to the reviewer's three questions.

Q1. Random perturbation when the residual is near zero, and its effect on congestion.

We ran an additional experiment with the small, controlled perturbation that the reviewer describes. To RectCOR we added a random perturbation of its routing: in every round a share d,t−1/4d\\,t^{-1/4} of the demand, with d=0.3d=0.3, is routed at random, so the loads keep varying while the perturbation fades. As the reviewer suggests, we also applied the perturbation only in rounds in which an edge used by the planned route is detected as degenerate (correlation ρ\rho of its confidence ellipse within 0.001 of −1-1). We took the extreme case, in which nothing else moves the loads: the small network with the context and the demand fixed and no residual. The perturbation brings the regret back to sublinear growth over the tested horizon, and with the detection rule it costs nothing when a residual already moves the loads.

No residual (σ=0\sigma=0)Residual (σ=1\sigma=1)
RectCOR10,9588.8
  added in the last 5,000 rounds1,0960.1
RectCOR + random perturbation1,303743
  added in the last 5,000 rounds9356
RectCOR + random perturbation when degeneracy is detected1,3858.6
  added in the last 5,000 rounds960.1

[Table 3. Regret on the small network with the context and the demand fixed (T=50,000T=50{,}000; mean of 20 seeds). The indented rows show the regret added over the last 5,000 rounds.]

Without residual the perturbation cuts RectCOR's regret by 88%. Also, the regret added per 5,000 rounds falls from 292 at the start to 93 at the end, whereas without the perturbation it stays at 1,096. When a residual already moves the loads (σ=1\sigma=1), no perturbation is needed, and applied in every round it only adds regret. With the detection rule it is not triggered there and the regret is that of RectCOR (8.6 against 8.8), while without residual it keeps its benefit (1,385).

The effect on congestion is small: with the perturbation the travel cost of other users is 0.1% above its level under optimal routing (0.25% for RectCOR alone).

Q2. How the price of rectangularization scales under nonlinearity of the cost function.

With a known exponent the geometry of the rectangle carries over: a cost a(x)+b(x)zpa(x)+b(x)z^p is linear in the features (1,zp)(1,z^p), so the rectangle's width still exceeds the ellipse's by at most 2/(1+ρ)\sqrt{2/(1+\rho)}, with ρ\rho the correlation in that design. An extension of the algorithm would also have to predict higher moments of the background flow, since $\mathbb E

(n+U)p(n+U)^p

\ne(n+\mathbb EU)^p$, which we leave for future work.

We added an experiment to measure the price for the affine learner when the true cost is nonlinear. The true unit cost of edge ee at total load zz is αe+se(z/Ce)p\alpha_e+s_e(z/C_e)^p, where CeC_e is the capacity of the edge and p=4p=4 gives the BPR curve of the Sioux Falls data. RectCOR runs with η0=0.025\eta_0=0.025, and greedy fits the same affine model without a rectangle. Along RectCOR's own trajectory, we also recorded how many times larger the rectangle's bonus is than the ellipse's at the routed load. The table reports this ratio (median over the used edges, rounds 4,001–10,000; 8 seeds).

(2/3)

Q2. How the price of rectangularization scales under nonlinearity of the cost function (continued).

p=1p=1p=2p=2p=3p=3p=4p=4 (BPR)
Regret of RectCOR, η0=0.025\eta_0=0.025216 ±\pm 10661 ±\pm 1185,127 ±\pm 1,90714,720 ±\pm 3,894
Regret of greedy233 ±\pm 13635 ±\pm 1095,087 ±\pm 1,91914,824 ±\pm 3,902
Rectangle's bonus relative to the ellipse's13.012.611.210.5

[Table 4. Regret on Sioux Falls under nonlinear costs (10,000 rounds, mean ±\pm sd over 20 seeds). The regret here is measured against an exactly solved benchmark, which adds about 114 to every method relative to Tables 1 and 2.]

What nonlinear costs add is the error of the affine model, not a wider rectangle. The rectangle's bonus relative to the ellipse's does not grow with the exponent, and RectCOR's regret stays close to greedy's at every exponent. Under BPR, with the busiest edge at 1.4 times its capacity, RectCOR costs 8.6% more than optimal routing and greedy 8.7% more, and this extra cost persists.

Q3. Effects of strategic background users who adapt to the platform.

Strategic response is outside our model, so we provide an experiment on Sioux Falls where all of the background volume is adaptive. When each round starts, these users compute their user (Wardrop) equilibrium given the platform's flow in the previous round and move a share θ\theta of the way there (θ=0\theta=0: no response; θ=1\theta=1: full re-equilibration). Adaptive users matter more when the platform is small, so we ran this at the submitted platform share (66%) and at shares of 30% and 10%. RectCOR runs with η0=0.025\eta_0=0.025. Each method runs in its own copy of the network, and its regret is measured in each round against the best routing for the background mean of that round along its own trajectory; this benchmark does not know the residual. In the θ=0\theta=0 control the adaptive users stay at their equilibrium for the mean conditions, so the background flow does not vary with the context. The effect of the response grows as the platform's share falls: relative to the matched θ=0\theta=0 control, RectCOR's regret rises by less than 4% at the submitted share and by 23–28% at a 30% share, while the excitation is not reduced.

Platform shareθ=0\theta=0θ=0.2\theta=0.2θ=0.5\theta=0.5θ=1\theta=1
66% (submitted)110 (2.7)110 (2.9)111 (2.9)114 (3.1)
30%135 (8.7)166 (12.3)167 (12.3)173 (12.4)
10%245 (22.6)276 (25.7)265 (24.5)263 (24.3)

[Table 5. RectCOR's regret on Sioux Falls when all background users are adaptive, by the platform's share of the traffic and the adaptation rate θ\theta (T=10,000T=10{,}000; mean of 10 seeds; η0=0.025\eta_0=0.025). In parentheses: the regret added over the last 1,000 rounds.]

At the submitted share the largest change is from 110 to 114 (paired change 4.2 [0.7, 7.7]). At a 30% share the regret rises from 135 to 166–173 (paired change 37.4 [30.6, 44.3] at θ=1\theta=1) and keeps growing sublinearly, with a growth exponent of about 0.7 against 0.61 in the control; greedy with the same response is then level with RectCOR (169 at θ=1\theta=1). At a 10% share the regret is already high in the control (245) and grows almost linearly there, because with the whole background flow fixed little moves the loads; the response adds 8–13% to it, and greedy is lower once the users respond (146 at θ=1\theta=1). The excitation is not affected: the factor 2/(1+ρ)\sqrt{2/(1+\rho)} of the rectangle (median over the used edges, over rounds 5,001–10,000 and over the seeds) is 19 at the submitted share, 33 against 31–33 at a 30% share and 46 against 42–45 at 10% (control against response). These results are for one response rule; a guarantee under strategic response is beyond the present analysis.

The table below lists where each point is addressed in the revised PDF.

PointRevised PDF
Radius scale η0\eta_0App. E.4; Table 4
1. Predictable background flowSec. 5 (Figure 3); App. E.6 (Figure 13)
2. Data from non-platform usersApp. E.8 (Figure 17b)
3. Platform shareApp. E.8 (Figure 17a)
Q1. Random perturbationApp. E.6 (Figure 14)
Q2. Nonlinear costsApp. E.5 (Figure 12)
Q3. Adaptive background usersApp. E.9 (Figure 18)

We are grateful for the reviewer's detailed and constructive engagement, which led to valuable new experiments. If our answers resolve the main concern, we would respectfully ask the reviewer to reconsider the assessment of the paper's overall soundness and, with it, the overall evaluation. We would be glad to clarify any point that remains open.

(3/3)

[1] Arora et al. Urban congestion relief experiments through routing-app interventions. Nature Cities, 2026.

Reviewer_8GX5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper proposes a new method for online routing, termed RectCOR, in a transportation network with dynamic background flows and arbitrary context, where context is defined as some general conditioning event such as weather. It replaces standard ellipsoidal confidence sets by rectangular confidence sets, thereby reducing the optimization difficulty from nonconvex to convex programming. A high probability O~(T)\tilde{O}(\sqrt{T}) regret bound is shown, against an optimal non-clairvoyant benchmark. Experiments with small networks are used to further show the performance benefit of the proposed method.

Critical strengths
  1. It is interesting to combine contexts, background flows, and the observation of background flows by controlled traffic, which leads to a nontrivial problem that requires a method to reduce the computation complexity of optimization.

  2. The sublinear O~(T)\tilde{O}(\sqrt{T}) regret bound provides strong performance guarantee for the proposed method. The derivation appears sound (but I have not checked all details in the appendix).

Critical weaknesses
  1. The main paper's presentation is poor. In Section 2.1, there are many undefined notions when they first appear, such as "round", "calibration constants", noise-scale profile", and symbols ce(x,z)c_e(x,z), zz, aea_e, beb_e, and ξt,e\xi_{t,e}. Furthermore, the writing in Section 5 is terse and lacking insight. Meanwhile, there is still room left on Page 9 that is unused. Overall, the paper appears rushed, and the main paper is understandable only after reading the appendix.

  2. The comparison with Gollapudi et al. (2023) is insufficient. Even though Gollapudi et al. (2023) does not consider context or background flow, it does use rectangular confidence sets and appears to be a special case of the current study. Some of the analysis techniques in the previous paper are transferred to the current paper without proper attribution. More explanation should be given on the differences between these two studies and what exactly is new in the proposed RectCOR method and regret bound derivation. Furthermore, Gollapudi et al. (2023) can be applied to the current system by either ignoring context and background flow or adopting some simple variant. Therefore, numerical comparison with Gollapudi et al. (2023) is necessary to demonstrate the claimed benefit of RectCOR.

  3. The numerical comparison benchmarks consist of only naive UCB and ϵt\epsilon_t-greedy. Besides Gollapudi et al. (2023), another interesting family of benchmarks would be approximate UCB with simplified computation, such as UCB using convex bounds. Since RectCOR mostly does not achieve the performance of naive UCB (see comment below), its main benefit is only complexity reduction. To make a strong case for that, we need to see some comparison with lower-complexity variants of UCB.

  4. The authors claim that Figure 2 (for the 7-edge network) shows that RectCOR outperforms naive UCB for the case σ=1\sigma=1. This claim is not substantiated by Figure 2, since the regret of RectCOR has a clear upward slope going toward the regret of UCB, whereas the regret of UCB stays flat. Based on the results for other σ\sigma values in the same figure, it looks likely that the regret of RectCOR eventually will exceed that of UCB. Furthermore, there is no comparison with naive UCB for the 76-edge Sioux Falls network.

  5. Both networks used in the presented experiments are very small (7 edges and 76 edges). They are not sufficient to demonstrate the performance of different methods in practical networks. As example for comparison, Gollapudi et al. (2023) experiments on a New York City network with over 300,000 edges. The contrast is striking.

  6. The cost function is linear in the load zz. This over-simplification is necessary for the analysis of regret. However, in most practical applications the cost would be far from linear, e.g., queueing/congestion delay, especially when the load is near the capacity of an edge.

Questions for authors
  1. What exactly are the new challenges in extending Gollapudi et al. (2023) to consider context and background flows?

  2. Does RectCOR outperform lower-complexity variants of UCB?

  3. Is it possible to experiment with larger-scale networks similar to the one in Gollapudi et al. (2023)?

6 comments

We thank the reviewer for the detailed and direct comments. We are glad that they find the combination of contexts, background flows and their observation through controlled traffic an interesting and nontrivial problem, and the sublinear O~(T)\widetilde O(\sqrt T) regret bound a strong guarantee whose derivation appears sound.

Below we respond to the reviewer's questions and concerns.

The new challenges over Gollapudi et al. [1]

The new challenges come from routing on a prediction while learning at the realized load, and three things go beyond the setting of Gollapudi et al.

The first is the information structure. Their setting has neither context nor background flow, so the cost of an edge depends on the platform's own flow, which is known when it routes. Here routing uses a prediction of the background flow by context, while costs are learned at the realized total load, which is revealed only after the decision.

The second is an explicit account of the rectangle's price. Their analysis (their Lemma 4) bounds the enlargement from the ellipse to the rectangle by a constant that depends only on the edge capacity. We characterize it: the rectangle's width exceeds the ellipse's by at most 2/(1+ρ)\sqrt{2/(1+\rho)}, where ρ\rho is the correlation of the intercept–slope confidence ellipse, and this factor is attained. It diverges as repeated loads drive ρ→−1\rho\to-1, and Proposition 4 shows that this causes actual linear regret, which is why the excitation must be controlled separately.

The third is an analysis that controls this price without forced exploration. Under adaptive routing, residual variation of the background flow, which their model does not have, keeps 1+ρ1+\rho bounded below uniformly in time, which yields the O~(T)\widetilde O(\sqrt T) bound.

The rectangular optimism that keeps routing tractable was first introduced for congestion routing by Gollapudi et al. [1], whom our submission cites in its introduction. The revised paper makes the credit and the relation to their analysis more explicit. A new paragraph in Section 1.1 attributes to them the learning of affine congestion costs from allocation-dependent observations and the rectangular optimism, and Section 4.2 relates their enlargement factor to ours.

Next, we describe the additional experiments that the reviewer requested. In the experiments, RectCOR's confidence radius is the theoretical radius times a scale η0<1\eta_0 < 1, as described in the appendix of the submitted paper (Appendix D). It was fixed at 0.25 on the small network and 0.1 on Sioux Falls. In additional experiments on Sioux Falls we varied the radius scale on a grid, η0=0.01\eta_0=0.01, 0.025, 0.05 and 0.1, and the constants of the other methods by the same factors. On the small network, the same check shows that the submitted 0.25 is at or near the best value in every design.

(a) Comparison with Gollapudi et al.

We ran an adaptation of their method with our regularization and radius (no context, regression on the platform's own flow) on the small network and on Sioux Falls. On the small network we ran Types 1–3 of the submitted paper with residual s.d. σ=0.5\sigma=0.5: context and demand move the loads in Type 1, the demand in Type 2 and the background flow in Type 3. On Sioux Falls we also varied how unevenly the context affects the edges, with a parameter hh: h=0h=0 is the submitted design, in which the context scales all edges alike, and at h=1h=1 the two halves of the network respond to different context variables. Both methods use the radius scale η0=0.025\eta_0=0.025 on Sioux Falls, the best value for RectCOR on the grid (Table 2).

Type 1Type 2Type 3h=0h=0h=0.5h=0.5h=1h=1
Gollapudi et al. (adapted)188102,1921455001,463
RectCOR3413141029896

[Table 1. Regret of the adapted method of Gollapudi et al. and of RectCOR (T=10,000T=10{,}000; mean of 20 seeds).]

RectCOR improves on their method where the context or the background flow moves the loads, which is where its extensions apply. On the small network RectCOR is far below the adaptation where the background flow moves the loads (Type 3) and lower where the context does (Type 1); in Type 2, where only the demand does, the two are close. On Sioux Falls RectCOR is below the adaptation at every hh, on all 20 seeds. As the context becomes uneven across the edges, the regret of the adaptation rises from 145 to 1,463, while that of RectCOR stays near 100. The gap is smallest in the submitted design (h=0h=0), where the context moves the optimal flow by only 2.3%.

(1/3)

(b) Larger networks.

We added Anaheim (914 edges) and Chicago-regional (39,018 edges), two standard test networks, with the Sioux Falls design, and ran RectCOR at four radius scales. RectCOR runs on networks of up to 39,018 edges at the routing cost of greedy, and with a smaller radius scale its regret is below greedy's on every seed of all three road networks.

Radius scale η0\eta_00.010.0250.050.1Greedy
Sioux Falls (76 edges, 20 seeds)108102121252119
Anaheim (914 edges, 20 seeds)4745619802,156591
Chicago-regional (39,018 edges, 3 seeds)1,2811,2141,6473,7131,545

[Table 2. Regret of RectCOR by radius scale η0\eta_0 and greedy, on three road networks (T=10,000T=10{,}000).]

In all cases RectCOR keeps the regret sublinear, and with a suitable radius scale η0\eta_0 it beats greedy. The comparison does not depend on tuning to each network: the value that was best on Anaheim, η0=0.01\eta_0=0.01, also beats greedy on every seed of the other two networks. These networks are smaller than the New York City network of Gollapudi et al. (over 300,000 edges), but Anaheim and Chicago-regional are road networks of a real city and a real metropolitan region, and we believe that they are sufficient to demonstrate the performance of RectCOR in practical networks.

(c) Lower-complexity variants of UCB, and naive UCB.

We ran three lower-complexity variants of UCB on Sioux Falls. Local UCB solves naive UCB's nonconvex objective by Frank–Wolfe without global search. Plug-in UCB subtracts the ellipsoidal bonus, evaluated at the greedy load, from the intercept. Envelope UCB replaces each edge's optimistic total cost by its convex envelope, so it is a UCB with convex bounds. All three use the cost model and the radius of RectCOR, and we ran each of them on the same grid of the radius scale η0\eta_0. RectCOR is the simplest and the fastest of these UCB variants, and its regret is comparable to theirs or lower.

Radius scale η0\eta_00.010.0250.050.1ms per round
RectCOR108 ±\pm 11102 ±\pm 10121 ±\pm 13252 ±\pm 3011.3
Local UCB116 ±\pm 12111 ±\pm 12108 ±\pm 11114 ±\pm 1434.1
Plug-in UCB120 ±\pm 12121 ±\pm 12123 ±\pm 12126 ±\pm 1222.2
Envelope UCB120 ±\pm 13121 ±\pm 14133 ±\pm 21233 ±\pm 4146.2
Greedy119 ±\pm 13–––11.3

[Table 3. Regret on Sioux Falls by radius scale η0\eta_0 and routing time per round (mean ±\pm sd over 20 seeds, T=10,000T=10{,}000).]

RectCOR performs well with the simplest and fastest routing step. With each method at its best radius scale, its regret is the lowest at T=10,000T=10{,}000. Moreover, RectCOR solves just one convex program per round, matching the routing time of greedy, while the other variants take two to four times as long.

Naive UCB itself takes about 3.3 s per round on Sioux Falls for its global solve, which is 9–13 hours per seed over 10,00010{,}000 rounds. We therefore do not have a complete run of it there. On the small network we extended the runs at σ=1\sigma=1 from T=4,000T=4{,}000 to T=100,000T=100{,}000. As the reviewer anticipated, the early advantage of RectCOR at σ=1\sigma=1 does not last, and the revised paper no longer claims it: it now states that naive UCB has lower regret at σ=0.25\sigma=0.25 and that the gap narrows as the residual variation increases.

(2/3)

Remaining points.

We thank the reviewer for pointing out where the presentation could be improved, including the notions that were undefined at first use. In the revised paper each notion is defined at first use in Section 2.1, and a table of the main notation is placed at the start of the appendix (Table 1 of the revised PDF). We also rewrote Section 5 around the insights from the experiments: each paragraph states what an experiment shows and why, and points to the new experiments of Appendix E, where a new table compares all methods on Sioux Falls (Table 4).

We also address the affine cost model. Affine costs are a first-order model of congestion that is standard in the analysis of routing (e.g., [2, 3]) and in the prior work on learning to route [1]. They are a reasonable approximation over a moderate operating range and become less accurate as strongly nonlinear costs are pushed above capacity. We measured this on Sioux Falls with costs αe+se(z/Ce)p\alpha_e+s_e(z/C_e)^p and every learner kept affine: RectCOR's routing costs 0.12%, 0.38%, 3.0% and 8.6% more than optimal routing for p=1p=1, 2, 3 and 4, and greedy with affine costs pays about the same. The full results are in Appendix E.5 of the revised paper and in our response to Reviewer hPk2 (Q2, Table 4).

The table below lists where each point is addressed in the revised PDF.

PointRevised PDF
New challenges over Gollapudi et al. [1]Sec. 1.1, 4.2
Radius scale η0\eta_0App. E.4; Table 4
(a) Comparison with Gollapudi et al.App. E.2 (Figure 7)
(b) Larger networksApp. E.4 (Figure 11)
(c) Lower-complexity variants of UCBApp. E.3 (Table 4, Figure 8), E.4
(c) Naive UCB over a longer horizonSec. 1, 5; App. E.1 (Figure 6)
Presentation and notationSec. 2.1, 5; Table 1
Affine cost modelApp. A.1, E.5 (Figure 12)

We hope that the comparison with Gollapudi et al. [1], the added baselines and networks, and the clearer presentation address the reviewer's main concerns. If they do, we would be grateful if the reviewer would consider raising the evaluation of the paper, and we would gladly clarify anything that remains unclear.

(3/3)

[1] Gollapudi et al. Online learning for traffic navigation in congested networks. International Conference on Algorithmic Learning Theory, 2023.

[2] Roughgarden & Tardos. How bad is selfish routing? Journal of the ACM, 2002.

[3] Cominetti et al. The price of anarchy in routing games as a function of the demand. Mathematical Programming, 2024.

Reviewer_RVnpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies contextual online routing in a congested network, where a platform allocates traffic before observing the background flow. Edge costs are unknown affine functions of the total load, and cost feedback is available only on used edges. The authors propose RECTCOR, which uses rectangularized confidence sets to keep each routing step a convex quadratic program. They show that residual variation in background flow can help identify the cost parameters and control the loss from rectangularization. Under this condition, the algorithm achieves a high-probability $\widetilde O(\sqrt T)$ regret bound without forced exploration.

Critical strengths
  1. I find the role of background-flow variation interesting. It makes congestion harder to predict, but also allows the platform to observe costs at different loads. The paper formalizes how this variation helps separate the intercept and slope of the cost function. The time-uniform compatibility result under adaptive routing is a useful part of the analysis.

  2. The analysis carefully handles the feedback structure. Routing decisions use predicted background flow, while cost estimates are updated using realized loads. The proof connects these two quantities and also accounts for the dependence of observation precision on allocated flow.

  3. The computational aspect is clearly explained. Each routing step remains a convex quadratic program and does not require enumerating all paths. The paper also discusses how optimization errors enter the regret bound. The small-network experiments separately vary context, demand, and background flow, which helps readers understand where the learning benefit comes from.

Critical weaknesses
  1. Several assumptions need stronger justification. The affine dependence of travel cost on total load is important for both the algorithm and the analysis. However, traffic costs can become strongly nonlinear near capacity. The Sioux Falls experiment fits an affine model to BPR costs, which keeps the evaluation within the assumed model. It would help to explain when this approximation is reasonable and how sensitive the method is to approximation errors. In addition, the regret guarantee requires persistent background-flow variation even after conditioning on context, history, and the routing decision. How restrictive is this condition in the intended applications? The “price of convexity” claim also needs a clearer qualification: Lemma 13 considers convex unit-cost minorants on the whole interval [0,∞)[0,\infty), while the actual routing problem has a bounded feasible load range and only requires a convex total-cost objective.

  2. The main performance result is an upper bound, and its tightness remains unclear. The compatibility result and the failure example provide useful supporting theory, but there is no matching lower bound to assess the regret guarantee. In particular, comparison with the T\sqrt T rate of standard linear bandits does not establish that this rate is necessary in the present routing problem. A lower bound, even for a simple network or a restricted version of the setting, would help clarify which dependencies are unavoidable. It would also be useful to understand whether the dependence on κ⋆\kappa_\star reflects an intrinsic difficulty of learning with limited load variation or mainly the rectangular approximation.

  3. The experiments could provide a stronger comparison with alternative methods. One useful addition would be the certainty-equivalent greedy baseline on Sioux Falls. This baseline is already implemented and performs best in the Type-1 small-network experiments, where context and demand both vary. Since these are also the main sources of excitation in Sioux Falls, this comparison seems particularly relevant. Furthermore, given the real-world motivation, a test with nonlinear costs or imperfect background-flow observations would also make the empirical evidence more convincing.

Questions for authors

Could the authors better justify the affine cost model and the persistent conditional variation assumption for background flow in the intended applications? Please also clarify the scope of the “price of convexity” claim when feasible loads are bounded. Also, could the authors include the certainty-equivalent greedy baseline on Sioux Falls and test robustness to nonlinear costs or imperfect background-flow observations, as discussed in Weakness 3?

5 comments

We thank the reviewer for constructive suggestions. We are glad that they find the role of background-flow variation in the theoretical analysis and the time-uniform compatibility result interesting and useful. They also note the clear explanation of the computational aspect of our work.

Below we respond to the reviewer's questions and suggestions.

Clarification of tightness of the regret bound.

We establish a minimax lower bound within our routing model, resolving the question of tightness in TT. Even on a simple network with two parallel edges, every non-anticipating routing policy incurs expected regret at least T/32\sqrt T/32 on some admissible instance. The full proof is in Appendix C.7 of the revised paper; we give a sketch here.

With a fixed context and unit demand, the edge costs at total load zz are 1−ϑ+2ϑz1-\vartheta+2\vartheta z and 1+ϑ+2ϑz1+\vartheta+2\vartheta z, with their assignment to the edges reversed between the two instances. Background flows are independently 00 or 22, with equal probability, across edges and rounds (v\*=1v_\*=1). Each used edge carrying flow n>0n > 0 yields a cost report with independent zero-mean Gaussian noise of variance 1+1/n1+1/n. Both instances satisfy Assumptions 1–4 with common constants independent of TT. Their optimal allocations to edge 1 are n1∗=3/4n_1^*=3/4 and n2∗=1/4n_2^*=1/4, and the one-round regret at allocation nn in instance s∈1,2s \in \\{1,2\\} is 4ϑ(n−ns∗)24\vartheta(n-n_s^*)^2. For every fractional split, the conditional KL divergence of one round's feedback is at most 2ϑ22\vartheta^2. Setting ϑ=1/(2T)\vartheta=1/(2\sqrt{T}) therefore bounds the KL divergence between the full adaptive transcript laws by 1/21/2. Pinsker's inequality and a two-point testing argument then give, on at least one instance, Pr⁡(RegretT≥T/8)≥1/4,\Pr(\mathrm{Regret}_T \ge \sqrt{T}/8) \ge 1/4, implying the expected-regret lower bound above. The hard pair is selected for each horizon from a fixed model class; the costs remain fixed throughout each run. This establishes optimality in TT, up to logarithmic factors.

The role of κ\*\kappa_\* dependence.

The κ\*−1/2\kappa_\*^{-1/2} factor in our upper bound controls mainly the additional uncertainty introduced by rectangularization. When the residual variation vanishes, the regret of RectCOR grows linearly while that of naive UCB, which keeps the confidence ellipse, stays low, as we describe below in discussing the residual-variation condition (Table 3). The new lower bound establishes optimality in TT up to logarithmic factors with a horizon-independent compatibility constant, but does not establish a minimax dependence on κ\*\kappa_\*.

Greedy on Sioux Falls.

We ran the certainty-equivalent greedy baseline on Sioux Falls. Along with the baseline, we varied the confidence radius scale on a grid, η0=0.01\eta_0=0.01, 0.025, 0.05 and 0.1, where it was fixed at 0.1 in submitted paper. In the experiments, RectCOR's confidence radius is the theoretical radius times a scale η0<1\eta_0 < 1, as described in the appendix of the submitted paper (Appendix D).

Cumulative regret at round2,0006,00010,000
RectCOR, η0=0.01\eta_0=0.0186 ±\pm 9100 ±\pm 10108 ±\pm 11
RectCOR, η0=0.025\eta_0=0.02578 ±\pm 893 ±\pm 9102 ±\pm 10
RectCOR, η0=0.05\eta_0=0.0582 ±\pm 7106 ±\pm 10121 ±\pm 13
RectCOR, η0=0.1\eta_0=0.1146 ±\pm 17215 ±\pm 25252 ±\pm 30
Greedy94 ±\pm 11111 ±\pm 12119 ±\pm 13

[Table 1. Cumulative regret on Sioux Falls up to various rounds (mean ±\pm sd over 20 seeds).]

Greedy has lower regret than RectCOR as submitted, but at η0=0.01\eta_0=0.01 and 0.0250.025 RectCOR is below greedy on all 20 seeds. At η0=0.025\eta_0=0.025 RectCOR is already below greedy at round 2,000, on every seed, and the gap stays about the same afterwards. The greedy falls behind in the early rounds, which we attribute to its lack of exploration. The comparison does not hinge on one value or one network: at both η0=0.01\eta_0=0.01 and η0=0.025\eta_0=0.025 RectCOR's regret is also below greedy's on the two larger road networks we added (Appendix E.4). The further experiments on Sioux Falls use η0=0.025\eta_0=0.025, the best value in Table 1; since it is chosen on the same network, we present them as a sensitivity analysis.

(1/3)

Justification of the affine cost model.

The affine model is a first-order description of congestion: a baseline cost plus a constant marginal effect of load. It is standard in the analysis of routing (e.g., [1, 2]) and in the prior work on learning to route [3], and here the intercept and the slope also depend on the context, such as the time of day or the weather. It is a reasonable approximation when the load on each edge varies over a moderate range.

To measure how sensitive the method is to the approximation error, we ran Sioux Falls with true unit costs αe+se(z/Ce)p\alpha_e+s_e(z/C_e)^p with exponent p=1p=1, 2, 3 or 4, where CeC_e is the capacity of edge ee, while every method still fits affine costs. With p=4p=4 this is the travel-time curve of the original Sioux Falls data.

p=1p=1p=2p=2p=3p=3p=4p=4
RectCOR, η0=0.025\eta_0=0.025216 ±\pm 10661 ±\pm 1185,127 ±\pm 1,90714,720 ±\pm 3,894
  extra cost over optimal routing0.12%0.38%3.0%8.6%
RectCOR, η0=0.1\eta_0=0.1 (submitted)366 ±\pm 30847 ±\pm 1774,893 ±\pm 2,13214,595 ±\pm 4,431
Greedy233 ±\pm 13635 ±\pm 1095,087 ±\pm 1,91914,824 ±\pm 3,902

[Table 2. Regret on Sioux Falls under nonlinear true costs with linear fitting (T=10,000T=10{,}000, mean ±\pm sd over 20 seeds).]

The results show that the learner with the affine cost model copes with moderate nonlinearity, but not with the highly nonlinear case. At p=2p=2 RectCOR costs 0.4% more than optimal routing, but the extra cost is 3.0% at p=3p=3 and 8.6% at p=4p=4. This is the price of fitting a line to a curve, and greedy with the same affine cost fitting pays it equally. The measured price of the rectangle does not grow with the exponent. Tuning the radius scale does not reduce it: at p=3p=3 and p=4p=4 the two radius scales give statistically the same regret.

Note: The regret in Table 2 is measured against an exactly solved benchmark, while Table 1 solves the benchmark with the same 200-iteration Frank–Wolfe routine as the algorithms. The regret of every method is therefore about 114 higher in Table 2 than it would be under the benchmark of Table 1.

How restrictive the persistent residual-variation condition is.

The condition is sufficient, not necessary, and in a setting close to practice it is hardly a constraint. What the analysis needs is that the confidence ellipse of intercept and slope does not degenerate on any edge, and other sources of informative load variation can also maintain compatibility. Residual variation matters only when nothing else moves the loads.

To see how much residual variation is needed in the extreme case, we ran an experiment with context and demand fixed on the small network, which leaves the residual as the only source of load variation, and varied its size. On this network a residual of about 1% of the mean flow is enough to end the linear growth of RectCOR's regret.

σ\sigma00.05 (1%)0.1 (2%)0.25 (6%)1
RectCOR10,958632161558.8
Naive UCB382515109.1

[Table 3. Regret on the small network with context and demand fixed, by the residual sd σ\sigma of the background flow, with its share of the mean flow in parentheses (T=50,000T=50{,}000, average of 20 seeds).]

At σ=0\sigma=0 RectCOR fails on 17 of the 20 runs: their regret grows linearly and still adds more than 100 over the last 10,000 rounds (10,958 on average). From σ=0.05\sigma=0.05 on, no run does. Naive UCB, which uses the same learner and radius with the confidence ellipse, fails on no run at any σ\sigma (38 on average at σ=0\sigma=0). The failure without residual variation therefore belongs to the rectangle, not to the learning problem; this is the evidence on the role of κ\*\kappa_\* above.

In a setting closer to practice, context and demand change from round to round and supply the variation. The Sioux Falls experiment of the submitted paper is such a case: its residual is only 0.01% of the mean background flow, yet RectCOR's regret grows no faster than the T\sqrt{T} rate. There the residual-variation condition is hardly a constraint.

(2/3)

Imperfect background-flow observations.

We ran the test with imperfect background-flow observations that the reviewer suggested, on Sioux Falls. After every round the count of the background flow on each edge is missing with probability qq, and the learner uses its own prediction in place of a missing count. A missing count matters only if it is hard to predict, and in the submitted design the residual is 0.01% of the mean flow, so we raised the residual standard deviation to 5% and 15% of the mean flow. RectCOR runs with η0=0.025\eta_0=0.025, and each run is paired with the same run under complete counts. Missing counts raise RectCOR's regret by less than 4%, even when 80% of them are missing.

Share of counts missing020%40%60%80%
Residual 5% of the mean flow100 ±\pm 9101 ±\pm 9100 ±\pm 9101 ±\pm 8100 ±\pm 7
  change from complete counts–0.4−0.2-0.20.2−0.9-0.9
Residual 15% of the mean flow95 ±\pm 896 ±\pm 896 ±\pm 998 ±\pm 898 ±\pm 7
  change from complete counts–1.51.83.63.4

[Table 4. RectCOR's regret (η0=0.025\eta_0=0.025) on Sioux Falls when counts of the background flow are missing, for two sizes of the residual (T=10,000T=10{,}000; mean ±\pm standard deviation over 10 seeds). The indented rows are the mean paired change from the run with complete counts.]

With a residual of 5% none of the changes is distinguishable from zero. With a residual of 15%, where the prediction that replaces a missing count is off by 10% (median relative error over the edges), the regret rises by 1.5 [−0.3-0.3, 3.3], 1.8 [0.3, 3.3], 3.6 [2.3, 4.9] and 3.4 [0.3, 6.4], that is, by less than 4%. RectCOR remains below greedy on all 10 seeds at every share of missing counts and for both residual sizes. Appendix E.7 of the revised paper also reports the submitted design, where no change is detectable, and count noise and undercounting on the small network.

Scope of the “price of convexity” claim on bounded loads.

We agree with the reviewer's point on the “price of convexity” and have narrowed the claim. The introduction and Section 4.2 of the revised paper no longer call the factor “the price of convexity itself”: it is now a price of this rectangularization. The factor 2/(1+ρ)\sqrt{2/(1+\rho)} compares two confidence constructions and is not the cost of every convex routing formulation. As Section 4.2 and Appendix C now state, Lemma 13 concerns the untruncated unit-cost bound on [0,∞)[0,\infty); on a bounded load range a chord can be tighter, and a convex routing objective does not need convex unit costs.

The table below lists where each point is addressed in the revised PDF.

PointRevised PDF
Tightness of the regret boundSec. 4.4; App. C.7 (Proposition 5)
Role of κ\*\kappa_\*App. E.3 (Figure 9)
Greedy on Sioux Falls, radius scale η0\eta_0App. E.1 (Figure 5), E.4; Table 4
Affine cost modelSec. 2.1; App. A.1, E.5 (Figure 12)
Residual-variation conditionSec. 5 (Figure 3); App. E.3 (Figure 9), E.6 (Figure 13)
Imperfect background-flow observationsApp. E.7 (Figures 15, 16)
“Price of convexity” claimSec. 1, 4.2; App. C (Lemma 13)

We hope that these answers, the new lower bound and the added experiments resolve the reviewer's main concerns. If they do, we would be grateful if the reviewer would consider raising the evaluation of the paper. We would be glad to clarify any remaining point.

(3/3)

[1] Roughgarden & Tardos. How bad is selfish routing? Journal of the ACM, 2002.

[2] Cominetti et al. The price of anarchy in routing games as a function of the demand. Mathematical Programming, 2024.

[3] Gollapudi et al. Online learning for traffic navigation in congested networks. International Conference on Algorithmic Learning Theory, 2023.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.