Teaching Memoryless Randomized Learners
Without Feedback
Frank J. Balbach1 and Thomas Zeugmann?2
1

Institut für Theoretische Informatik, Universität zu Lübeck
Ratzeburger Allee 160, 23538 Lübeck, Germany
balbach@tcs.uni-luebeck.de
2
Division of Computer Science
Hokkaido University, N-14, W-9, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

Abstract. The present paper mainly studies the expected teaching timeof memoryless randomized learners without feedback.
First, a characterization of optimal randomized learners is provided and,based on it, optimal teaching teaching times for certain classes are established. Second, the problem of determining the optimal teaching timeis shown to be NP-hard. Third, an algorithm for approximating the
optimal teaching time is given. Finally, two heuristics for teaching arestudied, i.e., cyclic teachers and greedy teachers.

1

Introduction

Teaching studies scenarios in which a teacher gives examples of a target conceptc, chosen from a prespecified concept class C, to a student or a set of students withthe aim that the student or all students, respectively, eventually hypothesize c.
Classically, the admissible students are deterministic learning algorithms andthe teaching performance is measured with respect to the worst case student.
Several models have been proposed to formalize these ideas mathematically.
In the inductive inference framework, Freivalds et al. [8] and Jain et al. [14]developed a model of learning from good examples. Jackson and Tomkins [13]as well as Goldman and Mathias [11, 18] defined models of teacher/learner pairs
where teachers and learners are constructed explicitly. In all these models, somekind of adversary disturbing the teaching process is necessary to avoid collusion
between the teacher and the learner. Angluin and Kriķis’ [1, 2] model prevents
collusion by giving incompatible hypothesis spaces to teacher and learner.
Further approaches differ from the ones mentioned above by not constructing
the learner but assume a learner or a set of learners is given. In Shinohara
and Miyano’s [20] model the students are all consistent deterministic learningalgorithms and the teacher provides a set of examples for the target concept csuch that c is the only concept in the class that is consistent with these examples.
?

This work has been supported by the MEXT Grand-in-Aid for Scientific Research
on Priority Areas under Grant No. 18049001

2Frank J. Balbach and Thomas Zeugmann

Goldman et al. [12] and Goldman and Kearns [10] also consider a helpful
teacher within the online learning model and investigate how many mistakes aconsistent learner can make in the worst case. This number equals the size of thesmallest sample in Shinohara and Miyano’s [20] model. This number is called
the teaching dimension of the target. Then, the difficulty of teaching a class C
is the maximum of the teaching dimensions taken over all c ∈ C. Because of thissimilarity we will from now on refer to both models as the teaching dimension(TD-)model. The teaching dimension has been studied as a measure for thedifficulty to teach a concept class. However, this measure does not always coincidewith our intuition, since it can be as large as the maximum value possible, i.e.,equal to size of the set of all examples (see, e.g., [4] for an illustrative example).
So, instead of looking at the worst-case, one has also studied the averageteaching dimension (cf., e.g., [3, 4, 15, 16]). Nevertheless, the resulting model still
does not allow to study interesting aspects of teaching such as teaching learners
with limited memory or to investigate the difference to teach learners providing
and not providing feedback, respectively (cf. [5] for a more detailed discussion).
Therefore, in [5] we have introduced a new model for teaching randomized learners. This model is based on the TD-model but the set of deterministic learners is
replaced by a single randomized one. The teacher gives in each round an exampleof the target concept to the randomized learner that in turn builds hypotheses.
Moreover, the memory of the randomized learner may range from memoryless(just the example received can be used) to unlimited (all examples received so
far are available). Additionally, the learner may or may not give feedback byshowing its actual guess to the teacher. The teacher’s goal is to make the learner
to hypothesize the target and to maintain it as quickly as possible. Now, theteaching performance is measured by the expected teaching time (cf. Sect. 2).
In [5] we showed that feedback is provably useful and that varying thelearner’s memory size sensibly influences the expected teaching time. Thus, inthis paper we focus our attention to randomized learners without feedback andlimited memory. If there is no feedback, then the teacher can only present an infinite sequence of examples. Teaching infinite sequences introduces difficulties notpresent in the variant with feedback. As there are uncountably many teachers,
there is no way to represent them all finitely. Also their teaching time cannot, ingeneral, be calculated exactly. Finding optimal teachers in the set of all teachers
also seems hard; it is not even clear that always an optimal one exists.
So, for getting started, we analyze the model of memoryless learners without
feedback and ask occasionally which results generalize to any fixed constantmemory size. First, we derive a characterization of optimal learners thereby
showing that there is always an optimal one (Sect. 3). This enables us to calculate
optimal teaching times for certain classes.
We then look at the computational problem of determining the optimal teaching time. No algorithm is known to solve this problem. We show that it is NPhard, and there is an (inefficient) algorithm to approximate this value (Sect. 4).
Since optimal teachers are hard to find, we study two heuristics for teaching. The
greedy one is sometimes optimal (checkable via the characterization in Sect. 3),

Teaching Memoryless Randomized Learners Without Feedback3

but can be arbitrarily far off the optimum (Sect. 5.2). In contrast, teachers iterating over the same sequence of examples forever can come arbitrarily close to
optimal, but it is hard to determine whether they in fact are optimal (Sect. 5.1).

2

Preliminaries

2.1

Notations

