Are coevolutionary "Free Lunches" really free lunches?
Coevolutionary algorithms can't magically accelerate progress on any arbitrary problem class. So in that sense, the conclusion at the end of the question is correct. However, it doesn't follow that all coevolutionary free lunches are trivial, as the conclusion of the question suggests. 

I can't offer an exhaustive account of all the kinds of coevolutionary free lunches, but I can offer two examples, the first of which is trivial, and the second of which I would argue is nontrivial. The second is nontrivial because it helps explain why the no free lunch theorem really must hold.

The important difference between the two examples is this: in the first, the competing algorithms are competing to achieve the same overarching goal, while in the second, the competing algorithms are trying to achieve different goals. In the second case, the mismatch between the two algorithms' goals allows interesting things to happen. I'll begin with the trivial example.

Opponents seeking the same goal

Imagine a very simple optimization problem in which the search landscape is a 7x7 grid of cells. The primary goal is to find the cell with the maximum value. 48 of the cells have a value of 0, and one randomly chosen cell on the grid has a value of 1.

Our secondary goal is to discover a search strategy that finds the maximum value more quickly. But it follows from the initial problem that no strategy could possibly beat random search here, because nothing can be learned from one cell about another. Nonetheless, the coevolutionary free lunch theorem holds! Here's why:

Suppose you have two optimization algorithms, A and B, both searching the grid. It doesn't really matter what strategy they use, but for concreteness, we'll stipulate that they both use a random search strategy. The only difference between them is that B pays attention to A's moves, and when it sees that A has found the maximum value, it jumps to that cell too. In some sense, when that happens, B has still "lost" the contest. But if you run a lot of competitions, and then compare the average performance of A to the average performance of B, you'll see that B finds the maximum value faster on average.

The explanation is simple. The average time to first discovery -- whether by A or B -- stays the same. But whenever A beats B to the win, B doesn't bother looking anywhere else. It skips ahead to the best cell. When B beats A to the win, on the other hand, A just continues searching, plodding along until it finds the maximum value on its own.

This looks like a win if you're only counting the number of moves B makes. If you look at the total number of moves that A and B make together, they actually do worse together than either would on its own, on average. That's because of A's obliviousness. If we change A to behave the same way as B, then they do about as well together as either would on its own -- but no better. 

So here, modeling both algorithms together returns us directly to the no free lunch zone, just as the question argues. In effect, A and B are just performing random search algorithms in parallel. The final number of search operations remains the same.

Opponents seeking different goals

Now imagine a very different scenario. Suppose we have a classification problem: recognizing sheep. Here, A's job is to look at a stream of pictures and say whether there are sheep in them. Simple enough.

But B's job is very different. B has the power to inject pictures of its own into the stream! Its goal is not to identify sheep; it just wants to slow A down.

How can B do this? There's a great blog post and associated Twitter thread about a closely related question by Janelle Shane. The Twitter thread begins:


  Does anyone have a picture of sheep in a really unusual place? It's for pranking a neural net.


And here's one of the first replies:


  How about an orange sheep?


Here's the orange sheep:



Turns out, this was perfect for pranking:


  You totally got it. Orange sheep are not a thing it was expecting. 
  "a brown cow laying on top of a lush green field"


Here are a couple of other examples from Shane's blog post:





So what does this have to do with our problem? We can connect them by being more precise. Suppose A's goal is to reach greater than 99% accuracy, and B has the power to inject one picture into A's stream for every nine "natural" pictures. B looks for patterns in A's behavior and uses them to find pictures that mess with its model. This will keep A's accuracy below 99% for much longer than if A saw only "natural" pictures.

Two things follow from this. First, B will do much better if it pays attention to what A does. If B just picks images on the basis of some randomly chosen general principle like "sheep in odd places," then there's a good chance that A will be prepared for them already. If not, it will quickly learn to handle them correctly, and B will then have to adopt a new strategy. On the other hand, if B watches A's behavior, it can pick out the specific things that A is worst at, and focus on those. As soon as A improves at one of them, B can have another one ready to go. As long as B can find patterns in A's behavior, B will always present the most challenging images for A.

Second, A will do much better if it pays attention to which images B picks. After all, B is looking for patterns in A's behavior. If it finds patterns, then it will use those patterns to send fake or troublesome pictures to A. In turn, that means that there will be noticeable patterns driving B's choices. Here again, if A is paying attention to the patterns in B's behavior, it will more quickly be able to identify which pictures B is injecting.

What's important is that in this scenario, both A and B are relying on data that is guaranteed to have patterns. It is guaranteed to have patterns because if A is doing its best, A is doing something other than random search. And if B is doing its best, then B is doing something other than random search. 

So initially, this looks like a really compelling free lunch situation. But what have we actually shown? We've shown this:


  As long as A is doing something other than random search, B can always find out-of-band samples that A's methods cannot handle.


That's the no free lunch theorem in a nutshell!

The only way A can prevent B from finding out-of-band images is by behaving in ways that look random to B. But if A's behavior isn't really random, then in the very long run, B will always be able to find the pattern -- even if B itself is only doing random search.

The very same argument works in the other direction. The only way B can prevent A from noticing patterns in its images is by behaving in random-seeming ways. But if B's behavior isn't really random, A will eventually find the pattern, even if it's only doing random search.

In this scenario, both algorithms will try to fool each other by adopting more and more complex, random-seeming behaviors. So in the very, very long run, they will slowly converge to a truly random search -- which is the best any algorithm can do on average across all problem domains.

An infinite pool of randomness

It might be that these coevolutionary learning strategies do still have this advantage over others: they may encourage both algorithms to explore the space of relevant non-random behaviors more quickly or extensively. I am not even sure of that. Either way, the no free lunch theorem holds in general, because the space of possible non-random behaviors is far, far smaller than the space of possible random behaviors.

How do we know? It would be off topic to go into a detailed proof, but consider the related question of how many long strings can be compressed into shorter strings. Regardless of the compression method, the majority of all strings cannot be compressed at all. This is easy to prove with a bin-counting argument. Suppose we consider binary strings, and start with the empty string. Assuming there can be no negative-length strings, that's incompressible. Now consider length-1 strings. There are two, but there's only one length-0 string, so only one of them can be compressed. Now we have two incompressible strings, and a third string that can be compressed by one bit. Moving on to length-2 strings: there are four, but there are only two length-1 strings, and the one length-0 string is already taken, so we can only compress two of the length-2 strings. The other two are incompressible. That's three compressible strings and four incompressible strings... and so on.

As the numbers get higher, one of the things you notice is that even among the compressible strings, half of them are only compressible by one bit, because they compress to strings that are themselves incompressible. A quarter are only compressible by two bits; an eighth are only compressible by three bits. No matter how you slice it, the number of substantially compressible strings is always much lower than the number of strings that are incompressible or barely compressible.

The line of reasoning for random behavior is similar. You could also connect these ideas to the proof that there are vastly more real numbers than integers. In the global scheme of things, the no free lunch theorem is true because the scope of randomness is unimaginably vast.