Research map / Reinforcement learning / Policy gradient and actor-critic
Test Where Decisions Matter: Importance-driven Testing for Deep Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes importance-driven model-based testing (IMT) for deep RL policies that ranks states by how much the agent's decision changes optimistic/pessimistic safety probabilities, samples the policy in top-ranked states, and restricts the MDP, with a clustering extension for scalability.
Problem
Exhaustively testing a trained deep RL policy over its full state space is infeasible, so testing budget must be focused on states where the agent's decisions most affect safety or performance outcomes, with formal guarantees.
Approach
Computes optimistic and pessimistic safety estimates via probabilistic model checking on an MDP, ranks states by the maximal difference between action-wise optimistic estimates, samples the policy only in the top-ranked states to restrict the MDP, and iterates until the estimates converge; clustering lets one test a fraction of each cluster.
Key results
- On the gridworld, IMT verified the full 196-state space for policy pi_1 with only 33 policy samples (|S_s|=145, |S_f|=51, |S_u|=0), while MT needed to sample almost the entire state space.
- On the UAV task, IMT verified policies over 25,517 states, finding safety violations for eta>=0.75 (15 and 775 additional avoidable unsafe states); runtime for eta=0.25 was 269.8 s for IMT vs 1793 s for MT.
- On Atari Skiing (~2.2M states), clustering reduced the required testing budget by up to a factor of 5 for average cluster size 25 compared to IMT without clustering.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add importance-based ranking to policy sampling | model-based testing (MT) · Slippery Gridworld, π1 | runtime (seconds): 25.62(±1.8) -> 12.29(±0.7) | Helped |
| add importance-based ranking to policy sampling | model-based testing (MT) · UAV Reach-Avoid, η=0.1 | runtime (seconds): 1793sec. (±21.7) -> 269sec. (±5.5) | Helped |
| add importance-based ranking to policy sampling | model-based testing (MT) · UAV Reach-Avoid, η=0.25 | runtime (seconds): 2227sec. (±0.2) -> 320sec. (±16.1) | Helped |
| add importance-based ranking to policy sampling | model-based testing (MT) · UAV Reach-Avoid, η=0.5 | runtime (seconds): 2570sec. (±125.4) -> 1264sec. (±3.8) | Helped |
| add importance-based ranking to policy sampling | model-based testing (MT) · UAV Reach-Avoid, η=0.75 | runtime (seconds): 2844sec. (±34.3) -> 1383sec. (±4.4) | Helped |
| add importance-based ranking to policy sampling | model-based testing (MT) · UAV Reach-Avoid, η=1.0 | runtime (seconds): 4016sec. (± 6.23) -> 2422sec. (± 3.87) | Helped |
| add clustering and test only a fraction of states per cluster | IMT · Atari Skiing | testing budget: up to a factor of 5 | Helped |
| increase cluster size (ablation) | IMTc · Atari Skiing | testing effort around unsafe regions | Hurt |
Limitations
- Assumes the policy under test is deterministic; stochastic policies are not supported.
- Clustering can over-approximate unsafe regions and may miss unsafe behavior when clusters are not sufficiently similar.
- Requires a discrete MDP model of the environment, which limits applicability to continuous domains.
Experimental setup
Datasets: Farama Minigrid slippery gridworld UAV reach-avoid drone environment (Badings et al.) Atari Skiing
Benchmarks: Slippery Gridworld UAV reach-avoid task Atari Skiing
Metrics: number of verified safe states number of verified failure states policy samples / test cases required runtime
Baselines: MT (model-based testing without importance ranking) RT (random testing) IMT without clustering
Builds on: Tempest Chockler et al. causal importance ranking stable-baselines3 DQN
Closest papers by meaning
- A Risk-Sensitive Approach to Policy Optimization (AAAI 2023 · similarity 0.88)
- Exploring Safer Behaviors for Deep Reinforcement Learning (AAAI 2022 · similarity 0.87)
- Safety Representations for Safer Policy Learning (ICLR 2025 · similarity 0.86)
- Adaptive Learn-then-Test: Statistically Valid and Efficient Hyperparameter Selection (ICML 2025 · similarity 0.86)
- Sampling-Based Safe Reinforcement Learning (NeurIPS 2026 · similarity 0.86)
- Safeguarded Progress in Reinforcement Learning: Safe Bayesian Exploration for Control Policy Synthesis (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.