Let X be a finite instance space and X = X × {0, 1} the corresponding set ofexamples. A concept class is a set C ⊆ 2X of concepts c ⊆ X. An example (x, v)
is positive if v = 1 and negative if v = 0. We denote the set of all examples fora concept c by X (c) = {(x, v) v = 1 ⇐⇒ x ∈ c} and the set of all concepts
consistent with an example z by C(z) = {c ∈ C z ∈ X (c)}.
A set Z ⊆ X is a teaching set for a concept c ∈ C with respect
T to a class C iff c
is the only concept in C consistent with all examples in Z, i.e., z∈Z C(z) = {c}.
For any set S, we denote by S ∗ the set of all finite lists of elements from S
and by S ` the set of all lists with length `. By [a, b] we mean {a, a + 1, . . . , b}.
We denote by Mn the concept class of monomials over X = {0, 1}n , that isconjunctions of Boolean literals over n variables. We exclude the empty conceptfrom Mn and can thus identify each monomial with a string from {0, 1, ∗}nand vice versa. The concept classes Sn over X = [1, n] are defined as Sn ={[1, n] \ {x} x ∈ [1, n]} ∪ {[1, n]}.
2.2

The Teaching Model

The teaching process is divided into rounds. In each round the teacher gives thelearner an example of a target concept. The learner chooses a new hypothesis
based on this example and on its current hypothesis.
The Learner. As a minimum requirement we demand that the learner’s hypothesis is consistent with the example received in the last round. But the hypothesis
is chosen at random from all consistent ones.
We define the goal of teaching as making the learner hypothesize the target
and maintain it. Consistency alone cannot ensure this, since there may be several
consistent hypotheses at every time and the learner would oscillate between themrather than maintaining a single one. To avoid this, the learner has to maintainits hypothesis as long as it is consistent to the new examples (conservativeness).
The following algorithm describes the choice of the next hypothesis by thememoryless randomized learner in one round of the teaching process.
Input: Current Hypothesis h ∈ C, example z ∈ X .
Output: Next Hypothesis h0 ∈ C.
1. if z ∈/ X (h) then pick h0 uniformly at random from C(z);2.
else h0 := h;In the following the term “learner” refers to the memoryless randomized learner.
In order to make our results depend on C alone, rather than on an arbitrary
initial hypothesis from C, we stipulate a special initial hypothesis, denoted init.

4Frank J. Balbach and Thomas Zeugmann

We consider every example inconsistent with init and thus init is automaticallyleft after the first example and never reached again.
The definition of the learner contains implicitly a function p : (C ∪ {init}) ×
X × (C ∪ {init}) → [0, 1] with p(h, z, h0 ) specifying the probability of a transition
from hypothesis h to h0 when receiving example z.
The Teacher. A teacher is an algorithm that is given a target concept c∗ inthe beginning and then outputs an example for c∗ in each round. A teacher forc∗ can thus be regarded as a function T : → X (c∗ ).
Definition 1. Let C be a concept class and c∗ ∈ C. Let T :→ X (c∗ ) be ateacher and (ht )t∈N be the series of random variables for the learner’s hypothesis
at round t. The event “teaching success in round t,” denoted by Gt , is defined as
ht−1 6= c∗ ∧ ∀t0 ≥ t : ht0 = c∗ .
hSi
The success probability of T is Pr t≥1 Gt . A teacher is successful iff thesuccess probability
P is 1. For such a teacher we therefore define the teaching timeas ET (c∗ , C) := t≥1 t · Pr[Gt ]. Then the teaching time for the concept c∗ isNNE(c∗ , C) := inf ET (c∗ , C) .
T

Although the teacher cannot observe the hypotheses, it can at least calculate
the probability distribution δ : C ∪ {init} → [0, 1] over all possible hypotheses.
Such a δ contains all knowledge of the teacher about the situation. The probability of being in c∗ , however, is irrelevant for the teacher’s decision. Only the
relations of the probabilities for non-target states are important. Normalizingthese probabilities yields a probability distribution γ : C ∪ {init} \ {c∗ } → [0, 1]
over Cb := C ∪ {init} \ {c∗ }. Following Patek [19] we call γ an information state.
We denote by γ (0) the initial information state, that is γ (0) (init) = 1.
The definition of the learner defines implicitly a state transition function
f : Γ × X → Γ , that is f (γ, z) is the follow-up information state after teachingexample z to a learner in state γ.
It is possible to describe teachers as functions T̃ : Γ → X (c∗ ) where Γ is theset of all information states. Such a teacher T̃ , when applied to the initial state
γ (0) and subsequently to all emerging states, yields a teacher T : → X (c∗ ).
Remark. If we assume that the learner’s hypothesis is observable as feedback
then teachers become functions T : C ∪ {init} → X (c∗ ). In this model variant
with feedback, teachers are finite objects (see Balbach and Zeugmann [5]).
Our teaching model without (with) feedback is a special case of an unobservable (observable) stochastic shortest path problem, (U)SSPP. Stochastic shortest
path problems are more general in that they allow arbitrary transition probabilities and arbitrary costs assigned to each transition. In our teaching models,
the transition probabilities are restricted to p and each example has unit cost.
For more details on SSPPs see e.g., Bertsekas [6].

N

3Existence of Optimal Teachers

The most interesting property of a target concept in our model is its optimalteaching time E(c∗ , C). One way to calculate E(c∗ , C) is to calculate ET (c∗ , C)Teaching Memoryless Randomized Learners Without Feedback

5

