Research map / Learning theory and algorithms / Sample complexity
On the Complexity of Teaching a Family of Linear Behavior Cloning Learners
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies optimal teaching of a family of consistent linear behavior-cloning learners, reduces it to teaching a linear version-space learner, and gives an extreme-ray set-cover algorithm (TIE / Greedy-TIE) with a log(|A|-1) approximation.
Problem
Finding the smallest demonstration dataset that teaches a deterministic target policy to an entire family of consistent linear behavior cloning learners, which is hard when the action space is large.
Approach
Shows teaching the whole consistent linear BC family is equivalent to teaching the linear version-space learner, then characterizes optimal teaching as covering the extreme rays of the primal cone of feature-difference vectors, found via LP-based elimination, followed by a (greedy) set cover over states.
Key results
- On Pick the Right Diamond with n=6, Greedy-TIE finds a teaching set of size 2 versus 5^6-1 states for Teach-All.
- Greedy-TIE gives a log(|A|-1) approximation to the optimal teaching set size; the exact problem is NP-hard for |A|>2.
- On Polygon Tower, TIE recovers the ground-truth minimum demonstration set across all tested n, with empirical running time slope about 4.67 on log-log plot.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Greedy-TIE to select demonstrations covering the extreme rays | Linear BC learner family · Pick the Right Diamond (n = 6) | teaching set size | Helped |
Surprising findings
- Teaching set optimal for a specific biased learner such as SVM may fail to teach the entire consistent family.
Limitations
- Assumes a powerful teacher able to demonstrate on any state in the state space.
- Focuses only on deterministic target policies and consistent linear learners.
- Exact optimality only for |A|<=2; greedy approximation otherwise.
Experimental setup
Datasets: Pick the Right Diamond (synthetic MDP) Visual block programming maze (synthetic MDP) Polygon Tower (synthetic)
Benchmarks: Pick the Right Diamond Visual Block Programming in Maze Polygon Tower
Metrics: teaching set size running time
Baselines: Teach-All Teach-Random
Builds on: version space learner teaching iterative elimination teaching greedy set cover
Closest papers by meaning
- Curriculum Design for Teaching via Demonstrations: Theory and Applications (NeurIPS 2021 · similarity 0.85)
- Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models (NeurIPS 2019 · similarity 0.85)
- The Sample Complexity of Teaching by Reinforcement on Q-Learning (AAAI 2021 · similarity 0.85)
- Teaching with Limited Information on the Learner’s Behaviour (ICML 2020 · similarity 0.85)
- Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning (NeurIPS 2024 · similarity 0.84)
- Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.