Novelty Search

Title: Novelty search

Novelty search is a search algorithm, introduced by Joel Lehman and Kenneth O. Stanley in 2011, that replaces the traditional objective-based fitness function with a behavior-based novelty metric. Instead of rewarding an individual for being closer to a goal, novelty search rewards it for behaving differently from previously encountered individuals. Behavioral difference is computed as the distance between the individual's behavior characterization (a vector summarizing the agent's trajectory, final state, or other observable signatures) and its k-nearest neighbors in the archive of already-discovered behaviors. The algorithm's central claim is that, especially in deceptive domains where objective fitness gradients lead search away from the goal, abandoning the objective entirely can be more effective: the archive of behaviors grows outward, and useful stepping stones appear without ever being selected for.

The technique is the foundational primitive of the Quality-Diversity (QD) family of algorithms, which combine a novelty or behavior metric with an optional local quality objective. MAP-Elites, the canonical QD algorithm, discretizes the behavior space into a grid of cells and stores the highest-performing individual in each cell. Dominated novelty search and other variants explicitly account for local competition among individuals that occupy similar behavior regions. The same archive-and-behaviors-distance machinery has been ported from evolutionary search to gradient-based optimization (where novelty-augmented loss functions encourage policy diversity), to quality-diversity neural architecture search, and to large-language-model decoding (where behavior characterizations derived from output diversity metrics steer generation toward novel regions of output space).

Novelty search is closely related to curiosity-driven exploration in reinforcement learning and to intrinsic-motivation methods more broadly. All three reward the agent for visiting under-explored regions of an accessible space. The distinction is genealogical. Curiosity-driven RL defines novelty in terms of prediction error on a learned forward model (Pathak et al. 2017, ICM). Count-based and Random Network Distillation bonuses define it in terms of visitation frequency in an embedding space. Novelty search, by contrast, originated in evolutionary computation and defines novelty through behavioral distance metrics in hand-designed or learned behavior spaces. The three lineages have since converged in practice, and modern exploration papers routinely combine behavioral novelty bonuses with prediction-error bonuses. The conceptual heritage differs, and novelty search remains the right name when the algorithmic frame is evolutionary search or quality-diversity optimization rather than policy-gradient RL.

The practical implications of novelty search have been demonstrated across robotics (acquiring diverse grasping repertoires without object-level rewards), game level generation (producing varied, playable layouts), image generation (steering diffusion sampling toward novel outputs), and protein engineering (exploring regions of sequence space beyond the natural-protein manifold). Its main limitation is the behavior characterization: the algorithm rewards whatever the behavior space encodes, so a poorly chosen characterization produces incoherent or useless diversity. Selecting or learning behavior characterizations remains an active research front.