for an optimal teacher T . However, as there are uncountably many teachers, it
is not even clear whether an optimal teacher exists at all. In this section we
derive a characterization of optimal teachers which shows that there is always
one. Moreover, it allows us to check whether a given teacher is optimal.
Our result is based on a characterization of optimal “policies” in USSPPs presented by Patek [19] that is applicable to USSPPs satisfying certain assumptions.
As our teaching model is a special case of USSPPs, where “policies” correspondto teachers, we have to show that these assumptions hold in our teaching model.
To state Patek’s [19] characterization and the assumptions under which it
works, it is inevitable to introduce some further technical notation. Moreover,
the optimality criterion is based on information state teachers T̃ : Γ → X (c∗ )rather than sequential teachers T : → X (c∗ ).
Following Patek [19], we consider series (T̃t )t∈N of teachers. Such a series iscalled stationary if all teachers in it are identical. For such a series (T̃t )t∈N , wedenote by Prm (γ, T̃ ) the probability that a learner reaches c∗ within m rounds
when it is started in γ ∈ Γ and is taught by teacher T̃t in round t = 0, 1, . . . .
We also need two so called dynamic programming operators D and DT̃ mapping functions G : Γ → to functions of the same type:X[DT̃ G](γ) = 1 + G(f (γ, T̃ (γ))) ·γ(c) · p(c, T̃ (γ), d) ,NRc,d∈Cb[DG](γ) = min∗

1 + G(f (γ, z)) ·Xγ(c) · p(c, z, d) .

z∈X (c )c,d∈CbThe sum c,d∈Cb γ(c) · p(c, T̃ (γ), d) yields the probability for not reaching c∗ inthe next round after being taught T̃ (γ) in state γ. To get an intuition about
above formulas, it is helpful to think of a value G(γ) as the expected number ofrounds to reach the target when the learner starts in state γ. Then [DT̃ G](γ)
specifies for every initial state γ the expected number of rounds under teacher T̃ ,assuming that for all other states the expectations are given by G.
Given a teacher series (T̃t )t∈N , the expected time to reach the target whenstarting in γ ∈ Γ is denoted by GT̃ (γ). This yields a function GT̃ : Γ → .
The characterization, in terms of the randomized teaching model, now is:
P

R

Theorem 2 ([19]). Let C be a concept class and c∗ ∈ C a target. Assume that(a) There is a stationary series (T̃t )t∈N with lim Pr m (γ, T̃ ) = 1 for all γ ∈ Γ .
m→∞(b) For every series (T̃t )t∈N not satisfying (a), a subsequence of∞[DT̃0 DT̃1 · · · DT̃t 0](γ) t=0 tends to infinity for some γ ∈ Γ .
Then

1. The operator D has a fixed point G, that is DG = G.
2. A teacher T̃ : Γ → X (c∗ ) is optimal (i.e., has minimal teaching time) iff
there is a G : Γ → such that DG = G and DT̃ G = G.

R6Frank J. Balbach and Thomas Zeugmann

Roughly speaking, Theorem 2 says: If (a) there is a teacher successful fromevery initial state and if (b) every non-successful teacher has an infinite teachingtime from at least one initial state, then there is an optimal teacher and its
teaching time G is just the fixed point of the operator D.
We now show that conditions (a) and (b) hold for all classes and targets in
our model. For condition (a) we show that a greedy teacher is always successful.
Definition 3. A teacher T̃ for c∗ ∈ C is called greedy iff for all γ ∈ ΓXT̃ (γ) ∈ argmax
γ(c) · p(c, z, c∗ ) .
bz∈X (c∗ )c∈CNote that replacing γ with δ and Cb with C ∪{init} yields an equivalent definition.
Lemma 4. Let C be a concept class and c∗ ∈ C. Let T be the sequential teacher
for some greedy teacher T̃ . Then T is successful for c∗ .
Proof. We denote by δt : C ∪ {init} → [0, 1] the probabilities of the hypothesesin. In each round t, T picks an example z maximizing
P round t under teacher T∗c∈C∪{init} δt (c) · p(c, z, c ). We lower bound this value.
There is a concept c0 6= c∗ with δt (c0 ) ≥ (1 − δt (c∗ ))/|C|.P
Let z 0 be an example
00∗inconsistent with c . Then p(c , z, c ) ≥ 1/|C| and therefore c δt (c)·p(c, z 0 , c∗ ) ≥2(1 − δt (c∗ ))/|C| . As T maximizes this sum, we have also for z = T (t) that
P
2
∗
∗
∗
∗
c δt (c) · p(c, z, c ) ≥ (1 − δt (c ))/|C| . This sum also equals δt+1 (c ) − δt (c )and therefore2
1 − δt+1 (c∗ ) ≤ (1 − 1/|C| ) · (1 − δt (c∗ )) .
Hence, 1 − δt (c∗ ) → 0 as t → ∞ and the probability δt (c∗ ) tends to one.

tu

We only sketch the technical proof that condition (b) is satisfied too.
Lemma 5. Let C be a concept class and c∗ ∈ C a target. Then (b) holds.
Proof. (Sketch) Let (T̃t )t∈N be a series that does not satisfy condition (a). Then
there is a γ with limm→∞ Pr m (γ, T̃ ) < 1. This means limm→∞ δm (c∗ ) < 1, where(δt )t∈N is the series resulting from application of T̃ to γ. The expected number ofrounds to reach c∗ is infinite in this case. Patek [19] shows that this expectationis also lim inf [DT̃0 · · · DT̃t 0](γ), where 0 : Γ → is the zero function.

Rt→∞Hence the sequence ([DT̃0 DT̃1 · · · DT̃t 0](γ))∞
t=0 tends to infinity.

tuR

Theorem 2 requires us to find a G : Γ → and to define a teacher T̃ : Γ →X (c∗ ). However, most of the states in Γ cannot be reached from the initial state
γ (0) and it seems unnecessary to specify T̃ ’s behavior for the unreachable states
too. As a matter of fact, it suffices to define G and T̃ for the reachable states inΓ denoted by Γ0 = {γ ∈ Γ ∃t ∃z0 , . . . , zt : γ = f (. . . f (f (γ (0) , z0 ), z1 ) . . . , zt )}.
We omit the proof thereof and state the final version of the characterization.
Corollary 6. Let C be a concept class and c∗ ∈ C a target. A teacher T̃ : Γ0 →X (c∗ ) is optimal iff there is a G : Γ0 →such that DG = G and DT̃ G = G,
where D and DT̃ have to be restricted suitably to work on functions G : Γ0 → .

