Fast Routing under Uncertainty: Adaptive Learning in Congestion Games via Exponential Weights
Authors: Dong Quan Vu
Kimon Antonakopoulos
Panayotis Mertikopoulos
Venue: NeurIPS 2021 Poster (2021)
Keywords: game theory
adaptive algorithms
routing

Abstract: We examine an adaptive learning framework for nonatomic congestion games where the players' cost functions may be subject to exogenous fluctuations (e.g., due to disturbances in the network, variations in the traffic going through a link). In this setting, the popular multiplicative/ exponential weights algorithm enjoys an $\mathcal{O}(1/\sqrt{T})$ equilibrium convergence rate; however, this rate is suboptimal in static environments---i.e., when the network is not subject to randomness. In this static regime, accelerated algorithms achieve an $\mathcal{O}(1/T^{2})$ convergence speed, but they fail to converge altogether in stochastic problems. To fill this gap, we propose a novel,  adaptive exponential weights method---dubbed AdaWeight---that seamlessly interpolates between the $\mathcal{O}(1/T^{2})$  and $\mathcal{O}(1/\sqrt{T})$ rates in the static and stochastic regimes respectively. Importantly, this "best-of-both-worlds" guarantee does not require any prior knowledge of the problem's parameters or tuning by the optimizer; in addition, the method's convergence speed depends subquadratically on the size of the network (number of vertices and edges), so it scales gracefully to large, real-life urban networks.

Fast Routing under Uncertainty: Adaptive Learning in Congestion Games with Exponential Weights
Dong Quan Vu
Kimon Antonakopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG 38000, Grenoble, France dong-quan. vuêinria. fr
kimon. iono.aannnnncoollleeeiii.....r
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG 38000, Grenoble, France Critco Al Lab
panayotis. siaayots..meriikouullossiii.
Abstract
We examine adaptive learning framework for nonatomic congestion games where the players' cost functions may be subject to exogenous fluctuations (e.g.. due to disturbances in the network, variations in the traffic going through link, etc.). In this setting, the popular multiplicative exponential weights algorithm en- joys an O(1/VT) equilibrium convergence rate; however, this rate is suboptimal in static environments i.e., when the network is not subject randomness. In this static regime, accelerated algorithms achieve an 0 convergence speed, but they fail converge altogether stochastic problems. To fill this gap, we propose a novel, adaptive exponential weights method - dubbed ADAWEIGHT that seamlessly interpolates between the (11T7²) and O(Iv/T) rates in static and stochastic environments respectively. Importantly, this guarantee does not require any prior knowledge of the problem's is parameters or any tuning by the optimizer; in addition, the method's 's convergence speed depends subquadratically on the size of the network (number of vertices and edges), so it scales gracefully large, real-life urban networks.
Introduction
Navigation apps like Google Maps and Waze have user bases numbering in the hundreds of millions, and they may receive upwards of 10 routing requests per second; in fact, Google Maps alone exceeded one billion monthly active users in 2019, and its interface routinely receives up to 10 requests during rush hour in major metropolitan centers [10]. This vast number of users must be routed efficiently, in real-time, and without causing any "ex-post" regret the user end; otherwise, if user could have experienced better travel times along non-recommended route, they would have no incentive to follow the app recommendation in the first place.
In the language of congestion games [40], this requirement is known as a "Wardrop equilibrium", tigh-dimensional vector describing the traffic flow along each path
and is typically represented in the network [49]. Ideally, this equilibrium should be computed before making recommendation, so as minimize the number of disgruntled users. In practice however, this is rarely possible: the state of the network typically depends on random factors that vary from one epoch to the next (weather conditions, traffic accidents, fluctuations in the total number of commuters the system, etc.), so it is generally unrealistic to expect that such recommendation can be made in advance.
Our paper takes learning approach to this problem: routing recommendations provided in online manner, and they are subsequently updated "on the fly" once the state of the network has
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

