Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).
main_review: The paper tackles a classical problem (routing in nonatomic congestion games) and presents an interesting perspective on this problem.

While 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.
limitations_and_societal_impact: I see no possible negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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.

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


limitations_and_societal_impact: The problem that the paper attempts to solve seems novel.
The authors seem state the limitations about their claims and their contributions. 
By 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.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

They consider two versions: 

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

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

Under 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).
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?

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

I 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?
limitations_and_societal_impact: I  don't think the proposed work has negative societal impact
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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: 

1. it attains the best rates in the stochastic and static regimes, 
2. the rates depend on $\log P$, not on $P$, 
3. it is parameter-agnostic (no knowledge of parameters is needed), 
4. it enjoys any-time guarantee (i.e., last-iterate convergence). 

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

--- After rebuttal ---

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


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

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

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

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

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

6. In practice, the distribution, $\mathbb{P}$, may also change over time. Could you say something in such cases? 

Minor comments: 

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

- 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. 
limitations_and_societal_impact: The limitations are described. The paper seems to have no negative societal impacts.
review_title: null

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)