RRTeaching Memoryless Randomized Learners Without Feedback

7

One advantage of using Γ0 instead of Γ is that we have to consider only one
state with γ(init) > 0, namely the initial state γ (0) . For illustration, we apply
Corollary 6 to the class Sn in order to find an optimal teacher for [1, n].

N

Fact 7. Let c∗ = [1, n] ∈ Sn . Then the teacher T :→ X (c∗ ) with T (i) =∗(1 + (i mod n), 1) is an optimal teacher for c with teaching time n(n − 1)/2 + 1.
Proof. The proof proceeds in several steps. First we define a teacher T̃ : Γ0 →X (c∗ ) and a function G : Γ0 → . Then we show that DG = G and DT̃ = Dfrom which we conclude that T̃ is optimal. Finally we show that T̃ , when appliedto γ (0) , generates the same example sequence as T .
For a γ ∈ Γ and i ∈ [1, n] we set as shortcut γi := γ(c) for c = [1, n] \ {i}. A
positive example (x, 1) is inconsistent only with the concept [1, n]\{x}. Teachingi +γx /nfor(x, 1) in a state γ 6= γ (0) results in a state f (γ, (x, 1)) = γ̂ with γ̂i = γ1−γx /nRi 6= x, and γ̂x = 0. For γ = γ (0) we have γ̂i = 1/(n − 1) for all i 6= x and γ̂x = 0.
We define T̃ to be a greedy teacher. If there are several equally “greedy” examples, T̃ picks the one with smallest instance. As every example is inconsistent
with exactly one concept, T̃ greedily picks an example that is inconsistent witha most probable hypothesis.
For defining G, let γ ∈ Γ0 \ {γ (0) } and assume without loss of generality
γ1 ≥ γ2 ≥ · · · ≥ γn . Let F = (n−1)n. Then we define
2G(γ) := F +Xni=1γi · iandG(γ (0) ) := F + 1 .

Next we show DG = G. Let γ ∈ Γ0 \{γ (0) } and recall that γ1 ≥ · · · ≥ γn . We haveto
P show that [DG](γ) = G(γ), in other
P words that 1+min(x,1)∈X G(f (γ, (x, 1)))·
p(c,
(x,
1),
d)
=
G(γ).
Since
c,d p(c, (x, 1), d) = 1 − γx /n this meansc,d∈Cb
1 + min G(f (γ, (x, 1))) · (1 − γx /n) = G(γ) .

(1)(x,1)∈X

Let z = (x, 1) ∈ X and γ̂ = f (γ, z). Then γ̂1 ≥ · · · ≥ γ̂z−1 ≥ γ̂z+1 ≥ · · · ≥ γ̂n ≥γ̂z = 0. The expression to be minimized is




X
X
γx 
γx 
1−
· G(γ̂) = 1 −· F+iγ̂i +(i − 1)γ̂i
n
n
i≤x−1
i≥x+1




X
X
γx
γi +γx /nγi +γx /n· F+
i · 1−γx /n +(i − 1) 1−γx /n
= 1−
n
i≤x−1
i≥x+1

n
X
X 
iγi − x · γx +
=F +
γi .
(∗)
i=1

i≥x+1

P

P
From γ1 ≥ · · · ≥ γn , it follows 1γ1 + i≥2 γi ≥ 2γ2 + i≥3 γi ≥ · · · ≥ nγn . Thismeans that the expression (∗) is minimal for x = 1, or
x = γ1 . Setting x = 1Pγnyields min(x,1) G(f (γ, (x, 1))) · (1 − γx /n) = F − 1 + i=1 iγi = G(γ) − 1 andthus Equation (1) is satisfied.

8Frank J. Balbach and Thomas Zeugmann

