Strategic Classification under Unknown Personalized Manipulation
Authors: Han Shao
Avrim Blum
Omar Montasser
Venue: NeurIPS 2023 poster (2023)
Keywords: strategic classification
mistake bound in online learning
PAC learning
TL;DR: We study the strategic classification problem when the agents' manipulations are personalized and unknown.

Abstract: We study the fundamental mistake bound and sample complexity in the strategic classification, where agents can strategically manipulate their feature vector up to an extent in order to be predicted as positive. For example, given a classifier determining college admission, student candidates may try to take easier classes to improve their GPA, retake SAT and change schools in an effort to fool the classifier. *Ball manipulations* are a widely studied class of manipulations in the literature, where agents can modify their feature vector within a bounded radius ball. Unlike most prior work, our work consider manipulations to be *personalized*, meaning that agents can have different levels of manipulation abilities (e.g., varying radii for ball manipulations), and *unknown* to the learner.

We formalize the learning problem in an interaction model where the learner first deploys a classifier and the agent manipulates the feature vector within their manipulation set to game the deployed classifier. We investigate various scenarios in terms of the information available to the learner during the interaction, such as observing the original feature vector before or after deployment, observing the manipulated feature vector, or not seeing either the original or the manipulated feature vector. We begin by providing online mistake bounds and PAC sample complexity in these scenarios for ball manipulations. We also explore non-ball manipulations and show that, even in the simplest scenario where both the original and the manipulated feature vectors are revealed, the mistake bounds and sample complexity are lower bounded by $\Omega(|\mathcal H|)$ when the target function belongs to a known class $\mathcal H$.

Strategic Classification under Unknown Personalized Manipulation
Han Shao Toyota Technological Institute Chicago Chicago, 60637 han@ttic.edu
Avrim Blum
Omar Montasser
Toyota Technological Institute Chicago Chicago, 60637 avrim@ttic.edi
Toyota Technological Institute Chicago Chicago, 60637 omar@ttic. edu
Abstract
We study the fundamental mistake bound and sample complexity in the strategic classification, where agents strategically manipulate their feature vector up to an extent in order to be predicted as positive. For example, given classifier determining college admission, student candidates may try take easier classes improve their GPA, retake SAT and change schools an effort to fool the classifier. Ball manipulations are widely studied class of manipulations in the literature, where agents can modify their feature vector within bounded radius ball. Unlike most prior work, our work considers manipulations be personalized, meaning that agents can have different levels of manipulation abilities (e.g., varying radii for ball manipulations), and unknown the learner.
We formalize the learning problem an interaction model where the learner first deploys classifier and the agent manipulates the feature vector within their manipulation set to game the deployed classifier. in terms of the information available to the learner during the interaction, such as observing the original feature vector before or after deployment, observing the manipulated feature vector, not seeing either the original the manipulated feature vector. We begin by providing online mistake bounds and PAC sample complexity in these scenarios for ball manipulations. We also explore non-ball manipulations and show that, even in the simplest scenario where both the original and the manipulated feature vectors are revealed, the mistake bounds and sample complexity are lower bounded by ?((H) when the target function belongs to a known class H.
investigate various scenarios
Introduction
Strategic classification addresses the problem of learning a classifier robust to manipulation and gaming by self-interested agents (Hardt et al. 2016). For example, given classifier determining loan approval based on credit scores, applicants could open or close credit cards and bank accounts to increase their credit scores. In the case of college admission classifier, students may try take easier classes to improve their GPA, retake the SAT or change schools in an effort to be admitted. both cases, such manipulations do not change their studied strategic classification in both the online setting where examples are chosen by an adversary in sequential manner (Dong al. 2018 Chen et al. 2020 Ahmadi et al. 202 2023). and the
qualifications. Recently, a collection of papers has
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

distributional setting where the examples are drawn from an underlying data distribution (Hard ct al. 2016; Zhang and Conitzer, 2021 Sundaram et al. 202T: Lechner and Umer 2022). Most existing works assume that manipulation ability is uniform across all agents or is known to the learner. However, in reality, this may not always the case. For instance, low-income students may have a lower ability to manipulate the system compared to their wealthier peers due to factors such as the high costs of retaking the SAT or enrolling in additional classes, as well as facing more barriers to accessing information about college (Milli et al. 2019) and it is impossible for the learner to know the highest achievable GPA or the maximum number of times a student may retake the SAT due to external factors such as socio-economic background and personal cireumstances.
We characterize the manipulation of an agent by a set of alternative feature vectors that she can modify her original feature vector to, which we refer to as the manipulation set. Ball manipulations are widely studied class of manipulations in the literature, where agents can modify their feature vector within a bounded radius ball. For example, Dong et al. (2018); Chen et al. [2020); Sundaram et al. (202T) studied ball manipulations with distance function being some norm and Zhang and Conitzer (202I): Lechner and Urner (2022); Ahmadi et al. (203)) studied manipulation graph setting, which can be viewed as ball manipulation w.r.t. the graph distance on a predefined known graph.
In the online learning setting, the strategic agents come sequentially and try to game the current classifier. Following previous work, we model the learning process as a repeated Stackelberg game over T time steps. In round f, the learner proposes a classifier fo and then the agent, with a manipulation set (unknown the learner), manipulates her feature in an effort to receive positive prediction from fe- There are several settings based on what and when the information is revealed about the original feature vector and the manipulated feature vector the game. The simplest setting for the learner is observing the original feature vector before choosing St and the manipulated vector after. In a slightly harder setting, the learner observes both the original and manipulated vectors after selecting fe. An even harder setting involves observing only the manipulated feature vector after selecting ft. The hardest and least informative scenario occurs when neither the original nor the manipulated feature vectors are observed.
In the distributional setting, the agents are sampled from an underlying data distribution. Previous work assumes that the learner has full knowledge of the original feature vector and the manipulation set, and then views learning as one-shot game and solves it by computing the Stackelberg equilibria of it. However, when manipulations are personalized and unknown, we cannot compute equilibrium and study learning as a one-shot game. In this work, we extend the iterative online interaction model from the online setting to the distributional setting, where the sequence of agents is sampled i.i.d. from the data distribution. After repeated learning for T (which is equal to the sample size) rounds, the learner has to output a strategy-robus, predictor for future use.
In both online and distributional settings, examples are viewed through the lens of the current predictor and the learner does not have the ability to inquire about the strategies the previous examples would have adopted under a different predictor.
Related work Our work is primarily related to strategic classification in online and distributional settings. Strategic classification was first studied in a distributional model by Hardt et al. (2016) and subsequently by Dyng et al. (2018) in an online model. Hardt et al. (2016) assumed that agents manipulate by best response with respect to a uniform cost function known to the learner. Building
on the framework of (Hardt et al. 2016), Lechner and Urner (2022); [Sundaram et al. (2021 Zhang and Conitzer 2021]; Hu et al. 2019); Milli et al. (2019) studied the distributional learning problem, and all of them assumed that the manipulations are predefined and known the learner, either by cost function or a predefined manipulation graph. For online learning. Dong et al. (2018) considered a similar manipulation setting as in this work, where manipulations are personalized and unknown. However, they studied linear classification with ball manipulations in the online setting and focused on finding appropriate conditions of the cost function achieve sub-linear Stackelberg regret. Chen et al. (2020) also studied Stackelberg regret in linear classification with uniform ball manipulations. Ahmadi et al. (202T) studied the mistake bound under uniform (possbily unknown) ball manipulations. and Abmadi et al. 2023) studied regret under a pre-defined and known manipulation. The most relevant work a recent concurrent study by Lechner et al., (2023), which also explores strategic classification involving unknown personalized manipulations but with different loss function. In their work, a predictor incurs a loss of if and only if the agent refrains from manipulation and the predictor correctly predicts at the unmanipulated feature vector. In our work, the predictor's 's loss is 0

---

