2 Preliminaries

We define the reasoning problem as follows: in a system of multiple agents, each agent has some background knowledge encoded in a knowledge base and receives information about the environment through the sensors, which are encoded as partial observations. We then ask the root agent queries about the environment. After receiving the partial observations, the agent returns with some degree of validity the answer for the specified query. In epistemic reasoning, we distinguish between what is true in the real world and what the agents know or believe about the world. For example, the beliefs of agent A about the world may differ from agent B’s knowledge, and what agent A believes B to know may differ from what B actually believes. In the context of multi-agent reasoning, we are interested in deciding the entailment of an input query about the other agents with respect to a background theory which contains the beliefs of agents in the application domain.

Syntax. Let $\mathcal{L}_n$ be a propositional language which consists of formulas from the finite set P of propositions and connectives $ \wedge, \vee, \neg, \rightarrow$ . Let $\mathcal{OL}_n$ be the epistemic language with additional modal operators. First, $K_i$ : $K_i \alpha$ is to be read as “agent i knows $\alpha$ ”, where i ranges over the finite set of agents $Ag = \{ A, B\}$ , which, for simplicity, assumes two agents, although this can be extended to many more agents. Second, $O_i \alpha$ is to be read as “all that agent i knows is $\alpha$ ” to express that a formula is all that is known. The only knowing operator is instrumental in capturing the beliefs as well as the non-beliefs of agents (Belle and Lakemeyer Reference Belle and Lakemeyer2014; Levesque Reference Levesque1990).

Somewhat unusually, as discussed above, borrowing from the dynamic version of $\mathcal{OL}_n$ (Belle and Lakemeyer Reference Belle and Lakemeyer2014), we introduce a dynamic operator $[\rho]$ such that $[\rho] \alpha$ is understood as formula $\alpha$ is true after receiving the observation $\rho$ . In particular, assume a finite set of observations OBS with elements consisting of conjunctions over the set P, for example, $OBS = \{ p, p \land q, \ldots, (p \land \neg q) \land r \}$ . The elements of OBS are used strictly within the dynamic operator $[\rho]$ . In order to interpret the action symbol, we will introduce a sensing function, one corresponding to each agent $obs_i$ , that takes as argument the action symbol and returns either the observation it corresponds to or simply returns true. A well-defined formula is then of the form $[\rho] \alpha$ where $\alpha$ is either propositional or at most mentions knowledge modalities $K_i$ . For example $obs_A(p \wedge q) = p \wedge q$ . It is not necessary that $obs_A(p \wedge q) = obs_B(p \wedge q)$ . For instance, we may also have $obs_B(p\land q) = true$ and $obs_A(p \land q) = p$ . In other words, the agents may obtain different observations from the same observational action. Suppose agent B looks at a card, he will be able to read what is written on the card whereas every other agent now knows that B has read the card but not what the card says. This is a simplified account from previous work by Belle and Lakemeyer (Reference Belle and Lakemeyer2014), mainly because we need to deal with a single observation for the purposes of this paper. It will be straightforward to extend it to a sequence of observations, however. Moreover, we will be appealing to Regression over sensing actions from that work in our approach.

Semantics. The semantics is provided in terms of possible worlds and k-structures (Belle and Lakemeyer Reference Belle and Lakemeyer2014). We distinguish the mental state of an agent from the real world and make use of epistemic states to model different mental possibilities. The standard literature uses the Kripke structure to model multi-agent epistemic states (Fagin et al. Reference Fagin, Halpern, Moses and Vardi1995). For this work, we use k-structures (Belle and Lakemeyer Reference Belle and Lakemeyer2014) instead, which deviates from the Kripke structure in the way the epistemic state is defined. The k-structure uses sets of worlds at different levels, the idea being that the number of levels corresponds to the number of alternating modalities in the formula. The i-depth is defined as follows:

