acceptodds
Under review as a conference paper at ICLR 2027

Failure Modes in AI Retraining Dynamics

Abstract

Modern AI systems are increasingly retrained on data generated through interaction with users. Three forces are at play: (i) AI is typically retrained "greedily," ignoring exploration-exploitation tradeoffs, (ii) the users strategically adapt their behavior, and (iii) user intents are not directly observable. We ask whether these dynamics lead to poor outcomes. We study a stylized model, focusing on the "nice" case when the AI and the users have aligned incentives. We identify two distinct failure modes. First, the system may fail to converge to an optimal Nash equilibrium (of the relevant stage game) due to limited exploration, instead stabilizing at a suboptimal outcome region. This mode is ubiquitous: it happens with a positive probability for every problem instance. Second, a non-degenerate subset of problem instances exhibits model deterioration, whereby the system converges to an outcome that is strictly worse than the initial state.

Primary area:
learning theory
Keywords:
Retraining dynamics, strategic users, human-AI interaction, bandit feedback, online learning, game theory, distribution shift

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_Ays9OpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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?
  2. 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.
1 comment

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.

Reviewer_8RFQOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the long-term dynamics of repeatedly retraining AI systems on user interaction data when incentives between users and the AI designer are perfectly aligned. It formulates this interaction as a repeated Stackelberg game characterized by three core properties: greedy model retraining without purposeful exploration, strategic user adaptation (prompt selection), and an unobservable latent intent space mediated through a shared prompt interface. Under this framework, the authors prove that retraining dynamics suffer from two fundamental failure modes: optimization failures (failing to converge to an optimal Nash equilibrium) and model deterioration (stabilizing at an outcome strictly worse than the initial deployment).

Critical strengths
  • A primary theoretical merit of the paper is demonstrating that severe retraining pathologies arise even in the idealized "nice" regime where user and designer incentives are perfectly aligned. In economic and multi-agent literature, system failures are routinely driven by misaligned objectives, adversarial manipulation, or externalities. By restricting the formulation to shared utilities and showing that greedy updates can still trigger model deterioration, where the model converges to a state strictly worse than its initial deployment, the paper delivers a counterintuitive and foundational insight. This highlights that the interaction between unobservable user intents, strategic prompt adjustment, and greedy updating is inherently destabilizing on its own.
  • Rather than merely showing an isolated or fragile edge-case pathology, the authors establish that model deterioration is structurally robust. They prove that it persists without ties, occupies an open set of positive Lebesgue measure, scales to arbitrarily large game instances via block embedding, and accounts for over 95% of empirically observed robust deteriorations in the studied domain. Crucially, the 4-way structural decomposition cleanly isolates the exact mathematical drivers: the authors prove that removing either the prompt interface (unpooling intents) or bandit feedback (full information) restores weak monotonicity and eliminates deterioration entirely. This provides actionable clarity on the precise conditions that make closed-loop AI retraining vulnerable to self-inflicted harm.
Critical weaknesses
  • The model assumes that at every retraining round, the user population observes the newly deployed answer policy πAt\pi_A^t globally and executes an exact, deterministic best-response across all prompts: πPt(i)∈arg⁡max⁡p∈[K]μi,πAt(p)\pi_P^t(i) \in \arg\max_{p \in [K]} \mu_{i, \pi_A^t(p)}. This requires users to possess counterfactual, complete knowledge of what the AI would answer for every possible prompt before interacting with the updated model. In real-world AI deployment, users face their own bandit exploration problem and cannot observe model shifts across unseen prompts without active experimentation. The specific rerouting dynamics driving model deterioration rely critically on this friction-free, omniscient user adaptation.
  • Absence of Function Approximation and Cross-Prompt Generalization: The AI designer is modeled via decoupled tabular averages μ^p,a\hat{\mu}_{p,a} for each discrete prompt-answer pair. The core mechanism underpinning model deterioration strictly requires unselected actions to remain completely "frozen" at historical estimates while the selected action's sample mean drifts below it. Real-world AI retraining (e.g., pre-training, SFT, or RLHF) updates continuous, shared parameters across a neural network rather than maintaining independent tabular buckets. Because parameterized models generalize across prompts and answers, updating on newly observed interactions inevitably alters the implied estimates of unplayed prompts and responses. It remains unproven whether the identified deterioration pathology survives in systems with inductive biases, representation sharing, or smooth regularization, or whether it is largely an artifact of decoupled, unregularized tabular bandit updates.
Questions for authors