been observed. In more detail, motivated by applications to GPS routing and navigation apps, we consider an adaptive recommendation paradigm that unfolds as follows:
1. At each epoch = 1,2,, .,,,..., a centralized control interface such as Google Maps determines routing flow for its users and provides recommendation accordingly.
After making recommendation, the interface observes the travel times of the network's users; based on this feedback, it updates the routing recommendation and the process repeats.
Main challenges. There several key challenges that arise in this setting. First and foremost, learning methods that are well-suited to rapidly fluctuating environments may be highly suboptimal in static networks and vice versa. Second, the problem's 's dimensionality the number / of available paths is exponential in the size of the underlying network, so crucial to propose learning methods that remain efficient in large networks. Finally, methods that require prior knowledge of the problem's 's parameters e.g., the smoothness modulus of the network's ' latency functions are beyond reach because such knowledge cannot be realistically obtained by the optimizer.
In view of all this, our paper seeks to answer the following question:
Is it possible to design adaptive, perameter-agnostie algorithm that is simultaneously optimal in static and stochastic networks, and whose convergence rate is polynomial in the network 's size?
Our contributions in the context of related work. Our paper proposes novel, adaptive expo- nential weights algorithm - dubbed ADAWEIGHT - which enjoys the following desirable properties:
1. In static networks, the method converges to a Wardrop equilibrium at a rate of ((log P) /T²). In stochastic networks, converges to a mean Wardrop equilibrium at an O(log P) / VT) rate.
3. These rates are attained without any prior tuning by the optimizer.
In the above, T denotes the learning horizon (number of epochs) and P is the number of paths used route traffic in the network. Thus, even though P may grow exponentially, the logarithmic dependence on P ensures that the algorithm's 's runtime remains polynomial, and in fact, subquadratic, in the size of the network. To the best of our knowledge, ADAWEIGHT is the first method that simultaneously achieves these desiderata; to provide the necessary context, we give below a detailed account of the related work on the topic.
The static regime of our learning model matches the standard framework of Blum et al. [7] who showed that variant of the classic exponential weights (EW) algorithm [4, 5, 31, 48] converges to averaged sense). This result was
a Wardrop equilibrium at an O(1/vT) rate (in the Cesàro, subsequently extended to stochastic congestion games by Krichene et al. [22, 24], who showed that the EW algorithm also enjoys an ((1/VT) convergence rate to mean Wardrop equilibria (again, in a Cesàro sense). we discuss in the sequel, the convergence speed of the EW algorithm of Blum al. [7] and Krichene al. [22] is (log P/VT)) in both cases; however, the method's learning rate is not chosen appropriately, the EW algorithm may lead to non-convergent, chaotic behavior, even symmetric congestion games over a 2-link Pigou network [42].
In general equilibrium problems, the (1/vVT) rate cannot be improved (see e.g., [1, 8)) with- out more stringent assumptions such as strong monotonicity and the like. However, nonatomic congestion games are well known admit convex potential sometimes referred as the Beck- Maenn-MGGuireWWinsste (BMW) potential [6] the O(I/VT) convergence guarantee of Blum et al. [7] is not optimal in the static regime (i.e., when costs functions do not change overtime). In this static regime, the optimal smooth convex minimization rate is (L1/T2) [34, 36), and it is achieved by the seminal "accelerated gradient" algorithm of Nesterov [35]. If applied directly to our problem, Nesterov's algorithm has a catastrophic (PP) dependence on the number of paths; however, by coupling it with a "mirror descent" template in the spirit of [38, 50], Krichene et al. [24] proposed an accelerated method with an exponential projection step that is particularly well- suited for congestion problems. In fact, going a step further, it is possible to design an accelerated exponential weights method ACCELEW EIGHT for short that achieves an (log( (P)T22 rate in static environments. Note also that Nakamura et al. [33] recently shows that an (exp((-T) rate is achievable under stronger assumption that the BMW potential strongly convex (which is beyond the scope of consideration of our paper).
BIGHT

---

EW
ACCELEWBIGHT
UNIXGRAD
UPGD
AC-SA
ADAWEIGHT [ours]
STATIC
log P/VT
log P/T2
P/T
log P/T
log P/T²
log P/T2
STOCH.
log P/VT
X
P/TT
X
log P/VT
log P/VT
ANYTIME partially
X
X X
PAR. AGN.
partially
X
Table I:
Overview of related work. All rates are reported in the O(-) sense; "par. agn." means that the method is parameter agnosticc i.e., it does not require prior tuning knowledge of the problem's parameters.
Crucially, the learning rate parameter of ACCELEWEIGHT must be tuned with prior knowledge of the problem's 's smoothness parameters, moreover, despite its optimality in the static regime, the method fails to converge altogether in stochastic problems. The universal algorithm of Nesterov [39] provides a method to resolve the former issue, but it relies on a line-search mechanism that cannot be adapted stochastic framework, so it does not resolve the latter. the flip side, the accelerated stochastic approximation (AC-SA) algorithm of Lan [26] achieves optimal rates in both the static and stochastic regimes, but does not provide anytime guarantees (the iteration budget must be fixed as function of the accuracy threshold required), and it assumes full knowledge of the smoothness modulus of the game's s cost functions (which is not realistically available to the optimizer).
Our approach adapts to the problem's 's smoothness parameters via an "inverse-sume sum-sss-m-ooofoo -ot--oo--uuuress learn- ing rate in the spirit of ADAGRAD [16] - though ADAGRAD itself lacks an acceleration mechanism, so it is suboptimal in static environments [29, 30J. To the best of our knowledge, the first order- optimal interpolation result was achieved by the ACCELEGRAD algorithm of Levy et al. [29] for unconstrained problems (and assuming knowledge of a compact set containing solution of the problem). The UNIXGRAD proposal of Kavis et al. [20] subsequently achieved the desired adap- tation in constrained problems, but under the requirement of a bounded Bregman diameter. This requirement rules out the EW template (the simplex has infinite entropic diameter), so the conver- gence speed of UNIXGRAD is polynomial in the number of paths, and hence unsuitable for large network instances. For convenience, we compare all these works in Table above.
2 Problem setup
2.1. The game. Building on the classical model of Beckmann et al. [6], we will consider class of routing games defined by three basic primitives: (i) the game's 's network structure; (ūi) the associated set of traffic demands; and (iä) the network's cost functions. The formal definition is as follows:
The network structure: Consider a directed graph G G(V,E) with vertex set and edge set E. The focal point of interest is set of pre-determined origin-destination (O/D) pairs (O,, D:) E V x V indexed by
Each pair E N is associated Mj >> 0 that is to be routed from O to D; via a fixed set of paths (or routes) P: joining O to D, in G. We denote the set of all such paths in the network by P UIEN P, and, for concision, denote the corresponding cardinalities
N = {1, ......... N). ....
traffic demand
P. [Pal and P = [P| Σ, P,. We also write Moot := EiEN M; and Mmax == maxieN M, for the total and maximum traffic demand associated to network's O/D pairs.
2. Routing flows: In order to route the traffic, the set of feasible flow profiles is defined
X {x RPP EpEP, Ttpp = M,,i 1, .. N
i.e., as the product of scaled simplices & x= II. M, MPP)) In turn, each feasible flow profile x E X induces on each edge e E E a routing load (x) = EieN EpEp, [eep,) Fi,p, i.c., the accumulated mass of all traffic associated to the focal set of O/D pairs that goes through
3. Congestion cost: The traffic routed through a given edge e E incurs congestion cost (or latency) depending on the total traffic on the edge and/or any other exogenous factors. Formally, we will collectively encode ambient probability space (Ω, F.)...). P). We will further assume that each edge E E is endowed with an edge-cost function e.: R state w Ω the cost to traverse edge e E E will be ce (Me (x), Analogously, the cost to
such factors
state variable w Ω taking values in some
-> R4; ; in this way, given a flow profile x X' and
3

---

traverse a path p E P will be given by the induced fonth-oost,fucttonn cp: : X x - R4 defindd as (z, Eeep ce (P))))),...
The only assumption that we will make for the game's cost functions is follows:
Assumption 1. Each cost function (p, w); e E & is measurable in w and non-decreasing, bounded and Lipschitz continuous in p. Specifically, there exist H 0 and L > 0 such that ce (e( s H for all p. p' E [0, Miol] and all w E S2 e E.
and Ice (p, w) ce wi) I Lip
Remark. Assumption is very mild regularity condition that is satisfied by most congestion models that occur in practice - including BPR, polynomial, or regularly-varyinn
latency functions, cf. [7.
11, 13, 22, 25, 27, 40, 43, 45] and references therein. For this reason, we will treat Assumption as standing, blanket assumption and we will not mention it explicitly in the sequel.
The key difference between our problem setup and other nonatomic congestion models in the liter- ature [40, 45] is the advent of uncertainty in the game's cost functions (as modeled by the game's ambient state variable E 92). For concreteness, we demonstrate below two examples of this type of uncertainty that could arise in practice:
Example 1 (Stochastically perturbed BPR costs). Standard BPR models [13, 27, 41, 43], under the form APR (p) = ag + be (p/cap,) ". vp 2 O, capture the effects of a link's length, its capacity, free-flow speed, etc.. urban network congestion. However, they neglect other miscellaneous factors such as weather conditions, accidents and other random factors which may cause a temporary increase or decrease in congestion. In our notation, if we is additive random fluctuation for the cost of edge e E &, the induced cost at a flow x E X becomes c(2, w) BPR (#e(az) + we- The noise also appear in cases where the actual latency congestion can only be measured up to certain error (a case of vital importance for Internet-like networks).
Example (BPR models with exogenous loads). In practice, the total traffic is the aggregation of all commuters, irrespective of whether they are using navigation app not. With this in mind, consider the problem of a navigation app making flow recommendation x X for its users. If we denotes the exogenous traffic load on edge e E & (i.e., commuters not using the app), the total load on e will be (e( + Web Thus, following the BPR model, the induced cost is co(ar, w) ce (P + we), i.e., the randomness is woven implicitly in the model.
2.2. The mean game and equilibrium flows In the above framework, each exogenous state variable w E Q determines an instance of a routing game, defined formally as a tuple I. = Tw (G, cw) where c. is shorthand for the network's cost functions {ce (-, (e,w)eeee instantiated at w. Of course, in analyzing the game, each individual instance Iw is meaningless by itself, un- less P assigns positive probability only to single w. For this reason, will instead focus on the mean game r = NGG P, C') which has the same network and routing flow structure as every T Ω but whose congestion costs are determined by the mean cost functions Cp(x)) Elcp(x,,) WI]
Now, motivated by the route recommendation problem described the introduction, we will focus on learning equilibrium flows where the controller can guarantee Wardrop's 's principle on average [49], i.e., that all traffic is routed along a path with minimal mean cost. Formally, we have:
Definition 1 (Mean equilibrium flows). We say that x² E X is mean equilibrium flow if and only if, for all i E A and all p. 9 E Pi such that ",,,- > O, we have Cy(#*) < Cz(=").
Remark. Definition 1 means that, on average, no user has an incentive to deviate from the recom- mended route; obviously, when the support of PP is singleton, we recover the usual definition of a Wardrop equilibrium [6, 40, 49]. This special case will be particularly important and we describe in detail in the next section.
Importantly, the problem of finding an equilibrium flow of a (fixed) routing game To admits a potential function often referred to the Beckmann-MoGhiln -entere-Wiinneeen Winsten (BMW) potential [6, 15].
Specifically, for a given instance w E Ω, the BMW potential is defined as
FL(z) = E.Es J
(P((x)
ce(p.w) dp for all x E X,
(BMW)
and it has the property that arg min FL coincides with the set (q(Tw) of equilibrium flows of Tu. In our stochastic context, natural question that arises is whether the potential property for each fixed w E Ω can be extended to the mean game I when w is randomly generated. Clearly, the most

---

direct candidate for a potential function in this case is is the averaged BMW potential:
Mela)
F(x) = [[]](())
Σ
ce(aww)
LE
Indeed, as we show in Appendix B, we have:
Proposition 1. A flow profile x² E X' is mean equilibrium flow if and only if it is minimizer of F over X; more succinctly, Eq(T) = arg min F(x:)
In view of the above, F provides natural merit function for examining how close given flow profile I E X' is to being an equilibrium; on that account, all our convergence certificates in the sequel will be stated in terms of F. Note also that since Ce e E &, continuous and non-decreasing, F is a differentiable, convex function on X. However, since the probability law IP on is not known, we will not assume that F (and/or its gradients) can be explicitly computed in general.
2.3. The learning model. The last component of our model is the actual learning process that unfolds over time. The specific sequence of events that we will consider evolves as follows:
1. At each stage = 2, .... the navigation interface selects flow profile X X' and makes the corresponding routing recommendation its users.
Concurrently, the state w' of the network is drawn from Ω (i.i.d. relative to P).
3. The interface observes the realized congestion costs (ee (X*), w/) along each e E & (possibly up to some error); subsequently, the flow recommendation is updated, and the process repeats.
We will refer to this general model as the stochastic regime. For concreteness, we discuss below two special cases that have attracted particular interest in the literature:
Example 3 (Static environments). In the absence of randomness, is supported on a single instance E Ω so we have w² w for all / = 1, 2,..... and we assume that the navigation interface measures directly C(X*)= c(X*, w). This setup matches the deterministic model of Blum al. [7]. Fischer and Vöcking [17] and Krichene et al. [23, 25], and we will refer to it as the static regime.
Example 4 (Routing games with noisy observations). Consider the setting where only a stochastic "perturbed" cost co (1)) w²) ce (e(()e()), + w is observed when a flow profile x E X' employed at time & (here, E Ω is fixed). When w is the random noise such that R[w"]] = O, Ve, Vt, our learning model reduced the routing game with noisy observations studied by Krichene al. [22, 25].
For a given learning window, it might not be a priori clear whether the system is in the static or stochastic regime. we shall see Section 3, standard stochastic algorithms are suboptimal in the static regime, while order-optimal deterministic algorithms may fail to converge altogether in the stochastic regime. As such, the key question that we aim answer is as follows: design routing algorithms that automatically adapt to the appropriate setting and provide optimal convergence guarantees both static and stochastic environments? We address this in Section
possible to
3 Non-adaptive methods
To the stage for the analysis come, begin by presenting the equilibrium convergence prop- erties of two learning methods that are tailor-made for each of the two basic regimes described the previous section: the "vanilla" exponential weights algorithm for the stochastic case, and an acceler- ated exponential weights method for the static one. Both algorithms rely crucially on the (rescaled) logit choice map A: R. + X. given in components as
M; expx(Yi. (V) Egep, cxp(Yi.g)
for all E P; and all A.
(3)
For concision, we will also write Cj for the total congestion cost measured for path E P at stage t, and C* (C))PER for the profile thereof.
5

---

3.1. Exponential weights in the stochastic regime. We begin by presenting the standard expo- nential weights algorithm the stochastic regime. pseudocode form, have:
Algorithm 1: Exponential weights (EXPWEIGHT)
Initialize y
for t= I, ... do
set X <- A(Y+=)) and get C + =xxx",
If route and neasure costs If update path scores
set y = C²
Then, by applying the classical analysis of exponential weights methods [9, 46], we obtain the following equilibrium convergence guarantee:
Theorem Let x² be an equilibrium of r. If Algorithm 1 is run with variable learning rate
J = the time- tineaaveraged flow profile X -1/T) Etn, Xt enjoys the equilibrium conver- gence rate
B[F(X*) - F(**)]
NM VT
log
Mmax P Moot
)+
H + (1 =0 log PT) VT
(4)
This result confirms that EXPWEIGITT achieves speed of convergence that is logarithmic in terms of P. and hence linear the size G = | |8) of the underlying network. Note that Theorem is direct application of standard results of EXPWEIGHT into the set-up of routing games (e.g., one can derive Theorem from Corollary 2. and Theorem 4.1 of [46]). Since EXPWEIGHT is not the main focus of this work, omit the details of the proof of Theorem instead, make two relevant remarks: First, the convergence rate obtained for Algorithm concerns the empirical average flow, not the actual recommendation, distinction which important for practical applications. Second, there is a slight suboptimality in terms of the learning horizon T: the rate presented in Theorem contains Iog(T)) term which can be shaved off by switching to the so-called "dual averaging" variant of the exponential weights template (or finetune the method's learning rate in terms of T and subsequently use doubling trick obtain an anytime guarantee). For the details, we refer the reader to [38, 46, 50].
3.2. Accelerated exponential weights in static environments. We now turn our attention the static regime, i.e., when there
exogenous variations in the game's state (w for all I t= 1, .,... In this case, is reasonable to expect that a faster convergence rate should be attain- able: in particular, below), so the optimal convergence speed in this case is the iconic O(1/T²) rate of Nesterov [35]. In more detail, we have:
we show below, the game's potential is Lipschitz smooth (see Proposition
Proposition The BMW potential Lipschitz smooth relative the L norm on X and has smoothness modulus 3 = KL. where K is the length of the longest path in P.
Now, to maintain the graceful scaling guarantees of the EW template, our proposal to achieve an O(L/T²) rate is an accelerated exponential weights algorithm that builds on ideas by Nesterov [35], Allen-Zhu and Orecchia [2] and Krichene et al. [24]. In pseudocode form, the method unfolds follows:
Algorithm 2: Accelerated exponential weights (ACCHLEWEIGHT)
Input: Smoothness parameter / Initialize y <- O, X 0, a and 70 NM
for f= 1, 2, do
set 7' A(Yt-1)
I/ exploratory flaw obtained fron path scores // average with previous
set X + a' a'-1x (1 )2'
set 7/ + i 22 1-1 t200 + // + (70
// update step-size
set a' +- 9¹ f-1/a²
// update noving weight and neasure // update path scores
set Z + a' X + +(1 -11- '2' and get O + c(Z',ww)
set yd yt-1 - (1-c) (1-a')a 'C'

---

Importantly, the step-size of Algorithm 2 is finetuned relative to the smoothness modulus of F, which assumed known the navigation interface. With this in mind, our main convergence guarantee for ACCELEWEIGHT is as follows:
Theorem 2.
Let x² be equilibrium ofT. If Algorithm 2 is run for T epochs in the static regime, the traffic flow profile X2 enjoys the equilibrium convergence rate:
F(X") - FF(x)) 4,N2 max log max P/ P/Mrot = O [og(P)
(5)
1T²
T
Theorem 2 confirms that, in the static regime, FIGHT converges to equilibrium with an optimal O (log( P)/T2) convergence speed, as desired. The proof of Theorem 2 is based tech- niques that are widespread in the analysis of accelerated methods, so we relegate it to Appendix C.
We only note here some limitations of the accelerated exponential weights method. First, the al- gorithm's 's convergence rate concerns a sequence of routing flows which is never recommended, a disparity which limits the algorithm's 's applicabilityy Second, the algorithm's 's step-size must be tuned with prior knowledge of the problem's 's smoothness modulus (which is not realistically available to the optimizer), it is not adaptive in this regard. More importantly, ACCELEW WEGGT fails to converge altogether in the stochastic regime, so it does not achieve rate interpolation either. Par- ticularly, ACCELEW FIGHT (and other Nesterov's acceleration methods) achieves convergence by building& a consistent positive momentum towards a minimizer and then introducing a dissipative, "vanishing friction" term. In the stochastic regime, the fluctuations induced by the stochastic gradi- ents fail to accumulate consistent momentum, so the acceleration provided is incoherent and hence the non-convergence of ACCELE
The per-iteration complexity of Algorithms 1 and 2. In the discussions above, we chose to present simple implementations of EW and ACCELEWEIGHT (as Algorithms and respectively). in which every iteration runs in O(P) time. This is inefficient in large-scale networks where P is typically exponentially large; however, owing to the underlying exponential weights template, both algorithms can be implemented efficiently in O(EI) time and space via a dynamic programming procedure known as "weight-pushing" [19, 47] under a mild assumption that the graphs defining the network are directed acyclic. The details of this efficient implementation lie beyond the scope of this work, so we do not present them here.
4 ADAWEIGHT: Adaptive learning in the presence of uncertainty
4.1. Statement and discussion of results. To summarize the situation so far, we have seen that EXpWEiGHT attains Ologg P)/vT) rate, which is order-optimal in the stochastic case but sub- optimal in static environments; by contrast, ACCELEW EIGHT attains an (loo(P))/T" rate in static environment, but has no convergence guarantees in the presence of randomness and uncertainty. Consequently, neither of these algorithms meets our stated objective to concurrently achieve order- optimal guarantees in both the static and stochastic cases (and without requiring prior knowledge of the problem's 's smoothness modulus).
To ve this gap, we propose below an adaptive exponential weights method - ADAGHIGHT for short - which achieves these objectives by mixing the acceleration template of ACCELEWEIIHT with the dual extrapolation method of Nesterov [37]. We present the pseudocode of ADAWRIGHT as Algorithm 3 below. The main novelty in the definition of the ADAWEIGHT algorithm is the intro- duction of two "extrapolation" sequences, Zt and Ýt, that venture outside the convex hull of the gen- erated primal (flow) and dual (score) variables respectively. These leading states are subsequently averaged, and the method proceeds with an adaptive step-size rule. Particularly, ADAWEIGHT relies on three key components:
a) A dual extrapolation mechanism for generating the leading sequences in Lines and 7; these sequences are central for anticipating the loss landscape of the problem.
b) An acceleration mechanism obtained from the (a*) wweighted average steps in Lines 5 and 8; in the analysis, o will grow as 4, so almost all the weight will be attributed the state closest to the current one.
7

