# Optimally Teaching a Linear Behavior Cloning Agent

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 24 references that are in the map.
- First posted on arXiv 26 Nov 2023.

## Builds on (most cited first, 14 of 14)

- [Exploring the Limitations of Behavior Cloning for Autonomous Driving](https://mlsanity.com/paper/1904.08980/) (2019)
- [Recent Advances in Imitation Learning from Observation](https://mlsanity.com/paper/1905.13566/) (2019)
- [Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12909/) (2020)
- [Machine Teaching for Inverse Reinforcement Learning: Algorithms and Applications](https://mlsanity.com/paper/1805.07687/) (2018)
- [Interactive Teaching Algorithms for Inverse Reinforcement Learning](https://mlsanity.com/paper/1905.11867/) (2019)
- [Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks](https://mlsanity.com/paper/2011.10824/) (2020)
- [The Teaching Dimension of Linear Learners](https://mlsanity.com/paper/1512.02181/) (2015)
- [Teaching Inverse Reinforcement Learners via Features and Demonstrations](https://mlsanity.com/paper/1810.08926/) (2018)
- [Machine Teaching for Bayesian Learners in the Exponential Family](https://mlsanity.com/paper/1306.4947/) (2013)
- [Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints](https://mlsanity.com/paper/1906.00429/) (2019)
- [Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models](https://mlsanity.com/paper/1910.10944/) (2019)
- [Teaching an Active Learner with Contrastive Examples](https://mlsanity.com/paper/2110.14888/) (2021)
- [Iterative Teaching by Label Synthesis](https://mlsanity.com/paper/2110.14432/) (2021)
- [Teacher Improves Learning by Selecting a Training Subset](https://mlsanity.com/paper/1802.08946/) (2018)

## Abstract (arXiv)

We study optimal teaching of Linear Behavior Cloning (LBC) learners. In this setup, the teacher can select which states to demonstrate to an LBC learner. The learner maintains a version space of infinite linear hypotheses consistent with the demonstration. The goal of the teacher is to teach a realizable target policy to the learner using minimum number of state demonstrations. This number is known as the Teaching Dimension(TD). We present a teaching algorithm called ``Teach using Iterative Elimination(TIE)" that achieves instance optimal TD. However, we also show that finding optimal teaching set computationally is NP-hard. We further provide an approximation algorithm that guarantees an approximation ratio of log(|A|-1) on the teaching dimension. Finally, we provide experimental results to validate the efficiency and effectiveness of our algorithm.