# Neural Architecture Search via Combinatorial Multi-Armed Bandit

arXiv: https://arxiv.org/abs/2101.00336 · HTML: https://mlsanity.com/paper/2101.00336/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 40 references that are in the map.
- First posted on arXiv 1 Jan 2021.

## Builds on (most cited first, 29 of 29)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications](https://mlsanity.com/paper/1704.04861/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Improved Regularization of Convolutional Neural Networks with Cutout](https://mlsanity.com/paper/1708.04552/) (2017)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware](https://mlsanity.com/paper/1812.00332/) (2018)
- [Progressive Neural Architecture Search](https://mlsanity.com/paper/1712.00559/) (2017)
- [SNAS: Stochastic Neural Architecture Search](https://mlsanity.com/paper/1812.09926/) (2018)
- [PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search](https://mlsanity.com/paper/1907.05737/) (2019)
- [Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation](https://mlsanity.com/paper/1904.12760/) (2019)
- [Understanding and Robustifying Differentiable Architecture Search](https://mlsanity.com/paper/1909.09656/) (2019)
- [FBNetV2: Differentiable Neural Architecture Search for Spatial and Channel Dimensions](https://mlsanity.com/paper/2004.05565/) (2020)
- [Fair DARTS: Eliminating Unfair Advantages in Differentiable Architecture Search](https://mlsanity.com/paper/1911.12126/) (2019)
- [EcoNAS: Finding Proxies for Economical Neural Architecture Search](https://mlsanity.com/paper/2001.01233/) (2020)
- [MiLeNAS: Efficient Neural Architecture Search via Mixed-Level Reformulation](https://mlsanity.com/paper/2003.12238/) (2020)
- [Densely Connected Search Space for More Flexible Neural Architecture Search](https://mlsanity.com/paper/1906.09607/) (2019)
- [Understanding Architectures Learnt by Cell-based Neural Architecture Search](https://mlsanity.com/paper/1909.09569/) (2019)
- [AtomNAS: Fine-Grained End-to-End Neural Architecture Search](https://mlsanity.com/paper/1912.09640/) (2019)
- [AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search](https://mlsanity.com/paper/1903.11059/) (2019)
- [DeepArchitect: Automatically Designing and Training Deep Architectures](https://mlsanity.com/paper/1704.08792/) (2017)
- [Theory-Inspired Path-Regularized Differential Network Architecture Search](https://mlsanity.com/paper/2006.16537/) (2020)
- [Anti-Bandit Neural Architecture Search for Model Defense](https://mlsanity.com/paper/2008.00698/) (2020)
- [Finding Competitive Network Architectures Within a Day Using UCT](https://mlsanity.com/paper/1712.07420/) (2017)

## Built on by (most cited first, 5 of 5)

- [Automated Quantum Circuit Design with Nested Monte Carlo Tree Search](https://mlsanity.com/paper/2207.00132/) (2022)
- [Quantum Circuit Design using a Progressive Widening Enhanced Monte Carlo Tree Search](https://mlsanity.com/paper/2502.03962/) (2025)
- [A Bandit Approach with Evolutionary Operators for Model Selection](https://mlsanity.com/paper/2402.05144/) (2024)
- [Combinatorial Rising Bandits](https://mlsanity.com/paper/2412.00798/) (2024)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)

## Abstract (arXiv)

Neural Architecture Search (NAS) has gained significant popularity as an effective tool for designing high performance deep neural networks (DNNs). NAS can be performed via policy gradient, evolutionary algorithms, differentiable architecture search or tree-search methods. While significant progress has been made for both policy gradient and differentiable architecture search, tree-search methods have so far failed to achieve comparable accuracy or search efficiency. In this paper, we formulate NAS as a Combinatorial Multi-Armed Bandit (CMAB) problem (CMAB-NAS). This allows the decomposition of a large search space into smaller blocks where tree-search methods can be applied more effectively and efficiently. We further leverage a tree-based method called Nested Monte-Carlo Search to tackle the CMAB-NAS problem. On CIFAR-10, our approach discovers a cell structure that achieves a low error rate that is comparable to the state-of-the-art, using only 0.58 GPU days, which is 20 times faster than current tree-search methods. Moreover, the discovered structure transfers well to large-scale datasets such as ImageNet.