- 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
-
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.
-
Sound theoretical analysis - The paper provides a clean theoretical framework, including a high-probability 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:
-
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.
-
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
-
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?
-
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?
-
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
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 share | 66% | 30% | 20% | 10% | 5% |
|---|---|---|---|---|---|
| RectCOR, | 102 | 95 | 96 | 88 | 107 |
| added in the last 1,000 rounds | 1.9 | 3.0 | 3.7 | 3.3 | 5.6 |
| Greedy | 119 | 185 | 253 | 263 | 214 |
| added in the last 1,000 rounds | 1.9 | 3.5 | 6.7 | 10.9 | 8.5 |
[Table 2. Regret on Sioux Falls at different platform shares (; averaged over 20 seeds). The indented rows show the regret added over the last 1,000 rounds.]
RectCOR with 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 keeps it falling, with an average regret of 126 at . We note that with the submitted 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 of the demand, with , 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 of its confidence ellipse within 0.001 of ). 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 () | Residual () | |
|---|---|---|
| RectCOR | 10,958 | 8.8 |
| added in the last 5,000 rounds | 1,096 | 0.1 |
| RectCOR + random perturbation | 1,303 | 743 |
| added in the last 5,000 rounds | 93 | 56 |
| RectCOR + random perturbation when degeneracy is detected | 1,385 | 8.6 |
| added in the last 5,000 rounds | 96 | 0.1 |
[Table 3. Regret on the small network with the context and the demand fixed (; 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 (), 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 is linear in the features , so the rectangle's width still exceeds the ellipse's by at most , with the correlation in that design. An extension of the algorithm would also have to predict higher moments of the background flow, since $\mathbb E
\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 at total load is , where is the capacity of the edge and gives the BPR curve of the Sioux Falls data. RectCOR runs with , 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).
| (BPR) | ||||
|---|---|---|---|---|
| Regret of RectCOR, | 216 10 | 661 118 | 5,127 1,907 | 14,720 3,894 |
| Regret of greedy | 233 13 | 635 109 | 5,087 1,919 | 14,824 3,902 |
| Rectangle's bonus relative to the ellipse's | 13.0 | 12.6 | 11.2 | 10.5 |
[Table 4. Regret on Sioux Falls under nonlinear costs (10,000 rounds, mean 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 of the way there (: no response; : 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 . 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 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 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 | ||||
|---|---|---|---|---|
| 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 (; mean of 10 seeds; ). 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 ) 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 ). 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 ). The excitation is not affected: the factor 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.
| Point | Revised PDF |
|---|---|
| Radius scale | App. E.4; Table 4 |
| 1. Predictable background flow | Sec. 5 (Figure 3); App. E.6 (Figure 13) |
| 2. Data from non-platform users | App. E.8 (Figure 17b) |
| 3. Platform share | App. E.8 (Figure 17a) |
| Q1. Random perturbation | App. E.6 (Figure 14) |
| Q2. Nonlinear costs | App. E.5 (Figure 12) |
| Q3. Adaptive background users | App. 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.
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) 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\*→0.
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 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 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, 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.
[Table 1. Regret on Sioux Falls by the share of edges with travel-time reports from background users (T=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)