# MDPFuzz: Testing Models Solving Markov Decision Processes

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 101 references that are in the map.
- First posted on arXiv 6 Dec 2021.

## Builds on (most cited first, 30 of 50)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [CARLA: An Open Urban Driving Simulator](https://mlsanity.com/paper/1711.03938/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [End to End Learning for Self-Driving Cars](https://mlsanity.com/paper/1604.07316/) (2016)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [ChauffeurNet: Learning to Drive by Imitating the Best and Synthesizing the Worst](https://mlsanity.com/paper/1812.03079/) (2018)
- [Learning by Cheating](https://mlsanity.com/paper/1912.12294/) (2019)
- [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)
- [Machine Learning Testing: Survey, Landscapes and Horizons](https://mlsanity.com/paper/1906.10742/) (2019)
- [Adversarial Policies: Attacking Deep Reinforcement Learning](https://mlsanity.com/paper/1905.10615/) (2019)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Controlling Overestimation Bias with Truncated Mixture of Continuous Distributional Quantile Critics](https://mlsanity.com/paper/2005.04269/) (2020)
- [Robust Deep Reinforcement Learning with Adversarial Attacks](https://mlsanity.com/paper/1712.03632/) (2017)
- [End-to-End Model-Free Reinforcement Learning for Urban Driving using Implicit Affordances](https://mlsanity.com/paper/1911.10868/) (2019)
- [Self-Driving Cars: A Survey](https://mlsanity.com/paper/1901.04407/) (2019)
- [DeepGauge: Multi-Granularity Testing Criteria for Deep Learning Systems](https://mlsanity.com/paper/1803.07519/) (2018)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Fairness Testing: Testing Software for Discrimination](https://mlsanity.com/paper/1709.03221/) (2017)
- [Guiding Deep Learning System Testing using Surprise Adequacy](https://mlsanity.com/paper/1808.08444/) (2018)
- [Delving into adversarial attacks on deep policies](https://mlsanity.com/paper/1705.06452/) (2017)
- [Vulnerability of Deep Reinforcement Learning to Policy Induction Attacks](https://mlsanity.com/paper/1701.04143/) (2017)
- [Automated Directed Fairness Testing](https://mlsanity.com/paper/1807.00468/) (2018)
- [Adaptive Stress Testing for Autonomous Vehicles](https://mlsanity.com/paper/1902.01909/) (2019)

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

- [Decictor: Towards Evaluating the Robustness of Decision-Making in Autonomous Driving Systems](https://mlsanity.com/paper/2402.18393/) (2024)
- [ROCAS: Root Cause Analysis of Autonomous Driving Accidents via Cyber-Physical Co-mutation](https://mlsanity.com/paper/2409.07774/) (2024)
- [Test Where Decisions Matter: Importance-driven Testing for Deep Reinforcement Learning](https://mlsanity.com/paper/2411.07700/) (2024)
- [Exploring Critical Testing Scenarios for Decision-Making Policies: An LLM Approach](https://mlsanity.com/paper/2412.06684/) (2024)
- [Navigating the Edge with the State-of-the-Art Insights into Corner Case Identification and Generation for Enhanced Autonomous Vehicle Safety](https://mlsanity.com/paper/2503.00077/) (2025)
- [Surrogate Fitness Metrics for Interpretable Reinforcement Learning](https://mlsanity.com/paper/2504.14645/) (2025)
- [DiCriTest: Testing Scenario Generation for Decision-Making Agents Considering Diversity and Criticality](https://mlsanity.com/paper/2508.11514/) (2025)
- [NeSy-CSA: A Neuro-Symbolic Framework for Open-Ended Critical Scenario Attribution](https://mlsanity.com/paper/2607.03847/) (2026)
- [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)

The Markov decision process (MDP) provides a mathematical framework for modeling sequential decision-making problems, many of which are crucial to security and safety, such as autonomous driving and robot control. The rapid development of artificial intelligence research has created efficient methods for solving MDPs, such as deep neural networks (DNNs), reinforcement learning (RL), and imitation learning (IL). However, these popular models solving MDPs are neither thoroughly tested nor rigorously reliable. We present MDPFuzz, the first blackbox fuzz testing framework for models solving MDPs. MDPFuzz forms testing oracles by checking whether the target model enters abnormal and dangerous states. During fuzzing, MDPFuzz decides which mutated state to retain by measuring if it can reduce cumulative rewards or form a new state sequence. We design efficient techniques to quantify the "freshness" of a state sequence using Gaussian mixture models (GMMs) and dynamic expectation-maximization (DynEM). We also prioritize states with high potential of revealing crashes by estimating the local sensitivity of target models over states. MDPFuzz is evaluated on five state-of-the-art models for solving MDPs, including supervised DNN, RL, IL, and multi-agent RL. Our evaluation includes scenarios of autonomous driving, aircraft collision avoidance, and two games that are often used to benchmark RL. During a 12-hour run, we find over 80 crash-triggering state sequences on each model. We show inspiring findings that crash-triggering states, though they look normal, induce distinct neuron activation patterns compared with normal states. We further develop an abnormal behavior detector to harden all the evaluated models and repair them with the findings of MDPFuzz to significantly enhance their robustness without sacrificing accuracy.