# Search-Based Testing of Reinforcement Learning

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 46 references that are in the map.
- First posted on arXiv 7 May 2022.

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

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [DeepMind Control Suite](https://mlsanity.com/paper/1801.00690/) (2018)
- [Deep Reinforcement Learning at the Edge of the Statistical Precipice](https://mlsanity.com/paper/2108.13264/) (2021)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [DeepXplore: Automated Whitebox Testing of Deep Learning Systems](https://mlsanity.com/paper/1705.06640/) (2017)
- [DeepTest: Automated Testing of Deep-Neural-Network-driven Autonomous Cars](https://mlsanity.com/paper/1708.08559/) (2017)
- [The NetHack Learning Environment](https://mlsanity.com/paper/2006.13760/) (2020)
- [DeepGauge: Multi-Granularity Testing Criteria for Deep Learning Systems](https://mlsanity.com/paper/1803.07519/) (2018)
- [The Art, Science, and Engineering of Fuzzing: A Survey](https://mlsanity.com/paper/1812.00140/) (2018)
- [Adaptive Shielding under Uncertainty](https://mlsanity.com/paper/2010.03842/) (2020)
- [Deep Reinforcement Fuzzing](https://mlsanity.com/paper/1801.04589/) (2018)
- [FuzzerGym: A Competitive Framework for Fuzzing and Learning](https://mlsanity.com/paper/1807.07490/) (2018)
- [Nyx-Net: Network Fuzzing with Incremental Snapshots](https://mlsanity.com/paper/2111.03013/) (2021)

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

- [A Search-Based Testing Approach for Deep Reinforcement Learning Agents](https://mlsanity.com/paper/2206.07813/) (2022)
- [Testing of Deep Reinforcement Learning Agents with Surrogate Models](https://mlsanity.com/paper/2305.12751/) (2023)
- [SMARLA: A Safety Monitoring Approach for Deep Reinforcement Learning Agents](https://mlsanity.com/paper/2308.02594/) (2023)
- [Boundary State Generation for Testing and Improvement of Autonomous Driving Systems](https://mlsanity.com/paper/2307.10590/) (2023)
- [Rule-Guided Reinforcement Learning Policy Evaluation and Improvement](https://mlsanity.com/paper/2503.09270/) (2025)
- [Test Where Decisions Matter: Importance-driven Testing for Deep Reinforcement Learning](https://mlsanity.com/paper/2411.07700/) (2024)
- [Surrogate Fitness Metrics for Interpretable Reinforcement Learning](https://mlsanity.com/paper/2504.14645/) (2025)
- [Speedrunning and path integrals](https://mlsanity.com/paper/2403.13008/) (2024)
- [Uncovering Systemic and Environment Errors in Autonomous Systems Using Differential Testing](https://mlsanity.com/paper/2507.03870/) (2025)
- [Gimitest: A Comprehensive Tool for Testing Reinforcement Learning Policies](https://mlsanity.com/paper/2607.07029/) (2026)
- [Evaluating Fuzz Testing for Reinforcement Learning Agents](https://mlsanity.com/paper/2607.24577/) (2026)
- [Learning from the Test: Self-Referential Differential Testing for Deep RL Agents](https://mlsanity.com/paper/2608.22284/) (2026)
- [DreamTest: World-Model Surrogates for Search-Based Testing of Deep Reinforcement Learning Agents](https://mlsanity.com/paper/2610.04494/) (2026)

## Abstract (arXiv)

Evaluation of deep reinforcement learning (RL) is inherently challenging. Especially the opaqueness of learned policies and the stochastic nature of both agents and environments make testing the behavior of deep RL agents difficult. We present a search-based testing framework that enables a wide range of novel analysis capabilities for evaluating the safety and performance of deep RL agents. For safety testing, our framework utilizes a search algorithm that searches for a reference trace that solves the RL task. The backtracking states of the search, called boundary states, pose safety-critical situations. We create safety test-suites that evaluate how well the RL agent escapes safety-critical situations near these boundary states. For robust performance testing, we create a diverse set of traces via fuzz testing. These fuzz traces are used to bring the agent into a wide variety of potentially unknown states from which the average performance of the agent is compared to the average performance of the fuzz traces. We apply our search-based testing approach on RL for Nintendo's Super Mario Bros.