---

c) An adaptive sequence of learning rates (cf. Line 10) in the spirit of Rakhlin and Sridharan [44], Kavis et al. [20] and Antonakopoulos et al. [3]. This choice is based on the ansatz that, the algorithm encounters coherent gradient updates (which can only occur in static environments), will eventually stabilize to a strictly positive value; otherwise, it will decrease to zero at (1/vV)) rate. This property is crucial to interpolate between the stochastic and static regimes.
Algorithm+ 3: adaptive exponential weights (ADAWEIGHT)
Initialize a < 7"
0, n and y +-
for t= 1,2, ...
set A + -i =
H/ set anchor primal paint
// the test phose:
set Z + A(t'Y*')
I/ compute pivot point
set X + ao +
Ei /Ei and get E + o(x
11 reweigh query test point
set ÿt + y a²C'
I/ exploratory score update
11 the recomnendation inn phase:
set Z A A(1'8²)
compute pivot point set X <- (a'z' + 11/ Eizo a² and get C +- ww)) /1 reweigh route and measure costs set yd+ t y - n'C
// update path scores
set tf - 1/ 1/ 1+ Ei=o (
10
11 update learning rate
The combination of the weighted average iterates and adaptive learning rate in ADAWeigHT is shared by the UNIXGRAD algorithm proposed by Kavis et al. [20], which also provides rate interpo- lation in constrained problems. However, UNIXGRAD requires the problem's 's domain to have finite Bregman diameter - and, albeit compact, the set of feasible flows X' has an infinite diameter under the entropic regularizer that generates the EW template. Therefore, UNIXGRAD is not applicable to our routing games. This is the reason for switching gears to the "primal-dual approach offered by the dual extrapolation template; this primal-dual interplay provides the missing link that allows ADAWEIGHT to simultaneously enjoy order-optimal convergence guarantees in both settings while maintaining the desired polynomial dependency on the problem's 's dimension.
In light of the above, our main convergence result for ADGHEIGHT as follows:
Theorem 3. Let x² be an equilibrium T. If Algorithn is run for T epochs with a' = & for any t= 1,2,..., the recommended flow profile XT enjoys the equilibrium convergence rate:
B[F(XT) -Fx))) S 4/2AKH 163/NM max A 3/2 +
=00 (log P)3/2
(6a)
VT
T2
VT
Moreover, in the static case, Algorithm 3 enjoys the sharper rate:
2/2 +B
(log 3/2
F(X²) - F(x*)
T O
(6b)
T
In the above expressions, A and B are positive constants given by A
N Muaax logg (olg Mmax/ Meat) + 13] = O(log P) and B Miot (Pg( MMot) = Olog P).
Theorem 3 confirms that ADAWEIGHT enjoys all of the desired features: (i) it achieves simultane- ously optimal guarantees in both stochastic and static environments (i.e., O(1/ VT) and O respectively); (i) the derived rates maintain a polynomial dependency in terms of the network' s combinatorial primitives; and (iii) it requires no prior tuning by the learner. Moreover, unlike Ex- PWEIGHT, the convergence of ADAWEIGHT corresponds to an actual traffic flow profile that is implemented in epoch and not the average flow.
A smooth trade-off rate between static and stochastic environments. In Inequality (6a) of The- orem 3, the convergence rate of ADAWEIGHT the stochastic case given the worst-case sce- nario. Alternatively, one can also quantify the convergence speed of ADA according to the
8

