Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification

Authors: saba  ahmadi
kunhe  yang
hanrui  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:31:40

Abstract: We study the problem of online binary classification in settings where strategic agents can modify their observable features to receive a positive classification. We model the set of feasible manipulations by a directed graph over the feature space, and assume the learner only observes the manipulated features instead of the original ones. We introduce the Strategic Littlestone Dimension, a new combinatorial measure that captures the joint complexity of the hypothesis class and the manipulation graph. We demonstrate that it characterizes the instance-optimal mistake bounds for deterministic learning algorithms in the realizable setting. We also achieve improved regret in the agnostic setting by a refined agnostic-to-realizable reduction that accounts for the additional challenge of not observing agents' original features. Finally, we relax the assumption that the learner knows the manipulation graph, instead assuming their knowledge is captured by a family of graphs. We derive regret bounds in both the realizable setting where all agents manipulate according to the same graph within the graph family, and the agnostic setting where the manipulation graphs are chosen adversarially and not consistently modeled by a single graph in the family.

Main paper: 
 introduction: 
 Strategic considerations in machine learning have gained significant attention during the past decades. When ML algorithms are used to assist decisions that affect a strategic entity (e.g., a person, a company, or an LLM agent), this entity -henceforth the agent -naturally attempts to game the ML algorithms into making decisions that better serve the agent's goals, which in many cases differ from the decision maker's. Examples include loan applicants optimizing their credit score without actually improving their financial situation. 2 It is therefore desirable, if not imperative, that the ML algorithms used for decision-making be robust against such strategic manipulation. Indeed, extensive effort has been made towards designing ML algorithms in the presence of strategic behavior, shaping the research area of strategic machine learning [Brückner and Scheffer, 2011, Hardt et al., 2016] . In particular, powerful frameworks have been proposed for offline environments, where the decision maker has access to historical data, on which they train a model that is subsequently used to make decisions about (i.e., to classify) members of a static population. These frameworks provide almost optimal learnability results and sample complexity bounds for strategic machine learning in offline environments, which gracefully generalize their non-strategic counterparts (see, e.g., [Zhang and Conitzer, 2021, Sundaram et al., 2023] ).However, the situation becomes subtler in online environments, where the decision maker has little or no prior knowledge about the population being classified, and must constantly adjust the decision-making policy (i.e., the classifier) through trial and error. This is particularly challenging in the presence of strategic behavior, because often the decision maker can only observe the agent's features after manipulation. In such online environments, the performance of a learning algorithm is often measured by its regret, i.e., how many more mistakes it makes compared to the best classifier within a certain family in hindsight. For online strategic classification, while progress has been made in understanding the optimal regret in several important special cases, a full instance-wise characterization has been missing, even in the seemingly basic realizable setting (meaning that there always exists a perfect classifier in hindsight). This salient gap is the starting point of our investigation in this paper -which turns out to reach quite a bit beyond the gap itself.Following prior work [Ahmadi et al., 2023 , Cohen et al., 2024] , we study the following standard and general model of online strategic classification: we have a (possibly infinite) feature space, equipped with a manipulation graph defined over it. An edge between two feature vectors x 1 and x 2 means that an agent whose true features are x 1 can pretend to have features x 2 , and in fact, the agent would have incentives to do so if the label assigned to x 2 by the classifier is better than that assigned to the true features x 1 . At each time step, the decision maker commits to a classifier (which may depend on observations from previous interactions), and an agent arrives and observes the classifier. The agent then responds to the classifier by reporting (possibly nontruthfully) a feature vector that leads to the most desirable label subject to the manipulation graph, i.e., the reported feature vector must be a neighbor of the agent's true feature vector. The decision maker then observes the reported feature vector, as well as whether the label assigned to that feature vector matches the agent's true label.An instance-optimal regret bound through the strategic Littlestone dimension. Our first main finding is an instance-optimal regret bound for online strategic classification in the realizable setting, when randomization is not allowed (we will discuss the role of randomization in Section 6). In this setting, there is a predefined hypothesis class of classifiers, in which there must exist one classifier that assigns all agents their true labels under manipulation. The decision maker, knowing that a perfect classifier exists in this class, tries to learn it on the fly while making as few mistakes as possible in the process. Naturally, the richer this hypothesis class is, the harder the decision maker's task will be (e.g., one extreme is when the hypothesis class contains only one classifier, and the decision maker knows a priori that that classifier must be perfectly correct, and the optimal regret is 0). Thus, the optimal regret must depend on the richness of the hypothesis class. Similarly, one can imagine that the optimal regret must also depend on the manipulation graph.Previous work [Ahmadi et al., 2023 , Cohen et al., 2024] has established regret bounds for this setting based on various complexity measures of the hypothesis class and the manipulation graph, including the size and the (classical) Littlestone dimension [Littlestone, 1988] of the hypothesis class, as well as the maximum out-degree of the manipulation graph. However, the optimality (when applicable) of these bounds only holds under the assumption that the mistake bound must be parametrized as a function on the classical Littlestone dimension and/or the graph's out-degree. However, these bounds are not tight for all instances, as there exist problem instances that are learnable where all these parameters are infinite.To address the above issue, we introduce a new combinatorial complexity measure that generalizes the classical Littlestone dimension into strategic settings. Conceptually, the new notion also builds on the idea of "shattered trees", which has proved extremely useful in classical settings. However, the asymmetry introduced by strategic behavior3 demands a much more delicate construction of shattered trees (among other intriguing implications to be discussed in Section 3). We show that the generalized Littlestone dimension captures precisely the optimal regret of any deterministic learning algorithm given a particular hypothesis class and a manipulation graph, thereby providing a complete characterization of learnability in this setting. Being instance-optimal, our bound strengthens and unifies all previous bounds for online strategic classification in the realizable setting.An improved regret bound for the agnostic case. We then proceed to the agnostic setting, where no hypothesis necessarily assigns correct labels to all agents. The regret is defined with respect to the best hypothesis in hindsight. Compared to the classical (i.e., non-strategic) setting, the main challenge is incomplete information: since the learner cannot observe original features, upon observing the behavior of an agent under one classifier, it is not always possible to counterfactually infer what would have been observed if the learner used another classifier.To understand why this can be a major obstacle, recall some high-level ideas behind the algorithms for classical agnostic online classification (see, e.g., [Ben-David et al., 2009] ). The key is to construct a finite set of "representative" experts out of the potentially infinite set of hypotheses, such that the best expert performs almost as well as the best hypothesis in hindsight. An agnostic learner then runs a no-regret learning algorithm (such as multiplicative weights) on the expert set, which in the long run matches the performance of the best expert, and in turn of the best hypothesis.The partial information challenge appears in both steps of the above approach. First, to construct the set of representative experts, the learner needs to simulate the observation received by each hypothesis, had that hypothesis been used to label the strategic agents. Second, the no-regret algorithm on the expert set also needs to counterfacurally infer the agent's response to each expert. To circumvent both issues, we design a nuanced construction of the representative set of experts that effectively "guesses" each potential direction of the agent's manipulation. We then run the biased voting approach introduced in [Ahmadi et al., 2023] on the finite set of experts, which enjoys regret guarantees in the strategic setting even with partial information. Combined with our regret bound for the realizable setting, this approach yields an improved bound for the agnostic setting.Learning with unknown manipulation graphs. Our last result focuses on relaxing the assumption that the learner has perfect knowledge about the manipulation graph structure. Instead, following previous works [Lechner et al., 2023 , Cohen et al., 2024] , we model their knowledge about the manipulation graph using a pre-defined graph class, which to some degree reflects the true set of feasible manipulations. In this setting, our work is the first that provides positive results when the learner only observes features after manipulation. We start with the realizable setting where the manipulation graphs are consistently modeled by the same (unknown) graph in the class. In this setting, we provide a more careful construction of the representative experts to account for the additional challenge of unknown graphs. Combing this construction with re-examining the effectiveness of the biased voting approach [Ahmadi et al., 2023] when the input graph is a overlyconservative estimate of the true graph, we obtain the first regret bound in this setting that is approximately optimal (up to logarithmic factors) in certain instances. We also extend our results to fully agnostic settings where the agents in each round manipulates according to a potentially different graph, and the best graph in the class has nonzero error in modeling all the manipulations.There is a growing line of research that studies learning from data provided by strategic agents [Dalvi et al., 2004 , Dekel et al., 2008 , Brückner and Scheffer, 2011] . The seminal work of Hardt et al. [2016] introduced the problem of strategic classification as a repeated game between a mechanism designer that deploys a classifier and an agent that best responds to the classifier by modifying their features at a cost. Follow-up work studied different variations of this model, in an online learning setting [Dong et al., 2018 , Chen et al., 2020 , Ahmadi et al., 2021] , incentivizing agents to take improvement actions rather than gaming actions [Kleinberg and Raghavan, 2020 , Haghtalab et al., 2020 , Alon et al., 2020 , Ahmadi et al., 2022] , causal learning [Bechavod et al., 2021 , Perdomo et al., 2020] , screening processes [Cohen et al., 2023] , fairness [Hu et al., 2019] , etc.Two different models for capturing the set of plausible manipulations have been considered in the literature. The first one is a geometric model, where the agent's best-response to the mechanism designer's deployed classifier is a state within a bounded distance (with respect to some ℓ p norm) from the original state, i.e. feature set [Dong et al., 2018 , Chen et al., 2020 , Shao et al., 2024 , Sundaram et al., 2023 , Ghalme et al., 2021 , Haghtalab et al., 2020] . In the second model, introduced by Zhang and Conitzer [2021] there is a combinatorial structure, i.e. manipulation graph, that captures the agent's set of plausible manipulations. This model has been studied in both offline PAC learning [Lechner and Urner, 2022 , Zhang and Conitzer, 2021 , Lechner et al., 2023] and online settings [Ahmadi et al., 2023] . In a recent work, Lechner et al. [2023] consider this problem in an offline setting where the underlying manipulation is unknown and belongs to a known family of graphs. Our work improves the results given by [Ahmadi et al., 2023] in the online setting and also extends their results to the setting where the underlying manipulation is unknown and belongs to a known family of graphs.Our work is also closely related to that of Cohen et al. [2024] , with two main points of distinction. First, in the realizable setting, their bound is shown to be optimal for a specific instance, whereas our bound is instance-wise optimal. Second, in both the agnostic and the unknown graph settings, they assume that agents' original features are observable before the learner makes decisions, whereas our algorithm only requires access to post-manipulation features.Finally, our work is also tangentially connected to several recent advances in understanding multiclass classification under bandit feedback, e.g., [Raman et al., 2024 , Filmus et al., 2024] , as the false-positive mistake types can be treated as multiple labels at a very abstract level. However, an additional challenge in the strategic setting is that the learner needs to choose a classifier without observing the original instance to be labeled. 