Q1: The core deterioration mechanism requires the user population to execute an exact, deterministic best response πPt∈arg⁡max⁡p∈[K]μi,πAt(p)\pi_P^t \in \arg\max_{p \in [K]} \mu_{i, \pi_A^t(p)}. In the canonical 3×2×33 \times 2 \times 3 construction, intent i1i_1 temporarily leaves prompt p1p_1 entirely, isolating intent i2i_2 on p1p_1 so that the empirical average of answer a2a_2 drops below the frozen initial estimate of a1a_1. Does robust model deterioration still exist with positive measure if users follow a smooth, stochastic choice model (e.g., softmax/Boltzmann choice with temperature τ>0\tau > 0 or ϵ\epsilon-noisy best response)? If intent i1i_1 continues to submit prompt p1p_1 with small probability ϵ>0\epsilon > 0, does this leak sufficient positive reward on (p1,a2)(p_1, a_2) to prevent the estimate from falling below the unplayed alternative, or does the deterioration region simply shrink continuously?

Q2: The update rule in Eq. (3) computes μ^p,at\hat{\mu}_{p,a}^t by weighting all historical observations uniformly with the initial data. In the deterioration trajectory, the switch occurs because the cumulative average of a2a_2 on prompt p1p_1 is dragged down over tt transient rounds until 1.48+0.50tt+2<0.525\frac{1.48 + 0.50t}{t + 2} < 0.525. If the designer instead uses an exponential moving average (discount factor γ<1\gamma < 1) or a finite sliding window of interaction history, does the system still deteriorate, or does it cycle, oscillate, or stabilize at the transient policy?

Q3: The paper proves that model deterioration requires both bandit feedback and the prompt interface, relying on decoupled tabular estimates μ^p,a\hat{\mu}_{p,a} where unselected actions remain frozen indefinitely. Under linear function approximation or structured reward representations (e.g., low-rank bilinear forms μp,a=ϕ(p)⊤Θψ(a)\mu_{p,a} = \phi(p)^\top \Theta \psi(a)), updating an answer on one prompt inherently updates its implied value across other prompts. Can the authors clarify whether the one-switch certificate in Appendix D.5 can be satisfied when prompt estimates are correlated, or does cross-prompt generalization preclude the selective "freezing" that triggers the deterioration switch?

1 comment

We appreciate your insightful comments and the positive evaluation.

Re Q1, Q2: While we focused on the core model of greedy retraining dynamics, many of our findings carry over to some relaxed models, both theoretically and experimentally, consistent with your suggestions. Please see the messages “for all reviewers” for these new results.

Re Q3: Indeed, we mainly consider an “unstructured” utility model – without any structure that allows generalization across different intents / prompts / actions. This is arguably a paradigmatic first/basic model to study (in our setting as well as in various prior works in game theory and online machine learning / multi-armed bandits).

Incorporating such utility structures would be a substantial additional challenge, best handled in another paper. (Besides, there’s some arbitrariness in which structures to focus on, unless one somehow considers arbitrary structures, which may be very difficult.) Most relatedly, structured greedy bandits were handled in a separate paper (Slivkins et al., 2025).

Cross-prompt generalization could mitigate model deterioration by updating estimates for unobserved prompt-answer pairs. However, whether it eliminates deterioration depends on the particular structure and learning rule. A point of comparison: structured greedy bandits are typically prone to optimization failures, but the corresponding construction needs to be tailored to the particular structure.

Re users’ best response. Indeed, in reality the user population faces its own bandit exploration and adjusts only eventually and approximately. We abstract this away in our model, assuming exact best-response. (And we acknowledge these idealizations as we describe our model in Section 2.) We believe this is reasonable for an already quite complicated model.

Reviewer_xyK5OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a stylized model of an AI system that is repeatedly retrained on data from strategic users. Users have latent intents and interact with the model only through a finite set of K prompts; the designer chooses an answer per prompt by greedily maximizing running empirical reward estimates at the prompt–answer level (bandit feedback, no exploration), and users then best-respond by re-routing each intent to the prompt whose current answer is best for it. Utilities are aligned. Two failure modes are studied. (1) Optimization failure: the dynamics lock into a policy pair with utility bounded away from the optimal Nash value (equivalently, linear policy regret). Theorem 3.2 shows this happens with positive, albeit exponentially small, probability for every non-degenerate instance; Theorems 3.4, 3.9 and 3.11 give stronger bounds under a “required answer” assumption, a Δ-robust biclustering assumption, and a “Nash-devious” biclustering, respectively, with the last yielding failure probability 1−o(1). (2) Model deterioration: the long-run utility is strictly below the utility of the initial policy pair. The paper gives an explicit 3×2×3 example (Theorem 4.3), shows the phenomenon occupies a positive-measure set of reward matrices robust to tie-breaking (Theorem 4.4) and embeds into arbitrarily large games (Theorem 4.5), with utility loss approaching 1/2. A Monte Carlo study over 10^5 random 3×2×3 instances reports deterioration in 5.85% of instances (0.95% tie-free). Finally, Appendix D shows that removing either the prompt interface or bandit feedback makes utility weakly monotone over time (Lemma D.3, Theorems D.2, D.4, D.5), isolating the two ingredients jointly responsible for deterioration.

