Autonomous Capability Assessment of Sequential Decision-Making Systems in Stochastic Settings
Authors: Pulkit Verma
Rushang Karia
Siddharth Srivastava
Venue: NeurIPS 2023 poster (2023)
Keywords: Sequential Decision Making
Interpretable Models
Relational Model Learning
Black-Box Agents
Symbolic Descriptions
TL;DR: Capability Assessment for Sequential Decision-Making Systems

Abstract: It is essential for users to understand what their AI systems can and can't do in order to use them safely. However, the problem of enabling users to assess AI systems with sequential decision-making (SDM) capabilities is relatively understudied. This paper presents a new approach for modeling the capabilities of black-box AI systems that can plan and act, along with the possible effects and requirements for executing those capabilities in stochastic settings. We present an active-learning approach that can effectively interact with a black-box SDM system and learn an interpretable probabilistic model describing its capabilities. Theoretical analysis of the approach identifies the conditions under which the learning process is guaranteed to converge to the correct model of the agent; empirical evaluations on different agents and simulated scenarios show that this approach is few-shot generalizable and can effectively describe the capabilities of arbitrary black-box SDM agents in a sample-efficient manner.

Autonomous Capability Assessment of Sequential Decision-Making Systems in Stochastic Settings
Pulkit Verma, Rushang Karia, and Siddharth Srivastava Autonomous Agents and Intelligent Robots Lab, School of Computing and Augmented Intelligence, Arizona State University, AZ, USA [verma. pulkit, rushang. karia, siddharths @asu. edu
Abstract
is essential for understand what their Al systems can and can't do in order to use them safely. However, the problem of enabling users to assess Al systems with sequential peccisionmmaking (SDM) capabilities is relatively understudied. This paper presents new approach for modeling the capabilities of black-box Al systems that can plan and act, along with the possible effects and requirements for executing those capabilities in stochastic settings. We present an active-learning approach that can effectively interact with a black-box SDM system and learn an interpretable probabilistic model describing its capabilities. Theoretical analysis of the approach identifies the conditions under which the learning process guaranteed to converge to the correct model of the agent; empirical evaluations on different agents and simulated scenarios show that this approach few-shot generalizable and can effectively describe the capabilities of arbitrary black-box SDM agents in a sample-efficient manner.
Introduction
Al systems are becoming increasingly complex, and is becoming difficult even for Al experts to ascertain the limits and capabilities of such systems, they often use black-box policies for their docision-making process [Popov et al., 2017, Greydanus et al., 2018]. E.g., consider an elderly couple with houschold robot that learns and adapts their specific houschold. How would they determine what it can do, what effects their commands would have, and under what conditions? Although making steady progress learning for sequential decision-making (SDM), the problem enabling users to understand the limits and capabilities of their SDM systems is largely unaddressed. Moreover, as the example above illustrates, the absence of reliable approaches for user-driven capability assessment of Al systems limits their inclusivity and real-world deployability.
This paper presents new approach for Query-based Autonomous Capability Estimation (QACE) of black-box SDM systems in stochastic settings. Our approach uses a restricted form of interaction with the input SDM agent (referred to SDMA) learn probabilistic model of its capabilities. The learned model captures high-level isserinterpreetall capabilities, such as the conditions under which an autonomous vehicle could back out of a garage, reach certain target location, along with the probabilities of possible outcomes of executing each such capability. The resulting learned models directly provide interpretable representations of the scope of SDMA's capabilities. They can also be used to enable and support approaches for explaining SDMA's behavior that require closed-form models (e.g., Sreedharan al. [2018]). We assume that the input SDMA provides a minimal query-response interface that is already commonly supported by contemporary SDM systems. In particular, SDMA should reveal capability names defining how each of its capabilities
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

can be invoked, and it should be able to accept user-defined instructions in the form of sequences of such capabilities. These requirements are typically supported by SDM systems by definition.
The main technical problem for QACE is to automatically compute "queries" in the form of instruction sequences and policies, and learn probabilistic model for each capability based SDMA's "responses" in the form of executions. Depending on the scenario, these executions can be in the real world, or in a simulator for safety-critical settings. Since the set of possible queries of this form is exponential in the state space, naive approaches for enumerating and selecting useful queries based on information gain metrics are infeasible.
This paper presents the first approach for query-based assessment of SDMAs in stochastic settings with minimal assumptions on SDMA internals. In addition, it is also the first approach for reducing query synthesis for SDMA assessment to full-observable non-deterministic (FOND) planning [Cimatti et al., 1998]. Empirical evaluation shows that these contributions enable our approach to carry out scalable assessment in both embodied and vanilla SDMAs.
Main contributions
We express the learned models using an input concept vocabulary that is known to the target user group. Such vocabularies span multiple tasks and environments. They can be acquired through parallel streams of research on interactive concept acquisition [Kim et al., 2015, Lage and Doshi-Veles 2020] or explained to users through demonstrations and training [Schulze et al., 2000]. These concepts can be modeled as binary-valucd' predicates that have their associated evaluation functions [Mao et al., 2022]. We use the syntax and semantics of a well-established relational SDM model representation language, Probabilistic Planning Domain Definition Language (PPDDL. [Younes and Littman, 2004), to express the learned models.
Related work on the problem addresses model learning from passively collected observations of agent behavior [Pasula et al., 2007, Martínez et al., 2016, Juba and Stern, 2022]; and by exploring the state space using simulators [Chitnis et al., 2021, Mao et al., 2022]. However, passive learning approaches can learn incorrect models as they do not have the ability to generate interventional or counterfactual data; exploration techniques can be sample inefficient because they don't 't take into account uncertainty and incompleteness in the model being learned to guide their exploration (see Sec. for greater discussion).
In addition to the key contributions mentioned earlier, our results (Sec. 6) show that the approaches for query synthesis in this paper do not place any additional requirements on black-box SDMAs but significantly improve the following factors: (i) convergence rate and sample efficiency for learning relational models of SDMAs with complex capabilities, (ii) few-shot generalizability of learned models to larger environments, and (iii) accuracy of the learned model w.r.t. the ground truth SDMA capabilities. convergence rate to the sound and complete model.
2
Preliminaries
SDMA setup We consider SDMAs that operate in stochastic and fully observable environments. An SDMA can be represented
3-tuple C, where X is the environment state space that the SDMA operates in, C is the set of SDMA's capabilities (capability names, e.g., "place object x at location y" "arrange table x"") that the SIDM can execute, and T X' x C ju is the stochastic black-box transition model determining the effects of SDMA's capabilities on the environment. Here, ptt is the space of probability distributions on X. Note that the semantics of C are not known the user(s) and X' may not be user-interpretable. The only information available about the SDMA is the instruction set in the form of capability names, represented as Cn. This isn' a restricting assumption as the SDMAs must reveal their instruction sets for usability.
Running Example Consider cafe server robot that can pick and place items like plates, cans, etc., from various locations in the cafe, like the counter, tables, etc., and also move between these locations. A capability pick-item (?location ?item) would allow an item like a soda can for any location. However, without knowing its description, the user would not know under what conditions the robot could execute this capability and what the effects will be.
instruct the robot pick up
Object-centric concept representation We aim to learn representations that are generalizable, i.c., the transition dynamics learned should be impervious to environment-specti properties such as num- bers and configurations of objects. Additionally, the learned capability models should hold in different settings of objects in the environment long as the SDMA's capabilities does not change. To this

---

effect, we learn the SDMA's transition model in terms of in- terpretable concepts that can be represented using first-order logic predicates. This is common formalism for express- ing the symbolic models of SDMAs [Zhi-Xuan et al., 2020, Mao et al., 2022]. We formally represent them using a set of object-centric predicates P. The set of predicates used for cafe server robot in Fig. can be (robot-at ?location), (empty-arm), thas-charge), (at ?location ?item), and (holding ?item). Here, precedes an argument that be replaced by an object in the environment. E.g., (robot-at tableRed) means "robot is at the red table." As mentioned earlier, we assume these predicates along with their Boolean evaluation functions (which evaluate to true if predicate is true in state) are available input. Learning such predicates is also an interesting but orthogonal direction of research [Mao et al., 2022, Sreedharan et al., 2022, Das et al., 2023].
The cafe server robot en- vironment in OpenRave simulator.
Figure I:
Abstraction Using object-centric predicate representation induces an abstraction of environment states X' to high-level logical states S expressible in predicate vocabulary P. This abstraction can be formalized using surjective function f X + S. E.g., in the cafe server robot, the concrete state may refer to roll, pitch, and yaw values. On the other hand, the abstract state s corresponding to x will consist of truth values of all the predicates [Srivastava al., 2014, 2016, Mao et al., 2022].
Probabilistic transition model Abstraction induces an abstract transition model T S x C > p.S, where guS is the space of probability distributions on S. This is done by converting each transition (z, c,,²) E T to (s, c, s') E T' using predicate evaluators such that f(x) = and f(x') = s'. Now, T' can be expressed as model M that a set of parameterized action (capability in our case) schema, where each c E C is described as c= (name(c)) (rrme( eff(c)),ff(c) where name(c) E Cy refers to name and arguments (parameters) of pre(c) refers to the preconditions of the capability c represented as a conjunctive formula defined over P that must be true in state to execute c and effic) refers to the set of conjunctive formulas over P, each of which becomes true executing e with an associated probability. The result of executing for model M is state c(s) s' such that Prr(s'(s,c)
(:capability pick-item :parameters (?location ?item) precondition (and (empty-arm) (has-charge) (robot-at ?location)
(at ?location ?item)) efffcct (and (probabilistic 0.7 (and (not (empty-arm))
(not (at ?location ?item)) (holding ?item))
0.2 (and (not (has-charge)))
0.1 (and)))
#No-change
Figure 2: PPDDL description for the cafe server robot's pick-item capability.
0 and one (and only one) of the effects of e becomes true in 8'. We also use (s, ",,c.,) 8') triplet to refer to c(s) = s'. This represen- tation is similar to the Probabilistic Planning Domain Definition Language (PPDDL), which can compactly describe the SDMA's capabilities. E.g., the cafe server robot has three capabilities (shown here as name (args)): pick-itens (?location ?item); place- - ittm (?location ?item); and move (?source ?destination). The description of pick - item in PPDDL is shown in Fig. 2.
Variational Distance Given black-box SDMA A. learn the probabilistic model M representing its capabilities. To measure how close M is to the true SDMA transition model T,,, we use variational distance standard measure in probabilistic-mode learning literature [Pasula al., 2007, Martinez et al., 2016, Ng and Petrick, 2019, Chitnis et al., 2021]. It is based on the total variation distance between two probability distributions T' and M, given as:
8(T', M) = D
Σ (A,D
(Pr(s')s,)) - (
(I)
where D is the set of test samples ((s, c, s') triplets) that we generate using T' to measure the accuracy of our approach. As shown by Pinsker [1964], 8(T', M) v0.5 (xx(T' || M), where DRL is the KL divergence.
3 The Capability Assessment Task
In this work, we aim to learn a probabilistic transition model T' of black-box SDMA as model M, given a set of user-interpretable concepts as predicates P along with their evaluation functions, and the capability names CN corresponding to the SDMA's capabilities. Formally, the assessment task is:
3

---

Definition 1. Given a set of predicates P along with their Boolean evaluation functions, capability names Cx. and a black-box, box SDMA A in a fully observable, stochastic, and static environment, the capability assessment task (A, Cv. (T)) is defined as the task of learning the probabilistic transition model T' of the SDMA A expressed using? P.
The solution to this task is model M that should idcally be the same as T' for correctness. In practice, T' need not be in PPDDL., so the correctness should be evaluated along multiple dimensions.
Notions of model correctness As discussed in Sec. 2, variational distance is one way to capture the correctness of the learned model. This useful when the learned model and the SDMA's model are not in the same representation. The correctness of model can also be measured using qualitative properties such as soundness and completeness. The learned model M should be sound and complete w.r.t. the SDMA's high-level model T i.e. for all combinations of c, 8, and s', if transition (s, c, c, is possible according to T', then it should also be possible under M, and vice versa. Here, (3, c, s') is consistent with M (or T') if (s) > O according to M (or T'). We formally define this as:
Let (A.P, CN, T) be capability assessment task with a learned model M as its solution. M is sound iff each transition (8,c, C, s') consistent with M is also consistent with T M is complete iff every transition that is consistent with T' is also consistent with M.
Definition 2.
This also means that if T' is also a PPDDL model, then (i) any precondition or effect learned as part of M is also present in T' (soundness), and; (ii) all the preconditions and effects present in T should be present in M (completeness). Additionally, a probabilistic model is correct if it is sound and complete, and the probabilities for each effect set in each of its capabilities are the same that of T
Interactive Capability Assessment
To solve the capability assessment task, we must identify the preconditions and effects of each capability in terms of conjunctive formulae expressed over P. At a very high-level, we do this by identifying that probabilistic model can be expressed which has two places where we can add a predicate p. namely precondition and effect. We call these locations within each capability. We then enumerate through these x [C| locations and figure out the correct form of each predicate at each of those locations. To do this we need to consider three forms: (i) adding it as p. i.c., the predicate must be true for that capability precondition), or it becomes true on executing it (when the location is effect); (ii) adding it as not(p), i.e. the predicate must be false for that capability to execute (when the location is precondition), or becomes false on executing it (when the location is effect); (iii) not adding it at all, i.e., the capability execution does not depend on (when the location is precondition), or the capability does not modify it (when the location is effect).
set of capabilities e E C, each of
execute (when the location is
Model pruning Let M represent the set of all possible transition models expressible in terms of P and C. We must prune the set of possible models to solve the capability assessment task, ideally bringing it to singleton. We achieve this by posing queries the SDMA and using the responses to the queries as data to eliminate the inconsistent models from the set of possible models M.
Given location (precondition or effect in capability), the set of models corresponding to predicate will consist of 3 transition models: one each corresponding to the three ways we can add the predicate in that location. We call these three possible models My, Mr, M,, corresponding to adding p (true), not(p) (false), and not adding (ignored), respectively at that location.
Note that the actual set of possible transition models is infinite due to the probabilities associated with each transition. To simplify this, we first constrain the set of possible models by ignoring the probabilities, and learn a non-deterministic transition model (commonly referred to FOND model [Cimatti et al., 1998]) instead of a probabilistic one. We later learn the probabilities using maximum likelihood estimation based on the transitions observed as part of the query responses.
Simulator use Using the standard assumption of a simulator's availability in research on SDM, QACE solves the capability assessment task (Sec. 3) by issuing queries to the SDMA and observing its responses in the form of its execution in the simulator. In non-safety-crittce scenarios, this approach can work without simulator too. The interface required to answer the queries is rudimentary as the SDMA A need not have access to its transition model T' (or T). Rather, it should be able to interact with the environment (or simulator) to answer the queries. We next present the types of queries

---

we use, followed by algorithms for generating them and for inferring the SDMA's model using its responses to the queries.
Policy simulation queries (Qrs) These queries ask the SDMA A to execute a given policy multiple times. More precisely, Qrs query is a tuple (s1; n. G, a, .)) where 87 E S is state, л is partial policy that maps each reachable state to a capability, G is logical predicate formula that expresses a stopping condition, a is an execution cutoff bound representing the maximum number of execution steps, and 7) is an attempt limit. Note that the query (including the policy) is created entirely by our solution approach without any interaction with the SDMA. Qrs queries ask A execute т, 17 times. In each iteration, execution continues until either the stopping goal condition G or the execution bound a is reached. E.g., "Given that the robot, soda- can, platel, bowl3 are at table4, what will happen if the robot follows the following policy: if there is an item on the table and arm is empty, pick up the item; if an item is in the hand and location is not dishwasher, move to the dishwasher; an item is in the hand and location is dishwasher, place the item in the dishwasher?" Such queries will be used to learn both preconditions and effects (Sec. 4.3).
A response to such queries is an execution in the simulator and traces of these simulator executions. Formally, the response Ops for query yPs E Qps a tuple (b, <). where b [T, indicates weather if the SDMA reached a goal state sG } G. and are the corresponding triplets (s, c, generated during the 1 policy executions. If the SDMA reaches sg even once during the r simulations, b is T, representing that the goal can be reached using this policy. Next, we discuss how these responses are used prune the set of possible models and learn the correct transition model of the SDMA.
4.1 Query-based Autonomous Capability Estimation (QACE) Algorithm
We now discuss how solve the capability assessment task using the Query-based Au- tonomous Capability Estimation algorithm (Alg. 1), which works in two phases. In the first phase, QACE learns all capabilities' pre- conditions and nen-deteriiiistic effects us- ing the policy simulation queries (Sec. 4.2). In the second phase, QACE converts the non- deterministic effects of capabilities into prob- abilistic effects (Sec. 4.3). We now explain the learning portion (lines 3-11) in detail.
Algorithm 1: QACE Algorithm
Input predicates P; capability names Cx: state s; SDMA A:; hyperparameters a, 37; FOND Planner p
Output: M
L (pre, eff)) CN 2 M t initializeModel (P,Cx) for each (l. (L, P) do Generate Mp. My by setting p at I in M for each pair M., M, in {MT, Mr, Mr) do
q + generateQuery M,, M,, ax 8, 0 S + getResponse(gg A, M + pruneModels (0 M,,
QACE first initializes a model M* over the predicates in P with capabilities having names CN E Cy- All the preconditions and effects for all capabilities are empty in this initial model. QACE uses M to maintain the current partially learned model. QACE 10 M < hew.ePPobbbliiissSSSccchcifffiid M*)
M + Iearn possible stochastic effects of
capability with eN in using (in 0
iterates over all combinations of L and P 1 return M (line 4). For each pair, QACE creates 3 can-
didate models Mr, Mr. and M, as mentioned earlier. It then takes 2 of these (line 5) and generates
a query q (line 6) such that responses to the query & from the two models are logically inconsistent (see Sec. 4.2). The query g is then posed to the SDMA A whose response is stored as 0 (line 7). QACE finally prunes at least one of the two models by comparing their responses (which are logically inconsistent) with the response P of the SDMA on that query (line 8). QACE also updates the effects of all models in the set of possible models to speed up the learning process (line 9). Finally, learns the probabilities of the observed stochastic effects using maximum likelihood estimation (line 10). An important feature of the algorithm (similar to PLEX [Mehta et al., 201 1] and AIA [Verma et al., 2021]) 1) is that it keeps track of all the locations where it hasn't 't identified the correct way of adding a predicate. The next section presents our approach for generating the queries in line 6.
4.2 Algorithms for Query Synthesis
One of the main challenges interactive model learning is to generate the queries we discussed above and to learn the agent's 's model using them. Although active learning [Settles, 2012] addresses the
5

---

related problem of figuring out which data sets to request labels for, vanilla active learning approaches are not directly applicable here because the possible set of queries expressible using the literals in a domain is vast: it is the set of all policies expressible using Cv- Query-based learning approaches use an estimate of the utility of a query to select "good" queries. This can be a multi-valued measure like information gain [Sollich and Saad, 1994], value [Macke et al., 2021], etc. or a binary-value attribute like distinguishability [Verma et al., 2021], etc. We use distinguishability as a measure to identify useful queries. According to it, query q is distinguishing w.r.t. two models if responses by both models to q are logically inconsistent. We now discuss methods for generating such queries.
Generating distinguishing queries QACE automates the generation of queries using search. As part of the algorithm, a model M is used to generate the three possible models Mr. My, and M, for a specific predicate and location combination. Other than the predicate p at location 1, these models are exactly the same. forward search used to generate the policy simulation queries with two possible models M,, M, chosen randomly from Mr, Mr, and M,. The forward search is initiated with an initial state (s6: s6) as the root of the search tree, where si and si are copies of the same state 80 from which we are starting the search. The edges of the tree correspond to the capabilities with arguments replaced with objects in the environment. Nodes correspond to the two states resulting from applying the capability in the parent state according to the two possible models. E.g., consider that a transition (sh. c, c.s is possible according to the model Mj. and let (s0 c, ss) be the corresponding transition (by applying the same effect set of as h2) according to the model Mj. Now there will be an edge in the forward search tree with label e such that parent node is (s6. si) and
child node is (si s)). The search process terminates when node (s" ) is reached such that either the states s² and s don't 't match, or the preconditions of the same capability were met in the state according to one of the possible models but not according to the other. Vanilla forward search scales poorly with the number of capabilities and objects in the environment. To address this we reduce the problem to fully observable non deterministic (FOND) planning problem. This can be solved by any FOND planner. The output of this search is a policy π to reach a state where the two models, M, and M, predict different outcomes. Additional details about the reduction and an example of the output policy are available in the extended version of the paper [Verma et al., 2023]. The query (sr, n,, G, a, v)) resulting from this search is such that 81 is set to the initial state Su. is the output policy, G is the goal state where the models' responses doesn't match, a and are hyperparameters as mentioned earlier. We next see how to use these queries to prune out the incorrect models.
4.3 Learning Probabilistic Models Using Query Responses
At this point, QACE already has a query such that the response to the query by the two possible models does not match. We next see how prune the model inconsistent with the SDMA. QACE poses the query generated earlier to the SDMA and gets its response (line 7 in Alg. 1). If the SDMA can successfully execute the policy, QACE compares the response of the two models with that of the SDMA and prunes out the model whose response does not match with that of the SDMA. If the SDMA cannot execute the policy, i.c., SDMA fails to execute some capability in the policy, then the models cannot be pruned directly. In such a case, a new initial state Sp must be chosen to generate a new query starting from that initial state. Since generating new queries for the same pair of models can be time consuming, we preempt this issue by creating a pool of states S that can execute the capabilities using a directed exploration of the state space with the current partially learned model as discussed below.
Directed exploration A partially learned model is model where one or more capabilities have been learned (the correct preconditions have been identified for each capability and at least one effect learned). Once we have such a model, we can do a directed exploration of the state space for these capabilities by only executing a learned capability if the preconditions are satisfied. This helps in reducing the sample complexity since the simulator only called when we know that the capability will execute successfully, thereby allowing us to explore different parts of the state space efficiently. If a capability's 's preconditions are not learned, all of its groundings might need to be executed from the state. In the worst case, to escape local minima where no models can be pruned, we would need to perform a randomized search for state where a capability is executable by the SDMA. In practice, we observed that using directed exploration to generate pool of states gives at least one grounded capability instance. This helps ensure that during query generation, the approach does not spend a long time searching for a state where capability is executable.

---

Learning probabilities of stochastic effects After QACE learns the non-deterministic model, to learn the probabilities of the learned effects it uses the transitions collected as part of responses to queries. This is done using Maximum Likelihood Estimation (MLE) [Fisher, 1922]. For each triplet (s, (5)) seen the collected data, let count, be the number of times a capability e is observed. Now, for each effect set, the probability of that effect set becoming true on executing that capability c is given as the number of times that effect is observed on executing c divided by counte. As we increase the value of the hyperparameter 7/, we increase the number of collected triplets, thereby improving the probability values calculated using this approach.
Theoretical Analysis and Correctness
We now discuss how the model M of SDMA A learned using QACE fulfills the notions of correctness (Sec. 3) discussed earlier. We first show that the model M learned before line 10 of QACE (Alg. I) is sound and complete according to Def. 2. The proofs for the theorems are available in the extended version of the paper [Verma et al., 2023].
Theorem 1. Let A be black-box SDMA with a ground truth transition model T' expressible in terms of predicates P and set of capabilities C. Let M* be the non-deterministic model expressed in terms of predicates p and capabilities C, and learned using the query-based autonomous capability estimation algorithm (Alg. 1) just before line 10. Let Cy be a set of capability names corresponding to capabilities C. Pf C P. then the model M* sound w.r.f. the SDMA transition model T'. Additionally, if P* = P. then the model M is complete w.r.t. the SDMA transition model" T
Next, show that the final step of learning the probabilities for all the effects in each capability converges to the correct probability distribution under the assumption that all the effects of a capability are identifiable. When a capability e executed in the environment, one of its effects ej(c) E eff( c) will be observed in the environment. To learn the correct probability distribution in M, we should accurately identify that effect (c). Hence, the set of effects identifiable if least one state exists in the environment from which each effect can be uniquely identified when the capability is executed. An example of this is available in the extended version of the paper [Verma et al., 2023].
Theorem 2. Let A be black-box SDMA with a ground truth transition model T' expressible in terms of predicates P and a set of capabilities C. Let M be the probabilistic model expressed in terms of predicates P and capabilities C, and learned using the query-based autonomous capability estimation algorithm (Alg. 1). Let P = Pp" and M be generated using a sound and complete non- deterministic model M in line 11 of Alg. 1, and let all effects of each capability C be identifiable. The model M is correct w.r.t the model T' in the limit as n tends to oc, where nj is hyperparameter in query Qus used in Alg. 1.
6 Empirical Evaluation
We implemented Alg. 1 in Python to evaluate our approach empirically.' We found that our query synthesis and interactive learning process leads to (i) few shot generalization; (ii) convergence to sound and complete model; and (iii) much greater sample efficiency and accuracy for learning lifted SDM models with complex capabilities compared to the baseline.
Setup We used a single training problem with few objects (S 7) for all methods in our evaluation and used test set that was composed of problems containing object counts larger than those in the training set. We ran the experiments on a cluster of Intel Xeon E5-2680 v4 CPUs with CentOS 7.9 running 2.4 GHz with memory limit of 8 GB and a time limit of 4 hours. We used PRP [Muise et al., 2012] as the FOND planner to generate the queries (line 6 in Alg. 1). For QACE, we used 2d where d is the maximum depth of policies used in queries generated by QACE and 77 = 5. All of the methods in our empirical evaluation receive the same training and test sets and are evaluated on the same platform. We used Variational Distance (VD) as presented in Eq. evaluate the quality of the learned SDMA models.
Baseline selection We used the closest SOTA related work, GLIB [Chitnis et al., 2021] baseline. GLIB learns probabilistic model of an intrinsically motivated agent by sampling goals far away from the initial state and making the agent try to reach them. This can be adapted to an assessment setting
Source code available at https: :/ggttubb...t/t//// wwwm/AIR../................. 1ab/
7

---

Figure 3: Screen captures from the Cafe Server Robot simulation. The complete environment is shown in the image on the left. The image grid on the right shows screen captures of multiple steps of the robot delivering a soda- can to table.
by moving goal-generation based sampling outside the agent, and, to the best of our knowledge, no existing approach addresses the problem of creating intelligent questions for an SDMA. GLIB has two versions, GLIB-G. G, which learns the model as a set of grounded noisy deictic rules (NDRs) [Pasula et al., 2007], and GLIB-L, which learns the model as set of lifted NDRs. We used the same hyperparameters as published for the Warehouse Robot and Driving Agent and performed extensive tuning for the others and report results with the best performing settings.
The models learned using GLIB cannot be used to calculate the variational distance presented in Eq. because for each capability GLIB learns set of NDRs rather than a unique NDR. In order to maintain parity in comparison, we use GLIB's setup to calculate an approximation of the VD. Using it, we sample 3500 random transitions (s, C, s") from the ground truth transition model T'' using problems in the test set to compute dataset of transitions D. The sample-based, approximate VD then given as: [D] EdED [(s (sr'tee (exx( where Car (s) samples the transition using the capability in the learned model output by each method. In Fig. 5, compare the approximate variational distance of the three approaches w.r.t. D as we increase the learning time. Note that we also evaluated VD for QACE using Eq. 1 and found that 8(T', M) x 0 for our learned model M in all SDMA settings.
SDMAs for evaluation To test the efficacy of our approach, we created SDMAs for five different settings including one task and motion planning agent and several SDMAs based on state-of-the-ar stochastic planning systems from the literature: Cafe Server Robot is Fetch robot [Wise al., 2016] that uses the ATM-MDP task and motion planning system [Shah et al., 2020] to plan and act in restaurant environment to serve food, clear tables, etc.; Warehouse Robot is a robot that can stack, unstack, and manage the boxes in warehouse; Driving Agent that can drive between locations and can repair the vehicle at certain locations; a First Responder Robot that can assist in emergency scenarios by driving to emergency spots, providing first-aid and water to victims, etc.; and Elevator Control Agent that can control the operation of multiple elevators in a building.
Additional details about each setting are available in the extended version [Verma et al., 2023].
6.1 Results
We present an analysis of our approach on all of the SDMAS listed above. We also present a comparative analysis with the baseline on all SDMAs except the Cafe Server Robot, whose task and motion planning system was not compatible with the baseline.
Cafe Server Robot This SDMA setup uses an 8 degrees of freedom Fetch [Wise et al., 2016] robot in cafe setting on OpenRave simulator [Diankov and Kuffner, 2008]. The low-level environment state consists of continuous x, y. Z, roll, pitch, and yaw values of all objects in the environment. The predicate evaluators were provided by ATM-MDP of which we used only a subset to learn PPDDL. model. Each robot capability is refined into motion controls at run-time depending on the configuration of the objects in the environment. The results for variational distance between the learned model and the ground truth model in Fig. 4 show that despite the different vocabulary, QACE learns an accurate transition model for the SDMA.
We now discuss the comparative performance of QACE with the baseline across the four baseline- compatible SDMAs presented above.
8

---

QACE (Ours)
GLIB-G
GLIB-L First Responder Robot
Warehouse Robot
Driver Agent
Elevator Control Agent
1n--
Variational Distance
0.8-
0.6-
0.4-
0.-
100
150
200
250
50
100
150
2000
250
50
1.0
350
2000
250
50
1.00
150
200
250
Learning Time (minutes)
Figure 5: A comparison of the approximate variational distance as a factor of the learning time for the three methods: QACE (ours), GLIB-G, and GL.BB- (lower values better). x shows that the learning process ended at that time instance for QACE. The results were calculated using 30 runs per method per domain. Solid lines are averages across runs, and shaded portions show the standard deviation. T' is the ground truth model. Detailed results are available in Verma et al. [2023].
Faster convergence The time taken for QACE to learn the final model much lower than that of GLIB for three of the four SDMAs. This is because trace collection by QACE is more directed and hence ends up learning the correct model in shorter time. The only setup where GLIB marginally outper- forms QACE is Warchouse Robot, and this happens because this SDMA has just two capabilities, istic. Hence, GLIB can easily learn their configuration from few observed traces. For SDMAs with complex and much larger number of capabilities - First Responder Robot and El- evator Control Agent GLIB finds more challenging to learn the model that is closer to the ground truth transition model. Additionally, QACE takes much fewer samples learn the model than the baselines. In all settings, QACE is much more sample efficient than the baselines as QACE needed at most 4% of the samples needed by GLIB-G to reach the variational distance that it plateaued at. In contrast, GLIB-L started timing out only after processing a few samples for complex SDMAs.
Cafe Server Robot
1.0
QACE (Ours)
Variational Distance
0.8
0.6-
0.4-
of which is determin-
0.2
T
10
20
30
40
50
60
Learning Time (minutes)
Figure 4: Variational Distance be- tween the Iearned model and the ground truth with increasing time for QACE for Cafe Server Robot. x shows that the learning process ended at that time instance.
Few-shot generalization To ensure that learned models not overfitted, our test set contains problems with larger quantities of objects than those used during training. As seen in Fig. 5, the baselines have higher variational distance from the ground truth model for complex SDMA setups as compared to QACE. This shows better few-shot generalization of QACE compared the baselines.
7 Related Work
The problem of learning probabilistic relational agent models from given set of observations has been well studied [Pasula et al., 2007, Mourão et al., 2012, Martínez et al., 2016, Juba and Stern, 2022]. Jiménez et al. [2012] and Arora et al. [2018] present comprehensive reviews of such approaches. We next discuss the closest related research directions.
Passive learning Several methods learn probabilistic model of the agent and environment from given set of agent executions. Pasula et [2007] learn the models the form of noisy deictic rules (NDRs) where action can correspond to multiple NDRs and also model noise. Mourão et al. [2012] learn such operators using action classifiers to predict the effects of an action. Rodrigues et al. [2011] 1] learn non- non-deteriiiistic models as collection of rule sets and learn these rule sets incrementally. They take a bound on the number of rules as input. Juba and Stern [2022] provide theoretical framework to learn safe probabilistic models with range of probabilities for each probabilistic effect while assuming that each effect atomic and independent of others. A common issue with such approaches is that they are susceptible to incorrect and sometimes inefficient model

---

learning as they cannot control the imput data used for learning or earry out interventions required for accurate learning.
Sampling of transitions Several approaches learn operator descriptions by exploring the state space the restricted setting of deterministic models [Ng and Petrick, 2019, Jin et al., 2022]. A few reinforcement learning approaches have been developed for learning the relational probabilistic action model by exploring the state space using pre-determined criteria to generate better samples [Ng and Petrick, 2019]. Konidaris et al. [2018] explore learning PPDDL models for planning, but they aim to learn the high-level symbols needed describe set of input low-level options, and these symbols are not interpretable. GLIB [Chitnis et al., 2021] also learns probabilistic relational models using goal sampling as heuristic for generating relevant data, whereas we use active querying using guided forward search for this. Our empirical analysis shows that our approach of synthesising queries yield greater sample efficiency and correctness profiles than the goal generation used in this approach.
Active learning Several active learning approaches learn automata representing a system's model [Angluin, 1988, Aarts al., 2012, Pacharoen et al., 2013, Vaandrager, 2017]. These ap- proaches assume access to teacher (or an oracle) that can determine whether the learned automaton correct and provide counterexample if it is incorrect. This is not possible in the black-box SDMA settings that constitute the focus of this work.
8 Conclusion
In this work, we presented an approach for learning probabilistic model an agent using interactive querying. We showed that the approach is few-shot generalizable to larger environments and learns sound and complete model faster than state-of-the-an approaches
sample-efficiet manner.
QACE describes the capabilities of the robot in terms of predicates that the user understands (this includes novice users well more advanced users like engineers). Understanding the limits of the capabilities of the robot can help with the safe usage of the robot, and allow better utilization of the capabilities of the robot. Indirectly, this can reduce costs since the robot manufacturer need not consider all possible environments that the robot may possibly operate in. The use of our system can also be extended to formal verification of SDMAs.
QACE can also be used by standard explanation generators as they need an agent's 's model. Such models are hard obtain (as also illustrate in this paper) and approach can be used to compile them when they are not available to start with.
Limitations and Future Work In this work, we assume that the agent can be connected to simulator to answer the queries. In some real-world settings, this assumption may limiting as users might not have direct access to such simulator. Formalizing the conditions under which is it safe to ask the queries directly to the agent in the real-world is a promising direction for the future work. Additionally, in this work, we assume the availability of the instruction set of the SDMA as input in the form of capability names. certain settings, might be useful to discover the capabilities of an evolving SDMA using methods proposed by Nayyar et al. [2022] and Verma et al. [2022].
Acknowledgments and Disclosure of Funding
We thank Jayesh Nagpal for his help with setting up the Cafe Server Robot SDMA. We also thank anonymous reviewers for their valuable feedback and suggestions. This work supported by the ONR under grants N00014-21-1-22 and 400014-23-1
References
Fides Aarts, Faranak Heidarian, Harco Kuppens, Petur Olsen, and Frits Vaandrager. Automata learning through counterexample guided abstraction refinement. In Proceedings of the 18th International Symposium on Formal Methods, 2012.
Dana Angluin. Queries and concept learning. Machine Learning, 214):319-342, 1988.
Ankuj Arora, Humbert Fiorino, Damien Pellier, Mare Métivier, and Sylvie Pesty. A review of learning planning action models. Knowledge Engineering Review, 33:E20, 2018.
10

---

Rohan Chitnis, Tom Silver, Joshua Tenenbaum, Leslie Pack Kaelbling, and Tomás Lozano-Péée Pérez. GLIB: Efficient exploration for relational model-based reinforcement learning via goal- eiterl babbling. In Proceedings of the 35th AAAI Conference Artificial Intelligence, 2021.
Alessandro Cimatti, Marco Roveri, and Paolo Traverso. Strong planning in non-deterministic domains via model checking. In Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems, 1998.
Devleena Das, Sonia Chernova, and Been Kim. State2Explanation: Concept-based explanations to benefit agent learning and user understanding. In Advances in Neural Information Processing Systems, 2023.
Rosen Diankov and James Kuffner. OpenRAVE: Planning Architecture for Autonomous Robotics. Technical Report CMU-RI-TR-08 34, Carnegie Mellon University, USA, July 2008
Ronald A. Fisher. On the mathematical foundations of theoretical statistics. Philosophical Transac- tions the the Royal Society of London, Series A, (22(594-004):309-2235 1922.
Samuel Greydanus, Anurag Koul, Jonathan Dodge, and Alan Fern. Visualizing and understanding Atari agents. In Proceedings of the 35th International Conference on Machine Learning 2018.
Sergio Jiménez, Tomás De La Rosa, Susana Feránndez, Fernando Fernández, and Daniel Borrajo. A review of machine learning for automated planning. Knowledge Engineering Review, 27(4): 433-467, 2012.
Mu Jin, Zhihao Ma, Kebing Jin, Hankz H. Zhuo, Chen Chen, and Chao Yu. Creativity of AI: Automatic symbolic option discovery for facilitating deep reinforcement learning. In Proceedings of the 36th AAAI Conference on Artificial Intelligence 2022.
Brendan Juba and Roni Stern. Learning probably approximately complete and safe action models for stochastic worlds. In Proceedings of the 36th AAAI Conference Artificial Intelligence, 2022.
Been Kim, Julie A. Shah, and Finale Doshi-Veles Mind the gap: A generative approach to inter- pretable feature selection and extraction. In Advances in Neural Information Processing Systems, 2015.
George Konidaris, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. From skills to symbols: Learn- ing symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, (1(1:2215-25 289, January 2018.
Isaac Lage and Finale Doshi-Velle Learning interpretable concept-based models with human feedback. In ICML Workshop Human Interpretability in Machine Learning, 2020.
William Macke, Reuth Mirsky, and Peter Stone. Expected value of communication for planning in ad hoc teamwork. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, 2021.
Jiayuan Mao, Tomás Lozano-Pérez. Joshua B. Tenenbaum, and Leslie Pack Kaelbing, PDSketch:
Integrated domain programming, learning, and planning. In Advances in Neural Information Processing Systems, 2022.
David Martínez, Guillem Alenyå, Carme Torras, Tony Ribeiro, and Katsumi Inoue. Learning relational dynamics of stochastic domains for planning. In Proceedings of the 26th International Conference on Automated Planning and Scheduling, 2016.
Neville Mehta, Prasad Tadepalli, and Alan Fern. Autonomous learning of action models for planning. In Advances in Neural Information Processing Systems, 2011.
Kira Mourão, Luke Zettlemoyer, Ronald P. A. Petrick, and Mark Steedman. Learning STRIPS operators from noisy and incomplete observations. In Proceedings of the 28th Conference on Uncertainity in Artificial Intelligence, 2012.
Christian Muise, Sheila Mcllraith, and Christopher Beck. Improved non-deterministic planning by exploiting state relevance. In Proceedings of the 22nd International Conference on Automated Planning and Scheduling, 2012.
11

---

Rashmeet Kaur Nayyar, Pulkit Verma, and Siddharth Srivastava. Differential assessment of black-box Al agents. In Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022.
Jun H. A. Ng and Ronald P. A. Petrick. Incremental learning of planning actions in model- reinforcement learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019.
Warawoot Pacharoen, Toshiaki Aoki, Pattarasinee Bhattarakosol, and Athasit Surarerks. Active learning of nondeterministic finite state machines. Mathematical Problems in Engineering, page 373265, 2013.
Hanna M. Pasula, Luke Zettlemoyer, and Leslie Pack Kaelbling. Learning symbolic models of stochastic domains. Journal of Artificial Intelligence Research, 29:309-352, 2007.
Mark S. Pinsker. Information and Information Stability of Random Variables and Processes. Holden- Day, Inc., 1964. ISBN 08 16268045.
Ivaylo Popov, Nicolas Heess, Timothy Lillicrap, Roland Hafner, Gabriel Barth-Maron, Matej Vecerik, Thomas Lampe, Yuval Tassa, Tom Erez, and Martin Riedmiller. Data-efficient deep reinforcement learning for dexterous manipulation. 1:Xiv::704.0555 2017.
Christophe Rodrigues, Pierre Gérard, and Céline Rouveirol. Incremental learning of relational action models in noisy environments. In Proceedings of the 21th International Conference on Inductive Logic Programming, 2011.
Kay G. Schulze, Robert N. Shelby, Donald J. Treacy, Mary C. Wintersgill, Kurt VanLehn, and Abigail Gertner. Andes: An active learning, intelligent tutoring system for Newtonian Physics. Themes in Education, 1(2):115-136, 2000.
Burr Settles, Active Learning. Morgan Claypool Publishers, 2012. ISBN 1608457257.
Naman Shah, Deepak Kala Vasudevan, Kislay Kumar, Pranav Kamojjhala, and Siddharth Srivastava. Anytime integrated task and motion policies for stochastic environments. In IEEE International Conference on Robotics and Automation, 2020.
Peter Sollich and David Saad. Learning from queries for maximum information gain in imperfectly learnable problems. Advances in Neural Information Processing Systems, 1994.
Sarath Sreedharan, Siddharth Srivastava, and Subbarao Kambhampati. Hicrarchical expertise level modeling for user specific contrastive explanations. Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2018.
Sarath Sreedharan, Utkarsh Soni, Mudit Verma, Siddharth Srivastava, and Subbarao Kambhampati. Bridging the gap: Providing post-hoc symbolic explanations for sequential decision-making problems with inscrutable representations. In Proceedings of the 10th International Conference on Learning Representations, 2022.
Siddharth Srivastava, Eugene Fang. Lorenzo Riano, Rohan Chitnis, Stuart Russell, and Pieter Abbeel. Anytime integrated task and motion policies for stochastic environments. In IEEE International Conference Roboties and Automation, 2014.
Siddharth Srivastava, Stuart Russell, and Alessandro Pinto. Metaphysics of planning domain descrip- tions. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016.
Frits Vaandrager. Model learning. Communications of the ACM, 60(2):86-95, 2017.
Pulkit Verma, Shashank Rao Marpally, and Siddharth Srivastava. Asking the right questions: Learning interpretable action models through query answering. In Proceedings the 35th AAAI Conference on Artificial Intelligence, 2021.
Pulkit Verma, Shashank Rao Marpally, and Siddharth Srivastava. Discovering user-interpretable capabilities of black-box planning agents. In Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, 2022.
12

---

Pulkit Verma, Rushang Karia, and Siddharth Srivastava. Autonomous capability assessment of sequential decision-making systems stochastic settings (Extended Version), arXiv:2306.04m 04806, 2023.
Melonee Wise, Michael Ferguson, Derek King, Eric Diehr, and David Dymesich, Fetch and freight: Standard platforms for service robot applications. IJCAI Workshop on Autonomous Mobile Service Robots, 2016.
Häkan L. S. Younes and Michael L. Littman. PPDDL 1.0: An extension to PDDL for expressing domains with probabilistic effects. Technical Report CMU-CS-04-167, Carnegie Mellon University, USA, October 2004.
Tan Zhi-Xuan, Jordyn Mann, Tom Silver, Josh Tenenbaum, and Vikash Mansinghka. Online bayesian goal inference for boundedly-ratio rationaal planning agents. In Advances in Neural Information Processing Systems, 2020.
13


Reviews:
[{"review_id": "XXOVCLbUjE", "reviewer": "Reviewer_pN4U", "summary": "This paper proposes a method for modeling the capabilities of black-box artificial intelligence systems, which can plan, act, and execute in a stochastic setting. Specifically, the proposed method introduces an active learning approach to interact with the black-box SDM system and learn a probabilistic model that describes its functionality. The paper presents theoretical analysis that guarantees the convergence of the learning process. Empirical evaluations on different intelligent agents and simulated scenarios demonstrate that the proposed method exhibits generalizability with limited data and effectively describes the capabilities of the agents.", "questions": "Regarding this paper, please refer to my \"Weaknesses\" for questions and comments. They mainly concern the limitations of the method, evaluation, and practical data.", "limitations": "The paper briefly mentions its limitations, but it would be beneficial to include a discussion on potential social implications.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a method for modeling the capabilities of black-box artificial intelligence systems. Overall, this paper is well-motivated and provides detailed explanations.\n2. This paper describes how the active learning method effectively interacts with the black-box SDM system and introduces a probabilistic model that explains its functionality.\n", "weaknesses": "1. The empirical evaluation results of the paper demonstrate that the model can adapt well to training tasks with few samples. However, how does it perform in terms of generalization evaluation for new tasks?\n2. Another major concern I have is the generality of the proposed method, especially when people want to apply it to more complex manipulation tasks. While it has been validated on several examples, I am unsure how these ideas can be extended. How can it be applied to more practical environments with skill-specific parameters, such as grasping angles and placement targets?\n3. In practice, how is the intelligent system trained with data? How is this data collected on physical robots, and what are the challenges involved?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for questions and support. We address your comments on the weakness of the approach below:\n\n**Weakness 1)** The test set is not the same as the training set. As mentioned in lines 332-334, we used a single problem as input. Additionally, QACE (our approach) generates queries and based on their responses we learn the correct model. The methods were tested on environments that were much larger in terms of objects as compared to the input problem. This shows the generalization of our approach for tasks that follow the same dynamics.\n\n**Weakness 2)** Our approach is highly general for SDM agents. Our experiments on the SDMA with cafe server robot had complex grasping poses and angles. The predicates used to express the domain were at a high level of abstraction which abstracted this low level information and hence explains the high-level dynamics of the system. For vocabularies that can express the difficult concepts like different types of grasps, this approach will accommodate for those predicates and learn a model in terms of those predicates. This feature makes the models personalized for each kind of user. \n\n**Weakness 3)** Our intelligent data gathering process uses active learning based query generation allowing the collection of training data in an automatic, handsfree fashion without requiring any human intervention. In our paper, this process was accomplished on benchmark SDM agents connected with simulators.\n\nIn the real-world, on physical robots, our system could connect to the robot via an interface or be deployed directly. It can issue commands (execute capability c) and observe the responses to those commands for collecting training data. The key challenges here would pertain to safe operation of the robot. Since the models of its capabilities are not known, running these commands directly on the robot could potentially lead it to perform an unsafe operation. This could be easily circumvented if the physical robot was inbuilt with rudimentary safety protocols. This is part of the future extension of the work that we mention in lines 422-424.\n\n\n\n"}, {"review_id": "gOOsAtkLT5", "reviewer": "Reviewer_Jehr", "summary": "This paper addresses the problem of creating a user-interpretable probabilistic model of the capabilities of a sequential decision-making (SDM) system (through only interacting with the system as a black-box (rather than inspecting its internal structure, e.g., reasoning dynamics).  In particular, PPDDL is proposed to model the SDM system.  An algorithm is proposed that (1) generates queries that seek to determine the location of predicates  either preconditions or effects for capabilties in PPDDL descriptions and (2) data is collected from repeated interactions with the system (likely through simulation, but also possibly through real-world runs) to both determine the validity of PPDDL descriptions and their component probabilities.  Theoretical results seek to establish that the resulting model is both \"sound\" and \"complete\" The algorithm is evaluated on five simulation environments, demonstrating convergence to a model with low variational distance from the true SDM.", "questions": "Q1) How does your search handle the exponential number of possible combinations of predicates that could exist as preconditions or effects?\n\nQ2) In your experiments, what do you mean by learning time, and how did you test your solution with different amounts of learning time?  My naive assumption would be that it took 4 hours to run the entire algorithm and you measured the quality of M* along the way, but that would imply that only looking at a few of the <l, p> pairs (the first few in the for loop on line 3) gave you a really accurate model, which doesn't make sense because they tell you little about the other <l, p> pairs not yet considered.\n\nQ3) How do you interpret the low variational distance with only \\eta = 5?\n\n### Post-Rebuttal ###\n\nI thank the authors' for their rebuttal and the ensuing conversation.  They helped strengthen my understanding of the proposed method.  I  think that adding more detail to the body of the paper (instead of the supplement) would greatly strengthen the impact of the work since it appears there are a lot of necessary details that were not originally presented that affect the efficiency and effectiveness of the algorithm.", "limitations": "There wasn't a lot of discussion of the limitations of the approach, but addressing many of the weaknesses (especially the combinatorial nature of the problem) would aid the reader in better understanding when the approach could be applicable vs. when improvements to the technique would needed.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1) The problem considered has many real-world applications, is indeed understudied, and is relevant for the planning and RL communities at NeuRIPs.\n\nS2) The paper is relatively well-written and easy to follow.\n\nS3) The use of maximal-likelihood estimation for determining probabilities in the PPDDL descriptions seems appropriate as proposed and in-line with other work on learning models of stochastic systems (e.g., model-based reinforcement learning).\n\nS4) I appreciate that the authors considered both theoretical and empirical analysis of their approach.\n\nS5) The empirical results considered a range of benchmarks to aid in evaluating the generalizability of the approach and its advantage over a baseline (GLIB).", "weaknesses": "The primary weaknesses of this paper include:\n\nW1) The algorithm proposed appears to perform a linear search through what is ultimately a combinatorial search space of potential PPDDL descriptions.  The for loop on line 3 of Algorithm 1 loops over each condition location and predicate combination independently to determine whether that predicate appears as a precondition or effect for a given condition in some PPDDL description relevant to the system.\n\nHowever, it isn't clear how the algorithm can discover PPDDL descriptions when two or more predicates appears as a precondition or effect only in AND combination with other predicates.  In that case, looking at and individual <l, p> pair will not provide enough evidence to determine that the predicate p should be in location l for the relevant condition.\n\nFor example, say that condition C has a single precondition (and P1 P2) and a single effect (and P3 P4).  Looking at <precondition P1> or <precondition P2> alone will not generate the necessary data to  determine that either are part of a PPDDL description since they are only relevant together and have no measurable outcomes alone.  Similar for <effect P3> and <effect P4>.  While there are only 2|C| locations where a predicate can appear, its appearance occurs within 2^|P| (power set of P) possible combinations of predicates, and it is completely unclear how your algorithm would find all such combinations for even a single capability that requires an search space of exponential combinations of predicates.  Especially using only \\eta simulated trajectories of the system.  And without all such combinations, it is unclear how your ultimate model is either sound or complete.\n\nI can imagine there might be some submodular subset of SDM problems where the algorithm converges to the correct set of PPDDLs.  But even in that subset of problems, a certain order of search in the for loop on line 3 (since M* is incrementally constructed) seems highly important for the soundness and correctness of the final model M constructed by the model.\n\nAltogether, the combinatorial nature of the PPDDL descriptions also implies scalability concerns as the number of capabilities and especially predicates increases, but a large number of unique predicates (and hence a very large number of combinations) are likely to be needed for realistic systems of important real-world problems.\n\nW2) The algorithm presented in Algorithm 1 is not any anytime, algorithm, so I'm not sure what it meant to increase the learning time.  It has two for loops whose time complexity depend on the number of capabilities and predicates, and the number of simulation traces \\eta was fixed in the experimental setup to 5.\n\nW3) The uncertainty present in the benchmarks seems rather small, so they do not seem to highlight how well the approach handles non-deterministic environments (which is considered one of the main strengths when compared to the prior work in Section 7).  Requiring only \\eta = 5 simulation traces per query for good convergence implies that (1) it was rather simple to experience traces that demonstrate the existance (or absence) of a predicate as a precondition or effect (i.e., the environment is not very stochastic),  and (2) the probabilities in the domain must all be close to multiples of 20% (since that's the best level of precision you can achieve with 5 traces in your data-driven Maximal Likelihood Estimation.  In most Monte Carlo sampling of complex stochastic environments, many traces are required (and are only guaranteed to converge as \\eta approaches infinity).\n\nW4) I think this work is a good starting point to achieve it's goal of explaining SDM systems to users.  It wasn't clear to me how well the approach factors in the user's environment, which will be necessary for end users (especially non-AI specialists) will interact with and trust the system.  For example, I might receive a set of descriptions of the capabilities of a retail robot vacuum with this approach, but when I take it home to my environment that is different from the one where the PPDDL descriptions were created, the robot might behave very differently.  Maybe the probabilities change as it has a more difficult time navigating around my furniture or along the type of rugs on my floor.  Or maybe even different predicates would need to be added since there are confounding factors (e.g., the presence of different types of pets).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed feedback and questions. We address your questions and other concerns below:\n\n**Q1)** The reviewer correctly points out that the search space of possible preconditions and effects is exponential. We also mentioned this in lines 40-42. Verma et al. [1] showed that preconditions (and effects) that are a conjunction of predicates can be learned in a linear number of queries (in terms of the number of predicates and capabilities) using query synthesis over abstract models (for deterministic settings). Our approach uses the same methodology and performs query synthesis over abstract models in non-deterministic settings.\nThis approach leads to fewer queries because the reasoning about the correctness of a precondition or effect is not done using models that are at the same level of abstraction as the ground truth model but instead using a high-level abstract model that has fewer predicates in the precondition and/or effect of some/all capability(ies). \n\nE.g., consider a capability with a precondition $p1 \\land p2$ as suggested by the reviewer. The automated query generation process will involve executing the capability successfully in some state $s$ by the policy. The SDMA can only execute the capability in $s$ if $p1 \\land p2$ is true in $s$. As mentioned in lines 279-284, if $s$ doesn’t fulfill this criterion (i.e., the SDMA fails to execute the policy successfully) a new query is generated from a new initial state $s’$. Hence, this property of executing the capability in a state having $p1 \\land p2$ is ensured. Now, when reasoning about p1, the policy can ask the agent to execute that capability in the state $s \\setminus p1$ and if the SDMA fails to execute it then it means $p1$ is part of the precondition. Similarly, this can be done for p2 independently. \n\nIn the worst case, the search for a state $s$ where a query policy is executable will be exponential, but as the evaluations show, we can learn the correct model much faster. We also mention a way to overcome this in lines 282-284. Please note that even for methods like reinforcement learning, the worst-case upper bound is exponential in terms of the state space. We will include this discussion in the final version using the additional page permitted by NeurIPS.\n\n**1.1:** About the method working only for submodular PPDDLs: As shown in the results, this method **does** work for PPDDLs that have conjunctive preconditions. E.g., in Fig.2 in the paper, we have the precondition (empty-arm) $\\land$ (has-charge) $\\land$ (robot-at ?location) $\\land$ (at ?location ?item). This capability is from the cafe server robot. \n\nThe empirical evaluation showed that QACE (our approach) can learn such models much faster than the closest SOTA approach GLIB as shown in Fig. 5.\n\n**Q2)** Your intuition is correct. For an experiment run, we run QACE as well as the baselines from scratch. For the plots, we took snapshot of the learned models every 60 seconds and computed the variational distance using a fixed test dataset. As you notice in the graph, the variational distance is very high initially, and it drops till the learning process of QACE ends (marked by a blue x on the plots). We do not need to run QACE beyond this point and this time is short for all the domains. On the other hand, GLIB doesn’t have a clear ending criterion. Hence we let it run for 4 hours and see that even with the extra time (and hence extra samples), it cannot learn a better model. \n\nAbout getting an accurate model with few $\\langle l,p \\rangle$ pairs: This is not true. Since the plots are shown for a period of 4 hours, it would seem that QACE learns the model without using all $\\langle l,p \\rangle$ models. We do consider all $\\langle l,p \\rangle$ models and learn the final model in an efficient manner. Fig. 1 in the extended supplementary material (uploaded with the rebuttal response) clarifies this point using the zoomed-in portions for duration when QACE is running. This figure also shows that the model learned by QACE gets better with time as it processes more $\\langle l,p \\rangle$ pairs.\n\nThis also addresses a similar concern raised in W2. Please note that a larger  $\\eta$ might be needed for a more complex domain to learn the correct probabilities.\n\n**Q3)** The hyperparameter $\\eta$ is 5, but this does not mean that we execute that capability just 5 times. As mentioned in the paper, consider $\\mathcal{P}$ to be the set of predicates, and $|\\mathcal{P}|$ be the number of predicates. Now a capability $c$ can appear in policies for $\\langle l, p \\rangle$ pairs, such that location $l$ corresponds to a precondition or effect in $c$. So effectively, $c$ can appear in at least for $2 \\times |\\mathcal{P}|$ queries. So we will have at least $2 \\times |\\mathcal{P}| * \\eta$ samples for each capability.   \n\n**W4)** This is precisely the motivation for our work, and is addressed directly by the presented method. In your scenario, the user would be able to use our system to discover the new model of the agent, with probabilities in this new environment. We agree that predicate discovery is also an open problem in this area and we plan to address it in future work by building upon the presented methods.\n\n----------------------\n*References:*\n\n[1] Verma, P., Marpally, S. R., & Srivastava, S. Asking the Right Questions: Learning Interpretable Action Models Through Query Answering. AAAI 2021."}, {"review_id": "VJou3deqIN", "reviewer": "Reviewer_Sjai", "summary": "The paper tackles the problem of modeling the capabilities of a block-box sequential decision-making agent (SDMA) by querying the SDMA agent along the way. The presented method (QACE) uses an active learning approach to interact with the block-box SDMA and learn an interpretable probabilistic model of its capabilities. The paper also presents a theoretical analysis of QACE showing that it can learn a model that is both complete and sound w.r.t the ground-truth model of the SDMA. QACE works using version space partitioning using the queries to remove inconsistent hypotheses until it converges on one model. In the final step, the learned non-deterministic model is converted into probabilities over the capabilities of the system -- via MLE done on the collected data via responses to the queries. QACE is evaluated in four different settings -- Cafe Server robot, warehouse robot, driving agent, and first responder agent. Results show that QACE is able to recover the underlying model of each environment almost always in a reasonable time. The method also outperforms extensions of SOTA methods such as GLIB-L and GLIB-A.", "questions": "- Clarification: Is it correct to assume that QACE assumes that there is a unique model that defines a given SDMA? What happens if that assumption is not satisfied, or is it the case that SDMA will always have a unique model by design?\n\n- What happens if the SDMA systems have some margin of error in providing responses to the queries? How would the error propagation be handled when generating distinguishing queries?\n\n- In real systems, sometimes it is not feasible to ask several queries to a system. When the number of queries has a budget (say c number of queries/ or the cost of a query is c), how does it affect the accuracy of the learned model? Can further guarantees be provided on the learned model?\n\n- See \"Weaknesses\" for additional clarifications.", "limitations": "The authors have addressed the limitations of the presented method and in its current form, there is no potential negative societal impact of the work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The premise of the problem that the paper tackles is an interesting one. It is a very practically relevant problem as the framework outputs interpretable capability names of the SDMA and defines how each capability name can be invoked. The paper is written clearly and the running example of the Cafe-server robot makes it easier to understand the presented algorithm. The experimental setup also shows that the policy simulation queries $\\eta (= 5)$ to learn distinguishing queries, are within a reasonable range, to be applied in practical environments. The completeness and soundness guarantees provide a stronger basis for the adoption of the algorithm. Overall, the problem setup is quite interesting, and QACE provides a new direction to reason about the capabilities of block-box SDMA in an interpretable manner.", "weaknesses": "- On the scalability of QACE: From the paper, it was not clear as to whether QACE can scale to systems that have a larger space of predicate and therefore larger probabilistic problem domain description language. For systems with larger predicates, would the parameter $\\eta$ be reasonable enough to estimate the response to a query?\n\n- Extended Theoretical analysis: While completeness and soundness guarantees are provided, it would also be interesting to see how many iterations of QACE are required for it to provide a reasonable estimate of the model. What is the convergence rate of QACE w.r.t the error in estimating the model?\n\n- Clarity: A short description of the GLIB (the baseline) method would be good, as it is the only baseline that QACE is compared against.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review. We address your questions and concerns below:\n\n**Q1)** No, QACE doesn’t assume that there is a single model that defines the given SDMA’s functionality. QACE can return a functionally equivalent model when there are multiple correct representations. E.g., if p(x) and q(x) are equisatisfiable in a domain, functionally equivalent models can be created by replacing p's and q's with each other. In such cases, QACE will return a model that is functionally equivalent (modulo such substitutions).\n\n**Q2)** In the current setup, the SDMA responds with the policy or the capability sequence that it would execute in response to the objective in a given query. However, the system allows execution errors and stochastic environments. The system can model probabilistic effects, and as a result execution errors will be learned as additional effects for the respective capability in the query. Thank you for the question. We will clarify this in the final version. \n\n**Q3)** (and **Weakness 2**): For our approach, QACE, the number of iterations of the algorithm is bounded by the number of interactions (steps) the system has with the agent. This is because each iteration has at least one interaction with the agent. The number of interactions (steps) is bounded by $\\eta \\times \\alpha \\times num-queries$. The plots for variational distance vs. the number of steps are available in the supplementary material (Fig. 3). Since this number is very small for QACE when compared to the baseline GLIB, we have also included a zoomed-in version of the plots and  a plot of variational distance vs number of unique queries in the additional supplementary material (Sec. 5) submitted with this rebuttal response. We will merge this with the main supplementary in the final version.\n\nTheoretically, for a fixed query budget, we can get an upper and lower bound on the number of $\\langle l,p \\rangle$ tuples that can be learned correctly. This is because if we stop the learning process in between, the current model M* will be correct in terms of $\\langle l,p \\rangle$ tuples that were already processed by QACE up to that point.\n\n**Weakness 1)** Scalability Issue: We are providing a table below with the size of domains in terms of the number of predicates and capabilities. The number of queries are linear in terms of the number of predicates and capabilities (for loop in line 3 of Alg. 1). Note that the for loop in line 5 only contributes to a constant factor in the running time, as only three hypotheses are possible (lines 177-181). Thank you for the question. We will clarify this in the final version.\n\n```\nSDMA                   | |P| | No of Capabilities\nWarehouse Robot        | 8   | 4\nDriver Agent           | 4   | 2\nFirst Responder Robot  | 13  | 10\nElevator Control Agent | 12  | 10\nCafe Server Robot      | 5   | 4\n```\n\nAdditionally, our approach is highly scalable  and the parameter $\\eta$ is used only to learn the correct probabilities in the effects of capabilities.\n\n**Weakness 3)** Thanks a lot for the suggestion. We did give a very high-level overview in lines 352-358. But we understand this might not be sufficient for audiences not familiar with GLIB. In addition to the text, we will add a short summary of GLIB in the revised version using extra pages."}, {"review_id": "yE8XvxqUFm", "reviewer": "Reviewer_Gtv9", "summary": "The paper proposes an algorithm for learning a probabilistic model of a black box agent's capabilities. The method assumes the existence of a vocabulary to describe the environment's state and the set of capabilities. The proposed method generates all possible hypotheses using three ways to add a predicate (as a condition, a negated condition, and not adding it). In the first instance, these hypotheses have no probabilities assigned. Using a sequence of distinguishing queries generated with a planner, they prune the version space (the possibly correct hypotheses). Lastly, the algorithm employs a frequentist estimation of the probabilities associated with the transitions.\n\nThe authors validate the algorithm empirically comparing it to a previous SOTA method.", "questions": "The abstract mentions \"evolving sequential decision making\", but the methods assume the capabilities of the black box are fixed, and it doesn't discuss an evolving/adapting agent.\n\nWhat is a FOND model? A short description would help.", "limitations": "Yes, the authors discussed limitations.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strength of the paper is the careful exposition of an intuitive approach to the problem, along with the empirical evaluation claiming to surpass previous state-of-the-art algorithms.", "weaknesses": "The weakness of the paper is the assumption that all possible hypotheses need to be generated. In real-life scenarios, this might be prohibitive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " We thank the reviewer for the review and suggestions. We address your concerns below:\n\n**Weakness)** As mentioned in lines 177-181, there are just three hypotheses corresponding to any $\\langle l,p \\rangle$ pair. Hence the number of hypotheses to be considered are a small constant (=3) at any step in the algorithm.\n\n----------\nThe answer to the individual questions are added below:\n\n**Q1) Evolving SDM:** We wanted to focus that in case an SDM’s capabilities evolve; we would want to generate the descriptions of the SDM agent after the update. The model itself remains the same during the assessment process. We will clarify this point in the paper.\nAn example scenario of such evolving capabilities would be a robot that is initially deployed and assessed by QACE to yield a model $M_1$. After some time, the coefficient of friction of the wheels and gripper could change due to wear and tear, changing the model. The assessment process could be re-run (and in fact can be run using overnight batch updates since it is automatic, and handsfree requiring no human intervention) to capture this update to the model.\n\n**Q2) FOND Model:** A FOND model is a fully observable non-deterministic model. Each capability has a precondition similar to the probabilistic model (lines 105-126), and an effect in the FOND model is also similar to the probabilistic model but without the associated probabilities. The capability shown in Figure 2, will be expressed as follows in a FOND model:\n```\n(:capability pick-item \n  :parameters (?location ?item) \n  :precondition (and (empty-arm) \n    (has-charge) \n    (robot-at ?location) \n    (at ?location ?item)\n  ) \n:effect (oneof  \n    (and (not (empty-arm)) (not (at ?location ?item)) (holding ?item)) \n    (and (not (has-charge))) \n    (and)  # No-change\n  ) \n) \n```\nHere ```oneof``` in the effect represents that only one of the three effects will be applied on executing this capability.\n\n"}, {"review_id": "XgL6cqeWS3", "reviewer": "Reviewer_k56H", "summary": "This paper introduces QACE, an algorithm for automatically learning the capabilities of sequential decision making agents through distinguishing queries. The problem is formulated in terms of the predicates and capabilities of an agent, which are assumed to be known a priori. QACE then aims to compute a transition model that encodes the probabilities that executing a given capability in a given state s will lead to state s'.", "questions": "**a)** \nIn the introduction, the authors claim that part of what makes this problem relevant is to allow users to understand what their robots can do and under what conditions. However it is unclear to me how QACE could help a user learn to take the most out of its robot. If instead QACE is meant to be used by a different stakeholder group, then I think this is not clear in the paper.\n\n**b)** \nIs a learning time of 20 or 30 minutes a big overhead for a user? Would they feel frustrated and give up from trying to learn how to use the robot? It is difficult to evaluate if the learning time of QACE is acceptable if there is no baseline against which to compare it.\n\n**c)**\n[lines 283-284] \"we preempt this issue by creating a pool of states S that can execute the capabilities using a directed exploration of the state space using partially learned models.\", it is not clear to me how having this pool of states can prevent the generation of queries to take \"forever\" (in cases where the hypotheses cannot be pruned directly). Also, what is a partially learned model in such cases and how do you get them and what do you mean with \"directed exploration of the state space\"?\n\n**d)** \n[Proof of proposition 1] Why is it not possible, according to Alg.1, for the two models to \"either have different preconditions for c′ or different effects.\" Isn't this necessary for the FOND planning problem to have a solution? \"the FOND planning problem ⟨M_ij , s_I_ij ,G_ij⟩, which has a solution if both the models have different precondition or at least one different effect for the same capability.\"\n\n\n**Comments:**\n\nAn introduction to the basics of FOND planning is missing. Providing one in the supplemental material could be helpful. \n\nSimilarly, some background on PPDDL would help with Figure 2 and section 1.3 of the supplemental material.\t\n\nFigure 5. Standard deviation of QACE is hard to see. For example changing colours could improve readability.\n\n[minor details]\n- [line 142] \"model M that should ideally be same as T'\" ==> **the** same as T'?\n- [line 160] \"formalae\"", "limitations": "The authors discuss some limitations of their work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Originality:** \nThis is an original piece of work (novel combination of techniques) and related work seems to be adequately cited.\n\n**Quality:** \nThe submission seems to be technically sound and the claims are supported. The authors discuss limitations of their work. The methods are appropriate but it could have been interesting to see a comparison against simpler baselines, such as against an approach that randomly generates queries.\n\n\n**Clarity:** \nThe submission is well written. The process for generating distinguishing queries could be demonstrated through figures (added to the supplemental material, for example) that show how the tree is built and how the pruning is executed. Similar strategies could be used to provide examples of the non-deterministic model and how it is transformed into a probabilistic model. More detail on background could be provided, for example with sections (e.g., in the supplemental material) introducing FOND planning and PPDDL. Also, sometimes it feels like some claims could use a bit more explanation (e.g., question c), below).\n\n\n**Significance:**\nI think the results are important, however it is not clear to me who would leverage QACE or how. Is it the actual users? Is it robot designers/engineers? \n\n\nEDIT:\n\nI read the author's rebuttal, which helped clarify matters I had not fully understood.", "weaknesses": "Please see above for strengths and weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for detailed review and suggestions. We plan to use the additional page to incorporate them including suggestions for the description of FOND and PPDDL models.\n\n**Quality:** GLIB uses such a method that generates random traces and hence is used in our comparison as a baseline. We will clarify this in addition to GLIB's summary in the final version.\n\nWe would like to highlight that, to the best of our knowledge, no other existing approach is able to solve the problem we are addressing in this work. There are significant challenges in solving the assessment problem we address here due to which the closest available baseline GLIB has several limitations, and we provided the baseline with additional details to work for the setting we address. GLIB requires input goals that should satisfy certain conditions (should be conjunctions of at least three predicates that are not true in the initial state), so we manually provided it with such goals (for each of the 3-5 input problems per domain) for it to perform comparably. We also used the same set of hyperparameters that the GLIB authors used in their evaluation. Even with these changes, we would need the fixes mentioned in lines 352-356 for it to apply to our setting. We will clarify this.\n\n**a)** (and **Significance**) As the reviewer correctly points out, we mentioned in lines 18-19 that in terms of an SDMA, we envision that lay users should be able to determine what an SDMA “can do, what effects their commands would have, and under what conditions?”. In this context, our approach (QACE) describes the capabilities of the robot in terms of predicates that the user understands (This includes novice users as well as more advanced users like engineers.) Understanding the limits of the capabilities of the robot can help with the safe usage of the robot, and allow better utilization of the capabilities of the robot. Indirectly, this can reduce costs since the robot manufacturer need not consider all possible environments that the robot may possibly operate in. The use of our system can also be extended for formal verification of SDMAs.\n\n**b)** We think that a learning time of 20-30 minutes might seem excessive *iff* there is no output provided to the user by the system during the assessment process. Our system works by identifying the correct preconditions and effects, one <l,p> pair at a time. This could be streamed to the user and the user can immediately benefit from this information (which is guaranteed to be correct). Furthermore, assessment is an infrequent process and the system could be programmed to run assessment during large periods of inactivity, thus making sure that the user is always informed of any changes that could occur (e.g. coefficient of friction of wheels changing from wear-and-tear). As seen by our empirical evaluation, our approach can provide the user with a complete model significantly faster than other SOTA approaches that learn models.\n\nYou are correct that a baseline performing exactly the same work as ours is missing, and hence we believe this is a valuable contribution in the direction of the personalized assessment of SDMA systems.\n\nNote that our approach can be used by standard explanation generators as they need an agent’s model. Existing methods for explanation generation [1,2] require such models as input. Those models are hard to obtain (as we also illustrate in this paper) and this approach generates those models when they are not available to the users to start with.\n\n**c)** As mentioned in lines 279-284, an important step in pruning the hypotheses is to get a state where the SDMA can execute a capability. Generating such states is easier if we use directed exploration, which can increase the probability of encountering such a state. Once we have such a state, we can use a process similar to the one used in response of Q1 to reviewer *Jehr* above.\n\n*Directed Exploration:* A partially learned model is a model where one or more capabilities have been learned (the correct preconditions have been identified for each capability and at least one effect is learned). We will clarify this. Once we have such a model, we can do a directed exploration of the state space for these capabilities by only executing a learned capability if the preconditions are satisfied. This helps in reducing the sample complexity since the simulator is only called when we know that the capability will execute successfully, thereby allowing us to explore different parts of the state space efficiently. Naturally, if a capability's preconditions are not learned, all of its groundings might need to be executed from the state.\n\nIn the worst case, to escape local minimas where no hypotheses can be pruned, we would need to perform a randomized search for a state where a capability is executable by the SDMA. But practically, as we observed in our empirical evaluation, using directed exploration to generate a pool of states gives at least one grounded capability instance. This ensures that during the query generation, the approach need not spend a long time searching for a state where a capability is executable.\n\n**d)** It is not possible for the two models to \"either have different preconditions for $c′$ or different effects” because the location $l$ corresponds to capability $c$ in line 124. According to Alg. 1, the models $M_i$ and $M_j$ are created such that they differ in precondition or effect of $c$ (depending on $l$).  Now since $c \\neq c’$ and the models already differ in precondition (or effect) of $c$, and the models $M_i$ and $M_j$ are exactly the same other than this difference. Hence $c’$ cannot have different preconditions or effects.\n\n-----\n*References:*\n\n[1] Chakraborti et al. Plan Explanations as Model Reconciliation: Moving Beyond Explanation as Soliloquy. IJCAI 2017.\n\n[2] Eifler et al. Plan-Space Explanation via Plan-Property Dependencies: Faster Algorithms & More Powerful Properties. IJCAI 2020."}]

Author rebuttal:
We thank the reviewers for their detailed reviews and comments. We answer the questions posed by the reviewers separately. Please find them in the response below the reviews. We are also adding a supplementary page with two plots. One showing the zoomed in version of the plot for variational distance vs learning time for QACE (our approach) and GLIB (baseline). And the other one showing the variational distance vs number of queries for QACE.

Meta-review: I am recommending accept for this paper. The reviews for the paper were originally (6, 5, 5, 5, 4). The reviewers praised the paper for being interesting and novel, saying it was a “new direction to reason about the capabilities of block-box SDMA in an interpretable manner”, and a “novel combination of techniques”, and said that "the results are important”. They liked that the technique had real world applications, and praised the theoretical analysis (they liked the completeness and soundness results) and empirical analysis (for being conducted in a range of environments).

The main complaints about the paper were that the method may be too complex, concerns were raised about the computational complexity and scalability, and about who would actually use it, and whether it would be possible to compare to simpler baselines. In my opinion the authors adequately addressed each of these concerns in the rebuttal. For example, regarding the simpler baselines, they explained that the baseline they implemented (GLIB) is essentially what the reviewer was requesting, and that “to the best of our knowledge, no other existing approach is able to solve the problem we are addressing in this work”.

The one negative reviewer (reviewer Jehr, who originally assigned a score of 4) raised concerns about how the method can be applied with conjunctive predicates. The authors attempted to answer his concerns to explain how this could work, and pointed out that one of their examples in Figure 2 includes conjunctive predicates. However the reviewer was still not clear on how the method worked, and asked for further clarification without raising their score. During the discussion with reviewers, I asked reviewer Jehr whether they believe the paper should be accepted if the method were explained more clearly, or whether they would argue for rejecting the paper. They responded that they would not argue for rejection, but that the method should still be clarified further, but ended up raising their score to a 5.

Therefore, I am recommending accept, although given the borderline scores (average of 5.2), I'm recommending it is accepted as a poster. I strongly encourage the authors to take the opportunity to revise the manuscript in the camera-ready version in order to address reviewer Jehr's concerns, particularly to clarify how the method works. Reviewer Jehr also requested that details necessary for understanding the efficiency and effectiveness be included. It is not only better for the scientific community, but in the authors' best interest to clarify the manuscript, because if the paper is more clear and comprehensible it is more likely to be cited and built upon in future work.
Decision: Accept (poster)