Robust Learning for Congestion-Aware Routing
Authors: Sreenivas Gollapudi
Kostas Kollias
Benjamin Plaut
Ameya Velingker
Venue:  (2021)
Keywords: routing algorithms
adversarial learning
congestion functions

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) + \eta_e^t$, where $x_e^t$ is the flow on edge $e$ at time $t$, $f_e$ is the congestion function, and $\eta_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 $\tilde{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| \log t)$. We also validate our algorithm empirically using graphs from New York City road networks.

Under review as a conference paper at ICLR 2021
ROBUST LEARNING FOR CONGESTION-AWARE ROUT- ING
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the problem of routing users through network with unknown con- gestion functions over an infinite time horizon. On each time step t, the algorithm receives a routing request and must select valid path. For each edge in the se- lected path, the algorithm incurs a cost cf Se (xx') + n where x is the flow on edge at time fe is the congestion function, and nz is noise sample drawn from an unknown distribution. The algorithm observes c and can use this observation in future routing decisions. The routing requests are supplied adversarially.
We present an algorithm with cumulative regret ((E))))/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/3) and time complexity O(E) log t). We also validate our algorithm empirically using graphs from New York City road networks.
INTRODUCTION
Modern navigation applications such Google Maps and Apple Maps critical tools in large scale mobility solutions that route billions users from their source to their destination. In order to be effective, the application should be able accurately estimate the time required traverse each road segment (edge) along the user route in the road network (graph): we call this the cost of the edge. In general, the cost of an edge also depends on the current traffic level (the flow) on the edge. Furthermore, costs may scale differently on different edges: highway can tolerate more traffic than small residential street. We model this using congestion functions that map traffic flows to edge costs.
Usually, cost information is not readily available to the routing engine and can only be inferred indirectly. For example, this can be done using location pings from vehicles, or with loop detectors that record when vehicles cross a particular marker. All realistic methods measuring the cost of an edge (such as those above) require the presence of a vehicle that reports this information back to the routing platform. In this paper, we assume that whenever a vehicle traverses an edge, we observe the time spent the edge. We can then use this observation in future routing decisions. This induces a natural exploratio/cexploitatin trade-off: we may wish to send vehicles on underexplored routes, even if those routes currently seem suboptimal.
In this paper, we propose a learning model for congestion- aware routing, and present an algorithm which seeks to minimize the total driving time across all vehicles. Our algorithm applies arbitrary networks and arbitrary (Lipschitz-continnuus)) congestion functions, even when observations are noisy. The algorithm is also robust to changes in traffic conditions in strong sense: show that even when request endpoints are chosen adversarially and even when traffic congestion on the edges updated adversarially between requests, our algorithm learns an optimal routing policy.
1.1 MODEL
Consider a directed graph (V. E). Each edge e has a deterministic and fixed (but unknown) conges- tion function fe R20 Rzo. We assume each fe is L-Lipschitz continuous and nondecreasing, with L known. For simplicity, we also assume that f0) = 0 for all e E (if not, we can simply translate and extend the function appropriately).

---

