Reinforcement Learning for NAS

The core component is a controller, typically a Recurrent Neural Network (RNN). This agent operates in a Markov Decision Process (MDP) where:

• State: The partial architecture description generated so far.
• Action: The selection of the next architectural component (e.g., layer type, filter size).
• Policy: The controller's strategy for selecting actions, parameterized by its own weights, which are optimized via RL. The controller sequentially samples a complete architecture string, which is then built and trained to obtain a reward.

The reward function is the critical link between architecture quality and controller learning. It is typically the validation accuracy of the child network after training. Key design considerations include:

• Sparse and Noisy: The reward is only provided after the lengthy process of training a child network to convergence, making credit assignment challenging.
• Normalization: Rewards are often normalized (e.g., using a moving baseline) to reduce variance and stabilize training.
• Multi-Objective Rewards: For hardware-aware NAS, the reward can be a composite function, e.g., Accuracy * (Latency/Target)^-α, to trade off performance with efficiency.

The controller's policy is optimized using Reinforcement Learning algorithms, most commonly policy gradient methods like REINFORCE. The core update rule increases the probability of actions that led to high rewards.

• REINFORCE: The gradient is estimated as: ∇J(θ) ≈ Σ_t (R_t - b) ∇_θ log π(a_t|s_t; θ), where b is a baseline (e.g., average reward) to reduce variance.
• Proximal Policy Optimization (PPO): A more advanced, stable alternative that constrains policy updates to avoid destructive large steps. The controller learns to generate architectures with higher expected rewards over many episodes.

The search space is the universe of all possible architectures the controller can generate. It must be expressive yet constrained for tractable search. Common paradigms include:

• Cell-Based Search: The controller designs a normal and reduction convolutional cell, which are then stacked to form the full network (e.g., NASNet, ENAS). This enables transfer across datasets.
• Macro Search: The controller defines the entire network macro-architecture, including layer count and connections.
• Operation Choices: At each step, the controller selects from primitives like conv 3x3, sep_conv 5x5, max_pool 3x3, identity, or zero (skip connection).

Training each child network from scratch is computationally prohibitive. Weight sharing is the key efficiency innovation in RL-NAS:

• A single supernet (or one-shot model) encapsulates all possible architectures in the search space.
• When the controller samples an architecture, a corresponding subgraph is carved from the supernet and evaluated without training from scratch.
• The supernet's weights are trained concurrently with the controller's policy (e.g., ENAS). This reduces search cost from thousands of GPU days to a few, making RL-NAS feasible.

The controller must balance exploration (trying novel architectural choices) and exploitation (refining known good patterns). This is managed by:

• The stochastic policy π(a|s), which inherently explores by sampling actions.
• Entropy Regularization: Adding a term to the reward that encourages policy entropy, preventing premature convergence to a suboptimal deterministic policy.
• The RL algorithm's inherent mechanisms (e.g., PPO's clipped objectives). Effective exploration is crucial to avoid getting stuck in local optima of the architecture space.

RL-NAS has produced foundational architectures that outperform human-designed counterparts. Key examples include:

• NASNet: Discovered by Zoph et al. (2018), this was a landmark RL-NAS model that found convolutional cell structures achieving state-of-the-art accuracy on ImageNet. The controller, an RNN, generated string descriptions of normal and reduction cells.
• AmoebaNet: An architecture discovered using an evolutionary algorithm with aging evolution, a population-based method closely related to RL paradigms. It demonstrated superior performance and became a standard benchmark.
• EfficientNet: While its scaling method is systematic, the base EfficientNet-B0 model was discovered via NAS (using a multi-objective RL search optimizing for both accuracy and FLOPS), leading to a family of highly efficient models.

RL-NAS has been applied to automate the design of efficient transformers and recurrent networks.

• Evolved Transformer: This architecture was discovered using evolutionary search (a sibling methodology to RL) to find novel self-attention and recurrent cell structures that outperformed the standard Transformer on machine translation tasks with fewer parameters.
• Hardware-Aware NLP Models: RL controllers have been tasked with finding architectures that maximize accuracy under strict latency constraints on target devices (e.g., mobile phones), leading to specialized models for tasks like on-device text prediction and named entity recognition.

A critical application is co-designing neural architectures with deployment hardware constraints.