if it correctly predicts at the manipulated feature, even when the agent manipulates. As result, their loss function serves as an upper bound of our loss function.
There has been a lot of research on various other issues and models in strategic classification. Beyond sample complexity, (Hu et al. (2019): Milli al. (2019) focused other social objectives, such as social burden and faimess. Recent works also explored different models of agent behavior, including proactive agents Zrnic al. (2021). non-myopic agents (Haghtalab al. 2022) and noisy agents (Ja- gadeesan et al. 2021). Ahmadi et al. (2023) considers two agent models of randomized learners: a randomized algorithm model where the agents respond to the realization, and a fractional classifier model where agents respond to the expectation, and our model corresponds to the randomized al- gorithm model. Additionally, there is also a line of research on agents interested in improving their qualifications instead of gaming (Kleinberg and Raghavan, (2020) Haghtalab et al., 2020; Ahmadii
al.
2022 J. Strategic interactions in the regression setting have also been studied (e.g.. Bechavod
et al.
2021
Beyond strategic classification, there is a more general research area of learning using data from strate- gic sources, such as a single data generation player who manipulates the data distribution (Brückner and Scheffer, 2alvi et al. 2004). Adversarial perturbations can be viewed another type of strategic source (Montasser el al. 2019).
2 Model
Strategic classification Throughout this work, we consider the binary classification task. Let X denote the feature vector space, ) = [+1,-1] denote the label space, and 7 S y denote the hypothesis class, In the strategic setting, instead of an example being pair (a., y), an example, or agent, is triple (2r, u, y) where x E X' is the original feature vector, y E 3/ is the label, and u C X is the manipulation set, which is of feature vectors that the agent can modify their original feature vector & to. In particular, given a hypothesis h E y²² the agent will try to manipulate her feature vector x to another feature vector z' within manipulation set u is unknown to the learner. In this work, we will be considering several settings based on what the information is revealed to the learner, including both the original/maniiulated feature vectors, the manipulated feature vector only, or neither, and when the information is revealed.
order to receive a positive prediction from h. The
More formally, for agent (z, u. v), given predictor h. if M(x) -1 and her manipulation set overlaps the positive region by h, ie.. u n Xn,+ * with Xr,+ := fir E X hx()) = +1}, the agent will manipulate r to A(z, h, u) E u un too receive positive prediction by h. Otherwise, the agent will do nothing and maintain her feature vector at x. i.e., A(xr, h, u) x. We call A(x, h u) the manipulated feature vector of agent (Ir, u, y) under predictor h.
A general and fundamental type of manipulations is ball manipulations, where agents can manipulate their feature within a ball of personalized radius. More specifically, given a metric over X, the manipulation set is a ball r();r) = {x' [d(z, x²) S r centered at x with radius for some E Rzo- Note that we allow different agents to have different manipulation power and the radius can vary over agents. Let Q denote the set of allowed pairs (z, u), which refer to as the feature feature-manipulle manipulation set space. For ball manipulations, we have Q = [<x,B<;; r))lz E X.r E R20} for some known metric d over X. In the context of ball manipulations, we use (z, 7. y) to represent (x, B(x;r),)) and A (x. h r) to represent (xx h, Blx;; r) for notation simplicity.
For any hypothesis h. let the strategic loss get (h, (I., u. v)) of h be defined as the loss at the manip- ulated feature, i.e., (h, (a. u, v)) == 1(h(A(r, h, u)) + y). According to our definition of A(-). we can write down the strategic loss explicitly as
y = 1, h(x) = +1
yf = - 11)(() = and u n Kr,+ * 0, if = +1, h(x))
eat (h, (z. u, 9))
1
= -1 and u n Kh,+ = 0.
0
otherwise.
For any randomized predictor p (a distribution over hypotheses), the strategic behavior depends on the realization of the predictor and the strategic loss of is ("t(p, (I, u, v)) := En-p [ (h, (2, u, v))].
For ball manipulations, agents break ties by selecting the closest vector. When there are multiple closest vectors, agents break ties arbitrarily. For nol- manipulations, agents break ties in any fixed way.
3

---

Online learning We consider the task of sequential classification where the learner aims to classify a sequence of agents (2), in V1), (I2, U2 8/2, ..... (ZT, uy, (r) E Q x 3 that arrives in an online manner. At each round, the learner feeds a predictor to the environment and then observes his prediction Dr. the true label Yt and possibly along with some additional information about the original/maniiulltten feature vectors. We say the learner makes mistake at round t if Tr A V/ and the learner's 's goal is to minimize the number of mistakes on the sequence. The interaction protocol (which repeats for 1 = ,.) is described in the following.
Protocol Lecaner-Agen Interaction at round f
1: The environment picks an agent (zg, Me Mr) and reveals some context ((z)). In the online setting, the agent is chosen adversarially, while in the distributional setting, the agent is sampled i.i.d.
2: The learner A observes C(x)) and picks hypothesis ft E )
3: The learner A observes the true label St. the prediction De = fi(A)), and some feedback
F(x,, Ax), where A. (rr, ft, u+) is the manipulated feature vector.
The context function CC-) and feedback function F()) reveals information about the original feature vector 2t and the manipulated feature vector A, C(-) reveals the information before the learner picks fe while F-) does after. We study several different settings based on what and when information is revealed.
The simplest setting for the learner is observing the original feature vector Ie before choosing fi and the manipulated vector A, after. Consider teacher giving students writing assignment or take-home exam. The teacher might have a good knowledge of the students' abilities (which correspond to the original feature vector xx)) based on their performance in class, but the grade has to be based on how well they do the assignment. The students might manipulate by using the help of ChatGPT / Google/ / Wolfram / their parents, etc. The teacher wants create an assignment that will work well even in the presence of these manipulation tools. In addition, If we think of each example as representing a subpopulation (e.g., an organization thinking of offering loans to a certain group), then there might be known statistics about that population, even though the individual classification (loan) decisions have to be made based on responses to the classifier. This setting corresponds to C(xa)= = and F(x,, A.) = A. We denote setting by their values of C, F and thus, we denote this setting by (x. A).
In slightly harder setting, the learner observes both the original and manipulated vectors after selecting fr and thus, ft cannot depend on the original feature vector in this case. For example, if a high-school student takes the SAT test multiple times, most colleges promise to only consider the highest one (or even to "superscore" the test by considering the highest score separately in each section) but they do require the student to submit all of them. Then C(x²) = and Flx Ae) = (Zz, At), where T token for "no information", and this setting is denoted by (1, (I,A)),
An even harder setting involves observing only the manipulated feature vector after selecting fo (which can only be revealed after fi since A, depends on ft). Then C(x,) =1 and F(x,, A.) = A. and this setting is denoted by AL.
The hardest and least informative scenario occurs when neither the original nor the manipulated feature vectors are observed. Then C(x,)) =1 and F FIz, A.) =1 and it is denoted by (1, 1).
Throughout this work, we focus on the realizable setting, where there exists a perfect classifier in H. that never makes any mistake at the sequence of strategic agents. More specifically, there exists hypothesis h²" E H such that for any t E [T), we have yt = h² ha (A(I,, h", ut) Then we define the mistake bound follows.
Definition 1. For any choice of (C, let A be online learning algorithm der Protocol 1 in the setting of (C,F). Given any realizable sequence S (IT,UT, h² h- (A(TT, h², (uT))) E (Ω x ))"" where T is any in- teger and h² E H. let MM(S)) be the number of mistakes A makes on the sequence S. The mistake N such that there exists an algorithm A such that MA(S)= < B over all realizable sequences S of the above form.
(x11, u1, h² hr'hh""( (AT1, hh, ((),)))).....
bound of (H, Q), denoted MBc,F, F, is the smallest number
PIt is possible that there is no hypothesis Te y s.t. y: T((xze) for all t [1]]
4

---

According the rank of difficulty of the four settings with different choices of F), the mistake bounds are ranked in the order of MB,,, I MB (r,A)= S MB I,A
IA S MB 1B
PAC learning In the distributional setting, the agents are sampled from an underlying dis- tribution D over 2 y. The learner's goal is find a hypothesis h with low popula- tion loss (h) := B(a,uy))-D (h, (I, u, y))] One may think of running empirical risk minimizer (ERM) over samples drawn from the underlying data distribution, i.e., returning arg min >in 1St (I,, u₁ vc)). where (z,, I1 Ui),..., (Tm, Um Vn,) are i..d. sampled from D. However, ERM unimplementable because the manipulation sets u4 are never revealed to the algorithm, and only the partial feedback in response to the implemented classifier is provided. In particular, this work we consider using the same interaction protocol as in the online setting, i.e., Protocol with agents (Iz, Ue, Vr) i..d. sampled from the data distribution D. After T rounds of interaction (i.e., T Lid. agents), the learner has to output a predictor fout for future use.
Again, we focus on the realizable setting, where the sequence of sampled agents (with manipulation) can be perfectly classified by target function in H. Alternatively, there exists classifier with zero population loss, i.e., there exists a hypothesis he E H such that (i(("") = 0. Then we formalize the notion of PAC sample complexity under strategic behavior as follows.
Definition 2. For any choice of F), let A be a learning algorithm that interacts with agents using Protocol
| in the setting of (C, F) and outputs a predictor fous in the end. For any E. 8 E (0. 1), the sample complexity of realizable (z, 6)-AA learning of (H. Q), denoted SCc, (E, 5). is defined as the smallest m. E N for which there exists a learning algorithm A in the above form such that for any distribution D over Q x y where there exists a predictor h² E H with zero loss, L (h) O, with
probability at least - 8 over (I1, 21,y1))))........)))1... 31..)...... (Zm, Mmn ym))
Ltd. D. (fott) SE.
Similar to mistake bounds, the sample complexities are ranked in the same order SCz,A I (C,,( I SC1,A < SC1,1 according to the rank of difficulty of the four settings.
3 Overview of Results
In classic (non-strategic) online learning, the Halving algorithm achieves a mistake bound of log( ())
by employing the majority vote and eliminating inconsistent hypotheses each round. In classic
PAC learning, the sample complexity of O (og(( (H)) is achievable via ERM. Both mistake bound and sample complexity exhibit logarithmic dependency on [76]. This logarithmic dependency on [H] (when there is no further structural assumptions) is tight in both settings, i.e., there exist examples of H. with mistake bound of 22 (log(()()) and with sample complexity of 22( log((HH)) ). In the setting where manipulation is known beforehand and only A, observed, Ahmadi al. (2023) proved a lower bound of ((H)) for the mistake bound. Since in the strategic setting we can achieve linear
dependency on [H] by trying each hypothesis in H one by one and discarding it once it makes mistake, the question arises:
Can we achieve logarithmic dependency on [H] in strategic classification?
In this work, we show that the dependency on |7(] varies across different settings and that in some settings mistake bound and PAC sample complexity can exhibit different dependencies on [H]. We start by presenting our results for ball manipulations in the four settings.
Setting of (a, A) (observing x, before choosing fr and observing A, after): For online learning, we propose an variant of the Halving algorithm, called Strategic Halving (Algorithm [. which can eliminate half of the remaining hypotheses when making mistake. The algorithm depends on ob- serving I2 before choosing the predictor ft. Then by applying the standard technique of converting mistake bound to PAC bound, we are able to achieve sample complexity of O log( (Hl) (H)))
Setting of (1L (I, A)) (observing both and A, after selecting fi): We prove that, there exists an example of (H, ②) s.t. the mistake bound is lower bounded by 12( This implies that no algorithm can perform significantly better than sequentially trying each hypothesis, which would make at most [7(] mistakes before finding the correct hypothesis. However, unlike the construction of mistake lower bounds in classic online learning, where all mistakes can be forced to occur in the
initial rounds, demonstrate that we require
rounds to ensure that all mistakes occur. In
5

---

the PAC setting, we first show that, any learning algorithm with proper output fout. i.., fout E H. needs a sample size S2( [ We can achieve a sample complexity of O log ([gg(( by executing Algorithm 2 which is randomized algorithm with improper output.
Setting of (T, A) (observing only A, after selecting ft) The mistake bound of ((H)) also holds this setting, as it is known to be harder than the previous setting. For the PAC learning, we show that any conservative algorithm, which only depends on the information from the mistake rounds, requires (2( [tl samples. The optimal sample complexity is left an open problem.
Setting of (T, (observing neither 2, nor A Similarly, the mistake bound of ((H)) still holds. For the PAC learning. we show that the sample complexity is 22( [k]] by reducing the problem to a stochastic linear bandit problem.
Then we move on to non-ball manipulations. However, we show that even in the simplest setting of observing 2, before choosing ft and observing A, after, there is an example of (H, Q) such that the sample complexity is O [9[] This implies that in all four settings of different revealed information,
we will have sample complexity of Ei( [Pl) and mistake bound of 52(1H()). We summarize our results in [
setting
mistake bound
sample complexity
(xr, A)
(llo(()H(I) (Thm
log( H1)
(Thm 2 2 log (H))
(onin(/log((7/()XT)) (741) (Thm 4
O log (124)) (Thm
52
log (PE)
(1, (1,
ball
2(min( [H [o] [H]) (Thm
SCPrpp = 22
(Thm
A)
((77)) (implied by Thm
SC 52(
H
g
(Thm
(1
((H)) (implied by Thm
O [
(Thm
nonball
all
(((H))(Corll 1b. O(HH)
[
92
H
(Cor
A factor of loglog( (Hl) is neglected.
Table I: The summary of results. O and f2 ignore logarithmic factors [7[ and 1 The superscripts prop stands for proper learning algorithms and csv stands for conservative learning algorithms. All lower bounds in the non-strategic setting also apply to the strategic setting, implying that
MBc, 2 (loog(( (?))) and SCc,F 2 (2( ( 2) for all settings of (C, F). In all four settings, mistake bound of ((H) can be achieved by simply trying each hypothesis in H while the sample
complexity can be achieved as Ö( [M]] by converting the mistake bound ((Hl)) a PAC bound
using standard techniques.
4 Ball manipulations
In ball manipulations, when B(x;r) n Xr,- has multiple elements, the agent will always break ties by selecting the one closest œ. i.e., (rr,hr h) arg min ( d(x, x²). In round the learner deploys predictor ft, and once he knows x, and ÿ., he can calculate A, himself without needing knowledge of r by
A aargmingex,, d(
if = +1
Ex
U -1
Thus, for ball manipulations, knowing 2e is equivalent knowing both xy and A.
4.1 Setting (z, A): Observing T; Before Choosing fr
Online learning We propose a new algorithm with mistake bound of log([?[]) in setting (z, A). To achieve logarithmic mistake bound, we must construct a predictor St such that if makes a mistake, we can reduce constant fraction of the remaining hypotheses. The primary challenge is that we do not have access to the full information, and predictions of other hypotheses are hidden. To extract the information of predictions of other hypotheses, take advantage of ball manipulations, which

---

induces an ordering over all hypotheses. Specifically, for any hypothesis h and feature vector we define the distance between z and by the distance between x and the positive region by h, th,+ i.e.,
(2) At each round I, given It, the learner calculates the distance d( ht) for all h in the version space (meaning hypotheses consistent with history) and selects hypothesis fa such that dz ft) is the median among all distances d(æ,, h)) for in the version space. We can show that by selecting fi in this way, the learner can eliminate half' of the version space if ft makes mistake. We refer to this algorithm as Strategic Halving, and provide a detailed description of it in Algorithm [
d(z, h) == min(d(2zz'')z= &h,+).
Theorem For any feature- -aature-ball manipulation set space Q and hypothesis class H. Strategic Halving achieves mistake bound MB,,A I log([?[)..
Algorithm Strategic Halving
1: Initialize the version space VS = H.
2: for 1.......... ,T do
3: pick an fa E VS such that d(re, ft) )) is the median of [d(z,, h)]h e VS}.
4: if Ue * 3r and y + then VS <- VS \ {h E VSId(z, h) d(z,, fi)):
5: else if Dt * yt and y/ then VS < VS \ (h E VSId(z,, s d(s,,
6: end for
To prove Theorem T we only need show that each mistake reduces the version space by half. Supposing that ft misclassifies a true positive example (t, by negative, then we know that d( fi) > rt while the target hypothesis h" must satisfy that d(x,, h²) S rt. Hence any with d(I,, h) 2 d(æ,, fr) cannot be h" and should be eliminated. Since d(I,, fi) is the median of {d(x,, hi]h VSJ, we can elimate half of the version space. It is similar when ft misclassifies true negative. The detailed proof is deferred to Appendix B
PAC learning We can convert Strategic Halving to a PAC learner by the standard technique of converting mistake bound to PAC bound (Gallant 1986). Specifically, the learner runs Strategic
Halving until it produces a hypothesis fr that survives for I log( log (Pd)) rounds and outputs this ft- Then we have Theorem 2 and the proof is included in Appendix
C
Theorem 2. For any feature-ball manipulation set space Q and hypothesis class H. we can achieve SCz.a 6) = O ((og(124)) log( [og([(H() )) by combining Strategic Halving and the standard technique é bound a PAC bound.
of converting a mistake
4.2 Setting (1. (2, A)): Observing xy After Choosing ft
When 2; is not revealed before the learner choosing ft, the algorithm of Strategic Halving does not work anymore. We demonstrate that is impossible to reduce constant fraction of version space when making a mistake, and prove that the mistake bound is lower bounded by S2((?(() by constructing negative example of (H, Q). However, we can still achieve sample complexity with poly-logarithmic dependency on [H] in the distributional setting.
4.2.1 Results in the Online Learning Model
To offer readers an intuitive understanding of the distinctions between the strategic setting and standard online learning, commence by presenting example in which no deterministic learners, including the Halving algorithm, can make fewer than [7]] mistakes.
Example 1. Consider a star shape metric space (X,d), where X = I...,.....)) d(i.j) = 2 and d(0, i) = for all i j [n) with i # j. The hypothesis class is composed of singletons over [ni) i..., H = (21,g) 1 [m]]. When the learner is deterministic, the environment can pick an agent (Ie, (c,,Ti,90 (t, ye) dependent on fc. ff is all ill-neeative, then the environment picks (I1, Te, re, (0, 1, +1), and then the learner makes mistake but no hypothesis can be eliminated. If ft predicts 0 by positive, the environment will pick (Ii, Tt, Vt)
(0, -1), and then the learner makes a mistake but no hypothesis can be eliminated, If Jt predicts some E [n] by positive, the environment will pick (xx, Ts, Vt) = (i,0, -1), and then the learner makes a mistake with only one hypothesis 21 21.g) - eliminated. Therefore, the learner will make n 1 mistakes.
7

---

In this work, we allow the learner to be randomized. When an (zg,re, 31) is generated by the environment, the learner can randomly pick an ft. and the environment does not know the realization of fe but knows the distribution where St comes from. It turns out that randomization does not help much. We prove that there exists an example in which any (possibly randomized) learner will incur ((H)) mistakes.
Theorem 3. There exists a. feature-ball manipulation set space Q and hypothesis class H. s.t. the mistake bound (x,,(r,A) 2 [74] 11. 1. For any (randomized) algorithm and any T N, there exists realizable sequence of (2t, Ft. Yt 1:T such that with probability least 1 - 6 (over randomness of T
A), A makes at least min( G/71] log( (1988)) [H] 1) mistakes.
Essentially, we design an adversarial environment such that the learner has a probability of [H]] of making a mistake at each round before identifying the target function h- The learner only gains information about the target function when a mistake made. The detailed proof is deferred to Appendix D Theorem Sannreemeestteee Bstablishhs a lower bound on the mistake bound, which is [H]] 1. However, achieving this bound requires a sufficiently large number of rounds, specifically = 52(17()) This raises the question of whether there exists learning algorithm that can make (T)) mistakes for any mistakes.
T < 1712. In Example 1 observed that the adversary can force any deterministic learner make | - mistakes in |92] 1 rounds. Consequently, no deterministic algorithm can achieve o(T)
To address this, we propose a randomized algorithm that closely resembles Algorithm with a modification in the selection of ft- Instead of using line we choose Si randomly from VS since we lack prior knowledge of zt. This algorithm can be viewed as variation of the well-known multiplicative weights method, applied exclusively during mistake rounds. For improved clarity, present this algorithm as Algorithmmjnn Appendix E due to space limitations.
Theorem 4. For any T E N, Algorithm 3 will make at most min( / / |log((H))) |H - 1) mistakes in expectation T rounds.
Note that the T-dependent upper bound in Theorem 4 matches the lower bound in Theorem up
to logarithmic factor when T= |7r/2_ This implies that approximately |²t]² rounds are needed to
achieve |H| - mistakes, which is a tight bound up to a logarithmic factor. Proof of Theorem is included in Appendix E
4.2.2 Results in the PAC Learning Model
In the PAC setting, the goal of the learner is to output a predictor fout after the repeated interactions. A common class of learning algorithms, which outputs a hypothesis fout H. is called proper. Proper learning algorithms are a common starting point when designing algorithms for new learning problems due their natural appeal and ability to achieve good performance, such as ERM in classic PAC learning. However, in the current setting, we show that proper learning algorithms do not work well and require sample size linear in [7]. The formal theorem is stated as follows and the proof is deferred to Appendix
Theorem There exists a feature-ball manipulation set space Q and hypothesis class H. s.s. SCT. (c, 3) = 2 ( where SCIPP 8) is the (e sample complexity achievable by proper algorithmns.
Theorem 5 implies that any algorithm capable of achieving sample complexity sub-linear in [H must be improper. As a result, we are inspired to devise an improper learning algorithm. Before presenting the algorithm, we introduce some notations. For two hypotheses h1 /22 let h1 V h2 denote the union of them, i.e., (h, V h2) = -1 iff. hy (z) = +1 or h2(x) = +1. Similarly, we can define the union hypotheses, f = //_ the positive region of f is the union of positive regions of the A hypotheses and thus, we have d(I,, f) = minjels d(x, h.). Therefore, we can decrease the distance between f and any feature vector x by increasing k. Based on this, devise a new randomized algorithm with improper output, described in Algorithm [
of more than two hypotheses. Then for any union
Theorem 6. For any feature-ball manipulation set space Q and hypothesis class H. we can achieve SCI.(a,)) (e, 6) 0 log" ((H)(()))))))))))) (174)+log)) Hog(1 (6) log()) by combining Algorithm with a standard confi- dence boosting technique. Note that the algorithm is improper.
8

---

Algorithm 2
1: Initialize the version space VS0 H.
2: for t I,..., do
3: randomly pick K4 Unif( Uni,(f,,2,2) 2,, ..... ()x where n, VV
4: sample kę hypotheses bi....,ha, ,k, independently and uniformly at random from VS,-
5: let ft v
6: if' Ur # yt and yr =+ then VS, VS,-1 {h e VS,_ild(z,,))) h) d(z fi)::
7: else if' Dt + yr and yt then VS, VS \ {h E VS--ild(z,, h) S d(zz, fi)::
8: else VS; VS,-
9: end for
randomly pick t from [T] and randomly sample h1, hg from VS,-1 with replacement.
11: output hı V h2
Now we outline the high-level ideas behind Algorithm In correct rounds where ft makes no mistake, the predictions of all hypotheses are either correct or unknown, and thus, it is hard to determine how make updates. In mistake rounds, we can always update the version space similar to what was done in Strategic Halving. To achieve poly-logarithmic dependency on [H], we aim to reduce significant number of misclassifying hypotheses in mistake rounds. The maximum number we can hope to reduce is constant fraction of the misclassifying hypotheses. We achieve this by randomly sampling a ft (lines 5 s.t. fo makes a mistake, and d(z;, fe) is greater (smaller) than the median of d( ft) for all misclassifying hypotheses h for true negative (positive) examples. However, due to the asymmetric nature of manipulation, which aims to be predicted as positive, the rate of negatives. To compensate
decreasing misclassifications over true positives is slower than for this asymmetry, we output a fous h2 V hı2 with two selected hypotheses h1, hz (lines 1O instead of single one increase the chance of positive prediction.
We prove that Algorithm can achieve small strategic loss in expectation as described in Lemma Then we can achieve the sample complexity in Theorem/6lb boosting Algorithm t strong learner. This is accomplished by running Algorithm 2 multiple times until we obtain a good predictor. The proof' of Lemma I and Theorem 6 are deferred to Appendix G
Lemma 1.
Let = (Ie, Tt, Vc ~ DJ denote the i..dd sampled agents in rounds and let A(S) denote the output of Algorithm interacting with S. For any feature-bal baal manipulation set space Q
320 ((Pl)) we have EAS [C*t (A(S))) S..
and hypothesis class H. when T
4.3 Settings (L,A) and ()
Online learning As mentioned in Section both the settings of A) and (J, are harder than the setting of (I, A)), all lower bounds in the setting of (1, (xr, A)) also hold in the former two settings. Therefore, by Theorem 3 we have MB 2 MB 2 (..,( = [H] - 1.
PAC learning In the setting of (1, A), Algorithm is not applicable anymore since the learner lacks observation of xt, making it impossible to replicate the version space update steps in lines 7 worth noting that both PAC learning algorithms we have discussed so far fall under general category called conservative algorithms, depend only on information from the mistake rounds. Specifically, an algorithm is said to be conservative if for any t, the predictor only depends on the history of mistake rounds up to I, i.e., T < with D- * yr. and the output fout only depends on the history of mistake rounds, i.e., (fe, Tt. Ut: At)es #u Any algorithm that goes beyond this category would need to utilize the information in correct rounds. As mentioned earlier, in correct rounds, the predictions of all hypotheses are either correct or unknown, which makes it challenging to determine how to make updates. For conservative algorithms, we present lower bound the sample complexity in the following theorem, which is ②( [H]]
and its proof is included in Appendix H The optimal sample complexity in the setting (1, A) is left as an open problem.
Theorem There exists a feature-ball manipulation set space and hypothesis class H. s.s. SCT. (e. = (((2)) [Hl), where SCI, 8) is (e, 8) the sample complexity achievable by conservative algorithms.

---

In the setting of (T, our problem reduces to best arm identification problem in stochastic bandits.
We prove lower bound on the sample complexity of {2( [H]] Theorem 8 by reduction to stochastic linear bandits and applying the tools from information theory. The proof is deferred to Appendix [
Theorem There exists a feature-ball manipulation set space and hypothesis class s.t.
SC1,1 5) = 02( [Hl]
Non-ball Manipulations
In this section, we move on to non-ball manipulations. In ball manipulations, for any feature vector r, we have ordering of hypotheses according to their distances æ, which helps to infer the predictions of some hypotheses without implementing them. However, in non-ball manipulations, we don't 'o have such structure anymore. Therefore, even the simplest setting observing 2t before fo and Ar we have the PAC sample complexity lower bounded by S2( [H
Theorem 9. There exists (C, }) = (2(1) )
mantuuuaianipllaiion set space Q and hypothesis class H. s.f.
The proof is deferred to Appendix D It is worth noting that in the construction of the proof, let all agents to have their original feature vector x O such that 2i does not provide any information. Since (ar, A) is the simplest setting and any mistake bound standard techniques (see Section A.2 for more details), we have the following corollary.
be converted to PAC bound via
Corollary 1. There exists a feature-manipulation sel space Q and hypothesis class H s.t. for all choices of (C, F), SCo.F(E, }) = M ( and MBC,F = 52(HH)).
Discussion and Open Problems
In this work, we investigate the mistake bound and sample complexity of strategic classification across multiple settings. Unlike prior work, assume that the manipulation is personalized and unknown to the learner, which makes the strategic classification problem more challenging. In the case of ball manipulations, when the original feature vector 2, revealed prior to choosing ft, the problem exhibits similar level of difficulty as the non-strategic setting (see Table for details). However, when the original feature vector 2; is not revealed beforehand, the problem becomes significantly more challenging. Specifically, any learner will experience a mistake bound that scales linearly with [HL). and any proper learner will face sample complexity that also scales linearly with [7]. In the case of non-ball manipulations, the situation worsens. Even in the simplest setting, where the original feature is observed before choosing and the manipulated feature is observed afterward, any learner will encounter linear mistake bound and sample complexity.
Besides the question of optimal sample complexity in the setting of (1, A) mentioned in Sec 4.3 there are some other fundamental open questions.
Combinatorial measure Throughout this work, our main focus on analyzing the dependency on the size of the hypothesis class [H| without assuming any specific structure of H. Just as VC dimension provides tight characterization for PAC learnaiility and Littlestone dimension characterizes online learnability. we are curious if there exists combinatorial measure that captures the essence of strategic classification in this context. In the proofs of the most lower bounds in this work, we consider hypothesis class to be singletons, in which both the VC dimension and Littlestone dimension are Therefore, they cannot be candidates to characterize learnability in the strategic setting.
Agnostic setting We primarily concentrate on the realizable setting in this work. However, inves- tigating the sample complexity and regret bounds in the agnostic setting would be an interesting avenue for future research.
Acknowledgements
This work was supported in part by the National Science Foundation under grant CCF-2212968, by the Simons Foundation under the Simons Collaboration the Theory of Algorithmic Fairness, by the
10

---

Defense Advanced Research Projects Agency under cooperative agreement HR00112020000 The views expressed this work do necessarlly reflect the position or the policy of the Govemment and no official endorsement should be inferred. Approved for public release; distribution is unlimited.
References
Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. (2021). The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 6-25.
Ahmadi, S., Beyhaghi, H.,, Blum, A., and Naggita, K. (2022). On classification of strategic agents who can both game and improve. arXiv preprint arX1v:2203.00124.
Ahmadi, S., Blum, A., and Yang. K. (2023). Fundamental bounds on online strategic classification. arXiv preprint arXiv: 12355.
Bechavod, Y., Ligett, K., Wu, S., and Ziani, J. (2021). Gaming helps! learning from strategic interactions natural dynamics. In International Conference on Artificial Intelligence and Statistics, pages 1234-1242. PMLR.
Brückner, M. and Scheffer, (2011). Stackellbegg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 547-555.
Chen, Y., Liu, Y., and Podimata, C. (2020). Learning strategy- aware linear classifiers. Advances in Neural Information Processing Systems, 33:15265--152 15276.
Dalvi, N., Domingos, P., Sanghai, S., and Verma, D. (2004). Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. pages 100.
Dong, J., Roth, A., Schutzman, 7.,, Waggoner, B., and Wu, Z. S. (2018). Strategic classification from revealed preferences. I Proceedings of the 2018 ACM Conference Economics and Computation, pages 55-70.
Gallant, S. I. (1986). Optimal linear discriminants. Eighth International Conference on Pattern Recognition, pages 849-852.
Haghtalab, N., Immorlica, N., Lucier, B., and Wang. J. (2020). Maximizing welfare with incentive- aware evaluation mechanisms. arXiv preprint 1r.iv:201100990
Haghtalab, N., Lykouris, T., Nietert, S., and Wei, A. (2022). Learning in stackelberg games with non-myopic agents. In Proceedingy of the 23rd ACM Conference on Economics and Computation, pages 917-918.
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. (2016). Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111-122.
Hu, L., Immorlica, N., and Vaughan, J. W. (2019). The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259-268.
Jagadeesan, M., Mendler-Dünner, C., and Hardt, M. (2021). Alternative microfoundations for strategic classification. In International Conference on Machine Learning, pages 4687-4697. PMLR.
Kleinberg, J. and Raghavan, M. (2020). How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23.
Lechner, T. and Urner, R. (2022). Learning losses for strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7337-7344.
Lechner, T., Urner, R., and Ben-David, (2023). Strategic classification with unknown user manipulations.

---

Milli. S., Miller, J., Dragan, A. D., and Hardt, M. (2019). The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 230-239.
Montasser, O., Hanneke, S., and Srebro, N. (2019), Vc classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pages 2512-25335 PMLR.
Rajaraman, N., Han, Y., Jiao, J., and Ramchandran, K. (2023). Beyond ucb: Statistical complexity and optimal algorithms for non-linear ridge bandits. arXiv preprint arXiv:2302.06025.
Sundaram, R., Vullikanti, A., Xu, H., and Yao, F. (2021). Pac-learning for strategic classification, In International Conference on Machine Learning, pages 9978-9988, PMLR.
Zhang, H. and Conitzer, (2021). lncentive-aware pac learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5797-5804.
Zmic, T., Mazumdar, E., Sastry, S., and Jordan, M. (2021). Who leads and who follows in strategic classification? Advances Neural Information Processing Systems, 34:15257-15269
12

---

A Technical Lemmas
A.1 Boosting expected guarantee to high probability guarantee
Consider any (possibly randomized) PAC learning algorithm A in strategic setting, which can output a predictor A(S) after T' steps of interaction with i.i.d. agents ~ D s.t. E (A())) < where the expectation is taken over both the randomness of S and the randomness of algorithm. One standard way in classic PAC learning of boosting the expected loss guarantee to high probability loss guarantee is: running A on new data S and verifying the loss of ((S) on validation data set, if the validation loss is low, outputting the current A(S), and repeating this process otherwise.
We will adopt this method to boost the confidence as well. The only difference in our strategic setting that we can not re-use validation data as are only allowed interact with the data through the interaction protocol. Our boosting scheme described in the following.
For round L.....R,
Run A for T steps of interactions obtain predictor h,-
Apply h, for the following me rounds obtain the empirical strategic loss on mo. denoted as 7, 1. - est (hr, (Ie, T's (t,)))) where 4, + is the starting time of these my rounds.
mno
Break and output h, if S 4s.
If for all r E [R], I, 4E, output an arbitrary hypothesis.
Lemma Given an algorithm A, which can output a predictor A(S) after T steps of interaction with i..d agents S ~ D s.t. the expected loss satisfies E ([cC((((S)) S e. Let h denote the output of the above boosting scheme given algorithm A as input. By setting R log and mo 3log (41g/)
25
we have L"r (ha) S 88 with probability 1 8. The total sample size R(T + mm) (log(()) log(1/8) }).
Proof. For all r I,..., R. we have E [L S By Markov's inequality, we have
Pr(c 28) - 2
For any fixed h,, if (St((h)) 2 8c, we will have 1, S 4e with probability S <e-mos; (hT) S 28, we will have T, < 4s with probability 2 1 - e 23 by Chernoff bound.
Let E denote the event of (3r E [R]. (h,) S 22} and F denote the event of (7, > 4e for all E [R). When F does not hold, boosting will output h, for some E [R].
Pr( 88)
< -F) (P(((E 8E(E, + Pr(-E)
Pr(E Pr(hA Ch, F Pr(-E)
<Re moc +e 23 +
2R
28,
by setting R log 2 and mo
(8 2
A.2 Converting mistake bound to PAC bound
In any setting of (C, F), if there is an algorithm A that can achieve the mistake bound of B, then we can convert A a conservative algorithm by not updating at correct rounds. The new algorithm can still achieve mistake bound of B as A still sees legal sequence of examples. Given any conservative online algorithm, we can convert to a PAC learning algorithm using the standard longest survivor technique (Gallant 1986).
13

---

Lemma 3. In any setting of (C, F), given any conservative algorithm A with mistake bound B, let algorithm A' run A and output the first ft which survives over log( B 8 examples. A' can achieve
sample complexity of O log( )
B the algorithm A will produce at most B Proof of Lemma When the sample size m 2 log( 8
different hypotheses and there must exist surviving for 1 log( ( rounds since i conservative algorithm with at most B mistakes. Let ......, fy denote these hypotheses and let &1. .1....,ff tg denote the time step they are produced. Then we have
.....,gg
Pr(fout = h4 and L (h+) E) <I (1 -)= 1og(4)
Pr(foot and (he) Eltr, 21.1,-1)
8
B
By union bound, we have
Prout))) (
>6) S
Pr (fout h2 and (mi > < 8. 21r
We are done.
A.3 Smooth the distribution
Lemma 4. For any two data distribution D1 and D2, let D3 = (1- p)D1 + pD2 be the mixture of them. For any setting of FC and any algorithm, let PD be the dynamics of (C(z1), fi, y1, Ir, F(11, Ai)..... C(IT), fT, yr, fr. Dr, F(ZT, AT)) under the data distribution D. Then for any event A. we have PD, (A) - PD, s 2pl.
Proof. Let B denote the event of all (I4, Ue, y being sampled from Dj. Then Prş(-B) S pT. Then
= (B)
-P,, (A)PP. ( (P,
= Pp, -
By re-arranging terms, have
(A) PD. (A)) (A), PD. (A) (-B)l (-B]) 2pl'.
B
Proof of Theorem i
Proof. When mistake occurs, there are two cases.
If ft misclassifies a true positive example (x,, rt, +1) by negative, we know that d(z fi) > re while the target hypothesis h" must satisfy that d(x,, h²) I r2. Then any h VS with d(z,, h) 2 d(zt: ft) cannot ht and are eliminated. Since d(z;, ft) the median of {d((,, hh E VS), we can eliminate half of the version space.
If ft misclassifies true negative example (Iz,
rt. 11) by positive, we know that d(z,, fi) < r. while the target hypothesis h" must satisfy that d(z;, h²) > r Then any h VS with d(x,, h) < d(z fi) cannot be h* and are eliminated. Since d(z,, is the median of {d(z,, h E VS), we can eliminate half of the version space.
Each mistake reduces the version space by half and thus, the algorithm of Strategic Halving suffers at most log, ((H!) mistakes.
D
14

---

C Proof of Theorem 2
Proof. In online learning setting, algorithm is conservative if it updates it's current predictor only when making a mistake. is straightforward to check that Strategic Halving is conservative. Combined with the technique of converting mistake bound to PAC bound in Lemma 3 we prove Theorem
D Proof of Theorem
Proof. Consider the feature space X' {0, e1, ei..... en, 0.9e1. 0.9e, where e; 's are standard basis vectors in R" and metric d(x, x²) ) = | - x' x'112 for all x, x' E X. Let the hypothesis class be a
set of singletons over {e,li E [n]]. i... H = {21 (e,) 1/i e [n]]. We divide all possible hypotheses (not necessarily in H) into three categories:
The hypothesis 21g- 1, which predicts all negative.
For each æ E {0, 00,.,...........,,,, let Fa,+ denote the class of hypotheses h predicting x positive.
For each [n]. let F; denote the class of hypotheses h satisfying h(z) -1 for all x E (0,0.9e)..... 0.9e,, and h(e,) = +1. And let F. = Uee[ F, denote the union of them.
Note that all hypotheses over X' fall into one of the three categories.
Now we consider a set of adversaries E En, such that the target function in the adversarial environment E; is 21l (c.) 1. We allow the learners be randomized and thus, round t, the learner draws an J, from a distribution D(f;) over hypotheses. The adversary. who only knows the distribution ((f:) but not the realization fo picks an agent (It, Tt, yr) in the following way.
Case I; If there exists x E {0, 0.9ei,......... 0.9e,,,,,).))) 0.9e,) } such that Pro.-D(t) f E F2.+) 2 c for some > O, then for all j E [n), the adversary Eg picks Pee,Te.0 = (x, 0, -1). Let BI. denote the event of ft E F2,+.
In this case, the learner will make mistake with probability c. Since for all h H. h(A(x, h, 0)) = h(x)= = 1, they are all consistent with (z, -1).
Case 2: Pr Pr (f: 21l 1) 2 c, then for all j E [n:. the adversary Ej picks
(æt, Ft, Me) = (0, 1, +1). Let BiJ denote the event of ft = 21g -
In this case, with probability c, the learner will sample a ft 21, and misclassify (0, +1). Since for all h E H. MA h, 1)) +1, they are all consistent with
(0, +1).
Case If the above cases do not hold, let i, arg max Pr(S((e.) - 11ʃe P.). 2, 0.9e,, For radius and label, different adversaries set them differently. Adversary E, will set (ri, y/) = (0, -1) while other F, for j * i will set (rt, vt) = (0.1, -1). Since Cases and 2 do not hold, we have Proi~Du,(ft F.) 2 (n 2)c. Let Bý. denote the event of ft F. and B3,, denote the event of Ft.
(a) With probability Pr(B,,)) n PT(B))) 1-(n+2)c the learner samples a fe n F.,, and thus misclassifies (0.9c;, ,,1,,,,,,,,1111 in E, for j + is but correctly classifies (0.9e,, O, 1).. In this case, the learner observes the same feedback in all E, for j & in and identifies the target function 21 (e:,)
in E,,-
(b) If the learner samples a fa with fe(o;,) ) = ft (0.9c;, = 11 then the learner observes in all E, for j [m]. Therefore the learner cannot
It = 0.9c,,, J/2 = and 0. distinguish between adversaries in this case.
(c) If the learner samples a fe with (0.99e;;
+1, then the learner observes x, = 0.9es,, Vt and T. = +1 in all F, for j E [n]. Again, since the feedback are identical in all E, and the learner cannot distinguish between ad adversaries in this case.
15

---

For any learning algorithm A, his predictions are identical in all of adversarial environments {Eşli [n]} before he makes a mistake in Case 3(a) in one environment E His predictions the following rounds are identical in all of adversarial environments {Egl [n]] (Ei, before he makes another mistake Case 3(a). Suppose that we run A in all adversarial environment of [Fyl E [n]] simultaneously. Note that once we make mistake, the mistake must occur simultaneously in at least n 1 environments. Specifically, if we make a mistake in Case 1, or 3(c), such mistake simultaneously occur in all environments. If we make mistake in Case 3(a), such mistake
simultaneously occur in n environments except E., Since we will make mistake with probability
at least min 1=(++2)e) at each round, there exists one environment in {Fgli [n]} in which A n will make n mistakes.
Now we lower bound the number of mistakes dependent on T. Let & 12,... denote the time steps in which we makes mistake. Let to for convenience. Now we prove that
4-1+t
Pr(t, > 4-11 k|(;-1)=
II
Pr(we don't 't make a mistake in round r)
+=4-1+1
1+b
(1(Case 3 at round 7) 1- 1-(n 2)c,
II
+ (Case I or 2 at round r) -c)
r=4--+1
(n + 2)c
1
<(1 -min(
.c))* S (11 2(n + 2)
n
by setting c 2[m+2]
Then by letting k = 2(n 2) In In(n/8), we have
Pr(4 > 4-11 + 11/4-1) S 8/n.
For any T,
T
Pr(# of mistakes < min(
4: + n 1))
Pr(Bic e In 1],t; t,-1 > k:)
Pr(l: - 4-11 > k) 5.
Therefore, we have proved that for any T. with probability at least - 6, we will make at least min( T ln(1/8((1 n mistakes.
E Proof of Theorem
Algorithm 3 MWMR (Multiplicatiive Weights on Mistake Rounds)
1: Initialize the version space VS H.
2: for := do
3: Pick one hypotheses ft from VS uniformly at random.
4: if Ut F ye and 1/+ + then
5:
VS < VS {h E VS|d(r,, h) 2 d(x, f() 6: else if V: + yt and ye then
7: VS < VS {h E VSId(zr,)) < d(z,. {t)).
8: end if
9:
end for
Proof. First, when the algorithm makes mistake round he least eliminate f.. Therefore, the total number of mistakes will be upper bounded by [7[] - 1.
Let Pt denote the fraction of hypotheses misclassifying zt. We say hypothesis h is inconsistent
with (It, Je, yt, De) iff (d(x;, h) 2 d(x,, ft) A Dt A ye = +) or (d(x,, h) S d(z,, fi) A T.
+ A yt -). Then we define the following events.
16

---

E denotes the event that MWMR makes mistake at round t. We have Pr(E;) Pc-
Br denotes the event that at least fh fraction of hypotheses are inconsistent with
(Te, Jt, Mr. D.). We have Pr(B, 2
Let [l| denote the cardinality of hypothesis class and n, denote the number of hypotheses in VS after round f. Then we have
T
5 nr mT= = II (BE) ").
By taking logarithm of both sides, we have
S In(or) = In(n) + Σ In(1 - ((E))(B))(BB)))) (h) In(n) Σ (EE))(BB)) Pt
where the last inequality adopts In(1 x) s - r for x [0, 1). Then by taking expectation both sides, have
T
0 < In(n))
Σ
Pr(E,ABi)
E=1
Since Pr(Ee) = pt and Pr(B.]E.) 2.2 then have
P s In(n).
Then we have the expected number of mistakes E. [Manwmn(T) as
T
(MMMMR(T)) Σ
Pt
S
Σ
oi VT 4ln(n)T
t=1
where the first inequality applies Cauchy-Schwarz inequality.
F
Proof of Theorem 5
Proof. Construction of Q, H and a set of realizable distributions
Let feature space X' = {0, e ei....,,e.! e U Xo, where Xo = 1 a E S,} with = V (n 1)a for some small a 0.1. Here S, the set of all permutations over n elements. So Xo is the set of points whose coordinates are permutation of {0, 1/,1/2,..., (n
1)/2} and all points in X, have the lg norm equal a. Define metric
d by letting 22) = || æ2l1, for all 21, 22 E X. Then for any E Xo and
E [n]. d(z, e;) = || e; = (c: 1)2 43 / V /1+2; ビドー 23 2x;
vI a² 2xg Note that we consider space (X' d) rather than (IR", 11.112)
Let the hypothesis class be a of singletons over {eili E [n]]] i.c. H (21 1/i [n]].
We now define collection of distributions {D,li [m|]] in which D; is realized by 21l (e:) 1. For any [n]. D; puts probability mass - 3ne on (0, 0, -1). For the remaining 3ne
probability mass, D, picks x uniformly at random from X, and label it as positive. If
set radius rxx) = Tu == /1 + a²: otherwise, set radius r rxx) = ri == / 11+ a² 2 4 Hence, Xo are all labeled as positive. For
hy (e,} labels {x Xol2; = 0) negative since r(x) ry and d(x, h2y ra > r(x). Therefore, (h,)
1 "
3ng 3e.
To output fout H. must identify the true target function.
17

---

Information gain from different choices of ft Let h- = 21 (e,.) -1 denote the target function.
Since (0, 0, -1) is realized by all hypotheses, we can only gain information about the target function
when 2y E Xo. For any 24 E Xo, if d( fi) S ri or d( fi) > Tu. we cannot learn anything about the target function. In particular, if d(z,, ft) S rt, the learner will observe I; ~ (nif( ytr = +1, Di +1 in all {Diji [n]]. If d(z,, fc) > Ta the learner will observe I₁ (Xi). y/ = +1,
V/ = -1 in all (Dalé E [n]]. Therefore, we cannot obtain any information about the target function.
Now for any 2, E Xu, with the 4-tth coordinate being O, we enumerate the distance between and x' for all x' EX
For all x' E Xu, d(z, x') S ||:||| + ||>'|| s 2a < ng
For all j + in e,),,,) = / a² - 20,- S r
d(r, Cx,) = Tu:
d(x, 0) = a < v1-
Only f = 21 {e,,} } satisfies that < d( f() S Tu and thus, we can only obtain information
when ft = 21 (e,,) } 1. And the only information we learn is whether i, - because if i # i", no matter which i* is, our observation is identical. If i, + i", we can eliminate ( - 1.
Sample size analysis For any algorithm A, his predictions are identical in all environments (D. e [n]} before round in which ft 21 (e.,} 1. Then either he learns i, in Dr, he eliminates 21 ) 1 and continues perform the same in the other environments {Dili o i.). Suppose that we run A in all stochastic environments {D,lé [n]} simultaneously. When we identify is in environment Di,; we terminate A in Di,, Consider good algorithm A which can identify i in D) with probability y after ''' rounds of interaction for each i [n]. that is,
Pr (Jout * +i) s 8' DinA
e [n].
(3)
Therefore, we have
Σ Pr Dund EE(A)
(ront (oout # +1) S
Let nr denote the number of environments that have been terminated by the end of round T. Let
B, denote the event of Ir being in Xo and C2 denote the event of fe = 21 (e.,) - 1. Then we have
Pr(Bi) 3ns and Pr(C, B₂) 1, and thus Pr(B, A C.) 3næ 1. Since at each round, we can climinate one environment only when B, A C2 is true, then we have
n.
"
T
E [nrl= S E
Σ 1(B,AC) = T 3ng 3=T.
Therefore, by setting T'
and Markov's inequality, we have
65
Pr(nt 2
n -
3=T -1 2
When there are [?] + environments remaining, the algorithm has to pick one iout, which fails in at least [ of the environments. Then we have
Σ Pr (tout # i) D.AA
72 Pr(nt <
12 1) 2 n / _2_
2
2
AE[m]
which conflicts with Eq 4 Therefore, for any algorithm A, to achieve Eq 3 it requires T >
18

---

G Proof of Theorem
Given Lemma T we can upper bound the expected strategic loss, then we can boost the confidence of the algorithm through the scheme in Section A.1 Theorem O follows by combining Lemma T and Lemma 2
Now we only need to prove Lemma
Proof of Lemmal /
For any set of hypotheses H, for every = (I, v), we define
ky 2) = [1 H)))( =-H y
00
otherwise.
So (p, is the number of hypotheses mislabeling z for positive 2'8 and 0 for negative z's. Similarly, define Kn follows,
[hh E HIM(A(,,)))) + ify y-
Ke H, 2) =
0
otherwise.
So Ki, (H, is the number of hypotheses mislabeling = for negative z's and for positive ='s. In the following, is constructed by randomly sampling two hypotheses with replacement and taking the union of them. We represent the loss of such random predictor using Kp (HH, and (n, defined above. Then we show that whenever the algorithm makes a mistake, with some probability, we can reduce (y(SS, 1.21)
divide the proof into two parts. First, recall that in Algorithm 2 the output
Ka (1.)) hypotheses and utilize this to provide guarantee on the loss of the final
output.
Upper bounds the strategic loss positive rate and false negative rate of respectively. Let p+ denote the probability of drawing positive sample from D, i.e., Pr(a.rg))D(( negative sample from D. Let D+ and D_ denote the data distribution conditional on that the label positive and that the label is negative respectively. Given any set of hypotheses H, we define random predictor H2 = h1 V h2 with f1, h2 randomly picked from H with replacement. For true positive 2, (H) will misclassify it with probability (=( negative rate of R2(H)
For any hypothesis h, let fpr(h) and fnr(h) denote the false
+) and p- denote the probability of drawing
Then we can find that the false [8]
Kip (p, 2)2
(nr(R((H)) B==(zn)) (H)( -)] Ex-(e)))
|H
Similarly, for true negative R2(H) will misclassify it with probability 2x., (B.=), Then the false positive rate of R2(H) is
(1
Kn (H. )2 H
HI
2k (H H
fpr(R2(H)) E (Br, (P)( = +)] S (x.
Hence the loss of R2(H) is
Ri 2)2 |112
2k, (H, 2)
L (R2()()) p+ EtWDD
+ t_-EeDD
Kip (1, 2)2
+ Kin (H,
EB~D
(5)
H
H
where the last equality holds since Kip (H, 0 for true negatives and K,, (H, z) = 0 for true positives.
Loss analysis In each round, the data o, (I,, we is sampled from D. When the label y is posi- tive, the drawn fo satisfying that 1) (A(Arr ftr r:)) = and 2) d(x,, ft) S median ((d(a, h) VS,-1, ((A, rc)) -},, then are able to remove Kr, (V) 2
hypotheses from the version
19

---

space. Let Ep,t denote the event of ft satisfying the conditions 1) and 2). With probability [mgg]
sample he 1. Then we sample
Unir(VS With probability 6p(VS the
2n
sampled fo satisfies the two conditions. So we have
Kp (V(
Pr(Ep,lZee VS 1og2(n))
(6)
2n
The case of y/ being negative is similar to the positive case. Let En,t denote the event of fr satisfying
that 1) (a(A(, re)) = + and 2) d(æ, ft) Z median( (d(ar, (aaiann((((a h)]h E VS,-1, ( h, rz))
+1). If Kn (VS 2 81 then with probability [Iogg(n.)]'
sample he 1. Then with
probability greater than 1 we will sample an ft satisfying that 1) fe(A(zt, ft, + and 2) d(z,, ft) 2 median [d(z,,))l E VS,-1, (()(2,, r() +}). K. (VS 1) < nu then
with probability [Toga[m]]] we sampled ky satisfying
74
Kr S
4km, (V
2n (VS
Then we randomly sample ke hypotheses and the expected number of sampled hypotheses which mislabel 2, is kę (x(( E (2, 2. Let Ir (given the above fixed k2) denote the number of
sampled hypotheses which mislabel x; and we have [gd] (1. by positive. We have
1. When Ir > 0, fc will misclassify
Pr(g: 0) (1 Kn (VS <
Kin Nn (VS,- 1, ze)
VVB-VVE-110 S0-1/4 < 0.78
74
f2
and by Markov's incquality, we have
E 19
1
Pr(gi 3)
0.17. 6
<
3
Thus Pr(ge E (1, 0.05. Conditional on dr is either 2, with probability 2 4. all of these Ie hypotheses ht' satisfies d(I,, ht) 2 median((d(a) h)]h E VS,,1, (,,,,,, r,), +}), which implies that d( ft) 2 median ((d(r,, h)lh E 1S,-1,h(A(ee h r.)) = +)). Therefore, we have
Pr(En,l VS.-1) 2
80 101zz2(1)) (n+)
Let ey denote the fraction of hypotheses we eliminated at round t, i.e., 1/
Dr-1
Then we have
Kp (V, + ((E,,)
Kin (VS, (, 2e)
U2 2 (Ep.))
(8)
2n
2n
Since n4+11 ne(1 v,), have
1 S OT+1
v4)
1=1
By taking logarithm of both sides, we have
T
T Inn
< I1nr41 Inn Σ
In(1 - vx)
Σ
Ut
where we use In(1 - x²) for x E [0, 1) in the last inequality. By re-arranging terms, have
Σ S Inn.
Combined with Eq 8
we have
r
Kip(VS 2+)
Knn (VSx-1,22) 21)
((Ex))
+ 1(Er,))
S Inn.
2n,
2n
20

---

By taking expectation w.r.t the randomness of fI.T and dataset S = 21:T on both sides, we have
Σ
T
(Fpp,.)
Hpp (V((VS-11,)) + 1 ((En,)) Kn ())
S Innn
2n,
2n,
Since the t-th term does depend on fI41:; #+11: and VS,-1 is determined by 21:-11 and fist-1. the f-th term becomes
Kpp (V(
Kn (VS.-1,
E Pi
((p.e)
+ ((Ennt
2nd
2nd
E₁. ((p,,) Rpp (V) 21)
Kn (VS,-1,2)) 21)
=E f11-1.511
+ 1(En,))
f1:1-1, 21: Zid
2n
2n
Kpl (V
Kn 1, =t)
= -E fra-1.F11
Ei (1(p,,))
11:1-1, 21:1
+ Esg (1
2n
2n
(9)
(V 21)
Kin Knn (VS
>B f (me)
(10)
4ng
80 loga (ne)
2nee
where Eq 9 holds due that VS.- determined by fi:t-1, 21:t-11 and does not depend on f
and Eq 10) holds since fry, (Ep f1--1, = Pry. (Ep,) VS 2x) 2 (ogg
(VS.-..))) by
2n,
Eq (6) and Pry, (Fm,elfit-3) 21x) pry, (Fn,t) VS,-1, 2 801ogg(n1) by Eq 7 Thus, we have
x² (V
KnnSS (VS 2e)
Σ B
S Inn.
log2(1e) (Tt)
4n
80 log2(T))
2n
Since 2, D and 2 is independent of 21:-1 and f12-1, thus, we have the t-th term on the LHS being
1
x2 (V
1
Kn (VS;-1, 2c)
fa 1i8a
(ogg(ne)
4n
80 logg (n+)
2n1,
kip (V
Kin (VS 2x)
= -B
BENDD
logg(n4)
4n
80 80
2n,
No (VS 2)
2km ( (VS 2)
2
E B1a-11 320 (ng2(n)
E
+
n
n4
E E
(R2(VS
320 log.
where the last inequality adopts Eq 5
By summing them up and re-arranging terms, we have
1 T
T
320 log, (n) In(n)
Bfer Bi
CH (R2(VSS))))
Σ 1=1
E
[ (R2(VS)))))) < T
T
T
1=1
For the output Algorithm which randomly picks T from [T], randomly samples h1 h2 from VS,-1 with replacement and outputs hy V h2, the expected loss is
E ((CT(((S)) (A(S)) -Es.fir
Un (1r v h2))
T
2 (12((V))))))
fi.r
T
320 log, (n) In(n))
<e.
T
when T
320 (n) In(n)
21

---

Post proof discussion of Lemma]
Upon first inspection, readers might perceive a resemblance between the proof of the loss analysis section and the standard proof of converting regret bound error bound, This standard proof converts regret guarantee on fI:r to an error guarantee of 7 E ft- However, in this proof, the predictor employed in each round is ft, while the output is an average over R2( for all E [T). Our algorithm does not provide regret guarantee on f1.T.
Please note that analysis exhibits asymmetry regarding losses on true positives and true negatives. Specifically, the probability of identifying and reducing half of the misclassifying hypotheses
positives, denoted Pr( F.p. 1pp.122 22, VS,-1 (Eq (6)) is lower than the corresponding probability for true negatives, Pr( (n,,,,lz,, 1)) (Eq 77). This discrepancy arises due the different levels of difficulty detecting misclassifying hypotheses. For example, if there is exactly one hypothesis / misclassifying true positive = (æx, Tt, Hr). it very hard detect this h. We must select fa satisfying that d(x,, fi) d(I,, h') for all h E H \ } (hence ft will make a mistake), and that d(Iz, ft) S d( h) (so that we will know misclassifies 24). Algorithm 2 controls the distance d(z,, ft) through k,, which is the number of hypotheses in the union. In this case, we can only detect h when be = 1 and f. h, which occurs with probability m. log(n))
However, if there is exactly one hypothesis h misclassifying a true negative 2, = (xt, Tt. Mt). we have that d( h) mingeR ((r),,")) Then by setting ft Vheæth which will makes a mistake and tells us h is a misclassifying hypothesis. Our algorithm will pick such
f. with probability Tog(ns))
H Proof of Theorem 7
Proof. We will prove Theorem 7 by constructing an instance of Q and H. and showing that for any conservative learning algorithm, there exists realizable data distribution s.t. achieving loss requires least ② [Hl) samples.
Construction of Q, and set of realizable distributions
Let the input metric space (X',) d) be constructed in the following way. Consider the feature space X fei..... e Xo, where Xo -000..... lo E S, with
vPt...tee-11 for some small = 0.1. Here Sn is the set of all permutations over elements. So X, the set of points whose coordinates are permutation of {0, 1/2,..., (n- 1)/2} and all points in Xp have the &g norm equal to a. We define the metric d by restricting l distance X, i.e., d(æ1, 222) || x2 l2 for all 21, 22 E X. Then we have that for any x E Xo and E [n], the distance between and e; is
d(z,e,, --1--eell = (I. 1)2
Σ J
2x,
V1 d²
224
j7i
which is greater than /1 a2 2a
0.8
For any two points x, xf E Xo- 2a.
d(x, S 2a by triangle inequality.
Let the hypothesis class be a set of singletons over {eili E [n]], i... H (21 1/i [n]].
We now define collection of distributions {D.li E [n|] in which D; is realized by 211 (e, -1. For any i E [n], we define D; in the following way. Let the marginal distribution Dx over X' be uniform over Xo- For any x, the label y is + with probability 1 6e and with probability 65, i.e., D(ylar = Rad(1 - 6e). Note that the marginal distribution Dexx = (Xo) Rad(1 6ε) identical for any distribution in (D.lé E [m]} and does not depend on
22

---

If the label is positive y = + then let the radius r = 2. If the label is negative y = then let
v1+ a² - 2(z; + ( which guarantees that can be manipulated e iff c( eạ) <
c() for all E [n]. Since 2; I and S a, we have / + a² 2(x; + !) 2
v1 -1-4a 4a 2x. Therefore, for both positive and negative examples, we have radius strictly greater than 2a in both cases.
Randomization and improperness of the output fout do not help Note that algorithms allowed to output randomized fout and to output fout $ H. We will show that randomization and impropemess of fout don't make the problem easier. That is, supposing that the data distribution D:- for some i" E [n], finding a (possibly randomized and improper) fout is not easier than identifying i". Since our feature space X is finite, we can enumerate all hypotheses not equal to 21 {
1 and calculate their strategic population loss as follows.
21g 1 predicts all negative and thus (21, - 1) 1
For any X' s.t. a a Xo 0, 21, will predict any point drawn from D;- as positive (since all points have radius greater than 20 and the distance between any two points in Xo is smaller than 20) and thus (21.. 1) 68:
For any C fei,.... ) satisfying that 3i + i", C, a, have nd -) 3c. This is due to that when y = -, x is chosen from (ni and the probability of d(x c,) < d(z, ex-) ) is 2. When d(æ, es) < d(x, es- 21. will predict as positive.
Under distribution Di-, we are able to find a (possibly randomized) Sout with strategic loss of L (Jant) S E, then we have L (fout)
Ba- [fSH (h)) 2 Pri--fou (h + 21 [e:-} 1003-111 1) 3e. Thus, Pra (h- ( - 1) 2 2 Hence, if we are able find (possibly randomized) fout with e error, then we are able to identify i" by checking which realization of fout has probability greater than 2. In the following, we will focus on the sample complexity to identify i" Let fout. denote the algorithm's answer to question "what i*?"
Conservative algorithms When running conservative algorithm, the rule of choosing fi at round t and choosing the final output fout does not depend on the correct rounds, i.e. f E [ = Vr). Let's define
Dt + yt if Dc = yc
A
(11)
where I is just symbol representing "no information". Then for any conservative algorithm, the selected predictor ft is determined by (fr, Ur, for T < I and the final output fout is determined by (Se, Dr, Ut, AD) From now on, we consider A as the feedback in the learning process of a conservative algorithm since it make no difference from running the same algorithm with feedback ,-
Smooth the data distribution For technical reasons (appearing later in the analysis), we don't 't want to analyze distribution (Dali E [n]} directly the probability of A, c; is when fc(),) +1 under distribution D;. Instead, we consider the mixture of D; and another distribution DV, which is identical D; except that r(x) d(x,, ex) when y D)D; + DD' with some extremely small p. where D marginal distribution over X' x y is still (Xo) Rad(1 6ε); the radius is r = 2 when y +. and the radius is r = d(z, e,) when - For any data distribution D, let PD be the dynamics of (f1, L1. A,... fr. yr, Dr, A/r under D. According to Lemma 4 by setting p- = á when T < E'
More specifically, let Dj (1
n with high probability we never
sample from DV and have that for any i,j [m]
1
Pd. (tout = 5) P PDy (fout 5) S g
(12)
From now on, we only consider distribution D' instead of D: The readers might have the question that why not using D' for construction directly. This because D' does not satisfy realizability and no hypothesis has zero loss under D/.
23

---

Information gain from different choices of ft In each round of interaction, the learner picks predictor fi, which can be out of H. Here we enumerate all choices of fr.
f4(-) 21g predicts all points in X' by negative, No matter what 1 is, we will observe (A: = Te, Vt) ~ Unif(XX) Rad(1 - 6ε) and T/ = They are identically distributed for all 1" [n], and thus, A also identically distributed. We cannot tell any information of i* from this round.
s.t. ft = 21. 1 for some C s.t. a X # H. Then A, = A(z,, fr, r2) = (3x,, ft. 2a)
since Ti > 2a and d(It; S 2cx, D1 + yt Rad(1 6e). None of these depends on i" and again, the distribution of (it. Vt. A/) is identical for all i" and we cannot tell any information
from this round.
ft = 21. 1 for some non-empty a C {ee,.... e. For rounds with 3/+ = +. we have D/ + and A, (z fa, 2), which still not depend on i* Thus cannot learn any information about i". But we can learn when y - For rounds with y/ = - if A E dg. then we could observe &t and A Ad, which at least tells that (A.) 1 is not the target function (with high probability); if A. & az, then Dt- and observe A =1.
Therefore, we only need to focus on the rounds with S. = 21 a, - for some non-empty d, C (ei...., ] and 1/+ = - worth noting that drawing an example x from X, uniformly, is equivalent to uniformly drawing permutation of H such that the distances between æ and h over all h E H are permuted according to it. Then A, = o, iff e, E a,, d(x, e2) S d(x, e,-) and d(x, e,) s d(x, ei) for all e, ag Let & = |ayl denote the cardinality of a, In such rounds, under distribution D/.,, the distribution of A are described as follows.
1. The case of ei E ae For all j E at \ { with probability +.2 d(Iz, ej) = mineyea, d( et) and thus, A = A. = ej and DI = (mistake round). With prob- mine,ea, d(x,, et). If the example is drawn from Dj., we have A 24 and y/ (correct round), thus A =L. If the example is drawn from D.,,, we have we have A; A. e,- and 3/2 = + (mistake round). Therefore, according to the definition of A (Eq
ability 1, we have d(z,, k.
have
1 for E a.ji w.p. E.
ej
A
e
w.p. k, P
w.p. k (1 (1
We denote this distribution by Pe((a,i"):
2. The case of e,- & ae: For all j E a, with probability K. then d(z,, e,) = mine; Ea.U(e.)) d(z,, e,) and thus, A, = c, and T. = + (mistake round). With proba- bility k,+T. we have d(z, e;,) < minerea. d(r, e,) and thus, A, = It. D: (correct round), and A; =1. Therefore, the distribution of A is
A ej
W.P. KTTT
for e, E a
w.p. ket1
We denote this distribution by (a))
To measure the information obtained from A/. we will utilize the KL divergence of the distribution of A under the data distribution D,- from that under a benchmark distribution. Let D n Eien D denote the average distribution. The process of sampling from D is equivalent to sampling i* uniformly at random from [n]] first and drawing a sample from D... Then under D, for any e, E az we have
Pr(A/ = e,) =Pr(i" = P) =yili* = =)) Pr(i" a PT)) = =e,li" E a (i))
PPr(i" a.) Pr(A// e,li" $ a.)
24

---

1
p
K: 1
1
nke 1 + p(ke + 1)
11
kit
11
kt
li +
nkk((ke + 1)
and
Pr(A) =1) Pr(i" E at)
Pr(A/
=1 jia ac) Pr(ii & a.) Pr(A/ =1 100 (
ht
1
n h4 n + 1 p(h +1)
ke 1
n (k + 1)
Thus, the distribution of A under D is
-k-1++p((+t)) for e, E (1x
w.p.
A
w.p. m(++1)
We denote this distribution by P(a)). Next we will compute the KL divergences of Pe i*) and Pg (ax) from P(az). We will use the inequality log(1 + S x for z 2 On the following calculation. For any i s.t. ei E ac, we have
DEL P( i²))
=(ke - -1 nkki - + p(kit + 11
log( nk: 1 p(kk + +1 ks)
nke (rr +1)
nkie (k: + 1)
nk, - + p((k + 1)
log( nk: 1 - p + 1)
Kr
nkie (Ait + 1)
nike (kg + 1)
+ n + p(ke + 1)
+
p(kk + 1)
ki
log(
n2ke + 1)
nike + 1)
1 - p
1
1
2p
1
2p
<0
log(
+
log(
-)
+
(13)
h;
p
Ri +
k +
p
1: +
and
DKL (k(a)))))lPP
ki nkk - + pike + 1)
log( nke - 1 + p(kkp +
(Ki 1))
nke (kg
nk: (k: + 1)
n + p(ki + 1)
log n n p(ks + 1)
+
(Ks + 1))
nike 1)
n(ke + 1)
n +
+1
<0
(14)
n (k +1) 1)
n² (kc +1
Lower bound of the information We utilize the information theoretical framework of proving lower bounds for linear bandits (Theorem 11 by Rajaraman et al. (2023) here. For notation simplicity, for all i E [m]. let P, denote the dynamics of (f1, A, V1, "r,..., A4. yr. Fr) under D' and P denote the dynamics under DD Let B, denote the event of {fe = -21,, - for some non-empty a, C (ei...., en As discussed before, for any a, conditional on -B, or yr +1, (A/, yt, De) identical in all (Dili [n]), and therefore, also identical in D. We can only obtain information rounds when B, A (ye- = 1) occurs. In such rounds, we know that ft is fully determined by history
(possibly with external randomness, which does not depend data distribution), y1 -1 and ūr is fully determined by A; (ūe = +1 iff. A E at).
Therefore, conditional the history H,-1 = (f1, A1, 11, DI............ . Ai-1, Wt-11 1, 11-1) before time t, we have
DKL V.
Me, 1.ll(-1))
=P(B, A (Bt = (e.P(B.))K((((A/// B, (vr - - B, ^ (yr -1)))
(vr = - (y== -1))
(15)
where the last equality holds due to that y1 Rad(1 - 6E) and does not depend on B,.
25

---

For any algorithm that can successfully identify i under the data distribution D; with probability 3
for all E [n], then PD, (dout i) 2/2 and PD, (Fout i) S 1 for all j * i. Recall that D; and D) are very close when the mixture parameter p is small. Combining with Eq (2). we have
(fout = 2) - P = =i]
2 Pd. (Jout = - PDy (Jout = i) - PP,, (fout = i) Pi =1] - PD, (bout = i) - -Py = 6)
1 1
2 4
Then we have the total variation distance between P; P,
TV)P,,P)) (fout = Py(tout = =i]l
(16)
Then we have
(nff((
T (P,. P ((+1) mad n)] S (nit(i)(())) [TV2 P)]
<2E;
(PIPP)
(Pinsker's ineq)
-26,
(KL(P( Ve M. A Mc. Dillle-11)
(Chain rule)
t=1
12elE,
PIB.)DK - (yr -1))
(Apply Eq 15
12c
11
P(B.)
DEL (P Be (v) (1)I) Br (vr = =1))
n
12g
E
Σ ((B))
Σ
DKa(((aa)IPP((a.))))
Σ
Daa(P(a))PPP(aa)))
n
fiiEa
iniaa
12g
log
1
2p
+ Σ
n +
T1
FUTT
kt +
p
hi + 1
n2 + 1)
kiEa,
(Apply Eq (33
12c
(log(- 1
2p 1) p
(2og'(Io /E) 2)
n
Combining with Eq 16 we have that there exists a universal constant e such that 7 >
en
Zlog(nn/e)
I Proof of Theorem g
Proof. We will prove Theorem 8 by constructing an instance of Q and H. and then reduce it to linear stochastic bandit problem.
Construction of Q. H. and a set of realizable distributions
Consider the input metric space in the shape of star, where X {0, 1,...,n) n) and the distance function of d(0, i) = and d(i..) = 2 for all i + E [n].
Let the hypothesis class be set of singletons over in., i.c. H (21 1/i E [m]].
26

---

We define a collection of distributions {D,li E [n]] in which D; is realized by 21l (1) 1.
The data distribution D: put 1 3(n 1)s on (0, 10)1+ and 3a on (i, 1, for all # i". Hence, note that all distributions in {D,li [n]] share the same distribution support ((0,1,+) U [ii, 1) E [<]]] but have different weights.
Randomization and improperness of the output Sout do not help. Note that algorithms are allowed to output randomized fout and to output fout & H. We will show that randomization and impropemess of fout don't make the problem easier. Supposing that the data distribution is Di- for some i" E [ra], finding (possibly randomized and improper) fout is not easier than identifying t". Since our feature space X' is finite, we can enumerate all hypotheses not equal to 21 (x) - and calculate their strategic population loss follows. The hypothesis 21g will predict all by negative and thus (21, 1) predict all points in the distribution support by positive and thus incurs strategic loss 3(n - 1)e. For any hypothesis predicting 0 by negative and some i + i" by positive, then it will misclassify (i, -)) and incur strategic loss 3e. Therefore, for any hypothesis + 21 (+-}
3 - 1)c. For any hypothesis predicting 0 by positive, it will
have CB, (h) 2 3s.
Similar to the proof of Theorem 7 under distribution D,., if we are able to find a (possibly random- ized) fout with strategic loss (ffut)))) S e. Then Pri (h 21 (i-) 1) 2 3. We can identify i" by checking which realization of four has probability greater than 3 In the following, we will focus on the sample complexity to identify the target function 21 (x*) 1 or simply i". Let iout. denote the algorithm's 's answer to question of "what is 2"?"
Smooth the data distribution For technical reasons (appearing later in the analysis), we don't want to analyze distribution (D.lé E [n]] directly as the probability of (i, 1.-) is under distribution D,- Instead, for each i E [mi] let D' (1 p)D; + pD) be the mixture of D; and DJ" for some small p. where D. = (1 - 3(n - 1)e) [(0,1,+)] + 3(n 1) ((111-))- Specifically,
1 3(n- 1)
for 2 (0,1, +)
D((2)= = 3(1 p)c
for z = (j. 1, ()
3(n 1)pE
for z = 11,
For any data distribution D, let PD be the dynamics of (fi, 81, P...... ........ fr yr, Tr) under D. Accord- ing to Lemma 4 by setting p 16n7. when T < g¹ we have that for any i,j E [n]]
PD. (iout =) - PDy (Nout =-) 1 8
(17)
From now on, we only consider distribution Dj instead of D; The readers might have the question that why not using Dj for construction directly. This is because no hypothesis has zero loss under Dj and thus D' does not satisfy realizability requirement.
Information gain from different choices of Sz Note that in each round, the learner picks Se and then only observes Tr and ye- Here we enumerate choices of J, as follows.
1. ft = 21, - 1 predicts all points in X' by negative. No matter what i is, we observe Ør = and yt 21 (2r, 0) 1. Hence (Tr, Mr) are identically distributed for all i" E [m]. and thus, we cannot learn anything about i* from this round.
2. ft predicts 0 by positive. Then no matter what i" is, we have Dr = + and yr: = 1 1(x = 0). Thus again, we cannot learn anything about i*.
3. fe = 21,,, for some non-empty ar [n]]. For rounds with x; we have 9t Yt no matter what i is and thus, we cannot learn anything about i For rounds with yr i.e., 24 # 0, we will observe Dt f((A(z (2t, ft, 1)) = 1(x, E a.).
Hence, we can only extract information with the third type of f. at rounds with x; + 0.
Reduction to stochastic linear bandits In rounds with fa = 21 a, - 1 for some non-empty de C [M] and x, # O. our problem is identical to a stochastic linear bandit problem. Let us state our problem as Problem I and linear bandit problem Problem 2 Let A {0. 1)" \ (0).
27

---

Problem 1. The environment picks an i" E [n]. At each round t, the environment picks E {eilē E [n]} with P(t) = ! for i it and P(r)) p and the learner picks an at E A (where we use a n-bit string to represent dg and at = 1 means that de predicts by positive). Then the learner observes 91 [[a]x; xz > 0) (where use 0 to represent nagative label).
Problem 2.
The environment picks linear parameter w {w"léé [n]] with w -
p)c, The arm set is A. For each arm a E A, the reward ii.dd from the following distribution:
(-1, w.p. wta
Tan (2)
(18)
10.
If the linear parameter w = =w".. the optimal arm is e
Claim 1. For any ô 0, for any algorithm A that identify i" correctly with probability 1 - 8 within rounds for any i" E [m]] in Problem we can construct another algorithm A' can also identify the optimal arm in any environment with probability
within T rounds in Problem 2
This claim follows directly from the problem descriptions. Given any algorithm for Problem I we can construct another algorithm A' which simulates A. At round t, if .A selects predictor os then A'' picks arm the same as a₁ Then A' observes a reward Two (at), which is -1 w.p. w' Ta and feed - (az) to A. Since yt in Problem is 1 w.p. Σi=1 az,; P(i) = w Ta, it is distributed identically as - (az). Since A will be able to identify i" w.p. 8 in T rounds, A' just need to output e,- as the optimal arm.
Then any lower bound on T for Problem 2 also lower bounds Problem Hence, adopt the information theoretical framework of proving lower bounds for linear bandits (Theorem 11 by Rajaraman et al. (2023) to prove lower bound for problem. In fact, also apply this framework to prove the lower bounds in other settings of this work, including Theorem and Theorem
For notation simplicity, for all i E [m), let Pa denote the dynamics of (f1. y1, fi....,fy: yr, (r) under Dj and and P denote the dynamics under = D' Let B, denote the event of {fs 21 a; 1 for a, conditional on -B, or yt = +1, (I,, Ft. Nt) are identical in all (Dili E [n]), ) and therefore, also identical in D. We can only obtain information at rounds when B, A yt = - occurs. In such rounds, Jt is fully determined by history (possibly with external randomness. which does not depend data distribution), 3/2 = and Vr = -r (a,) with r. (az) sampled from the distribution defined in
Lower bound of the information
non-empty a, [m]] }. As discussed before, for any
Eq (18)
For any algorithm that can successfully identify i under the data distribution D; with probability 3 for all i E [rs]. then Pr; (fout = i) 2 and PD, (font i) < 1 for all j * i. Recall that D; and Dj have
very close when the mixture parameter p small. Combining with Eq
P. Piouu
(iout = i) Pd. (iou i) PD. (fout =)] -P = Pi(fout i) PD, (iout = P- Pi =i)
(19)
2
4
Let 1 Let kl(g, q') denote the KI. divergence from Ber(y) to Ber(g'). Let H,-1 (S1, V1. "r....; 1/-1:: 11-1) denote the history up time Then we have
[xunit((a)) [TV Pi+t m)dn]] < 4Ep-nit((a)) [TV2(P.,P))
<2E,
DKI. (P (P))..]
(Pinsker's ineq)
-2E,
DKL (P Mt. H.-)) Del Hc
(Chain rule)
T
-2E,
Σ
P(B. = 1aan=-1)BB- -1)E
[KL. (Ber( (TT, az) ,a))))
28

---

T
-6(n- 1)
P P(B)) E P [DRL(Ber(TT,, Ber() (wo ,a))))
6(n - 1)
T
DKL (Ber(((T (TT,
,a))))
t=1
6(n - 1)
T
Σ E:ia
kl(
hit
(kp - 1)(1 p)
+ +p) + Σ
kl he he
-
91 -11
1
t=1
6(n - 1)
(Kr - 1)(1 -p)
ke kr(1 - p)
p))
E Barr~P
kickl(
+ + (n k.
kk]
(20)
71.
n1
n2
1
t=1 1
If k2 = 1, then
Re (he (0-1))) 1)(1 1)(1-p)) p)
1
log (
k kl(
+p) kk( -,,pp) p) - n
kl(=
n
n
n
p
and
hit
1a - p)
- p
(n - ke) kl
n2 n 1 = (n - 1) kl( n2'
(1 - p)n(n - 2)
where the ineq holds due to kl(g, o)) - (9- If kr = n - 1, it is symmetric to the case of hi = 1. (((1-9)"
We have
k2 kl( hic
(ke
p)
p) (n 1)kl - n-
1 1
n n -- -(n 1)kl(
p)
n n
n n
1
<
(1
p)n(n-22
and
(n kir)
kl[ Kt ke(1 - p)
kk(" -111 1 p)
kkl kl(-,p)
S log
1
1
1
n
p
If < ke < n 1, then
ht (k2- 1)(1 p)
his h2 1
ki
(a)
k k
hy kl(
+ p) =ke kl(
n 1 + n 1 p)
S hi kl
n n
n
n n
(b)
k--1% )z n-1
n kt
hi
2
< kg
ke
(1
k.
n (k, 1)
n -
1-1
n
where inequality (a) holds due to that
A--1 7-1
n-
<
hs and kl(q, g') is monotonically decreasing
in q' when q' q and inequality (b) adopts kl(4,9') (11-67 and
(g-o'1²
(n- - k.) kl( he n
ke
ka(1-p)
I (n ke) kll hr
ke
le ks)
2k n2
n
n
n2 n2(n
kir)
where the first inequality hold due to that k=(1-p) of when o' 2 q and the second inequality adopts kl(g, I (g-90)² 9'1-95
2 k n, and kl(g. q') is monotonically increasing in
=-1
Therefore, we have
6(n
1)s
T
2 log( ) p
12sT log(1/p)
Eq
20
Σ
E
n
Combining with Eq
19 we have that there exists universal constant e such that T 2
en
e(logtn/s)-
J Proof of Theorem 9
Proof. We will prove Theorem 9 by constructing instance of Q and H. and showing that for any learning algorithm, there exists a realizable data distribution s.t. achieving & loss requires at least
σ [H]] ) samples.
29

---

Construction of Q, H. and set of realizable distributions
Let feature vector space X = {0, 1....: n and let the space of feature caature-maiiuulationn set pairs = {(0, (0} Us] & C [v]]- That is to say, every agent has the same original feature vector I = O but has different manipulation ability according to 8.
Let the hypothesis class be set of singletons over [n],, i... H (21 1 E [n]]-
We now define a collection of distributions {D, E [n]] in which D; is realized by 21 - For any E [n). let D; put probability mass 1 - 6 on (0, +1) and 6s uniformly over {(0, (0) So.é. 1)|o E S,). where S, is the set of all permutations over elements and So,i ( < o (i)3 is the set of elements appearing before i in the permutation (o(1),..... (n)).. In other words, with probability 1 6c, we will sample (0, X, +1) and US.) and return (0, {0} U U -1). The data distribution D; is realized by 21 (2) since for negative examples (0, {0) 80,6 1), we have & and for positive examples (0, X, +1), we have i E X.
with will randomly draw a permutation
Randomization and improperness of the output fout do not help Note that algorithms are allowed to output randomized fout and to output fout $ H. We will show that randomization and impropemeess of fout don't make the problem easier. That is, supposing that the data distribution D:- for some i" E jn]. finding a (possibly randomized and improper) fout is not easier than identifying i*. Since our feature space X is finite, we can enumerate all hypotheses not equal to 21 (c-} - and calculate their strategic population loss as follows.
2 - 1 predicts all points in X' by negative and thus (21 - 1) = 1 - 6c;
For any X s.t. E 21. - will predict 0 positive and thus will predict any point drawn from D,. as positive. Hence C ( (21, - 1) 10==6; 6ε;
*
For any C [n] s.t. 3i + i we have (21, 1) 2 3c. This is due to that when
!/ = 1, the probability of drawing a permutation a with o -1 < o -i*) is z. In this case, we have i 80,i- and the prediction of 21l 1 is +1.
Under distribution Di., if we are able to find a (possibly randomized) fout with strategic loss L (Jout) S then have (fout) En [c' 2 Pries (h + (1 1)
-3)-3 3e. Thus, Pra (h- 21 (e-) - 1) 2 3/2 and then, we can identify i* by checking which realization of fout has probability greater than I. In the following, we will focus on the sample complexity to identify
the target function 21 ( 1 or simply i". Let iout denote the algorithm's answer question of "what is ?*?"
Smoothing the data distribution For technical reasons (appearing later in the analysis), don't want to analyze distribution {D,li E [n]] directly as the probability of A, = i" is when fe(i") = +1. Instead, we consider the mixture of DD and another distribution D to make the probability of A, = i" be a small positive number. More specifically, let D' = (1 - -D)D; + DD", where D' defined by drawing (0, X, +1) with probability 1 1-6s and (0, (), (0,i)-11 -1) with probability 6s. When is extremely small, we will never sample from D when time horizon 7' is not too large and therefore, the algorithm behaves the same under D' and D.. For any data distribution D, let Po be the dynamics of (æ1, f1. A1, V1: .i..... .T, fr, Ar, yr, Tr) under D. According to Lemma
by setting p 1 when T I
we have that for any i.j E [n]
E,
1
Pp, =) P PDy (Pout j) $
(21)
From now we only consider distribution D' instead of D: The readers might have the question that why not using D' for construction directly. This because no hypothesis has zero loss under D/ and thus D' does not satisfy realizability requirement.
30

---

Information gain from different choices of ft In each round of interaction, the learner picks a predictor ft. which can be out of H. Suppose that the target function is 21 (1-) 1. Here we enumerate all choices of Sa and discuss how much we can learn from each choice.
= 2 1 predicts all points in X' by negative. No matter what i" is, will observe Á, = 2i = 0. ye ~ Rad(1 - 6e). Dt = -1. They are identically distributed for any i" e [n] and thus we cannot tell any information of i" from this round.
for some a C X s.t. 0 aç- Then no matter what i is, we will observe A, = It = 0. yt ~ R1d(1 - 6e), Vt = +1. Again, we cannot tell any information of i" from this round.
f: = 2L.
ft = 21.. 1 for some some non-empty a [n]. For rounds with yu +1. we have Z7 = 0, 9t +1 and A, = (0, ft, X¹) ~ Unif(a:) ). which still do not depend on '*. For rounds with 3/+ -1, if the drawn example (0, {0} U s, -1) satisfies that 7 a o 0, the we would observe A E at and Dr = +1. At least we could tell that I (1,) is not the target function. Otherwise, we would observe A, 2t 0 and Dt- 11
Therefore, we can only gain some information about at rounds in which ft 21.. for some non-empty a, C [n]] and y/- = 1. In such rounds, under distribution D/-, the distribution of A, is described as follows. Let ky = la, denote the cardinality of a,. Recall that agent (0, {0) U Us;- 1) breaks ties randomly when choosing A, if there are multiple elements in az 0s. Here are two cases: i" E ag and i* & dr-
1. The case of 1" E ax: With probability p. we are sampling from D.d and then A. = i. With probability 1- p, we are sampling from Dj-. Conditional on this, with probability by we sample an agent (0, {0) U -0,,--11 with the permutation satisfying that o (i")
o Ti) for all j E dr \ { and thus, A, = 0. With probability 1 E. there exists jE a \ {it) s.t. o (0) < <o (i*) and A. + 0. Since all j at \ {(*} are symmetric, we have Pr(A, j) = (1 -p)(11 E k
1-p Hence, the distribution of A, is
j w.p.
L- for j E ac. #i k
4, = 1 w.p. p
0 w.p. 1-p
We denote this distribution by Pa(ae,
2. The case of i* & ag: With probability p. we are sampling from D. we have A, = x2
With probability 1 we are sampling from D,.. Conditional on this, with probability of k,+1 (i*) < o (j) for all E a and thus, A. Ir 0. With probability 1 k
there exists j E a, s.t. o (j( < (i*) and A. E at. Since all j E az are symmetric, we 1_p. Hence the distribution of A, is have Pr(A.- j) = (1 p1 K E. KTT
j
1- for E w.p. k.tl
A
1-p
w.p. p + ki+1
We denote this distribution by (ac).
To measure the information obtained from A,, we will use the KL divergence of the distribution of Ar under the data distribution Dí. from that under a benchmark data distribution. We use the
average distribution over {Diji E [n]]]. which is denoted by D = + Emen D'. The sampling process is equivalent to drawing i" [nll first and then sampling from D'.. Under D. for any E ou. we have
Pr(A. = 5) PPr(i Ea \ (11) Pr(A, = J/i E ((1) + Pr Pr(A jib 5)
+ Pr(ii & a4)) Pr(A. = ezyli" & at)
h 1 P 1
n hit
1- p
(nki - 1)(1 - p)
P
+
π
K
n1
n1
k +1
(ke + 1)
n
31

---

and
Pr(A: = 0) = Pr(ii E
at)
Pr(A, = 0 E az) + Pr(i" $ at) Pr(A, = 0/i" $ at)
htg p
n
K2
1-P
(n + 1)(1 - p)
(n kc)p
π
hiz
n
(p +
ki +
=
niks + 11
+
n
Thus, the distribution of A under D
is
A
j
w.p.
[nk - 11(1 (11-))
(k, +1)
p)
+ for j E az (n=
0 W.D.
(++ (1 p)
I(k++I)
We denote this distribution by P(at). Next we will compute the KL divergence of Pe (ax) and Pe (az) from P(at). Since p T S 16n we have (nk-11((1p))
[k(((+++1] + n S 1- and (n+1)(1-)) p) (n-k,ip 1 n + + P.. We will also use log(1 + x) S x for x 2 in the following calculation. For any i" E ar, we have
[[kx+1]
DRL DKL(P(aa)lPE(aa.F
= (K: 1) (nik, - 1)(1 - p)
+ P
log ( (nnbe- - 1)(1 - p)
+ P) kG
nkke [kg + 1)
n
nkk (kg +
1 - p
(nke - 1)(1 - p)
+ p
(nhi - -1)(1 -p)
p
1
log
+
(kt + 1)
(ke + 1)
n1
P
+ 1)(1 -p)
(n k(Pp
(mmtthe
(n + 1) - p))
(n
ke)p
his
+
+
log
+
n(ks +1)
n(ke + 1)
1 - p
<(k; - 1)
(nks - 1)(1 - p)
+ p
log(
1-p p
hit )
+
1 - p
log(1
- -
nhiekk (kx + 1)
n
k + 1
1
p
ke + 1
p
1
+
+ p)
log (1 + pkit)
kt
1
2 k
1
1
<0 +
log( )
+
phi-
log( -) + 2p.
(22)
hi +1
hig +
p
For Pε(ae), we have
(ka(P(a))lPP((a))
(nki 1)(1 - p)
P log
nhelki (1m +)
-1)(1 - p)
+ P)
h2 + 1
=ke
+ n
nki (kt + 1)
n
1-p
(n+ + 1)(1 - p)
(n ks)p
(n + (n11 p)
(n ke)p"
+
log
niki + 1)
n
nike + 1)
n
p
1-p ketl
<ki
(nki 1)(1 - p)
+ p
log(
1 p
k +
nk: (kic + 1)
n2
hit + 1-p p
1
(n 111+1((1 p)
(n - kelp kk))))p
1
+ ( hi
+ p) log
nikke + 1)
n
p
ket1
1-p
1
1 - p(k2 + his + 1)
-0 +
(
+ p) log(1 +
kt
n11 + ksp)
1
<( k, n(1 + kep)
+ p)
(23)
nk,
Lower bound of the information
Now we adopt the similar framework used in the proofs For notation simplicity, for all i E [n]. let P; denote the dynamics of
of Theorem 7 and 8
ST. AT, Ur, (T) under D' and and P denote the dynamics under D. (01, f1, 1I..A., VI.
V1.
Let B, denote the event of (L = 21
for some non-empty d, C [m]]]. As discussed before, for any ar, conditional on - B, or ye +1. (zz, Ae, Vt, De) are identical in all (Dili e [ri].. and therefore, also identical in D. We can only obtain information at rounds when B, A (ye -1) occurs.
32

---

In such rounds, we know that 2; is always O, ft is fully determined by history (possibly with external randomness, which does not depend data distribution), y/2 -1 and yr is fully determined by A (ūr = +1 iff. A, + 0).
Therefore, conditional the history Hz-1 (211 fI, A1, VI, D1, ..... J4-1: Se- At- Ut- Dt-1) before time t, we have
(PI, St, A.; Vr, De.HH.- Jes De, Wel Hr.HH
=P(B, A = 1I) (P(4 H,
B. A y/ = 11] H1-1, Be A y1 = -1))
-K.P(B.)DK..P(A H1-1, Bg A = - ( H, B, A -1))
(24)
where the last equality holds due to that yt ~ Rad(1 (1 - 6c) and does not depend on Bi.
For any algorithm that can successfully identify i under the data distribution D; with probability 3 for all E [n]. then PD, (Fout i) and PD, (Fout
S 1 for all * i. Recall that Dj and D are very close when the mixture parameter p is small. Combining with Eq (1). we have
P Pilfout = 1) P, (fout = +)
2 Pp, (fou i) PD, (Vout = +) - PP (Vout = i) Py(nt = 1) - PP (Vout = i) - -Py = i)
1 1
2
Then we have the total variation distance between and P
TV(P,,P,) 2 Pi(fout = Py(fout = 1)
(25)
Then we have
(nit(i(()))
E,
TV2 (P, P (od+1)mdnn)) mod 4I, (ni(((((( [TV P)]
<2E,
[PIP.)
(Pinsker's ineq)
T
=21
(KL( (.ll ft, Ve,
ye. De (el(4+-1))
(Chain rule)
<12=B,
-1))
1=1
(Apply Eq (4
12g
P (B.)
Σ
DEL (PA
n
i=1
T
12c
E
Barra
I(B))
Σ (RL(P(a))IP((aa)) + Σ DiL(((oo)))PP(aaa))
n
i:ia:
12F
E
Σ
Σ
log
1 (
+ 2p
Σ
(Apply Eq
22
k 1
p
ndip
[1[(B,]=1
I:Ea:
12s
(log( ) 2mp + 1)
n
p
127 12Te (eTTeloo(166 (/) 2)
71
Combining with Eq
25 we have that there exists universal constant such that T 2
=(log(n/cc- 1)
33


Reviews:
[{"review_id": "Ix83YmfPg7", "reviewer": "Reviewer_Ro1X", "summary": "This paper studies an online learning problem where the learner interacts with a strategic agent in the following way: the learner chooses a hypothesis from a hypothesis class; the agent, after observing the chosen hypothesis, can manipulate its feature vector to be within some ball of unknown and personalized radius to obtain a positive prediction. The paper considers various settings (adversarial online and distributional online) and various feedback models (what feedback does the learner observe before and after its decision). The paper provides mistake bounds (upper and lower) (for the adversarial online setting) and sample complexity bounds (for the distributional online setting) for all feedback models.", "questions": "* Is the definition of \"conservative algorithms\" (in section 4.3) a well-known concept? It certainly makes a lot of sense. I am wondering whether that formalism already exists or not. If not, do you have thoughts on how this could be used elsewhere in online learning for lower bounds?", "limitations": "Limitations: adequately addressed.\nNegative societal impact: this is theoretical paper and I don't see any direct negative impacts arising from this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written - it is clear and easy to follow. It also includes proof sketches and intuitions behind the results and proofs.\n\n* The paper studies an interesting online learning model and does a comprehensive job of modelling various types of feedback.\n\n* Algorithms 1 and 2 build on classic ideas but are cleverly modified for the problem being studied. \n\n* Theorem 7 about conservative algorithms is very interesting.", "weaknesses": "* This paper studies the setting of a finite hypothesis class and in the realizable setting. Extensions to a general hypothesis class (with an appropriate combinatorial measure) and the agnostic case would really enhance the value of the paper. (Note - the authors point out these avenues for future work in the conclusion.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Ro1X for their valuable comments. In response to their questions, we provide the following clarifications and explanations.\n\n> Extension to general hypothesis class and the agnostic case.\n\nWe agree with the reviewer that the general hypothesis class and the agnostic case are interesting open questions to explore! As mentioned by the reviewer, we had already included these directions in the \"Discussion and Open Problems\" section of our submission. However, it is essential to emphasize that our primary focus has been on formulating the problem and presenting preliminary findings in this direction, which is a challenging task in itself.\n\n\n> Is the definition of \"conservative algorithms\" a well-known concept?\n\nYes, the concept of 'conservative algorithms' is widely recognized in online learning, referring to algorithms that make updates only in mistake rounds.\n\nThe 'conservative' philosophy is widely adopted when designing algorithms, including the well-known Perceptron algorithm. Besides, the book 'Prediction, Learning, and Games' by Nicolo Cesa-Bianchi and Gábor Lugosi introduces conservative algorithms for linear classification and explains that \"The philosophy behind this conservative policy is that there is no reason to change the weight vector if it has performed well in the last time instance.\" \n\nIn standard online learning, it is well-known that if a hypothesis class is learnable with a mistake bound of M, then it is learnable by a conservative algorithm with the same mistake bound of M. Consequently, establishing a lower bound for conservative algorithms effectively establishes a lower bound for all algorithms.\n"}, {"review_id": "jaEhiNUiN4", "reviewer": "Reviewer_XhgR", "summary": "The paper explores a setting of strategic classification - where agents respond to deployed predictive policies by potentially manipulating their feature vector so as to achieve positive predictions. The authors explore this setting while allowing agent manipulations to be personalized (no assumptions regarding same manipulation budget across agents, etc.), and also do not assume that the learner knows the manipulation power of the agent ahead of time. The authors assume realizability - that the incoming agents and their labels are consistent with some \"true\" underlying concept h* in the concept class. They consider different variants of an online classification problem - based on whether the original/manipulated feature vector of the agent is revealed, and when are they revealed - before/after the learner selects its predictor. In these four settings, the authors give upper and lower bounds for mistakes (in a potentially adversarial setting), as well as sample complexity for PAC learning (In a stochastic data generation setting).", "questions": "I found it a bit difficult to follow example 1 in the main text. For example, if H is singletons over [n], how can f_t be all-negative? Also, could you clarify the definition of the metric - is it that distances from 0 to other nodes are 1, and all other distances are 2? Regardless, could you provide a more detailed explanation of the dynamics presented in this example?", "limitations": "The authors properly discuss limitations in the main text.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper offers a \"complete story\" in the context of an interesting sub-problem in strategic manipulation (where the true label cannot change) in realizable, online settings. I liked the framework the authors present to capture the feasible manipulation region for each agent, which abstracts away the cost function/budget in an elegant manner. I also like that the authors operate under the fact that the learner does not know how agents would manipulate. The division to revealing the original/manipulated features before/after the classification also makes a lot of sense and is a nice way of thinking about manipulation settings (where the true label is unaffected by such changes). In terms of results/techniques - the idea of leveraging the ball structure of feasible manipulation area to order concepts by distances and allow for bisecting the version space is pretty neat. The results for the setting where both the original and manipulated features are revealed after the predictor is picked are even more interesting (especially the algorithm and sample complexity for improper learning).\n\nThe paper is overall very well-written, and seems sound (although I have just looked, and not carefully read the appendix).", "weaknesses": "I find the realizability assumption rather strong, in the following sense - as it is written in line 139, realizability in this paper is defined with respect to the manipulated features, i.e. there exists a concept h* which is the one giving the \"true\" labels for all of the manipulated features. But this, in turn, depends on the manipulations, which are personalized. This degree of circularity makes it a bit hard to think of how can we pick H ahead of time such that h* is present, without potentially having H to be of very large complexity, or otherwise restricting the personalized nature of the manipulations to some degree. But maybe this is inevitable for such general model of manipulation.\n\nI think it is implicitly assumed that given agent x, the personalized manipulation is fixed (there can't be another agent with the same features, and different manipulation profile). If so, maybe it is worth noting in the main text.\n\nAcross the main text, the authors claim that prior work in strategic classification has not entailed personalized manipulation power for agents (e.g. line 375). This is inaccurate - see e.g. Bechavod et al. 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer XhgR for their valuable comments. We are particularly pleased that the reviewer finds merit in our modeling of personalized manipulation sets, the setting of unknown manipulation, and the algorithmic ideas involving bisecting the version space. In light of their questions and concerns, we offer the following clarifications and explanations.\n\n> Concerns on the realizability assumption.\n\nThe essence of our realizability assumption is that there exists a hypothesis h* satisfying the following conditions:\n1. All negative points and their manipulation sets lie on the negative side of h*.\n2. As for positive points, they either reside on the positive side of h*, or on the negative side with their corresponding manipulation sets intersecting the positive side of h*.\n\nFrom the adversarial robustness perspective, note that our realizability assumption is weaker than the realizability assumption in adversarial robustness (see Montasser et al., (2019) for example) which assumes that\n1. All negative points and their manipulation sets (referred to as perturbation sets in the context of adversarial robustness) lie on the negative side of h*.\n2. All positive points and their manipulation sets lie on the positive side of h*.\n\nFrom the game theory perspective, the strategic classification problem is a Stackelberg game, where the learner (the leader) selects a predictor and then the agent (the follower) manipulates their feature vector to best respond to the predictor. Our realizability assumption assumes that the value of the Stackelberg equilibrium (the negative strategic loss) is 0.\n\nIn the final version, we will include a thorough discussion on the realizability assumption.\n\n\n>  Is it implicitly assumed that given agent x, the personalized manipulation is fixed? \n\nNo, our approach allows different manipulations for the same x. As demonstrated in Example 1 of the paper, for x being 0, the radius can take values of either 0 or 1. We will address this in our Model section in the final version.\n\n>  Previous work on strategic classification with personalized manipulation power, e.g., Bechavod et al. (2021).\n\nBechavod et al. (2021) actually focused on the regression problem, which inherently differs from the classification problem. We will incorporate the literature of strategic regression in the related work.\n\n> Explanation on Example 1. \n\n* If $H$ is singletons over $[n]$, how can $f_t$ be all-negative?\n\nThis is because we are considering a more general case where $f_t$ can be any hypothesis and does not necessarily belong to $H$. As described in line 2 of protocol 1, $f_t\\in Y^X$ indicates that $f_t$ can be any hypothesis.\n\n* Is it that distances from 0 to other nodes are 1, and all other distances are 2?\n\nYou are correct. Consider a star graph, where 0 is the central node and the others are leaf nodes. Let the distance between every two nodes be the length of the shortest path on this star graph. Then the distance from 0 to other leaf nodes is 1 and the distance between any two leaf nodes is 2. \n\n* A more detailed explanation of the dynamics presented in this example.\n\nIn the realizable setting, suppose the target function $h^*$  is the singleton $21_{\\{i^*\\}} -1$ for some $i^* \\in [n]$. Then when $f_t\\neq h^*$, there are three different cases.\n\n1. If the learner picks $f_t$ = all-negative, then the environment will pick agent $(0, 1, +1)$. Note that no matter what $i^*$ is, the target function $21_{\\{i^*\\}} -1$ will predict the agent $(0,1)$ by positive since the distance between $0$ and $i^*$ is 1 and the agent can manipulate the original feature 0 to $i^*$. The all-negative predictor will misclassify this agent by negative. The learner will observe the original feature 0, manipulated feature (conditional on all-negative is implemented) 0, true label +1, and the prediction -1, which do not contain any information about $i^*$. Hence, the learner makes a mistake but cannot learn anything about $i^*$. \n\n2. If the learner picks an $f_t$ which predicts $0$ by positive, the environment will pick agent $(0,0,-1)$. Note that no matter what $i^*$ is, the singleton $21_{\\{i^*\\}} -1$ will predict the agent $(0,0)$ by negative since the distance between 0 and $i^*$ is 1 and the agent cannot manipulate the original feature $0$ to $i^*$. The implemented classifier $f_t$ will misclassify the agent by positive. The learner will observe the original feature $0$, manipulated feature $0$, true label $-1$, and the prediction $+1$, which do not contain any information about $i^*$. Hence, the learner makes a mistake but cannot learn anything about $i^*$.\n\n3. If the learner picks an $f_t$ which predicts some $i\\in [n]$ that is not equal to $i^*$ by positive, the environment will pick agent $(i,0,-1)$. The target function $21_{\\{i^*\\}} -1$ will predict the agent $(i,0)$ by negative since the distance between $i$ and $i^*$ is 2 and the agent cannot manipulate the original feature $i$ to $i^*$. The implemented classifier $f_t$ will misclassify this agent by positive. The learner will observe the original feature $i$, manipulated feature $i$, true label $-1$, and the prediction $+1$. The learner learns that $21_{\\{i\\}} -1$ cannot be the target function and does not know which one of $[n]\\setminus i$ is the true $i^*$. Hence, the learner makes a mistake but is only able to eliminate one hypothesis.\n\nSince $i^*$ can be chosen adversarially, the learner will not be able to pick an $f_t = 21_{\\{i^*\\}} -1$ (alternatively, identifying $i^*$) before making $\\Omega(n)$ mistakes. The formal proof for a more general case can be found in the proof of Theorem 3. Example 1 is utilized to offer intuitive insights into the linear dependency.\n"}, {"review_id": "2fofK507Qv", "reviewer": "Reviewer_V2P4", "summary": "The paper studies strategic classification where a sequence of agents, given information about decision rule, may manipulate their features strategically to receive favorable decisions. The goal of the learner is to find a hypothesis that minimizes the number of mistakes through sequential interaction with agents. In addition to conventional strategic classification where agents manipulate their features within a bounded radius ball, this paper also considers personalized manipulation where agents can only manipulate the features belonging to a manipulation set that is unknown to the learner. For both scenarios, it provides the mistake bounds and PAC sample complexity under several settings: 1) when original features are revealed to the learner before choosing the hypothesis and manipulated features after, 2) when both original and manipulated features are revealed after choosing the hypothesis, 3) when only manipulated features are revealed after choosing hypothesis, 4) neither original nor manipulated features are revealed.", "questions": "It is not clear to me how the present model captures the personalized manipulations (i.e., different manipulation abilities across agents). Based on my understanding, the authors assume there exists a pre-defined manipulation set $u$ that constrains agents' ability to manipulate. Agents choose to manipulate only if such a manipulation set overlaps the positive region of the predictor, and they would break ties randomly. By personalization, do you mean the manipulation set differs across agents? It seems that the manipulation set $u$ is the same and fixed over time. Should not this manipulation set depends on the predictor? Why break ties randomly? It is very hard for me to interpret this model. It would be helpful if authors can link the model to a real example.", "limitations": "The authors discussed the limitations, but the potential negative societal impact is not discussed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Establishing mistake bounds and sample complexity is an important topic in strategic classification, this can be challenging especially when agent features before/after manipulation are unknown to the learner.\n\n2. The paper considered many settings comprehensively, from a simpler setting when both original and manipulated features are revealed to the learner, to a more complex setting when neither is known to the learner.\n\n3. Section 3 (Overview of the results) is very helpful", "weaknesses": "1. The presentation and some statements can be misleading and confusing. \n\nThe authors emphasized in the abstract/introduction that one prime difference between the present paper and the prior works is that this paper considers personalized manipulation with non-ball manipulations. However, the majority of the paper still focuses on conventional settings with ball manipulations. It can be misleading as I expect more results on non-ball manipulations after reading the abstract. \n\n2. The paper needs more literature review and discuss the differences with prior works to show the novelty. \n\nThe paper introduced the existing works on regret bound in strategic learning very briefly, e.g., (Ahmadi et al., 2021), (Ahmadi et al., 2021). It seems they also considered mistake bound under uniform, unknown manipulations. Moreover, there are many other works studying PAC learning for strategic classification and conducting sample complexity analysis, e.g., [1,2,3]. I think a large body of related works is missing and authors should elaborate more on these works and discuss differences with the present paper. \n\n[1] Sundaram, R., Vullikanti, A., Xu, H., & Yao, F. (2021, July). Pac-learning for strategic classification. In International Conference on Machine Learning (pp. 9978-9988). PMLR.\n[2] Zhang, H., & Conitzer, V. (2021, May). Incentive-aware PAC learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5797-5804).  \n[3] Lechner, T., & Urner, R. (2022, June). Learning losses for strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 7, pp. 7337-7344).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer V2P4 for their valuable comments. In response to their questions, we provide the following clarifications and explanations.\n\n>  One prime difference between the present paper and the prior works is that this paper considers personalized manipulation with non-ball manipulations.\n\nNo, we did not say that the prime difference lies in non-ball manipulations. In the abstract, we stated that the main difference lies in that the manipulations are personalized and unknown (line 8-10). In the introduction, we began by mentioning that we model the manipulation through a set of feature vectors and then introduced ball manipulations (line 41-47). \n\nWe will add a sentence in the abstract to address that the main focus of this paper is on ball manipulations.\n\n> The paper needs more literature review and discuss the differences with prior works to show the novelty.\n\nDue to space limitations, we briefly discussed differences with the prior work and deferred some related work to the appendix. Check our appendix A for more related work. \n\nAlthough we only provided a brief discussion of prior work, we have indeed addressed the essential differences. For instance, we pointed out that the manipulations in Ahmadi et al., (2021) are uniform, while the manipulations in [1,2,3] are known. Throughout the paper, we consistently emphasize that the core of our work revolves around non-uniform unknown manipulations.\n\nWe will add a more detailed discussion in the final version.\n\n> How does the present model capture the personalized manipulations?\n\n* Does the manipulation set differ across agents?\n\nYes, personalized manipulation means that the manipulation set differs across agents. Note that the manipulation set varies over time. Recall that each agent is a triple of the original feature vector $x$, the manipulation set $u$ and the label $y$. At each time step $t$, a new agent $(x_t,u_t,y_t)$ comes. In the adversarial online setting, this new agent, including her manipulation set $u_t$ is picked by the environment adversarially. In the distributional setting, the new agent is sampled from a distribution.\n\n* Should not this manipulation set depend on the predictor?\n\nNo, the manipulation set does not depend on the predictor but the manipulated feature vector does. Note that the manipulation set $u_t$ is different from the manipulated feature vector $\\Delta_t = \\Delta(x_t,f_t,u_t)$. The manipulation set $u_t$ is a set of feature vectors that the agent can modify their original feature vector $x_t$ to. That is to say, the agent can only modify their original feature within $u_t$. For any implemented predictor $f_t$, if $u_t$ overlaps the positive region of the predictor, then the agent may manipulate as such a manipulation can help the agent receive a positive prediction. If $u_t$ does not overlap the positive region of the predictor, then the agent will not manipulate as such manipulation cannot help the agent receive a positive prediction. Hence, the manipulation set does not depend on the predictor. The manipulated feature vector $\\Delta_t = \\Delta(x_t,f_t,u_t)$, which is the feature vector the agent modifies to after observing the predictor $f_t$, depends on the predictor.\n\n> Why break ties randomly?\n\nWe actually allow breaking ties in any fixed way. For simplicity, we fix this tie breaking way to be random. We will clarify this in the final version.\n\n>  Link the model to a real example.\n\nConsider the example of college admission (line 27-28). Imagine a simplified situation where a college admits students with SAT scores higher than a certain threshold, denoted as C. For a student, obtaining a score of 1500 may be the best possible outcome if they are only allowed to take the SAT test once. However, if they have the opportunity to retake the test, they can achieve higher scores. The manipulation set for the student comprises all achievable scores through retakes. Notably, this manipulation ability varies between students of different financial backgrounds; wealthier students can afford to retake the test more frequently than their less affluent counterparts, resulting in different increases in scores that are independent of the predictor, i.e., the threshold C.\n\nHowever, once the threshold C is disclosed, students will adapt their manipulative behavior accordingly. If they reach the score C, they will no longer retake the test, effectively capping their score at that level. Conversely, if a student realizes that obtaining a score of C is unattainable, they will refrain from manipulating their scores. Therefore, the final SAT score becomes the manipulated feature, influenced by the predictor, which is the threshold C.\n"}, {"review_id": "pv8kVa0K3Y", "reviewer": "Reviewer_Hsdn", "summary": "The paper studies strategic classification in the setting where agents generally have different power of manipulation, which is unknown to the classifier.  The authors consider both the online model and the PAC model, and investigate 4 increasingly difficult settings in which the classifier observes different information about each agent.  They show nontrivial regret / sample complexity upper and lower bounds for all these settings.", "questions": "(also including detailed comments here)\n\nFootnote 1, \"agents break ties randomly\": do you really mean \"arbitrarily\"?\n\nLine 112, remark on randomized classifiers: the alternative model where agents don't observe the internal randomness of the classifier makes sense too.  Any reason for choosing this particular model?\n\nOverview of results: while these results are certainly nice and important, I wonder if anything can be said in the case where $|\\mathcal{H}| = \\infty$.  Can you comment on this (e.g., conjectures, difficulties)?  (Later I see you mention this as a future direction, which sounds fair since the paper already has quite a number of results.)\n\nLine 240: why is \"GALLANT\" all capitalized?\n\nGeneral technical question: how crucial is the metric space assumption?  In other words, what if the triangle inequality doesn't hold?  I guess at least some of your positive results still hold?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper explores a meaningful and challenging new direction in strategic classification.  The models and settings are natural and rich, and the results are fairly comprehensive (and in some cases surprising).  Technically, there seem to be several interesting ideas behind the bounds.", "weaknesses": "I'd be more excited to see results for infinite hypothesis classes and agonostic settings (both of which the authors discuss as future directions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Hsdn for their valuable comments. In response to their questions, we provide the following clarifications and explanations.\n\n> Extension to general hypothesis class and the agnostic case.\n\nWe agree with the reviewer that the general hypothesis class and the agnostic case are interesting open questions to explore! As mentioned by the reviewer, we had already included these directions in the \"Discussion and Open Problems\" section of our submission and we have already obtained numerous results. The primary focus of this work has been on formulating the problem and presenting preliminary findings in this direction, which is a challenging task in itself.\n\n> \"Agents break ties randomly\": do you really mean \"arbitrarily\"?\n\nWe actually allow breaking ties in any fixed way. For simplicity, we fix this tie breaking way to be random. We will clarify this in the final version.\n\n> Remark on randomized classifiers: the alternative model where agents don't observe the internal randomness of the classifier makes sense too. Any reason for choosing this particular model?\n\nThe paper by Ahmadi et al. (2023) actually gives a good discussion of both randomization models in their setting (where manipulation abilities are known up-front via a manipulation graph).  They show that the model you mention (which they call the \"fractional model\") behaves similarly to the deterministic model.  It also brings up additional complications, such as: do different manipulations have different costs, and if so, do agents still try to maximize their probability of success or do they instead look at expected utility = expected gain - cost?  For these reasons, we decided to focus on the randomized model where agents react to the realization of the randomness.  We can add additional discussion in the final version.\n\n> Comment in the case where $|H|=\\infty$.\n\nThanks for noticing the discussion on this question. As mentioned in the future directions, for infinite class, it is unclear what combinatorial measure can capture the essence of strategic classification.\n\n\n> Why is \"GALLANT\" all capitalized?\n\nWe will change it to “Gallant”.\n\n> How crucial is the metric space assumption? In other words, what if the triangle inequality doesn't hold? I guess at least some of your positive results still hold?\n\nThe metric space assumption is mainly used to provide an ordering of hypotheses. Take the Strategic Halving algorithm for example. If we replace the distance d with some function d’ such that the function d’ allows us to do binary search as we did in metric space, then our positive result should still hold."}, {"review_id": "fXFRTQWolk", "reviewer": "Reviewer_6Wy9", "summary": "- This paper studies strategic classification with unknown and personalized manipulation in an online/distributional setting, i.e. different agents can manipulate their features to a different degree, and the learner does not know the extent to which agents can manipulate their features. \n- The paper assumes realizability, i.e. the existence of a correct classifier in the hypothesis class, that remains correct under strategic manipulation. Both bounds on PAC sample complexity and mistake bounds are provided for a variety of assumptions about the possible manipulations (metric ball vs nonball) and the feedback provided to the learner (original features observed before deploying classifier or not; original/manipulate/no features observed along the true label after classification).  \n**While I remain unsure about the realistic applicability of the most interesting results, the rebuttal and others' reviews have not uncovered any new crucial weaknesses, so I am keeping my score.**", "questions": "- Do you expect (versions of) the proposed algorithms to still work if different players use different metrics rather than just differently sized balls for the same metric?", "limitations": "- The main limitations that are not discussed in the weaknesses were highlighted and discussed by the authors in the discussion/open problems section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written, and good intuition is provided for some of the technical theorems. \n- The setting of varying and unknown manipulations strength in strategic classification is relevant. \n- Both lower bounds and upper bounds based on concrete algorithms are provided", "weaknesses": "- The motivation for the easier cases is not entirely clear. For example, in which setting is it realistic for the learner to see the *original* features of the next agent before choosing which hypothesis to deploy?\n    - This is particularly relevant, as the more interesting results that seem clearly distinct from the previous literatur are on these easier cases. \n- Minor comments:\n  - The Formatting of table 1 could be improved. In particular, some tildes are intersecting the table lines. Additionally, the third row with multiple results for slightly different settings could be further split up to avoid confusion. \n  - If I understand correctly, it is possible for the strategic setting to be realizable for a class of hypotheses, while the non-strategic setting is not. Highlighting this might make some of the proofs (like for theorem 9) easier to parse. \n  - I guess the tie-breaking procedure is slightly underspecified when there are multiple points at the decision boundary with the same distance from x?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 6Wy9 for their valuable comments. In response to their questions, we provide the following clarifications and explanations.\n\n> The motivation for the easier cases.\n\nFor the easiest model (x is observed first):\n\n- Consider a teacher giving students a writing assignment or take-home exam.  The teacher might have a good knowledge of the students' abilities based on their performance in class, but the grade has to be based on how well they do the assignment.  The students might manipulate by using the help of ChatGPT / Google / WolframAlpha / their parents, etc.  The teacher wants to create an assignment that will work well even in the presence of these manipulation tools.\n\n- If we think of each example as representing a subpopulation (e.g., an organization is thinking of offering loans to a certain group) then there might be known statistics about that population, even though the individual classification (loan) decisions have to be made based on responses to the classifier.\n\nFor the second-easiest model (x is observed after):\n\n- Here, there are a lot more scenarios that might fit.  For example, if a high-school student takes the SAT test multiple times, most colleges promise to only consider the highest one (or even to \"superscore\" the test by considering the highest score separately in each section) but they do require the student to submit all of them.  \n\n> Do you expect (versions of) the proposed algorithms to still work if different players use different metrics rather than just differently sized balls for the same metric?\n\nYes, we expect the algorithms to work if the metrics are known to the learner. As our setting is online, the algorithm utilizes the metric at each round to order all hypotheses and reduce the version space, which should still work under different metrics.\n\nResponses to minor comments:\n\n> The Formatting of table 1 could be improved. \n\nWe will improve the formatting of the table.\n\n> Is it possible for the strategic setting to be realizable for a class of hypotheses, while the non-strategic setting is not?\n\nYes, the reviewer is correct on this. We will highlight it in the final version.\n\n> The tie-breaking procedure is slightly underspecified when there are multiple points at the decision boundary with the same distance from x?\n\nWe allow tie breaking arbitrarily when more than one points have the same distance from x. We will clarify this in the final version.\n"}]

Author rebuttal:

Meta-review: This is a well-executed paper the provides a nice contribution to the growing literature on strategic classification. The paper proposes a novel formulation of learning under unknown manipulation sets in a sequential setting, for which it provides comprehensive results. Reviewers found the paper to be clear and well-written. Some reviewers would have liked to see an extension to infinite hypothesis class and to an agnostic setting, but understand that establishing the simpler case of finite cases in the realizable setting, albeit being strong assumptions, is reasonable within the current scope.
Decision: Accept (poster)