Identification of Unexpected Decisions in Partially Observable Monte-Carlo Planning: a Rule-Based Approach
This work addresses the problem of interpreting and identifying unexpected decisions in POMCP policies, which is crucial for developers and users of AI systems in safety-critical applications. It offers an incremental improvement in interpretability for POMCP.
This paper introduces a rule-based methodology using Satisfiability Modulo Theory (SMT) to analyze Partially Observable Monte-Carlo Planning (POMCP) policies by inspecting their traces. The method identifies unexpected decisions by defining logical formulas describing belief-action relationships and solving MAX-SMT problems to find parameters that maximize satisfied clauses. The approach achieved an improvement of the Area Under Curve up to 47% in identifying unexpected decisions compared to state-of-the-art anomaly detection methods.
Partially Observable Monte-Carlo Planning (POMCP) is a powerful online algorithm able to generate approximate policies for large Partially Observable Markov Decision Processes. The online nature of this method supports scalability by avoiding complete policy representation. The lack of an explicit representation however hinders interpretability. In this work, we propose a methodology based on Satisfiability Modulo Theory (SMT) for analyzing POMCP policies by inspecting their traces, namely sequences of belief-action-observation triplets generated by the algorithm. The proposed method explores local properties of policy behavior to identify unexpected decisions. We propose an iterative process of trace analysis consisting of three main steps, i) the definition of a question by means of a parametric logical formula describing (probabilistic) relationships between beliefs and actions, ii) the generation of an answer by computing the parameters of the logical formula that maximize the number of satisfied clauses (solving a MAX-SMT problem), iii) the analysis of the generated logical formula and the related decision boundaries for identifying unexpected decisions made by POMCP with respect to the original question. We evaluate our approach on Tiger, a standard benchmark for POMDPs, and a real-world problem related to mobile robot navigation. Results show that the approach can exploit human knowledge on the domain, outperforming state-of-the-art anomaly detection methods in identifying unexpected decisions. An improvement of the Area Under Curve up to 47\% has been achieved in our tests.