In their paper Coevolutionary Free Lunches David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve two-player games in which a player tries to minimize expected search cost given optimal play, or at least good play, by an opponent.  Free lunches are allowed in this case because the exact choice of cost function to minimize changes depending on which fitness (i.e. objective) functions previous rounds of play have ruled out. In other words, given that an opponent already knows something about the game, and chooses responses that minimize the player's expected return, the player can eliminate certain fitness functions without having to evaluate them. To illustrate how this works, W&M provide this chart: Here, $\langle g \rangle$ represents the search algorithm that pays no attention to the opponent's moves; $\langle g \rangle_{1}$ represents the search algorithm that considers all possible opponent replies to each move; and $\langle g \rangle_{2}$ represents the search algorithm that samples just one possible opponent reply to each move. This illustrates the character of the free lunch provided: algorithms that take into account information provided by the opponent do better than algorithms that don't, and those that collect as much information as possible from the opponent do better than those that only collect some. W&M amplify this point in their later discussion of opponent intelligence. They show that even when an opponent is not omniscient, but has partial knowledge, the player can exploit its partial knowledge. In the case of total ignorance this won't work because the opponent always replies with a random move. In that case, there appears to be no gain: the expected performance of the agent will be the average over the antagonists possible responses.I guess this looks like $\langle g \rangle$ above. But in cases where the opponent has some knowledge, algorithm performance appears to increase monotonically with opponent intelligence.What confuses me about all this is that the argument appears to boil down to the following trivial-seeming claim: across all problem domains, algorithms that bother to learn from knowledgable opponents do better than algorithms that do not. That is, as long as you don't turn down the free lunch, you can have it. In effect, lunch is free because the opponent is buying.If that's true, then couldn't we imagine a whole range of games in which, say, players play cooperative games with oracles, and those that refuse to cooperate perform worse on all problems? That's a free lunch in the same sense, right? But then we haven't explained where the oracle's knowledge comes from.Does this mean that if we had to model the source of the other player's knowledge, we'd be back in the No Free Lunch zone? Or is the claim really that this sort of competitive play yields better outcomes even when both players start out in total ignorance, as the phrase free lunch seems to imply?
Are coevolutionary Free Lunches really free lunches?
optimization;machine learning