Abstract: As machine learning systems increasingly train on self-annotated data, they risk reinforcing errors and becoming echo chambers of their own beliefs. We model this phenomenon by introducing a learning-theoretic framework: Online Learning in the Replay Setting. In round (t), the learner outputs a hypothesis (\hat{h}_t); the adversary then reveals either the true label (f^{*}(x_t)) or a replayed label (\hat{h}_i(x_t)) from an earlier round (i \lt t). A mistake is counted only when the true label is shown, yet classical algorithms such as the SOA or the halving algorithm are easily misled by the replayed errors.
Introduction
The proliferation of generative AI has created a recursive feedback loop where models are increasingly trained on data they (or their predecessors) produced. This "model collapse" or "echo chamber" effect can lead to the reinforcement of errors and a narrowing of the model's worldview. While this has been observed empirically, particularly in Large Language Models (LLMs), theoretical understanding has lagged. This paper introduces a formal framework to analyze this phenomenon: Online Learning in the Replay Setting.
The Replay Setting and Complexity
In the Replay Setting, a learner interacts with an environment where feedback is not always the ground truth. Specifically, an adversary can choose to show the learner a "replayed" label—a prediction the learner itself made in a previous round. Because the learner cannot distinguish between a true label and a replayed one, it risks "learning" from its own past mistakes. If a model makes an early mistake and then "learns" from that mistake replayed as truth, it can fall into a trap where it never corrects itself.
To characterize learnability in this environment, the authors move beyond the standard Littlestone dimension and introduce the Extended Threshold dimension (ExThD). This measure captures the complexity of a hypothesis class when subjected to self-referential feedback. They also define the Threshold dimension (ThD) for intersection-closed classes, which represents the length of the longest chain of nested hypotheses.
The Closure Algorithm
A key contribution of the work is the Closure Algorithm, a conservative learning strategy designed to resist "gaslighting" by the adversary. Unlike standard algorithms that update on any perceived error, the Closure Algorithm only updates its internal hypothesis when it receives a label that is logically impossible to have been a replay.
The algorithm maintains a "Reliable Version Space" by considering only hypotheses consistent with labels that contradict all previous predictions for a given point. By using the intersection closure of the hypothesis class, it ensures that it only adopts the most restrictive hypothesis consistent with the verified ground truth. This highlights a qualitative difference in the setting: while proper learners (restricted to the original class) may fail, improper learners using the closure of the class can often succeed.
Key Results and Theoretical Bounds
The authors demonstrate a fundamental separation between standard online learning and the Replay Setting. Tasks that are typically easy, requiring only logarithmic mistakes (like learning thresholds), can become significantly harder, requiring linear mistakes when a replay adversary is present. For example, learning thresholds on a domain of size $N$ requires $O(\log N)$ mistakes normally, but a replay adversary can force $\Omega(N)$ mistakes.
As summarized in the table above, the mistake bounds are tightly linked to the proposed complexity measures. For an adaptive adversary, the mistake bound is $\Theta(\text{ExThD}(\mathcal{H}))$. In the stochastic setting, where the adversary's choices are less malicious, the expected mistakes often scale with $\log T$, though a gap remains involving the VC dimension. The authors also show that for convex bodies in $\mathbb{R}^d$, the expected number of mistakes scales as $O(T^{\frac{d-1}{d+1}})$ for $d \ge 2$.
Conclusion and Future Directions
This research provides the first rigorous characterization of learning in self-referential environments. It identifies the conditions under which a model can successfully escape its own "echo chamber" and provides optimal algorithms for doing so. Future work includes addressing the computational complexity of finding optimal representations for ExThD and exploring more realistic, less adversarial replay models, such as "consensus" models where labels are only replayed if multiple past versions agreed.
Summary updated