Venue: ICLR 2021 Conference

Reviews:

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

- Is the Lipschitz constant known? If not, is there a way to test this assumption?  
- I think the authors mean that the regret R_t is \sum_{r=1}^t E[c_r-c*_r]. 
- 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?  
- 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. 
- 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 

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

[Score updated From 6 to 5]

review_title: Nice contribution

final_score: rating: 3: Clear rejection
review_content: 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. 

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

However, there are a number of issues in the paper that makes the overall contribution questionable, as I list below.

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

[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

[2] Qin, Chen, and Zhu. Contextual Combinatorial Bandit and its Application on Diversified Online Recommendation. SDM'2014

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

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

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

- 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.
review_title: The paper studies online learning for routing in a city network (a graph) from adversarially given source to destinations and under adversarially given current flow on each road segment (edges), for a fixed but unknown congestion function. 

final_score: rating: 7: Good paper, accept
review_content: 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.

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

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

The main ideas behind the analysis are well explained at an intuitive level.

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

The definition of x_{max}^t on page 2 looks wrong because the max is over t.
review_title: An interesting extension of combinatorial semi-bandits

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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.

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

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

I 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.
review_title: Interesting (theoretical) algorithm

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