---

level of randomness of the game. Particularly, define the random variables U*, U and var such that (7) Ú' Ú'= (x*) and U* = VF and var == max E || [
Intuitively, U and U represent the noises of the observed costs C and C². induced by X and x in comparison with the corresponding gradients of the BMW potential F; on the other hand, var quantifies the variances of these noises. With the same set-up as Theorem 3. the recommended flow XT of ADAWEIGHT enjoys the following equilibrium convergence rate: [F(((X") - F(x*)] s
o( (log () (VVVvar//+++/3)) 1/T3)) Interestingly, in special instances where the cost observations become more accurate over time, we can achieve a smooth trade-off in the convergence rate; e.g., if var = (1/ /TP) for some suitable p. ADAWEIGHT 's rate of convergence carries a dependence of the order of O (Tmmx(-112-p)) )
Implementations of ADAWEIGHT. As in the case of EXPWEIGHT and ACCELE we note that ADAWEIGHT can also be implemented efficiently via the weight-pushing technique of Takimoto and Warmuth [47] (with linear space and time complexity in the size of the underly- ing graph). We leave the details of this efficient implementation for future works.
Technical contributions of the proof of Theorem 3. As analyzed above, ADAWEIGIIT is not merely a "convex combination" of the two non-adaptive optimal algorithms (ACCELEWEIGITT and EXPWEIGHT). From this reason, the proof of Theorem is technically involved. We analyze its main ideas in Section 4.2 and give a detailed proof in Appendix D.
4.2. Sketch of proof of Theorem 3. Let Rr = E (VF(X)), x²), ~x"), the starting point of our proof is the following result:
E [FF(X") F(x*)] S 2 (x*)) / for any T.
(8)
Intuitively, (8) shows that the convergence properties of ADAWEIGHT can be quantified via Rx")) Note that (8) a standard result in working with extappxtraoolation and a-weighted averaging tech- niques that also appears in several previous works [14, 21] (see Appendix D for a proof).
Recall that ADAWEIGHT is run, V ((*)) is not observable and only the cost C* is observed and used. Therefore, instead of Rx(")) ). we now focus on the term Ry == = L(C", Zt x²). ). In the static case, My (x*) coincides with Ry (x*) and in the stochastic case, we can prove that (x())) is an unbiased estimation thereof. Therefore, any upper-bound of (x=) can be translated into an upper-bound of the left-hand-sides of (6a) and (6b) via (8). The key question becomes "Which upper-bound of Ry (x*) can be derived guarantee the convergence rates in (6a) and (6b)?"
Recall that ADAWEIGHT (Algorithm 3) built on the dual extrapolation template with two phases: the test phase and the recommendation phase. In the sequel, we aim to upper-bound R. (a*) in terms of the "distance" between the pivot primal points in these phases (i.e., Z' and Z') and the difference between the costs measured in these phases (i.c., Ot and C*)). Particularly, we have
Rf S Σ Banal (1) (n +yyle - c01 + Σ Oprimal (1)+ -2
where Sasal (17 +1 and Oprimal (1) are certain functions that also depend on other parameters of the
game. Importantly, the terms in the right- saaht-hand-sizze of (9) are actually summable as follows:
(i) In the static case, it is bounded by the summation ΣT= Ssmaii ) -C"113 (due to the smooth- ness of the BMW potential F). Moreover, by our special choice of adaptive sequence of learning rate n7', there exists To < T such that only the first To components in this summation are positive and hence, this summation is actually of order O(1) (i.e., it does not depend on T).
(ii) In the stochastic case, beside the term derived in the static case, we also have an extra term in
the upper-bound of (9) that has the form v E @I[[[" Č4 - IV F(X)) v F(X)) in- tuitively, this quantifies the error of the observed costs with respect to the actual gradients of the potential. This term is of order (TT3/2).
Apply these result into (8), we obtain the convergence rates indicated in (6a) and (6b).

---

5 Numerical Experiments
5.1. Experiments in the stochastic regime. First, we conduct an experiment on routing game with noisy observations (as described Example 4) with the following setup: on a randomly gener- ated network with 24 vertices and 276 edges, we assign to each edge a BPR cost function and choose N = diginndestination pairs, each of which comes with a traffic demand; the traffic will be routed via the set of P 3366 paths. Particularly, at each time T, after the algorithms decide their flow profiles, we perturb the induced costs on each edge e by a noise wa that is drawn independently from the normal distribution (0, 10). The algorithms only observe these stochastically perturbed costs and use them to update the next iterations.
For validation purposes, we run EXPWEIGHT, ACCELEWEIGHT and ADAWEIGHT in 5 instances (of noises' layout) and report, in Figure la, the averaged results across these instances. Particularly, we plot out the evolution of the following values: AFXPWRIGHT (T) = F F F(x*) where X is F F(XT) -F())=((x)) where X is output by Algorithm 2 and A ADAWER (T) F(X") -=(x=) where X is output by Algorithm 3. Here, x² is chosen such that it induces the minimum F-value among all flow profiles computed by these algorithms after 1 15000 iterations; thus, x* represents the equilibrium flow.
the time-averaged of outputs of Algorithm 1, A ACCELEWEIGHT (T)
Figure Ia shows that AEXPWEIGHT(? (T) and A ADAWEICHT(?) tend to zero as T increeses; this confirms that EXPWEIGHT and ADAWEIGHT converge toward equilibrium. To this end, observe that ACCELEWEIGHT fails to converge altogether. We also plot out vT A Accehee (T)) and vT ADDAWFOOT (7) (see Appendix E), and we observe that these terms approach horizontal lines as T increases. This reaffirms the fact that the speed of convergence of EXPWEIGHT and ADAWEIGHT (1/vV)) in the stochastic regime which consistent with our theoretical analyses.
5.2. Experiments static regime. To illustrate the performance of the algorithms in the static case, we take advantage of a real data set collected and provided by [18] (with free license). This data set contains no personally identifiable information or offensive content. In this section, we present the experimental results by [28]). Results corresponding to other network instances are presented in Appendix E. The Sioux- Falls network has 24 vertices and 76 edges. We choose N 30 origin-destination pairs and the total number of paths in use is P = 3000. We extract from the data set the BPR cost function corre- sponding each edge and the traffic demand corresponding to each O/D pair. We run WEGGT, AIGHL and ADAWEIGHT in 16000 iterations and report the results thereof in Figure 1b.
instance in this data set: the SiouxFalls network (originated
Figure 1b confirms that in this static environment, all three algorithms converge towards equilib- and ADAWEIGHTT converges at an (1/T22) rate while Ex- PWEIGHT fails to achieve this speed. These convergence rates are reaffirmed by observing that T AACCELE (T)) and T - ADAAWIGHHT (T') approach horizontal lines as T increases (cf. Ap- pendix E). We also run ACCELEWEIGHT with several initial step-size options and observe in Fig- ure lb that with badly-tuned parameters (i.e., with a wrongly estimation of the smoothness level of F), SCcELeWeIGHT might have slow "warm-up" phase might even diverge. By contrast, ADAWEiGhT retains its appealing fast convergence properties throughout our experiments.
rium. Particularly, ACCELEWEIGHT
10a-
10
102
(T)
105
101
AcceloWeight -1
Accele 11
10-1
AcceleWe ght
AccoloWeeihh, 1E-01
ExpWeight AdaWeight
10
ExpWeight
10"
AdaWWiight
10a
10:
10'
10P
102
T
T
(a) Convergence in a stochastic environment
(b) Convergence in static enviromment
Figure 1: The convergence speed of EXPHEIGHT, ACCELEWEIGHT and ADAWEIGHT in routing games.
10

---

Acknowledgement
The authors are grateful for financial support by the French National Research Agency (ANR) in the framework of the "Investissements d' "'avenii" program (ANR-15-IDEX-AE the LabEx PERSYVAL (ANR-11-LABX-00550)
MIAI @ Grenoble Alpes (ANR-19-P3IA-0003), and the grant ALIAS (ANR-19-CE48 (0199--CE8--0---0000 The authors' research was also supported by the COST Action CA16228 "European Network for Game Theory" (GAMENET).
References
[1] Jacob Abernethy, Peter I.. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and min- imax lower bounds for online convex games. In COLT '08: Proceedings of the 21st Annual Conference on Learning Theory, 2008
[2] Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and
Mirror Descent. In Proceedings of the 8th Innovations in Theoretical Computer Science, ITCS '17, 2017.
Full version available at httpp//aaxivv org/ argg/bbb/140 1537.
[3] Kimon Antonakopoulos. E. Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra-gradient methods min-max optimization and games. ICLR '21: Proceedings of the 2021 International Conference on Learning Representations, 2021.
[4] Peter Auer, Nicolò Cesa- Bianchi, Yoav Freund, and Robert E. Schapire. Gambling in rigged casino: The adversarial multi-armed handit problem. In Proceedings of the 36th Annual Symposium Foundations of Computer Science, 1995.
[5] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
[6] Martin Beckmann, C. B. McGuire, and C.B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
[7] Avrim Blum, Eyal Even-Dar and Katrina Ligett. Routing without regret: on convergence to Nash equilib- ria of regret- minimizing in routing games. In PODC '06: Proceedings of the 25th annual ACM SIGACT-
SIGOPS symposium on Principles of Distributed Computing, pages 45 52, 2006.
[8] Séhastien Bubeck. Introduction online optimization. Lecture Notes, 2011.
Séhastien Bubeck and Nicold Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 511): 2012.
[10] Théophile Cabannes, Marco Sangiovanni, Alexander Keimer, and Alexandre M Bayen. Regrets in routing
networks: Measuring the impact of routing apps in traffic. ACM Transactions on Spatial Algorithmss and
Systemy (TSAS), 5(2): 1-19, 2019.
[11] Nicold Cesa-Biance and Gábor Lugosi. Combinatorial bandits. In COLT '08: Proceedings of the 22nd Annual Conference on Learning Theory, 2009.
[12] Gong Chen and Mare Teboulle. Convergence analysis of proximal- minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-54) 543,, August 1993.
[13] Riccardo Baiiii-aadesschi, Roberto Cominetti, Panayotis Mertikopoulos, and Marco Scarsini. When selfish routing had? The price of anarchy in light and heavy traffic. Operations Research, (8(2):111434, March 2020.
[14] Ashok Cutkosky. Anytime online-to-batch, optimism and acceleration. In International Conference on Machine Learning, pages 1446-1454. PMLR, 2019.
[15] S. Dafermos and Sparrow. The traffic assignment problem a general network. Journal of Research of the National Bareau of Standards, 73B(2)911-18, 1969.
[16] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121-2159, 2011.
[17] Simon Fischer and Berthold Vöcking. On the evolution of selfish routing. In Proceedings of the 12th European Symposiun on Algorithms, 2004.
[18] Transportation Networks for Research Core Team. Transportation networks for research project. https:
// thub. cwm/ coom/bstablee/Teeeo. /ree//raanprrrooeee wtw.aierrrraasoottttiiooooo iationNetwookke 2021.
[19] András György. Tamás Linder, Gábor Lugosi. and György Ottuesák. The online shortest path problem under partial monitoring. Journal of Machine Learning Research, 8:2369-2403. 2007.
[20] Ali Kavis, Ktir Yehuda Levy, Francis Bach, and Volkan Cevher. UnixGrad: A universal, adaptive algo- rithm with optimal guarantees for constrained optimization. In NewrIPS '19 Proceedings of the 33rd International Conference Neural Information Processing Systems, 2019.
11

---

[21] Ali Kavis, Kfir Yehuda Levy. Francis Bach, and Volkan Cevher. UnixGrad: A universal, adaptive algo- rithm with optimal guarantees for constrained optimization. In NeurlPS '19 Proceedings the 33rd International Conference on Neural Information Processing Systems, 2019.
[22] Syrine Krichene, Walid Krichene, Roy Dong. and Alexandre Bayen. Convergence heterogeneous distributed learning in stochastic routing games. Allerton '15: Proceedings of the 52nd Annual Allerton Conference on Communication, Control, and Computing, 2015.
[23] Walid Krichene, Benjamin Drighès, and Alexandre Bayen. On the convergence of no-regret learning in selfish routing. In ICML 'I4: Proceedings of the 31st International Conference Machine Learning. 2014.
[24] Walid Krichene, Alexandre Bayen, and Peter L. Bartlett. Accelerated mirror descent in continuous and discrete time. In NIPS '15: Proceedings of the 29th International Conference on Neural Information Processing Systems, 2015.
[25] Walid Krichene, Benjamin Drighès, and Alexandre M. Bayen. Online lcarning of Nash equilibria in congestion games. SIAM Journal on Control and Optimization, 53(2):1056 2015.
[26] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Progranmingg 133(1-2)336-337,, June 2012.
[27] L. LeBlane, E. K. Morlok, and W. P. Pierskalla. An efficient approach solving the road network equilibrium traffic assignment problem. Transportation Research, 9:309-318, 1975.
[28] Larry J LeBlanc and Mustafa Abdulaal, An efficient dual approach to the urban road network design problem. Computers & Mathematics with Applications, 5(1): 1979.
[29] Kfir Ychuda Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and ac- celeration. In NeurlPS '18: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018.
[30] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. AISTATS '19: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019.
[31] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Compu- tation, 108(2):212-211, 1994.
[32] H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimiza- tion. In COLT 10: Proceedings of the 23rd Annual Conference on Learning Theory, 2010.
[33] Kengo Nakamura, Shinsaku Sakaue, and Norihito Yasuda. Practical frank-wolfe method with decision diagrams for computing wardrop equilibrium of combinatorial congestion games. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2200-2200 2209, 2020.
[34] Arkadi Semen Nemirovski and David Berkovich Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, NY, 1983.
[35] Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence (L1/k)). Proceedings of the USSR Academy of Sciences, (693543-)47) 1983.
[36] Yurii Nesterov. Introductory Lectures on Convex Optimization: Basic Course. Number 87 in Applied Optimization. Kluwer Academic Publishers, 2004.
[37] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematicul Programming, 109())311-3344, 2007.
[38] Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Progranming, 120 (1):221-259, 2009.
[39] Yurii Nesterov. Universal gradient methods for convex optimization problems. Mathematical Program- ming, 152(1-2):381 404, 2015.
[40] Noam Nisan, Tim Roughgarden, Éva Tardos, and V. V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.
[41] Steven O'Hare, Richard Connors, and David P. Walling. Mechanisms that govern how the Price of Anarchy varies with travel demand. Transportation Research, 84:55-80, February 2016.
[42] Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In NIPS '17 Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
[43] Michael Patriksson. The traffic assignment problem: models and methods. Courier Dover Publications, 2015.
[44] Alexander Rakhlin and Karthik Sridharan. Optimization, learning. and games with predictable sequences. In NIPS '13: Proceedings of the 27th International Conference on Neural Information Processing Sys- tems, 2013.
[45] Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236-25 2599, 2002.
12

---

[46] Shai Shalev-Shwariz. Online learning and online convex optimization. Foundations and Trends in Ma- chine Learning, 4(2):107-194, 2011.
[47] Eiji Takimoto and Manfred Warmuth. Path kernels and multiplicative updates. Journal of Machine Learning Research, 4(773-818), 2003.
[48]
Vladimir G. Vovk. Aggregating strategies. In COLT '90: Proceedings of the 3rd Workshop on Computa- tional Learning Theory, pages 371-383, 1990.
[49] John Glen Wardrop. Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, Part volume 1, pages 325-378, 1952.
[50] Lin Xiao, Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543-2596, October 2010.
13


Reviews:
[{"review_id": "gNCvsFsoM4U", "reviewer": "Reviewer_U9xb", "summary": "This paper studies the equilibrium computation of congestion games and proposes a new algorithm, named ADAWEIGHT, that achieves $O(1/\\sqrt{T})$ convergence in the stochastic regime and $O(1/T^2)$ in the static regime. The algorithm has several desirable properties: \n\n1. it attains the best rates in the stochastic and static regimes, \n2. the rates depend on $\\log P$, not on $P$, \n3. it is parameter-agnostic (no knowledge of parameters is needed), \n4. it enjoys any-time guarantee (i.e., last-iterate convergence). \n\nThe results are obtained using some tools: primal and dual extrapolation, weighted-average analysis, and an adaptive learning rate. Experiments confirm the fast convergence of ADAWEIGHT in both regimes, while the existing ACCELEWEIGHT fails to converge in the stochastic regime. \n\n--- After rebuttal ---\n\nI appreciate the authors' kind response. I think the paper provides solid technical results, while the contribution to the ML community is somewhat marginal. Taking those into account, I keep my score of 6. I think the paper would be strengthened if the authors could work more on the smooth trade-off between the stochastic and static regimes. ", "questions": "", "limitations": "", "rating": 6, "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": "The paper is clearly written, and the proposed algorithm is well-positioned in the literature. The proposed algorithm has considerable advantages, as summarized above. On the other hand, I have several concerns and questions as listed below:\n\n\n1. It is shown only experimentally that ACCELEWEIGHT fails to converge in the stochastic regime. Why is it theoretically difficult to guarantee convergence of accelerated methods in the stochastic regime? In my opinion, clarifying this will help improve the significance of the theoretical result.\n\n2. In the experiments, UNIXGRAD, whose convergence rates are the same as ADAWEIGHT regarding $T$ in both regimes, is not presented. What if it is compared with ADAWEIGHT? \n\n3. In (Wang & Abernethy NeurIPS 2018, \"Acceleration through Optimistic No-Regret Dynamics\"), a similar analysis of $\\alpha$-weighted regret is presented. I would like the authors to explain whether there is a connection between the $(\\alpha^t)$-weighted average technique and that of Wang & Abernethy. \n\n4. In my understanding, weight pushing is applicable only to DAGs. This should be mentioned in the last paragraph in Section 3.2 (I would appreciate it if the authors could tell me if I am wrong). \n\n5. Is it possible to extend the proposed algorithm to obtain a parameterized guarantee such that, for $\\rho\\in[1/2, 2]$ representing some degree of randomness, $O(1/T^\\rho)$ is achieved? \n\n6. In practice, the distribution, $\\mathbb{P}$, may also change over time. Could you say something in such cases? \n\nMinor comments: \n\n- It should be noted that if potential functions are strongly convex, $O(\\exp(-T))$ convergence is possible in the static regime, e.g., (Nakamura, Sakaue, Yasuda, AAAI 2020, \"Practical Frank–Wolfe Method with Decision Diagrams for Computing Wardrop Equilibrium of Combinatorial Congestion Games\").  \n\n- Big O notation sometimes hides the $\\log T$ factor of EXPWEIGHT (e.g., in the first sentence in Section 4.1). It is better to use a different notation, e.g., $\\mathcal{O}^*$, for clarity. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are described. The paper seems to have no negative societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "YUtcoEBSUTj", "reviewer": "Reviewer_M6uQ", "summary": "The paper considers the speed on learning to route an equilibrium for in classical network routing models with congestion. The main application could be routing suggestions made by an application such as google maps. \n\nThey consider two versions: \n\n(1) static: when the congestion function is fixed throughout the learning process, called static process. In this case, equilibrium is the minimizer of the potential function, so algorithms minimizing the potential can lead to fast convergence to equilibrium. This leads to a $O(1/T^2)$ error rate as a function of the time. \n\n(2) which is called stochastic, but appears to be worse case instead, where routers can use multiplicative weight, leading to a $O(1/\\sqrt{T})$ error rate. \n\nUnder some smoothness assumption on the congestion functions (bounded and Lipschitz) the paper proposes a \"best-of-both worlds\" algorithm called ADAWeight, that claims to achieve the $O(1/T^2)$ regret in the static case and the $O(1/\\sqrt{T})$ regret in case (2).", "questions": "", "limitations": "", "rating": 5, "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": "The algorithm proposed appears to adapt ideas from the paper [11] in ICML 2019 to achieve the claimed \"best of both worlds\" bounds. I wonder if this would actually give something better: a smooth tradeoff between the worst case and the static case. Something bounding the speed depending on the variation in the latency function with $O(1/T^2)$ with no variability and a maximum of $O(1/\\sqrt{T})$ with variability, with a smooth transition between the two. Is such a bound possible?\n\nFor proving the best of both worlds bound a very short (1/2 a page) proof sketch is provided, which appears to be inaccessible without knowing the details of the paper [11]. \n\nI also wonder if the worst-case bound is the best way to think about a stochastic environment. If the latency function is stochastic: is the assumption that the each iteration is polled independently from a distribution? is better bound possible if that is the case?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I  don't think the proposed work has negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "YSK7o1y5Km_", "reviewer": "Reviewer_GAfB", "summary": "Regret-minimizing routing in nonatomic congestion games is a well-studied topic and it is known that simple, classical algorithms, such as multiplicative weights, fare well in this context. Specifically, such algorithms can converge to an equilibrium at a rate of O(1/√T) when cost functions are noisy. However, this leaves something to be desired; when the environment is static (no perturbations to cost functions are possible), this convergence rate is not optimal, motivating the search for algorithms with faster convergence rates. Such algorithms do exist but might not be robust when perturbations do occur. The key contribution of the paper is an adaptive exponential weights algorithm (ADAWEIGHT) that effectively interpolates between the two algorithmic approaches. An appealing property of ADAWEIGHT is that it does not require knowing the specifics of the environment and is scalable (in the size of the network).", "questions": "", "limitations": "", "rating": 6, "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": "The paper tackles a classical problem (routing in nonatomic congestion games) and presents an interesting perspective on this problem.\n\nWhile the approach is fairly incremental (and interpolates between two well-understood algorithmic schemes), I found the contributions and, in particular, the manner in which these two approaches were welded, interesting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I see no possible negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "8Qz3Pu3aqfB", "reviewer": "Reviewer_GCju", "summary": "The paper analyzes the Adaptive Exponential Weight Updates (AdaWeight) in the learning algorithm for dynamic path recommendations in networks. It shows that it reaches Wardrop Equilibrium at a rate that is a polynomial in the number of paths of the network and the number of epochs. The main contributions of this paper are to display that this algorithm reaches Wardrop Equilibrium in static and stochastic networks without the use of an optimizer.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper provides a detailed theoretical and experimental explanation. The implementation of AdaWeight seems new as it constructs a learning algorithm for both static and stochastic networks. Past approaches have only targeted this for either static or stochastic networks since doing so for both network seems expensive or impractical.\n\nThe paper provides sufficiently sound related work review before proceeding with explaining the background of their work. It seems clear to read and underlines the significance of the framework in the form of a time-optimized network path recommendation algorithm that can learn the network's Wardrop Equilibrium at a rate polynomial in the size of the network and the number of epochs.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The problem that the paper attempts to solve seems novel.\nThe authors seem state the limitations about their claims and their contributions. \nBy providing a clear and concise introduction to the problem and a possible solution to it, the authors open up space and scope for future research.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the question of learning an equilibrium in routing games and provides a  smooth interpolation between static results with O(1/T^2) convergence and worst-case results with O(1/\sqrt{T}) convergence rates. This is a relatively narrow contribution, but the reviewers found the results interesting and technically non-trivial. 
Decision: Accept (Poster)