How Stale Opponent Information Moves the Error Threshold in Coevolution

Evolutionary algorithms search by copying good candidates and randomly altering ("mutating") them. Theory shows a sharp tipping point in how much mutation they can tolerate. Below a critical mutation rate, selection keeps the population organised around good solutions and the running time is polynomial. Above it, random changes erase what selection has built, and the running time becomes exponential. Biologists call this tipping point the error threshold. Competitive coevolution runs two populations against each other to solve min-max games, and for it the threshold has now been proved rigorously. Every such proof assumes that each population is scored against the current state of its opponent. In any distributed deployment that assumption fails, because opponent samples arrive through a queue or a lossy channel and are always somewhat out of date. Age of Information is a networking measure that captures exactly this: the time since the freshest delivered update was generated. It rises with slope one between deliveries and drops when a new update lands, which produces a sawtooth.

This note proposes to measure and prove how the age of opponent information shifts the coevolutionary error threshold. The central claim is that staleness is not just another kind of fitness noise. When every individual in population $P$ is scored against the same outdated snapshot of population $Q$, the error is shared across the whole population, and it is biased in one direction. The population-level averaging that protects non-elitist algorithms against independent noise therefore does not protect them against staleness. On games where the best reply flips sides, such as the BILINEAR benchmark, the delay also induces overshoot oscillations. These should make the threshold depend on how long the gaps between updates can get (peak age), not only on how long they are on average.

Core Claim

We make three predictions that can each be checked. The first is that on BILINEAR, the critical mutation rate $\chi^*$ of the Pairwise Dominance Coevolutionary Algorithm (PDCoEA) falls as opponent age grows. The second is that two age processes with the same mean age but different peak age produce measurably different $\chi^*$, with peak age the better predictor. The third is a deliberate null prediction: retention of an already-found strict Nash equilibrium is almost insensitive to age. Once the opponent sits at a strict equilibrium, a stale snapshot of it is nearly identical to a fresh one. If the third prediction fails, our mechanism is wrong.

The mechanism is as follows. In BILINEAR, $g(x,y)=\|y\|(\|x\|-\beta n)-\alpha n\|x\|$, where $\|x\|$ counts the ones in bitstring $x\in\{0,1\}^n$ and $\alpha,\beta\in(0,1)$ are constants. The minimising player's best reply switches from all-ones to all-zeros as $\|x\|$ crosses $\beta n$. A maximiser scored against an old snapshot of $y$ keeps moving in a direction that has already stopped paying off. The resulting overshoot grows with the length of the update gap. Mutation widens it further. The sum of the two can push the population's typical distance from the target beyond what selection can pull back.

Relation to Prior Work

Three results supply the method and define the synchronous baseline. Runtime Analysis of Competitive Co-evolutionary Algorithms for Maximin Optimisation of a Bilinear Function builds a level-based argument over the joint state of both populations. It proves an expected runtime of $O(r\lambda^3 n)$ for population size $\lambda\ge 2000\ln n$ and an exponential blow-up above a constant mutation threshold, with evaluations assumed instantaneous. Theoretical Guarantees for the Retention of Strict Nash Equilibria by Coevolutionary Algorithms combines drift arguments with McDiarmid's inequality. It gives closed-form safe mutation rates $q_0(\gamma)$ for keeping a fraction $\gamma$ of the population at a strict equilibrium, also under synchronous play. We reuse both proof templates and add an age variable to the conditioning.

More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments both motivates and constrains the work. It shows that non-elitist populations with tournament selection absorb independent noise without resampling. That is exactly the protection we predict staleness defeats, because the staleness error is shared across the population rather than independent per evaluation. The negative-drift lower bounds of Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift supply the tool for the exponential side of the threshold.

On the Age of Information side, three papers shape the design. Optimizing Age-of-Information in a Multi-class Queueing System introduces peak age, the quantity we predict governs the threshold. Age-of-Information Bandits shows that failed updates compound because age keeps accumulating. It also shows that policies which explore when age is low and exploit when age is high beat age-blind ones. Our age-aware mutation schedule borrows that idea, though that paper studies regret over a handful of channels, not population search. The Dynamic Behavior of Frameless ALOHA: Drift Analysis, Throughput, and Age of Information uses drift in the queueing sense, meaning the expected change in the number of contending users, and exhibits a throughput-versus-freshness trade-off. We use drift in the runtime sense, as a bound on the hitting time of an optimiser. Its trade-off becomes our batching experiment. Age of Information: The Gamma Awakening shows that non-preemptive last-come-first-served can beat preemptive service. This warns us not to assume that dropping in-flight evaluations is always right.

Research Program

The model is PDCoEA in which population $P$ is scored against a snapshot of $Q$ delivered by an external update process, and symmetrically for $Q$. Age $\Delta_t$ is measured in generations. The update process is exogenous and independent of the search state. We study deterministic period-$D$ updates, geometric updates from a Bernoulli channel with success probability $p$, and a queue with and without preemption. We also build a control in which each individual receives an independently aged snapshot. This control has the same mean age but no shared error.

On the theory side, we generalise the drift condition to depend on age,

$$\mathbb{E}[X_t - X_{t+1}\mid X_t, \Delta_t] \ge \epsilon(\Delta_t),$$

where $X_t$ is the level-based potential (the distance of the joint population from the $\epsilon$-approximate region) and $\epsilon(\cdot)$ is the progress per generation at a given age. Because the age process renews at every delivery, we apply additive and negative drift over whole update cycles rather than single generations. Let $C$ be a cycle length. The process then has positive drift if