Critical strengths

The modeling contribution is clean and well-motivated. The three ingredients the paper isolates (greedy updates, strategic prompt adaptation, and unobserved intents that are pooled at the prompt level) are real features of deployed systems, and the model expresses them with minimal machinery: a common-payoff Stackelberg game plus running-average estimates. The decomposition in Table 2 / Appendix D is the most interesting conceptual result: deterioration needs both bandit feedback and prompt-level aggregation, and the proof of Lemma D.3 (full-feedback follow-the-leader against a myopic best-responding follower is weakly utility-improving in any finite common-payoff game) is short and general. The deterioration mechanism itself (an estimate for a pooled population is frozen while the population at that prompt shifts, so the designer later “returns” to an answer whose stale estimate was inflated by a user who has since left) is an intuitive and, to my knowledge, new explanation of how retraining on interaction data can degrade a system even with aligned incentives and no exogenous distribution shift.

The technical content I checked is correct. I verified by hand the numerics of the 3×2×3 witness in Theorem 4.3 / Appendix D.1 (initial estimates 0.525/0.740/0.495, the switching time t = 18, the limit utility 1.55), that the inequalities (6)–(8) are satisfied by the witness and do imply the trajectory in Eq. (5), the proofs of Theorems 3.2, 3.4, 3.11, 3.14 and Lemmas B.1, C.3, D.3, and I independently recomputed the exact volume of the canonical region in Appendix D.3 by symbolic integration, obtaining 827/15,482,880 as stated. I also re-implemented the dynamics of Appendix A/D.7 from scratch (deterministic rewards, n0 = 1, lowest-index tie-breaking) and on 4×10^4 fresh random instances obtained deterioration in 5.97% ± 0.12% of instances (0.96% ± 0.05% tie-free, 5.01% ± 0.11% tie-dependent), which agrees with Table 1 within sampling error; every sampled instance in the canonical region did exhibit robust deterioration, as Theorem 4.4 predicts. The fact that deterioration is a positive-measure phenomenon rather than a knife-edge example, and that the constructions avoid ties altogether, is a genuine strength over typical “counterexample” papers.

The paper is honest about its limitations: it states explicitly that the Theorem 3.2 bound is astronomically small, that the canonical region captures only a small fraction of deterioration, and that non-robust deterioration depends on tie-breaking. The reproducibility statement is credible: an anonymous repository exists, its README documents the exact commands (robust_trap_search, trap_volume, compare_trap_deterioration, one_switch_catalogue, harm_analysis) and conventions matching Appendix D.7, and it ships tests.