Under review as a conference paper at ICLR 2021
We consider infinite horizon of time steps, starting from t 0. At each time t, An adversary tells us the current amount flow on each edge, and the source and destination of the new Let z be the flow edge time and let P. be the set of paths between the source and destination for the time 1 arrival. Let me = m xe We must choose how to route the car, i.e., choice of Pt, incur cost based the flow and the
arrives.
must select a path pt P.. Based congestion functions on the edges in our chosen path:
Ct = Σ (e(2
PEP
For each Pt. we observe c² fe( + n/e where vī is a random variable with expectation O. The distribution of ne is unknown, and can vary between edges and time steps. The distributions can be correlated across edges, long as for given edge, all the individual samples (i.e., me ...). are independent. We assume that there exists 3 such that n' [-3/2, 8/2] for all edges and times and that / (or an upper bound on 3) known.
The optimal cost at time /. is
G
min El(('))
PEP:
PEP
so the regret of our algorithm over the first time steps is
R₂ Σ
where the expectation is over the randomness in the noise samples. Note also that do not include the noise we observe in the objective function, since the noise has expectation
Any algorithm with sublinear regret can be said learn optimal routing policy: if R2 o(t), then Efc; - <f) must shrink as / goes to infinity, i.e., the difference between our algorithm's 's cost and the optimal cost must go to 0 on average." In this paper, we give an algorithm with regret ((1255).
1.2 OUR CONTRIBUTION
Our main result the following theorem: Theorem 1.1.
The expected regret of Algorithm I after t time steps is
R, = 0 (2/3
log man (B (B logt + x )lmast))
The space complexity and time complexity on time step I are 2( log sman) and O (IEl(lg 1+
log log at ) (P((E),IV1)) respectively.
VV) denotes the time complexity of computing the shortest path between two vertices in graph with nonnegative weights. For example, this can be done by Dijkstra's 's algorithm in time O V log V).
Here SP( SP(E), El.
We also validate our algorithm's performance using graphs from New York City road networks.
1.3 RELATED WORK
Comparison with multi-armed bandits. Perhaps the simplest model of exploration vs exploita- tion the classical mulli-armed bandit (MAB) problem (Slivkins, 2019). A MAB instance consists of n arms, each with an unknown but fixed distribution. At each time step, the algorithm selects an arm and observes reward drawn randomly from that arm't 's distribution. Several algorithms ob- taining regret Ö(v)) are known, and this is also known to be the best possible, up to logarithmic factors.
Note that Efce- cf) may not monotonically decrease: sublinear regret algorithm still incur large errors sporadically, long the the frequency of the large errors goes
2

---

Under review as a conference paper at ICLR 2021
Our routing model generalizes the MAB problem. In particular, when the graph consists of n parallel edges, the congestion functions are constant, and each edge has a single fixed noise distribution, our model reduces to the MAB problem: each edge is arm, and the reward distribution for each edge is (the negative of) the congestion constant plus the noise distribution. Our model can be thought of extending the MAB problem to the case where (1) each reward distribution has parameter (in our case, the flow), and (2) the arms are edges in an arbitrary graph and their usage is constrained according to paths in the graph. We believe that routing is the most natural application of this model, but there could be other applications as well.
Since our problem is strictly harder than the MAB problem, we know that regret of /V) is impossible. We conjecture that even regret ((vi) is impossible for our problem, but leave this as an open question.
Comparison with other routing work. Our work is also related to the body of literature on short- est paths under uncertainty, in which it is typically assumed that edge lengths follow known inde- pendent distributions. A canonical problem is to find an s-1 path whose length is below a threshold L with highest probability. When the edge length distributions are Gaussian, Nikolova et al. (2006) present quasi-polynonial time algorithm for this problem via connections to quasi-convex maxi- mization. A related probing problem is the Canadian Traveler Problem (Nikolova & Karger, 2008; Papadimitriou & Yannakakis, 1991), where the length of an edge is revealed when we reach one of its
and the goal is to minimize the expected cost. There for this problem, except under special assumptions such as no backtracking (Bnaya et al., 2009).
efficient algorithms known
Awerbuch & Kleinberg (2004) study conceptually similar adaptive routing problem. In their ver- sion, there is no noise in the observations, but the algorithm observes only the total cost of the path, and not the cost of each individual edge. Their model also does not have the same notion of a parametrized congestion function. Although their model is technically distinct from ours, it is noteworthy that they also obtain a regret bound of ( A number of subsequent works have also sought to apply bandit algorithms to shortest path selection problems in the domain of network signal routing (Chen & Ji, 2005; György et al., 2007; Liu & Zhao, 2012; Zou et al., 2014; Talebi et al., 2018). Moreover, there is long line of other works broadly dealing with regret minimization in Internet routing and congestion control settings (Dong et al., 2015; 201 8; Jiang et al., 2016; 2017; Talebi et al., 2018).
Similar works apply bandit algorithms to shortest path selection have also been applied to traffic route planning (Chorus, 2010; de Oliveira Ramos et al., 2017). However, these works differ from ours in that they do not consider the more general congestion functions that we consider in our model. A more recent work (Zhou et al., 2019) considers a similar routing problem, labeled the Multi-Armes Bandit On-Time Arrival Problem. In this setting, regret is quantified in terms of on- time arrival reliability. and the arms are joint route and departure times. Kveton et al. (2014) also study (among other applications) a routing setting in the context of matroid bandits, but this work also assumes static edge costs and does not factor in congestion.
Routing in the presence of congestion functions has been studied in the context of selfish routing Roughgarden & Tardos (2002) and in the atomic congestion games setting Awerbuch et al. (2005); Christodoulou & Koutsoupias (2005). The difference from our setting is that the congestion games model and selfish routing models assume drivers have full information about the costs in the network and route themselves on an optimal path. In our setting costs are learned as time progresses and there is a centralized routing control as given by navigation applications.
DESCRIPTION OF THE ALGORITHM
In this section, we define and give intuition for our algorithm for learning an optimal routing policy.
2.1 INTUITION BEHHIND THE ALGORITIM
On each step. the algorithm uses past observations to form an estimate for the cost of each edge at the current flow, i.c., an estimate for fe(z.). It then selects the shortest path according to these estimated costs.
3

---

which fits our Under review as a conference paper at ICLR 2021
The heart of the algorithm is the cost estimation scheme. There are two sources of error in this estimation: we may not have observed this exact flow before (type error), and noise (type 2 error). For type 1 enror, suppose all the observations we use are based on flows y such that ly - æ'1 S E. Then Lipschitz, continuity implies that (fe(y) - [a(rr) S &T, and so if is small, this aspect of our estimation should be accurate.
However, we do not actually observe fe(::: instead, we observe fe(y) + ?z. where Fy is a random noise term with expectation O. Even if we have observed the exact flow x= before, this noise will prevent us from having a perfect estimate. However, the more observations we use to form our estimate, the less impact the noise has: we can use Hoeffding's Inequality to show that EE Vyl goes to O quickly the number of observations grows, and thus our type 2 error shrinks. But as we increase the number of observed flows that we use (for a fixed time step), we also (in general) increase the maximum distance max, ly x Concretely, if k(E,z) is the number of observations based on flows within & of z, then k(E, xx) is weakly increasing with E. This is diametrically opposed to our plan for the type error.
In order for the average error to approach 0 as increases, we will have to carefully manage this tradeoff. We will need to ensure that the number of observations we use for estimation tends to infinity, but also that the maximum distance tends to O. Intuitively, this should be possible: if observations are somewhat uniformly distributed across edges and across the flow spectrum, then we should have (tt) observations per edge and (treating E| as a constant here). Setting to be something like (((-1/2) would lead to O @(Vi/s observations being used for each estimation with maximum distance of requirements.
observations on every interval of size
Observations are of course not guaranteed to be uniform, and can even be adversarial. For example, suppose we have observed many flows less than 1 on some edge e, but no flows above 1. When estimating the cost of a flow less than 1, are in good shape (if those observations are uniformly distributed, say). But suppose we are asked to estimate the cost for flow 2: we may incur a large estimation error, since we have no information about that portion of the flow spectrum.
But our lack of information also implies that so far we have not incurred any error in that part of the flow spectrum, since we have never used it! The more edge (i.e., our chosen path used that edge at flow in that range), the more error we incur, but the more we learn. Thus we will need an analysis that is decomposable across edges and across the flow spectrum: for each interval I, we need to bound our cumulative error over all estimation queries that fall within that interval as a function of the length of the interval and the number of such queries.
part of the flow spectrum
given
There is one more complicating factor: what if we consistently overestimate the cost of particular flow, so that we never use it? Then we may repeatedly incur a large error from that flow, without ever learning about it. For this reason, we will want to ensure that with high likelihood, all of our estimates are underestimates: this will allow us to bound the regret on a given time step in terms of the estimation error only edges in the path that we used.
2.2 OUR COST ESTIMATION SCHEME
The cost estimation works roughly as follows. The algorithm maintains "bucketing" system for each edge, inspired by hashtables. The interval [0, xtmmael is partitioned into a set of intervals, with each interval being a "bucket". Whenever we observe new flow, we identify which bucket that flow falls into, and use all the observations in that bucket to estimate the cost. (We also subtract a term proportional
Vlog in order to ensure that we get an underestimate with high probability; this is similar to the Upper Confidence Bound algorithm for multi-armed bandits.) We then observe the resulting cost for this flow (for this edge), and insert it into the bucket. If we observe flow that falls outside of our bucketing system, we create a new depth 0 bucket so that the observed flow falls into our new bucket.
If the number of elements in the bucket surpasses certain threshold, we split it into two new buckets (whose associated intervals are equal length). The threshold depends on the depth (i.e., how many times one of its ancestors denote it by h(m). Our analysis will be "decomposable" across buckets: we will bound the total error any single bucket of depth can contribute over the course of its lifetime.
split). We denote the "lifetime" of a bucket at depth by and
4

---

Under review as a conference paper at ICLR 2021
Let by be the bucket we used for estimating the cost of edge time The smaller the interval associated with this ,y, the smaller the error of type I: our estimation only uses observed flows within this interval, and the interval has length E, then the type I error is most eL, since our target flow oe is also in the interval. This incentivizes us to make ((m) small, so that we can more quickly get to buckets with small interval lengths. If only cared about type error (i.e., if there were no noise) choosing (m) = 1 would be optimal.
On the other hand, the more observations stored in b9 the smaller type 2 error. This incentivizes us to make h(m) large, so that each bucket contains a large number of observations for larger portion of its lifetime. If we only cared about type error (i.e., if fe were constant), choosing h(m) 00 would be optimal. This is exactly the tradeoff we discussed in Section 2.1. Eventually, h(m) = 2 will give us the best regret bound.
2.3 DEFINING THE ALGORITHM
Algorithm I provides pseudocode for our algorithm. We use Be to denote the entire bucketing system for edge e. We treat B, as a set, whose elements are "buckets". Each bucket b supports the following operations:
bb] - returns the number of (flow, cost) pairs stored in b
dom (b) -> returns the interval [w, =] S [0, K] associated with
dept (bb) + returns the depth of bucket b
estimate (b) > returns the cost estimate based on the current observations stored in
create(m, [w, z]) -> returns new empty bucket b with dom(b) = [wr, =] and depth(() m
INSERT(b, Cy)) -> inserts the flow y/ and its associated observed cost cy into b
The first four operations will simply be numerical fields stored in b. We also assume that the create operation takes constant time and space, and that the aforementioned four fields are initialized ap- propriately restimate()) should be 0). However, we will need implement INSERT ourselves in order to ensure that it is done in an efficient fashion (hence the differing font). In general, we will reserve the variables w, z for dom(b), y for arbitrary elements of b, and z for the proposed flow on the current time step.
To limit space usage, we will not actually "store" each relevant observation in the bucket; instead, we will simply incorporate it into the estimate field that we store. However, in the analysis, it will be useful to use "y E 5" denote that particular observation (y, Cy) has been used in that bucket. For each E b, let fy denote the noise sample associated with this observation. Note that My is not known to the algorithm; we will simply use this notation our analysis. Also, let len(dom(b)) denote the length of the domain, i.e., w if dom(b) = [w,,
We can think of the bucketing system in terms of binary trees. Each bucket of depth is a "root", and whenever we split bucket, create two "children". Thus B, is essentially a forest of binary trees, where each node represents a bucket. Any bucket E Be has exactly one ancestor of depth O.
EXPERIMENTS
In this section, we empirically validate the algorithm's performance on graphs from New York City road networks. We first describe the methodology, and then reflect on the results.
3.1 METHODOLOGY
We used two different graphs, corresponding to different regions within New York City. Graph consisted of 303 vertices and 657 edges, and Graph 2 consisted of 429 vertices and 1204 PiggssCongestionn functions with domain [o, 1] were generated randomly for each run of the al- gorithm, with each congestion function consisting of three pieces of slope chosen uniformly from [0, 1]. Uniform noise distributions were used for all runs, with varying values of B. The algorithm was initialized with = and a = 2.32. On each time step, the following steps were performed:
1. Independently sample uniformly random flow ot in [0, for each edge e.
5

---

Under review as a conference paper at ICLR 2021
Algorithm Algorithm for learning optimal social routing policy.
for each E E do function ROUTINGALCCRRITIMEE... h)
2:
3: Bg + fcreate (0, [0, 1})} Start with single bucket of depth and constant length
4:
for each E No do
5:
ze - proposee flow on edge for each e E do
6:
7:
= + ESTIMAATEDDGCCOSTOO. Be, a))
8:
Pt < arg min Eeep "
9: selectRoute(pr), observe cost de Ve E Pt for each e E p4 do
10:
11:
UPDATEBUCKETS((1; Bey c.
1: function ESTIMAATEEDGECOSTTO B, L, a.t)
2: if 3b E B s.t. z dom(b) and b6] > then
3:
return max (0, eesesmmtateii / In
4: else
5:
return O
1: function UPDATEBUCKETSEE Cy. h)
2: if 36 B s.t. E dom(b) then
Insert our observation into the corresponding bucket
3: INSERT(b, (v, Gy))
4: m f- dept.h())
5:
if b (m) then
Split the bucket if it big
6:
W =| + dom(b)
7:
b1 create(m + 1, [w, 2
8:
b2 < create(m + 1, w+= 2])
9:
INSERT((I, (g.,y)) b Insert the observation into new buckets so they aren't empty.
10:
INSERT( (3) Gy))
P Type error still proportional to the domain lengths.
11:
B. (Be U (bb)
else
This flow does not fall into any bucket: create new depth bucket Vmaa + max (UBEB, dom(b))
13:
14:
b create (0, [ymax: 2xl)
15:
B. +- B. U {b}
1: function INSERT(b. (y,
2:
(w, 2] dom(b)
3: if then
y & dom(b) is possible if we created b on this time step
4:
My = Cy
5: else
6:
My = cy L(y w)
est mb) + |6| estimate(b)
7:
D This is running average of {uy E b)
|b| +1
8:
bb +1
2. Independently sample uniformly random noise term n/. E 81-8/2,8/21 for each edge
3. Independently sample a uniformly random source and destination from the graph.
4. Compute the path chosen Pt chosen by our algorithm.
5. Compute 6: c- Eeep, Sa ( minper P. Ecep fo(x1) and record the cumulative regret
R.
Each run was characterized by the following parameters:
Time horizon (either 100,000 or 1,000,000)
2. The graph used (Graph Graph 2)

---

Under review as a conference paper at ICLR 2021
3.
The noise parameter B E 00,.01..02.00,.11,,2
Figure/ shows the results of all runs.
3.2 RESULTS
All runs of the algorithm display the general behavior we would hope to see: concavity of the cumulative regret curve. Also expected, higher noise levels lead to both larger absolute regret, and weaker concavity: learning takes longer. Most the runs display substantial concavity within 100,000 time steps, but some the 3 .5 runs (on both graphs) require closer to 200,000 steps in order for the concavity to clearly manifest.
With regards to absolute regret, 3 has dramatic effect. On the extremes, the total regret for after 1, 1,000,000 time steps is less than 5,000 for Graph 1 and less than 9,000 for Graph 2. (The regret for Graph tends to larger, due the graph being larger.) However, for 100,000 time steps is already more than 12,000 and 20,000 for Graph and Graph 2, respectively. If we look the average regret for 3 0 over 1,000,000 time steps, we get <.005 and <.009 for Graphs and 2. respectively. Since the expected cost of each edge on given time step is .25 .5,
.5, the regret after
(expected flow is .5, expected slope is .5), we view this as quite good. In contrast, for the average regret over 1,000,000 time steps is >> .48 and >.88 for Graphs 1 and 2 respectively. Relative the average edge cost of 22,, we view this as quite poor. This behavior again matches expectations.
Finally, we note that there are many other experimental parameters that we have not included in these plots. For example: non-i.i.d flows, non-i.i.d. sources and destinations, non-i.i.d. congestion functions, congestion functions with different numbers of pieces, congestion functions with different Lipschitz constants, other noise distributions, correlated noise, and many more. We have indeed tested many of these, but due to space constraints, there a limit to the number of plots we can include in the paper. We assure the reader that have yet find parameter combination that causes unexpected behavior from the algorithm.
4 CONCLUSION
In this paper, we presented an algorithm which learns an optimal routing policy for any graph, any (Lipschitz continuous) congestion functions, and any (bounded) noise distribution, and adversarial routing requests (i.e., source, destination, and the current flow on each edge). Our algorithm has cumulative regret ((LE)(/33.
There are many interesting directions for future work. The first relates to the dependence on in the regret bound. Since our problem generalizes the multi-armed bandit problem, we immediately inherit a ((vl) lower bound. However, that still leaves substantial room to improve the dependence on It would also be interesting improve the dependence case assumptions in this paper that are perhaps overly pessimistic: for example, neighboring edges may have correlated congestion functions, and flows do not change arbitrarily between time steps.
E/] We have made several worst-
On the empirical side, we evaluated our algorithm using real-world graphs, but synthetic congestion functions. Future experiments could use real data for the congestion functions as well: either by fit- ting a congestion function to the data, or by randomly sampling data points to simulate a congestion function.
"Wit regards to the chosen range of 3 values, note that the expected maximum cost each edge is 5. since the domain of each fe is [0. 1] and the expected slope of each piece is 55. Thus in some sense, = .5 represents "as much noise signal", / represents "2/5 as much noise signal",, and on.

---

Under review as a conference paper at ICLR 2021
Graph
Graph
Cumulative regret.
1000
11:00
1000
Comutaativ regret
100K
1000
5000
3000
Comulatiiv regret
100
30001
7221
Cummlative reggett
4000
1b00
2000
Time step
Time step
Figure 1: the experimental performance of Algorithm 1. The x-axis in each plots is the time step, and the y-axis is the cumulative regret. There are eight plots, each consisting of four curves, each with different noise levels. Each curve is single run of the algorithm. The upper four plots have time horizons of 100,000, and the bottom four have time horizons of 1,000,000, All plots in the left column use Graph and all plots in the right column use Graph 2. Finally, since we tested seven values of 3, we separated them into two different plots to avoid overcrowding single plot. For example, the top two plots in the left column have the same time horizon of 100,000 and both use Graph 1. The top left plot contains the lower noise levels (0, ,01, .02, .05), and the second-from- the-top left contains the higher noise levels (.05. 11, 22, .5). Note that / = is included in both to allow visual comparison between the plots.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Baruch Awerbuch and Robert D Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 45-53, 2004.
Baruch Awerbuch, Yossi Azar, and Amir Epstein. The price of routing unsplittable flow, In Pro- ceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 57-66, 2005.
Zahy Bnaya, Ariel Felner, and Solomon Eyal Shimony. Canadian traveler problem with remote sensing. In IJCAI 2009, 2009.
Anthony Chen and Zhaowang Ji. Path finding under uncertainty. Journal of Advanced Transporta- lion, 39(1):19-37, 2005.
Caspar Chorus. Regret theory-based route choices and traffic equilibria. Transportmetrica, 8, 01 2010. doi:
George Christodoulou and Elias Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 67-73, 2005.
Gabriel de Oliveira Ramos, Bruno Castro da Silva, and Ana L. C. Bazzan. Learning to minimise regret in route choice. In Kate Larson, Michael Winikoff, Sanmay Das, and Edmund H. Dur- fee (eds.). Proceedings of the 16th Conference Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8- 12. 2017, pp. 846-855. ACM, 2017.
Mo Dong, Qingxi Li, Doron Zarchy, Philip Brighten Godfrey, and Michael Schapira. PCC: re- architecting congestion control for consistent high performance. In 12th USENIX Symposium on Networked Systems Design and Implementation, NSDI 15, Oakland, CA, USA, May 4-6, 2015, pp. 395-399559 USENIX Association, 2015.
Mo Dong, Tong Meng, Doron Zarchy, Engin Arslan, Yossi Gilad, Brighten Godfrey, and Michael Schapira. PCC vivace: Online-learning congestion control. In Sujata Banerjee and Srinivasan Se- shan (eds.), 15th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2018, Renton, WA, USA, April 9-11, 2018, pp. 343-356. USENIX Association, 2018
András György, Tamás Linder, Gábor Lugosi, and György Ottucsák. The on-line shortest path problem under partial monitoring. Mach. Learn. Res., 8:2369 22239922403,, 2007.
Junchen Jiang, Rajdeep Das, Ganesh Ananthanarayanan, Philip A. Chou, Venkat N. Padmanabhan, Vyas Sekar, Esbjorn Dominique, Marcin Goliszewski, Dalibor Kukoleca, Renat Vafin, and Hui Zhang. Via: Improving internet telephony call quality using predictive relay selection. In Pro- ceedings of the ACM SIGCOMM 2016 Conference, Florianopolis, Brazil, August 22-26, 2016, pp. 286-299 2016.
Junchen Jiang, Shijie Sun, Vyas Sekar, and Hui Zhang. Pytheas: Enabling data-driven quality of experience optimization using group-based
In Aditya Akella and Jon Howell (eds.), 14th USENIX Symposium Networked Systems Design and Implementation, NSDI 2017, Boston, MA, USA, March 27-29, 2017, pp. 393-406. USENIX Association, 2017.
Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. Matroid bandits: Fast combinatorial optimization with learning. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI 2014. Quebec City, Quebec, Canada, July 23-27, 2014, pp. 420-429, 429, 2014.
Keqin Liu and Qing Zhao. Adaptive shortest-pate routing under unknown and stochastically varying link states. In 10th International Symposium Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), Paderborn, Germany, May 14-18, 2012, pp. 232-237 IEEE, 2012.

---

Under review as a conference paper at ICLR 2021
Evdokia Nikolova and David R. Karger. Route planning under uncertainty: The canadian traveller problem. Dieter Fox and Carla P. Gomes (eds.), Proceedings of the Twenty- Third AAAI Confer- Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, pp. 969-974.
AAAI Press, 2008
Evdokia Nikolova, Jonathan A. Kelner, Matthew Brand, and Michael Mitzemmacher. Stochastic shortest paths via quasi-convex maximization. Yossi Azar and Thomas Erlebach (eds.), Al- gorithms- ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September / 11-13, 2006, Proceedings, volume 4168 of Lecture Notes in Computer Science, pp. 552-563. Springer, 2006.
Christos H. Papadimitriou and Mihalis Yannakakis. Shortest paths without map. Theoretical Computer Science, 84(1):127- - 150, 1991.
Tim Roughgarden and Éva Tardos. How bad is selfish routing? J. A.M, 49(2): 2002.
Aleksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint arXiv: 2019.
Mohammad Sadegh Talebi, Zhenhua Zou, Richard Combes, Alexandre Proutière, and Mikael Jo- hansson. Stochastic online shortest path routing: The value of feedback. IEEE Trans. Autom, Control., (119):955-99000 2018. doi: 10. 10.10099AA.2221.22777744. URL https: /ttp:::///ooorooo/ 10. 10.1109/IACE 2017 200.11..777444 2747409.
Jinkai Zhou, Xuebo Lai, and Joseph Chow. Multi-armed bandit on-time arrival algorithms for se- quential reliable route selection under uncertainty. Transportation Research Record Journal of the Transportation Research Board, 2673:673 682, 04 2019. doi: 10.1177/0361 19989611111111 19850457.
Zhenhua Zou, Alexandre Proutière, and Mikael Johansson. Online shortest path routing: The value of information. American Control Conference, ACC 2014, Portland, OR, USA, June 4-6, 2014, pp. 2142-2147. IEEE, 2014.
A PROOF OF THEOREM 1.1
In this section, we prove our main theorem:
Theorem 1.1. The expected regret of Algorithm 1 after time steps is
R 0 (1/33. log st s'ma ( Vlog + xmmax Ii)
and O (FE((1o 1+ The space complexity and time complexity on time step are 1( log or log log x'maz) + (P((E),IVI)) respectively.
We restate the algorithm below for the reader's 's convenience.
Our first lemma upper bounds the distance between two flows associated with the same bucket.
Lemma A.1. Consider arbitrary edge e and bucket b B let (x.
Cx) (x.Cx) E b, and let y don(b)
(but not necessarily E b). If m depth(b), then fr yl S x! x /2m /2m-1
Proof. Let 1' be the unique depth 0 ancestor b. If b has depth m, then dom(b) must have length exactly len (om(b)))m since the domain length is halved whenever the depth is incremented. Since len(dcm(b')) S x we have len(cio(b)) & xf xmaan/2"
If E dom(b), then |r yl xtnaz//2 12Th and we done. If not, then must have been inserted on the time step that b was created. Let 1/" be the parent of b. In this case, x E dom(b"). By construction, dom(b) dom(t/), ), we have F, y E dom(t"). Finally, since D' has depth 1. /m
len(dom(b"))
jæ yl S / m
Lemma A.2 a standard concentration equality due to Hoeffding. Lemma A.3 is essentially a restatement of Hoeffding's Lemma for our setting.
10

---

Under review as a conference paper at ICLR 2021
Algorithm Algorithm for learning optimal social routing policy.
for each E E do function ROUTINGALLCRRITIMME... h)
2:
3: Bg + fcreate (0, [0, 1})} Start with single bucket of depth and constant length
4:
for each E No do
5:
ze - proposee flow on edge for each e E do
6:
7:
= + ESTIMAATEDDGCCOSTOO. Be, a))
8:
Pt < arg min Eeep "
9: selectRoute(pr), observe cost de Ve E Pt for each e E p4 do
10:
11:
UPDATEBUCKETS((1; Bey c. h)
1: function ESTIMAATEEDGECOSTTE B, a.t)
2: if 3b E B s.t. z dom(b) and b6] > then
3:
return max (0, eesesmmtateii / In
4: else
5:
return O
1: function UPDATEBUCKETSCC Cy. h)
2: if 36 B s.t. E dom(b) then
Insert our observation into the corresponding bucket
3: INSERT(b, (v, Gy))
4: m f- dept.h())
5:
if b (m) then
Split the bucket if it big
6:
W =| + dom(b)
7:
b1 create(m + 1, [w, 2
8:
b2 < create(m + 1, w+= 2])
9:
INSERT((I, (g.yy)) b Insert the observation into new buckets so they aren't empty.
10:
INSERT( (z) Gy))
P Type error still proportional to the domain lengths.
11:
B. - (Be U (bb)
else
This flow does not fall into any bucket: create new depth bucket Vmaa + max (UBEB, dom(b))
13:
14:
b create (0, [ymax: 2x/))
15:
B. +- B. U (b)
1: function INSERT(b. (J,
2:
(w, 2] dom(b)
3: if then
y & dom(b) is possible if we created b on this time step
4:
My = Cy
5: else
6:
My = cy L(y w)
est 1 mmtiebb + |b| estimate(b) u2y
7:
D This is running average of {uy E b)
|b| +1
8:
bb b
+1
Lemma A.2 (Hoeffding's Inequality). Let XI...., Xn be independent random variables each sup-
ported on an interval of length > and let X Ei_ X, Then for any 0,
Pr||X E|X]| E) S exp (-
2nE2
32
Lemma A.3. Fix an edge and bucket b B With probability at least
In 5-5-1
nl
2
11

---

Under review as a conference paper at ICLR 2021
Proof. If B 0, the claim is trivially true. Otherwise, since Emmyl for a given edge, Hoeffding's 's Inequality gives us
0, and all my are independent
In 8
182 2|6]
2|b| ga
>
V
S exp
2/6
E
as required.
We will now start the process of bounding the costs incurred by our algorithm. Moving forward, we will need separately handle the time steps where x does not fall into any bucket we have, and we must create a new depth 0 bucket (on line 14 of UPDATEBUCKETS) Let Te be the set of time steps t where (I) E Pt. (2),
& such that E Pr (i.e., this is not the first we are using this edge), and (3) we do not create new depth O bucket. The reader can think of Te as the set of time steps when edge e is used a "normal" way.
Throughout the analysis, for each E E and time I, let by denote the bucket that is used on line 3 of ESTTMATEEDGFCOST such bucket exists. For each / E Te, we are guaranteed that by exists, since Condition 3 above ensures that there exists E Bg with x com(6), and Condition ensures that (6] > O. Throughout the proof, we will use 69 to denote the number of observations in the bucket on that time step, before inserting the new element (if one is inserted).
Also, for each e E E and time t, let (t) be the indicator variable that [6g EvErt Mol S
V - 10 = B 1 In ta/03, (If by does not exist, let Ce (1) 1). Note that by Lemma A.3, (t) 1] 1-
The next lemma states that as long as (L) = 1, our algorithm's estimate uf will always be an underestimate of the true cost Se (x:2)-
Lemma A.4. Fix time and edge (et) = 1, then fe(x)) 2 vlc
Proof. If E = O, then trivially ut S fe(x)). Thus assume n > 0. This implies E Te, and so by exists. For each y b,. define my as in the INSERT function in Algorithm 1, and let [w, z] dom(b()) For brevity, let x x Note that 2 w and thus fc (z) 2 fe(w). Also recall that Cy fe( + nl by definition. We first claim that fe(x) Z uy Fl for all y b
Case 1: y. Then > y, we have My Fly Cy fl = fv( S fx), as required.
Case 2: y 2 w. Then Uy fly = Cy 7 L w) fe(y) L w). Because fe L-Lipschitz,
we have fy) I (w( + L(u - w) so
Uy - ny = fy) L(y w)
s fe (w) + L w) L(y w)
$ fa (x)
Therefore
fe(x) 2
(uy
ny)
16
yEb
1
Σ ny
Uly
16
69
yED
3ED
1
Σ
Σ fy
"y
|
yE4
Since (t) 1 by assumption, we get
[e(22)
Σ my
= - Vibgi-1 1n l
Since ut > 0, we have ut estiimatee isttmtt)())))
bb 1n Thus fa(x!) u required. n
12

---

Under review as a conference paper at ICLR 2021
Lemma A.5 states that if Te and (t) 1, then estimate ut also shouldn't be too much more than fe (x
Lemma A.S. Fix a time E Te and edge and let m = depth(()). 15))(1) 1, then
Tn 2
Ie(x))) ut
Proof. As before, for each y E by define uy in INSERT, let [wo dom(b)), and let = xf for brevity. We first claim that fe(r) I My fl + L(x - y) for all E by. Since x 2 w and fa is L-Lipschitz, we have fe(x)= S fw( + L(x w)
Case 1: y 2 w. Then fe(w) _ fe(y) by monotonicity, so
fx( S fe(y) + L(x w)
Cy 12 L(r y) + Lyy w)
= Vy Bl + L iz w)
S My Bly + 2 x maaz
where the last step follows from Lemma A.I.
Case 2: w >> y. Then fe (w) & fe(w) + L(w - y),
[e(x) - [e( + L(w y) + 1(x w)
= Cy - fly + L(r - y!)
I Ul My + L(I y)
I Bly Fy 2 x man L
again using Lemma A.1 on the last step. Therefore
lc(x)
S
(ug
+
2 my x I.)
D
DE
= 2 mm x
man +
6C
My
b
yE
yED
<
m 1 mmao L + testimatellss +
Σ DCb
Th +
b
In
bo
Inta
Since u = max(0, (et.(()sssmmmatelle Int we have astimated V
Int S vz-
Also, 15
Eve Vyl S [bg -I since Co(1) = by assumption. Therefore
fe(x) S u + 2 21 m maa
6
In t
WEB!
< u + 21 max
L + 2/ 16
In t
The next lemma is simple bound the maximum flows time steps when we create new depth O bucket. This will be needed later to bound the error on those time steps.
Lemma A.6. Fix an edge E E and time step > O. Let to. and including time on which new depth 0 bucket created in B. (where to 0). Then < + log rt . Furthermore, E Lte S. 2x
tx be the time steps up
Thii means that is actually not in dom(b)). This only happens if inserted into by on the time step when B), was created.
13

---

Under review as a conference paper at ICLR 2021
Proof. Assume to f1,- fi...... tk- Let ying max(Ube pro where Be denotes the set of buckets for edge e at the beginning of time step r. This is the maximum flow that falls into any bucket in Be at time Note that Vinaz Vinar for all & {t....., tx). Furthermore, for r E (11....,le J. we have ymnaz = 2x > ymaw Therefore for each i E (1,...,k)
V = 2x 2ymnaz
Thus for all j,j E {1, with i S 3o Vinax 20- In particular,
Vina > 2 Vmmaz 2
where yma = 1 is because we initialize Be with single bucket corresponding to the interval [0, 1]. We know that u 2xre S 2xmax 2 2x Therefore ! k log maas Finally,
&
Umaz
2
+++t1
k
2
2h-
1=1
1++1 Mmaz
2
2x
max
as required.
Lemma A.7 gives first bound the cumulative regret of the algorithm. This bound is quite complex, and will take substantial work later to show that this bound is in fact O(t/3).
Lemma A.7. Assume = 2.3 Then for all i, we have
E rr mas 2( 18)
L L 2depth + 2 2 In
R4
Σ
eEPr
Proof. We first prove a lower bound on B[c;]], the expected cost incurred by the optimal algorithm. By definition, minpeP, Leep fe(x(), ), so Lemma A.4, we have fe(x{) 2 ut with probability
at least 1 - a- For brevity, let 5 = / Since 2 O always, we have
E (1 5) min
Σn
peP,
Next, we prove upper bound on Elea], the expected cost incurred by our algorithm. Note that
B[cr] so(t)))
Σ fa(x))
Σ So(x²)
eEPs
eEPddET.
eÉpeLeT.
We will first handle the first term, and then the second term. Since Sa is I--Lipschitz and fc(0) = 0, we have sx) < ae x L. for all x I se sheas- Since xh S Emazz we have
fe(x!)) < xmma To as broad upper bound for all cases. If E Te, then Lemma A.5 implies that [e() S 1++22 2 211--pppa(b) mar 2 [b -
In la with probability at least Also recall that
Pt arg minp Eeep u by definition. Thus
Σ (a(x))
Σ
dx dxinna (1
(1- -0)(ub
2depth(b!) 2 In l
Fman
eEPddET.
L L
< 8) El b L + (1 8)
min
2t + (1-8) Σ
2depth(b_)-1 + 2 6
In t
peP.
eEp
PEPp
T To
< 8) Iman
8) min
Σ
4 2depth + +2v an
PEP
eEp
eEps
14

---

Under review as a conference paper at ICLR 2021
Next, for EeEpORET fe(xz)
we have
Σ fe(x))
E
maa
Iee E Pt
eÉpeteT.
eEPeteTT
Combining this with upper bound E[[;], we get
E f I
2 Tmar I. (depth(b!)
E|c - c1 & He E pr # TeHla man
+ 2 6
Inta
ta/
eEpt
Summing the second term gives us
E Faa L pa/82
E I max La²
E max
p2
S
|E|
maz
L
6
For the first term, further divide time steps Te into (I) time steps where create new depth 0 bucket, and (2) time steps where we use edge for the first time. For case (1), let Q. denote the set of these time steps. Recall that we only create depth 0 bucket when the current flow of does not fall into any bucket we already have. In particular, that implies it is the maximum flow we have seen this edge: formally, indicator variable which takes on value I if t is the first time that is used, and 0 otherwise. Since this happens most once per edge, we have E ze(r) S for all E. Therefore,
Qe implies x' x' Fa.max. For case (2), let 2e be the
(e Pr :r r TTe max
= L Σ 2 mar
1}})
L
Re:re Te:re@e)la"" L Σ
xy
e,man Σ 2e(r)
eEpr
L
Σ
Σ
D + L
xmax (r(r)
6EE rstirEQ.
eEEr=1
<
x + E
20
cEF rStrrEQ
L 2x
|E|ximast L (Lemma A.6)
eEE
EE x L + EE 1 L
El xt xmma L
Putting this all together, we get
E 1 maz LT
LngeL L 2dept
R₂ Elee c7] s 3 F2 1 max
L +
2 11 1n 1a
r= CEPr
El man
L(T 2 + 18)
zet amar 2depth(b!)-
Σ
+ 22/1vll-1 In
6
eEP:
as required.
Let St be the set of buckets associated with edge e that have existed up to and including time I, and let Ab(b) fr < p. and by = b) be the set of time steps that we used bucket b. We know
NNote that could have chosen any a > 2,8 and simply obtained different constant.
15

