- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies greedy retraining in a finite common-payoff game between an AI designer and users with latent intents. The designer chooses a prompt-to-answer policy using historical prompt-level reward averages, while users best-respond by changing their prompts. The paper establishes a positive probability of persistent suboptimality for every nontrivial Bernoulli-reward instance, with stronger bounds under required-answer and biclustering assumptions, including near-certain failure for Nash-devious biclusterings. For deterministic rewards, it constructs dynamics whose limiting utility is lower than their initial utility and extends the construction to positive-measure families and arbitrarily large games. It also establishes utility monotonicity for corresponding variants without bandit feedback or without the prompt interface.
Critical strengths
- This paper gives a concrete deterioration mechanism. In Theorem 4.3, initially correct prompt-level averages become invalid when users change prompts. The played answer’s estimate is updated using a different population, while an alternative retains its earlier estimate. This identifies a specific interaction between latent-intent aggregation and selective feedback, beyond the familiar observation that greedy learning can miss an optimum.
- The structural analysis is insightful. Theorem 3.11 and the Nash-devious construction show how a biclustering-consistent initialization can trap the dynamics in a structurally suboptimal allocation of prompts. Under these assumptions, the lower bound on failure probability approaches one with sufficiently informative initialization. The example in Theorem 3.13 makes the reason transparent: allocating one prompt to each cluster can be inferior to allocating both prompts to a more valuable cluster.
Critical weaknesses
- While this paper establishes theoretically interesting failure mechanisms, their prevalence and significance in more general retraining settings remain unclear. For example, Theorem 3.2 establishes a positive probability of optimization failure, but its lower bound decreases exponentially with the problem size and initialization sample count. The stronger near-certain failure result in Theorem 3.11 requires a specific Nash-devious biclustering structure. Although these results rigorously demonstrate possible failure modes, they provide limited insight into how frequently such failures should be expected beyond these conditions.
- The empirical validation is restricted to simulations of small, randomly generated game instances rather than iterative training of actual AI models. The proposed framework relies on several idealized assumptions. It remains unclear whether the identified optimization failures and model deterioration persist when the retraining process involves approximate optimization or more realistic user adaptation. A small-scale experiment involving an actual learning model would substantially strengthen the connection between the theoretical findings and practical AI retraining systems.
Questions for authors
- Could the authors clarify how the theoretical results (for example Theorem 3.2/3.11) should be interpreted in terms of the prevalence of optimization failure in more general retraining settings?
- Have the authors considered validating the proposed failure mechanisms using an actual AI model undergoing iterative retraining, rather than only simulating the abstract game dynamics? For example, could a small neural network or LLM, retrained on feedback collected from adaptively changing prompts, exhibit the same optimization failures or deterioration? Such evidence would help establish whether the theoretical mechanisms remain relevant when the assumptions of exact best responses and greedy tabular updates are relaxed.
We thank the reviewer for the thoughtful and constructive feedback, and for highlighting both the strengths of our results and important directions for future work.
Q1: We provide two complementary (types of) results: all game instances are prone to optimization failures and some game instances exhibit deterioration failures.
For optimization failures, we focus on the “qualitative” distinction between linear and sublinear regret. Our results are broad but indeed are quite weak quantitatively, mirroring the SoTA in the much simpler problem of greedy bandits (as we state in Related Work). We make them somewhat stronger under some (plausible) structures.
For model deterioration, we focus on existence and non-degeneracy (which we establish for arbitrary large game instances).
Characterizing prevalence / severity of these failures on large and/or typical game instances remains open (as well as finding the right structural assumptions for “typical”). Our lower bounds are not intended to quantitatively characterize typical instances.
Q2. We agree realistic simulations with actual AI models would be valuable. We did not attempt them, in part because realistically modeling how users adapt their prompts to a changing AI system presents substantial additional challenges. Finding the right balance between realisticity and tractability would be challenging, too. Instead, we focused this project on a simpler, theoretically tractable model on par with those studied in the literature on learning in games.