=Paper=
{{Paper
|id=Vol-494/paper-23
|storemode=property
|title=Games for Learning: A Sabotage Approach
|pdfUrl=https://ceur-ws.org/Vol-494/famaspaper5.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/GierasimczukKV09
}}
==Games for Learning: A Sabotage Approach==
https://ceur-ws.org/Vol-494/famaspaper5.pdf
Games for Learning
A Sabotage Approach
Nina Gierasimczuk, Lena Kurzen and Fernando R. Velázquez-Quesada
Institute for Logic, Language and Computation
Universiteit van Amsterdam
Email: {N.Gierasimczuk | L.M.Kurzen | F.R.VelazquezQuesada}@uva.nl
Abstract—In formal approaches to inductive learning, the reached. These two properties make our notion of learn-
ability to learn is understood as the ability to single out a cor- ing different from the concept of learning formalized as
rect hypothesis from a range of possibilities. Although most epistemic update in Dynamic Epistemic Logic (see e.g. [2]),
of the existing research focuses on the characteristics of the
learner, in many paradigms the significance of the teacher’s where the word “learning” is often used as a synonym of
abilities and strategies is in fact undeniable. Motivated by “getting to know” and is usually represented as a one-
this observation, in this paper we highlight the interactive step epistemic update. Moreover, in our approach we
nature of learning by proposing a game-theoretical and pay attention to the strategies for teaching, highlighting
logical approach. We consider learning as a sabotage-type the fact that restricted power and knowledge of the
game between Teacher and Learner, and present different
variants based on the level of cooperativeness and the actions learner can be compensated by additional insights and
available to the players. We characterize the existence of a intentions of the teacher.
winning strategy in such games by formulas of Sabotage The paper is structured as follows. Section II intro-
Modal Logic, analyzing also their complexity. Our work duces the framework of learning as Sabotage Games,
constitutes the first step towards a unified game-theoretical shows how sabotage modal logic can express the exis-
and logical approach to formal learning theory.
tence of winning strategies in three different versions of
Sabotage Learning Games and gives complexity results
I. I
for them. Section III analyzes Sabotage Learning Games
The objective of this paper is to investigate how logics in which the players do not need to move in alterna-
for interaction in multi-agent systems can be used to rea- tion. Section IV presents a refined interactive view on
son about strategic abilities and information flow during teaching based on existing learning algorithms. Section
the learning process. Formal learning theory (see e.g. [4]) V concludes.
is concerned with the process of inductive inference: it
formalizes the process of inferring general conclusions II. L S G
from partial, consecutively given information, as in the Our work is motivated by the learning from queries and
case of language learning (inferring grammars from counterexamples model [1]. In that paradigm, the goal of
sentences) and scientific inquiry (drawing general con- Learner is to recognize an initially unknown language L.
clusions from partial experiments). We can think of this In order to do this, he is allowed to ask Teacher two types
general process as a game between two players: Learner of questions: about the membership of a certain string
and Teacher. The game starts with a class of possible to L, and about the equivalence of his conjecture (an-
worlds from which Teacher chooses the actual one, and other language) to L. When answering those questions,
Learner has to find out which one it is. Teacher provides Teacher does not have any freedom — her responses
information about the world in an inductive manner, are restricted by L. However, a negative answer to the
and whenever Learner receives a piece of information, second question is accompanied by a counterexample,
he picks a conjecture from the initial class, indicating which plays the role of a hint for Learner. This is the only
which one he thinks is the case. Several conditions can point of the procedure in which Teacher has a relative
be defined for the success of the learning process: we can freedom of choice, and in fact, the informativeness of
require that Learner arrives at a correct hypothesis (finite the string given as a counterexample influences the
identification), or that the sequence of Learner’s conjec- effectiveness of the learning process. We want to focus
tures converges to a correct hypothesis (identification in on this aspect of learning and show that the “profile” of
the limit) [3]. Teacher is relevant for the learning process. We consider
We give a high-level analysis of the described process. several possible scenarios — we describe games in which
First, we treat learning as a procedure of singling out one Teacher is either helpful or unhelpful, and Learner is
correct hypothesis from a range of possibilities. Second, either eager or unwilling to learn.
we see this procedure not as a one-move choice; instead, Let us consider a very simple “classroom” situation
we allow many steps of update before the conclusion is with one teacher and one learner. From our high-level
TABLE I
C L M Each match is played as follows: the initial position
hE0 , v0 i is given by hE, vi. Round k + 1 from position
hEk , vk i 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+1 i, 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
eliminates the possibility of a a and b
mind change from a to 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 , v g i to another Sabotage Game
which Learner changes his information state, and the SG0 = hV, Ek+1 , vk+1 , v g i, 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, v g i, we will
can be seen as feedback about Learner’s current con- mean edges and vertices of its underlying directed multi-
jecture, 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 re-
vertices 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 off 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 Σ = {a1 , . . . an } 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 ∈ Σ.
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, v g i is given by a directed labelled multi-graph
framework of Sabotage Games [6], [11]. A sabotage game (V, E) and two vertices v, v g ∈ V. Vertex v represents the
is played in a directed multi-graph, with two players, position of Runner and v g represents the goal state.
Runner and Blocker, moving in alternation with Runner Each match is played as follows: the initial position
being the first. Runner moves by making a single transi- hE0 , v0 i is given by hE, vi. Round k + 1 from position
tion from the current vertex; Blocker moves by deleting hEk , vk i with Ek = (Eka1 , . . . , Ekan ), consists of Runner mov-
a single edge from any part of the graph. We begin by ing to some vk+1 such that (vk , vk+1 ) ∈ Ekai for some
defining the structure in which a Sabotage Game takes ai ∈ Σ, and then Blocker removing an edge ((v, v0 ), a j ),
place. where (v, v0 ) ∈ Eka j for some a j ∈ Σ. The new position
Definition 2.1 ([6]): A directed multi-graph is a tuple G = is hEk+1 , vk+1 i, where Ek+1 aj = Eka j \ {(v, v0 )} and Ek+1
ai = Ekai
(V, E) where V is a set of vertices and E : V × V → N is for all i , j. The match ends if a player cannot make
a function indicating the number of edges between any a move or if Runner reaches the goal state, with him
two vertices. winning only in the last case.
The Sabotage Game is defined as follows. What is said in Remark 1 also holds for Labelled Sabo-
Definition 2.2 ([6]): A Sabotage Game SG = hV, E, v, v g i is tage Games.
given by a directed multi-graph (V, E) and two vertices In this definition of the game, it is easy to see that
v, v g ∈ V. Vertex v represents the position of Runner and when Blocker removes an edge from v to v0 , it is irrele-
v g represents the goal state. vant what is the label of the removed edge; what matters
TABLE II
for the existence of a winning strategy is the number of S L G
edges from v to v0 that are left.
Observation 1: Let SGΣ = hV, E, v0 , v g i and SG0Σ =
hV, E0 , v0 , v g i be two Labelled Sabotage Games that differ Game Winning Condition
only in the labels of their edges, that is, SLGUE Learner wins iff he reaches the goal state. Teacher wins
otherwise.
∀(v, v0 ) ∈ V × V : |{Eai | (v, v0 ) ∈ Eai }| = |{E0ai | (v, v0 ) ∈ E0a }|, SLGHU Teacher wins iff Learner reaches the goal state. Learner
wins otherwise.
where | · | stands for cardinality. Then Runner has a
winning strategy in SGΣ iff he has a winning strategy SLGHE Both players win iff Learner reaches the goal state. Both
lose otherwise.
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 ) ∈ Ei
• INPUT: A Sabotage Game SG = hV, E, v0 , v g i. 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 , v g i.
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, v g i with Σ = {a1 , . . . am },
nomially equivalent. define f 0 (SGΣ ) := hV, E, v, v g i, where E(v, v0 ) := |{Eai |
Proof: We show that the problems can be polynomi- (v, v0 ) ∈ Eai }|.
ally reduced to each other. Showing that Runner has a w.s. in SGΣ iff he has one in
First we show that SABOTAGE can be reduced to Σ- f (SGΣ ) isPstraightforward, and can be done by induction
SABOTAGE. Given a Sabotage Game SG = hV, E, v0 , v g i, on n := a∈Σ |Ea |. Both f and f 0 are polynomial.
let m := max{E(u, u0 ) | (u, u0 ) ∈ (V × V)}. Define the
Labelled Sabotage Game f (SG) := hV, E, v0 , v g i where B. Sabotage Learning Games
E := (E1 , . . . , Em ) and each Ei is given by Ei := {(u, u0 ) ∈ Based on the Sabotage Games framework, we define
V × V | E(u, u0 ) ≥ i}. 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 iffPhe has one in f (SG). The proof is by induction on Labelled Sabotage Game played by Learner (L, taking the
n = (v,v0 )∈V×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 = i=m
P
i=1 |Ei |, that is, We distinguish between three different versions, SLGUE,
f (SG) has the same number of edges. SLGHU and SLGHE, differing in the winning conditions
The base case is straightforward since in both games (given in Table II).
Runner has a w.s. iff v0 = v g . For the inductive case, The different winning conditions correspond to differ-
from left to right, suppose Runner has a w.s. in the game ent levels of Teacher’s helpfulness and Learner’s willing-
SG = hV, E, v0 , v g i with n + 1 edges. Then, there is some ness to learn. We can have an unhelpful teacher and an
v1 ∈ 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 , v g i 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
difference 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, [11]. Besides the standard modalities, it also contains
“transition-deleting” modalities for reasoning about a formula of SML that characterizes the existence of a
model change that occurs when a transition is removed. winning strategy, that is, the formula is true in a given
To be more precise, we have formulas of the form ^φ, – Pointed Sabotage Model if and only if the corresponding
expressing that it is possible to delete a pair from the player has a winning strategy in the game represented
accessibility relation such that φ holds in the resulting by the model.
model at the current state. First we look at the game SLGUE (the standard Sabo-
Definition 2.8 (Sabotage Modal Language [11]): Let PROP tage Game of [11]), with Learner trying to reach the goal
be a countable set of propositional letters and let Σ be a state and Teacher trying to prevent him from doing so.
finite set. Formulas of the language of Sabotage Modal Inductively, we define:
Logic are given by
γUE
0 := goal, γUE γUE
n+1 := goal ∨ ^– n .
φ ::= p | ¬φ | φ ∨ φ | ^a φ | ^– aφ
Our following result is a variation of Theorem 7 of
with p ∈WPROP and a ∈ Σ. We write ^φ for a∈Σ ^a φ and
W
[7], rephrased for Labelled Sabotage Games. We provide
– for a∈Σ ^
^φ – a φ. a detailed proof to show how our “labelled” definition
Definition 2.9 ([7]): Given a countable set of proposi- avoids a technical issue present in the original proof.
tional letters PROP and a finite set Σ = {a1 , . . . , an }, a Theorem 3: Learner has a winning strategy in the
Sabotage Model is a tuple M = hW, (Rai )ai ∈Σ , Vali where SLGUE game SGΣ = hV, E0 , v0 , v g i iff M(SGΣ ), v0 |= γUE n ,
for n := a∈Σ |E0a | (the number of edges in (V, E0 )).
P
W is a non-empty set of worlds, each Rai ⊆ W × W is
an accessibility relation and Val : PROP → P(W) is a Proof: The proof is by induction on n.
propositional valuation function. The pair (M, w) with Base case
w ∈ W is called a Pointed Sabotage Model.
(⇒) L having a w.s. in SGΣ implies that v0 = v g . Thus,
For the semantics of SML, we first define the model
M(SGΣ ), v0 |= goal and hence, M(SGΣ ), v0 |= γUE 0
.
that results from removing an edge.
(⇐) M(SGΣ ), v0 |= γUE means that M(SG Σ
), v 0 |= goal.
Definition 2.10: Let M = hW, Ra1 , . . . Ran , Vali be a Sabo- 0
tage Model. The model Ma(v,v i Thus v0 = v g . Hence, L wins SGΣ immediately.
0 ) that results from removing
0
the edge (v, v ) ∈ Rai is defined as Inductive case
(⇒) Suppose that SGΣ has n+1 edges, and assume that
Ma(v,v
i
0 ) := hW, Ra1 , . . . Rai−1 , Rai \ {(v, v )}, Rai+1 , . . . Ran , Vali.
0
L has a w.s. There are two possibilities. (1) v0 is the goal
Definition 2.11: Given a Sabotage Model state; then M(SGΣ ), v0 |= goal and hence M(SGΣ ), v0 |=
M = hW, (Ra )a∈Σ , Vali and a world w ∈ W, atomic γUE
n+1
. (2) v0 is not the goal state. Since L has a w.s.,
propositions, negations, disjunctions and standard there is some v1 ∈ V such that (v0 , v1 ) ∈ E0ai for some
modal formulas are interpreted as usual. For the case of ai ∈ Σ and no matter which pair ((u, u0 ), a j ) ∈ (V × V) × Σ
“transition-deleting” formulas, we have with (u, u0 ) ∈ E0a j T chooses, L has a w.s. in the resulting
game SG0Σ = hV, E1 , v1 , v g i, with E1 = (E0a1 , . . . E0a j−1 , E0a j \
M, w |= ^
– a φ iff ∃ v, v0 ∈ W : (v, v0 ) ∈ Ra & Ma(v,v0 ) , w |= φ,
{u, u0 }, E0a j+1 , . . . E0a|Σ| ). Now, SG0Σ has n edges and thus by
– a φ is defined to be equivalent to ¬^
and – a ¬φ. inductive hypothesis, M(SG0Σ ), v1 |= γUE n . This implies
Theorem 2 ([7]): Combined complexity of model M(SGΣ ), v0 |= ^– γUE n and thus M(SG Σ
), v0 |= γUE n+1
. (⇐)
Σ
checking for SML is PSPACE-complete. M(SG ), v0 |= goal ∨ ^– γUE
n implies that v 0 is the goal
Note that “combined complexity” means that both the state (so L wins immediately) or else there is v1 ac-
formula and the model are taken as input. cessible from v0 such that M(SGΣ ), v1 |= – γUEn , that is,
M(SGΣ )a(v,v i
0) , v 1 |= – γUE
n for any ((v, v 0
), a i ) ∈ (V × V) × Σ.
D. Sabotage Learning Games in Sabotage Modal Logic
By inductive hypothesis, this gives L a w.s. at v1 in a
For any given Sabotage Learning Game SGΣ we game that results from removing any edge from SGΣ ,
can construct a Pointed Sabotage Model M(SGΣ ) in a and hence a w.s. at v0 in the game SGΣ .
straightforward way. They key observation for the left-to-right direction of
Definition 2.12: Let SGΣ = hV, E, v0 , v g i be a Sabotage this proof is that the model that results from removing
Game with E = (Ea )a∈Σ . We define the Pointed Sabotage an edge from M(SGΣ ) is always a model that results
Model (M(SGΣ ), v0 ) over the set of atomic propositions from transforming a Labelled Sabotage Game into a
PROP := {goal} with model. With the original definition of a Sabotage Game,
M(SGΣ ) := hV, E, Vali, this is not the case: after removing an edge between v
and v0 with label k, the resulting model does not need
where Val(goal) := {v g }. to be the image of a multi-graph because the label of
In the light of this construction, SML becomes useful the removed edge does not need to be the biggest of
for reasoning about players’ strategic power in SLGs. them. Another way to look at it is the following: the
For each winning condition in Table II, we can define multiple edges of the original multi-graph can be seen
as implicitly labelled by numbers, and the existence of (proved in [7]) tells us that model checking of SML is
an edge labelled with k implies the existence of edges PSPACE-complete. This gives us PSPACE upper bounds
labelled with 1, . . . , k − 1. This property is not preserved for the complexity of the problems of deciding whether
when Teacher removes an edge with an arbitrary label each winning condition is satisfied in a given game. For
from the model M(SG). two of the winning conditions (SLGUE and SLGHE), we
Consider now the game SLGHU, with Teacher trying can also give tight lower bounds.
to force Learner to reach the goal state. Inductively, For SLGUE – the standard Sabotage Game – PSPACE-
define hardness is shown by reduction from QBF [7].
Theorem 6 ([7]): SLGUE is PSPACE-complete.
γHU
0 := goal, γHU – HU
n+1 := goal ∨ (^> ∧ ^γn ). As mentioned above, for SLGHU we obtain a PSPACE
Now, we can show that this formula corresponds to the upper bound.
existence of a winning strategy for Teacher. Note that in Theorem 7: SLGHU is in PSPACE.
order to win, Teacher has to make sure that Learner does Proof: Follows from Theorem 2 and Theorem 4.
not get stuck before he has reached the goal state. This It remains to be shown whether SLGHU is also
is why we need the conjunct ^> in the formula. PSPACE-hard. Whereas at first sight, SLGHU and SLGUE
Theorem 4: Teacher has a winning strategy in the might seem to be duals of each other, the relationship
SLGUE game SGΣ = hV, E0 , v0 , v g i iff M(SGΣ ), v0 |= γHU
n ,
between them is more complex due to the different
for n := a∈Σ |E0a |.
P nature of the players’ moves (Learner moves locally
Proof: Similar to the proof of Theorem 3. by choosing an accessible state, whereas Teacher moves
globally, manipulating the structure in which Learner
Finally, consider SLGHE, with Teacher and Learner
moves).hus, a reduction from SLGUE to SLGHU is not
winning iff Learner reaches the goal state. The corre-
straightforward. Let us now look at SLGHE. This game
sponding formula is defined as follows
is of a different nature than the two previous ones. It is
γHE
0 := goal, γHE n .
– HE
n+1 := goal ∨ ^^γ cooperative, and a winning strategy is a joint strategy
for both players. Such a strategy does not need to take
Theorem 5: Teacher and Learner have a joint winning
into account all possible moves of the opponent. This
strategy in the SLGHE game SGΣ = hV, E0 , v0 , v g i iff
suggests that this version should be less complex than
M(SGΣ ), v0 |= γHE 0
P
n , for n := a∈Σ |Ea |. SLGUE and SLGHU.
Proof: Note that L and T have a joint w.s. iff there is
The following result shows that at least for the com-
a path from v0 to v g . From left to right this is obvious.
parison of SLGUE and SLGHE, this is indeed the case:
From right to left, if there is such path, then there is also
for an eager learner, learning with a helpful teacher
one without cycles; then, there is a joint w.s. that follows
is easier than learning with an unhelpful one. This
the path and at each step removes the edge that has just
follows from the fact that the winning condition of
been used. The Theorem follows by observing that γHE n SLGHE is satisfied iff the goal vertex is reachable from
expresses the existence of such path.
the initial vertex (note that Learner moves first). Thus,
The previous results are summarized in Table III.
determining whether Teacher and Learner can win
TABLE III SLGHE is equivalent to solving the REACHABILITY
W C SLG SML (st-CONNECTIVITY) problem, which is known to be
nondeterministic logarithmic space (NL)-complete [9].
Theorem 8: SLGHE is NL-complete.
Game Winning Condition in SML Winner
Proof: Polynomial equivalence of SLGHE and
SLGUE γUE
0
:= goal, γUE
n+1
– UE
:= goal ∨ ^γn Learner REACHABILITY follows from the argument given in the
SLGHU γHU := goal, γHU – HU
:= goal ∨ (^> ∧ (^γn )) Teacher proof of Theorem 5.
0 n+1
SLGHE γ0 := goal, γn+1 := goal ∨ ^^γ
HE HE HE
– n Both Table IV summarizes the complexity results for the
different versions of SLG.
E. Complexity of Sabotage Learning Games TABLE IV
C R S L G
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 Game Winning Condition Complexity
easier than with an unhelpful teacher or a unwilling
SLGUE Learner wins iff he reaches the goal PSPACE-
learner. This is indeed reflected in the computational state, Teacher wins otherwise complete.
complexity of deciding in a given game whether the
SLGHU Teacher wins iff Learner reaches the PSPACE
winning condition is satisfied. goal state, Learner wins otherwise.
We have shown that our three winning conditions SLGHE Both players win iff Learner reaches the NL-
(Table III) can be expressed in SML, and Theorem 2 goal state. Both loose otherwise. complete
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 , v g i, if there is a
path from v0 to v g and there is no path from v0 to a state
III. R from where v g 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 v g . 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 v g is still reachable
Definition 3.1: A Sabotage Learning Game without strict from any vertex. L will eventually have to move to v g .
alternation (for Teacher) is a tuple SLG∗ = hV, E, v0 , v g i. Lemma 2: Consider the SLG∗ HU game hV, E, v0 , v g i. If T
Moves of Learner are as in the Sabotage Learning Game has a winning strategy and there is some edge (v, v0 ) ∈ Ea
and, once he has chosen a vertex v1 , Teacher has a for some a ∈ Σ such that no path from v0 to v g 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 , v g i, where E0 is the result of removing (v, v0 )
case the next game is hV, E, v1 , v g i. 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 v g 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∗ iff she has a w.s. in SLG. Theorem 10: If Teacher has a winning strategy in the
Consider the case of an unhelpful teacher and an eager SLG∗ HU hV, E, v0 , v g i, then she also has a winning strat-
learner SLG∗ UE. Before we go into the details, note that egy in which she removes an edge in each round.
if Learner can win the game, he can do so in a finite Proof: The proofP proceeds by induction on the num-
number of rounds. ber of edges n = a∈Σ |Ea |.
Theorem 9: Consider the SLG hV, E, v0 , v g i with (V, E) The base case is straightforward. For the inductive
a directed labelled multi-graph and v, v g vertices in it. case, assume thatPT has a winning strategy in SLG∗ HU
If Learner has a winning strategy in the corresponding hV, E, v0 , v g i with a∈Σ |Ea | = n + 1.
SLGUE, then he has a winning strategy in the corre- Then if v0 = v g , we are done. Thus, assume that v0 ,
sponding SLG∗ UE. v g . Then, since T can win, there is some v1 ∈ V such that
Proof: This can be shown by induction on the num- (v0 , v1 ) ∈ Ea for some a ∈ Σ and for all such v1 it holds
ber of rounds. The idea is that in each round L “pre- that:
tends” that T has removed some edge and then makes 1) There is a path from v1 to v g , and
the move given by his strategy for SLGUE. 2) a) T can win hV, E, v1 , v g i, or
If L can win a SLG∗ UE, then it is easy to see that he b) there is some ((v, v0 ), a) ∈ (V × V) × Σ such that
can also win the corresponding SLGUE by using his w.s. (v, v0 ) ∈ Ea and T can win hV, E0 , v1 , v g i where
from SLG∗ UE. E0 is the result from removing (v, v0 ) from Ea .
Corollary 1: Consider the tuple hV, E, v0 , v g i with (V, E) If 2b holds, since a∈Σ |E0a | = n, we are done — we can
P
a directed labelled multi-graph and v, v g vertices in it. use the inductive hypothesis and conclude that T has
Learner has a winning strategy in the corresponding a w.s. in which she removes an edge in each round (in
SLG∗ UE iff he has a winning strategy in the correspond- particular, she chooses ((v, v0 ), a) in the first round). This
ing SLGUE. ((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 ) ∈ V × V such that (v, v0 ) ∈ Ea for
is more interesting. One might expect that the additional some a ∈ Σ and this edge is not part of any path from
possibility of an empty move gives more power to v1 to v g 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 IV. R :
v g , from 1, there are two cases: either there is only one, The perspective on learning that we have adopted is
or there are more than one paths from v1 to v g . very general. To give a more refined view, let us go back
In the first case (only one path) (v0 , v1 ) can be chosen to the queries and counterexamples paradigm (see [1]). In
since it cannot be part of the unique path from v1 to v g . that approach, Learner is an algorithm that embodies a
Assume now that there is more than one path from v1 winning strategy in the game of learning (the learning
to v g . Let p = (v1 , v2 , . . . , v g ) be the/a shortest path from v1 procedure succeeds on all possible true data). Teacher
to v g . This path cannot contain any loops. Then, from this can significantly influence the learning process by giv-
path take vi such that i is the smallest index for which ing counterexamples, and the time needed for learning
it holds that from vi there is a path (vi , v0i+1 , . . . v g ) to v g depends on her choices. Therefore, the game of teaching
that is at least as long as the path following p from vi (i.e. in such a setting can be formalized in extensive form as
(vi , vi+1 , . . . , v g )). Intuitively, when following path p from presented in Figure 1.
v1 to v g , vi is the first point at which one can deviate
from p in order to take another path to v g (recall that
we consider the case where every vertex in the graph
is part of some path from v1 to v g ). Now it is possible C0
for T to choose ((vi , v0i+1 ), a) such that (vi , v0i+1 ) ∈ Ea . Let ...
E0 be the resulting set of edges after removing (vi , v0i+1 ) w1 w2 w3 w4
from Ea . Then we are in the position hV, E0 , v1 , v g i. Note
that because of the way we chose the edge that has been
C1 C2 C3 C5
removed, in the new graph it still holds that from v0
... ... ...
there is no path to a vertex from which v g is not reachable
(this holds because from vi the goal v g is still reachable). w0 w0 w0 w00 w00 w00 w000 w000 w000
1 2 3 1 2 3 1 2 3
Then by Lemma 1, T can win hV, E0 , v1 , v g i, which then ... ... ...
implies 2b. C5 C5 C5
Hence, we conclude that 2b has to be the case and thus
using the inductive hypothesis, we conclude that T can 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;
win the game hV, E, v0 , v g i also by removing an edge in wi are counterexamples given by Teacher; Ci are conjectures made by
every round. Learner; C5 is the correct hypothesis.
Corollary 2: Consider the tuple hV, E, v0 , v g i with (V, E) There are many game-theoretical issues that arise
a directed labelled multi-graph and v0 , v g vertices in it. when viewing the run of the learning algorithm as
Teacher has a winning strategy in the corresponding a game. We can for example consider the epistemic
SLG∗ HU, iff she has a winning strategy in the corre- status of the players, introduce imperfect information
sponding SLGHU. and analyze payoff characteristics. Concerning the pay-
Finally, let us move to the case of a helpful teacher off characteristics and different classes of teachers such
and an eager learner. as (un)helpful teachers, we can define corresponding
preference relations or payoffs: the helpful teacher may
Theorem 11: Consider the tuple hV, E, v0 , v g i with (V, E)
strictly prefer all shortest paths in the game tree, i.e.
a directed labelled multi-graph and v0 , v g vertices in
the paths in which the learner learns the fastest. The
it. If Learner and Teacher have a winning strategy in
unhelpful teacher might strictly prefer all the longest
the corresponding SLG∗ HE, then they have a winning
paths in the game tree, i.e. the paths in which the learner
strategy in the corresponding SLGHE.
learns slowly.
Proof: The proof of Theorem 5 provides the needed We can also provide a choice for Learner in this game.
strategy. Firstly, we can allow that at each step the learner can
Corollary 3: Consider the tuple hV, E, v0 , v g i with (V, E) choose from one or more procedures which are part
a directed labelled multi-graph and v, v g vertices in it. of one algorithm. Secondly, in the beginning Learner
Learner and Teacher have joint winning strategy in the can decide with which of the available algorithms he
corresponding SLG∗ HE iff they have a joint winning is going to proceed. Moreover, we can consider also an-
strategy in the corresponding SLGHE. other possibility that involves extending the traditional
In this section we have shown that in Sabotage Learn- inductive inference paradigm. Usually, learnability of a
ing Games, allowing Teacher to skip moves, does not class is interpreted as the existence of a learner that
change the winning abilities of the players. Using these learns every element from the class independently of the
results, both the complexity and definability results from behavior of Teacher — if we introduce the possibility of
the previous section also apply to the versions of the non-learnability to the game, we can view learning algo-
game in which Teacher can refrain from making a move. rithms as winning strategies for an eager learner in the
learning game. With the possibility of non-learnability, we can now hypothesize is that the complexity of the
there are also paths in the game tree in which the learner scenario with a random Learner and a helpful Teacher
never makes a correct conjecture. In this framework, is bounded by the worst case scenario, in which Learner
a helpful teacher would also prefer all (shortest) paths avoids the goal as long as possible, i.e. the game SLGHU.
ending in a position in which the learner makes a correct In the introduction we described the concepts of finite
conjecture over all the other paths. An unhelpful teacher identification and identification in the limit. Our work on
then prefers all the paths in which the learner does not SLGs is closer to the first one, as we understand learning
learn over those in which he does learn. as the ability to reach an appropriate information state,
without taking into account what will happen after
V. C such a state has been reached. In particular, we are
We have provided a game theoretical approach to not concerned with the stability of the resulting belief.
learning that allows us to analyze different levels of Identification in the limit extends finite identification by
cooperativeness between Learner and Teacher. We have looking beyond reachability in order to describe “ongo-
defined Sabotage Learning Games with three variations, ing behaviour”. Fixed-point logics, like the propositional
representing different didactic scenarios. Then, we have µ-calculus [10], [5], can provide us with tools to express
shown how Sabotage Modal Logic can be used to reason this notion of learnability. In this case, epistemic and dox-
about these games and, in particular, we have identified astic interpretations of learning would involve notions of
certain formulas of the language with the existence of stable belief and a kind of operational, non-introspective
a winning strategy. We gave complexity results for the knowledge as a result of the process.
decision problems associated with each version of the
game. These problems correspond to model checking R
for the associated formulas and models. Our complexity [1] Dana Angluin. Learning regular sets from queries and counterex-
amples. Information and Computation, 75(2):87–106, 1987.
results support the intuitive claim that the cooperation [2] H. van Ditmarsch, W. van der Hoek, and B. Kooi. Dynamic
of agents facilitates learning. We investigated an exten- Epistemic Logic. Springer Netherlands, 2007.
sion of the Sabotage Learning Games that relaxes the [3] E.M. Gold. Language identification in the limit. Information and
Control, 10:447–474, 1967.
condition of the strict alternation of moves. Our results [4] Sanjay Jain, Daniel Osherson, James S. Royer, and Arun Sharma.
presented in Section III show that if we allow Teacher to Systems that Learn. MIT Press, Chicago, 1999.
skip a move, the winning abilities of the players do not [5] Dexter Kozen. Results on the propositional mu-calculus. Theoret-
ical Computer Science, 27:333–354, 1983.
change with respect to the original versions of the games. [6] Christof Löding and Philipp Rohde. Solving the Sabotage Game
In the case of the helpful teacher and unwilling learner, is PSPACE-hard. In Proceedings of the 28th International Symposium
this is quite surprising since it says that if Teacher on Mathematical Foundations of Computer Science, MFCS ’03, volume
2474 of LNCS, pages 531–540. Springer, 2003.
can force Learner to learn in the game with nonstrict [7] Christof Löding and Philipp Rohde. Solving the Sabotage Game
alternation, then even if she is forced to remove edges is PSPACE-hard. Technical report, Aachener Informatik Berichte,
in each round she can do so without removing edges Rwth Aachen, 2003.
[8] Dominik Klein, Frank G. Radmacher, and Wolfgang Thomas.
that are necessary for Learner to eventually reach the The Complexity of Reachability in Randomized Sabotage Games.
goal state. Proceedings of FSEN 2009, LNCS, 2009.
From the perspective of Formal Learning Theory, [9] Christos M. Papadimitriou. Computational complexity. Addison-
Wesley, MA, 1994.
several relevant extensions can be done. We have de- [10] Dana Scott and J. W. de Bakker. A theory of programs. Unpub-
scribed the learning process as changes in information lished manuscript, IBM, Vienna, 1969.
states, without going further into their epistemic and/or [11] Johan van Benthem. An essay on sabotage and obstruction. In
Mechanizing Mathematical Reasoning, Essays in Honor of Jörg H.
doxastic interpretation. A deeper analysis can give us Siekmann on the Occasion of His 60th Birthday, pages 268–276, 2005.
insights about how the learning process is related to
different notions of dynamics of information, such as A
belief revision or dynamic epistemic logic. The authors would like to thank Jakub Szymanik
Moreover, it can be argued that in some natural learn- and Johan van Benthem for their help and their useful
ing scenarios, e.g. language learning, the goal of the comments on previous versions.
learning process, e.g. a correct grammar, is concealed Fernando R. Velázquez-Quesada is supported by Con-
from Learner. In our approach we assume that Learner sejo Nacional de Ciencia y Tecnologı́a (CONACyT),
has at least some markers of the goal state, otherwise México (scholarship # 167693).
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 [8] and hopefully can be
extended to deal with the aforementioned issue. What