It remains to show [DG](γ (0) ) = G(γ (0) ). For all examples
1) ∈ X we have (x,Pn−1 1/n 
1
1
(0)
(0)
[DG](γ ) = 1 + (1 − n )G(f (γ , (x, 1))) = 1 + (1 − n ) · F + i=1 i 1−1/n =n(n−1)
1= 1 + n(n−1)
1 + n−1= F + 1 = G(γ (0) ).
n · F + n−1 ·2
2
It follows that [DG](γ) = G(γ) for all γ ∈ Γ0 . Moreover, teacher T̃ always
picks the example (x, 1) minimizing the term in Equation (1), thus DT̃ G = G
and T̃ is optimal according to Corollary 6.
The teacher T̃ , when started in γ (0) , generates the same sequence of examples
as T . By the definition of T̃ , T̃ (γ (0) ) = (1, 1) and for γ 6= γ (0) with γ1 ≥ · · · ≥ γn(w. l. o. g.) T̃ chooses example (1, 1) and the next information state is γ̂ withγ̂2 ≥ · · · ≥ γ̂n ≥ γ̂1 = 0. Therefore, T̃ chooses (2, 1) next and so on.
tuWith feedback [1, n] ∈ Sn can be taught in expected n rounds: A teacher T
observing the learner’s hypothesis can always choose an inconsistent example.
Under T , the learner has in each round a probability of 1/n of reaching the target.
But teaching [1, n] ∈ Sn without feedback requires Ω(n2 ) rounds (cf. Fact 7).
As the previous fact also shows, to prove the optimality of a sequential
teacher, we have to take a detour via information state teachers. Thus finding
the “right” information state teacher is the crucial step in applying Corollary 6.

4

Finding Optimal Teachers

Now that we know that there is always an optimal teacher, we ask how to find one
effectively. But as these teachers are infinite sequences of examples, it is unclear
how an “optimal teacher finding”-algorithm should output one. Alternatively,
we could seek a generic optimal teacher, that is an algorithm receiving a class, atarget c∗ , and a finite example sequence, and outputting an example such thatits repeated application yields an optimal teacher for c∗ .
A closely related task is to determine the teaching time of an optimal teacher,that is E(c∗ , C).
Definition 8. We call the following problem OPT-TEACHING-TIME.
Input: Concept class C, concept c∗ ∈ C, rational number F .
Question: Is E(c∗ , C) ≤ F ?
In the more general setting of USSPPs the analog problem is undecidable (seeMadani et al. [17] and Blondel and Canterini [7]). This can be seen as evidence
for the undecidability of OPT-TEACHING-TIME. On the other hand, USSPPs differ
from our model in some complexity aspects. For example, deciding whether there
is a teacher with at least a given success probability is easy (because there isalways one), whereas the analog problem for USSPPs is undecidable [17, 7].
Although the decidability of OPT-TEACHING-TIME is open, we can at least
show it is NP-hard. So even if there is an algorithm, it is presumably inefficient.
The proof is by reduction from the EXACT-3-COVER (X3C) problem [9]. The
following algorithm computes OPT-TEACHING-TIME instances from X3C instancesin polynomial time (see Fig.1 for an example).

Teaching Memoryless Randomized Learners Without Feedback

B = {1, 2, 3, 4, 5, 6},
A1 = {2, 4, 5},
A2 = {1, 3, 5},
A3 = {1, 3, 6}

x1 x2 x3c∗ 1 1 1
c1 1 0 0
c2 0 1 1
c3 1 0 0
c4 0 1 1
c5 0 0 1
c6 1 1 0−→

9y1 y2 y3 y4 y5 y61 1 1 1 1 1
0 1 1 1 1 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1
1 1 1 1 1 0

Fig. 1. Illustration of the reduction from X3C to OPT-TEACHING-TIME. Every example on
the left is inconsistent with exactly three concepts; y1 , . . . , y6 are “dummy” instances
making all concepts unique. The examples (x1 , 1), (x3 , 1) have the X3C property.

N

Input: Set B = [1, 3n] (n ∈ ), sets A1 , . . . , Am ⊆ B with |Ai | = 3.
1. X := {x1 , . . . , xm } ∪ {y1 , . . . , y3n }2. cj := {xi j ∈/ Ai } ∪ {yi i 6= j} for j = 1, . . . , 3n
3. c∗ := X
4. C := {c∗ , c1 , . . . , c3n }5. Output hC, c∗ , 1 + 32 n(n − 1)i
We call a concept class C output by this algorithm a positive or negative X3Cclass depending on whether the input was a positive or negative X3C instance.
An X3C class is positive iff there are examples z1 , . . .S, zn ∈ X (c∗ ) such thatthe sets C\C(zj ) are pairwise disjoint for j = 1, . . . , n and j (C\C(zj )) = C\{c∗ }.
Examples z1 , . . . , zn satisfying the property
 just stated have the X3C property.
If A1 , . . . , Am consists of all m = 3nsubsets of B we call the class a full3
X3C class. Every full X3C class is a positive X3C class.
Of all X3C classes, the full X3C classes are easiest to analyze because of
their intrinsic symmetries. Moreover, the optimal teachers are just the greedy
teachers, which simplifies the application of our optimality criterion. Note thatfor arbitrary X3C classes a greedy teacher need not to be optimal.
Lemma 9. Let n ≥ 2, let C be a full X3C class for n and c∗ be the concept
containing all instances. Then a teacher T̃ : Γ0 → X (c∗ ) is optimal if and only
if T̃ is greedy. The teaching time, when starting in γ (0) , is 1 + 23 n(n − 1).
Proof. (sketch) The class C is similar to the class S only with three zeros percolumn instead of one. Consequently the proof that all greedy teachers are optimal is similar to that of Fact 7. That the “dummy” examples are never chosen
by an optimal teacher and that all optimal teachers are greedy can be provedby straightforward but technically involved application of Corollary 6.
tu
The next lemma describes the optimal teachers as example sequences rather
than in terms of the information states.
Lemma 10. Let n ≥ 2, let C be a full X3C class for n and c∗ be the concept
containing all instances. A teacher T :→ X (c∗ ) is optimal if and only if
T (t) = zt mod n for all t with the examples z0 , . . . , zn−1 having the X3C property.

N10Frank J. Balbach and Thomas Zeugmann

Proof. This proof is similar to the last paragraph of the proof of Fact 7. We omit
the technical details.
tu
So far, we have characterized the optimal teachers for full X3C classes.
Lemma 11. Let C be an X3C class. Then E(c∗ , C) = 1 + 23 n(n − 1) if and only
if C is a positive X3C class.
Proof. For the if-direction, let z1 , . . . , zn ∈ X (c∗ ) have the X3C property.
The teacher T defined by T (t) = zt mod n has a teaching time of 1+ 32 n(n−1).
This follows similar to Lemma 10. If there was a better teacher, this teacher
would also have a smaller teaching time when applied to the full X3C class, thus
contradicting Lemma 10.
For the only-if direction, assume E(c∗ , C) = 1 + 32 n(n − 1) and suppose that
C is a negative X3C class. Then there is a teacher T for c∗ with teaching time
1 + 32 n(n − 1), but not iterating over a sequence of examples z1 , . . . , zn ∈ X (c∗ )with the X3C property (because negative X3C classes have no such examples).
The teacher T would then have the same teaching time with respect to a full
X3C class, too. Hence, T would be an optimal teacher for the full X3C class, acontradiction to Lemma 10.
tu
Using Lemma 11 we can show our main result.
Theorem 12. The problem OPT-TEACHING-TIME is NP-hard.
Proof. Let hB, A1 , . . . , Am i with B = [1, 3n] be an instance of X3C and let
hC, c∗ , 1 + 23 n(n − 1)i be the instance of OPT-TEACHING-TIME resulting from thepolynomial time reduction on Page 9.
By definition hB, A1 , . . . , Am i is a positive instance of X3C iff C is a positive
X3C class. The latter holds iff E(c∗ , C) = 1 + 32 n(n − 1) (by Lemma 11). This inturn holds iff hC, c∗ , 1+ 23 n(n−1)i is a positive OPT-TEACHING-TIME instance. utThe last theorem implies that no polynomial time generic optimal teacher
exists (unless P = NP).
In our teaching model it is at least possible to effectively approximate E with
arbitrary precision.
Fact 13. There is an algorithm with:
Input: Concept class C, concept c ∈ C, precision ε > 0.
Output: F ∈ with |F − E(c, C)| < ε.

R

Proof. Roughly speaking, the probability for not being in the target state tends
to zero as the sequence of examples given by the teacher grows. The idea of
the algorithm in Fig. 2 is to approximate the expectations for growing finite
sequences of examples until the probability of not being in the target state
becomes negligibly small.
The values Pr[hi = c ∧ hi−1 6= c] can be calculated according to the statetransition function f . Its values are always rational numbers which can be calculated and stored exactly. The value D is an upper bound for the expectedTeaching Memoryless Randomized Learners Without Feedback

11

Input: Concept class C, concept c ∈ C, rational number ε > 0.
1. D := |X| · |C|
2. for ` = 1, 2, . . . :3.
for all α ∈ X (c)` :// denote with hi (i = 1, . . . , `) the random variable for the// hypothesis
the teacher after round i when taught α.
P
4.
b(α) := `i=1 i · Pr[hi = c ∧ hi−1 6= c] + (` + 1) · Pr[h` 6= c]P
5.
B(α) := `i=1 i · Pr[hi = c ∧ hi−1 6= c] + (` + D) · Pr[h` 6= c]
6.
b` := min{b(α) α ∈ X (c)` }7.
if ∃α ∈ X (c)` : B(α) − b` < ε:8.
Output B(α).
Fig. 2. Algorithm computing an approximation of E(c∗ , C).

