The Human-AI Substitution game: active learning from a strategic labeler

Thank you for your review, Reviewer k54k! We are confident that we can address your technical concerns, and summarize our responses below:

The difference between an adversarial labeler and an abstaining labeler is not discussed.The difference between the concerning problem from active learning within an adversarial environment is not clear. Meanwhile, though it is mentioned that the labeler's strategy is identifiable, it is still unclear if it is the worst case.

To clarify, in the learning game, we can deduce that the labeler will not be adversarial. Note that this is not by assumption, but rather by observation on which labeling strategies can be minimax optimal in the learning game.

To see this, if the labeler is adversarial, then this will lead to a payoff of zero. This is because adversarially generated data will not realize the learning outcome, and thus the learner will not pay the labeler (L67-70). Hence, while adversarial labeling is a valid strategy, it will not be minimax optimal in our learning game and will not be adopted by a labeler as an optimal labeling strategy.

Finally, to your last point, the labeler’s minimax strategy will always be identifiable. Only these strategies ensure the learner’s learning outcome is met, and thus lead to a positive payoff in the learning game.

The motivation of the problem is too detailed, such that it can hardly be extended to other applications. It is recommended that real-world experiments should be conducted to validate the problem or it seems too artificial.

We believe that our setup is fairly general, involving only a simple twist of the standard active learning setting (L44). It serves to address an inherent tension in any supervised learning setup: if the labeler allows the learner to learn fast (e.g. through active learning), this in turn reduces the final profit of the labeler.

Moreover, we believe our work is timely and well-motivated. Just in the recent months, we have seen (in the real-world) Hollywood screenwriters go on strike to negotiate a deal that prevents companies from training on their data and replacing them with AI [1]. Thus, we believe it is important to build our understanding of the replacement aspect of learning, which we set out to do in our paper.

[1] WGA Negotiations — Status as of May 1, 2023

The theoretical results are does not belong too much surprising information and has limited contribution to the algorithm design, since the algorithm design is mainly based on the labeler's strategy that is already pre-defined.

We believe our learning algorithm is novel, since we prove that it is near-minimax optimal in the learning game. Contrary to your point, we do not pre-define the labeler’s strategy. Our learning algorithm is proven to be near-optimal with respect to any labeling strategy in the learning game.

We hope this helped clarify most of the questions. We found your feedback very useful in revising the manuscript, thank you! Please let us know if there are any further questions.

Thank you for your detailed review, Reviewer GuAP! We are confident that we can address your technical concerns, and summarize our responses below:

(1) The learner is not allowed to query an example multiple times. If the learner can query an example multiple times, then the labeler can first abstaining from labeling for a while and then eventually give a correct label. It is very natural in practice for a learner to query an example multiple times until he gets a label.

Deadlock: We have considered the setting you propose, as a possible formulation. However, one issue is that some AL algorithms would deadlock. To see this, at time $t$, an algorithm would query the optimal point $x_t$. If the labeler declines to label and $x_t$ is not removed from the data pool, the algorithm would still query $x_t$ at $t+1$. This is because the state has not changed, $x_t$ would still be the best point to query, and eligible to be queried since it’s in the data pool. Thus, for the setting you suggest, there would have to be an apt way to modify AL algorithms and ensure the process does not hang. By contrast, in our setting, a data point is removed from the pool at each time step, thus ensuring progress.

Labeler controlled queries: If there is a way around the deadlock issue, we also thought that this setup may grant the labeler a lot of power. If the labeler can hold off on labeling a point indefinitely, the labeler can dictate the order the learner receives the labels. This is achieved by refusing to label any point but one (say $x’_t$ at time $t$). Thus, the learner’s choice in queries would not matter as labels can only be received in the order $x’_1$, …, $x’_n$, as decided by the labeler. We thought that this setup may differ substantially from the standard AL setting, and our goal is to study the problem closest to the canonical AL setup (L43-44).

Guaranteeing Learning Outcome" (Section 1.1): the labeler must label in a way to guarantee that the learner can identify the hypothesis in the end. However, this requires the labeler to know the hypothesis space of the learner very well so that he will not abstain from labeling critical examples (e.g., the above). This is a strong assumption -- how can an average human worker knows the hypothesis space of the sophisticated machine learner?...I might change my opinions if the authors can provide some strong motivations or real-world scenarios to support these two assumptions.

