Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper focuses on the network load balancing problem in data centers using multi-agent RL paradigm. The main goal in load balancing problems is to minimize the makespan
The authors prove various properties of the setting with the main result to be that such setting is a Markov Potential Game. They showed this result via properly defining a workload distribution fairness potential function. Moreover, using facts established in Leonardos et al, they design a distributed algorithm to approximate Nash equilibrium policies. The authors provide an extensive experimental section that suggest that the proposed algorithm is effective.
strengths_and_weaknesses: Pros
The paper is interesting, with both theoretical and applied merits and an interesting modeling of the network load balancing prblems in data centers as a MARL system. 
Cons: The result of the proposed framework to be a Markov potential game is not very surprising as load balancing games are known to be potential games (see [Koutsoupias, Papadimitriou 99]).

questions: What was the main technical difficulty that did not allow the authors to provide theoretical guarantees for their proposed algorithm?
limitations: This work has no negative societal impact as far as the reviewer can forsee.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes MPG-based MARL solution for the load-balancing problem. Applying RL directly for load-balancing is not favorable as the load balancers (i.e., multiple-agents) need to synchronize observations as well as the action space grows with number of agents (requiring re-training etc.)
strengths_and_weaknesses: **Strengths**
1. Does not require re-training with increasing number of multiple agents as the proposed approach decomposes
the joint state and action space.
2. Does not require synchronization between the load balancers


**Weakness**
1. Poor evaluation
  * No scaling experiments (i.e., increasing number of LBs or servers). Only 2 LBs in evaluation. If the paper had scaled the experiments more they would find that their approach may not be practical for real DCs (discussed later). 
  * No real traffic/workload. The supposedly real benchmark is a mocked up small testbed that does not mimic real distribution of traffic or scale. 
  * Experimentally weak: no variation in traffic and limited variation of IO/CPU
  * What about QoS (99th percentile behavior, an important metric to evaluate for LBs)?
2. Invalid and inconsistent assumptions wrt problem statement.
  * In the intro, the paper claims that "existing algorithms are not adaptive to due to dynamic environments" yet the assumption made in this paper is that each server is capable of processing a certain amount of workload v_j, which is a number only dependent on server capabilities and not on the request (or traffic type itself). For example, a GET request of type X can take 2s whereas a another GET request of type Y can take 20s. The paper mentions collided elephants and yet does not provide any experiments that the proposed technique can handle such situations. In other words, v_j should be stochastic and not fixed on just the server but also on the request characristics. 
  * previous assumption invalidates most of the derivation presented later in the paper. 

  * Another assumption is that active probing is impractical. However, it is okay for LBs to communicate with severs to observe the server state, why? There is no citation or experiment showing that indeed that is a reasonable assumption. All of the work is based on this key assumption. 

3. Limited insights:
  * why Markov Potential Games for handling the stated problem? Why not use mean-field theorem to approximate the behavior of all the other multi-agents using mean or median behavior. Overall the paper reads as an application of MPG rather than "there is a nice solution" to the load-balancing problem. Insights and analysis of different approaches are missing. 
 * No evaluation of the overhead of the RL vs MARL solution in terms of performance as well as overhead (to justify MARL is needed over RL). There are several solutions proposed such as RLB-SAC (Neurips 2021) which reports similar high performance, and Park: An Open Platform for Learning-Augmented Computer Systems. 
 * What happens if RL makes bad decisions (safety of RL: Towards safe online reinforcement learning in computer systems, NeurIPS 2021).

4. Writing needs significant improvement esp. introduction and related work section.  
     * citations on key assumptions/claims or experiments to make those statements
    * Abbreviations introduced without describing what it stands for?: e.g. NE for MPG


questions: Please clarify the questions and limitations raised in the weakness section above. 
limitations: * Limited evaluation
* Strong assumptions for a practical system
* No comparison with other ML-based approaches.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers the load balancing problem in a network of multiple heterogenous servers, and multiple load balancers.  The authors formulate the problem as a multi agent reinforcement learning problem, and specifically consider a Markova potential game.

The settings is that of multiple load balancers, each responsible for sending jobs to a set of servers.  There might be overlaps in the set of servers the various load balancers serve, and the load balancers thus have partial observability of the system state.  Using the cumulative total fairness as the potential function, where fairness is defined as either variance fairness or product fairness, the authors show that the job allocation game where the objective is to minimize the makespan while maximizing the variance fairness or product fairness, is a Markov potential game.  
strengths_and_weaknesses: A network with multiple load balancers managing load to multiple and overlapping servers is a complex problem.  The interactions between the load balancers is such that a closed form solution to the balancing problem is not evident.  This approach of setting a potential game within a RL environment is interesting and seems novel.

The authors propose a distributed load balancing method where each agent independently learns a policy, through policy gradient methods. The reward function is set to be per-LB variance or product fairness.  The authors show that maximizing for these local fairness metrics is sufficient tor minimizing makespan, a global metric. 
The exact model, with respect to overlap of servers among the load balancers, is not clear.  Are all servers allocated jobs by all LBers? What do the results look like with partial overlaps? This seems to be a harder problem.  


questions: Are all servers allocated jobs by all LBers? 
What do the results look like with partial overlaps? This seems to be a harder problem.  
limitations: The experimentation doesn’t include comparison with classical methods such as LSQ.  It would be interesting to see how a distributed, blind, greedy LSQ compares to the distributed MARL method proposed here, especially since the computation costs are so vastly different.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a distributed Multi-agent Reinforcement Learning based approach for load balancing at the network layer formulated as a Markov Potential game.

