The Neural Architecture Search (NAS) problem is typically formulated as a graph search problem where the goal is to learn the optimal operations over edges in order to maximize a graph-level global objective. Due to the large architecture parameter space, efficiency is a key bottleneck preventing NAS from its practical use. In this paper, we address the issue by framing NAS as a multi-agent problem where agents control a subset of the network and coordinate to reach optimal architectures. We provide two distinct lightweight implementations, with reduced memory requirements (1/8th of state-of-the-art), and performances above those of much more computationally expensive methods. Theoretically, we demonstrate vanishing regrets of the form O( √ T ), with T being the total number of rounds. Finally, aware that random search is an (often ignored) effective baseline we perform additional experiments on 3 alternative datasets and 2 network configurations, and achieve favorable results in comparison with this baseline and other methods.
In this paper, the authors proposed MANAS, which is based on DARTS, by approximating the problem space by factorizing them into smaller spaces, which will be solved by multiple agents. The authors claimed that this can simplified the search space so that the joint search can be more efficient to enable us to search a larger space faster. While the overall idea seems simple but the coordinating among agents can be difficult, where the authors proposed credit assignment techniques to address the issue. The final algorithm is evaluated on CV datasets as well as 3 new datasets. 
Overall, I found the motivation and proposed solution by the authors convincing. However, in a search space where random searcher is competitive, it is important for us to have an in-depth understanding on the proposed techniques. Especially when the experimental results is not fully comparable (it is difficult to control #params to evaluate the Test Error, and Search Cost being a one-time cost), I think the magnitude of the improvement showed in the experimental results itself might not be enough to justify this new approach. 
I am curious about the how does the number of agents affects the experimental results. It seems that it is not mentioned in the experiment section (or I might missed it?). And do we need to search for the best number of agents, which will add to the search cost?
I am also curious on if one can combine other search algorithms with the similar idea on dividing the search space, e.g., using random search on a subspace in a coordinate descend fashion. It will be great if the authors can provide more in-depth analysis on different component of the proposed algorithm so that we can fully understand the source of improvement.