Note that the dynamic modality has no impact on the i-depth of the formula, as it does not refer to the agent’s knowledge. The reason for choosing k-structures instead of the classical Kripke is because it provides a very simple semantics for only knowing in the multi-agent case (Belle Reference Belle2010). Beliefs are reasoned about in terms of valid sentences of the form: $O_A(\Sigma) \vDash K_A \alpha$ , read as “if $\Sigma$ is all that the agent A believes, then the agent knows $\alpha$ ”. In the interest of simplicity, we focus for the rest of the paper on only two agents A and B, where moreover A is the root agent, in the sense that we will be interested in what A knows and what A observes, and the queries will be posed regarding A’s knowledge. The i-depth of a formula $\alpha$ is agent dependent, so it can have A-depth k and B-depth j in terms of the nestings of modalities. A formula is i-objective if its i-depth is 0 and objective if both its A- and B-depths are 0. The k-structure might be used with a subscript to denote the agent possessing that mental state and a superscript to represent the depth of the modal operators.

We denote the set of worlds by $\mathcal{W}$ and the set of k-structures for an agent A by $e^k_A$ . A world $w \in \mathcal{W}$ is a function from the set P to $\{0,1\}$ , that is, a world stipulates which propositions are true, such that if $w[p] =1$ then p is true at the world, and false otherwise. A k-structure models an agent’s knowledge using the possible worlds approach: an agent A say, knows the statements that are true in all the worlds they consider possible. To account for what agent A knows about B’s knowledge, every possible world of A is additionally associated with a set of worlds that A knows B to consider possible.

Therefore, with two agents $\{A, B \}$ , a (k,j)-model is a triple $(e^k_A, e^j_B, w)$ , where $e^k_A$ is a k-structure for A, $e^j_B$ is a j-structure for B and w is a world. Before introducing satisfaction, we need to talk about the compatibility of worlds after an observation, and this is agent-specific ^{Footnote 1} . For any two worlds w, w’ and observation $\rho \in OBS \cup \{\langle\rangle\}$ , let us define $w\sim ^i_\rho w'$ iff $w[obs_i(\rho)] = w'[obs_i(\rho)] = 1$ . That is, agent i considers w and w’ to be compatible iff i’s sensory data for the observation $\rho$ is the same in both. When $\rho=\langle\rangle$ , then $w\sim ^i_{\rho} w'$ holds, that is, all worlds are compatible if no sensing has happened. Essentially, either $\rho$ is an action or the empty sequence where no observation has taken place. Now, we define satisfaction following the work of Belle and Lakemeyer (Belle and Lakemeyer Reference Belle and Lakemeyer2014) but modified to account for the adaptations we have introduced above:

So the main difference between only-knowing and knowing is the “iff” rather than “if” which forces every pair of world and $(k-1)$ -structure where $\alpha$ is satisfied to be included, and only these to be included in $e^k_A.$ Note also that on evaluating the epistemic operators, when $z = \langle\rangle$ , the compatibility can be fully ignored. But when $z\in OBS$ , we then look at compatible worlds and evaluate $\alpha$ in the corresponding models against the empty sequence. ^{Footnote 2} We say $\alpha$ is satisfiable if there is a model of appropriate depth, and valid if it is true in every such model. Note that it is the property of the logic that if $\alpha$ is of depth k, and it is valid in all k-structures, it is also valid in all $k+n$ -structures for $n\in \{0,1, \ldots\}$ . So for all intents and purposes, we can stop caring about the depth of formulas as any class of semantic structures of the corresponding or higher depth suffice for reasoning. We often write $e_A^k, e_B^j, w\models \alpha$ to mean $e_A^k, e_B^j, w, \langle\rangle\models \alpha$ .

3 Sensing

We model the agent receiving information about the world through observations. The observations received are represented as $[\rho]$ , where $\rho$ is an action standing for a propositional conjunction drawn from OBS, interpreted, say, as reading from a sensor. We now need to discuss how information from the sensors can be incorporated into the knowledge of the agent in a formal way. Recall that since we start with agents only-knowing formulas, we cannot simply conjoin new knowledge. That is why we leverage an insight from the dynamic multi-agent only knowing framework: what the agent knows after sensing is contingent on what was known previously in addition to observing some truth about the real world (Belle and Lakemeyer Reference Belle and Lakemeyer2014). In other words, the following is a theorem in the logic:

