# BR-NS: an Archive-less Approach to Novelty Search

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 31 references that are in the map.
- First posted on arXiv 8 Apr 2021.

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

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions](https://mlsanity.com/paper/1901.01753/) (2019)
- [Quality and Diversity Optimization: A Unifying Modular Framework](https://mlsanity.com/paper/1708.09251/) (2017)
- [A Primer on the Signature Method in Machine Learning](https://mlsanity.com/paper/1603.03788/) (2016)
- [Meta Learning Shared Hierarchies](https://mlsanity.com/paper/1710.09767/) (2017)
- [AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence](https://mlsanity.com/paper/1905.10985/) (2019)
- [A survey on intrinsic motivation in reinforcement learning](https://mlsanity.com/paper/1908.06976/) (2019)
- [Autonomous skill discovery with Quality-Diversity and Unsupervised Descriptors](https://mlsanity.com/paper/1905.11874/) (2019)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [The iisignature library: efficient calculation of iterated-integral signatures and log signatures](https://mlsanity.com/paper/1802.08252/) (2018)
- [Embedding and learning with signatures](https://mlsanity.com/paper/1911.13211/) (2019)
- [Unsupervised Learning and Exploration of Reachable Outcome Space](https://mlsanity.com/paper/1909.05508/) (2019)
- [Hierarchical Behavioral Repertoires with Unsupervised Descriptors](https://mlsanity.com/paper/1804.07127/) (2018)
- [The Benefits of Over-parameterization at Initialization in Deep ReLU Networks](https://mlsanity.com/paper/1901.03611/) (2019)
- [Novelty Search makes Evolvability Inevitable](https://mlsanity.com/paper/2005.06224/) (2020)
- [Character-level Chinese Writer Identification using Path Signature Feature, DropStroke and Deep CNN](https://mlsanity.com/paper/1505.04922/) (2015)

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

- [Relevance-guided Unsupervised Discovery of Abilities with Quality-Diversity Algorithms](https://mlsanity.com/paper/2204.09828/) (2022)
- [Online Damage Recovery for Physical Robots with Hierarchical Quality-Diversity](https://mlsanity.com/paper/2210.09918/) (2022)
- [Quality Diversity under Sparse Reward and Sparse Interaction: Application to Grasping in Robotics](https://mlsanity.com/paper/2308.05483/) (2023)
- [Discovering and Exploiting Sparse Rewards in a Learned Behavior Space](https://mlsanity.com/paper/2111.01919/) (2021)
- [Hierarchical Quality-Diversity for Online Damage Recovery](https://mlsanity.com/paper/2204.05726/) (2022)
- [Discount Model Search for Quality Diversity Optimization in High-Dimensional Measure Spaces](https://mlsanity.com/paper/2601.01082/) (2026)
- [Geodesics, Non-linearities and the Archive of Novelty Search](https://mlsanity.com/paper/2205.03162/) (2022)

## Abstract (arXiv)

As open-ended learning based on divergent search algorithms such as Novelty Search (NS) draws more and more attention from the research community, it is natural to expect that its application to increasingly complex real-world problems will require the exploration to operate in higher dimensional Behavior Spaces which will not necessarily be Euclidean. Novelty Search traditionally relies on k-nearest neighbours search and an archive of previously visited behavior descriptors which are assumed to live in a Euclidean space. This is problematic because of a number of issues. On one hand, Euclidean distance and Nearest-neighbour search are known to behave differently and become less meaningful in high dimensional spaces. On the other hand, the archive has to be bounded since, memory considerations aside, the computational complexity of finding nearest neighbours in that archive grows linearithmically with its size. A sub-optimal bound can result in "cycling" in the behavior space, which inhibits the progress of the exploration. Furthermore, the performance of NS depends on a number of algorithmic choices and hyperparameters, such as the strategies to add or remove elements to the archive and the number of neighbours to use in k-nn search. In this paper, we discuss an alternative approach to novelty estimation, dubbed Behavior Recognition based Novelty Search (BR-NS), which does not require an archive, makes no assumption on the metrics that can be defined in the behavior space and does not rely on nearest neighbours search. We conduct experiments to gain insight into its feasibility and dynamics as well as potential advantages over archive-based NS in terms of time complexity.