A Method for Efficient Argument-based Inquiry
Bas Testerink1 , Daphne Odekerken1,2 , and Floris Bex2
1

Police Lab AI
Netherlands National Police{bas.testerink,daphne.odekerken}@politie.nl
2
Police Lab AI
Utrecht University
f.j.bex@uu.nl

Abstract. In this paper we describe a method for efficient argumentbased inquiry. In this method, an agent creates arguments for and against
a particular topic by matching argumentation rules with observations
gathered by querying the environment. To avoid making superfluous
queries, the agent needs to determine if the acceptability status of the
topic can change given more information. We define a notion of stability,
where a structured argumentation setup is stable if no new arguments
can be added, or if adding new arguments will not change the status of
the topic. Because determining stability requires hypothesizing over all
future argumentation setups, which is computationally very expensive,
we define a less complex approximation algorithm and show that this is asound approximation of stability. Finally, we show how stability (or ourapproximation of it) can be used in determining an optimal inquiry policy, and discuss how this policy can be used to, for example, determine
a strategy in an argument-based inquiry dialogue.
Keywords: Computational Argumentation· Inquiry

1

Introduction

When performing inquiry or information seeking, an agent gathers informationfrom the environment such that it can form an opinion on a particular topic.
There are different strategies that one can consider for an agent [7, 3, 11]. We
propose a method for capturing agent inquiry policies in a way that is efficient– both computationally and in terms of the length of the inquiry process. The
knowledge of the agent is modelled as as a structured argumentation setup similar to ASPIC+ [8]. A set of possible queryable literals (observations which canbe made in the future) is also defined as part of the argumentation setup. Given
these queryable literals and the arguments that follow from the current observations, it can then be determined whether the topic is an acceptable conclusion[4], and which future observations (i.e. answers to queries) could conceivably
change the acceptability of this conclusion.
In order to avoid making superfluous queries we define a notion of stability:
an argumentation setup is stable if given the possible queries no new arguments

2

Testerink, Odekerken, Bex

can be added or adding new arguments will not change the acceptability of the
topic. Concretely: does an argument for the topic exist, is this argument in the
grounded extension [4], and can future answers to available queries change thesefacts? It is computationally complex to generate all arguments given the current
observations and then calculate the grounded extension. Extra complexity isadded for inquiry because one has to hypothesize on the possible results of future
queries. We therefore we propose a considerably less complex approximation
algorithm for determining stability. We also show that this algorithm provides asound approximation of stability: if the approximation algorithm, for example,
determines that the topic is acceptable, it is guaranteed that the topic is in the
grounded extension and further observations cannot change this.
The proposed inquiry method is currently applied in practice for crime investigation. As an example throughout the paper, we use a simplified version of thedomain of internet trade fraud (e.g. scammers on eBay or fake online stores), andspecifically the situation where a complainant files an official complaint with thepolice. Structured argumentation is an obvious way to model the practical andlegal rules concerning a crime [10]. Crime investigation should also be performed
efficiently, as investigative actions (questioning the complainant, requesting thecounterparty’s bank details) inevitably come with a cost. Furthermore, investigation is a stochastic process, as investigative actions are not guaranteed toyield new information – the complainant might, for instance, not know the requested information. Our method takes these aspects into account. The method
shows how the argumentation setup can be used to construct a Markov-decision
process that represents the inquiry task. Any suitable technique can be used
to approximate the optimal policy given the MDP (e.g. dynamic programmingor reinforcement learning). Roughly speaking, the argumentation aspect of themethod determines what kind of information is still relevant, and the policy
learning aspect determines which relevant information to inquire about next.
Due to limited space we had to abbreviate examples and proofs. For the interested reader we provide extended examples and full proofs3 . The rest of thispaper is structured as follows. In Section 2 we discuss our base argumentation
formalism. In Section 3 we then describe stability, that is, how to hypothesize
over possible future observations, and an algorithm that approximates stability,and give soundness and complexity results for the approximation algorithm. Section 4 discusses our inquiry policy. Section 5 discusses related work and Section 6
concludes the paper.

