# Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2019.

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

- [Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments](https://mlsanity.com/paper/2102.08492/) (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)
- [Nonparametric Teaching for Multiple Learners](https://mlsanity.com/paper/2311.10318/) (2023)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Explanatory machine learning for sequential human teaching](https://mlsanity.com/paper/2205.10250/) (2022)
- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)
- [Optimally Teaching a Linear Behavior Cloning Agent](https://mlsanity.com/paper/2311.15399/) (2023)

## Abstract (arXiv)

Algorithmic machine teaching studies the interaction between a teacher and a learner where the teacher selects labeled examples aiming at teaching a target hypothesis. In a quest to lower teaching complexity and to achieve more natural teacher-learner interactions, several teaching models and complexity measures have been proposed for both the batch settings (e.g., worst-case, recursive, preference-based, and non-clashing models) as well as the sequential settings (e.g., local preference-based model). To better understand the connections between these different batch and sequential models, we develop a novel framework which captures the teaching process via preference functions Sigma. In our framework, each function σ ∈ Sigma induces a teacher-learner pair with teaching complexity as TD(σ). We show that the above-mentioned teaching models are equivalent to specific types/families of preference functions in our framework. This equivalence, in turn, allows us to study the differences between two important teaching models, namely σ functions inducing the strongest batch (i.e., non-clashing) model and σ functions inducing a weak sequential (i.e., local preference-based) model. Finally, we identify preference functions inducing a novel family of sequential models with teaching complexity linear in the VC dimension of the hypothesis class: this is in contrast to the best known complexity result for the batch models which is quadratic in the VC dimension.