number of rounds to reach c regardless of the initial state of the learner. Thatmeans that in every state of the learner teaching can be continued such that thetarget is reached in expected at most D rounds.
The values b(α) and B(α) are a lower and an upper bound for the teachingtimeP` of a teacher starting with example sequence α. To verify this note thati=1 i · Pr[hi = c ∧ hi−1 6= c] is the expectation considering the first ` rounds
only. The remaining probability mass P r[h` 6= c] needs at least 1 and at mostD additional rounds, which yields b(α) and B(α), respectively.
It follows that B(α) ≥ E(c, C) for all α ∈ X (c)∗ . Moreover, since every
teacher starts with some example series α ∈ X (c)` , the values b` are all lower
bounds for E(c, C), that is b` ≤ E(c, C) for all ` ≥ 1. Therefore the output B(α)
with B(α) − b` < ε is an ε-approximation for E(c, C).
It remains to show the termination of the algorithm. To this end we show:
Claim. lim`→∞ b` = E(c, C).
Proof. Let δ > 0 and set `0 := (D · E(c, C))/δ. We show that for all ` ≥ `0 ,|E(c, C) − b` | < δ. Let ` ≥ `0 . Then ` ≥ (D · E(c, C))/δ.
Let α ∈ X (c)` such that b(α) = b` . Then b(α) ≤ E(c, C) and therefore(` + 1) · Pr[h` 6= c] ≤ E(c, C). It follows Pr[h` 6= c] ≤ E(c, C)/(` + 1).
For B(α) we haveE(c,C)
B(α) = b(α) + Pr[h` 6= c] · (D − 1) ≤ b(α) + E(c,C)· D.
`+1 · (D − 1) < b(α) +`Using 1/` ≤ δ/(D · E(c, C)), we get B(α) < b(α) + δ.
On the other hand, E(c, C) ≤ B(α) and therefore E(c, C) < b(α) + δ, henceE(c, C) − b` = E(c, C) − b(α) < δ.
 ClaimTo prove the termination of the algorithm we have to show that there is anα such that B(α) − b` < ε. Let T : → X (c) be an optimal teacher and denotehT (0), . . . , T (` − 1)i ∈ X (c)` by T0:` . Then lim`→∞ B(T0:` ) = E(c, C). Together