---

Under review as a conference paper at ICLR 2021
that every time edge (i.e., E Pt), exactly one bucket bz. Thus rewrite the bound from Lemma A.7 as
E 2 man L 2 12)
Σ
Σ
2depch(b)-T + 2V 69 In
Imas L
BESt rEA((b)
Note that we use |b;] instead of [6] in order denote the size of the bucket on time step specifically.
Let (b) = ErEA,()) (2) (21-dapth(b) xt m + 1 be the total regret incurred by bucket and let Re(e) = LBs
>obS: (b( be the total regret incurred by edge e. The rest of the proof is
devoted bounding (e):): after have done so, can simply this bound across all edges. We next give a brief proof of a standard inequality that will be useful to us.
Lemma A.8. For all n, E 2/TL
Proof. The proof is by induction n. The base case of n = 1 trivial so consider an arbitrary n and assume the claim holds for n 1. Then
Σ
1
1
71
i=1
2
+ +22n-
V + vn -
2 - vn + -1
=2
as required.
We will now bound the maximum regret a single bucket of depth m can contribute. Lemma A... Let b E St be a bucket with depth m. Then
x1 Fyma Lh(m)
Re(b) S 4 h(m) lnt
2
Proof. Substituting depth(b), Rb( is defined by / aina (b)
(b(b) S
+2 Σ V16 161-1
2m-1
rEA(())
Next, observe that [b) S h(m): [b] = 1 initially, and once [b] > h(m), we split it into two new buckets and never use it again. Thus we can rewrite the above bound over the number of elements in b:
[A,(b]]
Id maz L|)((b)] + 2v/n l0
(b) <
Σ
2m-1
Vi
f=1
h(m)
A maz I.((m)
+ 22
2m-1
Vi
xat maz I.(m)
+ 4 ((m) Inta In
(Lemma A.8)
2m
required.
Next, we will analyze a linear program which will be useful in bounding the total regret contributed by single edge.
16

---

Under review as a conference paper at ICLR 2021
Lemma A.10. Consider the following linear program, parameterized by t, and kt
max
Im 2km
(1)
ER
s.t.
2
2m
t
m=l
Im S 2 vm E [I,...,m)
Assume 0 S k < 2, and let (ai,..., kn) be an optimal solution, and suppose Im > Then for all i < 2
Proof. Suppose not, and let 8 min( xx2) > 0. Define new solution (Vi...., Un) by y/ = 24 z Vm = I'm 2im-J, and !// = =, for j E {i, m).
We first claim that y is feasible. We have ym 2 Zm - 2 0, and yE S x; + S 2'. Since yj = Iz
for j E mi, we have S xi S 2 for all j. Also, we have
Σ 2 j=1
Iz 221-3)
2 + [m
8
2 33
2,225-3
22m
[i,m)
= x;2 221
+ + Im
2mm
8
Σ
2,221-3
x 22-3
which must be at most t, since (#1..... zn) is assumed to be feasible. Finally, we claim that (y1,..., vn) has a better objective value. We have:
Σ 2 زj Σ 2 x. 2h + Vm
2km
r,2hi
Im 2km
82ki
82km
2hi +
+ Im
2km
2h'
kmm
2
22m
222 ki
2(2-k)m
Since and m > we have kyi 22mm))m positive. Therefore (y1,..., Vn) has a higher objective value, which contradicts the optimality of (II....,,,,) v.))
Thus the above expression is strictly
For now, are primarily interested in k 1. Let gt, n) denote the maximum value of Program for parameters t and n, with & 1. Lemma A. 10 implies that for a fixed t, n actually does not matter, assuming it is sufficiently large: the Σm=1 22m-3 33 I t constraint will be saturated by smaller values of m, so any additional variables will always have value O. Formally, for all t, there n4. Thus can simply take be large enough exists ne such that g(l, n4) = g(t,n) for all and write g(t) = g(l, nz). For example, n, = / suffices.
The next lemma bounds the total regret contributed each "tree", i.e., set of buckets that share depth 0 ancestor. Also, at this point we will substitute in h(m) = 22m
Lemma A.11. Fix edge and time t. Let S C St. be set of buckets which all have the same depth 0 ancestor. Then
Σ Ra(b) < (AvInta + L)g(()
BES
Proof. Let am denote the number of buckets b S of depth m. Letting h(m) 22m Lemma A.9 implies that
1t I Lh(m) (4vIn + 2x 2 mm
(b(b) < 4/h(m) in
2
17

---

Under review as a conference paper at ICLR 2021
Thus
Σ Re(b) & (4vin to + 20 L.) BE
Iim 2
m=0
We next claim that (e.....,Tm! feasible for Program 1. We know that Zm S 2 since within a single binary tree, there are at most 2n nodes of depth m. It remains to show that
t Em= 22m-3
Note that all buckets of depth at least come in pairs: spending h(m - 1) steps on a bucket of depth m creates two buckets of depth m. Thus the number of time steps we spent on buckets of depth
1 is exactly 2 h 1) 2 am 22m-32m Lm. Thus the total number of time steps is
bounded by
2 2m mam--a.m
2m
m=
required.
Therefore (.1,..., (m,) is feasible solution Program 1, and Eves R2( is at most (4vIn to + L)) times the objective value of Program for (21...., Fm)) Since the objective value for (11 (F1....,TT is most the optimal objective value g(t), have Eres (b) S (4vīn 2x (igazL)g(()
We are now ready bound the total regret contributed by single edge.
Lemma A.12. For all e, t, we have
Re(e) S (1+ log 2 s'maz (4vIn + 2x L)g(t)
Sg Proof. Let SI....,,, be and buckets in St have the same depth ancestor. (i.e., each St constitutes a single binary tree). By Lemma A.6, q s log of maa. Therefore
partition of St such that each St contains exactly one depth 0 bucket,
Re(e)
(b)
i=1 bES;
< Σ (4Vint + L) (Lemma A.11)
q(Avint + 2m Ltg
S (1 + log ( 14V 2x 20 L)g(()
as required.
We are almost done. One of our last remaining tasks is to bound g(t): the optimal objective value of Program 1.
Lemma A.13. For all I, we have g(() <
22/33
2 3
Proof. Fix a time t, and let (æ)..... Zn, be an optimal solution to Program for parameter t. Let
m the minimum integer so that Σ m
i=1 221 32 > Then there exists S m so that 2;; 2 oth-
erwise, Σm 22i-3 x; = Em 22 32d by assumption, which would imply that (a1,..., Ra) infeasible.
Since there exists < m so that Bi 24, Lemma A.10 implies that x; for all m. Therefore g(() = >i 2'x; Σm 2xx;
Dm 1 22
By definition of we have & 2ih 22i-32i D 23i-3 > 23m-9 Therefore
3m
log
18

---

Under review as a conference paper at ICLR 2021
log t -
m I log
logt1/8 /2/3 +
Therefore
- s(1)
2
1=1
2
22
log 1
4
22
.2/3
2
22/
required.
Our last lemma analyzes space and time complexity of our algorithm.
Lemma A.14. The space complexity and time complexity of Algorithm on time step t are O(EE)11/ log x'maz) and O (IE[(to log x xmmx)) (hortesstattaa(()))) respectively,
Proof. For the space complexity, note that each bucket b requires constant amount of space: it simply needs to store dept))) and est esstiate(b (b), each which take constant space. Thus the space complexity is the total number of buckets time 1. In fact, will bound |S% the number of buckets that have existed at any time up to time for edge e. As Lemma 12, let .i.... , Sg be partition of S. such that each S, contains exactly one depth 0 bucket, and all buckets in S, have the same depth 0 ancestor. We claim that [S,] S t1/3 for all i.
We will show this using Program 1, but now with k = 0 instead of 1:
Σ
max 21 Pa ERza
Jm
s.t.
2m
Fm S t
m=1
2 Vm E {1,...,m? Pm S
The analysis proceeds similarly to Lemmas A.11 and A.13. Let (t) be the optimal objective value for Program with parameter t. We claim that |S S gt( Let I' denote the number of buckets of depth that have existed up to and including time for this edge. Since the constraints in Program are the same as in Program 1, we already showed in the proof of Lemma A. that (zi,..., is feasible for Program 2. Since |
- Tens we have S S (t).
remains to bound g()t). Let m be the minimum integer such that Σm 22
Then as
argued in Lemma A.13, m S log 11/ + Therefore g((1) S m Im S Di= 2 5 2m+1, so
g' g'(t) 2log 1/2 0
By Lemma A.6, q S 1 + log xt maz. Therefore the total number of buckets for edge at time f is at most
g
S
< q 0(t2/3)
O(log u'nazt /1/3)
19

---

Under review as a conference paper at ICLR 2021
and thus the total space complexity is O([E) log mantt 1/3).
For the time complexity, each time step involves two tasks that may take non-constant time: com- puting " for each E, and computing arg minper, Eeep un- Once the first task has been done, the second task can by running any shortest path algorithm the directed graph (E, V) where edge e has nonnegative weight uf: this takes time Shortest Patststttttt))
For the first task, there two parts that may take non-constant time. The first part is searching for a bucket such that E 6. The buckets correspond to non-overlapping intervals, so this can be done by keeping the buckets in sorted order and using binary search. This approach yields a time complexity of (log (S = (loog t-l log max) per edge and thus O[ t-tlog log log x maz)) total. Note that to keep the buckets in sorted order, creating a bucket now requires us to insert into the right place in the ordering. Using self- seff-balancing binary tree, this be done in time O (S per operation as well (and at most two buckets are created per edge per time step).
The second part that may take non-constant time is computing Ymar = max UbER, dom(b)), if applicable. If the buckets are stored in sorted order, this can be done in constant time by looking at the last bucket in the ordering. This yields the desired bound.
We are finally ready to prove Theorem 1.1.
Theorem 1.1. The expected regret of Algorithm I after t time steps is
Rs 0 (1/33 R==0(pp3....
log x m'a BB/log + a'max b)
The space complexity and time complexity on time step t are /( log x maxx) and O [Elg
log log d'max) + SP((E),IV1)) respectively,
Proof. We have
x man I(x² + 12)
Rs
+
Σ
Re(e)
(Lemma A.7)
eE E
E mar L(x²² + 12)
Σ
(1 + log xe man (AvIn 1a L)g(() (Lemma A.12)
e
x max L(T² + 12)
28
+ [ + log m (4VIn + 20maa I.)
22/3
(Lemma A.13)
Plugging in a 2,3 as in Lemma A.7 gives us
E xe man L(x² + 12) + [1 + log T (43v2 2n 20 I.).
2
R2
22/33
0 E log mas (B logt t amaa D)t2/3)
Combining this with Lemma A.14 proves the theorem.
20


Reviews:
[{"review_id": "ovBn_ddU4Wu", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper uses the bandit learning framework to study the online learning problem for routing in a city network . After each routing decision, the learning agent observes the actual delay on each edge, which is given by the congestion function on the given flow plus a random noise, and the reward is the total delay on all edges. The paper proposes a learning algorithm similar to the UCB approach, provide the regret bound result, and conduct simulations on the New York City network to verify performance of the algorithm. \n\nThe contribution of the paper in my view is mainly on the setting where the nonlinear congestion function (satisfying a Lipschitz condition) with arbitrarily given flow is considered, and on using dynamic splitting to refine the budgets based on the number of observations.\n\nHowever, there are a number of issues in the paper that makes the overall contribution questionable, as I list below.\n\n- The first issue is that the authors is missing an entire line of very relevant result work and results. In particular, the work is closely related to the combinatorial semi-bandit research. The following are several most relevant studies, while many others are available in the literature.\n\n[1] Chen, Wang, Yuan, and Wang. Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms. JMLR'2016, Conference version appeared in ICML'2013\n\n[2] Qin, Chen, and Zhu. Contextual Combinatorial Bandit and its Application on Diversified Online Recommendation. SDM'2014\n\nThe routing problem in the current paper has a number of similarities with the CMAB framework in [1]: each road segment (edge) is a base arm, and it can be individually observed when the selected path contains the edge --- semi-bandit feedback, and each action is a set of base arms (a path) that follows certain constraints. The adversarial chosen path source and destination and the current flow can be viewed as the context in CMAB. The contextual CMAB problem is studied in [2]. The current paper has a bit more complication due to the congestion function. But the authors treat it by discretizing the flow into buckets. Essentially this is treating the pair of (edge, flow budget) as a base arm in the CMAB framework. Therefore, I believe that if we do not do dynamic bucketing and use a fixed discretization budget, the current problem fits as a special instance in the CMAB framework, and thus can be solved by the CUCB algorithm for CMAB. Noticeably the CUCB algorithm has O(\\sqrt{t}) regret (ignoring the additional log t term). However, the current paper only has a result for O(t^{2/3}), and the authors mention both in the introduction and conclusion that achieving O(\\sqrt{t}) regret as a future research work. But with proper setup as the above, I believe the O(\\sqrt{t}) regret has been achieved. Therefore the authors are seriously missing some existing work in this regard. Of course, the above discussion only uses static buckets. But applying dynamic buckets should only improve the results. The static bucketing may give some extra factor in the regret bound in terms of the number of budgets, but that is independent of time t. Therefore, I believe the dependency on time t should be O(\\sqrt{t}), and it should be easily achieved under the CMAB framework, such as using the CUCB algorithm in [1].\n\n- The second issue is that in terms of the theoretical analysis, the authors only provide the regret bound result as a theorem in the introduction. There is no more discussion on the factors related to the regret bound, such as |E|, and \\beta. Are their dependency tight or not? There is also no explanation on the outline of the analysis. In particular, how to incorporate the dynamic splitting of the buckets into the analysis. Dynamic splitting is the only thing that is different from existing work in my view, and its advantage should be further discussed.\n\n- The third issue is on the experimental evaluation. The authors do not compare the proposed algorithm with any baseline algorithms. Baseline algorithms that could be considered include epsilon-greedy algorithms and Thompson Sampling based algorithms. Without such comparison, it is hard to understand the benefit of the proposed algorithm. \n\n- Another issue is that the proposed algorithm is essentially very close to using the lower confidence bound (LCB) for the edge delays in the CMAB setting. Since the optimization problem is minimizing the delay, so it is understandable that the standard UCB is replaced by the LCB. The authors need to discuss whether there is any more difference between their algorithm and the LCB/UCB based algorithms.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AzSntIGEXNx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work introduces an interesting generalization of stochastic combinatorial semi-bandits for routing in a static graph. The main differences are: (1) the expected loss of an edge e is f_e(x^t_e) where the flow x^t_e is revealed at the beginning of each round (for each edge) and f_e is an unknown Lipschitz function (with known Lipschitz constant); (2) the regret is dynamic, computed against the sequence of optimal paths. When f_e is a constant function for each edge, then we recover a version of the stochastic combinatorial semi-bandit.\n\nThe main contribution is a novel UCB-like algorithm with a dynamic regret bound after T steps of |E|T^{2/3} (ignoring log factors in T). This is larger than the rate |E|T^{1/2} achievable for *adversarial* combinatorial semi-bandits, but ---as we said--- the problem studied here is more general.\n\nThe algorithm uses a hierarchical and dynamical bin structure to produce convergent estimates of f_e(x) for different values of x. This is a nice idea which is not standard in the bandit literature. The analysis of the algorithm is quite involved and apparently novel for the most part.\n\nThe main ideas behind the analysis are well explained at an intuitive level.\n\nThe source of the T^{2/3} dependence should be independent of the combinatorial nature of the semi-bandit problem. It would be interesting to know what happens in the simpler setting of parallel edges. Can the upper bound be improved? And if not, can a tight lower bound be proven?\n\nThe definition of x_{max}^t on page 2 looks wrong because the max is over t.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4SwDSoprfR8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this submission a routing problem is studied. In the considered model with each edge of the given graph a congestion function is associated that specifies the congestion depending on the current load of the edge. Then cars have to be routed through the network where each car has a source and a destination and one aims at choosing a path from the source to the destination with the smallest total congestion. However, the congestion functions of the edges are a priori unknown and hence one cannot trivially use a shortest path algorithm. Instead one gains information about the congestion functions only by routing the cars. When a car is routed one observes for each edge on its path the current congestion up to some random additive term. These observations can then be used for future routing decisions.\n\nThe main result of the submission is an algorithm that achieves a cumulative sublinear regret of O(|E|t^{2/3}) where the regret is defined as the difference between the expected path length chosen by the algorithm and the length of the shortest path. Some experiments are also conducted with this algorithm but the focus of the submission is clearly on the theoretical results. \n\nThe algorithm itself is non-trivial but also not too surprising. Due to the random noise one needs enough samples to estimate the congestion on an edge. The difficulty is that the congestion depends on the current load, i.e., one needs enough samples close to the current load (here one uses that the congestion functions are assumed to be Lipschitz continuous). The algorithm cleverly and adaptively partitions the samples of an edge into buckets where each bucket represents a certain range of loads. Then there are two factors that determine the precision of the congestion estimation: the range of the buckets and the number of samples per bucket. The more samples one has in a certain range the smaller can the ranges of the buckets be. Basically the algorithm splits a bucket if it contains already enough samples.\n\nI find the results interesting. The proposed algorithm is natural and its analysis is non-trivial. I am not completely sure if the model is very realistic though. It is assumed that the congestion functions are unknown (which makes sense). However, if I understand it correctly it is assumed that each driver knows exactly the current load on all the edges. It is not clear to me why this makes sense. It might also be the other way round: While the congestion functions are more or less known from historic data, the current load is unknown to the drivers. In my opinion the authors could discuss the model in more detail.", "extra_scores": {}, "extra_text": {}}, {"review_id": "12wIRFRtgYJ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nIn this paper the authors study the problem of routing users according to their requests through a network with unknown congestion functions over infinite time horizon. They model the problem as follows. A directed graph G(V,E) is given, where each edge is associated with  a congestion function f_e that maps the flow along edge e to some positive real. The mild assumption the authors make on the congestion functions of all edges is that they are L-Lipschitz. At every timetick a car enters the routing app, and asks to move from a source to destination. Given the collection of paths, the routing app is required to make a choice of a path. This choice incurs a cost, which is the noisy version of the sum of the congestions along the edges of the path Again, the author(s) make the reasonable assumption that the noise is zero mean and bounded by some value beta. The model is nicely motivated by real-world aspects of routing apps, and is a clean mathematical model. The key result is stated as Theorem 1.1. I checked the proof, and it appears solid. The authors design algorithm 1. ITs intuition is well described in section 2.1 Some comments to the authors of the paper follow \n \n\n- Is the Lipschitz constant known? If not, is there a way to test this assumption?  \n- I think the authors mean that the regret R_t is \\sum_{r=1}^t E[c_r-c*_r]. \n- Can you elaborate on your conjecture (e.g., page 3) concerning the right asymptotics of the regret as a function of t?  Is your conjecture related to the Awerbuch-Kleinberg SODA paper?  \n- Is the dependence of |E| tight? It felt while reading the proof (e.g., in Lemma A.7 where the summation over time and edges along the path are exchanged) that perhaps the analysis could be improved. \n- The experimental part is the weakest part in this paper. I would urge the authors to try settings where the assumptions of the theorem start breaking down, and see how the regret changes. For instance, what if some congestion functions are not L-Lipschitz but all the rest are. What if these functions correspond to edges with  high betweenness centrality? One can think of many other settings that could have made the paper (including the supplementary material) more interesting \n\nOverall this is a well-written paper with a clear contribution. The weak parts are the experiments which are practically sanity check for the validity of theorem 1.1, and the fact that from a technical point of view there is not much novelty. The novelty in my opinion lies in the design of the estimation algorithm of the cost. \n\n[Score updated From 6 to 5]\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an algorithm with sublinear regret for the problem of routing users through a network with unknown congestion functions over an infinite time horizon. The reviewers generally appreciated the main contribution of this work. One of the reviewers also felt that, although it may be possible to obtain the main result using more standard techniques, it is not clear whether doing so is an easy extension of the prior work. Following the discussion, all of the reviewers agreed that the paper missed important related work and it needs a major revision that incorporates the extensive feedback of Reviewer 2. For these reasons, I recommend reject.
Decision: Reject