Test Where Decisions Matter: Importance-driven Testing for Deep Reinforcement Learning

Summary

This paper proposes a model-based method for testing the safety properties of Deep Reinforcement Learning (DRL). The method computes a ranking of state importance across the entire state space, dividing the state space into safe and unsafe regions. The approach provides optimal test-case selection and guaranteed safety by providing formal verification guarantees over the entire state space. The method is evaluated on several examples, showing it discovers unsafe policy behavior with low testing effort.

Strengths

+ The paper introduces a novel method to rank state importance across the entire state space, which further assist the testing procedure. + The use of optimistic and pessimistic safety estimates provides a range of expected outcomes and is interesting + The authors conduct a detailed evaluation of the method on several popular DRL tasks and demonstrate its effectiveness.

Weaknesses

- Some technical details should be explained more clearly. - The authors doesn't compare IMT with the SOTA DRL testing method, like [15] mentioned by the authors in the paper.

Questions

In general, the idea of ranking the importance of the state and leveraging it as the testing guidance is very interesting. I believe this work would have a certain impact on the further development of DRL testing. There are a few technical points unclear. 1. Page 2, Line 60. It would be good if the authors gave a more concrete concept of the formal guarantee provided by IMT, like probabilistic certification. 2. Page 5, Line 175. What do you mean by "significantly larger"? Do you perform statistical testing here? Moreover, some related work is missing: - Gerasimou, Simos, Hasan Ferit Eniser, Alper Sen, and Alper Cakan. "Importance-driven deep learning system testing." In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering, pp. 702-713. 2020. - Song, Jiayang, Xuan Xie, and Lei Ma. "$\mathtt {SIEGE} $: A Semantics-Guided Safety Enhancement Framework for AI-enabled Cyber-Physical Systems." IEEE Transactions on Software Engineering (2023). - Shi, Ying, Beibei Yin, and Zheng Zheng. "Multi-granularity coverage criteria for deep reinforcement learning systems." Journal of Systems and Software 212 (2024): 112016.

Rating

7

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, the authors address it in the guideline.

Summary

This paper proposed a novel model-based importance-driven framework for testing trained DRL policies. By focusing on testing the cases with higher importance ranks, the proposed framework improves the testing scalability. The evaluation of several case studies demonstrates that the proposed framework can more efficiently discover unsafe policy behavior with low testing effort.

Strengths

1. The paper is well-structured and easy to follow. 2. The idea of testing on important samples is interesting.

Weaknesses

1. The definition of the safety formula $\phi$ and the formula for calculating $\mathbb{P}\_{\mathcal{M}^\pi, \phi}$ should be stated clearly. 2. The current framework depends on several human-defined thresholds, for instance, $\delta_{\phi}$, $\epsilon_{\phi}$ $\delta_{i}$. How those parameters are determined and sensitive to the final testing result should be discussed more clearly. 3. The current framework is shown to be applicable in a discrete state and action space. It would be nice to see the discussion on the potentials and limitations applied to the continuous state and action space.

Questions

1. The importance ranking is based on the maximal difference between the optimistic estimates concerning the available actions, which considers the impact of decisions on the optimistic estimates. Why not use the pessimistic estimate, as it is more concerned about safety violations?

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

No

Summary

This paper presents a framework called importance-driven model based testing for RL models. ​ It uses a model-based approach to compute estimates of safety based on the MDP explored so far using the policy and ranks the importance of states based on the impact of decisions on safety. Then it samples the policy on these state to further restrict the MDP. ​ The framework provides formal verification guarantees and partitions the state space into safe and unsafe regions. ​ The authors also propose a version to cluster similar states to further reduce the number of samples but at the cost of a relaxed guarantees. Experimental evaluations on different environments of various sizes demonstrate its effectiveness in reducing number of samples needed compared to random sampling both with and without the model. ​

Strengths

- **Relevance**: Policy testing is an important area of research in reinforcement learning. - **Novelty**: The paper introduces a novel algorithm that uses model-based approaches to reduce sample complexity while providing strong guarantees. - **Soundness and clarity**: The experiments are thorough. The results clearly illustrate the system's effectiveness and are presented clearly with appropriate images and plots. Figure 2, in particular, best illustrates the effectiveness of this system.

Weaknesses

Some of the weaknesses of this paper are: - The approach relies on very strict assumptions on having a model for the environment with fixed set of states and actions, which could be very restricting for real world RL tasks. - The introduction and abstract could better motivate and establish the problem. Currently, they only explain the algorithm without much context. For example, it is not clear how the safety estimates are computed until sections 2 and 3 or why computing them iteratively is easier than sampling the action on every state.

Questions

- How can number of policy queries in Fig 3c be greater than the number of states in the environment? - For runtimes, it will also be useful to break it down into model checking and policy sampling times for both IMT and MT approaches. - Please add legends to Figure 3

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors briefly talk about limitation about the requirements of the current approach, but they could definitely expand a bit more on these limitations early on the paper.

Summary

