On the Complexity of Teaching a Family of Linear Behavior Cloning Learners

S. Bharti, Stephen Wright, A. Singla, Xiaojin Zhu
2/3/2026

Abstract

We study optimal teaching for a family of Behavior Cloning learners that learn using a linear hypothesis class. In this setup, a knowledgeable teacher can demonstrate a dataset of state and action tuples and is required to teach an optimal policy to an entire family of BC learners using the smallest possible dataset. We analyze the linear family and design a novel teaching algorithm called ‘TIE’ that achieves the instance optimal Teaching Dimension for the entire family. However, we show that this problem is NP-hard for action spaces with |A| > 2 and provide an efficient approximation algorithm with a log( |A| − 1) guarantee on the optimal teaching size. We present empirical results to demonstrate the effectiveness of our algorithm in different teaching environments. The code is available at https: //github.com/skbharti/Optimal-Teaching-Linear-BC-Family

DOISemantic Scholar

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{bharti2026complexity,
  title  = {On the Complexity of Teaching a Family of Linear Behavior Cloning Learners},
  author = {S. Bharti and Stephen Wright and A. Singla and Xiaojin Zhu},
  year   = {2026},
  doi    = {10.52202/079017-3302},
  url    = {https://doi.org/10.52202/079017-3302},
  journal = {NEURIPS 2024 2024}
}

Discussion