strategic classification.: 
 Let X be a space of feature vectors, Y = {-1, 1} be the binary label space, and H : X → Y be a hypothesis class that is known to the learner (also referred to as "decision-makers"). In the strategic classification setting, agents prefer positive labels over negative labels, and they may manipulate their features within a predefined range to receive a positive label. We use the manipulation graphs introduced by [Zhang and Conitzer, 2021, Lechner and Urner, 2022] to model the set of feasible manipulations. The manipulation graph G(X , E) is a directed graph in which each node corresponds to a feature vector in X , and each edge (x 1 , x 2 ) ∈ E ⊆ X 2 represents that an agent with initial feature vector x 1 can modify their feature vector to x 2 . For each x ∈ X , we use N + G (x) to denote the set of out-neighbors of x in G, excluding x itself, andN + G [x] to denote the out-neighbors including x. Formally, N + G (x) = {x ′ ∈ X \ {x} | (x, x ′ ) ∈ E} and N + G [x] = {x} ∪ N + G (x). Similarly, we use N - G (x) and N - G [x] to denote respectively the exclusive and inclusive in-neighborhood of x.Agents' utility and the manipulation rule. Given a manipulation graph G(X , E) and a classifier h ∈ Y X , an agent with initial features x ∈ X aims to maximize their utility by potentially manipulating their features to a different x ′ . The agent's utility function util G,h (x, x ′ ) is defined asutil G,h (x, x ′ ) = h(x ′ ) -∞ • 1{(x, x ′ ) ∈ E} ,where the agent's utility is the classification outcome h(x ′ ) minus the manipulation cost associated with changing features from x to x ′ . For the classification outcome, agents receive utility +1 if the classifier h labels x ′ as positive and -1 otherwise. For the manipulation cost, moving from x to x ′ incurs no cost if the two features are connected by an edge in G, but when x and x ′ are not connected (i.e., (x, x ′ ) ̸ ∈ E), the manipulation incurs an infinite cost, effectively making such a manipulation infeasible. As a result, an agent with initial features x would move to some x ′ in the inclusive neighborhood N + G [x] that is labeled as positive by h, if such a node exists. Formally, the set of best response features from x, denoted by BR G,h (x), is defined asBR G,h (x) ≜ {x ′ | util G,h (x, x ′ ) = +1} = N + G [x] ∩ {x | h(x) = +1}. If, however, the set BR G,h (x) is empty -indicating that the entire out-neighborhood N + G [x]is labeled as negative by h -then the agent is assumed to not manipulate their features and remain at x. In addition, when there are multiple nodes in BR G,h (x), the agent may select any node arbitrarily. We do not require the selection to be consistent across rounds or to follow a pre-specified rule. Our results specifically focus on the learner's mistakes against worst-case (adversarial) selections by the agent. 4 Finally, the manipulated feature vector is denoted by br G,h (x).The labels induced by the manipulated feature vectors br G,h (x) are captured by effective classifiers h G , formally defined ash G (x) ≜ h(br G,h (x)) = +1, if ∃v ∈ N + G [x], s.t. h(v) = +1; -1, otherwise.Online learning. We consider an online strategic classification setting modeled as a repeated game between the learner (aka the decision maker) and an adversary over T rounds, where the learner make decisions according to an online learning algorithm A. At each round t ∈ [T ], the learner first commits to the classifier h t ∈ Y X (not necessarily restricted to H) that is generated by A. The adversary then selects an agent (x t , y t ) where x t ∈ X is the original feature vector and y t ∈ Y is the true label. In response to h t , the agent manipulates their features from x t to v t = br G,h (x t ). Consequently, the learner observes the manipulated features v t (instead of x t ), and incurs a mistake if y t ̸ = h t (v t ). We use S = (x t , y t ) t∈[T ] to denote the sequence of agents.The learner aims to minimize the Stackelberg regret on S with respect to the optimal hypothesis h ⋆ ∈ H had the agents responded to h ⋆ :Regret A (S, H, G) ≜ T t=1 1{h t (br G,ht (x t )) ̸ = y t } -min h ⋆ ∈H T t=1 1{h ⋆ (br G,h ⋆ (x t )) ̸ = y t } .We call a sequence S realizable with respect to H if the optimal-in-hindsight hypothesis h ⋆ ∈ H achieves zero mistakes on S. Specifically, this means that for all (x t , y t ) in the sequence S, we havey t = h ⋆ (br G,h ⋆ (x t )) = h ⋆ G (x t ).In such cases, the learner's regret coincides with the number of mistakes made. We use Mistake A (H, G) to denote the maximal number of mistakes that A makes against any realizable sequence with respect to class H and graph G. A deterministic algorithm is called minmax optimal or instance-optimal if achieves the minimal Mistake A (H, G) across all deterministic algorithms5 . We denote this optimal mistake bound by M(H, G) ≜ inf A deterministic Mistake A (H, G).In this section, we revisit the classical online binary classification setting where the agents are unable to strategically manipulate their features. This setting can be viewed as a special case of strategic classification where the manipulation graph G consists solely of isolated nodes. We will introduce the characterization of the optimal mistake in this classical setting -known as the Littlestone Dimension -which inspires our analysis in the strategic setting. Definition 2.1 (H-Shattered Littlestone Tree). A Littlestone tree shattered by hypothesis class H of depth d is a binary tree where:• (Structure) Nodes are labeled by X and each non-leaf node has exactly two outgoing edges that are labeled by +1 and -1, respectively.• (Consistency) For every root-to-leaf pathx 1 y1 -→ x 2 y2 -→ • • • x d y d-→ x d+1 where x 1 is the root node and each y t is the edge connecting x t and x t+1 , there exists a hypothesis h ∈ H that is consistent with the entire path, i.e., ∀t ≤ d, h(x t ) = y t .The above tree structure intuitively models an adversary's strategy to maximize the learner's mistakes, where each node x t represents the unlabeled instance to be presented to the learner, and y t represents the type of mistake (either a false positive or a false negative) that the adversary aims to induce. For example, if the learner predicts the label of x t to be y t = +1, then the adversary will declare y t = -1, enforce a false positive mistake, and choose the next instance x t+1 as the children of the current node along the -1 edge. In addition, the consistency requirement guarantees that the resulting input sequence is realizable by some classifier in H. Definition 2.2 (Littlestone Dimension). The Littlestone dimension of class H, denoted as Ldim(H), is the maximum integer d such that there exists an H-shattered Littlestone of depth d.The interpretation of the true structure immediately implies that the mistake of any algorithm should be lower bounded by Ldim(H). Moreover, a seminal result by Littlestone [1988] also showed that an online learning algorithm known as the Standard Optimal Algorithm (SOA, see Algorithm 2 in Appendix A) can achieve this lower bound. Together, they form a complete characterization of the optimal mistake bound in the classical setting, which we summarize in the following proposition. Proposition 2.1 (Optimal Mistake Bound [Littlestone, 1988] ). Let M(H) be the optimal mistake in the classical online learning setting, then M(H) = Ldim(H).In the next section, we will discuss the challenges of extending Littlestone's characterization to the strategic setting, and present our solution. 
