When Predictions Become Supervision: Sharp Minimax Laws for Stochastic Replay

When past predictors are reused to generate new training labels, each prediction shapes both current accuracy and future supervision. We study this feedback in online learning over $K$ thresholds with a fixed but unknown target. After an initial truthful round, an independent audit reveals the true label with probability $\rho$, and otherwise an adversary-selected past predictor generates the feedback label. For horizons $T\le K^{1/2-\epsilon }$ with fixed $\epsilon \in (0,1/2)$, we establish sharp minimax rates for every $\rho$. At $\rho =1/2$, the minimax cumulative loss is $$\begin{gathered} {\Theta }_{\epsilon }(\min \\ T,T^{2/3}(\log K{)}^{1/3} \\ ) \end{gathered}$$. Achieving this rate requires sacrificing some current accuracy to preserve future information, and this tradeoff is unavoidable even for improper learners. Restricting replay to sufficiently recent predictors on average reduces the loss to $$\begin{gathered} \Theta (\min \\ T,(\log K)/\rho \\ ) \end{gathered}$$. For proper learners, revealing audit status or the selected replay source achieves the same rate. We further derive sharp rates for partial or noisy information about label generation and show that equally frequent disclosures can yield different minimax rates. Finally, with the replay source revealed but audit status hidden, fixing the reusable first predictor to $p_1\equiv 1/2$ raises the long-horizon loss from $\Theta ((\log K)/\rho )$ to $\Theta ((\log K)/{\rho }^2)$.