• MobileNetV3: While partially human-designed, its final architecture was refined using hardware-aware NAS, where an RL-based controller searched for optimal layer configurations (kernel sizes, expansion ratios) to maximize accuracy for a target latency on mobile CPUs.
• Search Objectives: The reward signal is often a composite metric, e.g., Reward = Accuracy - λ * (Latency), where λ controls the trade-off. The controller learns to generate architectures that satisfy real-world deployment specs.

To reduce the prohibitive cost of training each candidate from scratch, modern RL-NAS often employs weight-sharing within a supernet.

• ENAS (Efficient Neural Architecture Search): Pioneered weight-sharing for RL-NAS. The controller RNN samples sub-graphs (architectures) from a large directed acyclic graph (the supernet). All sampled architectures share weights from this supernet, allowing performance estimation in minutes instead of days.
• Process: The controller's policy is updated using REINFORCE, with the reward being the validation accuracy of a child network after a short training period using the shared weights. This dramatically improves search efficiency.

RL-NAS has been extended to dense prediction tasks requiring specialized decoder heads and backbone connections.

• Auto-DeepLab: Adapted RL-NAS for semantic image segmentation. The controller searched for both the cell-level microstructure and the network-level macro-architecture (feature map resolutions and connection paths), outperforming human-designed models like DeepLabv3+ on Cityscapes and PASCAL VOC.
• NAS-FPN: Used RL to search for feature pyramid network architectures for object detection, discovering novel top-down and lateral connections that improved upon the manually designed FPN in RetinaNet and Mask R-CNN frameworks.

Neural Architecture Search (NAS) is the overarching subfield of AutoML focused on algorithmically discovering high-performing neural network architectures for a given dataset and task, replacing manual design. Core methodologies include:

• Reinforcement Learning (RL): An agent learns a policy to generate architectures.
• Evolutionary Algorithms: Architectures are evolved via selection, mutation, and crossover.
• Gradient-Based Methods (e.g., DARTS): The search space is relaxed to be differentiable. The primary objective is to optimize a reward signal, typically the trained model's accuracy on a validation set.

Differentiable Architecture Search (DARTS) is a gradient-based NAS method that formulates the search over discrete architectural choices (e.g., which operation to use between two nodes) as a continuous relaxation. This allows the architecture parameters (alpha) and the model weights (w) to be optimized jointly via standard gradient descent in a bilevel optimization problem. It significantly reduces search cost compared to RL-based methods but can suffer from performance collapse if the continuous relaxation does not faithfully represent the final discrete architecture.

One-Shot NAS is an efficiency paradigm where the entire search space is encoded within a single, over-parameterized supernet. Candidate architectures are evaluated as subgraphs of this supernet, sharing its weights. This eliminates the need to train each candidate from scratch. Weight sharing is the core technique, but it introduces the problem of weight coupling, where the performance of a standalone trained architecture may not correlate well with its performance when evaluated using the shared weights, potentially biasing the search.

Hardware-Aware NAS extends the search objective beyond just accuracy to include deployment constraints like inference latency, memory footprint, or energy consumption. The search is formulated as a multi-objective optimization problem, often targeting the Pareto front—the set of architectures representing optimal trade-offs between accuracy and the hardware metric. For example, an RL agent's reward can be a composite function: R = Accuracy - λ * Latency. This is critical for deploying models on edge devices, mobile phones, or specialized accelerators (NPUs).

Evolutionary NAS uses evolutionary algorithms, inspired by biological evolution, to search for optimal architectures. It maintains a population of candidate architectures. Each iteration (generation), architectures are selected based on fitness (e.g., validation accuracy). New candidates are created through mutation (e.g., adding a layer, changing an operation) and crossover (combining parts of two parent architectures). While often computationally expensive, evolutionary methods are highly parallelizable and can escape local optima, making them effective for complex, non-differentiable search spaces.

The search space is the formally defined set of all possible neural network architectures an NAS algorithm can explore. Its design is a critical prior that constrains and guides the search. Common paradigms include:

• Cell-Based Search Spaces: Search for a optimal computation cell (e.g., a normal cell and a reduction cell), which is then stacked repetitively to form the full network. This reduces dimensionality.
• Macro Search Spaces: Search over the full network topology, including the number of layers, layer types, and connectivity.
• Hierarchical Search Spaces: Search at multiple levels of abstraction (e.g., outer network layout and inner cell structure). A poorly designed search space cannot yield a high-performing model, regardless of the search algorithm's sophistication.