The efficiency of information gain by natural selection

Natural selection enriches populations for genotypes that are well adapted to their environments, accumulating information about the selective conditions in the process. Therefore, selection can be viewed as a learning process through which populations acquire information about the environment. Motoo Kimura derived a relationship between the amount of information gained by selection and a measure of the inefficiency of the selective process, known as substitution load [M. Kimura, Genet. Res. 2, 127-140 (1961)]. Due to the gradual nature of selection and the ongoing mismatch of types to the environment, a lineage that is still acquiring information has lower mean fitness than a lineage that already has it. While this has been an influential insight, we find that Kimura's model is inconsistent with selection experiments involving Escherichia coli. To address limitations in this model and develop a more robust measure for the efficiency of selection, we turn to computational learning theory. We show that the learning-theoretic concept of regret quantifies the inefficiency of selection as a learning process in terms of relative lineage fitness. We establish bounds on the efficiency of information gain in general settings, including frequency-dependent selection and arbitrary environmental change. We experimentally validate these bounds and demonstrate that our extended theory recovers Kimura's fundamental insight. Finally, we show that selection is an asymptotically optimal algorithm for the basic problem faced by evolving populations and that it acquires information more efficiently than comparable processes in complex environments.