Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification

Thank you for the detailed and insightful comments.

Deterministic learners in the agnostic setting

Our focus on deterministic algorithms is motivated by real-world applications of strategic classification where legal or regulatory requirements often demand the learner to use deterministic algorithms. For example, in college admissions, institutions are required or expected to publish clear and transparent decision criteria, as randomization could be seen as arbitrary or unfair, weakening the trustworthiness of the admissions process.

At the technical level, our construction of representative experts (Lemma 4.3) relies on a careful coupling analysis that applies to any trajectory of classifiers chosen by the learner, regardless of whether randomness is used or not. However, for the strategic variant of the learning from expert advice algorithm, the only known agnostic algorithm (from [Ahmadi et al., EC’23]) is also deterministic, which accounts for the deterministic nature of our agnostic algorithm. Therefore, to extend this technique to randomized algorithms, one key challenge is to design randomized agnostic algorithms in the finite expert setting with at most logarithmic dependence on the size of the experts. We believe this is an interesting and non-trivial question for future research.

Finiteness of the graph class in the unknown manipulation graph setting, and joint dimension of the graph class and the hypothesis class

Thank you for the insightful question. While the finiteness of the graph class is necessary in the worst case scenario (see [Prop 14, Cohen et al, 2024] for a lower bound in terms of $\log|\mathcal{G}|$), it is not necessary for every instance. We agree that introducing a joint complexity measure for the graph class and the hypothesis class to characterize minmax rates is a valuable open question. Some technical challenges we encountered in extending our single-graph SLDim to the multi-graph setting include:

• In the structure of the strategic Littlestone tree (see Lines 247-248), the set of outgoing edges from a node depends on its out-neighborhood under the manipulation graph. When dealing with a family of graphs, one might attempt to use the union of the out-neighborhood for each graph in the class. However, that causes the tree to be too wide and shallow, resulting in a dimension that is smaller than the actual minmax mistake bound. In particular, it cannot become a valid upper bound because the branches no longer reflect the true types of mistakes that the learner can possibly make.

• If one keeps track of a “graph version space” and to determine the structure of the Littlestone tree, there may be a monotonicity issue. As graphs are eliminated from the graph version space, the set of feasible manipulations shrinks, which may potentially cause the tree to become thinner and deeper, thus increasing the dimension of the subgraph! This is in contrast to the monotonicity in terms of the hypothesis class which is less subtle and almost immediate from definition.

Definition of realizability and regret

Thanks for the question. We believe this is an important point and we will add a remark to future versions of our paper. Unlike the traditional notion of realizability that simply assumes $h(x_t)=y_t$ some $h\in H$ across all $t\in[T]$, we use the strategic notion of realizability that requires $h(BR_{G,h}(x_t))=y_t$. In other words, we require that a hypothesis $h\in H$ classifies each agent correctly if the agents also best respond to $h$. We adopt this notion for several reasons:

• This notion is rooted in the concepts of Stackelberg value and Stackelberg regret in game theory, which account for agents’ best responses and serve as a natural benchmark in strategic settings.

• It places the learner and the optimal hypothesis on equal footing when evaluating the number of mistakes they make, unlike the standard notion of realizability which implicitly assumes that agents manipulate against the learner but not against the optimal hypothesis.

• Under this strategic notion of realizability, there always exists a learning algorithm in hindsight that can achieve zero mistakes against a realizable sequence, such as when the algorithm implements the optimal hypothesis throughout. This aligns with the purpose of introducing realizability in the first place. In contrast, it is unclear that any algorithm would be able to achieve zero mistakes against a standard realizable sequence. Previous work has shown strong incompatibility between these two notions in the context of linear strategic classification setting [Chen, Liu & Podimata, NeurIPS’20].

Separations between deterministic and randomized learnability

Yes, we showed a separation between deterministic and randomized mistake bounds in Appendix E. Specifically, we constructed a family of instances where for each value of $\Delta$, there exists an instance where the minmax bound for deterministic algorithms is at least $\Delta-1$, but the minmax bound for randomized algorithms is at most $\log\Delta$. This class witnesses a super-constant gap between deterministic and randomized bounds, unlike their non-strategic counterparts which only differ by a factor of 2. This implies that the proposed SLDim does not characterize randomized learnability and that characterizing learnability in the randomized setting is highly nontrivial.

Thank you for your the detailed review and valuable feedback.

Technical contribution

We respectfully disagree that our paper lacks technical novelty because it applies ideas from standard online learning. While we build on established methodologies such as the Littlestone tree, SOA learning rules, and the agnostic-to-realizable reduction via experts, these are foundational philosophies in learning theory literature that require different technical insights when applied to different settings. An active and expanding line of work have also been applying these methodologies to understand the learnability and optimal rates in various contexts, such as the multiclass Littlestone dimension [Daniely et al., COLT’11], Natarajan-Littlestone dimension [Kalavasis et al., NeurIPS’22], the randomized Littlestone dimension [Filmus et al., COLT’23], the VC-Littlestone tree [Bousquet et al., STOC’21], to name a few. While these results share common philosophies, each presents unique technical challenges and requires new insights.