the strategic littlestone dimension: 
 In this section, we will introduce a new combinatorial dimension called the Strategic Littlestone Dimension, and show that it characterizes the minmax optimal mistake bound for strategic classification.Inspired by the classical Littlestone dimension, we hope to use a tree structure to model an adversary's strategy for selecting agents (x t , y t ), where nodes serve as (proxies of) the initial feature vector of each agent, and edges represent the types of mistakes that the adversary can induce. However, since agents can strategically manipulate their features, the potential mistakes associated with the same initial feature vector could manifest in many more types depending on the learner's choice of classifiers. Specifically, let x be the initial feature vector. Then a mistake associated with x might be observed as a false negative mistake at node x (denoted as (x, +1) where x is the observable node and +1 is the true label), or as a false positive mistake at any outgoing neighbor v of x (denoted as (v, -1) accordingly). Therefore, an adversary's strategy should accommodate all such possibilities, which necessitates the strategic Littlestone tree to contain branches representing all potential mistake types.Another challenge is caused by the mismatch of the information available to the learner and the adversary. Since the learner only observes manipulated features instead of the true ones, the amounts of information carried by false positive and false negative mistakes are inherently asymmetric. False negatives provide full-information feedback as the manipulated and original features are identical. However, false positives introduce uncertainty about the original features, which could potentially be any in-neighbor of the observed one. As a result, a hypothesis is deemed "consistent" with a false positive observation as long as it can correctly label any one of the potential original nodes. Now we formally introduce the strategic Littlestone tree with adapted branching and consistency rules tailored for strategic classification. See Figure 1 for a pictorial illustration. Definition 3.1 (H-Shattered Strategic Littlestone Tree). A Strategic Littlestone tree for hypothesis class H under graph G with depth d is a tree where:• (Structure) Nodes are labeled by X . The set of outgoing edges from each non-leaf node x are: one false negative edge (x, +1), and a set of false positive edges{(v, -1) | v ∈ N + G [x]}. • (Consistency) For every root-to-leaf path x ′ 1 (v1,y1) ----→ x ′ 2 (v2,y2) ----→ • • • x ′ d (v d ,y d ) ----→ x ′ d+1 where x ′1 is the root node and (v t , y t ) ∈ X × {±1} is the edge that connects x ′ t and x ′ t+1 , there exists a hypothesis h ∈ H that is consistent with the entire path. Specifically, ∀t ≤ d,∃x t s.t. h G (x t ) = y t , where x t satisfies x t = v t if y t = +1, and x t ∈ N -1 G [v t ] if y t = -1 . Definition 3.2 (Strategic Littlestone Dimension).The Strategic Littlestone Dimension of a hypothesis class H under graph G, denoted with SLdim(H, G), is defined as the largest nonnegative integer d for which there exists a Strategic Littlestone tree of depth d shattered by H under graph G.Theorem 3.1 (Minmax optimal mistake for strategic classification). For any hypotheses class H and manipulation graph G, the minmax optimal mistake in the realizable setting is captured by the strategic Littlestone dimension, i.e., M(H, G) = SLdim(H, G).We divide the proof of Theorem 3.1 into two parts: the lower bound direction is established in Theorem 3.2, and the upper bound direction is established in Theorem 3.3. Theorem 3.2 (Lower bound part of Theorem 3.1). For any pair of hypothesis class H and manipulation graph G, any deterministic online learning algorithm A must suffer a mistake lower bound ofMistake A (H, G) ≥ SLdim(H, G).Proof sketch of Theorem 3.2. Let T be a strategic Littlestone tree for (H, G) with depth d. We will show that for any deterministic algorithm A, there exists an adversarial sequence of agents x ′ 1 x ′ 2 (v1, y1) • • • • • • • • • • • • x ′ 3 (v2, y2) • • •(v 1 ,y 1 ) ----→ x ′ 2 (v 2 ,y 2 ) ----→ x ′3 is an example root-to-leaf path. In this path, the first observation (v1, y1) is a false positive, which satisfies v1 ∈ N + G [x ′ 1 ] and y1 = -1; the second observation (v2, y2) is a false negative, which satisfies v2 = x ′ 2 and y2 = +1.S = (x t , y t ) t∈ [d] such that A is forced to make a mistake at every round. We construct the sequenceS by first finding a path x ′ 1 (v1,y1) ----→ x ′ 2 (v2,y2) ----→ • • • x ′ d (v d ,y d )----→ x ′ d+1 in tree T which specifies the types of mistakes that the adversary wishes to induce, then reverse-engineering this path to obtain the sequence of initial feature vectors before manipulation that is realizable under H. We remark that the need for reverse-engineering is unique to the strategic setting, which is essential in resolving the information asymmetry between the learner and the adversary regarding the true features. We formally prove this theorem in Appendix B.1.In the remainder of this section, we present an algorithm called the Strategic Standard Optimal Algorithm (SSOA) that achieves the instance-optimal mistake bound of SLdim(H, G). We first define some notations. For any hypothesis sub-class F ⊂ H and an observable labeled instance(v, y) ∈ X × Y, we use F (v,y) Gto denote the subset of F that is consistent with (v, y) under manipulation graph G. We refer to the consistency rule defined in Definition 3.1, i.e., for all v ∈ X ,F (v,+1) G and F (v,-1) Gare defined respectively as:F (v,+1) G ≜ {h ∈ F | h G (v) = +1}; F (v,-1) G ≜ {h ∈ F | ∃x ∈ N - G [v] s.t. h G (x) = -1}.We present SSOA in Algorithm 1 and prove its optimality in Theorem 3.3. The high-level idea of SSOA is similar to the classical SOA algorithm (Algorithm 2): it maintains a version space of classifiers consistent with the history, and chooses a classifier h t in a way that guarantees the "progress on mistakes" property. This means that the (strategic) Littlestone dimension of the version space should decrease whenever a mistake is made.However, designing h t to satisfy this property in a strategic setting is more challenging because the potential types of mistakes depend on h t 's labeling in the neighborhoodN + G [x t ], where x t is unobservable. If we directly optimize the labelings on N + G [x] for each x independently, the resulting classifier may suggest self-contradictory labelings to the nodes in the overlapping parts of N + G [x] and N + G [x ′ ] for different x and x ′ . Instead, the learner needs to choose a single h t that simultaneously guarantees the "progress on mistakes" property for all possible x t and their neighborhoods.In the following, we will show that this challenge can be resolved by choosing a classifier h t that labels each node x only based on whether a false positive observation (x, -1) can decrease the strategic Littlestone dimension, as described in Line 3 of Algorithm 1.Theorem 3.3 (Upper bound part of Theorem 3.1). The SSOA algorithm (Algorithm 1) achieves a maximal mistake bound of Mistake SSOA (H, G) ≤ SLdim(H, G).Remark 3.4 (Comparison with previous results). Since the mistake bound of SSOA is shown to be instance-optimal across all deterministic algorithms, it improves upon the bounds established by Ahmadi et al. [2023] , Cohen et al. [2024] , which both depend on the maximum out-degree of the graph G. Furthermore, we show in Appendix B.2 that the gap between their bounds and ours could be arbitrarily large. An extreme example is the complete graph G supported on an unbounded domain, where SLdim(H, G) = 1 but both previous bounds are ∞.Proof of Theorem 3.3. It suffices to prove that if SSOA makes a mistake at round t, then the strategic Littlestone dimension of version space H t (maintained by the SSOA algorithm in Line 5) must ∀x ∈ X , h t (x) ← +1, if SLdim (H t-1 ) (x,-1) G , G < SLdim(H t-1 , G);-1, otherwise.;Observe the manipulated feature vector v t and the true label y t ;If a mistake occurs (ht (v t ) ̸ = y t ), update H t ← (H t-1 ) (vt,yt) G . Otherwise H t ← H t-1 . end decrease by at least 1, namely SLdim(H t , G) ≤ SLdim(H t-1 , G) -1. For notational convenience, let d = SLdim(H t-1 , G).False positives. We start with the case where SSOA makes a false positive mistake, i.e., h t (v t ) = +1 but y t = -1. According to the definition of classifier h t and the update rule of version space H t , we immediately obtainSLdim(H t , G) = SLdim (H t-1 ) (vt,-1) G , G < SLdim(H t-1 , G) ⇒ SLdim(H t , G) ≤ d -1.False negatives. Then we consider the case where SSOA makes a false negative mistake, i.e., h t (v t ) = -1 but y t = +1. For the sake of contradiction, assume that the strategic Littlestone di-mension does not decrease, i.e., SLdim(H t , G) = SLdim (H t-1 ) (vt,+1) G , G = d.This assumption implies that there exists a strategic Littlestone tree T that is shattered by(H t-1 ) (vt,+1) G and of depth SLdim(H t-1 , G).Since the agent is classified as negative, it must be the case that the agent has not manipulated (i.e., x t = v t ), and the entire outgoing neighborhood N + G [x t ] is labeled as negative by h t . Therefore, according to the definition of h t , for all v ∈ N + G [x t ], we have SLdim (H t-1 )(v,-1) G, G = d, which implies that there also exists a strategic Littlestone tree T v of depth d that is shattered by(H t-1 ) (v,-1) G .Now consider the tree T ′ with root x t , subtree T on the false negative edge (x t , +1), and subtree T v on each false positive edge (v, -1) for all v ∈ N + G [x t ]. Since we have argued that each subtree has depth d, the overall depth of T ′ is d + 1. We claim that T ′ is shattered by H t-1 . In fact, for all root-to-leaf paths in T ′ , the first observation is guaranteed to be consistent with all hypotheses in the subclass for the subtree, and the consistency of each subtree ensures the existence of a hypothesis that makes all subsequent observations realizable.We have thus constructed a strategic Littlestone tree T ′ that is shattered by H t-1 and of depth d + 1. However, this contradicts with the assumption that SLdim(Ht-1 , G) = d. Therefore, it must follow that SLdim(H t , G) ≤ d -1 = SLdim(H t-1 , G) -1, which in turn proves Mistake SSOA (H, G) ≤ SLdim(H, G).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
agnostic setting: 
 In this section, we study the regret bound in the agnostic setting. Recall that benchmark is defined as the minimum number of mistakes that the best hypothesis in H makes, i.e., OPT ≜min h ⋆ ∈H t∈[T ] 1{h ⋆ (br G,h ⋆ (x t )) ̸ = y t }.We will present an algorithm that has vanishing regret compared to ∆ + G • OPT whenever the strategic Littlestone dimension is bounded, where ∆ + G is the maximum out-degree of G. Inspired by the classical reduction framework proposed by Ben-David et al. [2009] , our algorithm aims to reduce the agnostic problem to that of strategic online learning with expert advice by constructing a finite number of representative experts that performs almost as well as the potentially unbounded hypothesis class. The problem with a finite expert set can then be solved using the biased weighted voting algorithm proposed by Ahmadi et al. [2023] . However, establishing the reduction turns out to be more challenging in the strategic setting, as the learner can only observe manipulated features instead of the original ones. We address this problem by designing the experts to "guess" every possibile direction the original node could have come. We present our algorithms (Algorithms 3 and 4) in Appendix C and analyze their regret in Theorem 4.1. Theorem 4.1. For any adaptive adversarial sequence S of length T , the Agnostic Online Strategic Classification algorithm (Algorithm 3) has regret boundRegret(S, H, G) ≤ O ∆ + G • OPT + ∆ + G • SLdim(H, G) • (log T + log ∆ - G ) ,where ∆ + G (resp. ∆ - G ) denotes the maximum out-degree (resp. in-degree) of graph G. Remark 4.2. Ahmadi et al. [2023] showed that there exists instances in which all deterministic algorithms must suffer regret Ω(∆ + G •OPT), which means the first term in the above bound is necessary. The second term connects to our instance-wise lower bound of SLdim(H, G) in Theorem 3.2.Proof sketch of Theorem 4.1. We use E to denote the set of experts constructed in Algorithm 4, and define OPT E as the minimum number of mistakes made by the best expert e ⋆ ∈ E, had the agents responded to e ⋆ . Then the Biased Weighted Majority Vote algorithm from Ahmadi et al. [2023] guarantees that the number of mistakes made by Algorithm 3 is at most∆ + G • OPT E + ∆ + G • log |E|.According to our construction of experts, the total number of experts satisfies log |E| ≤ logm≤d T m • (∆ - G ) m ≤ O(d • (log T + log ∆ - G )), where d = SLdim(H, G) is the strategic Littlestone dimension. Therefore, it suffices to show that OPT E is not too much larger than OPT-in other words, the set of experts E are representative enough of the original hypothesis class H in their ability of performing strategic classification. We use the following lemma, which we prove in Appendix C by establishing the equivalence between the SSOA instance running on the sequence labeled by the effective classifier and the SSOA instance simulated by a specific expert. Lemma 4.3 (Experts are representative). For any hypothesis h ∈ H and any sequence of agents S, there exists an expert e h ∈ E that makes at most SLdim(H, G) more mistakes than h. 