The proof is based on the fact that when the sensing action happens, we only look at worlds that agree with the sensed observation (in accordance with the semantics for the dynamic operator). Therefore not only must the sensed observation hold in the real world, but also knowing this observation must mean that $\alpha$ is known (assuming it was not known already). Note two points: first, the observations are assumed to not conflict with what was already known or with $\Gamma$ , which represents the real world; that is, as discussed before, we are operating under the setting of knowledge expansion and not belief revision. The agent may be ignorant about something and the sensing adds more knowledge to the agent, but it is not possible for the agent to know something which is then contradicted by an observation. This is the standard setting in the epistemic situation calculus (Scherl and Levesque Reference Scherl and Levesque2003). Second, the sensing theorem works very much like the successor state axiom for knowledge in the epistemic situation calculus (Scherl and Levesque Reference Scherl and Levesque2003); however, in the latter, it is a stipulation of the background theory, whereas here it is a theorem of the logic. The sensing theorem establishes that $[\rho]K_A\alpha \equiv o \land K_A(o \rightarrow[\rho]\alpha)$ , where $o = obs_A(\rho)$ , and it is the RHS that we will make use of in our learning theorem. Note, however, that in the RHS, the dynamic modality is now being applied to $\alpha.$ At this point, the sensing theorem applies recursively and stops when it is in the context of a propositional formula. That is, $[\rho]\alpha = \alpha$ if $\alpha$ is propositional; and $[\rho]\alpha = o' \land K_i(o'\rightarrow [\rho]\beta)$ if $\alpha = K_i \beta$ , where $o' = obs_i (\rho) $ .

This is the essence of the Regression Theorem (Belle and Lakemeyer Reference Belle and Lakemeyer2014), where the application of an observational action in the context of a propositional formula yields the formula itself because sensing does not affect truth in the real world. Only when it encounters an epistemic operator, it uses the RHS of the sensing theorem. In what follows, for improving readability, we abuse notation and sometimes use $\rho$ outside the dynamic operator to mean the corresponding observation w.r.t. the root agent. That is, we write a formula such as $\rho \land \alpha$ to mean $obs_A(\rho) \land \alpha$ . Likewise, we write $K_A(\rho \supset [\rho]\alpha)$ to mean $K_A(obs_A(\rho) \supset [\rho]\alpha)$ , that is, inside the dynamic operator $\rho$ is left as is but everywhere else it is being replaced by the observational formula that it corresponds to.

4 Reasoning

The language in general allows for arbitrary nesting of epistemic operators. And as already mentioned, at least for formulas not mentioning the dynamic operator and only knowing, k-structures can be shown to be semantically equivalent to the Kripke structures with respect to the entailment of a formula. What we are interested in now is finding a connection between validity and what we require in the learning algorithm. To do this we need to resolve two issues: first, how can observations be incorporated into the background knowledge, and second, how can the entailment of the query with respect to the background knowledge as well as the observations be evaluated?