In the strategic classification context, one significant challenge for us is the information asymmetry between the learner and adversary regarding the true features before manipulation. This challenge is not addressed by previous works on non-strategic learning where the true features are always observable. Below we outline our main technical contributions in addressing these challenges:

• Structural insights. As discussed in Lines 225-242 of Section 3, our construction of the strategic Littlestone tree accounts for the asymmetric information carried by false positives and false negatives by creating an asymmetric number of branches. We also introduce a carefully designed consistency rule to ensure realizability of the adversary’s choices.

• Lower bounds: While constructing a sequence of post-manipulation observations that the adversary wishes to induce to the learner is straightforward, a critical challenge is in finding a realizable sequence of initial features before manipulation. We address this by combining our new consistency rule with a novel reverse-engineering technique.

• Upper bounds: As discussed in Lines 285-290, the main challenge in proving the upper bound is to construct a classification rule that simultaneously satisfies the “progress on mistakes” property for all features in the space. Since each layer of the SL tree inspects the entire neighborhood of a certain node, one cannot optimize each node independently as in non-strategic settings. We resolve this by favoring positive labels whenever false positives decrease the SLDim, a technique also rooted in the asymmetric information carried by false positives vs negatives.

• Agnostic reduction: As discussed in Lines 88-93, our expert set needs to effectively guess the direction from which each agent moves from. We also extend this technique to the unknown graph setting. We will add a more detailed discussion about these technical challenges and contributions in the revisions of our paper.

Manipulation rule, false positives and false negatives

Implicit in our model is that all agents prefer positive labels over negative labels. While we use $h$ to denote the learner’s choice of classifier, you’re correct that agents’ loss function can also be written in terms of $h$. Specifically, under classifier $h$, an agent with true features $x$ and post-manipulation features $v$ incurs a loss of $-h(v)-\infty\cdot\mathbf{1}\{(x,v)\not\in E\}$, where the second term is to ensure feasibility of manipulation from $x$ to $v$. To minimize this loss, agents will choose $v$ such that $h(v)=+1$ if possible. That’s why we define the best response on nodes where $h$ return $1$. We will clarify this assumption explicitly in future versions.

If an agent $(x,y)$’s true label $y$ is negative but she manipulates her features to receive a positive classification $h(v)=+1$, the learner has made a “false-positive mistake”. In this case, the observation available to the learner is represented as the pair (agent’s observable features, agent’s true label)$=(v,-1)$. Conversely, if $y=+1$ but no neighbor of $x$ is classified as positive by $h$, the agent will not manipulate and will receive a negative label $h(x)=-1$, resulting in a “false-negative mistake”. The learner’s observations are denoted by the pair (agent’s observable features, agent’s true label)$=(x,+1)$.

Line 71 ״under the respective particular parametrization״

Thank you for pointing this out, we are sorry for the confusion. What we meant is that the (near)-optimality of the mistake bounds in previous work [Cohen et al., Ahmadi et al.] are established under the assumption that the mistake bound must be parametrized as a function on the Littlestone dimension and/or the graph’s out-degree. These works show optimality in a specific instance in which the bounds cannot be improved when parameterized in these particular ways. However, these bounds are not tight for all instances, especially when the parameters such as LDim or out-degree are infinite. We will clarify this in more detail.

Typo in Lines 94-95

Yes, this is a typo. We meant to write “to construct the set of representative experts”.

Learner’s prior knowledge

While it is true that in the stochastic/offline setting with an unknown distribution, the learner has no prior knowledge about the population being classified, we want to emphasize that this is still easier than our online setting because even though the distribution is unknown, the learner knows that that there exists an underlying distribution, allowing her to learn a good classifier by estimating the distribution. In contrast, in the online setting, agents are adversarially chosen on-the-fly and do not come from any prespecified distribution.

Learner vs decision maker

Yes, we will make it clear in future versions of our paper.

Thank you for the positive feedback and the insightful comments.

Comparison of our agnostic regret bound (Thm 4.1) to that of Cohen et al. (Prop 30), and whether there are tight lower bounds

Thank you for your question. Our agnostic algorithm that achieves the mistake bound in Thm 4.1 only requires observing post-manipulation features after committing to a classifier at each round. In contrast, Prop 30 of Cohen et al. requires the learner to observe pre-manipulation data before choosing a classifier and then observe post-manipulation data afterwards. This makes their setting strictly easier than ours. We will add a remark about this comparison to revised versions of our paper.

About lower bounds in the agnostic setting, we agree that both $\Delta\cdot\text{OPT}$ and $\text{SLDim}$ are valid lower bounds but it’s unclear whether the $\Delta\cdot\text{SLDim}$ term is necessary. It remains an important open question to derive lower bounds for this agnostic setting.

Does the domain $\mathcal{X}$ need to be discrete?

No, the assumption on the discrete domain $\mathcal{X}$ is not necessary. We totally agree that our results can be immediately extended to any domain with arbitrary predefined manipulations characterized by some abstract function $f$. We will clarify this in revisions.

