# Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners

arXiv: https://arxiv.org/abs/1802.05190 · HTML: https://mlsanity.com/paper/1802.05190/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2018.

## Built on by (most cited first, 16 of 16)

- [Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments](https://mlsanity.com/paper/2102.08492/) (2021)
- [Interactive Teaching Algorithms for Inverse Reinforcement Learning](https://mlsanity.com/paper/1905.11867/) (2019)
- [Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints](https://mlsanity.com/paper/1906.00429/) (2019)
- [Teaching an Active Learner with Contrastive Examples](https://mlsanity.com/paper/2110.14888/) (2021)
- [Fair Clustering Using Antidote Data](https://mlsanity.com/paper/2106.00600/) (2021)
- [Iterative Teaching by Label Synthesis](https://mlsanity.com/paper/2110.14432/) (2021)
- [Curriculum Design for Teaching via Demonstrations: Theory and Applications](https://mlsanity.com/paper/2106.04696/) (2021)
- [Nonparametric Iterative Machine Teaching](https://mlsanity.com/paper/2306.03007/) (2023)
- [Iterative Teaching by Data Hallucination](https://mlsanity.com/paper/2210.17467/) (2022)
- [Iterative Teacher-Aware Learning](https://mlsanity.com/paper/2110.00137/) (2021)
- [Nonparametric Teaching for Multiple Learners](https://mlsanity.com/paper/2311.10318/) (2023)
- [Making a Bird AI Expert Work for You and Me](https://mlsanity.com/paper/2112.02747/) (2021)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [Time-Constrained Learning](https://mlsanity.com/paper/2202.01913/) (2022)
- [Manipulating Predictions over Discrete Inputs in Machine Teaching](https://mlsanity.com/paper/2401.17865/) (2024)

## Abstract (arXiv)

In real-world applications of education, an effective teacher adaptively chooses the next example to teach based on the learner's current state. However, most existing work in algorithmic machine teaching focuses on the batch setting, where adaptivity plays no role. In this paper, we study the case of teaching consistent, version space learners in an interactive setting. At any time step, the teacher provides an example, the learner performs an update, and the teacher observes the learner's new state. We highlight that adaptivity does not speed up the teaching process when considering existing models of version space learners, such as "worst-case" (the learner picks the next hypothesis randomly from the version space) and "preference-based" (the learner picks hypothesis according to some global preference). Inspired by human teaching, we propose a new model where the learner picks hypotheses according to some local preference defined by the current hypothesis. We show that our model exhibits several desirable properties, e.g., adaptivity plays a key role, and the learner's transitions over hypotheses are smooth/interpretable. We develop efficient teaching algorithms and demonstrate our results via simulation and user studies.