2

Base Formalism

The base formalism for argumentation draws upon ASPIC+ [8] for structured
argumentation and Dung’s grounded semantics [4] for abstract argumentation.
From ASPIC+ the concepts of a topic language, knowledge base and defeasible
rules are used. The concepts of queryable literals and a topic are added to these.
3

Extended examples and proofs: https://preview.tinyurl.com/y656r3ek

A Method for Efficient Argument-based Inquiry

3

The queryable literals are those literals in the topic language of which an observation might be made. The topic is a special literal of interest for which theagent aims to get a stable opinion. Together, these components are referred toas an argumentation setup as defined below. For notation convenience we use−l to negate a literal l, i.e.: −l = p if l = ¬p and −l = ¬p if l = p, for some
propositional atom p.
Definition 1 (Argumentation Setup, AS). An argumentation setup AS is
a tuple AS = (L, R, Q, K, τ ) where:– L is a logical language consisting of propositional literals, such that if l ∈ Lthen also −l ∈ L.
– R is a set of defeasible rules p1 ...pm ⇒ q s.t. p1 , ..., pm , q ∈ L. p1 ...pm arecalled the antecedents of a rule and q the consequent. The antecedents of arule are unordered. We refer to a rule p1 ...pm ⇒ q as ‘a rule for q’.
– Q ⊆ {l ∈ L|l 6= ¬p} is a set of non-negated queryable literals.
– K ⊆ L, such that ∀l ∈ K : (−)l ∈ Q ∧ −l 6∈ K, is a knowledge base ofobservations which is a consistent set of literals.
– τ ∈ L is a topic.
Example 1. As an example, let AS = (L, R, Q, K, τ ) be an argumentation setup
for a simplified fraud scenario. Figure 1 depicts the topic language and rules.
We abbreviate in formal examples the literals in the graph to the parenthesized
literals. In this example L consists of literals made of the atoms f , cp, c, p, s andw, where ‘f’ stands for ‘this is a case of fraud’, ‘c’ for ‘the complainant delivered’,‘cp’ for ‘the counterparty delivered’, ‘p’ for ‘the complainant paid’, ‘s’ for ‘thecomplainant sent a product’ and ‘w’ for ‘the wrong product was delivered’. The
rules are given by R = {p ⇒ c, s ⇒ c, (¬cp, c) ⇒ f , w ⇒ cp, w ⇒ ¬f }. In
the graph we represent a rule with an ‘&’ that points to its consequent and isundirectionally connected to its antecedents. The idea behind the rules is that
if the complainant delivered in the trade but the counterparty did not, thendefeasibly the setup is a case of fraud. If a wrong product was delivered, then it
is defeasibly not a case of fraud. Finally, if a wrong product was delivered thenarguably the counterparty delivered in the trade, but this could be overruled by
the fact that the complainant considers the ordered product to not have beendelivered. The queryable literals are given by Q = {p,s,w,cp}. This means thatfor instance the complainant can be queried for whether he/she paid. As the
topic we take τ = f . We will consider different knowledge bases throughout theexamples.
As per ASPIC+ ’s formalism, an argument is an inference tree that is constructed through the application of rules. The starting points for constructing anargument are the observations in the knowledge base. They are arguments themselves and on top of them new arguments can be made. Cyclic arguments are
forbidden to avoid an infinite number of arguments. This is enforced by requiringthat the conclusion of an argument cannot occur in any of its subarguments. The
inference function that gives the arguments for a given argumentation setup isdefined next.

4

Testerink, Odekerken, Bex