It is important to appreciate that the second challenge deserves great attention because we are dealing with noisy observations. Roughly speaking, the way implicit learning works (Juba Reference Juba2013) given a set of noisy observations is that the conjunction of the background knowledge together with the observation is used to check if the query formula logically follows. Suppose this happens for a high proportion of the observations. In that case, the query is accepted by the decision procedure which can be seen as implicitly including whatever formula might be captured by the high proportion of observations. So checking logical validity will be an important computational component of the overall algorithm. We will only obtain a polynomial time learning algorithm if checking validity is in polynomial time. It is widely known that reasoning in the weak-S5 is PSPACE-complete (van Ditmarsch et al. Reference van Ditmarsch, Halpern, van der Hoek and Kooi2015). So what hope do we have? Not surprisingly, with the only-knowing operator, the reasoning is much harder, at the second level of the polynomial hierarchy even for a single agent (Rosati Reference Rosati2000). However, as it turns out, there is a very popular and interesting result: if one is interested only in the validity of the formulas $O(\Sigma) \rightarrow K \alpha$ , this can be reduced to propositional reasoning. (However, this, in fact, is co-NP hard (Levesque and Lakemeyer Reference Levesque and Lakemeyer2001), but that is another matter because much is known about bounded proofs in propositional logic (Juba 2012; Reference Juba2013). Likewise, when we consider multi-agent knowledge bases of the form $O_A(\phi \wedge O_B(\psi \wedge...) ...)$ , where $\phi$ and $\psi$ are objective formulas, and we are interested in the entailment of $K_A \alpha$ , where $\alpha$ does not mention dynamic “ $[\cdot ]$ ” nor “ $O_i$ ” operators, we can reduce it to propositional reasoning (Belle and Lakemeyer Reference Belle and Lakemeyer2014). The reduction to propositional reasoning is achieved using the Representation Theorem denoted by the operator $|| \cdot ||$ , first introduced by Levesque and Lakemeyer (Levesque and Lakemeyer Reference Levesque and Lakemeyer2001). It works by going through a formula and replacing knowledge of an objective sentence by either true/false according to whether the sentence is entailed by the given knowledge base $\Sigma$ . This idea is then generalized to non-objective knowledge by working recursively on formulas from the inside out.

Putting it together, suppose that $\phi, \psi$ are objective formulas and $\alpha$ is an epistemic formula that does not mention $\{ O_i, [\cdot]\}$ operators. Then $O_A(\phi \wedge O_B \psi) \vDash K_A \alpha$ if $\vDash ||\alpha||_{\phi, \psi}$ , where $||\alpha||_{\phi, \psi}$ is a propositional formula. The reduction works by slicing up the knowledge base and query at the modal operator and transforming these formulas into objective formulas.

Originally, the Representation Theorem used a second operator $RES[\cdot,\cdot]$ (Levesque Reference Levesque1990) in Cases 4 and 5, but for propositional languages, this operator simplifies to checking entailment w.r.t. the indicated agent’s knowledge base.

And then because p is an atom, which is objective, $||p||_{\phi, \psi}= p$ , so $||K_A K_B p || _{\phi, \psi}=\phi\rightarrow ||K_B p|| _{\phi, \psi}=\phi\rightarrow (\psi\rightarrow ||p||_{\phi, \psi})$

which finally results in checking the validity of $\phi \rightarrow (\psi \rightarrow p)$ , or equivalently $(\phi \wedge \psi) \rightarrow p$ .

The following example is adapted and modified from Belle and Lakemeyer (Reference Belle and Lakemeyer2014):

Suppose two agents A and B are playing a card game with cards numbered from 1 to 4. The cards have been shuffled and two face-down cards are dealt, one to each agent. A player picks a card, reads the number on it, and has to decide whether to challenge the other player or not. Once the other player responds by showing their card, the player with the highest number on the card wins.

We use the notation $N_A=\#1$ to represent that agent A has drawn card number 1 from the deck, and analogously for agent B we use $N_B$ . The initial conditions $\Sigma$ are represented by:

1. 1. $((N_{A} = \#1) \vee (N_{A} = \#2) \vee (N_{A} = \#3) \vee (N_{A} = \#4)) \wedge ((N_{B }= \#1) \vee (N_{B }= \#2) \vee (N_{B}= \#3) \vee (N_{B} = \#4))$ : each agent draws only one card from the deck;

2. 2. $(N_{A} = \#4) \equiv (N_{B} = \#1) \vee (N_{B} = \#2) \vee (N_{B} = \#3)$ : the card agent A draws must be distinct from agent B’s card (and likewise for other combinations);

3. 3. $W_A \equiv (N_A = \#2 \wedge N_B = \#1) \vee (N_A = \#3 \wedge N_B = \#1) \vee (N_A = \#4 \wedge N_B = \#1) \vee (N_A = \#3 \wedge N_B = \#2) \vee (N_A = \#4 \wedge N_B = \#2) \vee (N_A = \#4 \wedge N_B = \#3)$ ; Agent A wins the round if he draws a card with a higher number than agent B, and analogously when agent B is winning;

4. 4. $(\neg W_A \wedge \neg W_B)$ : initially, no agent has won the game; and

5. 5. finally, we also need to introduce the observational actions. For every card picking action $N_i = \#n$ , we assume an action $\rho_{in}$ . Clearly, such an action should tell agent i that his card is n, but should not reveal anything else to the other agent. (Interestingly, by the above formulas, the agent i should be able to infer that the other agent has any card but n; we will come to this later.) So, we define $obs_i(\rho_ {in}) = (N_i = \#n)$ but $obs_j(\rho_{in}) = true$ for $j\neq i.$ By extension, define the action $\rho_{in,jk}$ to mean i has read the value n and j the value k, and thus, $obs_i(\rho_{in,jk}) = n$ and $obs_j(\rho_{in,jk}) = k.$

Both agents A and B have the same initial knowledge about the game, encoded by a formula $\phi$ which also includes the sensing rule described above. Let us say that agent A draws card $\#4$ and agent B draws card $\#3$ . These observations are represented by $(N_{A} = \#4) \wedge (N_{B}=\#3)$ . Since we are making the case for the root agent to be A we have the initial theory as $\theta = O_A(\phi \wedge O_B(\phi)) \wedge [(N_{A} = \#4) \wedge (N_{B}=\#3)]$ . We can then reason about beliefs and non-beliefs. The following properties follow:

1. 1. $\theta \vDash \neg K_A (N_A = \#1) \wedge \neg K_A (N_A = \#2) \wedge \neg K_A (N_A = \#3) \wedge \neg K_A (N_A = \#4)$ ;Initially, agent A does not know the card he has.

2. 2. $\theta \vDash [\rho_{A4}] K_A (N_{A}=\#4)$ ; After A picks up his card, and then sensing the card, agent A knows that the number is 4.

3. 3. $\theta \vDash [\rho_{A4}] K_A \neg (N_{B}=\#4)$ ; The logical reasoning allows A to infer that $N_B$ is one of $\{\#1, \#2, \#3\}.$

4. 4. $\theta \vDash [\rho_{A4}] K_A (\neg K_B ((N_A = \#1))$ ; Agent A knows that agent B does not know the number on A’s card, by means of his knowledge of the sensing actions (likewise for the $N_A = \# 2, N_A = \#3, N_A = \#4$ ).

5. 5. $\theta \vDash [\rho_{A4}] K_A K_B(K_A (N_A = \#1) \vee K_A(N_A \neq \#1))$ ; Agent A knows that agent B does not know the number of his card, but nonetheless knows that A knows whether he has the card.

6. 6. $\theta \vDash [\rho_{A4}] K_A W_A \land K_A \neg K_B W_A$ ; By logical reasoning, A infers that he has won but knows that B does not know this.

7. 7. $\theta \vDash [\rho_{A4,B3}] K_A (K_B\neg (N_{B}=\#4))$ ;

After both agents see their cards, A knows that B knows his card, which cannot be $N_{B} = \#4$ since A has the card with the number 4. At this point in the game, if B had obtained the card with value 1, only then would he know he has lost. But since he has the value 3, he does not know that he has lost, because, after all, A could have the card with value 2. By extension, A also does not know that B does not know. This is because only if B’s card had the value 1, B knows that he has lost. But in all other circumstances, B could still imagine that he has the higher card.

5 PAC semantics

Various approaches have been proposed in the attempt to gain efficient and robust learning, including inductive logic programming (Muggleton and de Raedt Reference Muggleton and de Raedt1994) and concept learning (Valiant Reference Valiant1984). Concept learning, also known as PAC learning is a machine learning framework where the classifier receives a finite set of samples from distribution and must return a generalization function within a class of possible functions. This approach aims to produce with high probability (P) a function that has a low generalization error (AC). In the context of logic, Valiant (Reference Valiant2000) proposed the PAC Semantics, a weaker semantics (compared to the classical entailment) for answering queries about the background knowledge, that integrates noisy observations against a logical background knowledge base. The knowledge is represented on one hand by a collection of axioms about the world, and on the other, by a set of examples drawn from an (unknown) distribution. In this way, the algorithm uses both forms of knowledge to answer a given query, which one may not be able to answer using only the background knowledge or the standalone examples. The output generated by this approach does not, however, capture the sense of validity in the standard (Tarskian) sense; rather, validity is defined as follows:

Suppose we have a distribution $\mathcal{D}$ supported on $E_A ^k\times E_B ^j \times \mathcal{W}$ and $\alpha$ an epistemic formula $\alpha \in \mathcal{OL}_n$ , that does not mention $\{ O_i, [\cdot]\}$ operators. Then we say that $\alpha$ is $(1-\varepsilon)$ -valid iff $Pr_{(e^k_A, e^j_B, w) \in E_A ^k\times E_B^j \times \mathcal{W}} [(e^k_A, e^j_B, w) \vDash \alpha] \geq 1- \varepsilon$ , where $(e^k_A, e^j_B, w)$ is a model from $E_A ^k\times E_B ^j \times \mathcal{W}$ . If $\varepsilon = 0$ , we say that $\alpha$ is perfectly valid.

It is worth pointing out that the overall thrust of the framework is quite different from popular approaches such as inductive logic programming (Muggleton and de Raedt Reference Muggleton and de Raedt1994) and statistical relational learning (Getoor and Taskar Reference Getoor and Taskar2007; De Raedt and Kersting Reference De Raedt and Kersting2011), etc. In inductive logic programming, an explicit hypothesis is learned that captures only the examples currently provided, and rarely is there an explicit account of how the hypothesis might reflect some unknown distribution from which the examples are drawn. In statistical relational learning, a hypothesis captures the distribution of the examples provided in terms of a logical formula or a probabilistic logical formula.

Once again, no accounts are provided about how this formula might capture the unknown distribution from which the examples are drawn. The key trick is to develop a decision procedure that checks the entailment of the query against the knowledge base by conjoining the observations to the background theory and checking the queries. Then, if for a higher proportion of observations, the query is indeed contained, we conclude that the explicit knowledge base together with the implicit knowledge base entails the query and all of this is robustly formalized using the PAC semantics (Valiant Reference Valiant2000). The proportion of times the query formula evaluates to true can be used as a reliable indicator of the formula’s degree of validity, as guaranteed by Hoeffding’s inequality (Hoeffding Reference Hoeffding1963).

Theorem 10 (Hoeffding’s inequality)

Let $X_1,\ldots,X_m$ be independent random variables taking values in [0,1]. Then for any $\varepsilon>0$ ,

$$\Pr\left[\frac{1}{m}\sum_{i=1}^mX_i\geq \mathbb{E}\left[\frac{1}{m}\sum_{i=1}^mX_i\right]+\varepsilon\right]\leq e^{-2m\varepsilon^2}.$$

The agent will have some knowledge base encoded in the system, and will also be able to sense the world around them and receive readings describing the current state of the world. These readings are generally correct for that environment but are neither fully accessible nor are they exact. As a consequence, the observations can be noisy or inconsistent with each other, but they are always consistent with the knowledge base. So in the spirit of knowledge expansion, the agent may be ignorant about many things and the agent is informed by the observations it makes. These observations only focus on a few properties of the world, as would be expected from most physical sensors in robotics and other applications. Formally we introduce a masking process that randomly reveals only a few properties of the world (Michael Reference Michael2010). These readings are conjunctions of propositional atoms and are drawn independently at random from some probability distribution $\pmb{M}$ over $\mathcal{L}_n$ which is unknown to the agent. For example, a smartwatch might only be getting readings about the heart rate of the person wearing the watch but not the blood oxygen levels (Rader et al. Reference Rader, Mocanu, Belle and Juba2021). In the multi-agent setting, sensors may only reveal what cards the agent itself holds but may not provide information about the cards held by the other agents as is intuitive. An agent attempting to sense the same environment twice could end up with two different observations, and so the masking process captures this stochastic nature of sensing.

The masking process induces a probability distribution $\pmb{M}(\mathcal{D})$ over observations $\rho \in OBS$ modeling the readings of an agent’s sensors. We assume from now on that this modeling is performed on the root agent’s sensors. The masking process can be understood in two different ways: either the readings are absent due to a stochastic device failure, or the agent is unable to concurrently detect every aspect of the state of the world. In essence, the model incorporates unforeseen circumstances like a probabilistic failure or an agent’s sensors’ inability to provide readings (de C. Ferreira et al. 2005). So the formalization of the reasoning problem should capture this limitation somehow. The reasoning problem of interest becomes deciding whether a query formula $\alpha$ is $(1-\varepsilon)$ -valid. Knowledge about the distribution $\mathcal{D}$ comes from the set of examples $\rho^{(c)} \in \mathcal{L}_n$ . Additional knowledge comes from a collection of axioms, the knowledge base $\Sigma$ . We do not have complete knowledge of the models drawn from $\mathcal{D}$ , instead, we only have the observations $\rho$ sampled from $\pmb{M}(\mathcal{D})$ and the knowledge base $\Sigma$ .

We assume here two agents A and B, but it can be generalized to multiple agents, from which agent A is the root agent. The background knowledge is represented by $\Sigma, \Sigma' \in \mathcal{OL}_n$ , where $\Sigma$ corresponds to agent A and $\Sigma'$ corresponds to agent B. The input query $\alpha$ is of the form $M^l \alpha'$ , where M denotes a sequence of bounded modalities, that is, $K_A K_B K_A \alpha ' = M^3 \alpha'$ , the query is of maximal depth of k, j which are the i-depths of the k-structures for agents A and B. And finally, we draw m partial observations which are of propositional format $\rho^{(1)},\rho^{(2)}, ..., \rho^{(m)}$ . In implicit learning, the query $\alpha$ is answered from observations directly, without creating an explicit model. This is done by means of entailment: we repeatedly ask whether $O_A(\Sigma) \vDash [\rho^{(c)}] K_A \alpha$ for examples $\rho^{(c)}\in \pmb{M}(\mathcal{D})$ where $c \in \{1,..., m\}$ . So this entailment checking with respect to each observation $\rho^{(c)}$ becomes our best approximation to $(1-\varepsilon)$ -validity. If at least $(1-\varepsilon)$ fraction of the examples entail the query $\alpha$ , the algorithm returns Accept. The estimation is more accurate the more examples we use. The concepts of accuracy and confidence are captured by the hyper-parameters $\gamma, \delta \in (0,1)$ , where $\gamma$ bounds the accuracy of the estimate and $\delta$ bounds the probability the estimate is invalid.

Since we are only concerned with entailment and not proof theory here, there is essentially no distinction between the implicit knowledge itself and the provable consequences/entailments of the implicit knowledge. We can just talk about whether or not $\alpha$ is implicitly known to A. These formulas are witnessed true with probability $1- \varepsilon$ ; in particular, a proportion of them may still evaluate to false with probability up to $\varepsilon$ . We will now move on and motivate the learning algorithm. As observed before, the key step in the decision procedure is given the partial observations as discussed above and the background theory which is of the form $O_A(\phi \wedge O_B(\psi ...))$ or simply $O_A(\Sigma)$ , we check the entailment of the query given the observations against the background theory. As we discussed in Theorem 4, this can be reduced to a statement of the following form: $O_A(\Sigma) \vDash \rho \wedge K_A(\rho \rightarrow \alpha)$ .

Algorithm 1: DecidePAC Implicit learning reduction

Let us demonstrate the functionality of the PAC framework by going through the example previously outlined and considering a real-life scenario where some statement that often (but not always) holds may be inferred from the information available to the agent.

6 Tractability and future work

One of the main motivations of implicit learning, following the works of Khardon and Roth on learning-to-reason framework (Khardon and Roth Reference Khardon and Roth1997), and Juba on implicit learnability (Juba Reference Juba2013), was to enable tractable learning for reasoning by bypassing the intractable step of producing an explicit representation of the knowledge. Indeed, if the observations are sufficiently nice, reasoning with the PAC semantics may even be more efficient than classical reasoning (Juba Reference Juba2015). The problem is only more acute in multi-agent settings: in prior work on multi-agent reasoning (Lakemeyer and Lesp´erance 2012), Lakemeyer proposed a polynomial time algorithm if the knowledge base was encoded as a proper epistemic knowledge base which proved to be computationally costly. Indeed, most prior work on efficient multi-agent reasoning requires such an expensive compilation step in order to introduce a conjunctive observation to an agent’s knowledge base. By using the Representation Theorem (Belle and Lakemeyer Reference Belle and Lakemeyer2014), we can reduce the entailment checks in Algorithm 1 to propositional queries. In turn, if these propositional queries are members of an adequately restricted fragment such as Horn clauses or more generally, those provable using bounded-space treelike resolution, then polynomial-time algorithms exist for deciding such queries (Kullmann Reference Kullmann1999). Similarly, Liu et al. (Reference Liu, Lakemeyer and Levesque2004) proposed a sound and (eventually) complete method for reasoning in first-order logic that is polynomial in the size of the knowledge base. The tractability is guaranteed using a notion of mental effort characterized by the parameter k, for example, if $k=0$ , then a sentence $\alpha$ is believed only if it appears explicitly in the given knowledge base. The downside of this approach is that the complexity of converting the entire knowledge base to a required CNF formula increases exponentially as the parameter k increases. What remains to be done, that we leave for future work, is to establish a guarantee that the propositional reasoning needed to decide a query remains in such a tractable fragment. Alternatively, it might be sensible to take one of the limited belief reasoning logics (Liu and Levesque Reference Liu and Levesque2005) and integrate it into our learning framework. All of these are interesting directions for future work.

7 Related work

Several results have been obtained by leveraging PAC semantics’ advantages in order to obtain implicit learning. After first being formalized by Juba (Reference Juba2013) for the propositional logic fragments and obtaining more efficient reasoning there (Juba Reference Juba2015), Belle and Juba Belle and Juba (Reference Belle and Juba2019) demonstrated an integration of the PAC semantics with first-order logic fragments. Later on, work by Mocanu et al. Mocanu et al. (Reference Mocanu, Belle and Juba2020) showed that polynomial reasoning can be achieved efficiently with partial assignments for standard fragments of arithmetic theories. They proposed a reduction from the learning-to-reason problem for a logic to any sound and complete solver for that fragment of logic. On the empirical side, Rader et al. Rader et al. (Reference Rader, Mocanu, Belle and Juba2021) proposed an empirical study for learning optimal linear programming objective constraints which significantly outperforms the explicit approach for various benchmark problems. Although polynomial guarantees are obtained for various language domain fragments, they do not offer the expressiveness of a multi-agent language, which is what our work considered.

On the epistemic logic axis, Lakemeyer and Lesperance have proposed a form of epistemic reasoning in which the knowledge base is encoded as a set of modal literals (PEKB) (Lakemeyer and Lespérance Reference Lakemeyer and Lespérance2012). Although this approach showed some computational speedup when it comes to reasoning, it did carry along the disadvantage of converting both the knowledge base and the query to certain formats before entailment is checked. This conversion becomes computationally costly as the modal depth increases, and although this form of knowledge might be useful for certain applications, it does not handle an important epistemic notion: knowing-whether (Fan et al. Reference Fan, Wang and van Ditmarsch2013). That means that the language does not cover any form of incomplete knowledge or disjunctions (horn clauses) and so very limited forms of inference were possible. Although an extension to knowing-whether was later proposed in work by Miller et al. (Reference Miller, Felli, Muise, Pearce and Sonenberg2016), it still lacks arbitrary disjunctions, which our framework can handle fully. In a non-modal setting, Lakemeyer and Levesque (Reference Lakemeyer and Levesque2004) proposed a tractable reasoning framework for disjunctive information. In another work, Fabiano (Reference Fabiano2019) proposed an action-based language for multi-agent epistemic planning and implemented an epistemic planner based on it. Work by Muise et al. (Reference Muise, Belle, Felli, McIlraith, Miller, Pearce and Sonenberg2022) addresses the task of synthesizing plans that necessitate reasoning about the beliefs of other agents. Learning is not addressed in any of these. Likewise, in research work by Lakemeyer and Levesque (Reference Lakemeyer and Levesque2020) a logic of limited belief with a possible-worlds semantics is proposed. Each epistemic state is represented as sets of three-valued possible worlds, which allows some tractability with epistemic reasoning, but it is limited to the single-agent case and also does not address learning. In the context of dynamic epistemic logic (Baltag and Renne Reference Baltag, Renne and Zalta2016), there is some recent work on “qualitative learning” (Bolander and Gierasimczuk Reference Bolander, Gierasimczuk, van der Hoek, Holliday and Wang2015) which considers learning in the limit for propositional action models. This is very different in thrust from ours, where we are interested in answering queries from noisy observations with robustness guarantees. Although there are many research works focusing on learning in multi-agent settings for coordination and competition (Albrecht and Stone Reference Albrecht and Stone2017), we are not aware of any work that addressed arbitrary nesting of belief operators in the style of $K45_n$ in a learning setting.