-In formal approaches to inductive learning, the ability to learn is understood as the ability to single out a correct hypothesis from a range of possibilities. Although most of the existing research focuses on the characteristics of the learner, in many paradigms the significance of the teacher's abilities and strategies is in fact undeniable. Motivated by this observation, in this paper we highlight the interactive nature of learning by proposing a game-theoretical and logical approach. We consider learning as a sabotage-type game between Teacher and Learner, and present di erent variants based on the level of cooperativeness and the actions available to the players. We characterize the existence of a winning strategy in such games by formulas of Sabotage Modal Logic, analyzing also their complexity. Our work constitutes the first step towards a unified game-theoretical and logical approach to formal learning theory.
The objective of this paper is to investigate how logics
for interaction in multi-agent systems can be used to
reason about strategic abilities and information flow during
the learning process. Formal learning theory (see e.g. [
We give a high-level analysis of the described process.
First, we treat learning as a procedure of singling out one
correct hypothesis from a range of possibilities. Second,
we see this procedure not as a one-move choice; instead,
we allow many steps of update before the conclusion is
reached. These two properties make our notion of
learning di erent from the concept of learning formalized as
epistemic update in Dynamic Epistemic Logic (see e.g. [
The paper is structured as follows. Section II introduces the framework of learning as Sabotage Games, shows how sabotage modal logic can express the existence of winning strategies in three di erent versions of Sabotage Learning Games and gives complexity results for them. Section III analyzes Sabotage Learning Games in which the players do not need to move in alternation. Section IV presents a refined interactive view on teaching based on existing learning algorithms. Section V concludes.
counterexamples model [
Let us consider a very simple “classroom” situation with one teacher and one learner. From our high-level
hE0; v0i is given by hE; vi. Round k + 1 from position hEk; vki consists of Runner moving to some vk+1 such Learning Model Sabotage Games that E(vk; vk+1) > 0, and then Blocker removing an hypotheses states edge (v; v0) such that Ek(v; v0) > 0. The new position is correct hypothesis goal state hEk+1; vk+1i, where Ek+1(v; v0) := Ek(v; v0) 1 and, for every possibility of a mind change from edge from state a to b (u; u0) , (v; v0), Ek+1(u; u0) := Ek(u; u0). The match ends if hypothesis a to hypothesis b a player cannot make a move or if Learner reaches the a mind change from hypothesis a transition from state a to b goal state, which is the only case in which he wins. to hypothesis b Remark 1: It is easy to see that Sabotage Games have giving a counterexample that removing a transition between the history-free determinacy property: if one of the players emliimndincahteasngtehferopmosasitboilbity of a a and b has a winning strategy then she has a winning strategy that depends only on the current position. Then, each round can be viewed as a transition from a Sabotage perspective, learning is a step-by-step process through Game SG = hV; Ek; vk; vgi to another Sabotage Game which Learner changes his information state, and the SG0 = hV; Ek+1; vk+1; vgi, since previous moves become process is successful if he eventually reaches a state irrelevant. We will use this fact through the whole paper. representing the goal. The information Teacher provides Also, by edges and vertices of SG = hV; E; v; vgi, we will can be seen as feedback about Learner’s current con- mean edges and vertices of its underlying directed multijecture, allowing him to rule out possible changes of graph (V; E). mind. We can represent the situation as a graph whose In this definition of the Sabotage Game, Blocker revertices represent Learner’s possible information states moves an edge between two states v; v0 by decreasing and edges stand for transitions between them. During the value of E(v; v0) by 1. As we will see later, this the learning process, Learner can change his information definition of the game based on the above definition state by moving along the edges and Teacher can cut o of multi-graphs can lead to some technical problems edges, thereby preventing Learner from making certain when transforming such a graph into a Sabotage Model. transitions. One state is associated with the learning goal: Therefore, we will now present an alternative definition, if Learner reaches it, we say that the learning process which we later show (Theorem 1) to be equivalent with has been successful. The correspondence between the respect to the existence of a winning strategy. learning model from formal learning theory and our Definition 2.3: Let = fa1; : : : ang be a finite set of labels. proposal is described in Table I. A directed labelled multi-graph is a tuple G = (V; E) where
Observe that in learning from queries and counterex- V is a set of vertices and E = (Ea1 ; : : : ; Ean ), where Eai amples, a counterexample results in the absolute removal V V for each ai 2 . of some initially possible hypothesis. Our setting gen- In this definition, labels from are used to represent eralizes this idea: the removal of a transition need not multiple edges between two vertices; E is simply an make the target vertex unreachable. ordered collection of binary relations on V with labels from . Then, the definition of the game is as follows.
A. Sabotage Games Definition 2.4: A Labelled Sabotage Game SG =
Our perspective on learning leads naturally to the hV; E; v; vgi is given by a directed labelled multi-graph
framework of Sabotage Games [
Definition 2.1 ([
The Sabotage Game is defined as follows. What is said in Remark 1 also holds for Labelled
SaboDefinition 2.2 ([
Observation 1: Let SG = hV; E; v0; vgi and SG0 = hV; E0; v0; vgi be two Labelled Sabotage Games that di er only in the labels of their edges, that is, 8(v; v0) 2 V
V : jfEai j (v; v0) 2 Eai gj = jfE0ai j (v; v0) 2 E0agj;
Game SLGUE SLGHU where j j stands for cardinality. Then Runner has a winning strategy in SG i he has a winning strategy SLGHE in SG0 .
We will now show that the problems of deciding whether Runner has a winning strategy in each of the by definition of f , choosing v1 is also a legal move for Sabotage Games SG and SG are polynomially equiva- Runner in f (SG) and, since he can win every f (SG)0, he lent. We start by formalizing the problems. has a w.s in f (SG).
Definition 2.5: The decision problem SABOTAGE is From right to left, Runner having a w.s. in f (SG) defined as follows. means that he can choose some v1 with (v0; v1) 2 Ei INPUT: A Sabotage Game SG = hV; E; v0; vgi. for some i m such that he has a w.s. in all games QUESTION: Does Runner have a winning strategy f (SG)0 resulting from Blocker’s move. Choosing v1 is in SG? also a legal move of Runner in SG. Suppose that Blocker Definition 2.6: The decision problem -SABOTAGE is replies by choosing (v; v0). Let us call the resulting game defined as follows. SG0. By assumption and Observation 1, Runner also has a w.s. in the game f (SG0) which is the result from Blocker INPUT: A Sabotage Game on a labelled multi-graph choosing ((v; v0); E(v; v0)). Since f (SG)0 = f (SG0), we can SG = hV; E; v0; vgi. apply the inductive hypothesis.
QUESTION: Does Runner have a winning strategy in SG ? Let us see now how SG can be polynomially reduced Theorem 1: SABOTAGE and -SABOTAGE are poly- to SG. Given SG = hV; E; v; vgi with = fa1; : : : amg, nomially equivalent. define f 0(SG ) := hV; E; v; vgi, where E(v; v0) := jfEai j
Proof: We show that the problems can be polynomi- (v; v0) 2 Eai gj. ally reduced to each other. Showing that Runner has a w.s. in SG i he has one in
First we show that SABOTAGE can be reduced to - f (SG ) is straightforward, and can be done by induction SABOTAGE. Given a Sabotage Game SG = hV; E; v0; vgi, on n := Pa2 jEaj. Both f and f 0 are polynomial. let m := maxfE(u; u0) j (u; u0) 2 (V V)g. Define the Labelled Sabotage Game f (SG) := hV; E; v0; vgi where B. Sabotage Learning Games E := (E1; : : : ; Em) and each Ei is given by Ei := f(u; u0) 2 Based on the Sabotage Games framework, we define V V j E(u; u0) ig. Sabotage Learning Games as follows.
We show that Runner has a winning strategy (w.s.) in Definition 2.7: A Sabotage Learning Game (SLG) is a SG i he has one in f (SG). The proof is by induction on Labelled Sabotage Game played by Learner (L, taking the n = P(v;v0)2V V E(v; v0), which is the number of edges of role of Runner) and Teacher (T, taking the role of Blocker). SG. Note that by definition of f , n = Pii==1m jEij, that is, We distinguish between three di erent versions, SLGUE, f (SG) has the same number of edges. SLGHU and SLGHE, di ering in the winning conditions
The base case is straightforward since in both games (given in Table II).
Runner has a w.s. i v0 = vg. For the inductive case, The di erent winning conditions correspond to di
erfrom left to right, suppose Runner has a w.s. in the game ent levels of Teacher’s helpfulness and Learner’s
willingSG = hV; E; v0; vgi with n + 1 edges. Then, there is some ness to learn. We can have an unhelpful teacher and an
v1 2 V such that E(v0; v1) > 0 and Runner has a w.s. eager learner (SLGUE), but there is also the possibility
for all games SG0 = hV; E0; v1; vgi that result from Blocker of a helpful teacher and an unwilling learner (SLGHU).
removing any edge (u; u0) with E(u; u0) > 0. Note that The cooperative case corresponds to the version with a
all such games SG0 have just n edges, so by induction helpful teacher and an eager learner (SLGHE).
hypothesis Runner has a w.s. in f (SG0). But then, by We now show how Sabotage Modal Logic can be used
Observation 1, Runner has also a w.s. in all games f (SG)0 for reasoning about Learner’s and Teacher’s strategic
that result from removing an arbitrary edge from f (SG), power in the learning games previously defined.
because for any removed edge (u; u0), the only possible
di erence between f (SG0) and f (SG)0 is in the labels of C. Sabotage Modal Logic
the edges between u and u0 (in f (SG0) the removed label Sabotage Modal Logic (SML) has been introduced in
was the largest, in f (SG)0 the removed label is any). Now, [
Definition 2.8 (Sabotage Modal Language [
a M(vi;v0) := hW; Ra1 ; : : : Rai 1 ; Rai n f(v; v0)g; Rai+1 ; : : : Ran ; Vali:
M = hW; (Ra)a2 ; Vali and a world w 2 W, atomic propositions, negations, disjunctions and standard modal formulas are interpreted as usual. For the case of “transition-deleting” formulas, we have M; w j= ^–a i 9 v; v0 2 W : (v; v0) 2 Ra & M(av;v0); w j= ; and –a is defined to be equivalent to : ^–a: :
Theorem 2 ([
Note that “combined complexity” means that both the formula and the model are taken as input.
can construct a Pointed Sabotage Model M(SG ) in a straightforward way.
Definition 2.12: Let SG = hV; E; v0; vgi be a Sabotage Game with E = (Ea)a2 . We define the Pointed Sabotage Model (M(SG ); v0) over the set of atomic propositions PROP := fgoalg with
M(SG ) := hV; E; Vali; where Val(goal) := fvgg:
In the light of this construction, SML becomes useful for reasoning about players’ strategic power in SLGs. For each winning condition in Table II, we can define ()) L having a w.s. in SG implies that v0 = vg. Thus, M(SG ); v0 j= goal and hence, M(SG ); v0 j= 0UE.
(() M(SG ); v0 j= 0UE means that M(SG ); v0 j= goal. Thus v0 = vg. Hence, L wins SG immediately.
Inductive case ()) Suppose that SG has n+1 edges, and assume that L has a w.s. There are two possibilities. (1) v0 is the goal state; then M(SG ); v0 j= goal and hence M(SG ); v0 j= UE . (2) v0 is not the goal state. Since L has a w.s., n+1 there is some v1 2 V such that (v0; v1) 2 Ea0i for some ai 2 and no matter which pair ((u; u0); aj) 2 (V V) with (u; u0) 2 Ea0j T chooses, L has a w.s. in the resulting game SG0 = hV; E1; v1; vgi, with E1 = (Ea01 ; : : : Ea0j 1 ; Ea0j n fu; u0g; Eaj+1 ; : : : Ea0j j ). Now, SG0 has n edges and thus by 0 inductive hypothesis, M(SG0 ); v1 j= nUE. This implies M(SG ); v0 j= ^– nUE and thus M(SG ); v0 j= nU+E1. (() M(SG ); v0 j= goal _ ^– nUE implies that v0 is the goal state (so L wins immediately) or else there is v1 accessible from v0 such that M(SG ); v1 j= – nUE, that is, M(SG )(avi;v0); v1 j= – nUE for any ((v; v0); ai) 2 (V V) . By inductive hypothesis, this gives L a w.s. at v1 in a game that results from removing any edge from SG , and hence a w.s. at v0 in the game SG .
They key observation for the left-to-right direction of this proof is that the model that results from removing an edge from M(SG ) is always a model that results from transforming a Labelled Sabotage Game into a model. With the original definition of a Sabotage Game, this is not the case: after removing an edge between v and v0 with label k, the resulting model does not need to be the image of a multi-graph because the label of the removed edge does not need to be the biggest of them. Another way to look at it is the following: the multiple edges of the original multi-graph can be seen as implicitly labelled by numbers, and the existence of an edge labelled with k implies the existence of edges labelled with 1; : : : ; k 1. This property is not preserved when Teacher removes an edge with an arbitrary label from the model M(SG).
Consider now the game SLGHU, with Teacher trying to force Learner to reach the goal state. Inductively, define
HU := goal; 0 nH+U1 := goal _ (^> ^ ^– nHU):
existence of a winning strategy for Teacher. Note that in order to win, Teacher has to make sure that Learner does not get stuck before he has reached the goal state. This is why we need the conjunct ^> in the formula.
Theorem 4: Teacher has a winning strategy in the SLGUE game SG = hV; E0; v0; vgi i M(SG ); v0 j= nHU, for n := Pa2 jEa0j.
Proof: Similar to the proof of Theorem 3.
Finally, consider SLGHE, with Teacher and Learner winning i Learner reaches the goal state. The corresponding formula is defined as follows 0HE := goal;
nH+E1 := goal _ ^ ^– nHE:
strategy in the SLGHE game SG = hV; E0; v0; vgi i M(SG ); v0 j= nHE, for n := Pa2 jEa0j.
Proof: Note that L and T have a joint w.s. i there is a path from v0 to vg. From left to right this is obvious. From right to left, if there is such path, then there is also one without cycles; then, there is a joint w.s. that follows the path and at each step removes the edge that has just been used. The Theorem follows by observing that nHE expresses the existence of such path.
The previous results are summarized in Table III.
Intuitively, some versions of the Sabotage Learning Game are simpler than others. With a helpful teacher and an eager learner, the learning process should be easier than with an unhelpful teacher or a unwilling learner. This is indeed reflected in the computational complexity of deciding in a given game whether the winning condition is satisfied.
We have shown that our three winning conditions
(Table III) can be expressed in SML, and Theorem 2
(proved in [
For SLGUE – the standard Sabotage Game –
PSPACEhardness is shown by reduction from QBF [
Theorem 6 ([
As mentioned above, for SLGHU we obtain a PSPACE upper bound.
Theorem 7: SLGHU is in PSPACE.
Proof: Follows from Theorem 2 and Theorem 4.
It remains to be shown whether SLGHU is also PSPACE-hard. Whereas at first sight, SLGHU and SLGUE might seem to be duals of each other, the relationship between them is more complex due to the di erent nature of the players’ moves (Learner moves locally by choosing an accessible state, whereas Teacher moves globally, manipulating the structure in which Learner moves).hus, a reduction from SLGUE to SLGHU is not straightforward. Let us now look at SLGHE. This game is of a di erent nature than the two previous ones. It is cooperative, and a winning strategy is a joint strategy for both players. Such a strategy does not need to take into account all possible moves of the opponent. This suggests that this version should be less complex than SLGUE and SLGHU.
The following result shows that at least for the
comparison of SLGUE and SLGHE, this is indeed the case:
for an eager learner, learning with a helpful teacher
is easier than learning with an unhelpful one. This
follows from the fact that the winning condition of
SLGHE is satisfied i the goal vertex is reachable from
the initial vertex (note that Learner moves first). Thus,
determining whether Teacher and Learner can win
SLGHE is equivalent to solving the REACHABILITY
(st-CONNECTIVITY) problem, which is known to be
nondeterministic logarithmic space (NL)-complete [
Theorem 8: SLGHE is NL-complete.
Proof: Polynomial equivalence of SLGHE and REACHABILITY follows from the argument given in the proof of Theorem 5.
Table IV summarizes the complexity results for the di erent versions of SLG.
In the case of an eager Learner, the complexity results when removing an edge would have made the goal agree with our intuitions when comparing the cooper- unreachable from the current vertex. However, we can ative version of the Sabotage Game (SLGHE) with the show that this is not the case. First, we state the following non-cooperative one (SLGUE). The easiest way to learn lemmas. for an eager Learner is when the Teacher is helpful. Lemma 1: For any SLG HU hV; E; v0; vgi, if there is a path from v0 to vg and there is no path from v0 to a state
III. Relaxing strict alternation from where vg is not reachable, then T has a winning As mentioned above, Learner’s moves in the graph strategy. are interpreted as changes of information states. Then, Proof: By assumption, all states reachable from v0 when Teacher removes an edge, she actually informs are on paths to vg. Therefore, even if T will refrain from Learner which changes of information state should not removing any edge, L will always be on some path to be performed. In this perspective, Learner’s moves can the goal. There are two possibilities: either the path to be seen as internal ones while Teacher’s moves can the goal does not include a loop or it does. If it does not be interpreted externally. Due to this asymmetry, each then T can simply wait until L will arrive to the goal. Learner’s move does not in principle need to be followed If it does, in order to win T can remove the edges that by a teacher’s move. lead into the loops in such a way that vg is still reachable
Definition 3.1: A Sabotage Learning Game without strict from any vertex. L will eventually have to move to vg. alternation (for Teacher) is a tuple SLG = hV; E; v0; vgi. Lemma 2: Consider the SLG HU game hV; E; v0; vgi. If T Moves of Learner are as in the Sabotage Learning Game has a winning strategy and there is some edge (v; v0) 2 Ea and, once he has chosen a vertex v1, Teacher has a for some a 2 such that no path from v0 to vg goes via choice between removing an edge, in which case the next the edge (v; v0), then T also has a winning strategy in game is given as in SLG, and doing nothing, in which hV; E0; v0; vgi, where E0 is the result of removing (v; v0) case the next game is hV; E; v1; vgi. We again distinguish from Ea. between three versions, SLG UE, SLG HU and SLG HE, Proof: If v is not reachable from v0, it is easy to see with winning conditions given as before. that the claim holds. Let us consider the case that v is
Though we provide Teacher with an additional pos- reachable from v0. Since there is no path to vg visiting sible move, this does not change her winning abilities. v, T’s winning strategy should keep L away from it In the rest of this section we show that, for the three (otherwise L would win). Hence, T can also win if the variations of a Sabotage Learning Game, a player has a edge (v; v0) is not there. w.s. in SLG i she has a w.s. in SLG. Theorem 10: If Teacher has a winning strategy in the SLG HU hV; E; v0; vgi, then she also has a winning strategy in which she removes an edge in each round.
Proof: The proof proceeds by induction on the number of edges n = Pa2 jEaj.
The base case is straightforward. For the inductive case, assume that T has a winning strategy in SLG HU hV; E; v0; vgi with Pa2 jEaj = n + 1.
Then if v0 = vg, we are done. Thus, assume that v0 , vg. Then, since T can win, there is some v1 2 V such that (v0; v1) 2 Ea for some a 2 and for all such v1 it holds that:
learner SLG UE. Before we go into the details, note that if Learner can win the game, he can do so in a finite number of rounds.
Theorem 9: Consider the SLG hV; E; v0; vgi with (V; E) a directed labelled multi-graph and v; vg vertices in it. If Learner has a winning strategy in the corresponding SLGUE, then he has a winning strategy in the corresponding SLG UE.
Proof: This can be shown by induction on the number of rounds. The idea is that in each round L “pretends” that T has removed some edge and then makes the move given by his strategy for SLGUE.
If L can win a SLG UE, then it is easy to see that he can also win the corresponding SLGUE by using his w.s. from SLG UE.
Corollary 1: Consider the tuple hV; E; v0; vgi with (V; E) a directed labelled multi-graph and v; vg vertices in it. Learner has a winning strategy in the corresponding SLG UE i he has a winning strategy in the corresponding SLGUE.
2) a) T can win hV; E; v1; vgi, or b) there is some ((v; v0); a) 2 (V V) such that (v; v0) 2 Ea and T can win hV; E0; v1; vgi where
E0 is the result from removing (v; v0) from Ea.
If 2b holds, since Pa2 jE0aj = n, we are done — we can use the inductive hypothesis and conclude that T has a w.s. in which she removes an edge in each round (in particular, she chooses ((v; v0); a) in the first round). This ((v; v0); a) can be chosen in one of the following ways.
The case of a helpful teacher and an unwilling learner If there is some (v; v0) 2 V V such that (v; v0) 2 Ea for is more interesting. One might expect that the additional some a 2 and this edge is not part of any path from possibility of an empty move gives more power to v1 to vg then by Lemma 2, T can remove this edge and Teacher since it allows her to skip a move in cases 2b holds and we are done.
If every edge in (V; E) belongs to some path from v1 to vg, from 1, there are two cases: either there is only one, or there are more than one paths from v1 to vg.
In the first case (only one path) (v0; v1) can be chosen since it cannot be part of the unique path from v1 to vg.
Assume now that there is more than one path from v1 to vg. Let p = (v1; v2; : : : ; vg) be the/a shortest path from v1 to vg. This path cannot contain any loops. Then, from this path take vi such that i is the smallest index for which it holds that from vi there is a path (vi; vi0+1; : : : vg) to vg that is at least as long as the path following p from vi (i.e. (vi; vi+1; : : : ; vg)). Intuitively, when following path p from v1 to vg, vi is the first point at which one can deviate from p in order to take another path to vg (recall that we consider the case where every vertex in the graph is part of some path from v1 to vg). Now it is possible for T to choose ((vi; vi0+1); a) such that (vi; vi0+1) 2 Ea. Let E0 be the resulting set of edges after removing (vi; vi0+1) from Ea. Then we are in the position hV; E0; v1; vgi. Note that because of the way we chose the edge that has been removed, in the new graph it still holds that from v0 there is no path to a vertex from which vg is not reachable (this holds because from vi the goal vg is still reachable).
Then by Lemma 1, T can win hV; E0; v1; vgi, which then implies 2b.
Hence, we conclude that 2b has to be the case and thus using the inductive hypothesis, we conclude that T can win the game hV; E; v0; vgi also by removing an edge in every round.
Corollary 2: Consider the tuple hV; E; v0; vgi with (V; E) a directed labelled multi-graph and v0; vg vertices in it.
Teacher has a winning strategy in the corresponding SLG HU, i she has a winning strategy in the corresponding SLGHU.
Theorem 11: Consider the tuple hV; E; v0; vgi with (V; E) a directed labelled multi-graph and v0; vg vertices in it. If Learner and Teacher have a winning strategy in the corresponding SLG HE, then they have a winning strategy in the corresponding SLGHE.
Proof: The proof of Theorem 5 provides the needed strategy.
Corollary 3: Consider the tuple hV; E; v0; vgi with (V; E) a directed labelled multi-graph and v; vg vertices in it. Learner and Teacher have joint winning strategy in the corresponding SLG HE i they have a joint winning strategy in the corresponding SLGHE.
In this section we have shown that in Sabotage Learning Games, allowing Teacher to skip moves, does not change the winning abilities of the players. Using these results, both the complexity and definability results from the previous section also apply to the versions of the game in which Teacher can refrain from making a move.
The perspective on learning that we have adopted is
very general. To give a more refined view, let us go back
to the queries and counterexamples paradigm (see [
:::
::: w010 w020 w030 : : : w0100 w000 w0300 2 : : : Fig. 1. The tree of the teaching game: dotted lines are Learner’s moves, which are determined by his algorithm; solid lines are Teacher’s moves; wi are counterexamples given by Teacher; Ci are conjectures made by Learner; C5 is the correct hypothesis.
There are many game-theoretical issues that arise when viewing the run of the learning algorithm as a game. We can for example consider the epistemic status of the players, introduce imperfect information and analyze payo characteristics. Concerning the payo characteristics and di erent classes of teachers such as (un)helpful teachers, we can define corresponding preference relations or payo s: the helpful teacher may strictly prefer all shortest paths in the game tree, i.e. the paths in which the learner learns the fastest. The unhelpful teacher might strictly prefer all the longest paths in the game tree, i.e. the paths in which the learner learns slowly.
We can also provide a choice for Learner in this game. Firstly, we can allow that at each step the learner can choose from one or more procedures which are part of one algorithm. Secondly, in the beginning Learner can decide with which of the available algorithms he is going to proceed. Moreover, we can consider also another possibility that involves extending the traditional inductive inference paradigm. Usually, learnability of a class is interpreted as the existence of a learner that learns every element from the class independently of the behavior of Teacher — if we introduce the possibility of non-learnability to the game, we can view learning algorithms as winning strategies for an eager learner in the w1 C1
::: w01 w02 w03 : : : C5 w2 C2 C5
C0 w3 C3 C5 : : : w4 C5 learning game. With the possibility of non-learnability, there are also paths in the game tree in which the learner never makes a correct conjecture. In this framework, a helpful teacher would also prefer all (shortest) paths ending in a position in which the learner makes a correct conjecture over all the other paths. An unhelpful teacher then prefers all the paths in which the learner does not learn over those in which he does learn.
We have provided a game theoretical approach to learning that allows us to analyze di erent levels of cooperativeness between Learner and Teacher. We have defined Sabotage Learning Games with three variations, representing di erent didactic scenarios. Then, we have shown how Sabotage Modal Logic can be used to reason about these games and, in particular, we have identified certain formulas of the language with the existence of a winning strategy. We gave complexity results for the decision problems associated with each version of the game. These problems correspond to model checking for the associated formulas and models. Our complexity results support the intuitive claim that the cooperation of agents facilitates learning. We investigated an extension of the Sabotage Learning Games that relaxes the condition of the strict alternation of moves. Our results presented in Section III show that if we allow Teacher to skip a move, the winning abilities of the players do not change with respect to the original versions of the games. In the case of the helpful teacher and unwilling learner, this is quite surprising since it says that if Teacher can force Learner to learn in the game with nonstrict alternation, then even if she is forced to remove edges in each round she can do so without removing edges that are necessary for Learner to eventually reach the goal state.
From the perspective of Formal Learning Theory, several relevant extensions can be done. We have described the learning process as changes in information states, without going further into their epistemic and/or doxastic interpretation. A deeper analysis can give us insights about how the learning process is related to di erent notions of dynamics of information, such as belief revision or dynamic epistemic logic.
Moreover, it can be argued that in some natural
learning scenarios, e.g. language learning, the goal of the
learning process, e.g. a correct grammar, is concealed
from Learner. In our approach we assume that Learner
has at least some markers of the goal state, otherwise
we could not introduce the two possible characteristics
of Learner. The assumption of the absence of any ability
to recognize the goal by Learner, leads to a model in
which the Learner moves randomly. Some approaches
that take into account randomness in Sabotage Games
have already been introduced [
In the introduction we described the concepts of finite
identification and identification in the limit. Our work on
SLGs is closer to the first one, as we understand learning
as the ability to reach an appropriate information state,
without taking into account what will happen after
such a state has been reached. In particular, we are
not concerned with the stability of the resulting belief.
Identification in the limit extends finite identification by
looking beyond reachability in order to describe
“ongoing behaviour”. Fixed-point logics, like the propositional
-calculus [
Fernando R. Vela´zquez-Quesada is supported by Consejo Nacional de Ciencia y Tecnolog´ıa (CONACyT), Me´xico (scholarship # 167693).