Definition 2 (Inference, I). Let AS = (L, R, Q, K, τ ) be an argumentation
setup. An argument is an inference A1 ...Am 7→ c such that A1 ...Am is an unordered set of arguments called its premises and c ∈ L is its conclusion. We
refer to A1 ...Am 7→ c as ‘an argument for c’. The arguments of AS are given by
I(AS):– ∅ 7→ c ∈ I(AS) iff c ∈ K.
– A1 ...Am 7→ c ∈ I(AS) iff A1 ...Am are in I(AS) and their conclusions are
c1 ...cm , and there is a rule c1 ...cm ⇒ c ∈ R, and c does not occur in any of
the arguments A1 ...Am .
Example 2. Consider the previously defined argumentation setup and let theknowledge base be K = {p,¬cp} (the complainant paid but the counterparty did
not deliver). For this example I(AS) = {A1 = (∅ 7→ p),A2 = (∅ 7→ ¬cp),A3 =(A1 7→ c),A4 = (A2 , A3 7→ f )}. Hence, given this knowledge there is an argument
for fraud.
Arguments may attack and/or defend each other. An argument A atfraud
tacks an another argument B if A’s~fraud(f)(~f)
conclusion negates some conclusion of
a subargument of B (a premise at~delivered_cp&tack) or B’s own conclusion (a rebut).
(~cp)
In the first case, the attack is onesided (from A to B), in the other case delivered_c
delivered_cp(c)(cp)
it is two-sided. There is one exception; an argument cannot be attacked
on a premise or its conclusion if that&&&&premise/conclusion is an observation.
paid
sent
wrong
The reasoning behind this is that an
(p)
(s)
(w)
observation is a low-level directly ob~paid~sent ~wrong
(~p)
(~s)
(~w)
served piece of evidence and not defeasibly inferred. An argument A candefend another argument B if A at- Fig. 1. A graphical representation oftacks attackers for B. The notion of the example topic language and rules.
Queryable literals are underlined.
attack and defense are defined next.
Definition 3 (Attack, Defense). Let AS = (L, R, Q, K, τ ) be an argumentation setup. For two arguments A, B ∈ I(AS) we say that A attacks B iff A’s
conclusion is c and −c occurs in B and −c 6∈ K. A set of arguments X ⊆ I(AS)
defends an argument A ∈ I(AS) iff for each B ∈ I(AS) that attacks A there isa C ∈ X that attacks B.
The acceptability of arguments is determined by Dung’s grounded semantics
for abstract argumentation [4].
Definition 4 (Grounded Extension, G). Let AS = (L, R, Q, K, τ ) be anargumentation setup. The grounded extension G ⊆ I(AS) of AS is the smallest
set of arguments (w.r.t. set inclusion) such that:

A Method for Efficient Argument-based Inquiry

5– There is no pair A, B ∈ G such that A attacks B (conflict-free), and– G = {A ∈ I(AS)|G defends A} (complete)
Example 3. Consider the previously defined argumentation setup and let theknowledge base be K = {p,¬cp, w} (the complainant paid and the counterparty
delivered the wrong product). For this example I(AS) are the arguments in
Figure 2. The attack relation is also shown in Figure 2. The grounded extension
for this example is {A1 , A2 , A3 , A5 }. Note that without the observation w, as
in the previous example, the argument A4 for fraud would be in the grounded
extension. Hence, extra observations may change whether or not an argument isin the grounded extension.

3

Hypothesizing over Future Observations

An inquiry agent tries to form a stable opinion
on its topic literal. An argument for a literalcan be non-existent, in the grounded extension, or outside the grounded extension. In
the latter case, the argument might be attacked from within the grounded extension
or otherwise from outside the grounded extension. These four cases indicate different
belief-statuses. If the status of the topic cannot change by executing more queries, thenthe argumentation setup is called stable. The
possible future argumentation setups are all
those setups where the queryable literals are
put in a current knowledge base as either positive or negative. Stability of an argumentation
setup is defined below.

A1: ∅|p

A5: ∅|w

A2: ∅|~cp

A6: A5|cp

A3: A1|c

A7: A5|~f

A4: A2,A3|

fFig. 2. A graphical representationarguments and their attack relation (the arrows). Boldface arguments are in the grounded extension.