Symmetric setting where agents can adversarially modify their features to the neighboring features

We agree that your proposed setting is also well-motivated, though it takes a different approach compared to our work. Our focus is on strategic modifications, which can be viewed as a special case of the fully adversarial setting that you mentioned. The setting you described–where each $x$ can adversarially move to any neighbor in $N(x)$ regardless of the label–has also been explored in the adversarial robustness literature, particularly in the context of offline learning where dat appoints are sampled from a fixed distribution (see, eg, [Montasser et al., NeurIPS’22]). Another related model (also in the offline setting) that reflects your motivation is proposed by [Sundaram et al., ICML’21] which introduces another parameter $r\in\mathbb{R}$ that indicates how much a data point prefers label $+1$ over $-1$. In this model, a negative $r$ implies that some agent wants to be classified as $-1$ rather than $+1$. Although our current approach does not generalize immediately, we believe that it is an interesting direction to bring either model to the online learning setting.

Thank you for your questions and comments.

Weakness 1: deterministic learning algorithms

While we agree that many robust algorithms rely on randomization to deal with adversaries, we want to highlight that in the context of strategic classification, there are important scenarios where the learner must use deterministic algorithms due to legal or regulatory requirements. An example is college admissions, where institutions are required to publish clear and transparent decision criteria (aka classifiers), as randomization could be perceived as arbitrary or unfair, weakening the trustworthiness of the admissions process. This motivates our study of deterministic algorithms and highlights its practical relevance. We will add this note to the revised paper.

In addition, characterizing the minmax rates for randomized algorithms is highly nontrivial. In Appendix E, we have constructed instances for all $\Delta$ where the deterministic minmax bound is $\Omega(\Delta)$ but the randomized minmax bound is $O(\log\Delta)$. This reveals a super constant gap that did not exist in the non-strategic setting.

On the technical front, one of the many challenges of establishing a lower bound for randomized algorithms is that the adversary's ability to reverse-engineer the post-manipulation features to obtain pre-manipulation ones relies on “looking ahead” at the learner’s algorithm. However, if the learner uses randomness, the adversary cannot fully control which mistakes will occur or what information they provide to the learner. This challenge is deeply rooted in the information asymmetry inherent in the strategic setting.

Weakness 2: computational complexity of Algorithm 1

While we acknowledge that Algorithm 1 can be computationally expensive to implement, we want to remark that our primary focus is on the statistical complexity of learning in the presence of strategic manipulations, rather than the computational complexity. It is often the case that statistically optimal algorithms become computationally intensive — this is also true in the traditional (non-strategic) setting, where the SOA algorithm that enjoys minimax optimal mistake bound is also computationally expensive, and there are even computational hardness results for learning certain classes [Hazan and Koren, STOC’16]. We believe that exploring the tradeoff between computational and statistical complexity is an interesting direction for future research.

Thank you for the positive feedback on our work. We are happy to see that you find our notion of Strategic Littlestone Dimension elegant and valuable.

Question 1: Improved bound for the agnostic setting

This improvement results from the comparison between Theorem 4.1 in our paper and the agnostic mistake bound in [Theorem 4.5, Ahmadi et al., 2023]. Both papers study the same setting of agnostic online strategic classification and design deterministic algorithms that achieve mistake bounds in terms of $\Delta\cdot$OPT. However, their result requires the hypothesis class $\mathcal{H}$ to be finite, whereas we only require finiteness of the strategic Littlestone dimension, which is a strictly weaker condition. We will add clarifications to revisions of our paper.

Question 2: Data points with no feasible manipulation that receives positive label would stay unmanipulated

Yes, we do assume that data points that cannot manipulate to get a positive label would choose not to manipulate, and this is a necessary assumption for establishing our upper bound (whereas the lower bound would still hold if we remove this assumption). On the technical side, when false negative mistakes are made, this assumption enables us to identify the pre-manipulation features as the root of the strategic Littlestone subtree, and is crucial for establishing the “progress on mistakes” property. This assumption is also crucial for the previous upper bounds in [Ahmadi et al, Cohen et al.]. We believe that extending the results to the setting where all data points could manipulate is an interesting question for future research.

The importance of modeling the manipulation graph G accurately

We completely agree that accurate modeling of the manipulation graph is crucial and that inaccurate estimations for certain graphs could lead to fairness issues. As a preliminary effort towards addressing unknown manipulation graphs, we allow the learner to run the strategic classification algorithm using knowledge about a potentially larger graph class that contains the true graph. The learner incurs only a logarithmic cost in the size of the graph class (assuming that taking union of the graphs does not significantly increase maximum in/out degree). Since this extra cost is only logarithmic, this (to some extent) allows the learner to adopt more conservative estimations of the manipulation that captures the types of manipulations from both groups. However, this approach focuses on the objective of minimizing the total number of mistakes rather than ensuring fairness among different groups. We believe the fairness implications that you described can be an interesting direction for future research.