unknown manipulation graph: 
 In this section, we generalize the main settings to relax the assumption that the learner has full knowledge about the underlying manipulation graph G. Instead, we use a graph class G to capture the learner's knowledge about the manipulation graph. In Section 5.1, we begin with the realizable graph class setting, where the true manipulation graph remains the same across rounds and belongs to the family G. We then study the agnostic graph class setting in Section 5.2, where we drop both assumptions and allow our regret bound to depend on the "imperfectness" of G. In both cases, we assume the hypothesis class H is also agnostic, which encompasses the setting where H is realizable.In this section, we assume that there exists a perfect (but unknown) graph G ⋆ ∈ G, such that each agent (x t , y t ) ∈ S manipulates according to G ⋆ . We define the benchmark OPT H to be the optimal number of mistakes made by the best h ⋆ ∈ H assuming that each agent best responds to h ⋆ according to G ⋆ . Formally, OPT H ≜ min h ⋆ ∈H 1{h ⋆ (br G ⋆ ,h ⋆ (x t )) ̸ = y t }. Same to our main setting, we assume that the learner only observes the post-manipulation features v t = br G ⋆ ,ht (x t ) after they commit to classifier h t , but cannot observe the original features x t .Our algorithm (Algorithm 6) for this setting leverages two main ideas. First, to overcome the challenge that G ⋆ is unknown to the experts, we blow up the number of experts by a factor of |G| and let each expert simulate their own SSOA instance according to some internal belief of G ⋆ . Since the regret bound depends logarithmic on the number of experts, this only introduces an extra log |G| term, which has been shown by Cohen et al. [2024] to be unavoidable even when the learner has access to the original features.Our second idea involves re-examining the correctness of Algorithm 5 for bounded expert class to the scenario where the input G is a pessimistic estimate of the true graph G ⋆ , i.e., G contains all the edges in G ⋆ but potentially some extra edges. This allows us to use G union whose edge set is taken to be the union of all egdes in G. Combining these two ideas, we present our algorithm and establish its regret bound (Theorem 5.1) in Appendix D. Theorem 5.1. For any realizable graph class G and any adaptive adversarial sequence S of length T , Algorithm 6 has regret boundRegret(S, H, G) ≤ O ∆ + G • OPT H + d G • (log T + log ∆ - G ) + log |G| ,where d G ≜ max G∈G SLdim(H, G) is the maximum strategic Littlestone dimension for all graphs in G, ∆ + G ≜ ∆ + Gunion is the maximum out-degree of G union (i.e., the union of graphs in G), and ∆ - G ≜ max G∈G ∆ - G is the maximum max in-degree over graphs in G. Remark 5.2 (Implications in the realizable setting). In the realizable setting where OPT H = 0, Theorem 5.1 implies a mistake bound ofÕ(∆ + G •d G +log |G|).This bound is optimal up to logarithmic factors due to a lower bound proved by Cohen et al. [2024, Proposition 14] . They constructed an instance with |G| = |H| = Θ(n) in which any deterministic algorithm makes Ω(n) mistakes. In this instance, our bound evaluates to be Õ(n) since ∆ + G = Θ(n) and d G = 1.In this section, we consider a fully agnostic setting where each agent (x t , y t ) may behave according to a different manipulation graph G t ⊆ G union . We define the benchmark OPT G to count the number of times that the best graph G ⋆ ∈ G fails to model the local manipulation structure under G t , and OPT H is defined as in Section 5.1, using the graph G ⋆ that achieves OPT G .OPT G ≜ minG ⋆ ∈G T t=1 1 N + G ⋆ [x t ] ̸ = N + Gt [x t ] , OPT H ≜ min h ⋆ ∈H T t=1 1{h ⋆ (br G ⋆ ,h ⋆ (x t ) ̸ = y t )} 6 .Assuming access to an upper bound N of OPT G , we present Algorithm 7 that achieves a regret bound of Õ ∆ + G (N + OPT H + d G ) , as shown in Theorem D.2. We additionally apply the standard doubling trick to remove the requirement of knowing N . More details can be found in Appendix D.2. 