This work looks into the RL testing problem. RL policies are complex and hard to understand in terms of safety and performance. This work aims to test the policies via states in which the agent’s decisions have the highest impact on the expected outcome. This paper proposes a model-based method to compute a ranking of state importance and focus the testing on the highest-ranked states. The evaluation covers multiple benchmarks and shows that this approach can find unsafe policies.

Strengths

1. RL testing is important and few works touched on this. 2. The idea of using the highest impact states to test the policies is interesting and seems effective.

Weaknesses

1. The guarantee about the correctness of the ranking does not seem to be clarified. Do you iterate over all the actions in the action set? What if the action space is large and continuous? 2. The testing is based on probabilistic model checking instead of worst-case checking. It would be good to bring out this in the abstract and introduction explicitly.

Questions

1. How is the ranking computed? Do you cover continuous space? 2. What’s the scalability of this approach? Are there any cases where testing fails?

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

The limitations are not discussed in the main test.

Summary

The paper proposes an algorithm (IMT) to test a deterministic policy in finite MDPs where a model of the MDP is available. The primary contributions of the paper are algorithmic and empirical. IMT works by iteratively partitioning the state space into safe, unsafe or undetermined. Using the MDP model, IMT is able to construct optimistic and pessimistic bounds on the property being tested (e.g., safety). These estimates are used to identify the states with the largest gap in their optimistic estimates between any pair of actions. IMT prioritizes testing these states next, which has the effect of tightening the bounds and taking the largest possible step towards convergence and halting. The final result includes a partitioning of the state space into safe and unsafe states, which is valuable feedback for improving the policy (offline). The paper also includes a clustering-based variant to scale the algorithm to larger MDPs. Experiments on 3 domains demonstrate the utility of IMT against a random baseline and a variant which does not rank the states.

Strengths

+ The paper studies the important problem of verifying black-box policies used in control applications. This is an important question as RL-learned controllers are deployed more widely. Advances here are likely to be of significant interest to the community. + The paper is well written. The main ideas, algorithms, ideas and experiments are generally explained clearly. Although some important implementation details are missing, the paper is nevertheless easy to read. + The proposed algorithm is intuitively clear and using the estimates to identify "important" states to test next seems to work well. In cases where a model of the discrete MDP is available (or perfectly learnable), this seems like a useful technique to rigorously test a policy and uncover states where the policy does not behave safely. The experiments and appendices include a good amount of detail.

Weaknesses

- The paper does not provide sufficient detail on important algorithmic implementation details. Examples include the prerequisites for the algorithm (simulators, CTL), implementation of `computeEstimates`, $e_opt(s, a, n)$, clustering similarity/distance function, etc. - The assumption of a correct model of the MDP is a somewhat large one in many domains. A discussion of the effort needed to obtain such a model would improve the paper and make its applicability to new domains clearer. Additionally, exploring the use of noisy simulators with varying levels of noise in the dynamics would be really interesting to see. As the paper mentions in Line 331, being able to leverage models of the environment learned from data is likely to increase the applicability. However, these are likely to include noisy dynamics so an experimental evaluation of the impact of noisy dynamics in the current experimental setup would have strengthened the paper. - A comparison to stronger baselines would make it easier to assess the empirical contributions of the paper. Currently, the only comparison is to random testing. Comparing safety-violation detection rates against black-box policy testers (e.g., MDPFuzz, STARLA) using the same budget would have helped place this paper in the larger body of work on DRL testing as well as understand the applicability of these techniques in domains with different characteristics (size, model availability or learnability, etc.).

Questions

- What is the exact implementation of `computeEstimates`? How does it scale with the size of the input (restricted) MDP? Similarly, how exactly is $e_opt(s, a, n)$ estimated? - What steps are involved in adding a new domain from scratch? How easy or hard is it to create the simulator, specify the CTL objective, etc.? - Is it feasible to quantify or conduct investigations into how AMT might handle noise in the transition function in the current experimental setup? - What is the precise definition of a robust policy in Line 195? - What is the computational cost of the clustering approach used here? Should it be reflected in the complexity analysis in Lines 214 - 219? - How does the quality of the resulting clusters affect performance? Does Alg 2 degrade gracefully as cluster quality decreases? - Is it necessary to use a different mechanism (sink states) to restrict the MDP when clustering? How does terminating the trajectory at the sink state affect the e_opt, e_pes estimates, if at all? Does the approach still work if the restriction mechanism from Alg 1 is used? - Does it make sense to compare safety-violation detection rates against other baselines (MDPFuzz, STARLA)? - Does it make sense to consider continuous state and / or action MDPs using this framework? If yes, what modifications might be needed to make it work on cMDPs?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes

Re. author response

I thank the authors for their detailed response to the reviewers. After reading the response, other reviews and comments, I've increased my score to "Weak Accept". While I don't think there's anything technically wrong with the paper, there are a number of major assumptions being made, which might reduce the applicability of the proposed approach. The performance of the proposed method is not explored on abstract or learned models of the environment, which is the most likely scenario. Including these experiments would significantly strengthen the paper, in my opinion. In the absence of these, it becomes challenging to evaluate the paper for impact and overall utility.