The cost of information acquisition by natural selection

Natural selection enriches genotypes that are well-adapted to their environment. Over successive generations, these changes to the frequencies of types accumulate information about the selective conditions. Thus, we can think of selection as an algorithm by which populations acquire information about their environment. Kimura (1961) pointed out that every bit of information that the population gains this way comes with a minimum cost in terms of unrealized fitness (substitution load). Due to the gradual nature of selection and ongoing mismatch of types with the environment, a population that is still gaining information about the environment has lower mean fitness than a counter-factual population that already has this information. This has been an influential insight, but here we find that experimental evolution of Escherichia coli with mutations in a RNA polymerase gene (rpoB) violates Kimuras basic theory. To overcome the restrictive assumptions of Kimuras substitution load and develop a more robust measure for the cost of selection, we turn to ideas from computational learning theory. We reframe the learning problem faced by an evolving population as a population versus environment (PvE) game, which can be applied to settings beyond Kimuras theory - such as stochastic environments, frequency-dependent selection, and arbitrary environmental change. We show that the learning theoretic concept of regret measures relative lineage fitness and rigorously captures the efficiency of selection as a learning process. This lets us establish general bounds on the cost of information acquisition by natural selection. We empirically validate these bounds in our experimental system, showing that computational learning theory can account for the observations that violate Kimuras theory. Finally, we note that natural selection is a highly effective learning process in that selection is an asymptotically optimal algorithm for the problem faced by evolving populations, and no other algorithm can consistently outperform selection in general. Our results highlight the centrality of information to natural selection and the value of computational learning theory as a perspective on evolutionary biology.