Teaching Memoryless Randomized Learners Without Feedback* Authors: Frank J. Balbach and Thomas Zeugmann Source: Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, October 2006, Proceedings, (José L. Balcázar, Phil Long and Frank Stephan, Eds.), Lecture Notes in Artificial Intelligence 4264, pp. 93 - 108, Springer 2006. Abstract. The present paper mainly studies the expected teaching time of 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 time is shown to be NP-hard. Third, an algorithm for approximating the optimal teaching time is given. Finally, two heuristics for teaching are studied, i.e., cyclic teachers and greedy teachers. * This work has been supported by the MEXT Grand-in-Aid for Scientific Research on Priority Areas under Grant No. 18049001 ©Copyright 2006, Springer