Definition 5 (Future setups, Stability, F ). Let AS = (L, R, Q, K, τ ) be anargumentation setup. The set of all future setups F (AS) consists of all setups(L, R, Q, K0 , τ ) such that K ⊆ K0 . AS is stable iff any of the following holds:– Unsatisfiable: For each AS 0 ∈ F (AS) there is no argument for τ in I(AS 0 )– Defended: For each AS 0 ∈ F (AS) there is an argument for τ in the grounded
extension of AS 0
– Out: For each AS 0 ∈ F (AS) there is an argument for τ in I(AS 0 ) but allarguments for τ are attacked by an argument in the grounded extension of
AS 0– Blocked: For each AS 0 ∈ F (AS) there is an argument for τ in I(AS 0 ) but
not in the grounded extension of AS 0 and at least one argument for τ is not
attacked by an argument from the grounded extension of AS 0
Example 4. Let us consider the previous example again where K = {p,¬cp, w}
and the arguments and attack relation are shown in Figure 2. The blocked case6

Testerink, Odekerken, Bex

applies because there exist arguments for f and ¬f (A4 and A7 ) and they areboth outside the grounded extension. Furthermore, the only queryable literalthat is left is s, which cannot influence this situation if s or ¬s is observed.
Consider also the setup where K = {cp}. For this setup no argument can possibly
exist for f because all potential arguments require ¬cp. Therefore, in that setup
the unsatisfiable case applies. If s, ¬w and ¬cp are observed, then there exists
an argument for f in the grounded extension and no further observations (i.e.
p or ¬p) can change this. Therefore in that case the defended case applies.
Finally, in this example the out case can only apply for the literal ¬cp. This
happens when w and cp are observed. In that case w is a basis for an argument
for cp whilst ¬cp’s observation unilaterally attacks that argument.
A brute-force method for determining stability would be to calculate all possible future setups and then for each setup calculate the grounded extension to
see whether the topic is stable. This results in possibly 3|Q| different setups tocalculate the grounded extension for. The number of arguments in the grounded
extension given n = |L| is maximally n · g(n), g(n) = (1 + g(n))n−1 . The runtime complexity of this approach would be unpractical. Therefore a less complex
approach to this task is preferable. The following labelling is an approximationof the task. The idea behind it is that rules and literals are labelled, wherelabels relate to the cases of stability. The labelling is defined as follows. Afterthe definition and an example we discuss the soundness and complexity of thelabelling.
Definition 6 (Labelling, L). Let AS = (L, R, Q, K, τ ) be an argumentation
setup. A labelling L is a partial function that assigns a label from {U, D, O, B}
to literals and rules. Literals that are in Q but not observed (l, −l 6∈ K) are notlabelled. For the other literals and the rules the labelling is defined as follows:
Case U literal: l ∈ L is labelled U iff either: A) No rule exists for l and if(−)l ∈ Q then −l ∈ K. B) There are rules for l and they are labelled U andl 6∈ K.
Case U rule: r ∈ R is labelled U iff any of its antecedents is labelled U .
Case D literal: l ∈ L is labelled D iff either: A) l ∈ K. B) There is a rule forl labelled D, −l 6∈ K and there is no rule for −l. C) There is a rule for l labelled
D, −l 6∈ K and there are rules for −l but they are all labelled U or O.
Case D rule: r ∈ R is labelled D iff all its antecedents are labelled D.
Case O literal: l ∈ L is labelled O iff either: A) There exists a rule for l labelled
D, O or B and −l is labelled D. B) There are rules for l of which at least one
is labelled O and the rest is either labelled O or U .
Case O rule: r ∈ R is labelled O iff at least one antecedent is labelled O andthe rest is labeled D, B or O.
Case B literal: l ∈ L is labelled B iff l, −l 6∈ Q and either: A) A rule for l anda rule for −l is labelled D or B. B) There are rules for l of which one is labelled
B and the rest is either labelled U , O or B.
Case B rule: r ∈ R is labelled B iff at least one antecedent is labelled B andthe rest is labeled B or D.