Analyzing minimax strategies: For most of the paper, in the learning game, we think of the labeler as a “[resourceful] data labeling company” (L199). This is because in game theory, one needs to consider players who play optimally in order to study the Nash Equilibria/minimax query-complexity.

Dealing with myopic labelers: With that said, in subsection 4.1 and 4.3, we offer some remedies when facing a player that behaves sub-optimally, for instance due to lack of knowledge about $\mathcal{H}$ as you suggest (assume also the learner does not communicate $\mathcal{H}$ for some reason):

1. If the learner knows that the labeler may behave myopically, one idea is to loosen the “learning outcome” to approximate identifiability. Thus, the labeler abstaining on one critical example is not fatal ($x^*$ in your example). In subsection 4.1, we show how to extend our learning algorithms to the PAC learning setting.
2. In 4.3, we observe that the E-VS can be used to detect when an abstained point leads to non-identifiability. Thus, the learner can use this to send a certified “warning” to the labeler: if this critical point (e.g. $x^*$) is abstained upon, it will provably lead to non-identifiability. In this way, the learner can use the E-VS representation to prevent an unaware labeler from prematurely halting the learning process. Indeed, non-identifiability is something neither party wants. The learner wants to learn. The labeler needs to realize the learning outcome, in order to be paid.

Worker Unions: In the specific case of AI automation, we have seen in recent news that Hollywood screenwriters have collectively gone on strike, engaging in negotiations with companies through their union (“Writers Guild of America'') [1]. Thus, in the AI automation setting, we are inclined to think that the labeler may in fact correspond to a union of workers, which may be more resourceful than a single worker.

[1] WGA Negotiations — Status as of May 1, 2023

Finally, as we write in the introduction (paragraph at L29), this paper studies a general conflict in incentives that can arise in any learner-labeler relationship. Active learning enables the learner to learn fast, but in doing so, leads to lower labeler profit. This calls into question a fundamental assumption in active learning: what is to say that the labeler wants the learner to learn fast? We note that the setting of the labeler as an “average human worker” is only one instantiation of this setup (L34).

What is the purpose of Section 3.1 (in particular Algorithm 3 and Proposition 3.7) ? … If this is the case, then what is the time-complexity of Algorithm 3? How does Proposition 3.7 shows that finding the maximal E-VS bisection point can be done efficiently?

(Q2) What is the purpose of Section 3.9? The authors say that this section is to compare with EPI-CAL, but only give a formal result for EPI-CAL ( samples in Proposition 3.9) and didn't give any formal result for the algorithm they proposed for comparison.

(Q3) How is this paper's model and result related to the "well documented" phenomenon that "teachers (masters) strategically slow down the training of their apprentices (Garicano & Rayo, 2017)" ?

…Proposition 5.1 is a counterexample where the upper bound doesn't hold without the regularity assumption, but the authors didn't say which label cost this Proposition is for…

Thank you for your review and your helpful suggestions, Reviewer ciAE! Please see our responses to your questions below:

Clarity: the notation is convoluted; V is used for both VS and a hypothesis space variable. For instance, in table 1, what is V? it seems introducing a specific notation for VS (e.g., V) or for the hypothesis space variable (e.g., V) could help.

Thank you for this formatting suggestion! We will be sure to clarify the difference and adapt the presentation accordingly. To clarify, we meant to write $H[S]$ for the version space in Table 1.

We hope this helped clarify most of the questions. We found your feedback very useful in revising the manuscript, thank you! Please let us know if there are any further questions.

Thank you for your review, Reviewer rYHN! Please see our responses to your questions below:

I only have a minor question. This paper assumes "the learner’s strategy corresponds to some deterministic, querying algorithm". Nevertheless, non-deterministic policies such as Thompson sampling is quite common in some active learning tasks such as Bayesian optimization. How does these non-deterministic policies fit into the framework of this paper?

To clarify, Bayesian optimization/Thompson sampling is used for finding a maxima $x \in X$ of some unknown $h$. There, the goal is to adaptively query in order to shrink the uncertainty over $h$, to find one of its maxima with low (simple) regret.

Our setting is quite different in that we want to learn the unknown hypothesis $h$, instead of optimizing $h$. Moreover, our paper studies minimax learning strategies in the learning game, in face of a strategic labeler who may be playing an optimal labeling strategy. This game theoretic setup is another major difference that complicates the analysis and differs from the setup of Bayesian Optimization.

We hope this helped clarify most of the questions. We found your feedback very useful in revising the manuscript, thank you! Please let us know if there are any further questions.