# Provably Sub-Linear Two-Timescale NeuroEvolution with Online Plasticity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 55 references that are in the map.
- First posted on arXiv 18 Jun 2026.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Evolving Deep Neural Networks](https://mlsanity.com/paper/1703.00548/) (2017)
- [Differentiable plasticity: training plastic neural networks with backpropagation](https://mlsanity.com/paper/1804.02464/) (2018)
- [Evolution-Guided Policy Gradient in Reinforcement Learning](https://mlsanity.com/paper/1805.07917/) (2018)
- [Eligibility Traces and Plasticity on Behavioral Time Scales: Experimental Support of neoHebbian Three-Factor Learning Rules](https://mlsanity.com/paper/1801.05219/) (2018)
- [Evolving Reinforcement Learning Algorithms](https://mlsanity.com/paper/2101.03958/) (2021)
- [Meta-Learning through Hebbian Plasticity in Random Networks](https://mlsanity.com/paper/2007.02686/) (2020)
- [Born to Learn: the Inspiration, Progress, and Future of Evolved Plastic Artificial Neural Networks](https://mlsanity.com/paper/1703.10371/) (2017)
- [Neuroevolution is a Competitive Alternative to Reinforcement Learning for Skill Discovery](https://mlsanity.com/paper/2210.03516/) (2022)
- [First Steps Towards a Runtime Analysis of Neuroevolution](https://mlsanity.com/paper/2307.00799/) (2023)
- [Discovering Effective Policies for Land-Use Planning with Neuroevolution](https://mlsanity.com/paper/2311.12304/) (2023)
- [Runtime Analysis of Evolutionary NAS for Multiclass Classification](https://mlsanity.com/paper/2506.06019/) (2025)

## Abstract (arXiv)

NeuroEvolution of Augmenting Topologies (NEAT) is a widely used neuroevolution algorithm for learning neural network architectures and weights for control tasks. However, standard offline optimisation searches for connection strengths directly, which can scale poorly in high-dimensional weight spaces and more difficult continuous control problems. Hybrid methods that combine neuroevolution with online learning can address this challenge, but their theoretical properties remain underexplored. This paper gives the first regret analysis for a general NeuroEvolutionary Online Learning (NEOL) framework, which decouples learning into two timescales: an outer loop for architecture search and an inner loop for online weight adaptation via rewardmodulated plasticity. Under mild conditions, we prove that NEOL achieves sublinear regret. Empirically, under fixed interaction budgets on four standard control benchmarks, a NEAT-based NEOL implementation achieves higher final fitness and lower variance than pure NEAT, and is competitive with strong reinforcement learning (RL) baselines on several tasks. The results are supported byWilcoxon rank-sum tests and ablation studies. Overall, the findings show that online plasticity can improve the sample efficiency and robustness of two-timescale neuroevolution. Code is available at https://github.com/boobaa2001/NeuroEvolution Online Learning NEOL.