$$\mathbb{E}\Big[\textstyle\sum_{a=0}^{C-1}\epsilon(a)\Big] > 0.$$

It is driven to exponential time if this expectation is negative and $C$ has light enough tails for the negative-drift theorem to apply.

On BILINEAR we expect $\epsilon(a)$ to become negative beyond a critical age that decreases in $\chi$. This is where the dependence on peak age comes from: long cycles spend many generations in the negative-progress region. The result would be a computable $\chi^*$ as a function of the age distribution. It would reduce to the synchronous constant when $D=1$.

On the retention side, we extend the $\gamma$-stability argument and expect $q_0(\gamma)$ to change only through second-order terms. The final piece is an age-aware schedule $\chi(\Delta_t)$ that lowers mutation as age rises. We will try to prove that it restores polynomial time for age processes under which fixed-rate PDCoEA is exponential.

Baselines

The naive reference point is synchronous PDCoEA ($\Delta\equiv 0$) on the same instances. Its runtime guarantee is $O(r\lambda^3 n)$ at $\lambda\ge 2000\ln n$, from Runtime Analysis of Competitive Co-evolutionary Algorithms for Maximin Optimisation of a Bilinear Function. No reported empirical runtime or measured threshold value for PDCoEA on BILINEAR was found on Lacuna. We will therefore measure its $\chi^*$ ourselves using the same budget as every other variant.

The strongest existing method is fixed-rate PDCoEA run under staleness at the best mutation rate found by a grid search, with the grid identical across all conditions. On retention, the strongest existing result is the synchronous $q_0(\gamma)$ bound from Theoretical Guarantees for the Retention of Strict Nash Equilibria by Coevolutionary Algorithms. Its empirical stability transition was run with population 10,000 over 400,000 evaluations and "fell exactly between the theoretical upper and lower bounds"; we reuse that population size and budget.

The key ablation is the independent-age control, which keeps each evaluation's age distribution and removes only the sharing across the population. A second ablation replaces staleness with independent fitness noise matched to its variance, which is the setting of More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments.

Every variant receives the same evaluation budget, the same $\lambda$ and $n$ grid, the same random seeds, and the same mutation-rate grid. We would consider the proposal successful under three conditions. Shared staleness must lower $\chi^*$ measurably more than both the independent-age control and matched noise. Peak age must predict $\chi^*$ better than mean age across the age processes. The age-aware schedule must solve instances within budget in cases where the best fixed rate does not.

Why not just…?

Why not just treat staleness as noise and apply the existing noisy-EA theorems? This is the most serious threat. If mapping age to an equivalent noise level reproduces the measured $\chi^*$, our main claim is false and the result reduces to a corollary of More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments. There is a structural reason to doubt the mapping: the stale error is identical for every individual and biased in one direction, whereas the population buffer in that paper relies on errors being independent. The matched-noise and independent-age ablations settle the question directly. If either one matches shared staleness, we will report that.

Why not just pick a conservatively lower mutation rate? A fixed safety margin may be enough when age is bounded. That would make the age-aware schedule unnecessary, though the threshold characterisation would still be needed to size the margin. The experiments compare the best fixed rate against the schedule under heavy-tailed geometric age. There, a single rate that is safe during long gaps is too slow during short ones. If the best fixed rate matches the schedule, we will drop the schedule as a contribution and keep the characterisation of the threshold.

Why not just keep evaluations fresh with zero-wait or synchronous updates? In distributed runs the delay is imposed by the system, not chosen. Pushing updates as fast as possible does not reliably reduce age: Joint Status Sampling and Updating for Minimizing Age of Information in the Internet of Things shows zero-wait sampling is often suboptimal, and the Frameless ALOHA analysis shows that settings which maximise throughput can worsen freshness. We will run a batching experiment in which larger evaluation batches raise throughput but also raise age. It tests whether throughput-optimal settings cross the threshold.

Why not model it as an age-aware bandit or Markov decision process instead? Those formulations keep statistics per action. The action spaces here are bitstrings with $2^n$ elements, where the retention paper notes that exhaustive methods become infeasible. They also bound regret or time-averaged cost, not the hitting time of a search. They answer a different question from ours.

Proposed Experiments

The first experiment maps the threshold on BILINEAR. For $n$ from 50 to 400 and $\lambda$ around $c\ln n$, we sweep $\chi$ under deterministic, geometric, and queued age processes. Each process is run at several mean ages, with pairs matched in mean but differing in peak age. We record the fraction of runs that reach an $\epsilon$-approximate solution within budget, the median hitting time, and the amplitude of oscillation of $\|x\|$ around $\beta n$. The empirical $\chi^*$ is the point where the success fraction crosses one half, and we compare it with the cycle-drift prediction.

The second experiment is the null test, run on PlantedBilinear and MBJR_2024 with population 10,000 and 400,000 evaluations. We measure $\gamma$-stability as a function of mutation strength and age, and expect the transition to stay between the synchronous bounds.

The third experiment compares the age-aware schedule, the best fixed rate, and a variant with resampling, all at equal evaluation cost.

The decisive checks are three. Shared staleness must be worse than the independent-age control at equal mean age. Peak age, rather than mean age, must order the $\chi^*$ values. Retention must remain insensitive to age while the approach phase does not. Any single failure falsifies a named part of the mechanism.