Critical weaknesses
  • The gap between the model and the title/abstract framing is large, and the paper does not test whether its failure modes survive minimal, realistic changes to the retraining rule. Every failure result is driven by estimates that are exactly zero or exactly frozen forever: Theorems 3.2, 3.4, 3.9 need the critical answer to have all-zero initial Bernoulli samples at every relevant intent, Theorem 3.11 needs exact zero rewards across biclusters (Δ-robustness), and deterioration needs an estimate that is never refreshed. Any ε-exploration, optimistic initialization, recency weighting / sliding window, or sampling temperature, all of which real retraining pipelines contain in some form, plausibly destroys these mechanisms, and the paper neither analyzes nor simulates any of them. The results are non-degenerate in instance space but may be degenerate in algorithm space, and for a paper that motivates itself with “modern AI systems” that is the question a reader most wants answered. Relatedly, the Nash-devious failure (Theorems 3.11–3.13) hinges on prompt scarcity: it can only occur when K < |I|, because with one prompt per intent a bicluster-consistent policy already attains the global optimum. The “optimal” outcome in the example abandons a user segment entirely, so whether staying bicluster-consistent is a failure is debatable, and the assumption of a small fixed prompt vocabulary is at odds with the free-form prompting the introduction invokes. A discussion of these points, and ideally a short robustness experiment (e.g., ε-greedy or discounted averages on the same 10^5 instances), is needed.

  • The quantitative results are weak and the constructive side is missing. Theorem 3.2 (exp(−Θ(n0|I||A|))) is essentially an existence statement and its proof is a few lines of standard greedy lock-in reasoning; Theorem 3.4 is the same argument with one action. The stronger Theorem 3.11 rests on a strong structural assumption (exact zeros across clusters plus an initially consistent prompting policy). For deterioration, the theory (canonical region, Theorem 4.4) explains only about 6–7% of the already small 0.95% robust-deterioration rate, and the “one-switch catalogue” that reportedly covers > 95% is described only informally in Appendix D.5 without a theorem or a reported coverage number; the empirical study covers one game size (3×2×3), one initial prompting policy, n0 = 1 and deterministic rewards, so nothing is known about prevalence in larger games, with more data, or with noisy rewards. The paper also offers no positive result: which simple modification of the retraining rule (exploration, intent clustering, per-prompt recency) provably avoids deterioration or restores convergence? Without this, the contribution is a well-crafted negative example rather than guidance, and the impact for an ML audience is limited.

  • Several inconsistencies and loose ends in the writing and proofs. (a) The statement of Theorem C.1 contains a factor (e^{−λn0}/√(4n0Δ(1−Δ/2)))^{|I{b*}|} with a λ that is never used in the proof, which instead derives α^{n0|I{b}|}; the statement and proof do not match. (b) The SAFE bound applies Theorem C.2, stated for i.i.d. Bernoulli(α), to an adaptively routed, non-identically distributed sequence; the supermartingale argument does go through with conditional mean ≥ Δ, but this should be said. (c) Definition 4.1 measures deterioration against W0 = u(πP^init, πA^1), a policy pair that is never played (in the witness the first played round already has utility 1.99, not 1.98); the choice should be justified or replaced by the first realized utility. (d) Section 4 implicitly sets n0 = 1 (the estimates (1+0.05)/2 etc. and the (1.48+0.5t)/(t+2) formula presuppose it); the dependence of the deterioration region on n0 is not discussed. (e) “under 6%” on p. 9 does not match the stated numbers: 827/1,290,240 ≈ 0.064% divided by 0.95% is about 6.7%. (f) Notation drifts between the main text (πP, πA) and appendices (πH, πD), with typos such as Ib* and μ̂ * p, a_s. (g) The repository README states rewards are drawn from [0, 10] while the paper says [0, 1]; harmless by scale invariance but it should be aligned. (h) Related work omits the closest lines: multi-learner retraining with users who choose which learner to use (Dean et al., 2022, “Emergent specialization from participation dynamics and multi-learner retraining”; Shekhtman & Dean, 2024, “Strategic usage in a multi-learner setting”, which also shows naive retraining can fail to converge), self-consuming / model-collapse retraining loops (Shumailov et al., 2023; Alemohammad et al., 2023), and feedback loops in recommender systems, all of which a reader will expect to see contrasted with the present mechanism.

Questions for authors

See weaknesses.

2 comments

We appreciate the thoroughness of the review and the insightful comments picking up on the strengths and limitations of our approach.

Re “robustness experiments”. While we consider the core model of greedy retraining dynamics, many of our findings carry over to some relaxed models consistent with your suggestions, both theoretically and experimentally. Please see the messages “for all reviewers”.

Re Nash-devious failures. This is one result among many. Our notion of “optimization failure” is about optimizing total utility. As we show, this may require sacrificing some user segment. While utility maximization is a standard “primary” objective, alternative objectives incorporating fairness would also be interesting.

We indeed rely on “prompt scarcity” compared to #intents. The motivation is that the space of possible user intents is enormous, while what the users can realistically communicate via prompts is limited by their efforts and ingenuity.

Re no positive results. Indeed, we focus this paper on natural “greedy” dynamics in AI retraining. We believe this is an important subject on its own. One positive result that we do provide is that removing either bandit feedback or the prompt interface restores utility monotonicity (i.e., removes model deterioration). Identifying practical modifications that guarantee safe retraining is a compelling next step, building on the failure mechanisms isolated in this paper. Interestingly, (as per the new results reported above) persistent exploration alone is not sufficient to prevent model deterioration.