with lim`→∞ b` = E(c, C) it follows lim`→∞ (B(T0:` ) − b` ) = 0. That means for
sufficiently long α = T0:` , the condition B(T0:` ) − b` < ε is satisfied.
t
u

N

12

5

Frank J. Balbach and Thomas Zeugmann

Heuristics for Teaching

As it seems difficult to find an optimal teacher, next we study teaching heuristics.
5.1

Cyclic Teachers

Probably the simplest teachers are those that give the same sequence of examples over and over again. Such a cyclic teacher is identified with the sequence(z0 , . . . , zm−1 ) ∈ X m of examples it teaches.
Fact 14. Let C be a concept class and c∗ ∈ C a target concept. A cyclic teacher(z0 , . . . , zm−1 ) is successful iff {z0 , . . . , zm−1 } is a teaching set for c∗ wrt. C.
Not only is success of a cyclic teacher easy to decide, the teaching time isalso efficiently computable.
Lemma 15. The teaching time of a cyclic teacher can be computed from thesequence of examples that the teacher repeats.
Proof. Let C be a concept class and let c∗ ∈ C. Let T be a cyclic teacher repeating
z0 , . . . , zm−1 . We assume that the examples constitute a teaching set.
Teaching will be successful no matter at which of the examples zi the loop
starts. We denote by Fi (0 ≤ i < m) the teaching time for the teacher Ti : T (t) =z(i+t) mod m starting with example zi . For h ∈ C we denote by Fi (h) the teachingtime for teacher Ti when the learner’s initial hypothesis is h. For conveniencethroughout this proof all subscripts of T, z, and F are to be taken modulo m.
We can now state a linear equation for Fi involving all Fj with j 6= i. Consider
the teacher Ti and the learner’s state δ after the first example, zi , has been given.
The learner assumes all hypotheses h ∈ C(zi ) with equal probability δ(h) =1/|C(zi )| and all other hypotheses with probability δ(h) = 0.
The expectation Fi is one plus the expectation for teacher Ti+1 when thelearner starts in state δ. This expectation equals the weighted sum of the expectations of teacher Ti+1 starting in state h, that isX
Fi = 1 +δ(h) · Fi+1 (h) .
∗h∈C\{c }We now determine Fi+1 (h). Consider a learner in state h 6= c∗ and a teacher
giving zi+1 , zi+2 , . . . . The learner will change its state only when the first exampleinconsistent with h arrives (such an example exists since the zi ’s form a teaching
set for c∗ ). Let zi+k be this example. Beginning with zi+k , teaching proceeds as if
teacher Ti+k had started from the init state. Therefore Fi+1 (h) = (k − 1) + Fi+k .
If we denote for i = 0, . . . , m − 1 and for k = 1, . . . , m,Ci,k = {h ∈ C \ {c∗ }h ∈ C(zi ), h ∈/ C(zi+1 ), . . . , h ∈/ C(zi+k−1 ), h ∈ C(zi+k )},then we get the following linear equation for Fi :Fi = 1 +m
X|Ci,k |k=1

|C(zi )|· ((k − 1) + Fi+k ) .

Teaching Memoryless Randomized Learners Without Feedback

13

In this manner we get m linear equations in the variables F0 , . . . , Fm−1 .
Denoting the solution vector by F we get a linear equation system of the form
(1 − C) · F = U , where 1 is the m × m unit matrix, C is a substochastic matrix
composed of entries of the form |Ci,k |/|C(zi )| and zeros. Thus 1 − C is invertible
and the values F0 , . . . , Fm−1 are uniquely determined by the equation system.
F0 is the sought teaching time.
tu
The algorithm in Fig. 2 computes an α ∈ X ∗ such that every extensionof α yields a teacher ε-close to optimal. In particular, this holds for the cyclic
teacher α. Hence, cyclic teachers can be arbitrarily close to the optimal teacher.
A drawback of cyclic teachers T is that they do not directly yield an information state teacher T̃ . Thus the optimality criterion cannot immediately beapplied. But cyclic teachers can be used to calculate upper bounds on E(c∗ , C).
Fact 16. Let k ≥ 3, n ≥ k. The monomial 1k ∗n−k has a teaching time of at
k+1
n
n+k+2
+22+k ·3n +2n+2 ·3n −2·3n+1 −4n+1 −2(2k −2n+1 +2·3n )kmost −2+2 +7·2 −2.
2·3n −2n+1 +2k
Proof. This teaching time is achieved by the following cyclic teacher T . The
teacher provides alternately positive and negative examples. The positive examples alternate between the two complementary examples 1k 0n−k and 1k 1n−k .
The first k characters of the negative examples iterate through 01k−1 , 101k−2 ,. . . ,1k−1 0, the last n − k characters equal the last n − k characters of the immediately preceding positive example. For example, let k = 3 and n = 5. Thenthe example sequence is (11100, 1), (01100, 0), (11111, 1), (10111, 0), (11100, 1),(11000, 0), (11111, 1), (01111, 0), (11100, 1), (10100, 0), (11111, 1), (11011, 0).
Applying the method of the proof of Lemma 15, the expected teaching timeof this teacher can be calculated. We omit the details.
tu
For comparison, the optimal teaching time for monomials in the scenario withnnnk)−2n+k−1 +2n+1 −3n(see [5]). A tedious analysis would
feedback is (3 −2 )(2 3+2n −2n +2k−1
show that the value given in Fact 16 is at most twice as high. Thus, teachingmonomials without feedback takes at most twice as long as with feedback.
Corollary 17. The following problem OPT-CYCLIC-TEACHING-TIME is NP-hard.
Input: Concept class C, concept c∗ ∈ C, rational number F .
Question: Is there a cyclic teacher with teaching time at most F ?
5.2

Greedy Teachers

We know from Lemma 4 that a greedy teacher is always successful. Moreover,in contrast to cyclic teachers, they allow a direct application of the optimality
criterion. Thus we were able to prove their optimality in Fact 7. However, they
can be arbitrarily far off the optimal teacher.
Fact 18. For every d > 1 there is a class C and a target c∗ such that for all
greedy teachers T , ET (c∗ , C) > d · E(c∗ , C).

14Frank J. Balbach and Thomas Zeugmann
x1 x2 x3
1 1 1
0 1 1
1 0 1
1 1 0
0 0 1
.. .. ..
. . .
.. .. ..
. . .
.. .. ..
. . .
c3+n 0 0 1

c∗
c1
c2
c3
c4

y1 . . . . . . . . . y n
1 ... ... ... 1
1 ... ... ... 1
1 ... ... ... 1
1 ... ... ... 1
0 1 ... 1 1
1 0 1 ... 1..
..
.
. 1 ..
.
.. ..
..
. 1
. .
1 1 ... 1 0

9
>
>
>
>
>
>
>
>
=

n

>
>
>
>
>
>
>
>
;

Fig. 3. For growing n, the greedy teacher for c∗ becomes arbitrarily worse than the
optimal teacher. See Fact 18. The examples on the right are “dummy” examples.

Proof. Figure 3 shows a family of classes parameterized by n. We sketch themain steps of the proof.
(1) The cyclic teacher ((x1 , 1), (x2 , 1), (x3 , 1)) has a teaching time of (16 +5n)/(4 + n) < 5. Therefore E(c∗ , C) < 5. This can be shown using Lemma 15.
(2) Setting n := 23 (32`−1 − 3) + 1 makes the greedy teacher be a cyclic teacherof the form (((x1 , 1), (x2 , 1))` , (x3 , 1)) or (((x2 , 1), (x1 , 1))` , (x3 , 1)) giving ` times
x1 , x2 before giving x3 . The value ` becomes larger with growing n because,
intuitively, the example x3 becomes less attractive for the greedy teacher.
`

2`+1

`

+9 n)
(3) For given ` the cyclic teacher has −n+9 (16+5n)+4`(1+3
as teaching2(−1+9` )(4+n)
time. The proof is again an application of Lemma 15.
(4) For n as in (2) the greedy learner is cyclic with ` = log(7 + 2n)/ log(9)and according to (3) with a teaching time of(56 + n(33 + 5n)) log(3) + (22 + n(13 + 2n)) log(7 + 2n)(3 + n)(4 + n) log(9)which is not bounded from above and can be larger than 5 by any factor d.

tu

In general there can be more than one greedy teacher for a given class andconcept. It is NP-hard to compute the teaching time of the optimal one.
Corollary 19. The following problem OPT-GREEDY-TEACHING-TIME is NP-hard.
Input: Concept class C, concept c∗ ∈ C, rational number F .
Question: Is there a greedy teacher with teaching time at most F ?
Conclusion. We presented a model for teaching randomized memoryless learners without feedback, characterized optimal learners, and analyzed the expectedteaching time of certain classes. We showed the problem of determining the
optimal teaching time to be NP-hard and studied useful heuristics for teaching.
Acknowledgment. The authors are very grateful to the ALT 2006 PC members
for their many valuable comments.

Teaching Memoryless Randomized Learners Without Feedback

15

References[1] D. Angluin and M. Kriķis. Teachers, learners and black boxes. In Proc. 10th Ann.
Conf. on Comput. Learning Theory, pp. 285–297. ACM Press, New York, 1997.
[2] D. Angluin and M. Kriķis. Learning from different teachers. Machine Learning,
51(2):137–163, 2003.
[3] M. Anthony, G. Brightwell, D. Cohen, and J. Shawe-Taylor. On exact specification
by examples. In Proc. 5th Ann. ACM Works. on Comput. Learning Theory, pp.
311–318. ACM Press, New York, NY, 1992.
[4] F. J. Balbach. Teaching Classes with High Teaching Dimension Using Few Examples. In Learning Theory, 18th Ann. Conf. on Learning Theory, COLT 2005,
Bertinoro, Italy, June 2005, Proc., LNAI 3559, pp. 668–683, Springer, 2005.
[5] F. J. Balbach and T. Zeugmann. Teaching randomized learners. In Learning
Theory, 19th Ann. Conf. on Learning Theory, COLT 2006, Pittsburgh, PA, USA,
June 2006, Proc., LNAI 4005, pp. 229–243, Springer, 2006.
[6] D. P. Bertsekas. Dynamic Programming and Optimal Control. Athena Sci., 2005.
[7] V. D. Blondel and V. Canterini. Undecidable problems for probabilistic automata
of fixed dimension. Theory of Computing Systems, 36(3):231–245, 2003.
[8] R. Freivalds, E. B. Kinber, and R. Wiehagen. On the power of inductive inference
from good examples. Theoret. Comput. Sci., 110(1):131–144, 1993.
[9] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the
Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.
[10] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. of Comput.
Syst. Sci., 50(1):20–31, 1995.
[11] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. of Comput.
Syst. Sci., 52(2):255–267, 1996.
[12] S. A. Goldman, R. L. Rivest, and R. E. Schapire. Learning binary relations andtotal orders. SIAM J. Comput., 22(5):1006–1034, 1993.
[13] J. Jackson and A. Tomkins. A computational model of teaching. In Proc. 5th
Ann. ACM Works. on Comput. Learning Theory, pp. 319–326. ACM Press, 1992.
[14] S. Jain, S. Lange, and J. Nessel. On the learnability of recursively enumerable
languages from good examples. Theoret. Comput. Sci., 261(1):3–29, 2001.
[15] C. Kuhlmann. On Teaching and Learning Intersection-Closed Concept Classes. In
Computat. Learning Theory, 4th European Conf., EuroCOLT ’99, Nordkirchen,
Germany, March 29-31, 1999, Proc., LNAI 1572, pp. 168–182, Springer, 1999.
[16] H. Lee, R.A. Servedio, and A. Wan. DNF Are Teachable in the Average Case. In
Learning Theory, 19th Ann. Conf. on Learning Theory, COLT 2006, Pittsburgh,
PA, USA, June 2006, Proc., LNAI 4005, pp. 214–228, Springer, 2006.
[17] O. Madani, S. Hanks, and A. Condon. On the undecidability of probabilistic planning and infinite-horizon partially observable markov decision problems. In Proc.
16th Nat. Conf. on Artificial Intelligence & 11th Conf. on Innovative Applicationsof Artificial Intelligence, pp. 541–548, AAAI Press/MIT Press, 1999.
[18] H. D. Mathias. A model of interactive teaching. J. of Comput. Syst. Sci., 54(3):487–501, 1997.
[19] S. D. Patek. On partially observed stochastic shortest path problems. In Proc. of
the 40-th IEEE Conf. on Decision and Control, pp. 5050–5055, 2001.
[20] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Computing, 8(4):337–348, 1991.