A Method for Efficient Argument-based Inquiry

7

Example 5. Figure 3. Shows the labelling for the example argumentation setup
where K = {p, ¬cp, w}. As expected given the previous example, the f literal islabelled B. Consider also the setup where K = {cp}. The labelling for that setup
labels ¬cp U due to case ‘U literal A’. Consequently, the rule c, ¬cp ⇒ f islabelled U due to case ‘U rule’. Finally f is labelled U because of case ‘U literal
B’. Hence, as discussed in the previous example, for the example argumentation
setup where K = {cp} the topic f is unsatisfiable. In the ‘extended examples
and proofs’ document we discuss more examples.
Note that alongside possible future observations, other literals can also be unlabelled.
In particular, as long as the topic remains
unlabelled it means that more information isrequired. The labelling of an argumentation
setup is a sound approximation of stability.
This means that if the topic is labelled, thenthe argumentation setup is stable. The following two propositions together show this.
As the method is an approximation there arecases where a literal might be stable but unlabelled. The proof for proposition 2 in the ‘extended examples and proofs’ document4 contains such an example.

fraudB(f)~fraud B
(~f)

&

D

~delivered_cpD(~cp)

delivered_cD(c)delivered_cpO
(cp)

D

D

D

&

&

&

paidD
(p)

sent
(s)

wrongD(w)~sent~wrong

U

~paid

&

U

Proposition 1. Let L be the labelling of an
(~p)
(~s)
(~w)
argumentation setup AS = (L, R, Q, K, τ ). If
for a rule r = (p1 ...pm ⇒ c) ∈ R: L(r) ∈ Fig. 3. Labelling of Figure 2 given{D, B, O} then there exists an argument for c K = {p, w, ¬cp}. Boldface literals
are in K and underlined literals arein I(AS).
Proof sketch: By following the labels D, B queryable.
and O from literals to rules we must end up in
observed literals. Hence, if a rule is labelled D,
B or O then we can follow the labelling until
we end up with a set of observed literals. The observed literals, and the rules thatwere passed by following the labelling, can be used to construct the argument forc.
Proposition 2. Let AS = (L, R, Q, K, τ ) be an argumentation setup and L be
its labelling. If L(τ ) = U , D, O or B then AS is stable because of the unsatisfiable, defended, out, or blocked case of Definition 5, respectively.
Proof sketch: The different labels are ‘introduced’ under the stated property
and their propagation through the rules to other literals preserves this property.
U is introduced if a literal l has no rules for it and is unobservable (possibly due
to −l being observed). Hence, no argument could exist for l. D is introduced forobserved literals and hence for such literals an argument is guaranteed to exist
4

Extended examples and proofs: https://preview.tinyurl.com/y656r3ek

8Testerink, Odekerken, Bex

that is in the grounded extension. O is introduced if a rule for a literal l can beapplied to make an argument but −l is observed. Hence every argument for l isunilaterally attacked by an argument in the grounded extension. B is introduced
if for l and −l there exists at least one argument that is not attacked by anargument from the grounded extension.
U is propagated through rules if for a rule at least one premise is labelled
U . This indicates that the rule cannot be applied to construct an argument for
its conclusion. If a literal has only U -labelled rules then therefore no rule canbe applied to construct an argument for that literal. D is propagated if for arule all premises are labelled D. This indicates that if the conclusion cannot
have a rebutter, then this rule can be applied to construct an argument for in
the grounded extension. So an unobservable literal becomes D if this holds. O
is propagated if for a rule all premises are not unsatisfiable (so arguments canbe made) but at least one is O, indicating that there will always be a unilateralpremise attack from the grounded extension to arguments based on this rule.
Which is why literals with only O-applicable rules are labelled O. B is propagated
if for a rule if at least one of its premises is labelled B and the others are D
or B-labelled. This indicates that every argument based on this rule will have a
unilateral attacker on one of its premises. However, this attacker has a bi-lateralattacker that rebuts it. Hence arguments based on this rule will be attacked but
not by arguments in the grounded extension. Therefore if a literal has only rulesthat are labelled U , O or B then the labelled becomes B.
Finally, we aim to improve upon the complexity of the brute-force method ofdetermining stability. The following proposition discusses the big-Oh complexityof labelling an argumentation setup.
Proposition 3. Let AS = (L, R, Q, K, τ ) be an argumentation setup. The labelling L of AS can be constructed in O((|L| + |R|)2 ).
Proof sketch: A simple algorithm for the labelling works as follows. We canstart with the set L ∪ R minus the literals from L that might be observed in the
future. Then, we iterate through the cases of Definition 6 until no case applies
anymore. Any time a case applies for a literal or rule, we remove it from theset. Worst-case, the set shrinks one-by-one until the empty set is reached (every
literal/rule has a label) in which case a quadratic number of passes through thecases has been executed (0.5 ∗ (|L| · |R|)2 ).