More broadly, we would like to design efficient algorithms in the same or similar framework. However, we believe that positive algorithmic results deserve a separate paper, as developing and analyzing such algorithms would constitute a substantial research contribution in its own right. Moreover, an algorithm design paper for the same high-level story may adopt a somewhat different technical model (e.g., use an initial AI model rather than initial data set; or perhaps invoke "algorithmic oracles" for supervised learning or regression, as is common in contextual bandits).

Re our results. For optimization failures, we focus on the “qualitative” distinction between linear and sublinear regret. Our general lower bounds are quantitatively conservative, reflecting similar limitations in the state of the art for the simpler setting of greedy bandits (as we state in Related Work). We make them somewhat stronger under some (plausible) game structures.

For model deterioration, we focus on existence and non-degeneracy (and we do establish this for arbitrary large game instances). We also provide an extension that captures most of robust deterioration observed experimentally. However, numerically stronger theoretical characterizations may be possible, especially for large game instances.

Our simulations focus on small game instances for tractactability: we approximate prevalence rates by sampling random game instances. Characterizing prevalence on large game instances remains open. We did not attempt realistic simulations with actual AI models, in part because it is unclear how to efficiently simulate users’ best-response.

Re corrections: We thank the reviewer for the exceptionally careful reading. We will correct the theorem statement and proof inconsistencies, clarify the application of the supermartingale bound to adaptively generated feedback, and fix the numerical and notational errors in the revision. Regarding the initial utility benchmark, our definition of deterioration is stronger than one using the first realized round's utility: since users best-respond, the first realized utility is always weakly-higher than our benchmark. Moreover, this is the benchmark relative to which we establish utility monotonicity when either bandit feedback or the prompt interface is removed.

Thank the authors for the detailed response. The response addresses all my concerns that I weigh heavily in favor of acceptance. It is reasonable to consider algorithmic design as out of the scope and a short discussion recording what the new results imply (small persistent exploration does not help but early exploration can) would give readers guidance that the current draft lacks.

On the new experiment the author shared, it indeed strengthens deterioration exists and survives small changes to the rule, though it does not support “exploration cannot fix it”. One possible addition is to also report tie-free or tie-dependent deterioration separately, as in Table 1 (the word used in the text was "robust") in the paper. The drop from 5.5% to 3.0% at δ=0.0001\delta = 0.0001 implies the tie-dependent cases are fragile to arbitrarily small perturbations, and the increase at larger δ\delta may desire an explanation.

That being said, this is a complete and well-studied paper with the additional results added. I would raise the score given all the edits are applied.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response to all reviewers (1/2): New theoretical results

We thank all reviewers for their thoughtful and constructive feedback. In response to questions about the robustness of our failure modes, we have obtained new theoretical results showing that they persist under several natural modifications of the retraining dynamics. We also conducted additional experiments to investigate these modifications (see second comment). We will add these additional results to the paper upon revision. We summarize our theoretical results below.

(1) Optimization failures. Most of our results (Thms 3.2, 3.4, 3.9) carry over if the designer uses recency weighting. That is, the designer can replace sample averages over the data (for each prompt-answer pair) with weighted averages, for some positive time-dependent weights that sum up to 1.

(2) Model deterioration. The main result (Thm 4.4) carries over, with the same construction, if:

  • (2a) The designer uses η\eta-exponential recency weighting.
  • (2b) The designer uses ε\varepsilon-greedy exploration, for a small enough constant ε>0\varepsilon>0. (Here, the “greedy” branch is defined the same as before. The user population best-responds to the entire ε\varepsilon-greedy policy.)
  • (2c) The user population uses δ\delta-greedy exploration, for a small enough constant δ>0\delta>0. (The designer treats all data points equally, whether they came from “explore” or “greedy” branches of the user population.)

Proof sketches are below.

Further possible extensions. Our intuition is that:

  • (1) and (2a) also carry over to an observation-based sliding window, where the designer averages the last NN observations separately for each prompt-answer pair (retaining the previous estimate when no new observations arrive), for sufficiently large NN.
  • (2b) and (2c) similarly carry over to SoftMax with a small enough temperature.

We have not worked out these extensions for this rebuttal.

Proof sketches for new results

(1) In all these results, our analysis relies on certain alternatives receiving 0 average reward in the initial data and no reward since then, whereas some other alternatives receive strictly positive average rewards. This property persists even under weighted averages.

