Automatically searching for neural network architectures for reinforcement learning agents is expensive. A large part of the cost is not training but judging: to decide which candidate network is better, current methods such as SEARL run each candidate through full episodes in the environment and compare the returns. Most of those episode steps carry no information about the comparison. Work on "critical states" shows that in most of an episode, any reasonable action leads to the same outcome, and a trained policy can be swapped for a trivial default action in roughly 70 to 90 percent of states without losing much reward. Two candidate networks that differ only in how they act in those states get the same score. The evaluation signal comes almost entirely from the few moments where the choice of action changes what happens next.
We propose to spend the evaluation budget on those moments. Candidates are compared by saving simulator snapshots along the incumbent policy's trajectories. We sample snapshots in proportion to how critical they look, run short branched rollouts from each one (the candidate acts first, then the incumbent takes over, with shared random seeds), and reweight the results so that the fitness estimate stays unbiased even when the criticality estimate is poor. The claim is that this criticality-weighted branched estimate ranks candidate architectures as accurately as full-episode evaluation while using several times fewer environment steps. The claim is also falsifiable: the gain should shrink on tasks where criticality is spread uniformly across states.
Core Claim
The performance difference lemma says that the gap in expected return between a candidate policy $\pi_c$ and an incumbent $\pi_0$ equals the candidate's average advantage under the incumbent's value function:
$$J(\pi_c) - J(\pi_0) = \frac{1}{1-\gamma}\,\mathbb{E}_{s \sim d^{\pi_c}}\big[A^{\pi_0}(s, \pi_c(s))\big].$$
Here $J$ is expected discounted return, $\gamma$ the discount, $d^{\pi_c}$ the candidate's discounted state distribution, and $A^{\pi_0}(s,a)$ the advantage of taking action $a$ in state $s$ and then following $\pi_0$. In states where every action has nearly the same value, $A^{\pi_0}$ is close to zero for any candidate, so those states add sampling noise to a full-episode return comparison but no signal. We estimate the gap by importance sampling. States $s_i$ are drawn from the incumbent's stored trajectories with probability $q(s) \propto \max(c(s), \epsilon)\, d^{\pi_0}(s)$, where $c(s)$ is a criticality score. The estimate is
$$\widehat{\Delta}(\pi_c) = \frac{1}{N}\sum_{i=1}^{N} \frac{d^{\pi_0}(s_i)}{q(s_i)}\,\hat{A}^{\pi_0}(s_i, \pi_c(s_i)).$$
Each $\hat{A}$ is a short branched rollout from a restored snapshot: the candidate acts at $s_i$ and the incumbent continues for $H$ steps. It is paired, with common random numbers, against the incumbent acting at $s_i$. Using $d^{\pi_0}$ in place of $d^{\pi_c}$ is the same first-order approximation used in conservative policy iteration. It is appropriate here because the mutations in Lamarckian search, where offspring inherit the parent's weights, are small. The floor $\epsilon$ keeps the estimator unbiased under that approximation no matter how wrong $c(s)$ is. A bad criticality score costs variance, not correctness. This matters because the criticality literature depends heavily on oracles.
Relation to Prior Work
The motivation comes from critical-state research. Ranking Policy Decisions replaces a trained policy with a default action in most states and keeps 90% of reward while querying the network in 31% of CartPole states and 10% of Breakout states. Test Where Decisions Matter verifies policies by querying only states with wide optimistic–pessimistic safety bounds. The Concept of Criticality in Reinforcement Learning defines criticality as the spread of action values and uses it to set update horizons. All three study a single fixed, already-trained network. We use the same observation to decide how candidate architectures are compared during search.
The criticality score uses the max–min action-value gap from Interactive Teaching Strategies for Agent Training, computed from the population's shared critic. We borrow one idea from State Relevance for Off-Policy Evaluation, which suppresses importance weights in states where returns do not depend on the action. That paper needs discretized states for its t-tests. We avoid discretization because we branch from real snapshots instead of grouping logged samples.
The search setting is SEARL (Sample-Efficient Automated Deep Reinforcement Learning) and its predecessor ACN (Neural Architecture Evolution in Deep Reinforcement Learning for Continuous Control). Both share one replay buffer across the population but score candidates with full episodes that treat every state alike. We keep their training loop and change only the fitness function.
The closest bridge between criticality and efficiency, Saliency-Aware Quantized Imitation Learning, weights a distillation loss by state saliency so that a fixed network can be quantized. It neither searches architectures nor estimates fitness. PoRank ranks finished policy checkpoints offline with a learned transformer. We rank live candidates online, and our estimator is unbiased without learning any ranker.
Two lines of work set limits on the design. Rethinking Performance Estimation in NAS warns that cheap estimators can preserve local rankings and still lose global ones, so we measure both. The AutoRL survey argues that static supervised proxies fail when the data distribution shifts during RL training, which is why we do not rely on zero-cost proxies computed at initialization.
Research Program
We build a drop-in fitness module for SEARL on top of TD3 (continuous control) and Rainbow DQN (discrete control). During each generation's training phase, the incumbent, meaning the elite from the previous generation, records simulator snapshots at every $k$-th step. MuJoCo allows restoring the full physics state, and the Arcade Learning Environment can clone emulator state. At evaluation time, each snapshot is scored with the shared critic's action-value gap. For discrete actions we take the gap over all actions. For continuous actions we take it over a small set of perturbed actions around the policy's output.
The module then draws $N$ snapshots by criticality and runs paired $H$-step branched rollouts for each candidate. Candidates are ranked by $\widehat{\Delta}$. Branched rollouts for different candidates reuse the same snapshots and seeds, so between-candidate comparisons share noise. This is the source of variance reduction beyond the reweighting.
We will analyze three things. The first is how estimator variance scales with $N$, $H$, and how concentrated criticality is. The prediction is that the variance ratio against uniform sampling tracks the squared coefficient of variation of $|A^{\pi_0}|$ across states, which is the standard importance-sampling result. The second is how much bias the $d^{\pi_0}$ approximation introduces as mutation size grows. The third is whether a critic-free criticality score works nearly as well, which would remove the dependence on the critic entirely. That score is the variance of returns across a handful of random-action branches, the "suspense" measure from Hanging in the Balance.
Baselines
The naive reference point is a fixed-architecture TD3 or Rainbow agent with the default [400, 300] network, trained for the same number of environment steps. It shows whether architecture search pays off at all under the budget. ACN reports that this default network fails on Humanoid, while an evolved [672, 508] network succeeds, so the naive baseline is weak on Humanoid and competitive on Ant and HalfCheetah.
The strongest existing method is unmodified SEARL with full-episode fitness. We run it from the authors' configuration with the same population size, mutation operators, and total environment steps, counting evaluation steps and training steps together. The file reports SEARL's advantage only as a 10x sample-efficiency improvement over random search and population-based training on MuJoCo. It gives no absolute returns; we found no reported result on Lacuna for SEARL's per-task final return. We therefore rerun SEARL ourselves with identical seeds and hardware. To beat it, our variant must reach SEARL's final median return in at most half the total environment steps, or achieve higher return at equal steps, across at least three of the five MuJoCo tasks with non-overlapping 95% bootstrap intervals over 10 seeds.
A budget-matched variant of SEARL gives each candidate the same number of evaluation steps as our method, spent as truncated or fewer full episodes. The ablation that isolates the key ingredient keeps snapshots, branching, and common random numbers but samples snapshots uniformly. Any gap between this ablation and our method is attributable to criticality weighting alone. A second ablation uses a random criticality score, which checks that the $\epsilon$ floor keeps the estimate unbiased. We also include a zero-environment-step baseline that scores each candidate by the shared critic's value of its actions on replay-buffer states, with both uniform and criticality-weighted versions. Finally, we include the zero-cost proxies synflow and nwot from NAS-Bench-Suite-Zero, computed on replay-buffer batches. All methods use the same tuning budget for their own evaluation hyperparameters, a small grid of five settings each.
Why not just…?
Why not just evaluate each candidate with fewer or shorter full episodes? Truncating episodes keeps the early, mostly non-critical part of each trajectory and drops later events, such as a humanoid falling, that often decide the comparison. Using fewer episodes lowers cost but leaves the noise from uninformative states in place. SEARL's weaker results on Reacher, which has very short episodes, suggest the fitness signal is already fragile when evaluation is thin. The budget-matched SEARL baseline tests this directly. If it matches our rank correlation, the proposal fails.
Why not just score candidates with the shared critic and use no environment steps at all? This is the most serious threat, because it is nearly free. Its weakness is that the critic was trained on the population's own data and shares errors with the actors, overestimation in particular. A mutant that exploits a critic error would score well and act badly. Our estimator uses the critic only to choose where to sample, never as the measured value. We run both the uniform and criticality-weighted versions of critic scoring. If either tracks true return as well as branched rollouts, we will report that critic scoring is the better tool and reframe the contribution around it rather than argue against it.
Why not just use zero-cost proxies? NAS-Bench-Suite-Zero finds that raw proxies largely track parameter count and FLOPs. In RL, ACN finds that the best architecture is sometimes larger (Humanoid) and sometimes smaller (Ant, HalfCheetah). A size-tracking proxy cannot capture that task dependence. We include synflow and nwot so the data can decide.
Why not just adjust full-episode fitness with training-log covariates? Can Training Logs Make Model Comparisons More Precise? finds that covariate adjustment widens confidence intervals at about ten runs. That is the regime of a single generation's population, so we do not expect it to help much. It is complementary to our method and can be layered on top as a secondary check.
Proposed Experiments and Decisive Checks
The main testbed is MuJoCo HalfCheetah, Walker2d, Hopper, Ant, and Humanoid under TD3-SEARL, plus a small set of Atari games under Rainbow-SEARL, including Breakout, where Ranking Policy Decisions found criticality to be highly concentrated.
The first decisive check isolates estimation from search. Each generation, we compute a "true" fitness for every population member from 50 full evaluation episodes. We then plot Spearman rank correlation and top-1 regret against environment steps spent, for every fitness estimator. Following Rethinking Performance Estimation in NAS, we report correlation both within a generation (local) and across pooled generations (global).
The second check is end-to-end search: final return against total environment steps, and the architectures found. We want to know whether our method still discovers the wider networks needed for Humanoid.
The third check is a falsification test built around criticality concentration. We measure the Gini coefficient of $|A^{\pi_0}|$ over states for each task. We predict that our method's step savings grow with this concentration. We expect small gains on steady locomotion like HalfCheetah and larger gains on tasks with rare failure modes, such as Humanoid, Hopper, and Breakout. A flat relationship would mean the benefit comes from branching and common random numbers, not criticality, and the uniform-snapshot ablation would then be the real result.
As a sanity check, we use a gridworld with a few planted bottleneck states and a fully enumerable population. There, true advantages can be computed exactly, so we can confirm the estimator's unbiasedness and its predicted variance ratio before trusting the deep RL results.
References
- Ranking Policy Decisions
- Test Where Decisions Matter: Importance-driven Testing for Deep Reinforcement Learning
- The Concept of Criticality in Reinforcement Learning
- Interactive Teaching Strategies for Agent Training
- State Relevance for Off-Policy Evaluation
- Sample-Efficient Automated Deep Reinforcement Learning
- Neural Architecture Evolution in Deep Reinforcement Learning for Continuous Control
- Saliency-Aware Quantized Imitation Learning for Efficient Robotic Control
- PoRank: A Practical Framework for Learning to Rank Policies
- Rethinking Performance Estimation in Neural Architecture Search
- Automated Reinforcement Learning (AutoRL): A Survey and Open Problems
- Hanging in the Balance: Pivotal Moments in Crisis Counseling Conversations
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies
- Can Training Logs Make Model Comparisons More Precise?