4

Optimizing Inquiry Policies

An inquiry policy returns a query to execute given an argumentation setup andavailable queries. In the following, we show how to model the inquiry setting asa Markov Decision Process (MDP) for which the optimal policy can be obtainedby standard methods. An MDP consists of actions, states, a transition function
and a reward function. For the actions we take the queries that are available. A

A Method for Efficient Argument-based Inquiry

9

query can be executed once during a dialogue.5 . A state in the MDP is a pair ofan argumentation setup and a set of available queries. After executing a query
it is removed from the available queries and the setup may change because newobservations might be added to the knowledge base.
The transition function tells us what the probability of a transition from one
state to the next is when executing some query. For example, observing thata wrong product was received increases the probability of observing in the future that the complainant paid. We cancel out illegal transitions by setting theirprobability to zero. As for the reward function; we generate positive reward whena stable argumentation setup is reached from an unstable setup. Any transitions
among unstable setups are negative because a query was executed. The transitions among stable setups are considered neutral. The labelling of Section 3 isapplied to approximate stability. Finally, the optimal policy immediately follows
from the MDP. The best action to execute give a state is the query which maximizes the expected reward. By maximizing reward, the policy will minimize theexpected number of executed queries before reaching a stable setup.
Definition 7 (Argumentation MDP, policy, M , π). Let AS = (L, R, Q, K, τ )be an argumentation setup and F (AS) be all its possible future setups. An argumentation MDP M for AS is a tuple (Q, S, δ, r), where:– Q is a set of queries– S = F (AS) × 2Q is the state space– δ : S × Q × S → [0, 1] is the transition function which returns the probabilityof the next state being s2 ∈ S given some state s1 ∈ S and query q ∈ Q.
Furthermore, δ(s1 , q, s2 ) = 0 if the knowledge base of AS1 is not a subset ofthat of AS2 , or if q is not available (q 6∈ Q1 ), or if Q2 6= Q1 \ {q}.
– r : S × S → I is the reward for transitioning from s1 = (AS1 , Q1 ) ∈ S tos2 = (AS2 , Q2 ) ∈ S and is given by: r(s1 , s2 ) = |Q1 | if τ is labelled in thelabelling of AS2 but not AS1 , r(s1 , s2 ) = 0 if τ was already labelled in thelabelling of AS1 , else r(s1 , s2 ) = −1.
The policy π : S → Q is given by:∀s1 = (AS1 , Q1 ) ∈ S : π(s1 ) = argmaxq∈Q1 Σs2 ∈S δ(s1 , q, s2 )(r(s1 , s2 ) + V (s2 ))where: V (s2 ) = Σs3 ∈S δ(s2 , π(s2 ), s3 )(r(s2 , s3 ) + V (s3 )).
Example 6. Consider a policy for the MDP that belongs to the argumentation
setup of the previous examples. A query can be any action that potentiallyleads to some observations. For this example we take Boolean queries that only
have single queryable literal for which they may lead to an observation. Let thequeries be Q = {p?,s?,w?,cp?}. For a query x? assume that its execution resultsin x or −x being added to the knowledge base. The policy may then look likethe one that is shown in Figure 4. Note that for simplicity’s sake, we assume
some (implicit) probabilities for the transitions. From the policy it can be read5