discussion and future research: 
 Improved bounds for the agnostic setting. An immediate direction for future research is tightening our bounds in the agnostic setting under known manipulation graph. Note that our upper bound is Õ ∆ + G • (OPT + SLdim(H, G) whereas the lower bounds are Ω(∆ + G • OPT) from Ahmadi et al. [2023] and Ω(SLdim(H, G)) from Theorem 3.2. The extra ∆ + G factor is introduced by the strategic learning-with-expert-advice algorithm, for which all known results have the dependency on ∆ + G . Randomized learners. Our results mainly focus on deterministic learners. It is an important open problem to find the corresponding characterizations for randomized learners. In Appendix E, we provided a family of realizable instances that witnesses a super-constant gap between the optimal mistake of deterministic and randomized algorithms. This is in contrast to their classical counterparts which are always a factor of 2 within each other. One challenge (among others) of proving a tight lower bound in the randomized setting is controlling the learner's information about the agents' original features, as the adversary can no longer "look-ahead" at an algorithm's future classifiers.We present the SOA algorithm in Algorithm 2. (H, G) ≥ SLdim(H, G).Proof of Theorem 3.2. Recall that to construct an adversarial sequence of agents S = (x t , y t ) t∈ [d] such that A is forced to make a mistake at every round, we will first find a pathx ′ 1 (v1,y1) ----→ x ′ 2 (v2,y2) ----→ • • • x ′ d (v d ,y d ) ----→ x ′d+1 in tree T which specifies the types of mistakes that the adversary wishes to induce, then reverse-engineering this path to obtain the sequence of initial feature vectors before manipulation that is realizable under H.Constructing the path. We initialize x ′ 1 to be the root of the tree T . For all t ≤ d and given the history (partial path)x ′ 1 (v1,y1) ----→ • • • x ′ t-1 (vt-1,yt-1) -------→ x ′t , we find the edge (v t , y t ) and the next node x ′ t+1 as follows: run the online learning algorithm A for t -1 rounds with inputs (v t ′ , y t ′ ) t ′ ≤t-1 , and let h t be the outputted classifier at round t. We examine the labels of h t in the out-neighborhoodN + G [x ′ t ]under graph G and consider the following two cases. Case 1: False negatives. If all the feature vectors in N + G [x ′ t ] is labeled as negative by h t , then the adversary will induce a false negative mistake by letting the post-manipulation feature vector be x ′ t (which is same as the original feature vector x t ) and the true label be positive, i.e., (v t , y t ) ≜ (x ′ t , +1). We then choose the next node x ′ t+1 to be the child of x ′ t along the false negative edge(x ′ t , +1) in T . Case 2: False positives. If there exists v ∈ N + G [x ′ t ] such that h t (v) = +1, then the adversary will induce a false positive mistake that is observed at v with true label -1, i.e., (v t , y t ) ≜ (v, -1). However, we remark that the true features x t may be chosen as a different node in N - G [v t ] to ensure realizability, which we will discuss in the reverse-engineering part. We choose x ′ t+1 to be the child of x ′ t along the false positive edge (v, -1) in T .Reverse-engineering. Repeating the above procedure for all t ≤ d gives us the pathx ′ 1 (v1,y1) ----→ • • • x ′ d (v d ,y d ) ----→ x ′ d+1, where each y t already specifies the true labels of each agent. It remains to select the initial features (x t ). Since T is shattered by H, the consistency part of Definition 3.1 guarantees the existence of h ∈ H such that ∀t < d, there exists x t that satisfies h G (x t ) = y t , wherex t = v t = x ′ t if y t = -1 and x t ∈ N - G [v t ] if y t = +1.We let those (x t ) t∈[d] be agents' true feature vectors. It then follows that the sequence of agents S = (x t , y t ) t∈ [d] is realizable under (H, G) and indeed induces a mistake observed as (v t , y t ) at every round t ∈ [d].Finally, if SLdim(H, G) < ∞, then the above argument with d = SLdim(H, G) proves the theorem. When SLdim(H, G) = ∞, the above argument shows Mistake A (H, G) ≥ d for all d ∈ N, which implies that Mistake A (H, G) = ∞ by driving d → ∞. The proof is thus complete.In this section, we consider two families of instances (H, G) in which our mistake bound SLdim(H, G) from Theorem 3.3 significantly improves the previous bounds. We compare with upper bounds O(∆ + G • log |H|) from [Ahmadi et al., 2023] and Õ(∆ + G • Ldim(H)) from [Cohen et al., 2024] , where Ldim(H) denotes the classical Littlestone dimension of hypothesis class H. We focuses on comparing with the latter bound, since it can be shown that Ldim(H) ≤ log |H| for all H.Graphs with a large clique. Our first example involves graphs with a very large clique. The main idea is that the densest part of graph may turn out to be very easy to learn since there are only a few effective hypotheses supported on it. On the other hand, the harder-to-learn part of the hypothesis class may be supported on a subgraph with a much smaller maximum degree. For this reason, the previous bounds that directly multiply the complexity of the entire graph (e.g., ∆ + G ) with the complexity of the entire hypothesis class would be suboptimal.Let (G ′ , H ′ ) be a pair of manipulation graph and hypothesis class, for which we haveSLdim(H, G ′ ) ≤ O(∆ + G ′ • Ldim(H ′) since the strategic Littlestone dimension is a lower bound of all valid mistake bounds (Theorem 3.2). Let N ≫ max{|G ′ |, |H ′ |} be a very large integer, and K N be a clique of size N . We assume that the vertex set of K N is disjoint from that of G ′ . We take the hypothesis class on K N to be the set of all functions, i.e., {±1}K N . Let G = G ′ ∪ K N and H = H ′ × {±1} N .• Previous bound: Since ∆ + G = N and Ldim(H) ≥ Ldim(H ′ ). Therefore, the bound in [Cohen et al., 2024] is of order (ignoring logarithmic factors)∆ + G • Ldim(H) ≥ Ω(N • Ldim(H ′ )).• Our bound based on the strategic Littlestone dimension: By Theorem 3.2, SLdim(H, G) lower bounds the mistake bound achievable by any deterministic algorithm. Consider the following deterministic algorithm that uses two independent algorithms A 1 and A 2 to learn on each of the disjoint subgraphs G ′ and K N . We will choose A 1 to be the Red2Online-PMF(SOA) algorithm proposed by Cohen et al. [2024] , and A 2 be the algorithm that predicts all nodes negative until a mistake happens, at which point flips the prediction to positive on all nodes. Since the effective classifiers on K N is either all positive or all negative, A 2 makes at most 1 mistake. We haveSLdim(H, G) ≤ Mistake A1 (H ′ , G ′ ) + Mistake A2 ({±1} K N , K N ) ≤ Õ(∆ + G ′ • Ldim(H ′ )).• Improvement. As a result, for this instance, the gap between these two algorithms is lower bounded by N/∆ + G ′ , which can be arbitrarily large by taking N → ∞.Random graphs in G(n, p), H = {±1} n . Our second example considers random graphs G ∼ G(n, p), in which every (undirected) edge is realized independently with probability p. We will show that when p = ω(1/n) (when the random graph is "effectively" dense), with high probability over G ∼ G(n, p), the strategic Littlestone dimension significantly improves previous bounds.Since H is extremely expressive (contains all functions), we have log |H| = Ldim(H) = n. However, we will show that even after strengthening the previous bounds by applying it on the reduced-size hypothesis class H G ⊆ H-which contains only one hypothesis in each equivalence class that induces the same effective hypothesis h G -the strategic Littlestone dimension SLdim(H, G) still offers significant improvement over ∆ + G • Ldim( H G ).• Previous bound: By concentration, ∆ + G ≥ Ω(np) with high probability. Moreover, with high probability, the independence number α(G) satisfies α(G) ≥ Ω(log(np)/p) [Frieze, 1990] . Let I(G) be the independent set with size α(G) and consider the projection of H G onto I(G). Since there are no edges inside, the effective hypothesis coincides with the original hypothesis, therefore ( H G ) I(G) contains all functions that maps from I(G) to {±1}, which has classical Littlestone dimension |I(G)| = α(G). As a result, we have that with high probability,∆ + G • Ldim( H G ) ≥ Ω(np)• Ω(log(np)/p) ≥ Ω(n log(np)).• Our bound based on the strategic Littlestone dimension: Again, SLdim(H, G) lower bounds the mistake bound of all deterministic algorithms. Consider the following algorithm: start with predicting all nodes as positive. Whenever a false positive is observed at some node u, flip the sign of u to negative. Such an algorithm achieves a mistake bound of n. Therefore, SLdim(H, G) ≤ n.• Improvement When p = ω( 1 n ), with high probability, the gap between these two bounds are Ω(np) = ω n (1), which can be made to approach ∞ as n → ∞.In this section, we present algorithms for the agnostic setting and prove their regret guarantees. As discussed in Section 4, the main idea behind the strategic version of agnostic-to-realizable reduction lies in our "guess" of the possible direction the original node would have come from. To do this systematically, we first need to specify a indexing system to the in-neighborhoods of every node in the graph. For each node v ∈ X , we assign a unique index to each in-neighbor inN - G [v] from the range {0, 1, • • • , ∆ - G }, where ∆ - G being the max in-degree of G. This indexing is specific to each v and does not require consistency when indexing a common in-neighbor of different nodes. We are now ready to formally introduce our algorithms in Algorithms 3 and 4. ≤ i 1 < • • • < i m ≤ T , 0 ≤ r 1 , • • • , r m ≤ ∆ - G doConstruct Expert(i 1:m , r 1:m ) as in Algorithm 4. end Run Biased Weighted Majority Vote (Algorithm 5) on the set of experts. Observe the manipulated feature vector v t and the true label y t ; , where we keep the same sequence of initial feature vectors (x t ) in S, but adjust their labels to be yAlgorithm 4: Expert(i 1 , • • • , i m , r 1 , • • • , r m ; G) Input: Hypothesis class H, manipulation graph G, indices for mistakes 1 ≤ i 1 < • • • < i m ≤ T , indices for manipulation directions 0 ≤ r 1 , • • • , r m ≤ ∆ - G ,if t ∈ {i 1 , • • • , i m } (suppose t = i k ) then xt ← the in-neighbor in N - G [v t ] with index r k //(h) t ≜ h G (x t ),i.e., the label that the effective classifier h G assigns to x t . Note that this sequence is defined only for analytical purpose and not required to be known by either the agnostic algorithm or the experts.By definition, S (h) is realizable by the hypothesis h ∈ H under graph G. Therefore, Theorem 3.3 guarantees that runnning SSOA on S (h) gives at most SLdim(H, G) mistakes. Let m ≤ SLdim(H, G) be the number of mistakes made, and i 1 , i 2 , • • • , i m be the time steps at which the mistakes occur.In addition, at every mistakei k = t ∈ [T ], let v (h) tbe the post-manipulation node observed by the SSOA algorithm running on sequence S (h) . On the other hand, let v t be the observation received by each expert. Although v t may be different from v (h) t because v t is the best response to the agnostic algorithm while v (h) t is the best response to SSOA, we know that v t must be an out-neighbor of x t . Therefore, there must exist an index r k (where 0 ≤ r k ≤ ∆ - G ) such that x t is the r t -th in-neighbor of v t . We argue that Expert(i 1:m , r 1:m ) is the expert e h that we want.We first establish the equivalence of the two following instances of SSOA:• SSOA e h denotes the algorithm instance simulated by expert e h ;• SSOA h denotes the algorithm instance running on sequence S (h) .We will show by induction that both instances SSOA e h and SSOA h have the same version space-and as a result, output the same classifier for the next round-at all time steps. This is clearly true at the base case t = 1, as the version spaces of both instances are initialized to be H. Now we assume the two instances are equivalent up to t -1 and prove that they are still equivalent at time t. Since they have the same version spaces H t-1 , they output the same classifiers for time step t. We denote this classifier by ĥt as in line 2 of Algorithm 4.∈ {i 1 , • • • , i m }, then the version space H t are still the same because neither instances update. Otherwise, there exists k ∈ [m] such that t = i k . Since SSOA h makes a mistake at i k , it will update the version space with observation (v(h) t , y (h) t ) = (v (h) t , -ĥt (v (h) t )). On the other hand, according to line 7 of Algorithm 4, the instance SSOA e h is updated using observation (v t , -ĥt (v t )). Therefore, it suffices to show that v (h) t = vt . Since our choice of r k guarantees x t to be the r k -th in-neighbor of v t , we have xt = x t based on line 5 of Algorithm 4. Therefore, both v (h) t and vt are equal to br ĥt,G (x t ), so they are the same. As a result, both SSOA e h and SSOA h updates their version space using the same observation, so their H t remains the same. By induction, these two instances are equivalent for all time steps. Finally, we use the equivalence established above to prove the lemma. Using ( ĥt ) t∈[T ] to denote the sequence of classifiers outputted by e h , we have h) is realizable under H and G)Mistake e h (S) -Mistake h (S) = T t=1 1 ĥt (br ĥt,G (x t )) ̸ = y t - T t=1 1{h(br h,G (x t )) ̸ = y t } ≤ T t=1 1 ĥt (br ĥt,G (x t )) ̸ = h(br h,G (x t )) = T t=1 1 ĥt (br ĥt,G (x t )) ̸ = y (h) t (y (h) t = h G (x t ) in S (h) ) = Mistake SSOA (S (h) ) (Equivalence of SSOA h and SSOA e h ) ≤ SLdim(H, G). (S (The proof of the lemma is thus complete.We present the algorithm in Algorithm 5.Algorithm 5: Biased Weighted Majority Vote [Ahmadi et al., 2023] Input: Expert class E, manipulation graph G(X , E) that is a supergraph of the true (unknown) manipulation graph G ⋆ . Initialization :For all experts e ∈ E, set weight w 0 (e) ← 1. for t ∈ [T ] do /* the learner commits to a classifier ht that is constructed as follows:*/for v ∈ X do elseEQUATIONW t = W + t (v) + W - t (v) = e∈E w t (/* False negative mistake. */ N [v t ] ← N + G [v t ] \ {x ∈ N + G [v t ], h t (x) = +1}; 16 E ′ ← {e ∈ E | ∀x ∈ N [v t ], e t (x) = -1};// penalize the experts that label all nodes in N [vt] as negative.end if e ∈ E ′ , then w t+1 (e) ← γ • w t (e); otherwise, w t+1 (e) ← w t (e); Regret(S, H, G) ≤ O ∆ + G • OPT + ∆ + G • SLdim(H, G) • (log T + log ∆ - G ) , where ∆ + G (resp. ∆ - G )denotes the maximum out-degree (resp. in-degree) of graph G.Proof of Theorem 4.1. As showed in the proof sketch, combing the guarantee of Algorithm 5 and bound on |E| givesMistake(S, H, G) ≤ ∆ + G • OPT E + ∆ + G • log |E| ≲ OPT E + ∆ + G • d(log T + log ∆ - G ),where OPT E denotes the optimal number of mistakes made by the best expert in E.Applying Lemma 4.3 to the best hypothesis in hindsight h ⋆ ∈ H shows that there exists e h ⋆ ∈ E that makes no more than OPT + d mistakes, which further implies OPT E ≤ OPT + d. Hence, we haveMistake(S, H, G) ≲ ∆ + G • (OPT + d log T + d log ∆ - G ).D Supplementary Materials for Section 5 G. foreach G ∈ G do Let d G ← SLdim(H, G); foreach m ≤ d G , i 1:m , r 1:m where 1 ≤ i 1 < • • • < i m ≤ T , 0 ≤ r 1 , • • • , r m ≤ ∆ - G doConstruct Expert(i 1:m , r 1:m ; G) as in Algorithm 4.Let G union ← (X , G∈G E G ) be the union of graphs in G; Run Biased Weighted Majority Vote (Algorithm 5) on the set of experts under graph G union .Theorem 5.1 (Restated). For any realizable graph class G and any adaptive adversarial sequence S of length T , Algorithm 6 has regret boundRegret(S, H, G) ≤ O ∆ + G • OPT H + d G • (log T + log ∆ - G ) + log |G| , where d G ≜ max G∈G SLdim(H, G) is the maximum strategic Littlestone dimension for all graphs in G, ∆ + G ≜ ∆ +Gunion is the maximum out-degree of G union (i.e., the union of graphs in G), and ∆ - G ≜ max G∈G ∆ - G is the maximum max in-degree over graphs in G.Proof of Theorem 5.1. For each G ∈ G, we use E G to denote the subset of experts constructed in Algorithm 6 for graph G. We also use E ≜ ∪ G∈G E G to denote the set of all experts.To prove this theorem, we first revisit the regret guarantee for Algorithm 5 in Lemma D.1, especially when the input graph G does not match the actual graph G ⋆ . The proof of Lemma D.1 largely follows from [Ahmadi et al., 2023] , but we include it in the end of this section for completeness.Lemma D.1 (Regret of Algorithm 5 [Ahmadi et al., 2023] ). If Algorithm 5 is called on manipulation graph G that includes all the edges in the actual manipulation graph G ⋆ , then the number of mistakes is upper bounded as follows:Mistake(H, G ⋆ ) ≤ O ∆ + G • OPT E G ⋆ + ∆ + G • log |E| ,where ∆ + G is the maximum out-degree of graph G, and OPT E G ⋆ is the minimum number of mistakes made by the optimal expert under graph G ⋆ .Since G union contains all edges in any G ∈ G and thus the unknown G ⋆ , Lemma D.1 that the number of mistakes made by Algorithm 6 is at most∆ + G • OPT E G ⋆ + ∆ + G • log |E| ≤ ∆ + G • OPT E G ⋆ + ∆ + G • d G • log(T ∆ - G ) + log |G|, where the second step uses the following upper bound on the number of experts:|E| ≤ G∈G m≤SLdim(H,G) T m • (∆ - G ) m ≤ |G| • m≤d G T m • (∆ - G ) m (∀G ∈ G, SLdim(H, G) ≤ d G , ∆ - G ≤ ∆ - G ) ≲ |G| • (T • ∆ - G ) d G +1 .Therefore, it remains to show thatOPT E G ⋆ ≤ OPT H + d G .To this end, we apply Lemma 4.3 the expert class E G ⋆ , in which all experts have the correct belief about the manipulation graph G ⋆ . For the hypothesis h ⋆ ∈ H that achieves OPT H under G ⋆ , there must exist e h,G ⋆ ∈ E G ⋆ ⊆ E such that e h,G ⋆ makes at most SLdim(H, G ⋆ ) ≤ d G more mistakes than h ⋆ under G ⋆ . We have thus proved that OPT E G ⋆ ≤ OPT H + d G , which in turn establishes the theorem.Proof of Lemma D.1. Suppose a mistake is made in round t, we show the following claims hold:• The total weights decrease by at least constant fraction:W t+1 ≤ W t 1 -γ/(∆ + G + 2)where G is the input graph.• The algorithm penalizes experts only if it makes a mistake on G ⋆ .To prove these claims, we consider the following two types of mistakes.False positive. Suppose h t (v t ) is positive but the true label y t is negative. According to the algorithm, h t labels v t positive only when the total weight of experts predicting positive on v t is at least W t /(∆ + G + 2). Moreover, each of their weights is decreased by a factor of γ. As a result, we have W t+1 ≤ W t 1 -γ/(∆ + G + 2) and the first claim holds. For the second claim, note that the algorithm only penalize experts e where e t (v t ) = +1. Sincev t ∈ N + G ⋆ [x t ],this implies e t (br et,G ⋆ (x t )) = +1, whereas y t = -1. In other words, the experts penalized must have made a mistake under G ⋆ .False negative. In the case of a false negative, the agent has not moved from a different location to v t to get classified as negative, so v t = x t . Since the agent did not move, none of the vertices in N + G ⋆ [v t ] was labeled positive by the algorithm. However, there might exist some vertices inN + G [v t ] \ N + G ⋆ [v t ]that are labeled as positive by the algorithm. Let N [v t ] denote the set that includes all vertices in N + G [v t ] that are labeled as negative by h t , we haveN + G ⋆ [v t ] ⊆ N [v t ] ⊆ N + G [v t ].According to the algorithm, for each x ∈ N [v t ], the total weight of experts predicting x as positive is less than W t /(∆ + G + 2) where ∆ + G is the maximum out-degree of G. Therefore, taking the union over all x ∈ N [v t ], it implies that the total weight of experts predicting negative on allx ∈ N [v t ] is at least W t 1 -| N [v t ]|/(∆ + G + 2) ≥ W t 1 -(∆ + G + 1)/(∆ + G + 2) = W t /(∆ + G + 2), where the inequality comes from N [v t ] ⊆ N + G [v t ].Reducing their weights by a factor of γ results in W t+1 ≤ W t -(γW t )/(∆ + G + 2). The first claim holds true. As for the second claim, if an expert e is penalized, then e t (x) = -1 for allx ∈ N [x t ]. Since N + G ⋆ [x t ] ⊆ N [x t], e t must label all nodes in N + G ⋆ [x t ] as negative. In other words, e t (br et,G ⋆ (x t )) = -1, which means that e must have made a mistake under G ⋆ . The second claim holds.Regret analysis. Let M = Mistake(H, G ⋆ ) denote the number of mistakes made by the algorithm. Since the initial weights are all set to 1, we haveW 0 = |E|. The first claim implies that W t+1 ≤ W t 1 -γ ∆ + G +2 . Therefore, W T ≤ |E| 1 -γ ∆ + G +2 M .On the other hand, we use the second claim to show that W T ≥ γ OPT E G ⋆ . We have proved that whenever the algorithm decreases the weight of an expert, they must have made a mistake on G ⋆ . Let e ⋆ ∈ E denote the best expert that achieves the minimum number of mistakes OPT E G ⋆ under G ⋆ . From our argument above, the weight of e ⋆ is penalized by no more than OPT E G ⋆ times. Therefore, after T rounds, W T ≥ w T (e ⋆ ) ≥ γ OPT E G ⋆ where the second inequality holds since 0 < γ < 1. Finally, we have:γ OPT E G ⋆ ≤ W T ≤ |E| 1 - γ ∆ + G + 2 M ⇒ OPT E G ⋆ • ln γ ≤ ln |E| + M ln 1 - γ ∆ + G + 2 ≤ ln |E| -M γ ∆ + G + 2 ⇒ M ≤ ∆ + G + 2 γ ln |E| - ln γ(∆ + G + 2) γ OPT E G ⋆By setting γ = 1/e, we bound the total number of mistakes as M ≤ e(∆ + G +2)(ln |E|+OPT E G ⋆ ). xt ← the in-neighbor in N - Gunion [v t ] with index r ′ s // when Gt ̸ = G,Regret(S, H, G) ≤ O ∆ + G • OPT H + (d G + N ) • (log T + log ∆ - G ) + log |G| ,where d G ≜ max G∈G SLdim(H, G) is the maximum strategic Littlestone dimension for all graphs in G, and ∆ + G (resp. ∆ - G ) is the maximum out-degree (resp. in-degree) of G union , where G union is the union of G that contains edges from all graphs in G.Proof of Theorem D.2. Similar to the proof of Theorem 5.1, we use E G to denote the subset of experts constructed in Algorithm 7 for graph G, and use E ≜ ∪ G∈G E G to denote the set of all experts. Since we have G t ⊆ G union at all time steps, Lemma D.1 on the expert set E gives us an upper bound on the number of mistakes made by Algorithm 7 as follows:Mistake(S, H,G 1:T ) ≲ ∆ + G • OPT E G 1:T + ∆ + G • log |E|.(1) We establish the following lemma, which is a strengthened version of Lemma 4.3 that accounts for the possibility of G t ̸ = G. Lemma D.3. For any hypothesis h ∈ H, any sequence of agents S, and any sequence of graphs G 1:T whereT t=1 1 N + Gt [x t ] ̸ = N + G [x t ]≤ N , there exists an expert e h ∈ E G (which are constructed in Algorithm 7) such that Mistake e h (S, G 1:T ) ≤ Mistake h (S, G) + N + SLdim(H, G).Applying the above lemma to E G ⋆ and using the upper bound OPT G = 1{G t ̸ = G ⋆ } ≤ N , we conclude that for the optimal hypothesis h ⋆ , there must exist experte h ⋆ ,G ⋆ ∈ E G ⋆ ⊆ E, such that the number of mistakes e h ⋆ ,G ⋆ makes under G 1:T is at most SLdim(H, G ⋆ ) + N ≤ d G + N more than that made by h ⋆ under G ⋆ . This implies OPT E G 1:T ≤ OPT H + d G + N.(2) As for the number of experts, we have|E| = G∈G   m≤SLdim(H,G) T m • (∆ - G ) m     n≤N T n • (∆ - G ) n   ≤ |G|   m≤d G T m • (∆ - G ) m     n≤N T n • (∆ - G ) n   (∀G ∈ G, SLdim(H, G) ≤ d G , ∆ - G ≤ ∆ - G ) ≲ |G| • (T • ∆ - G ) d G +1 • (T • ∆ - G ) N +1 .(3) Finally, plugging both (2), (3) into the bound Equation (1) gives usRegret(S, H, G) ≤ O ∆ + G • OPT H + (d G + N ) • (log T + log ∆ - G ) + log |G| , as desired.The proof is thus complete.Proof of Lemma D.3. We use a similar approach to that of proving Lemma 4.3. We define the sequence S (h) and the indices i 1:m , r 1:m in the same way as Lemma 4.3. In addition, we set i ′ 1:n to be the time steps where G t ̸ = G, which clearly satisfies n ≤ N . At time step t = i ′ s (s ∈ [k]), since v t is the best response according to graph G t ⊆ G union , there exists an index r ′ s ∈ {0, • • • , ∆ - G } such that x t is the r ′ s -th in-neighbor under graph G union . We will show that expert e h = Expert(i 1:m , r 1:m , i ′ 1:n , r ′ 1:n ; G) is the one we want. Again, we prove this by showing the equivalence of the following two SSOA instances:• SSOA e h is the algorithm instance simulated by expert e h ;• SSOA h is the algorithm instance running on sequence S (h) .Repeating the induction approach in Lemma 4.3, it suffices to show that the estimate xt correctly matches the true x t during the rounds i1:m . When t / ∈ {i ′ 1 , • • • , i ′ n }, this is guaranteed by the way indices r 1:m are constructed. When there exists s ∈ [n] such that t = i ′ s , this also holds based on the definition of r ′ 1:n . Therefore, the above two SSOA instances are equivalent. Finally, we have Mistake e h (S, G 1:T ) -Mistake h (S, G)= T t=1 1 ĥt (br ĥt,Gt (x t )) ̸ = y t - T t=1 1{h(br h,G (x t )) ̸ = y t } ≤ T t=1 1 N + Gt [x t ] ̸ = N + G [x t ] + T t=1 1 ĥt (br ĥt,G (x t )) ̸ = h(br h,G (x t )) (break [T ] into two parts on whether N + Gt [x t ] ̸ = N + G [x t ]) ≤ N + SLdim(H, G).(Combining t 1{G t ̸ = G} ≤ N and the bound from Lemma 4.3)We have thus established the lemma.Doubling trick to removing the assumption of knowing OPT G We end this section with an algorithm for agnostic graph classes that does not require any prior knowledge on OPT G . We present Algorithm 9 which uses Algorithm 7 as a subrountine and performs the doubling technique on the parameter N . This algorithm is based on the important observation that, if N ≥ OPT H + OPT G + d G + log |G| (in particular this implies N ≥ OPT G ), then Theorem D.2 guarantees that running Algorithm 7 with parameter N achieves the mistake upper bound ofO ∆ + G • (2N ) • (log T + log ∆ - G ), where the leading constant of the mistake bound can be estimated to be ≤ 4 by a more careful analysis. Therefore, if we denote define the problem-dependent parameter C to beC ≜ 8∆ + G • (log T + log ∆ - G), then as long as N reaches value at leastN ⋆ ≜ OPT H + OPT G + d G + log |G|,(4) running Algorithm 7 makes no more than C • N mistakes. Therefore, the learner just needs to estimate N through the doubling trick and terminate when the observed mistake does not exceed C times the estimate of N . C • k ⋆ k=1 2 k ≤ C • 2 k ⋆ +1 ≤ O(CN ⋆ ) ≤ O ∆ + G • (OPT H + OPT G + d G + log |G|) • log(T ∆ - G ) .This completes the proof.In this section, we present a an instance (H, G) in which there exists an exponential gap between the optimal mistake bound of deterministic and randomized algorithms.Let G be the star graph with center x 0 and ∆ leaves {x Justification: The limitations and future directions are discussed in Section 6. Guidelines:1 , • • • , x ∆ }. H = {h 1 , • • • , h ∆ } where h i (x) = 1{x = x i }.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: This paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper is a theoretical work without any direct societal impact to the best of our knowledge.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.The following article (among others) discusses some well-known tricks for this: https://www. nerdwallet.com/article/finance/raise-credit-score-fast.E.g., unlike in classical (non-strategic) settings, a true positive does not carry the same information as a false negative in our setting.Some previous works, such as[Ahmadi et al., 2023, Cohen et al., 2024], assume that agents will not manipulate their features if x ∈ BR G,h (x). While this assumption enforces consistency in the special case of h(x) = 1, we remark that most algorithms proposed by both papers remain effective even without this assumption.In this paper, we mainly consider deterministic algorithms. We will discuss the role of randomness in Sectionand Appendix E.We can also derive regret bounds when OPTH is defined based on the agents' best responses according to their own manipulation graph Gt instead of G ⋆ . In this case, the regret bound would be the same up to constant factors. 
 
 Appendix:  


Decision: The reviewers are in agreement that this paper studies a well-motivated problem, and proposed a novel instance-dependent complexity notion (strategic Littlestone's dimension that depends on the hypothesis class and manipulation graph). Extensions to the agnostic setting and the unknown manipulation graph setting are deemed interesting. The rebuttal addressed many concerns of the reviewers (mainly from a clarity perspective). They are happy to recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper considers the problem of online binary classification when each data point can strategically manipulate its features in a discrete way which is captured by a manipulation graph. 

Protocol and regret: In each round, the learner picks a deterministic classifier $h_t$, and then the data point $(x_t,y_t)$ arrives, and manipulates its feature according to graph $G$ from $x_t$ to $v_t$. The learner receives only $v_t$ and incurs loss $\mathbb{1}[h_t(v_t) \neq y_t]$. The regret is measured with respect to the best fixed $h \in \mathcal{H}$.

**contributions**


1. They introduced an elegant notion of Strategic Littlestone Dimension $\mathrm{SLdim}(\mathcal{H}, G)$, which is based on hypothesis class $\mathcal{H}$ and manipulation graph $G$

2. They showed that $\mathrm{SLdim}(\mathcal{H}, G)$ fully characterizes the optimal mistake bound for a realizable case, by showing a lower bound on the mistake using a strategic counterpart of shattering tree and an upper bound using a strategic version of SOA.  (Note: The realizable case here means there exists some $h \in \mathcal{H}$ with no mistakes on the manipulated data. so $h$ does not necessarily need to correctly classify the actual data.)
3. They extended their results for the agnostic case and showed an improved upper bound compared to previous works. They used the idea of approximating the whole class $\mathcal{H}$ using a finite set of representative experts. (Their benchmark is $\Delta_G^+ \cdot OPT$, where $OPT$ is the error of the best hypothesis and $\Delta_G^+$ is maximum out-degree of graph $G$)
4. Finally, they designed algorithms with regret upper bound for the setting where the manipulation graph is unknown to the learner. They consider two cases: (i) all data points use the same unknown manipulation graph from a set of graphs, (ii) each data point uses a separate manipulation graph (case (ii) better captures those real-world applications in which different data points might have different capabilities for manipulation.)
strength_weakness: strength_weakness: I don't find any major weakness at all.
questions: questions: 1. In line 101, you mentioned that, your approach yields an improved bound for the agnostic setting. Can you please provide more details about this improvement? I believe you are comparing the upper bound in Theorem 4.1. with an upper bound from previous work.
2. In your setting, you assumed that each strategic data point only gets manipulated for a positive classification and if no manipulation leads to a positive classification, then the data point remains unchanged. Is this a necessary assumption for your results? In other words, I was wondering, do you anticipate that your result can be easily extended to the setting where all data points (even those without a chance of getting positive classification)  have the potential to be manipulated?
limitations: limitations: As mentioned by the authors in the checklist, this paper is theoretical with no direct implications. I completely agree with this.

However, I want to note that the motivation for strategic classification comes from real-world problems. I think the progress toward this direction by theoretical researchers and practitioners can only be beneficial for society. This paper improves our theoretical understanding of the complexity of this problem in a somewhat stylized case.

I can think of only one possible potential limitation (in a very high-level sense). Suppose a practitioner decided to use manipulation robust learning algorithms in their specific application. They need to model a set of manipulation graphs $\mathcal{G}$. If due to inaccuracy in the modelling by the practitioner, $\mathcal{G}$ only captures the certain type of manipulations done by group $A$ and does not capture the type of manipulations done by group $B$, then the resulting learning algorithm will be only robust with respect to a certain type of manipulation from group $A$. Therefore, group $B$ **might** have gained some unfair advantages. Hence, it is important to model the manipulation graph set $\mathcal{G}$ accurately.
paper_summary: paper_summary: The paper tackles online binary classification where agents manipulate observable features for positive outcomes. It introduces the Strategic Littlestone Dimension (SLD), a new measure capturing the complexity of the hypothesis class and manipulation graph, demonstrating its role in achieving optimal mistake bounds for deterministic algorithms in the realizable setting. It also improves regret bounds in the agnostic setting by refining agnostic-to-realizable reductions and addressing unobserved original features. Additionally, it relaxes the assumption of a known manipulation graph, deriving regret bounds for scenarios with imperfect graph knowledge in both realizable and agnostic settings.
strength_weakness: strength_weakness: My main concern is twofold:

1. The paper primarily concerns deterministic learning algorithms, while most robust algorithms dealing with adversaries are stochastic, which greatly limits the practical relevance of the paper.

2. The computational complexity of Algorithm 1 is not clear. Line 3 of Algorithm 1 looks computationally expensive. Can authors comment on the computational complexity of the algorithm?
questions: questions: See weaknesses.
limitations: limitations: The authors did discuss the limitations of their work.
paper_summary: paper_summary: The authors continue the study of strategic classification in the online setting, where an agent can manipulate the instance features to potentially force a positive prediction (governed by a manipulation graph). In the *realizable* case, the authors provide a strategic variant of the Littlestone dimension and the SOA algorithm yielding the exact instance-dependent mistake rate. This improves upon degree-dependent mistake bounds of previous work. They also consider two individual additional directions: the agnostic case and the case when the manipulation graph is unknown. In the first they improve upon existing regret bounds, while in the latter they state novel upper bounds almost matching existing lower bounds.
strength_weakness: strength_weakness: Strength of the agnostic result is a bit unclear / open (see questions / limitations below).
questions: questions: How does Thm 4.1. (the agnostic regret bound) relate to Prop. 30 in Cohen et al. [2024]? Moreover, are there somewhat tight (say up to log factors) lower bounds on the agnostic regret bound? In particular is the $\mathcal{O}(\Delta\cdot\mathrm{SLdim})$ term necessary in the upper bound (Thm 4.1)? (From your remark I understood that only $\Delta\cdot\mathrm{OPT}$ and $\mathrm{SLdim}$ are known lower bounds).

Is the assumption that $X$ is discrete a strong one/necessary? We can just model the "manipulation graph" on an arbitrary domain $X$ as a function $f:X\to P(X)$, where $f(x)$ is the set of allowed manipulations of $x$. Are there any difficulties generalizing here?

Is a "symmetric" setting possible where the agent can (adversarially) modify $x$ to $v\in N[x]$ no matter the label $h(x)$?. The motivation could be that some agents want to be strategically classified as $-1$ while others as $1$.
limitations: limitations: The achieved agnostic regret bound is not compared to the agnostic one in Cohen et al. [2024, Prop 30], or perhaps I missed it, see question above. Please clarify as this would help to judge the novelty and strength of the result.
paper_summary: paper_summary: This paper studies an adversarial online setting where the agents can manipulate their feature vector $x_t$ to some feature vector $x'_t$ given a graph of manipulation rules $G$. The learner observes only $x'_t$ and knows in advance $G$. 
The usual goal is to obtain sublinear regret, with respect to some hypothesis class. In the realizable setting, this is equivalent to minimizing the number of mistakes, also known as the "mistake bound model". 
When $G$ is "empty", meaning there are no edges, we get the standard online model. 

The main contributions are as follows: 

In the realizable setting, the authors define a Littlestone tree that incorporates the manipulations and defines a notion of the Littlestone dimension for these trees. Extending to the agnostic setting, the authors use a known technique for constructing a finite "online cover" of the hypothesis class, and then apply an algorithm for the finite case (version of multiplicative weights update). 

Moreover, an extended model is introduced, where there is a finite set of manipulation graphs from which a graph is chosen. When all agents use the same graph from this set this is called the realizable case otherwise it is an agnostic setting.
strength_weakness: strength_weakness: My main concern about the paper is the lack of technical novelty, ideas from standard online learning translate pretty smoothly to the strategic online learning setting.

The definition of the Littlestone tree is straightforward, taking the "strategic loss" into account. Indeed, the upper and lower bound proofs are very similar to those of the standard Littlestone dimension and the SOA algorithm.

The ideas in the agnostic setting are also quite standard: the agnostic online learning technique of constructing a finite "online cover" for the class (by Ben-David et al.) and using a version of multiplicative weights on the finite class (by Ahmadi et al.).

What is the technical contribution of this paper?

The writing of the paper could be improved. I understand why the proofs should go through, but some definitions are really confusing. 
See the next section.
questions: questions: There are many parts of the paper where the writing/definitions are confusing.

Paragraph on the manipulation rule: $h$ denotes the classifier or the loss function? Why does it make sense to define the best response on points where $h$ returns $1$? I don't see how it compiles if it's not the loss function. 
It's not clear if it is consistent with lines 230-235: how do you define false positive and false negative? with respect to $h$ or the loss of $h$? 

Line 71 ״under the respective particular parametrization״ what does it mean?
I understand what the line afterward means, but line 71 is not clear to me.

Lines 94-95: "First, to construct the set of representative challenges". Is it a typo?

Minor: 

Line 34: "decision maker has little or no prior knowledge about the population being classified", this is also the case where the learner has no prior knowledge of the distribution. 

Sometimes the learner is also referred to as the decision maker (mostly in the intro), it's worth making it clear.
limitations: limitations: The limitations are addressed properly.
paper_summary: paper_summary: This paper studies online strategic classification from a combinatorial perspective. The paper defines a new combinatorial dimension called the Strategic Littlestone dimension that jointly captures the complexity of the hypothesis class and the manipulation graph. They show that the Strategic Littlestone dimension exactly quantifies the minimax number of mistakes made by deterministic learners in the realize setting. The paper also provides improved upper bounds in the agnostic setting by modifying the classic agnostic-to-realizable reduction to handle the fact that the learner does not observe true features. Finally, the paper considers the case where the manipulation graph is not known to the learner but belongs to a family of graphs which is known to the learner. They provide bounds on the minimax value in both the realizable and agnostic settings in this case.
strength_weakness: strength_weakness: - Lack of lower bounds. Apart from the known manipulation graph, realizable setting (Theorem 3.2), lower bounds on the minimax regret in terms of the strategic Littlestone dimension are not provided. 

- Lack of results for randomized learners in the realizable setting. While the authors do discuss randomized learnability, and its difficulty in the discussion section, I find it a bit unsatisfying. Without lower bounds for randomized learners, it is not clear whether the strategic Littlestone dimension characterizes realizable strategic online learnability in full generality. Meaning,  as far as I can tell, there could be a separation between deterministic and randomized realizable learnability for strategic online classification (correct me if I'm wrong here). 

- Deterministic learners in the agnostic setting. It is well known that in order to achieve sub linear regret in the traditional online classification setting, one needs randomization in the agnostic setting. Thus, it is a bit strange to me that the authors study/construct deterministic learners for strategic online classification in the agnostic setting. This also leaves open the question of whether the strategic Littlestone dimension characterizes agnostic online learnability. 

- The two points above bring into question the utility/usefulness of the strategic Littlestone dimension. Compared to say the Littlestone dimension, which not only qualitatively characterizes online learnability in the realizable and agnostic settings but also exactly quantifies the minimax rates, the same (at least as of right now), cannot be said of the strategic Littlestone dimension. As far as I can tell, the strategic Littletone dimension only characterizes deterministic realizable learnability. 

- Lack of intuition behind the dimension. In traditional online classification, the intuition behind needing shattered Littlestone trees is very easy from a lower bound perspective  - we just need to tell the adversary what to play for every move of the learner. However, this sort of logic does not seem to work for strategic Littlestone trees due to the need for reverse engineering. Unfortunately, I did not fully understand the intuition behind the strategic Littlestone tree from the proof sketch of the lower bound in the main text.  I had to read the full proof in the Appendix to fully understanding the structure of the strategic Littlestone tree. I think the paper can benefit from a more detailed discussion about the differences between shattered Littlestone trees and shattered strategic Littlestone trees and how the adversary should use strategic Littlestone trees to construct hard streams. In addition, I think to improve intuition, it would be nice to buff up the proof sketch of Theorem 3.2, and even better to include the full proof in the main text. 

- Minor: there is a typo in the second bullet point in Def. 3.1. I think it should be $N_G^{-}$.
questions: questions: -  In the case of unknown manipulations graphs, is the finiteness of the graph class necessary? Is there a joint dimension of the graph class and the hypothesis class that captures learnability and the minimax rates in this setting?

- Your definition of realizability states that if $(x_1, y_1), ..., (x_T, y_T)$ is the sequence of agents chosen by the adversary, there is a hypothesis $h \in H$ such that $h(br_{G, h}(x_t)) = y_t$. That is, the label $y_t$ agrees with the value of $h$ on the agents best-response to $x_t$ w.r.t $h$. Is this the most natural definition of realizability? What about simply requiring that $h(x_t) = y_t$ for all $t \in [T]$. Then, perhaps the fact that the learner observes $v_t$ instead of $x_t$ but still needs to correctly predict $y_t$ can be viewed as the learner observing noisy features? It would be nice if you can comment about why you choose this particular notion of regret and realizability. 

- Can you comment about any known separations between deterministic and randomized learnability for strategic online classification in the realizable setting?
limitations: limitations: No limitations.

Comments: title: Raising my score
comment: Thank you for raising the score! We will incorporate your suggestions into revisions of the paper to make the presentation more clear.
Thank you for raising the score!
Thanks for the clarification, I raised my score. This is a timely paper studying an important problem.
Thanks for your response. 
I believe the contribution is sufficient for acceptance.  

Please make the relevant changes in the presentation so it will be easier to understand the main definitions.
Thanks for your response.
Many thanks for your response.
Thanks for your response.