Current network load balancers have limited observability over the workloads and servers performance and are prone to misconfiguration due to heterogeneity and elasticity. Centralized approaches (CTDE) incur an additional overhead from centralized communication. This work addresses this by using a local variance-based fairness function in each load balancer which, when maximized, can minimize the potential function of the Markov potential game. This approximates the Nash equilibrium of the game.

strengths_and_weaknesses: ## Strengths
* Significant gains by using proposed design over current in-production load balancing algorithms
* Strong theoretical foundation of formulating load balancing as a multi-agent RL-based Markov potential game
* Well written paper that puts the pieces of the design in an easy to understand order

## Weaknesses
* DCs typically have high bandwidth for internal communication. The paper states that centralized communication leads to heavy overhead which is not convincing in the main paper. The evaluation section mentions it in passing as being evaluated in the appendix but I feel it would be helpful to show in the main paper.
* Not sure if I agree with "large-scale" DC networks having only 20 servers. The largest of data centers have thousands of servers and load balancers. This makes the real-world setup slightly less impressive.
* Fault tolerance not evaluated in the paper (in terms of failed requests leading to incorrect job completion estimates for next time period, network partitions etc.)

questions: * This work addresses load balancing in a single data center but I think it can easily be extended to a multi-DC setup by capitalizing on the low-observability approximation. Have you considered this?
* Have you considered including some offline learning as the intial state? System logs from data centers usually provide good information about request patterns and existing data center hardware.
* What is the rationale behind using 2/3 agents in Fig 2b?
* Did you consider other kinds of traffic other than wiki (database heavy) and static? (video for example)
* Are the numbers in Tables 1/2 mean or median?
* Nitpick: Page 3, line 100 should say [M] denotes the set of LB agents {1,...,M} instead of set of servers
* Nitpick: Specs for the real world setup would be helpful to compare to existing DCs

limitations: * The paper doesn't seem to address elastic setups even though their motivation included both heterogeneous and elastic infrastructures.
* Simulator not as complex as real-world (addressed in paper). Still allows to test parts of the system without stochastic network parameters. These could be synthetically injected though.
* Need for low communication overhead in DC is not motivated strongly. Centralized methods (QMix for example) still show comparable performance in some application setups.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper explores the task of multi-agent network load balancing via formulation as a Markov potential game, using workload distribution fairness as a potential function. A MARL algorithm is proposed based on this formulation and provides for fully-decentralized learning. The paper further develops an event-based simulator which, along with a real-world network setup, is used to evaluate the proposed algorithm against several MARL baselines. 
strengths_and_weaknesses: Strengths:
+ Rigorous formulation of network load balancing as MPG with proofs that appear sound.
+ Generally interesting and well-motivated application for MARL with promising potential

Weaknesses:
- Concern regarding representativeness of baselines used for evaluation
- Practical benefits in terms of communication overhead & training time could be more strongly motivated

Detailed Comments:

Overall, the paper was interesting to read and the problem itself is well motivated. Formulation of the problem as an MPG appears sound and offers a variety of important insights with promising applications. There are, however, some concerns regarding evaluation fairness and practical benefits.

The baselines used for evaluation do not seem to accurately represent the state-of-the-art in CTDE. In particular, there have been a variety of recent works that explore more efficient strategies (e.g., [1-3]) and consistently outperform QMix with relatively low inter-agent communication. Although the proposed work appears effective as a fully-decentralized approach, it is unclear how well it would perform against more competitive CTDE baselines. Comparison against these more recent works would greatly improve the strength of evaluation.

Benefits in terms of reduced communication overhead could also be more strongly motivated. Presumably, communication between agents could be done over purpose-built inter-LB links, thus avoiding QoS degradation due to contention on links between LBs and servers. Even without inter-LB links, the increase in latency demonstrated in Appendix E.2.2 appears relatively low.

Robustness against dynamic changes in network setup are discussed to some degree, but it’s unclear how significant this issue is in a real-world environment. Even in a large-scale setup, the number of LBs/servers is likely to remain fairly constant at the timescales considered in this work (i.e., minutes). Given this, it seems that the paper should at least discuss trade-offs with a longer training time, which could impact the relative benefits of various approaches. 

Some confusion in notation:
-	Algorithm 2, L8 should be t = 1,…,H (for horizon)?
-	L100, [M] denotes the set of LBs?

Minor notes:
-	Some abbreviations are not defined, e.g., “NE” on L73
-	Superscript notation in Eq 6 is not defined until much later (L166), which hindered understanding in an initial read.

[1] S. Zhang et al, “Efficient Communication in Multi-Agent Reinforcement Learning via Variance Based Control”, NeurIPS 2019.
[2] Z. Ding et al, “Learning Individually Inferred Communication for Multi-Agent Cooperation”, NeurIPS 2020.
[3] T. Wang et al, “Learning Nearly Decomposable Value Functions Via Communication Minimization”, ICLR 2020.

questions: - Is there any reason why the work cannot compare against more recent CTDE schemes?
- Comments on other concerns?

limitations: n/a
review_title: null

Meta-review: metareview: The paper received an uniformly positive evaluation, although all the scores are in the "borderline / weak accept" range. The authors included a long and comprehensive rebuttal and actively participated in the discussion, which made some of the reviewers updating their scores.

I recommend the paper to be accepted, but I understand the decision could be reverted when comparing the paper with the other candidates.
confidence: Less certain
Decision: Accept