Note that, if desired, the same query can be ‘copied’ multiple times in the formal
model to allow for repeated execution.

10

Testerink, Odekerken, Bex
L(f)=B
K={-cp, w, p}
Q={s}
p?

L(f)=U
K={cp}
Q={p, s, w}
cp?
K={}
Q={p, s, w, cp}
K={-cp}
Q={p, s, w}s?

K={-cp, w, -p} K={-cp, w, -p, -s}
Q={s}
Q={}
L(f)=U
L(f)=D
L(f)=D
K={-cp, w} K={-cp, -w, s} K={-cp, -w, -s, p}
Q={p, s}
Q={p}
Q={}
w?

s?

p?

K={-cp, -w} K={-cp, -w, -s} K={-cp, -w, -s, -p}
Q={p, s}Q={p}Q={}
L(f)=U

Fig. 4. Part of the example policy. These are the reachable states/actions from theempty observation set (i.e., zero probability transitions are omitted). States with stable
setups are boldface and the label of the topic f is shown as well for such states.

that first it queried whether the counterpary delivered (partially) upon his/herpromise. If not, then it is queried whether a wrong product was delivered. If
so, then it is queried whether the complainant paid, or otherwise whether thecomplainant sent a product. In both situations, if the answer is negative, then thelast query is executed. Note that in the example policy, after the user answered
negative to ‘cp?’ and positive to ‘w?’, that the label for fraud cannot be D in the
future. It depends on an application whether this might be a reason to halt theexecution. Formally, the system still executes queries because the reason why
the label is not ‘D’ is still unstable.
Roughly speaking, for our real-world applications the argumentation systemprovides information on what queries are relevant and the policy then chooses
among the relevant queries. We apply various techniques to make the policy suchas dynamic programming and q-learning. The policy itself can also be used indifferent ways. In one of our applications it guides a dialogue with the user andin another it prioritizes database queries. Similarly, the argumentation setup has
different applications. It can be used to determine what information is relevant
but also provide argumentation-based explanations for the agent’s decisions.

5

Related WorkA typical argument-based inquiry is a so-called inquiry dialogue [7, 3], in whicharguing agents collaborate to answer some question the answer to which is notknown by the individual agents. Our setting is different in that the information source of our agent is not necessarily another arguing agent: a query canbe implemented as an utterance in an argumentation dialogue, but it can also

A Method for Efficient Argument-based Inquiry

11

for instance be a query on a database. Thus, our optimal query policy can beused to determine an efficient strategy for inquiry dialogues, but it can also be
used outside such dialogues. Furthermore, as already discussed in Section 3, in
our setting the agent can only query observations, whereas in an argument inquiry dialogue the other agent (i.e. the agents that “answers” the query) can
also provide an argument, making these dialogues slightly more flexible. However, in the existing work on inquiry dialogue strategies [3, 11] only exhaustive
strategies are defined, which simply perform all queries, that is, the agent keeps
asking questions even if it already has an argument for its topic, or if adding
new arguments cannot change the status of the topic. Such exhaustive strategies
are both inefficient (in terms of the length of the inquiry process) and computationally very expensive. While there is work on developing more optimal policies
or strategies for argumentation dialogues (see [9] for a fairly recent overview),
some of which shows some similarities with our work in their use of (in theircase partially observable) MDPs for defining policies [6], this existing work all
focuses on strategies for so-called persuasion dialogue, in which the agent tries
to convince an opponent of some conclusion. Furthermore, this existing work is
all based on abstract argumentation frameworks [4], in which only arguments assingle entities (propositions, nodes) and their attacks are considered, and there is
no argument structure that includes inferences based on a knowledge base. Workon inquiry that does not explicitly use arguments is [5], in which the authors
propose a four-valued logic with the truth values true, false, inconsistent andunknown, which, broadly speaking, are similar to the current paper’s Defended,
Out, Blocked and Unsatisfiable stability cases. Like [3], the strategies for inquiry
discussed in this paper are all exhaustive and hence not efficient.
With respect to the idea of stability, much of the work on argumentation ismore concerned with the static situation: given the knowledge we have now, what
are the acceptable arguments. A notable exception is by Ballnat and Gordon [1].
This work looks at determining which possible future additions to a knowledge
base might change the acceptability of a conclusion. They do not use their basic
ideas for determining optimal policies, however, nor do they discuss the complexity and approximation results we provide in this paper. The idea of stability
also has clear links to what is called the enforcing problem [2]: given a set ofarguments, can we modify this set by adding or removing arguments and conflicts so that some argument from the original set becomes acceptable? The workthat exists on this topic, however, again only deals with abstract argumentation
frameworks.

