This paper introduces a new approach for machine teaching that partly addresses the (unavoidable) mismatch between what the teacher assumes about the learning process of the student and the student’s actual process. We analyze several situations in which such mismatch takes place and weshow that, even in the simple case of a Bayesian
Gaussian learner, the lack of knowledge regarding the student’s learning process significantly deteriorates the performance of machine teaching: while perfect knowledge of the student ensures that the target is learned after a finite number of samples,
lack of knowledge thereof implies that the student will only learn asymptotically (i.e., after an infinite number of samples). We propose interactivity as a means to mitigate the impact of imperfect knowledge and show that, by using interactivity, we are able to attain significantly faster convergence, in the worst case. Finally, we discuss the implications
of our results in single- and multi-student settings.
