On the Complexity of Teaching a Family of Linear Behavior Cloning Learners
Authors: Shubham Kumar Bharti
Stephen Wright
Adish Singla
Jerry Zhu
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine Teaching
Behavior Cloning
Reinforcement Learning
Supervised Learning
Primary area: reinforcement_learning
TL;DR: We study optimal teaching complexity of a family of consistent linear behavior cloning learners.

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 $|\mathcal{A}| > 2$ and provide an efficient approximation algorithm with a $\log(|\mathcal{A}| - 1)$ guarantee on the optimal teaching size. We present empirical results to demonstrate the effectiveness of our algorithm and compare it to various baselines in different teaching environments.

On the Complexity of Teaching a Family of Linear Behavior Cloning Learners
Shubham Bharti UW-Madison skbharti@cs. wisc. edu
Stephen Wright UW-Madison swright0cs.
Adish Singla MPI-SWS
wwtpatttsssiiscceeooooeoeoeeee wisc.edu
adishs@mpi-sws.orf
Xiaojin Zhu UW-Madison jerryzhu&cs wisc. edu
Abstract
We study optimal teaching for a family of Behavior Cloning learners that learn using linear hypothesis class. In this setup, knowledgeable teacher demonstrate a dataset of state and action tuples and is required to teach an optimal policy to entire family of BC learners using the smallest possible dataset. We analyze the linear family and design novel teaching algorithm called 'TIE' that achieves the instance optimal Teaching Dimension for the entire family. However, we show that this problem 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 lttps -inear //github. com/ Sasharti/Dppe 1ptmmalllll....mmmmmplmmmmmm.1ma mal- Teaching Linear BBc--BC-FFa BC-Famil,,
1
Motivation
is an important paradigm of learning in Reinforcement Learning solve real-world problems like teaching machines to drive autonomous vehicles [24]25], 25), fly planes (28), perform robotic manipulations [19] etc. These real-world environments have large state space where the ability to generalize using linear or neural hypothesis class becomes essential for effective learning.
Behavior Cloning (BC) 1 30
(RL), that has been applied extensively
BC learner using i.i.d. sample often demands dataset that scales with the horizon length, the complexity of learner's 's hypothesis class and desired error 4 (2). In many scenarios, like teaching to drive cars, expert teacher may know (near)- optimal policy and can leverage this knowledge to construct a small, non-i.idd dataset to teach the target policy the BC learner far more efficiently. This problem is known Machine Teaching and the size smallest teaching set so produced called Teaching Dimension (TD) [6 32..
However, naively teaching optimal policy
Several existing works 20 23 21 have studied optimal teaching in linear settings, primarily targeting individual surrogate learners, such as linear support vector machines (SVM). These surrogate learners often exhibit optimization biases, arguably making it easier teach them individually. Consequently, teaching set for specific learner is often highly tailored to their biases, limiting effectiveness for others. In contrast, in many real-world scenarios, such teaching classroom of students [33] the teacher must teach the entire class students with a single lesson, even though each student may have unique biases. In this work, we focus the task of optimally teaching family of lincar BC learners that satisfy the consistency property, meaning each learner in this family produce a (subset of) hypotheses consistent with a demonstration dataset. We seek to answer the following question:
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

5
2 5
6
x((s)
5
A
52
*1(+)) =
optinal teaching {(01, (x2,5))
Figure I: a) A board in a "Pick the Right Diamond" game. In this example I the target policy says to pick the diamond with the highest edge breaking the tie in favor of the rightmost slot if any. There are a total of 5 1 candidate teaching state and action pairs. We ask what is the minimum set of demonstrations of such boards would allow the teacher to teach the target policy to consistent linear learners, b) Only two carefully chosen demonstrations are sufficient to teach.
What is the smallest dataset required to teach policy to a family of consistent linear BC learners? To demonstrate the effectiveness of optimally teaching the linear BC family with single dataset, we consider the following example.
Example 1 (Pick the Right Diamond). The game is shown Figure Ta There is board with slots where each slot can have one of 4 different types of diamonds or be empty. The game rule says that one must pick the most expensive diamond i.e. one with the highest number of edges, first; and if there are ties one must pick the rightmost one. The game continues until the board is empty. The teacher wants to find a minimal demonstration set to convey this rule to the agent.
There are 5" - 1 number of states with A = [n]. Consider the family of consistent linear BC learners with a rvo-dimensional feature space denoting slot index and the number of edges in the slot. naive teacher would demonstrate target action in all 5" 1 states which grows exponentially with n. However, clever teacher succeeds by just demonstrating two states(refer to Section 4.1 for complete results), thereby significantly saving the teaching cost from O(5") to 2.
Towards our goal of optimal teaching, make the following contributions:
We formulate the problem of optimally teaching a family of linear BC learners and show that this problem is equivalent to teaching the hardest member in the family, i.e., linear version space learner (Lemma
2. We characterize optimal teaching in terms of covering extreme rays of primal and design a novel algorithm called "TIE' to optimally teach the family (Theorem 4
3. However, as shown in Theorem 5 solving this problem is NP-hard and we propose an efficient algorithm with an approximation ratio of log([A) 1) on TD (Theorem 6).
4. Through set experiments on real-world environments, we demonstrate the effectiveness of our TIE algorithm compared to other baselines (Section
2 Problem Formulation
Consider a Markov Decision Process (MDP) M AS, where state space, A finite action space, R S x A -> [0.1] 1] is reward function, P : x A + A(S) is transition function, y is the discount factor and y is the initial state distribution. For simplicity, we assume S is finite, however, our analysis also extends to infinite case under reasonable assumptions. Let A + Idd be a feature function that defines a structured linear policy class. Given a fixed E Rdd it induces set of policies II,,, defined as follows:
Vs S, The (s) A arg max w (5s.)( (e) aed
Consider a linear hypothesis class 76 = Rd and let II Uwenll,, I III E II: II E A be the set of all stochastic and deterministic policies induced by H respectively. The value of policy E IT in MDP M is given by V = Er,p (E 7"r(s1, Furthermore, a class optimal policy n" E the one that maximizes value among policies the linear class, i.e., n² arg ma V

---

2.1 The Learner Family
We consider Behavior Cloning (BC) learner L D - 2 that learns using a linear policy class
H. = RR. On receiving dataset D = (s;, 04) E [n]} S.S. x A. it aims to learn a 'good' policy by imitating the dataset using a supervised learning algorithm [27].
Given dataset D, the learner maintains a set Li(D) of empirical risk minimizing (ERM) hypotheses defined by loss function é: A A R+, i.e.,
(x( - arg min TE
Σ
(s.a)ED
During deployment, the learner first arbitrarily selects uses π to execute all its actions. Correspondingly, it suffers a worst-case value risk of R(D; L) = Vi - min (E( V in the MDP environment. We remark that BC learner is nothing but supervised learner applied RL setting.
LD( and I. and then
Consistent Linear BC Learners: We consider teaching a family of linear BC learners that have the consistency property and denote the family by E. The consistency property is as follows: given any realizable dataset D, i.e., a dataset generated by any policy π E II L always maintains a non-empty subset of hypotheses consistent with D, i.e.,
VI E Det: D
(Usses (ss, (s)))), we have that, Vw E (D), x(s), v(s, (s)) D.
In linear settings, many well-known learners, such as the linear support vector machine(SVM) linear perceptron are consistent learners. We remark that each consistent learner may have their own bias prefer certain consistent hypotheses over others which is directly influenced by their surrogate loss function or update methods [14 (29]. For example, an SVM learner always prefers max-margin hypothesis over other hypotheses.
However, this family also contains arguably the most simplest linear BC learner, one that maintains the entire version space of consistent hypotheses and does not have any bias to prefer one consistent hypothesis over the other. We call it linear version space(LVS) learner.
Linear Version Space (LVS) Learner: An LVS learner maintains the entire version space of hypothesis (DD consistent with input dataset D, i.e.,
V(D) = {w E Rd w (é(s,a) Φ(s, b)) > 0, V(s,a) E D,a # b}. Equivalently, does empirical risk minimization with respect to zero-one loss, i.e., V(D) Co.1 (D). Note that for realizable dataset D, V(D) 2 ( is open polyhedral cone in Rdd
(1)
Remark We introduce the following notation: let weab = (88 a) -Ø(s, b) be the feuture difference vector for preferring action over b in state s, V (D) be the set of all feature difference vectors induced by dataset D. i.e., (DD)
{zead : (s.a) E D, b E A.b b + a}. We define the primal cone of (D) as cone (D)) = (Eee(D) Nant Ay 2 0, + 0}. and its dual as cone" (IT(D) == (w E IRd: (w. 16) > 0, Vub E (D)). Note that the version space is the dual cone of T (D), Le., V(D) cone" (D)D. We refer to Example for illustration.
2.2 The Teacher
In our setup, there is helpful teacher who controls the dataset D S A provided the learner. The teacher knows an optimal deterministic policy गO" : S + A induced by a w" H, i.e. nT" = Tw" and has the following teaching objective:
wants to unambiguously teach the target policy n² to the entire family of consistent linear BC learners E using as few demonstrations possible.
We remark that our framework can handle teaching any deterministic policy in TTa to the learner. But for simplicity, we will consider teaching optimal deterministic policy Λ². Formally, given teaching instance (M, é, π TT", , the optimal teaching problem of the teacher is defined by the following optimization problem:
(Teach-C)
min D
D
DCSXA
s.t.
YL
E
C lears x² uniquuly.
(2)
3

---

V(D)
M(D)
V(27)
(DD)
VID*)
came (2(2)))
Vanh
Vinc
Viss
Vuss
Sho
Vusk
Muez
Vlac
Vear
( (...
Ralbel
10 [5.0)
(a)
(h)
(c)
(d)
Figure 2: A simple illustration on importance of extreme rays. D, D',', D succeed in teaching but D fails depending on if they cover the extreme rays of (D)).
This formulation models classroom teaching setting, where the teacher is required to teach x to
all learners in using a single dataset which is more challenging than teaching individual biased learners studied in prior works [20 23 I8]. The size of the optimal teaching set TD(x"; called the teaching dimension( TD) of the family C.
; C) D
Remark 2. Teaching the entire family C has its drawback; if the teacher knows the learning bias of a specific learner, it may be able to possibly teach them with a smaller dataset. For example, to optimally teach a linear SVM in Rd just requires two examples [20]. However, such individual conner-specifte teaching sets may not even be valid teaching set for other learners in the C like version space learners, hence useless for teaching the entire family. See Figure for an example.
In a finite state setting, a naive teacher could succeed in teaching by demonstrating a full dataset Ds = (ss and prohibitively expensive for large state space environments. A clever teacher who knows ग can utilize the linear feature function of the learner family teach ' them using a much smaller dataset. As shown in Example demonstrating n² on only one state is sufficient for teaching on the entire state space.
S} to the learner. However, teaching on entire state space can be suboptimal
We recall that our problem Saseem@rrees requires the teacher to teach n to all learners in e, which includes large and diverse set of learners. fact, enumerating all consistent learners may not even be practical. To address this issue, our next lemma shows that it is sufficient to focus on teaching the most challenging member of the family, i.e., the linear version space learner. The proof can be found in the Appendix.
Lemma 1. Optimally teaching the family of consistent linear BC learners is equivalent to optimally teaching the linear version space BC learner.
Hence, the teacher can achieve its objective by just focusing on optimally teaching the LVS learner. From now on, we will focus on optimally teaching x² to LVS learner given by the following optimization problem:
(Teach-LVS)
D +
min DCSXA
D
S.L. VW V(D), क E Uw:
(s))
This requires finding a minimal data D" that induces n" uniquely as the version space under D".
Previous works have studied the problem of optimal teaching of version space learners, but have mostly been limited to either a finite hypothesis setting [6] or highly structured hypothesis classes like axis-aligned rectangles [12 16) which very different from our structured linear setting. Before delving into the algorithm, we present an illustrative example in R.?.
Example 2 (An instance of teaching linear version space BC learner R²). Let S = (s,t, A= {a, b, ct, and π (s) a, Vs E S. Consider the full demonstration set D ((s, at, (u, () that induce Te (D) = (weab Deace Vhaa, trace unab Vuact as indicated by dots in Figure 2a The primal cone cone( V (D)) is shown in blue, and the version space VDD) is in green. We note that the primal cone is supported by two extreme rays.
The subset D is not valid/feusible teaching set as its version space V(D*) (shown in green in Figure 2bb wider than VDD and contains some 's that do not induce n² all states, thus violating the feasibility condition in equation 3 On the other hand, both D' and D" induce the

---

53
55
Phoce
55
54
93
olunb
$2
$1
81
(a)
(b)
Figure 3: a.) Optimal teaching set D of (biased) consistent learner like SVM induce larger space of weights w some of which (shown in yellow region) are inconsistent wrt π and so they cannot succeed in teaching LVS learner and the entire family of consistent learners. b.) Optimal teaching example in higher dimension d 2 3 can have large number of extreme rays to be covered using subset of states making it an NP-hard problem
correct version space V(Ds) (as shown in green in Figures and 2d on the learner and succeeds in teaching x' it. Furthermore, D" which consists of teaching on only one state the optimal set. The problem becomes challenging as we move to higher dimensions where we can have a large number of extreme rays as shown Figure 3b
Teaching Algorithm and Analysis
We first describe naive teaching algorithm that frames optimal teaching as infinite set covering problem in the hypothesis space. This approach underscores the challenge addressing our problem using the greedy inconsistent hypothesis elimination algorithm proposed in prior works (16).
3.1 Optimal Teaching an Infinite Set Cover Problem in w Space
We observe that demonstrating iT" on state s induces |.A] feature difference vectors (sr (1)6 b A,b x (s)) in the primal (feature) space and correspondingly version space cone* (V (a)) fw E Rd w T
db > 0, Vob E (s) } in the dual (weight) space of the LVS learner. Each such inequality, w (s)m > O, climinates a halfspace Wab == {w w ((st S 0} C Rd. Therefore, the effect of demonstrating xs.x'(s) is to eliminate the set of weights W. = (nyirr Wab (cone" ( (())) The full demonstration set Ds = Uses [(s, x² (s))) all states eliminates the union Uses W.s such that only the consistent version space (DDs) {w Rd w (s)x O, Vs 8,6 E A, & a} survives.
The optimal teaching problem requires finding the smallest demonstration set that produces (Ds) in the dual space which equivalent covering/eliminating the infinite set of inconsistent weights (C by a smallest finite collection of infinite subsets (Wa)ees. This is an infinite set cover problem in the weight space given as follows:
min TES
[T]
s.t. V(Ds) W.er
At first glance, solving this problem may seem daunting. Certainly, since the inconsistent hypotheses set is uncountably infinite, we cannot keep track of inconsistent weights that have been eliminated so far and perform greedy hypotheses elimination by greedily selecting the state that eliminates the maximal number of inconsistent hypotheses, as proposed by prior works [7].
However, note that (DDs) cone" (Tr (Ds)) has nice polyhedral cone structure that can be utilized further to simplify our problem as we show in the next section.
3.2 Teaching as Finite Set Cover Problem on Extreme Rays Primal cone(V((ss)
To overcome the challenge mentioned above, we characterize the target version space cone V(Ds) ) in terms of extreme rays of primal cone cone(V (D)))) and devise an optimal teaching algorithm based on this insight. Before doing that, introduce some definitions below.
5

---

Definition 1 (Extreme Ray and its Cover). A ray R. induced by vector E R is the set R {cv 0}. Any vector in serves representative of A ray R called an extreme ray of cone S _2 if for any 2, y E K, I y E = y, R. We say that a state E S covers a ray R if 3 # x (s) (sr (w)6 E R. Similarly, T C S is said to cover R 3s E 'I that covers R.
Recall that demonstrating x² on state & induces the feature difference set V Van in the primal space. Collectively teaching x² on entire S induces feature difference set V/ (Ds) in primal and correspondingly version space cone" (V((s) in the dual space. By definition, x if and only if w E cone" (ovee"(V(()) induce the version space cone" (Ds)) in the dual space of the learner. This is equivalent covering all the extreme rays of the primal cone ( (Ds)) as shown by the next lemma. We defer the proof to the appendix.
R induces Thus, for successful teaching 2 the teacher needs to exactly
Lemma 2 (Necessary and Sufficient Condition for Teaching). A subset T C is valid teaching set if and only if induces a representative vector on each extreme ray of the primal cono cono(V(Ds)
We denote the extreme ray set of primal cone (Ds)) by Mr. Note that demonstrating Ds trivially induces Y however, doing so may not be optimal. Instead, as suggested by the above lemma, it is sufficient find a minimal subset of states that covers all rays V/"
At a high level, our algorithm TIE utilizes this insight to solve the optimal teaching problem in two stages. It first finds the extreme ray set T of primal cone(V(Ds)) Next, it solves set cover problem to find a minimal set of states that covers Vr"
Stage 1: Finding extreme rays of primal cone cone(V (Ds)))): Given of vectors X, we propose an iterative algorithm to find all the extreme rays, i.e., a representative for each extreme rays of the primal cone(X)). The algorithm solves a sequence of linear program LP(xr, X), where each step it tests whether a candidate removes æ from X' and moves the next candidate as shown MinimalExtreme procedure Otherwise, it has to keep x to cover all extreme rays. The proof can be found in the appendix.
X' is a unique representative of an extreme ray of cone( J If not,
Lemma (Extreme Ray Test). Given set of vectors X E Rdd, a candidate a E X is unique representative an extreme ray of primal cone ()), i.e, & cooe(AA) (x+} if and only LP -C,, where, LP(x,X):
min
(w, s.t. (w, x²) 21 Val E
We remark that x is not unique representative if and only if [x. X) 0 and in that case we can safely remove x. Employing this test iteratively on each element of X' produces a unique representative for each extreme ray of primal cone(X'). We apply this process to X' = T/ (Ds) to obtain an extreme ray set V C (Ds) that contains exactly one representative for each extreme ray of cone( V (Ds)).
Stage 2: Finding minimal subset of states that cover the extreme rays V': Once we have the extreme ray set " Lemma 2 requires valid teaching set to cover all the rays in wr To do that optimally using the smallest dataset, the teacher has to solve the following set covering problem on extreme rays space:
minygs [T] s.t. USET V3 = U.
where universe U = V and each state S covers subset of extreme rays V, C Vr Note that, unlike the infinite set cover problem over hypotheses space (3.T), this is a finite set cover problem over extreme ray set. An optimal solution to this subproblem produces the optimal teaching set for teaching LVS learners which, by Lemma] I is also an optimal teaching set for teaching the entire family of consistent linear BC learners.
3.3 Theoretical Results
We provide a complete pseudocode our teaching algorithm 'IE' Algorithm 'TIE' achieves the following guarantec the Teaching Dimension.
Theorem 4 (Optimal Teaching in Finite State Setting). Given an optimal teaching problem instance (M, 0 n" [ our teaching algorithm TIE coorectly finds the optimal teaching set D and achieves the Teaching Dimension T TD(s (D(""" C).

---

Computational Complexity: We note that stage I of 'TIE' is efficiently solvable. However, stage 2 involves solving finite set cover problem where each subset V, can cover as many as |A 1 elements. Note that for |A| 2. each subset is singular, and the set cover problem can be efficiently computed. Hence, 'TIE' efficiently computes the optimal teaching set for instances with |A] s
Algorithm 1 Teach using Iterative Elimination (TIE)
def MinimalFxttrme((2))
1: for each z; E X' do
2: Solve LP(x,,\/(<)) defined by
3: if oy > 0 then
4: A'+ xr
eliminate zj if not necessary > extreme vectors
5: return X'
def OptimalTeach(S, A,, ())
I: let (Ds)) (1) E Rd 8 E +((
D compute feature differences
2: Vr* + MinimalExtreme((VDD
3: for E do
4: V, + v v : E (Ds), (s)
extreme rays covered by DT is smallest cover of all extreme rays b D is the minimum demonstration set
5: (V:: T C S) SetCover( V (V,) lees)
6: teach D = {(t, x (t)) to the agent
However, for |A| > 2, stage requires solving a general set cover problem which is NP-hard to solve. We show that no teacher can avoid this hardness by giving a poly-time reduction from finite set cover problem to our optimal teaching problem. We defer the proof to the appendix.
Theorem (Hardness of Optimal Teaching). Finding an optimal teaching set for teaching a linear version space BC learner is NP-hard in general for instances with action space size |A) 2.
Although the set cover subproblem NP-hard to solve, we can obtain an approximate solution efficiently using greedy covering strategy. Applying this approach to solve our set cover problem in line 5 of Algorithm [ yields an efficient, approximately optimal algorithm, called 'Greedy-TIE" with the following guarantee:
Corollary (Approximately Optimal Teaching). Our algorithm Greedy-TIR Teffeficinl teaches family of consistent linear BC learners, C, and finds an approximately optimal teaching set D such that D < log(IA| - D))
The log(IA) 1) approximation ratio of Greedy-TIE comes from the approximating set cover problem 31 Furthermore, 'Greedy-TIE' runs poly-time ((()))
So far, we have assumed that the state space is finite. This assumption can be relaxed to infinite state setting under mild assumption as stated next. The proof can be found in the appendix.
Corollary (Optimal Teaching for Infinite State Setting). Consider our optimal teaching problem with infinite state space S. Under the assumption that cone( L (Ds)) a closed and convex with finite extreme rays and the teacher knows the extreme rays to slate mupping, our algorithm Greedy-TIEIT correctly finds an approximately optimal teaching set.
In the general case of an infinite state space, the induced version space may contain an (uncountable) infinite number of extreme rays. Consequently, covering this infinite set of extreme rays with finite teaching set becomes impossible, which renders optimal teaching impractical.
Now, turn the issue of distribution shift which has been pertinent issue in behavior cloning in RL (77) For a BC learner imitating teacher's policy n² using a learnt policy क, the error amplification in value given by V V I - Ex-a=' [[]=(s) - π (s))[11).
However, in our teaching setting, this issue resolved as the optimal teacher ensures the learner precisely learns nr" leading to the following corollary.
Corollary (Optimal Value Guarantee). Under teaching by our algorithm TIE, the entire family of linear learners e achieve zero approximate value risk, i.e., VL E C. R(D"; L) = 0.
7

---

buchal kuchitanion
COR MU
x/(og) -6
Toudiing by
(b)
(C)
Figure 4: Optimal teaching in "Pick the right diamond" with n = slots. a) Feature difference vectors (Ds) induced by target policy is shown blue dots, primal cone cone (Ds)) blue area, and dual version space V(Ds) as green area. b) A teaching set produced by Greedy-TIE on board of size 6. c) Comparison our Greedy-TIE algorithm with other baselines.
Furthermore, it can be argued that BC learners are the most natural choice for a learner when supportive teacher is available demonstrate the target behavior. Unlike other learners like inverse RL [ 8 BC operates directly in policy space, eliminating the need for planning. On the downside, since they maintain consistent hypotheses, they are limited to teaching only deterministic policies.
4 Experiments
We evaluate our teaching algorithm Greedy-TIE on three environments: 1) Pick the Right Diamond, 2) Visual Programming Maze with Repeat Loops and 3) Polygon Tower environment (provided in the appendix). Through these experiments, we aim demonstrate the following: a) Our algorithm Greedy-TIF finds an optimal or near-optimal teaching set in all these environments. The optimal teaching dataset so produced is competitive with learner-specffic optimal teaching set and can teach any consistent linear BC learners, and c) Greedy- TIE performs significantly better than competitive baselines like Raach--addom and Teach-All that we define below.
Baselines: We consider two baselines. 1) Teach-All: This teacher simply teacher the target action in all states to the learner, 2) Teach- This teacher draws states uniformly at random (S) and adds collection until the collection becomes a valid teaching set, i.e., it induces the target cone V(Ds). We note that the teaching set produced by prior works [20 23 are specialized to individual learners and do not yield a feasible set for teaching the entire family of consistent lincar learners. Furthermore, their teacher directly constructs covariate vectors (features) in Ed and is not able to choose individual states, thus, not directly applicable to our setting.
4.1 Pick the Right Diamond
Recall the game from Example | board with one of four types diamond or be empty(o). Each action in action space A = [M] represents picking object in one of the cells. The complete description of the MDP environment can be found in the appendix.
A state in S = (0,0, "0"",,,)"///)""""" consists of a n dimensional
Feature representation & optimal policy: The learner uses natural feature function in R² given as follows, ((s, a) [a, #edges diamond at al, where [#edges of diamond at a] is 0 the slot is empty. The optimal policy is to collect the diamonds in order of decreasing value i.e. from large to small number edges. In the case of ties, the learner should choose the rightmost diamond. This policy is feasible under the above featurization, for example, w² [1, 10) uniquely induces n². For board of size n = 6. there are total of 56 states, and their feature difference vectors (Ds) are shown as blue dots in Figure 4al The primal cone cone( V (Ds)) is the blue-shaded area. It contains two extreme rays, both need to be covered for successful teaching. The version space is denoted in green.
Optimal teaching set: We note that any set that covers the two extreme rays is valid teaching set. On a board instance of size 6, our algorithm Greedy-TIE produces teaching set of size two as

---

A Maze Exampie with Solution Code
TeachTElOurs)
Action Space
RachAl
ripoal ES 99123
I: [3.13
NCM
(b)
Figure 5: a) An example of programming task in 5 x 5 with solution code. The maze contains turtle facing one of four directions (shown by green arrow) and a goal cell (shown by a red star). The optimal (smallest) solution code to lead the turtle to the goal is shown the side. The action space consisting of basic code blocks is shown on the right. b) Performance of Greedy-TIF: compared to baselines this domain with different maze sizes.
illustrated in Figure 4b This is instance optimal teaching and shows dramatic improvement over teaching all 56
states. We performed experiments on boards of different sizes and found that
Greedy- significantly outperforms the other two baselines as shown in Figure
4.2 Visual Block Programming in Maze with Repeat Loop
We consider real-world visual programming platform used for teaching kids/learners to write code to complete visual tasks in a maze environment [ teach learners in maze environments of different sizes. The environment state consists of a n x n maze with a turtle (shown in green in Figure 5a facing one of four directions, a goal cell (shown by red star), and (partial) piece of code that can be executed to move the turtle in the maze. The learners' objective is assemble code blocks in sequence write piece of code that can solve the given maze task.
[5]. Further, we choose a domain that aims repeat code blocks to write succinet code complete navigation-based task
The action space A consists of n actions (each representing a basic code block) available to learner write code and is given follows: Turn-Left (TL): turns turtle its left. Turn- Tugn-Right (TR): turns turtle to its right, Mlove-oorwan (MV): moves turtle forward by one cell, Repeat-k Times-Move (R--MV) is complex block with repeat loop that moves the turtle forward by & cells in single command where k E {3,
n 1} The task is to teach the agent to write most succint piece of code that can be executed to make the turtle reach the goal cell. This is captured by a reward function that gives a reward of 1 to the first three code blocks (TL/TR//V) and a reward of -2 to repeat blocks Rg-MV. T The complete description of the MDP defining this problem be found in the appendix.
Feature representation & optimal policy: We consider an execution-guided feature representation[[]] that takes initial board with partial piece of code and constructs fea- ture vector by first executing the partial code to get an intermediate state and extracting features from that state. We orientation and distance of the goal cell from the turtle cell; refer to the appendix for more details. The optimal policy is realizable by linear policy under this representation. The teacher knows o and can construct a dataset D of (state and optimal action) tuples and provide it to the learners. Its goal is to teach the target optimal policy of writing a succinct code to the entire family of learners C.
natural feature representation & S A Rd that encodes the relative
Optimal teaching set: We run our algorithm Greedy-TIE on environments with different sizes of maze and observe that it is able to find an optimal teaching set for each of the environments: refer to Figure for an example on 5 x 5 maze. This optimal teaching set demonstrates each action exactly once on suitable maze state where that action is an optimal one. Our algorithm performs significantly better than the other two baselines:
Ranch- and Teach-All when
maze of
We note that repeats are complex code blocks that have two components and should be used only when they provide advantage, i.e., they substitute more than two basic blocks.

---

repeat D times
upeat tima
whoT
move forward
move forward
Figure 6: Optimal Teaching Set produced by Greedy- TIE on a goal reaching coding task with 5 x maze. The demonstration consists of states with an initial board without any partial code. The optimal action demonstrated to the learner is shown below each state.
We also trained other candidate consistent learners like linear SVM, linear perception, and linear logistic regression on teaching set obtained by Greedy-TIE and verified that all of them achieve risk of zero as claimed by our Theorem
different sizes as shown by Figure 5b
Related Work
Several prior works have studied optimal teaching of version space learners but mostly in finite or countable infinite version space settings 16 17). Some works like [3 have studied teaching multiple
learners simultaneously but in unsupervised learning setting of mean teaching. Instead, we study teaching a family of consistent behavior-cloning learners in a linear hypothesis space setting.
Comparatively, studies on optimal teaching of different linear learners are highly relevant to our work. For example, (20 23 examined teaching linear learners like SVM, perceptron and logistic
regression which can be seen as individual instances of consistent linear BC learners. These works focus on teaching individual learners, where teachers could exploit the strong biases of these learners to teach them relatively easily. On the other hand, we aim to teach the entire family of consistent linear BC learners where the teacher cannot base their teaching on the bias of individual learners. Additionally, [21] delved into the optimal teaching of iterative learners like gradient descent which also biased 29 Further, [8 26 have explored the teaching dimension of kernel learners for teaching linear/non- boundary in I space. Furthermore, these studies typically assume more powerful teacher capable of constructing arbitrary covariate and label pairs, whereas our teacher is restricted selecting states from fixed state space and aims teach the learner generalize to other states using feature covariates induced by the feature function.
Another significant line of research involves beachnng-by-dmoonsee beydeoootttttttoonn in an RL setting. Relevant studies by [8 [0] have focused on teaching linear IRL learners 2 22 which reward based imitation learners that learn primarily in reward space and require planning access to the environment to eventually learn an optimal policy. Unlike them, our linear BC learners learn directly the policy space by only using teaching demonstrations and do not require access the MDP environment.
6 Limitations & Future Work
We studied the optimal teaching of a family of linear BC learners and provided an efficient algorithm that achieves log(1A 1)aaprooxiotioon guarantee the teaching dimension. Our work focused mainly on teaching a deterministic policy to consistent linear family and we hope future works would extend this more complex non-linear learners and stochastic policies.
We assumed the existence of a powerful teacher who could construct dataset using any state in the state space. This may not always be possible in real-world when the states complex and the teacher may actually have to efficiently navigate the MDP environment to lead the students to different states first and then teach them there. Another interesting future direction would be study optimal teaching the family of linear learners under budget constraints on the teacher.
Acknowledgment: Wright was supported in part by NSF grants 2023239 and 2224213 and AFOSR FA9550-21-I 111500221-10008- 1-0084. Zhu was supported part by NSF grants 2202457, 2331669, 1836978, 2023239, ARO MURI W911NF21 10331 17, and AF CoE FA9550- 119550018-1-0000 18-1-0166.
10

---

References
[1] High Performance Outdoor Navigation from Overhead Data using Imitation Learning, pages 262-269. 2009.
[2] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference Machine learning, page 1, 2004.
[3] Stephen Adams, Tyler Cody, and Peter A Beling. A survey of inverse reinforcement learning. Artificial Intelligence Review, 55(6):4307-4346, 2022.
[4] Alekh Agarwal, Nan Jiang, Sham M. Kakade, and Wen Sun. Reinforcement Learning: Theory github.
and Algorithms. 2021. https://r1tthorr/ppt
[5] Umair Ahmed, Maria Christakis, Aleksandr Efremov, Nigel Fernandez, Ahana Ghosh, Abhik Roychoudhury, and Adish Singla. Synthesizing tasks for block-based programming. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 22349-223600 22360. Curran Associates, Inc., 2020.
[6] Martin Anthony, Graham Brightwell, and John Shawe-Taylor. On specifying boolean functions by labelled examples. Discrete Applied Mathematics, 61(1):1-25, 1995.
[7] Michael Bain and Claude Sammut. A framework for behavioural cloning. In Machine Intelli- gence 15, pages 103-129, 1995.
[8] Daniel Š Brown and Scott Niekum. Machine teaching for inverse reinforcement learning: Algorithms and applications. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 7749-7758, 2019.
[9] Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. CoRR, abs/1805.0444 2018.
[10] Maya Cakmak and Manuel Lopes. Algorithmic and human teaching of sequential decision tasks. In Twenty-Sixth AAAI Conference Artificial Intelligence, 2012.
[11] Xinyun Chen, Chang Liu, and Dawn Song. Execution- guided neural program synthesis. In International Conference Learning Representations, 2019.
[12] Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pietro Perona, and Yisong Yue. Understanding the role of adaptivity in machine teaching: The case of version space learners. Advances in Neural Information Processing Systems, 31, 2018.
[13] Felipe Codevilla, Eder Santana, Antonio M. Lopez, and Adrien Gaidon. Exploring the limita- tions of behavior cloning for autonomous driving. Proceedings the Conference on Computer Vision (ICCV), October 2019.
the IEEE/CVF International
[14] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20:273-297, 1995.
[15] Aleksandr Efremov, Ahana Ghosh, and Adish Kumar Singla. Zero-shot learning of hint policy via reinforcement learning and program synthesis. In Educational Data Mining, 2020.
[16] Sally A Goldman and Michael J Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50(1):20-3,, 1995.
[17] Hayato Kobayashi and Ayumi Shinohara. Complexity of teaching by restricted number of examples. 01 2009.
[18] Akash Kumar, Hanqi Zhang, Adish Singla, and Yuxin Chen. The teaching dimension of kernel perceptron. International Conference on Artificial Intelligence and Statistics, pages 2071-2079. PMLR, 2021.

---

[19] Y. Kuniyoshi, M. Inaba, and H. Inoue. Learning by watching: extracting reusable task knowledge from visual observation of human performance. IEEE Transactions on Robotics and Automation, 10(6):799-825 822, 1994.
[20] Ji Liu, Xiaojin Zhu, and Hrag Ohannessian. The teaching dimension of linear learners. In International Conference on Machine Learning, pages 117-126. PMLR, 2016.
[21] Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B. Smith, James M. Rehg, and Le Song. Iterative machine teaching, 2017.
[22] Andrew Y Ng. Stuart Russell, et al. Algorithms for inverse reinforcement learning. In Ieml, volume I, page 2, 2000.
[23] Xuezhou Zhang Hrag Gorune Ohannessian, Ayon Sen, Scott Alfeld, and Xiaojin Zhu. Optimal teaching for online perceptrons. University of Wisconsin-Madison.
[24] Dean A. Pomerleau. Alvinn: An autonomous land vehicle in a neural network. D. Touretzky, editor, Advances in Neural Information Processing Systems, volume 1. Morgan Jorgan-Kaufmamnt 1988.
[25] Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural compulation, 3(1):88-97, 1991.
[26] Hong Qian, Xu-Hui Liu, Chen-Xi Su, Aimin Zhou, and Yang Yu. The teaching dimension of regularized kernel learners. In International Conference on Machine Learning, pages 17984- 18002. PMLR, 2022.
[27] Stephane Ross and Drew Bagnell. Efficient reductions for imitation learning. Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 661-668, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
[28] Claude Sammut, Scott Hurst, Dana Kedzier, and Donald Michie. Learning fly. 02 1992.
[29] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1-57, 2018.
[30] Faraz Torabi, Garrett Warnell, and Peter Stone. Recent advances in imitation learning from observation. CoRR, abs/1905. 13566, 2019.
[31] Valika K. Wan and Khanh Do Ba. Approximating cover, 2005. Accessed: 2023-10-15.
[32] Xiaojin Zhu. Machine teaching: An inverse problem machine learning and approach toward optimal education. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 29, 2015.
[33] Xiaojin Zhu, Ji Liu, and Manuel Lopes. No learner left behind: On the complexity of teaching multiple learners simultaneously. pages 3588-3594, 08 2017.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract clearly reflects the main contribution of studying optimal teaching problem for family of linear BC learners and providing an (approximately) optimal algorithm for teaching the family. Our experiments support highlight the effectiveness of our teaching algorithm over other baselines.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed in last section of the paper.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide complete theorem with assumptions in main paper and proofs in appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe the experimental setup in the paper with additional details provided in appendix. We also provide code to replicate our results in supplementary material.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes]
Justification: We provide code for constructing simulation environment and our algorithms in supplementray material.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the relevant details to reproduce the experimental results provided in appendix and supplementary materials.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For experiments that involved randomness like our algorithm, showed error bars in the plot.
8. Experiments Compute Resources
13

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes)
Justification: We performed our experiments on a Apple Macbook M1 laptop with 16GB and our code can be run any standard machine.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///w.aaaap....pppppppaaaaaa
Answer: [Yes]
Justification: Our algorithm is intended to help learners to speed up learning and we do not envision safety or privacy concerns with our work.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide details about code and how to run it in the readme file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
14

---

7 Appendix
Lemma 9 (Proof of Lemma 1). Optimally teaching the family of consistent linear BC learners is equivalent to optimally teaching the linear version space BC learner.
Proof. Consider any learner & E C. Given consistent dataset D, the learner maintains subset of consistent hypothesis (D( S V(D). We note that since (D(D) S V(D), any teaching set for linear version space(LVS) learner is also valid teaching teaching set of other learners in the family, Hence, it is sufficient to teach the LVS learner. Secondly, since the LVS learner is also a consistent learner, it is necessary teach LVS as well. Hence, teaching LVS is both necessary and sufficient to teach the entire family.
We introduce some definitions before proceeding further. Given a finite set of vectors X' fare [d : E [ni]], we define the primal cone generated by this set as
(x))
Σ BEX
Asti 2 0, ViEX
(4)
Given any set U, we define the dual cone
cone" * (U) == (ylv² > 0, Vo E U, + 0}.
(5)
In particular, if the finite set has x; + O for all E [n]. we have
cone" (x) == t y² x, 0, i = 1, 2,
n
(6)
We prove some basic properties about cones in Rd Proposition 10. For any finite sets U, V s.t. U C V C Rd, we have that,
1. cone" (U) = cone" (cone(U)) (U)).
2. cone* (U) 2 cone* (V).
3. cono(U) cone(V) = cone"(U) cone" (V).
Vi, Z 0, O.E, A,u; + O, (w, ) 0 = w E cone" (cone(U)). For the opposite direction, let A\; 2
Proof. For any w E CUn) (w, u.) > O, Vu, E
O, Σ, A * 0, (w. E, A,uu) > O. For a fixed i, choose A; = and X3. 0, bjj + Then, have (w, u,) > 0, Vu, E U. thus,
cone"(U)
2 Now, for second part of the proposition, let cone" i.e. (x, v) > O, Vo E V. Since, U U.V. this implies (w, us) > 0, Vu, E U. Thus, E cone" (U), thus proving the statement.
Finally, for the third part, we have that (U) cone* (cone(U)) cone" (cone (V)) cone (V), where the first and third equality follows from part of this proposition and second equality follows from the premise.
7.1 Finding extreme rays of primal cone
In the remainder, we assume that the finite set X' = {ax, E Rd ; E [n]} contains all nonzero vectors such that cone* (X') nonempty. Our problem is to find set X C X of minimum cardinality such that cone" (X**) cone" (X)).
Recall that cone (X) (v y x4 0, i E [n]]. We define cone (X') alternatively as follows:
cone cone"(X)) (X)
{az a 0, 2 P(X)}
where P(X) = 11,
15

---

Proof. Any az satisfying 7 clearly has 2'x; > 0 for all E X. E cone" (X) Conversely,
given any y with y" 2y > for all i [n]. we set minke(n] y 2; > 0 and y a to get a and satisfying 7
The key element of the algorithm is L.P of the following form, for some X
min w²
(8)
subject to w w"x, 1 Vi X/(z).
Note that this problem can be written alternatively, using the notation of 7
min w" subject to w (x))(x))
(9)
10
The dual of 8 will also be useful in motivating and understanding the approach:
LP-Dual(a, x/{x))
max ()
Σ X
21EX/(a)
(10)
Σ
Am;=
A 2 for all o4 (2)))
We prove a lemma with several observations.
Lemma 11 (Proof of Lemma 3). For non-empty set X and x E X, we have the following results.
(i) When unbounded, (TPp is infeasible, so x & cone(X (x))) Furthermore, Ew E Rd s.t. w cone" conc"(X(/(z) but w & cone" (X²).
(ii) if 8 has solution, the optimal objective value must be positive.
(iii) When (8) has solution with positive optimal objective, then x E cone(XX(<2))
Furthermore, we can iterate over all candidate elements in X to find a unique representative set X which contains on vector for each supporting halfspace of cone" (X) and equivalently each extreme ray of (x)
Proof.
From LP duality, when 8 is unbounded, then 10 is infeasible, giving the first part of the result. For the second part, we note by the feasibility condition of that the optimal
solution w² E cone" (x/(x)) but since solution unbounded, i.e., w - - 00 < O, we have that, w" & cone" (2)). Such represents supporting halfspace of cone" (A') equivalently an extreme ray of cone(X').
(ii) If (8) were to have a solution with optimal objective O, then by LP duality, the optimal objective of (1O) would also be zero, so the only possible value for À is X for all E x/(xx. The constraint of (TO) then implies that x = 0, which cannot be the case, since we assume that vectors in X are nonzero.
Note that cannot have a solution with a finite negative optimal objective value, because by LP duality, (T0) would also have solution with negative objective value. However, the value of the objective for (10) is non-negative at all feasible points, leading to a contradiction.
(iii) When S has a solution with positive optimal objective, then LP duality implies that (IO) has solution with the same objective, Thus, there are nonnegative Aú Iy (/(z), not all 0, such that the constraint in (10) is satisfied, giving the result.
The above lemma completely characterizes the set of supporting halfspaces that define cone cone" To find all the supporting halfspaces we iterate over all E Y' and remove the ones that are not necessary, ie.. cone" (X (x)) = cone" (X'), and keep the ones that are necessary to preserve cone" (X)), i.e.,
cone" (X Ç cone* (x)).
16

---

By the lemma, the former happens when L xxx)) > 0 while the later happens when LP(x, ('lz,,' [x]) + -o. This iterative procedure outputs a set X whose vectors uniquely rep- resent collection of supporting halfspaces of cone" (2)) in dual space and equivalently collection of extreme rays of cone( in primal space.
Lemma 12. Let U and V be finite sets with U S V S TR and cone" cVne"(V) is non-empty. Then cone(U) cone(V) and cone" (U) cone"(V) if and only U contains at least one vector on each of the extreme rays of cone(V).
Proof. For the sufficiency direction, we note that for a set U CVV if U contains at least one vector on each of the extreme rays of cone(V) then cone(U) = cone(V) (by definition all vectors in a cone can be expressed as a conic combination of all extreme vectors). Furthermore, by Proposition B we have cone* (U) = conc"(V). (V).
For necessary direction, assume that U does not contain a vector x E V that uniquely represents an extreme ray cr cone(V), then by Lemma 11 point (i), cone(U) Ç cone(V) and correspondingly cone' (U) 2 (V).
Lemma 13 (Proof of Lemma 2). A subset T C a valid teaching set if and only if it induces representative vector on each extreme ray of the primal cone y (Ds))
Proof Sketch. Recall that teaching is successful if the teacher can induce non-empty subset of consistent version space V)Ds) on the learner using a subset of states T S S, ie.. 0 & V(Dr) S V(Ds). Since Dr C Ds. we have that (DD) 2 V(Ds) [ Hence, for successful teaching, the teacher has to induce complete V(Ds) on the learner. Using Lemma 12 with V (DDss,, we
observe that teaching is successful, i.e., cone" (T (Dr) = cone" (V((s)) if and only if (D(r) cover each extreme ray of cone( ( (Ds)).
Theorem 14 (Proof of Theorem 4). Given an optimal teaching problem instance (M,6, x 2 our teaching algorithm TIE correctly finds the optimal teaching set D and achieves the Teaching Dimension T ;(T
Proof. Lemma 13 tells us that for valid teaching, the teacher must induce at least one feature difference vector on each of the extreme rays of cone V (Ds)). Since S, A finite, there are only a finite number of extreme rays possible. The iterative elimination procedure in MinimalExtreme in Algorithm| first finds unique representatives for each extreme ray of conc( ( (D))). This follows from lemma 11 Let X be the surviving set of vectors at the start of an iteration where x is considered. We have that
E cone(X (=))) it will get eliminated by the extreme ray test On the other hand, if æ is unique representative for extreme ray in X, we have & cone(X /+=)), and thus will not get climinated. At every iteration, we either eliminate a vector in Vi (Ds) or that vector is a unique representative for an extreme ray of cone V (Ds)) and cannot be climinated. Thus, at the end of the itcrative climination procedure, we recover a set of unique representative vectors V for each extreme ray of cone V (Ds)).
The next step involves finding a smallest subset of states T C S that can cover all the extreme rays. This is done by a set cover problem defined on lines 4-7 of the OptimalTeach procedure in Algorithm [ The set of unique representatives of extreme rays forms the universe to be covered and each state defines a subset of representatives for extreme rays that it can cover. The minimum number of subsets that can cover the entire universe is the minimum number of states that covers the extreme rays giving us T C S an optimal solution for the teaching problem. For instance with |A| = 2, every state can induce at most one extreme ray so picking one state for each extreme ray gives the optimal teaching set.
Theorem 15 (Proof of Theorem 5). Finding an optimal teaching set for teaching linear version space BC learner is NP-hard in general for instances with action space size |A 2.
Proof. We provide poly-time reduction from the set cover problem to the optimally teaching version space BC learner problem 3 Since the set cover is an NP-hard problem, this implies that optimal teaching is NP-hard to solve as well. Let P (U, (Vi)ee))) be an instance of set cover problem
17

---

where U is the universe and (e is collection of subsets of U. We transform P into an instance of optimal teaching problem Q @,
Construction: For each subset V; of P. we create state s; of Q. For each element & in the universe P. we create an extreme ray vector us of feature difference vectors in Q. The complete construction is given follows:
1. S [n]. A = [A] where = maXie[a] [V]] + 1.
2. The target policy is x² (s) = A, E.
3. V {&h (cos( 27r sin( 2mk) 10) & [|U1]).
4. for each S construct feature vectors (Ø(s, A} such that the feature differences map to extreme rays yss. Enumerating over element V := (Var, ka define the induced feature difference vectors as,
ab V.V
vb V
(11)
Ab = ViVS v/V.l AbSA-1
(12)
{82)
V/.
(xc)
Cejk
eloo
Figure 7: An reduction example from a set cover problem to optimal teaching LBC problem
Claim 16. A solution of optimal teaching LBC instance (8,A, RT" () gives a solution the set cover problem (U, (Vilie()) and vice versa.
Finding collection of subsets (Ej) of smallest size that covers all elements in universe U is equivalent to selecting a subset of states S of smallest size that covers all the extreme rays defined by T.
For a solution {Vihee s.t. 7 S [x]] to the set cover instance (U, { (Vijiej)) the set of states indexed by T argument follows from direct translation between two instances. See Figure
solution the optimal teaching instance (S, A, '", 6) and vice versa. The
n
Theorem 17 (Proof Corollary 7). Consider our optimal teaching problem with infinite state space S. Under the assumption that conc V (Ds)) is closed and convex with finite extreme rays and the teacher knows the exireme rays to state mapping, our algorithm Greedy- Freedy-TIIE] correctly finds an approximately optimal leaching set.
Proof. Since the convex cone cone T (Ds)) is closed, we know that extreme rays must be contained in it. Furthermore, an extreme ray must be induced by one the states. The teacher knows the states that induce each extreme ray or a subset of and can construct a set cover problem over a finite extreme ray to solve the optimal teaching problem.
8
More Experimental Results
8.1 Polygon Tower
Let the state space be S m2, the action space be A [n + 1], the feature function be
6: S x A R given by
[0, 0,8)
if n otherwise
0(s, a) =
(13)
[-s 8 cos( 2n0 ) - sin 250 ). ).0]
18

---

(166
(5
ranting EmC
24.0 2A4E
(1.4)
(0
largen (S)
35
30 40.00
largest
20
33
(a)
(b)
(c)
(d)
Figure Polygon Tower. a) All feature difference vectors for = b) Top-down view of the extreme vectors of the primal cone for = 6. c) TIE running time on polygon tower with increasing n. d) The teaching dimension (optimal) vs. the demonstration set size found by TIE. They overlap. In fact, TIE finds the exact correct optimal teaching sets polygon tower.
We note that for a fixed state the feature vectors for actions 1... n lie on a polygon of radius centered around the origin the xy plane.
Target Policy
The teacher wants to teach the target policy лt where Vs E ES, (s) - 1. The policy realizable: for example, w [0, 0, 1] induces this policy. The feature difference vectors induced by πí on S is given as v (Ds) { cos 2 ) sin( 2 ), s]
S.a # n + 1}. These on elevated polygons as shown in Figure 8 a). particular, state s induces
difference vectors s-gon of radius centered at (0, 0, s). Figure (()) shows the top view of the extreme rays of the primal cone cone(V (Ds)) The extreme rays are shown as dots and the states that cover each extreme ray are labeled.
Optimal Teaching The polygon tower problem has an interesting structure that allows us to characterize the minimum demonstration set.
Proposition 18. The optimal teaching set T of the polygon tower consists of all states that are not divisible by any other states in S.
Proof. For any pair of states 8, such that s' > s and s' mod = O, then s' fully covers the induced difference vectors of the characteristic of teaching state is not required if s' is taught. For example, state 6 in Figure (b) covers all the extreme rays induced by states 2, and Conversely, a state is not factor of any other states in S then must be taught because induces the extreme ray [s cos( ), sin( 2m that can only be covered by s.
We TIE with greedy set cover {3, 4,5, 5, 6, 7,8, 12, 16, 20, 24, 22, We verify TIE's solution to the ground truth minimum demon- stration set established in Proposition [8.
family of polygon towers with
We observe that TIE always recovers the correct minimum demonstration set. This can observed from the overlap curve of the optimal size of the teaching set (shown in orange) and the size of the teaching set found by TIE (shown in green) in Figure d).
We also observe that TIE runs quickly. We plot the running time of TIE over instance size in log-log plot in Figure c). For each n, we average the running time over 3 independent trial runs. The straight line of this log-log plot shows that our algorithm indeed runs in polynomial time. The empirical estimate of slope of the linear curve (after omitting the first three outlier points for small n) turns out to be 4.67 implying running time of order O(n²) on this family of instances.
Our algorithm has worst-case running time of order (((())A)) and for [S] [Al in this example, it (
8.2 Pick the Right Diamond
The MDP M = A, R, u.).u) that describes the Block Programming problem is defined as follows:
19

---

Teach-Ti((OUrs) Teach-Al
Teach-TIE(Ours)
10
Teach-All Teach-Random
Teadh-Random
teaching sel: size
teaching sel size
101
grid
Figure 9: Performance of TIE compared to other baselines on visual programming task with local(on the left) and global features(on the right).
1. A state E S is specified by an n size board where the cells are indexed {1, -1. n. Each cell contains one of the four diamonds or be empty leading total of 5 states of non-empty boards.
2. The action space is given as A = (1. (1....... . where each action a represents picking an object at location and removing it from board.
3. The learner receives reward of -1 for picking the rightmost diamond with the largest edge and 22 for all other actions on a non-empty board. Once the board is empty it receives a reward of O. The discount factor is 0.9.
4. The environment transitions deterministically to update the board if the agent picked the right object, i.e., the rightmost object with the largest edge otherwise remains the same. The initial state distribution is uniform on S.
The optimal policy defined by the reward structure above is to pick the diamond in order of decreasing the number of edges. In the case ties, the rightmost diamond should be picked.
8.3 Visual Block Programming in Maze with Repeat Loop
The MDP M = R, that describes the Block Programming problem is defined as follows:
1. A state S is specified by and a turtle orientation E [I, R, U, D} denoting whether the turtle facing left, right, up and down, refer figure 6 for example state. There is also partial code of up constant size giving us a total of 4c(n - n2? states.
n board with turtle cell and goal cell [n:] [n²]
2. The abstract action space is given as A = {TL. TR, MVJ U (R-MVV k {3, ....... n 1}} where TL, TR. MV represent simple code block that when executed allows the turtle to turn left, right and move forward actions respectively and R&-MV represents a complex block of repeat loop that allows the turtle move forward by kesste. In total, we have actions where taking an action means adding the corresponding code block to the partial code the state.
3. The learner receives reward of -1 for using a simple code block action i.e. action a (TL, TR, MV) and -2 for taking complex action RV-MV. The disocunt factor y 0.9.
4. The environment transitions deterministically to update the orientation/possiionn of the agent based on its chosen action. The initial state distribution is uniform on S.
The goal of the teacher is to teach the optimal policy to write succint piece of code which when executed helps to lead the learner the goal cell. The teacher do this by showing smallest size of the (state, action) demonstration dataset.
20

---

Feature Representation for Visual Programming
9.1 Local Feature Representation
This feature representation effectively captures the spatial relationship between the turtle and the goal, as well the impact of different actions.
9.1.1
State and Action description
board: A 2D array representing the game board with cells indicating the agent's orientation (U for up. for down, L for left, R for right).
agent_poss tuple (x, y) represents the agent's current position on the board.
goal_pos: tuple (x, y) representing the goal's position the board.
action: A string representing the specific action taken by the agent (e.g.. 'TL' 'RR' 'MV', 'Ry-MV" etc.).
9.1.2 Feature Vector Construction
1. Relative Quadrant of Goal: Compute the relative quadrant of goal from the agent's orientation.
2. Forward Distance: Compute the distance from the agent to the goal in the direction the agent is facing.
We refer interested readers to the supplementary material for the code.
10 Compute Resources
We ran all our experiments on an Apple MI Pro system with 16GB memory.
21


Reviews:
[{"review_id": "akkPapfcYw", "reviewer": "Reviewer_UxoA", "summary": "The problem being considered is how to provide demonstrations that are useful to a family of consistent behavior cloning (BC) learners, where consistency means that the learner produces a policy consistent with the dataset. The authors study what is the smallest dataset required to teach a family of consistent linear BC learners. The authors characterizes this problem and provides an algorithm called TIE that finds an $\\log(A)$ approximate teaching set. Finally there is a demonstration on a visual programming problem.", "questions": "1. $\\Delta$ is undefined on line 63. \n2. While I'm not very familiar with the literature for optimal teaching via BC, requiring consistent learners to incur zero risk seems rather stringent. It essentially requires $\\pi^\\star$ to lie in the policy class, which is often not the case as the training error is almost never zero in practice. Can this be relaxed to a more realistic (maybe agnostic) setting?\n3. The authors claim that SVM, perceptron and logistic regression are specific instances of this paper's formulation. I wonder if an experiment can compare TIE vs. algorithms specific to SVM, perception, or logistic regression? Since TIE is supposed to be general, how much performance degradation do we see? \n4. I'm a bit confused by Thm 4 and Cor 8. On one hand, Thm 4 claims that TIE achieves teaching dimension. On the other hand, Cor 8 says TIE finds an approximate solution which contradicts Thm 4. Are they referring to two instantiations of TIE? Is TIE referring to the exact exponential-time alg or is TIE referring to the approximation alg?\n\n\nMinor typos:\n1. Extra \"like\" on line 294\n2. mulitple on line 290", "limitations": "No. The checklist says that limitations are discussed in the last section of the paper, but I did not find such a discussion anywhere. Can the authors please discuss their limitations in detail?", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. For the most part, the paper is written in a clear and instructive way. Overall, the paper introduces a new setting (teaching a family of consistent linear learners) and provides a reasonably extensive treatment of the setting, including proving sufficient & necessary conditions for solutions, proving that it is NP-hard, providing an approximation algorithm.", "weaknesses": "1. The empirical baselines that are considered seem rather weak. Teach-All is just brute-force (which as mentioned scales exponentially with n) and Teach-Random is just looking at states randomly. Are there better baselines for this task? Since you could reduce to set cover, can you also try popular approximation algorithms for set cover? In particular, do they directly work for this problem, and if so can you provide empirical / theoretical comparisons to TIE? \n1b. Related to the above, the experimental setting also seems a bit lacking. The problem is of very small scale where the optimal solution of this NP-hard problem can be computed. The paper would be much better motivated if there was an experiment that demonstrated the significance of TIE and the problem formulation being studied.\n2. Cor 8 seems to be the crux of the paper since it's claimed to be a practical alg for this NP-hard problem. However, it is hastily stated and not discussed in detail at all. \n3. The computational complexity of TIE is $(SA)^3$ (line 218) which seems quite unscalable. For example, in the Diamond example, the state space grows exponentially with n, so any poly dependence on $S$ is bad. In other words, while TIE might be able to find a very small dataset for teaching that doesn't grow exponentially with n, it's still prohibitive if TIE itself grows exponentially with n.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and suggestions. Please find our replies to your individual raised concerns below. \n\n### **1. Baselines are rather weak; provide comparison with other baselines for set cover.**\n  We do agree that Teach-ALL is a weak baseline. However we note that Teach-Random is not that weak as it utilizes our crucial insight to cover infinite hypothesis space by just covering finite extreme rays as stated in Lemma 2.  \n\nWe thank you for your suggestion to try other algorithms for the set cover subproblem. To that end, we implemented three other approximation algorithms of set cover: 1. relaxed LP method, 2. randomized rounding method, and 3. primal-dual method. \n\nWe produced the teaching set size result (as in experiment 5.b.) by substituting greedy algorithms with these candidates and found that they performed equally well as greedy. This is not surprising since these algorithms have similar logarithmic approximation guarantees like the greedy algorithm. We recall that they all still use our insight to cover finite extreme rays as given by Lemma 2.\n\n### **2. Clarifying difference between Theorem 4 and Corollary 8.**\n  \nWe apologize for the confusion caused due to the wording of corollary 8. We intended the corollary 8 to be read with preceding statements and would like to clarify the differences below. We will also add this clarification in the updated version of the paper.\n\nFirst, we note that our algorithm TIE has two parts : 1.) finding all extreme rays of the cone and 2.) covering these extreme rays by a minimal set of states. Solving first part is computationally efficient in relevant parameter i.e. $|S|, |A|$ as it involves solving a sequence of linear program, while the second part is a finite set-cover problem which is known to be a NP-hard problem. \n\n\nTheorem 4 comments on the teaching sample complexity also known as Teaching Dimension  achieved by our Algorithm 1 i.e. TIE produces an optimal teaching size for any instance of the problem. However, as we note this algorithm is not computationally efficient as it involves solving a NP-hard set cover problem in line 5 of OptimalTeach procedure of Algorithm 1. Secondly, in Theorem 7, we prove that in general one cannot avoid this hardness by showing that our problem is indeed NP-hard. \n\nFinally, we propose a computation efficient and approximately optimal algorithm by using a greedy solver for the set cover subproblem in line 5 of OptimalTeach procedure. We can call this algorithm Greedy-TIE which achieves an approximation ratio of $\\log(|\\mathcal A|-1)$ on optimal teaching size as stated in Corollary 8. \n\nThe approximation result follows straightforwardly from the following known results in approximation of the set cover problem: \"Consider a set cover problem where universe set is of size $n$ and each cover subset is of size at most $m$, then the greedy algorithm achieves an approximation ratio of $\\log(m)$ on the size of the optimal cover\" [2]. In our case, since the size of each cover subset is at most $A-1$, the corollary follows. \n\n### **3. Is it essential to require optimal policy to be in the learner's policy class? Can we extend it to agnostic setting?**\n   \nThis is a great question. Indeed, we can extend our setup to an agnostic teaching setting, where the learner's (policy) function class need not contain the globally optimal policy. In that scenario, the teacher will aim to teach the class (approximately) optimal policy to the learner i.e. $\\pi^* \\leftarrow \\arg\\max_{\\pi \\in \\Pi(w), w \\in \\mathbb R^d} V^{\\pi_w}_\\mu$. \n\nWe note that the teacher would eventually have to suffer a finite approximation error which cannot be avoided due to the bias induced by the learner's restricted feature function and the associated linear hypothesis class. Moreover, since the class optimal policy is realizable wrt the feature function $\\phi$, our results and analysis would apply to teaching this policy as well. \n\n### **4. Compare to learner-specific optimal teaching**\nMost prior works on optimal teaching of specific learners are limited to a relatively 'easier' constructive setting where the teacher can construct any covariate/feature vector in $\\mathbb R^d$. On the other hand, our setting is non-constructive where the teacher can only use the feature vectors induced by (state, action) tuple leading to a difficult combinatorial optimization problem that is not present in a constructive setting. \n\nDue to this reason, the optimal teaching algorithms proposed by prior works would fail to even produce a valid teaching set(they would only produce covariate vectors rather than actual states to teach) and thus cannot be applied to our setting.\n\n### **5. Regarding computational complexity**\n\nWe understand your concern and would like to note that $n$ is not a natural parameter for the diamond game example. Instead the set of all possible configurations in which objects could appear on the board, i.e., the state space is a natural parameter for the problem. In RL literature, a poly-time algorithm in $|S|, |A|$ space is considered efficient [1]. On the other hand, expecting a sublinear complexity would raise the following question : how can one expect to find the most optimal dataset if they are not even allowed to enumerate all input points? \n\nNevertheless, the exponential reduction in teaching set size from $|S|$ to $\\log(|S|)$ is of great importance in any real-life setting as it can significantly speed up the training process of the learner.\n\nFurthermore, we note that computing an optimal teaching set is only a one-time cost. Once the teacher computes it, it can use the same teaching set to teach any consistent learner. On the other hand, prior works require computing an optimal teaching set for each learner which can be more computationally expensive for teaching a class of diverse consistent learners.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qrx8Mv93Ng", "reviewer": "Reviewer_pEtD", "summary": "The authors propose a method for determining the a minimal dataset of state-actions tuples that would allow a family of linear learning agents to learn to imitate the optimal policy of a teacher. The authors motivate their method by describing the desired set of all linear weights that lead to an optimal policy through the difference in feature vectors between optimal and non-optimal features, $w^\\top (\\psi(s,\\pi^*(a)) - \\psi(s,b)) > 0$, and noticing that each datapoint eliminates a halfspace, $\\lbrace w : w^\\top (\\psi(s,\\pi^*(a)) - \\psi(s,b))\\rbrace$. They show that this covering problem is equivalent to covering the \"extreme rays\" of the cone of the differences in feature, $\\psi(s,\\pi^*(a)) - \\psi(s,b)$. Once the extreme rays are found, the states to include in the dataset are found by finding the minimal set of states that cover them through the solving of a finite cover set problem.\n\nThe authors provide an analysis of their method showing that it is optimal. Additionally, they show that this problem is NP-hard and provide an approximate algorithm for finding near-minimal datasets. Finally, the authors show their method working in a \"pick the right diamond\" game, a maze navigation programming problem, and polygon tower environment.", "questions": "Line 63, what is the meaning of $\\Delta$?\n\nCorollary 5, how strong are these assumptions? When would they realistically hold?", "limitations": "No issues", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and structured.\n\nThe theoretical results are conclusive and provide an interesting perspective on the problem.", "weaknesses": "I do not have any significant criticism.\n\n\n### minor comments and typos\n\nLine 67, if $\\mathcal{L}: D \\to 2^\\mathcal{H}$ and $\\mathcal{H} = \\mathbb{R}^d$, what does $2^{\\mathbb{R}^d}$ mean?\n\nLine 67, $\\mathcal{L}(D)$ is assigned the argmin of a $w$ and $\\pi$, feels like there are some type mismatch here.\n\nLine 163, \"an ray\" -> \"a ray\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and their valuable feedback. Please find our responses to your individual comments below.\n\n### **1. Clarification on notations and typos.**\n   - The set  $2^{𝑅^𝑑}$ denotes the set of all possible subsets of $\\mathbb R^d$ space. The learner's version space belongs to this set.\n   - $L(D)$ denotes all possible consistent policies that minimize the empirical risk of the learner. Switching the ordering of $w$ and $\\pi$, i.e., the learner first chooses a consistent $w$ and then selects any policy induced by this $w$ fixes this issue.\n   - $\\Delta$ denotes the simplex over finite input set. In this case, it denotes all stochastic policies over the argmax action set.  \n   - We thank you for pointing out the typos! We will fix them in the updated version.\n\n### **2. How strong is the finite extreme ray assumption in the infinite state setting in corollary 5.**\n\nWe appeciate your attention to this point. In practical settings, it is not hard to find examples where this assumption holds true. For example, consider the following environment (with continuous state space) where an agent moves in a circle with a fixed center and radius in a clockwise direction. The state of the agent is defined by a continuous angle value in $[0,2\\pi)$. \n\nNow, consider a feature function that maps the angle into one of four quadrants represented by four one-hot vectors in $\\mathbb R^4$. Note that even though the state space is infinite the induced feature space and correspondingly the extreme rays are finite in size and thus our assumption holds true.\n\nWe hope our responses satisfactorily answered your questions. Thank you for your time and consideration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3fCAAFWqJ8", "reviewer": "Reviewer_sX37", "summary": "This paper studies optimal teaching of behavior cloning learner with a linear hypothesis class, that is, finding the minimum number of demonstrations needed to teach a target policy to the entire family of consistent linear BC learner. They first show that this problem can be transformed into a finite set-cover problem, which is NP-hard when the size of action space is greater than $2$. They also propose an efficient approximately optimal algorithm such that the size of dataset is at most $\\log(|A|-1)$ times that of the optimal one. Finally, they perform empirical experiments to show that their algorithm finds a much smaller teaching set compared to using all data and randomly selecting a subset of data.", "questions": "1. Perfectly fitting the learner to the training set is not a common practice. Does it have any implication on the validation accuracy?\n2. Can you obtain any meaning results without the realizability assumption?", "limitations": "Nothing necessary stands out.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies a setting of potentially great importance in practice: finding the smallest dataset that can teach a family of BC learner to fit the optimal policy. Such an algorithm would be useful when there is a large dataset and the horizon is long. The results presented in this paper is elegant and initial experimental results seem promising. The paper is also easy to follow with clear notations.", "weaknesses": "1. It is a bit unclear to me why being able to teach a family of learners is preferable compared to teaching a specific type of learner. The author gives a motivating example on teaching a whole class of students, but I am still not sure whether there are any real application scenario in machine learning that can motivate such a setting.\n\n2. Although the approximately optimal algorithm runs in polynomial time, the time complexity still scales up quickly w.r.t the number of states and actions and does not seem to be practical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and suggestions. Please find our replies to your individual raised concerns below. \n\n### **1. Why teaching a family instead of individual learners - any real scenario in ml?**\n\nWe appreciate your thoughtful question. In a real life scenario of teaching a population of learners, each one can have their own bias for choosing one consistent hypothesis over the other which are often implicitly induced by their loss function. Designing an optimal teaching dataset for each of them would not only require algorithmic novelty but it would also be computationally expensive for the teacher. However, if all the learners are consistent, our teacher can easily construct a single teaching dataset to teach them all.\n\nFor an example, consider the following teach-by-demonstration task in a robotic setting. In a population of users, every user trains their own robot to assist them in home cleaning task by providing demonstrations to them. Each user may likely use a different algorithm to train their robot. \n\nFrom a security point of view, it’s more safe for the users to accept training data as they can evaluate the labels directly. On the other hand, accepting a trained model opens the possibility of hidden backdoors. In that scenario, assuming they all use consistent linear learners, our teacher can construct a small demonstration dataset and provide it to all the users so that they can train their algorithm to the correct behavior policy. \n\n\n\n### **2. Time complexity scales quickly with state size.**\n   \nWe understand your concern and would like to note that $n$ is not a natural parameter for the diamond game example. Instead all possible configurations in which objects could appear on the board, i.e., the state space is a natural parameter to quantify the complexity of the problem. In RL literature, a poly-time algorithm in $|S|, |A|$ space is considered efficient [1]. On the other hand, expecting a sublinear complexity would raise the following question : how can one expect to find the most optimal dataset if they are not even allowed to enumerate all input points? \n\n\nNevertheless, the exponential reduction in teaching set size from $|S|$ to $\\log(|S|)$ is of great importance in any real-life setting as it can significantly speed up the training process of the learner.\n\nFurthermore, we note that computing an optimal teaching set is only a one-time cost. Once the teacher computes it, it can use the same teaching set to teach any consistent learner. On the other hand, prior works require computing an optimal teaching set for each learner which can be more computationally expensive for teaching a class of diverse but consistent learners.\n\n\n### **3.  Imperfectly fitting the training dataset for the learner.**\n\nIt would indeed be interesting to consider learners that cannot perfectly fit the demonstrated data. However, recent works like [1],[2] on over-parameterized models have suggested that overfitting training data perfectly need not be a bad thing(as was thought previously) and it leads to improved generalization error. \nFurthermore, in the context of machine teaching, several past works like [3], [4], [5] have made this assumption. So, we believe it is a reasonable assumption to start with and leave it to future works to address.\n\t \n\n### **4. Meaningful results without realizability assumption.**\n\nIndeed, we can extend our setup to an agnostic teaching setting, where the learner's (policy) function class need not contain the globally optimal policy. In that scenario, the teacher will aim to teach the class (approximately) optimal policy to the learner i.e. $\\pi^* \\leftarrow \\arg\\max_{\\pi \\in \\Pi(w), w \\in \\mathbb R^d} V^{\\pi_w}_\\mu$. \n\nWe note that the teacher would eventually have to suffer a finite approximation error which cannot be avoided due to the bias induced by the learner's restricted feature function and the associated linear hypothesis class. Moreover, since the class optimal policy is realizable wrt the feature function $\\phi$, our results and analysis would apply to teaching this policy as well. \n\nWe hope our responses satisfactorily answered your questions. Should you have any follow up questions, please let us know. Thank you for your time and consideration!\n\n---\nReferences :\n\n [1] \"Reconciling Modern Machine Learning and the Bias-Variance Trade-off\" by Belkin et al. (PNAS 2019)\n\n [2] \"Understanding Deep Learning Requires Rethinking Generalization\" by Zhang et al. (ICLR 2017)\n\n [3] \"On the complexity of teaching\" by Goldman et. al. \n\n [4] \"The Teaching Dimension of Linear Learners\" by Liu et. al. (JMLR 2017)\n\n [5] \"The Teaching Dimension of Kernel Perceptron\" by Kumar et. al. (AISTATS 2021)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mLA8Fnz0LJ", "reviewer": "Reviewer_d9NQ", "summary": "Summary: \nThis paper \"Optimal Teaching of Linear Behavior Cloning Learners\" introduces a novel algorithm called TIE (Teach using Iterative Elimination) aimed at efficiently teaching a family of consistent linear behavior cloning (BC) learners. The algorithm focuses on constructing an optimal teaching set from a fixed set of states, demonstrating actions that induce the target policy across all members of the learner family. The approach is evaluated across various environments, demonstrating its effectiveness in producing near-optimal teaching sets compared to baseline methods. \n\nStrengths:\nAlgorithmic Innovation: \nTIE introduces a systematic approach to teaching linear BC learners by iteratively eliminating states that are not necessary for inducing the target policy. This iterative elimination based on covering extreme rays of the version space cone simplifies the otherwise complex problem of optimal teaching.\n\nTheoretical Guarantees: \nThe paper provides theoretical guarantees, showing that TIE achieves near-optimal teaching dimension, particularly noting its efficiency in generating teaching sets that cover the version space efficiently. This is supported by proofs and corollaries that establish the algorithm's effectiveness under different settings.\nEmpirical Validation: \nThe effectiveness of TIE is demonstrated across diverse environments, including maze navigation and coding tasks. It consistently outperforms baseline methods such as Teach-All and Teach-Random, illustrating its practical applicability and superiority in real-world scenarios.\n\nWeaknesses:\nComputational Complexity: \nWhile the paper discusses the efficiency of TIE in generating teaching sets, the computational complexity may increase significantly with larger state and action spaces. The approach relies on solving set cover problems, which can be NP-hard, especially as the size of the action space increases.\n\nAssumption of Known Features: \nThe algorithm assumes knowledge of feature representations and their effectiveness in inducing the target policy. This may limit its applicability in cases where feature representations are not well-defined or when the learner's policy cannot be fully captured by the chosen features.\n\nGeneralization to Non-linear Learners: \nThe focus on linear BC learners limits the generalizability of the proposed method to more complex learners such as neural networks or non-linear models. Extending the approach to these settings would require significant adaptation and validation.\n\nInsignificant Community Contribution:\nThis work assumes that learners possess consistent properties, which is an overly stringent assumption imposing strict constraints on the hypothesis class. In Section 3.1, while the main contribution is outlined, it lacks a rigorous analysis, failing to obtain the necessary approximation loss. Regarding Section 3.2, the contributions appear negligible; the theorems and lemmas presented therein do not lead to significant conclusions.", "questions": "How to control the approximation teaching loss? Any safety guarantees?", "limitations": "This work assumes that learners possess consistent properties, which is an overly stringent assumption imposing strict constraints on the hypothesis class. \n\nThe recent contributions to the machine teaching community have been overlooked. Please consider including more surveys from recent conferences.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Strengths:\n\nAlgorithmic Innovation: \nTIE introduces a systematic approach to teaching linear BC learners by iteratively eliminating states that are not necessary for inducing the target policy. This iterative elimination based on covering extreme rays of the version space cone simplifies the otherwise complex problem of optimal teaching.\n\nTheoretical Guarantees: \nThe paper provides theoretical guarantees, showing that TIE achieves near-optimal teaching dimension, particularly noting its efficiency in generating teaching sets that cover the version space efficiently. This is supported by proofs and corollaries that establish the algorithm's effectiveness under different settings.\n\nEmpirical Validation: \nThe effectiveness of TIE is demonstrated across diverse environments, including maze navigation and coding tasks. It consistently outperforms baseline methods such as Teach-All and Teach-Random, illustrating its practical applicability and superiority in real-world scenarios.", "weaknesses": "Weaknesses:\nComputational Complexity: \nWhile the paper discusses the efficiency of TIE in generating teaching sets, the computational complexity may increase significantly with larger state and action spaces. The approach relies on solving set cover problems, which can be NP-hard, especially as the size of the action space increases.\n\nAssumption of Known Features: \nThe algorithm assumes knowledge of feature representations and their effectiveness in inducing the target policy. This may limit its applicability in cases where feature representations are not well-defined or when the learner's policy cannot be fully captured by the chosen features.\n\nGeneralization to Non-linear Learners: \nThe focus on linear BC learners limits the generalizability of the proposed method to more complex learners such as neural networks or non-linear models. Extending the approach to these settings would require significant adaptation and validation.\n\nInsignificant Community Contribution: \nThis work assumes that learners possess consistent properties, which is an overly stringent assumption imposing strict constraints on the hypothesis class. In Section 3.1, while the main contribution is outlined, it lacks a rigorous analysis, failing to obtain the necessary approximation loss. Regarding Section 3.2, the contributions appear negligible; the theorems and lemmas presented therein do not lead to significant conclusions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and suggestions. Please find our replies to your individual raised concerns below. \n\n### **1. Regarding the setting where the feature function is not well defined.**\n   \n\nThank you for your feedback. We believe your comment may be referring to the scenario when the teacher does not know the exact feature function of the learner. If this is not what you meant, we would greatly appreciate further clarification so that we can appropriately address your concerns.\n\nAssuming you meant the former, we note that in a benevolent teaching setting, it is considered safe for the teacher to know the feature function of the learner. Indeed, several prior works in machine teaching like [6],[7],[8] have made this assumption. However, we acknowledge that it would be an interesting direction to study if the teacher can itself learn about the feature function of the learner but this is beyond the scope of this work and we leave it to the future works to address this setting.\n\n\n### **2. When learner's feature function  and corresponding approximation guarantee.**\n   \nWe acknowledge that realizability can be a strict requirement for the learner and appreciate your concern about it. Indeed it would be interesting to also consider approximate teaching goals where the teacher is required to teach a class optimal policy(best policy in its hypothesis class) to the learner.\n\nIn fact it is quite easy to extend our work to the setting of teaching approximately optimal policy to the learner i.e. $\\pi^* \\leftarrow \\arg\\max_{\\pi \\in \\Pi(w), w \\in \\mathbb R^d} V^{\\pi_w}_\\mu$. Since the class optimal policy is realizable wrt the feature function $\\phi$, our results and analysis would apply to teaching the approximate optimal policy as well. However, we note that the teacher would eventually suffer a finite approximation error which cannot be avoided due to the bias of the learner’s hypothesis class. \n\n\n### **3. Clarifying the relevance of theorem and lemmas in section 3.2 to optimal teaching.**\n\n\nWe respectfully disagree with your observation that theorems and lemmas in section 3.2 does not lead to any conclusions. In fact, the lemma 2 is crucial to giving us a handle to solve the seemingly difficult infinite set covering problem that comes up when attempting to solve the problem naively using prior method of inconsistent hypothesis elimination. \n\nWe note that section 3.1 just aims to highlight the difficulty of solving our optimal teaching problem by naively using the method of inconsistent hypothesis elimination used in prior works [3]. Since our universe and cover subsets are uncountable, it leads to a non-trivial uncountable set covering problem that cannot be solved by prior methods. \n\nOur main contribution lies in showing that this problem of covering/eliminating the uncountable set can ultimately be reduced to covering the finite extreme rays of the induced cone(as shown in Lemma 2). This motivates our algorithm TIE which tries to first find the extreme rays of the cone and then cover it using the smallest subset of finite states. We later prove that our exact algorithm TIE is NP-hard but also provide an efficient greedy version of TIE that comes with $\\log(|A|-1)$ approximation guarantee.\n\n### **4. Regarding missing recent related works and surveys.**\n\nWe appreciate your constructive comment to include more recent related works in machine teaching in our paper. On our side, we have taken care to cite all recent works specifically on teaching linear learners, version space learners, and RL learners that are relevant to our paper. \n\nHowever, we recognize that despite our diligence, some of the important papers might have been inadvertently missed. We would greatly appreciate it if you could point us to any specific paper or surveys you have in mind and we will be happy to include it in our related works section. We thank you for your help to enhance the quality of our paper.\n\n### **5. Generalization to non-linear consistent neural network learners.**\n   \nWe thank you for your suggestion to generalize our setting to teaching more complex learners like neural networks. Indeed, it would be an interesting direction to extend our work to fully trainable neural networks(NN). However, we note that quantifying the version space of NN learners in itself is a challenging problem, and is beyond the scope of our linear learning.\n\nNevertheless, we would like to mention a simplified transfer learning setting(where all except the last layers of the NN are fixed and have been very popular for large models recently), where our teaching algorithm can be directly applied to teaching consistent NN learners using latent feature representation. \n\nMore concretely, one can treat the pre-trained network(excluding the last layer) as feature representation function $\\phi$ in our setting and apply our TIE algorithm of the induced latent feature space. Since our primary focus was on studying optimal teaching for consistent linear learners, we did not mention this simple extension in our work but would be happy to include a subsection in the appendix if you think highlighting this connection would be helpful to a broader audience.\n\n### **6. Regarding consistency property being an overly stringent assumption.**\n\nIt would be indeed interesting to consider a scenario where the learner cannot perfectly fit the demonstrated data. However, recent works [1],[2] on over-parameterized models have shown that overfitting data may not be a bad thing(as was thought previously) and leads to improved generalization performance.\n\nFurthermore, in thoery of machine teaching, several past works [3], [4], [5] have made this assumption. So, we believe its a good first step towards our goal of understanding optimal teaching of consistent linear learners and leave it to future works to address inconsistent learners.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of optimally teaching the behavior generated by a linear decision policy, assuming that the learner is a consistent linear classifier. The authors reduce this to a set cover problem and present solutions, hardness results and an approximation algorithm for it. They further complement the results with empirical evaluation. 
Perhaps I missed something, but I fail to see what is important about the RL problem here. Since BC, as formulated here, is essentially multiclass linear classification, why is this not a paper about multiclass linear classification? Secondly, for baselines in the experiments, why is optimal design not a valid baseline?
Decision: Accept (poster)