6

Conclusion and Future WorkIn this paper we have described a policy for efficient argument-based inquiry –that is, a policy that minimizes the expected number of queries required to reacha stable setup in which the acceptability of some conclusion cannot change any
more given a stochastic environment. Our approach is efficient in a number ofways, computationally as well as with respect to the inquiry process itself.

12

Testerink, Odekerken, Bex– By rewarding an agent that reasons towards a stable argumentation as quickly
as possible we ensure that only the minimum required number of queries is
executed to draw a stable conclusion.
– By approximating the notion of stability we make determining or learning thepolicy feasible in terms of computational complexity.
– Finally, by defining the policy by means of an MDP we allow the agent toavoid executing queries that are likely to be unsuccessful.
As for future work we want to further explore the notion of stability in structured argumentation, taking into account the possibility of rules, preferences
and attacks being added through queries. We also intend to see how we canfurther embed the policy in argument dialogues between agents. Finally, ourimplementations of this method are leading to best-practices (e.g. to deal withnoisy observations) which we aim to publish publicly.

References
1. Ballnat, S., Gordon, T.F.: Goal selection in argumentation processes. In: Computational models of argument: Proceedings of COMMA 2010. Frontiers in Artificial
Intelligence and Applications, vol. 216, pp. 51–62. IOS Press (2010)
2. Baumann, R.: What does it take to enforce an argument? minimal change in abstract argumentation. In: Proceedings of the 20th European Conference on Artificial Intelligence. pp. 127–132. No. 242 in Frontiers in Artificial Intelligence andApplications, IOS Press (2012)
3. Black, E., Hunter, A.: An inquiry dialogue system. Autonomous Agents and MultiAgent Systems 19(2), 173–209 (2009)
4. Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial intelligence
77(2), 321–357 (1995)
5. Dunin-Keplicz, B., Strachocka, A.: Tractable inquiry in information-rich environments. In: Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence (IJCAI 2015). pp. 53–60. AAAI publishing (2015)
6. Hadoux, E., Beynier, A., Maudet, N., Weng, P., Hunter, A.: Optimization of probabilistic argumentation with markov decision models. In: Proceedings of the TwentyFourth International Joint Conference on Artificial Intelligence (IJCAI 2015). pp.
2004–2010. AAAI publishing (2015)
7. Parsons, S., McBurney, P., Wooldridge, M.: The mechanics of some formal interagent dialogues. In: Advances in Agent Communication, pp. 329–348. Springer(2004)
8. Prakken, H.: An abstract framework for argumentation with structured arguments.
Argument and Computation 1(2), 93–124 (2010)
9. Thimm, M.: Strategic argumentation in multi-agent systems. KI-Künstliche Intelligenz 28(3), 159–168 (2014)
10. Verheij, B.: Dialectical argumentation with argumentation schemes: An approachto legal logic. Artificial intelligence and Law 11(2-3), 167–195 (2003)
11. Yan, C., Lindgren, H., Nieves, J.C.: A dialogue-based approach for dealing withuncertain and conflicting information in medical diagnosis. Autonomous Agentsand Multi-Agent Systems 32(6), 861–885 (2018)