This extended abstract gives an overview of the work presented in [8]. We are interested in the formal and computational aspects of the problem of an agent learning from the knowledge of another agent, playing the role of a domain expert. In general, the raw knowledge of an agent is not directly accessible. In particular, the knowledge of an expert, the target domain of interest, cannot be duplicated as is and transferred to a learner. Nonetheless, agents can still learn from one another through questions and answers in a communication protocol. These acts of communication are expected to be simple.

A classical communication protocol from computational learning theory is based on questions of two types: membership and equivalence queries [1]. In a learning from entailments setting [5], these questions can be described as follows. Membership queries correspond to asking whether a certain statement formulated as a logical sentence follows from the target. Equivalence queries correspond to asking whether a certain logical theory, called hypothesis, precisely describes the target. If there are wrong or missing statements in the hypothesis, a statement illustrating the imprecision should be returned to the agent playing the role of the learner. Arguably, equivalence queries are not in fact simple, and this is one of the main difficulties in implementing this protocol in practice [7, page 297]. Whenever a learner poses an equivalence query, the expert playing the role of an oracle needs to evaluate the whole hypothesis and decide whether or not it is equivalent to the target. If not, then the oracle returns a statement in the logical difference between the hypothesis and the target.

One way out of this difficulty is hinted to us by a simple observation: during interactive communication among agents, not only domain knowledge is exchanged and acquired but also second-order knowledge, which is the knowledge of what is known by the other agents. We propose a new and more realistic learning model which takes into account what is known by the agents, either because a statement was explicitly communicated or because it is a logical consequence of previous statements given during their interaction. Our protocol is based on queries of two types. The first is an epistemic version of membership queries where the oracle 'remembers' those membership queries whose reply was 'yes'. We call the second type example queries. When asked an example query, the oracle answers a statement which follows from its knowledge but does not follow from its knowledge about what the learner knows. The oracle also 'remembers' that the statements given are now known by the learner.

Formally, each i ∈ A aims at learning a target formula l j ∈ L j of each other agent j = i ∈ A by posing them queries. A membership query to i asks an oracle

[1] and [2] ⊂ PAC Fig. 1. Polynomial learnability. Each class denotes the set of frameworks that are polynomial query learnable in the corresponding learning model. MEM, EQ and EX stand for membership, equivalence, and example queries respectively.

MEM whether an example x ∈ X i is entailed by l i . An equivalence query to i asks an oracle EQ whether a formula h ∈ L i is equivalent to l i ; it returns yes if it is the case, or an counterexample in X i otherwise. Here, we introduce new kinds of queries. A K-membership query to i asks an oracle MEM K whether an example x ∈ X i is entailed by l i . When it is the case, the oracle MEM K also remembers that the learner j knows that x, adding K j x to its own knowledge. An example query to i requests the oracle EX to provide an example x that is entailed by l i but does such that K j x does not follow from the oracle's knowledge. An exact learning algorithm for a learning framework is a deterministic algorithm that takes no input, is allowed to make queries to MEM and EQ, and eventually halts and outputs some h ∈ L i , equivalent to l i . An epistemic learning algorithm is similar to an exact learning algorithm, except that it is only allowed to make queries to MEM K and EX. Polynomial time learnability means that there is an algorithm such that the time used is bounded by a polynomial in the size of the target and the largest counterexample seen so far. An analogous notion depending on the size and number of queries is used for polynomial query learnability [8].

We show that if a multi-agent learning framework is polynomial query (resp. time) epistemically learnable with only example queries then it is polynomial query (resp. time) exactly learnable with only equivalence queries; while the other direction does not hold. Example queries to EX are indeed less powerful than equivalence queries to EQ. Indeed, we show that if a multi-agent learning framework is polynomial query (resp. time) epistemically learnable with only example queries then it is polynomial query (resp. time) exactly learnable with only equivalence queries. This is summarized in Figure 1, together with known results about the relationship between exact learning and PAC learning. We then instantiate our learning framework to EL. We prove that satisfiability of conjunctive formulas of EL extended with epistemic modal operators (called conjunctive ELK) is PTime-complete (see, [8,Th. 5]). Conjunctive ELK captures the expressivity used in the epistemic learning model. Together with the results in Figure 1, the PTime complexity of the satisfiability problem of conjunctive ELK demonstrates that epistemic learning is a reasonable substitute to the exact learning model in the EL case. Finally, we transfer known results [3,4,6] for exact learnability of EL ontologies and its fragments to our learning model.