(2a) In the original example from Thm 4.4, the designer initially selects the good policy, but changes in users' prompt choices eventually cause it to switch to the deteriorated policy πALIM\pi_A^{\mathrm{LIM}}. Under exponential recency weighting, the estimates evolve at different rates, so the timing of this switch may change, but the underlying mechanism remains: the selected answer's estimated reward responds to changes in the population using its prompt, while the estimate of the abandoned answer (a2a_2) remains frozen. Once the designer reaches the deteriorated policy, the selected answer's estimate converges toward its reward under the new population, which is higher than the abandoned answer's frozen estimate. Thus, the deteriorated policy remains stable. The only additional step is to verify that the initial switch still occurs under the new weighting rule, which it does.

(2b) Exploration eliminates the fixed point from our original analysis. Instead, the dynamics cycles between "good" and "bad" answering policies, with the designer spending most of its time using the bad policy. This happens because exploration eventually corrects the estimate of an abandoned answer, but selecting this answer changes users' prompt choices and makes it less attractive again.

(2c) Consider the example from Thm 4.4. User-side exploration does not force the designer to revisit the abandoned answer a2a_2 (the answer selected during the transient phase but never again after the switch), allowing misleading estimates to persist despite continued experimentation. For small enough δ>0\delta>0, the designer still reaches the deteriorated policy with positive probability. Once there, the estimate of the abandoned answer remains frozen because the designer never selects it. However, unlike in our original analysis, the observed rewards of the selected answers now fluctuate because users sometimes choose random prompts. These fluctuations could cause the designer to switch policies again, even though the expected rewards favor staying at the deteriorated policy. To rule this out with positive probability, we consider the cumulative reward advantage of the selected answer over the abandoned answer's fixed estimate. This advantage is a random walk with positive drift, so it has a positive probability of remaining positive forever, conditional on a sufficiently favorable finite history.

AuthorsOpenReview ↗

Response to all reviewers (2/2): New experiments

Response to all reviewers (2/2): New experiments

We ran new simulations to investigate model deterioration under the three modifications described in (2a–c) in our previous comment, as well as simultaneous designer and user exploration. As in the paper, we sampled NN random 3×2×33 \times 2 \times 3 game instances, with each reward drawn independently and uniformly from [0,1][0,1]; we used N=20,000N=20{,}000. For each combination of game instance, model, and parameter value, we generated one trajectory of length T=1,000,000T=1{,}000{,}000 rounds.

Detecting deterioration. Since some of the modified dynamics are randomized and need not converge to a fixed policy, we cannot always detect deterioration by checking for convergence. Thus, instead of checking for fixed points, we average the expected utility over the last 3T/43T/4 rounds and compare it to the initial utility under the same parameter setting. If the former is smaller by at least 0.01, we declare "deterioration". (This margin is intended to rule out random fluctuations; for comparison, the standard deviation of an average of TT independent bounded observations is O(1/T)=O(0.001)O(1/\sqrt{T})=O(0.001).) The baseline deterioration rate here is slightly lower than that reported in the original paper because our finite-horizon criterion is more stringent.

Experimental results. The estimated prevalence rates for representative parameter settings are summarized below. (The standard errors are all in the range 0.12–0.16%, not listed.) We additionally investigated joint exploration for both players, and provide a representative result in the table below.

ModelParameterPrevalence
Baseline—5.5%
2aη=0.001\eta=0.0015.5%
2aη=0.1\eta=0.15.5%
2aη=1\eta=15.5%
2bε=0.0001\varepsilon=0.00015.3%
2bε=0.01\varepsilon=0.015.2%
2bε=0.1\varepsilon=0.14.7%
2cδ=0.0001\delta=0.00013.0%
2cδ=0.01\delta=0.013.2%
2cδ=0.1\delta=0.14.7%
Joint explorationε=δ=0.1\varepsilon=\delta=0.14.1%

Main findings

  • Model deterioration persists under all three modifications. Exponential recency weighting (2a) has essentially no effect on prevalence, across six values of η\eta between 0.001 and 1. Designer exploration (2b) modestly reduces prevalence, whereas user exploration (2c) interestingly has a non-monotonic effect, with small exploration rates reducing prevalence more substantially than larger rates.

  • Deterioration also persists when both parties explore simultaneously. We tested 25 joint parameter combinations with ε,δ∈{0.0001,0.001,0.01,0.05,0.1}\varepsilon,\delta \in \{0.0001,0.001,0.01,0.05,0.1\}, obtaining deterioration rates between 2.7% and 4.5%. We omit them from the table for brevity.

Thus, model deterioration is not an artifact of cumulative averaging or absent exploration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.