Introduction
On 8 September 2026, OpenAI announced that a coordinated system of artificial intelligence (AI) agents had produced a proposed resolution of the Navier–Stokes Millennium Prize problem, showing that a finite-time singularity forms under smooth external forcing [33 ] . According to OpenAI, roughly 10,000 concurrent agents explored different formulations and approaches, shared intermediate findings, and built on promising results. They reached the proposed solution in about 88 hours and then spent 17 hours formalizing and verifying it in Lean [12 ] .
This search resembles evolution: variants are generated, promising ones are retained, and useful information is passed on to later attempts. FunSearch [35 ] , AlphaEvolve [31 ] , and the Darwin Gödel Machine [42 ] follow the same principle: AI systems propose modifications to programs or agents, evaluate them, and build on the successful ones.
These ideas come together in an emerging research direction, recursive self-improvement (RSI), in which an AI system improves itself and uses the improved version to make further improvements. In the Darwin Gödel Machine, AI agents modify their own code, evaluate the resulting variants, and keep the successful changes for later generations [42 ] . More recently, Srikanth et al. [40 ] developed AIDE2 , an AI research agent that recursively modifies its own code and evaluates the results. These studies suggest that AI systems are increasingly able not only to perform complex tasks but also to improve the processes through which they perform them.
These developments point to a more fundamental possibility: AI systems may increasingly take control of their own evolution. Instead of improving within a process designed by humans, a system may decide how it searches for improvements, how extensively it experiments, and how it carries improvements forward to later generations. Because improved systems can produce further improvements, this could greatly accelerate AI development and make its capabilities harder for humans to anticipate and oversee. We call this shift agent-directed evolution . It holds great potential for scientific discovery and technological progress, but it also raises safety concerns as AI systems gain greater control over their own development.
This possibility motivates several questions. How much faster can a system adapt through learning and self-directed search than through natural selection alone? What determines the speed of adaptation, and how should an agent weigh the benefits of more search against its costs? More importantly, does faster adaptation necessarily lead to better outcomes, or can it also accelerate the development of behaviors that humans did not intend?
To address these questions, we build on the evolutionary framework of Brennan and Lo [4 , 5 ] , in which individuals inherit different behaviors and natural selection favors the behaviors that lead to faster population growth. When the environment changes, previously successful behaviors may no longer be optimal, and the population must adapt. In § 3 , we show that the growth lost to suboptimal behavior equals the Kullback–Leibler (KL) divergence between the environmental and behavioral distributions (Propositions 2 and 3). We call this loss growth regret and use it to compare how quickly Darwinian, Lamarckian, and agent-directed evolution adapt.
The three mechanisms start from the same population. Under Darwinian evolution , inherited behaviors are fixed, and the population adapts as natural selection makes better-adapted individuals more prevalent (§ 4 ). Under Lamarckian evolution , individuals can also learn from their environment and pass their acquired improvements to later generations (§ 5 ). Under agent-directed evolution , individuals further generate multiple variants of themselves, evaluate them, and retain the best for further learning (§ 6 ). More importantly, the agent decides how extensively to search, which we use as a simple model of how an intelligent system can influence its own evolution. We measure speed by the adaptation time , the number of generations needed to reduce growth regret to a given threshold, and the adaptation rate , the long-run exponential rate at which growth regret declines.
Our first set of results characterizes the adaptation speeds of the three mechanisms. Darwinian adaptation relies on natural selection to spread individuals who already have the optimal behavior, so it can take arbitrarily long when they are initially rare (Theorem 1). Lamarckian evolution removes this dependence, because individuals improve their inherited behavior directly through learning (Theorem 2). Agent-directed evolution adapts even faster by searching among alternative improvements (Theorem 3). In § 7 , we show that, when learning is sufficiently effective, agent-directed evolution has the highest long-run adaptation rate, followed by Lamarckian and then Darwinian evolution; the same ranking holds for expected adaptation times (Theorem 4).
Our second set of results, in § 6 , concerns how search accelerates adaptation and how an agent should allocate its search effort. Generating more variants always increases the adaptation rate, by an amount that depends on the difficulty of the problem (Proposition 4). For easier problems, the gain can be substantial: in the most favorable case, it grows approximately as 2 log N 2 \log N 2 log N , where N N N is the number of variants. For harder problems, the gain is smaller and approaches a finite ceiling, although more variants still speed up adaptation. When search is costly, the optimal number of variants increases as learning becomes less effective, the problem becomes easier, or search becomes cheaper (Proposition 5). An intelligent system can thus adjust its search effort according to its learning ability, problem difficulty, and available resources.
Our third set of results concerns AI safety: faster adaptation does not necessarily move a system toward the objectives its developers intend. In § 8 , we extend the agent-directed mechanism so that search and learning are guided by an incorrectly specified evaluation target. The agent then keeps improving rapidly according to its evaluator, but its true growth regret does not vanish, and more variants only accelerate convergence toward the incorrect target (Theorem 5). Natural selection, acting on realized outcomes, can eventually correct the population’s behavior, but this correction may be slow. Independent evaluation and oversight therefore become increasingly important.
Our analysis brings together ideas from evolutionary biology, economics, and AI: drawing on the biological mechanisms of selection and inheritance, we use a growth-based framework to study how learning and search affect the speed and cost of adaptation in AI systems. Appendix § 12 summarizes how the main elements of our model correspond to their counterparts in evolutionary biology and modern AI systems.
The remainder of this paper proceeds as follows. § 2 reviews the related literature, and § 3 introduces the Brennan–Lo framework. § 4 to § 6 analyze Darwinian, Lamarckian, and agent-directed evolution, respectively, and § 7 compares their adaptation speeds. § 8 examines adaptation toward an incorrectly specified target and its implications for AI safety. § 9 concludes.
Related Literature
We review six areas of research in evolutionary biology, information theory, economics, and AI that bear on the speed and direction of adaptation.
Natural Selection and Growth-Optimal Behavior. We build on the evolutionary model of Brennan and Lo [4 ] , in which natural selection favors inherited behaviors that lead to higher population growth. Later studies extend this framework to bounded rationality and intelligence (Brennan and Lo [5 ] ), behavioral diversification (Brennan, Lo, and Zhang [6 ] ), and learning under limited information and memory (Lo and Zhang (2021); Lo, Zhang, and Zhao (2025)). In evolutionary biology, bet hedging describes how organisms diversify their offspring’s behaviors to cope with environmental uncertainty (Cohen [10 ] ; Bull [8 ] ; Seger and Brockmann [37 ] ). Building on this literature, we study how quickly a population adapts after an environmental change.
Information Theory and Evolutionary Growth. Information and growth have long been linked. In the framework of Kelly [22 ] , the growth lost by using incorrect probabilities can be expressed in terms of the KL divergence [11 Chapter 6] , and evolutionary biology studies the fitness value of information about the environment [23 , 13 , 34 ] . We establish an analogous relationship between population growth and KL divergence, which lets us measure the loss from suboptimal behavior and compare how quickly different evolutionary mechanisms eliminate it.
Learning and the Inheritance of Acquired Traits. Previous research distinguishes learning that affects an individual’s performance from learning whose improvements are inherited. In the Baldwin effect, individual learning can facilitate evolution even without the inheritance of acquired traits [20 , 1 ] , whereas Lamarckian evolutionary algorithms pass improvements acquired through learning to offspring [41 ] . Related ideas appear in population-based training [21 ] and in methods that transfer learned knowledge across generations of neural networks [16 ] . Our Lamarckian mechanism isolates the inheritance of acquired improvements and examines how this channel changes the speed of adaptation under natural selection.
Adaptive Search and Resource Allocation. Evolutionary computation has long studied how to adjust search parameters, such as mutation rates and the distribution of candidate solutions, to improve performance [14 , 19 , 2 , 32 ] ; autoconstructive evolution goes further and lets the mechanisms of reproduction and variation evolve within the individuals themselves [39 ] . Economic models examine how agents adjust their learning rules to changing environments or forecasting performance [15 , 28 ] . More recent research on inference-time computation studies how the benefit of generating more candidates depends on problem difficulty and computational resources [7 , 38 ] . Our agent-directed mechanism poses a related decision in an evolutionary setting, how many variants to generate, and we characterize how search raises the rate of adaptation and how the optimal number of variants depends on problem difficulty, learning ability, and search costs.
RSI in AI. The possibility that intelligent machines could improve their own capabilities has been discussed since Good [18 ] ; an early formal approach is the Gödel machine of Schmidhuber [36 ] . FunSearch and AlphaEvolve use AI to generate, evaluate, and retain improved solutions [35 , 31 ] , and the Darwin Gödel Machine [42 ] , AIDE2 [40 ] , and multi-agent RSI [24 ] extend this process to AI agents themselves. These developments have prompted discussion of whether AI evolution will remain directed by humans or become increasingly autonomous [3 , 29 , 43 ] . Our analysis offers a theoretical perspective by studying how an agent’s control over its own search effort affects the speed and cost of adaptation.
Evaluation and the Direction of Adaptation. The effectiveness of search depends on how candidate improvements are evaluated. Evolutionary algorithms can exploit evaluation criteria in unintended ways [25 ] , and stronger optimization against learned reward models can widen the gap between measured reward and true quality [17 ] . We examine how an incorrectly specified evaluation target affects evolutionary adaptation and show that more search can accelerate adaptation toward the evaluator’s target without correcting the error.
The Framework
To compare different mechanisms of adaptation, we need a framework that identifies both the optimal behavior and the cost of deviating from it. We adopt the evolutionary model of Brennan and Lo [4 ] , in which natural selection favors behaviors that maximize long-run population growth. § 3.1 studies the growth of a lineage, § 3.2 extends the analysis to a population with multiple lineages, and § 3.3 introduces the three evolutionary mechanisms, establishes a common setting for comparing them, and defines the adaptation time and rate.
Growth of a lineage
Consider a large lineage of asexually reproducing individuals. In generation t t t , all individuals inherit the same behavior f t ∈ ( 0 , 1 ) f_t \in(0,1) f t ∈ ( 0 , 1 ) , choosing action a a a with probability f t f_t f t and action b b b with probability 1 − f t 1-f_t 1 − f t . The three evolutionary mechanisms considered in this study differ in whether and how f t f_t f t changes across generations. Individuals in generation t t t reproduce to form generation t + 1 t+1 t + 1 , and their reproductive success depends on the chosen action and the environmental state X t + 1 ∈ { α , β } X_{t+1} \in\{\alpha, \beta\} X t + 1 ∈ { α , β } , which is shared by all individuals. Let x a x_a x a and x b x_b x b denote the numbers of offspring produced by an individual choosing a a a and b b b , respectively. Then
( x a , x b ) = { ( m , 0 ) , X t + 1 = α , with probability p , ( 0 , m ) , X t + 1 = β , with probability 1 − p , (x_a,x_b)=
\begin{cases}
(m,0), & X_{t+1}=\alpha,\quad\text{with probability }p,\\
(0,m), & X_{t+1}=\beta,\quad\text{with probability }1-p,
\end{cases} ( x a , x b ) = { ( m , 0 ) , ( 0 , m ) , X t + 1 = α , with probability p , X t + 1 = β , with probability 1 − p ,
where m > 0 m>0 m > 0 is the number of offspring produced by an individual choosing the successful action: action a a a succeeds in state α \alpha α , and action b b b succeeds in state β \beta β . Individuals choosing the other action produce no offspring. The probability of state α \alpha α is p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , and the environmental states X 1 , X 2 , … X_1,X_2,\ldots X 1 , X 2 , … are independent across generations.
Let n t n_t n t denote the size of the lineage in generation t t t . Because the lineage is large, a fraction f t f_t f t of its individuals chooses action a a a , while the remaining fraction 1 − f t 1-f_t 1 − f t chooses action b b b . If X t + 1 = α X_{t+1}=\alpha X t + 1 = α , only those choosing a a a reproduce, each producing m m m offspring, so the lineage grows by the factor n t + 1 / n t = m f t n_{t+1}/n_t=mf_t n t + 1 / n t = m f t . Similarly, if X t + 1 = β X_{t+1}=\beta X t + 1 = β , the lineage grows by the factor n t + 1 / n t = m ( 1 − f t ) n_{t+1}/n_t=m(1-f_t) n t + 1 / n t = m ( 1 − f t ) . Taking the expected logarithm of these growth factors gives
I p ( f t ) ≡ E [ log n t + 1 n t ∣ f t ] = p log ( m f t ) + ( 1 − p ) log ( m ( 1 − f t ) ) = log m + p log f t + ( 1 − p ) log ( 1 − f t ) . (1) \begin{aligned}
I_p(f_t)\equiv\mathbb{E}\left[\left.\log\frac{n_{t+1}}{n_t}\right|f_t\right]
=p\log(mf_t)+(1-p)\log\left(m(1-f_t)\right) \\
&=\log m+p\log f_t+(1-p)\log(1-f_t). \tag*{(1)}
\end{aligned} I p ( f t ) ≡ E [ log n t n t + 1 f t ] = p log ( m f t ) + ( 1 − p ) log ( m ( 1 − f t ) ) = log m + p log f t + ( 1 − p ) log ( 1 − f t ) . (1)
We refer to I p ( f ) I_p(f) I p ( f ) as the growth rate associated with behavior f f f .
Given the growth rate in Equation (1) , we can now identify the inherited behavior that maximizes population growth.
Proposition 1 (Probability matching). For p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , I p I_p I p is strictly concave on ( 0 , 1 ) (0,1) ( 0 , 1 ) , and
arg max f ∈ ( 0 , 1 ) I p ( f ) = p . \underset{f\in(0,1)}{\operatorname{arg\,max}}\ I_p(f)=p. f ∈ ( 0 , 1 ) arg max I p ( f ) = p .
The proposition shows that a lineage maximizes its expected log growth in every generation by matching the fraction of individuals choosing each action to the probability that the action succeeds. The intuition is that diversification is essential when all individuals face the same environmental risk. A lineage that always chooses one action will eventually become extinct when the other action succeeds, whereas a lineage that divides its individuals between the two actions can reproduce in either environmental state. This is the probability-matching result of Brennan and Lo [4 ] .
To compare how different evolutionary mechanisms adapt to a changing environment, we need a measure of how much growth a lineage loses when its behavior deviates from the optimum. The following proposition defines this loss and establishes its connection to information theory.
Proposition 2 (Growth regret is relative entropy). For p , f ∈ ( 0 , 1 ) p,f \in(0,1) p , f ∈ ( 0 , 1 ) , the growth regret of behavior f f f is
R p ( f ) ≡ I p ( p ) − I p ( f ) = p log p f + ( 1 − p ) log 1 − p 1 − f = D K L ( Bern ( p ) ∥ Bern ( f ) ) ≥ 0 , (2) \mathcal{R}_p(f) \equiv I_p(p)-I_p(f)=p\log\frac{p}{f}+(1-p)\log\frac{1-p}{1-f}=D_{\mathrm{KL}}\bigl(\operatorname{Bern}(p)\mathbin{\|}\operatorname{Bern}(f)\bigr)\geq0, \tag*{(2)} R p ( f ) ≡ I p ( p ) − I p ( f ) = p log f p + ( 1 − p ) log 1 − f 1 − p = D KL ( Bern ( p ) ∥ Bern ( f ) ) ≥ 0 , (2) where Bern ( θ ) \operatorname{Bern}(\theta) Bern ( θ ) denotes the Bernoulli distribution with success probability θ \theta θ , and D K L D_{\mathrm{KL}} D KL denotes the KL divergence. Equality holds if and only if f = p f=p f = p .
The proposition shows that growth regret can be expressed exactly as the KL divergence between the environmental distribution and the inherited behavioral distribution. This result is closely related to the Kelly criterion [22 ] , which characterizes the cost of betting according to incorrect probabilities. For a lineage with the behavior f t f_t f t in generation t t t , R p ( f t ) \mathcal{R}_p(f_t) R p ( f t ) is the expected log growth that it loses from generation t t t to generation t + 1 t+1 t + 1 relative to a lineage with the optimal behavior p p p . Growth regret thus provides a natural measure of maladaptation, allowing us to compare the three evolutionary mechanisms in terms of how quickly they recover the growth lost after an environmental change.
To understand the magnitude of growth regret and how it varies with behavior f f f , consider its Taylor expansion around the optimal behavior f = p f=p f = p :
R p ( f ) = ( f − p ) 2 2 p ( 1 − p ) + O ( ( f − p ) 3 ) , f → p . (3) \mathcal{R}_p(f)=\frac{(f-p)^2}{2p(1-p)}+O\bigl((f-p)^3\bigr),\qquad f\to p. \tag*{(3)} R p ( f ) = 2 p ( 1 − p ) ( f − p ) 2 + O ( ( f − p ) 3 ) , f → p . (3)
The expansion shows that, for small deviations, growth regret increases approximately with the square of the distance from the optimum. Doubling the deviation therefore approximately quadruples the loss in growth.
Growth of a population
So far, we have considered a single lineage whose individuals share the same behavior within each generation. We now extend the analysis to a population consisting of several lineages, each with its own behavior. For simplicity, we focus on two lineages, although the results extend to more. In generation t t t , let f 1 , t f_{1,t} f 1 , t and f 2 , t f_{2,t} f 2 , t denote their behaviors, q t q_t q t and 1 − q t 1-q_t 1 − q t their population shares, and n t n_t n t the size of the entire population. The two lineages therefore contain q t n t q_t n_t q t n t and ( 1 − q t ) n t (1-q_t)n_t ( 1 − q t ) n t individuals, respectively.
To determine the growth of the entire population, we first consider the offspring produced by each lineage. If X t + 1 = α X_{t+1}=\alpha X t + 1 = α , only individuals choosing action a a a reproduce. The first lineage therefore grows by the factor m f 1 , t m f_{1,t} m f 1 , t , contributing m f 1 , t q t n t m f_{1,t}q_t n_t m f 1 , t q t n t individuals to the next generation. Similarly, the second lineage contributes m f 2 , t ( 1 − q t ) n t m f_{2,t}(1-q_t)n_t m f 2 , t ( 1 − q t ) n t individuals. Adding the two contributions, the population has m f 1 , t q t n t + m f 2 , t ( 1 − q t ) n t = m f ˉ t n t m f_{1,t}q_t n_t + m f_{2,t}(1-q_t)n_t = m\bar{f}_t n_t m f 1 , t q t n t + m f 2 , t ( 1 − q t ) n t = m f ˉ t n t individuals in generation t + 1 t+1 t + 1 , where
f ˉ t ≡ q t f 1 , t + ( 1 − q t ) f 2 , t (4) \bar{f}_t \equiv q_t f_{1,t} + (1-q_t)f_{2,t} \tag*{(4)} f ˉ t ≡ q t f 1 , t + ( 1 − q t ) f 2 , t (4)
is the average behavior of the population. If X t + 1 = β X_{t+1}=\beta X t + 1 = β , only individuals choosing action b b b reproduce. The two lineages then contribute m ( 1 − f 1 , t ) q t n t m(1-f_{1,t})q_t n_t m ( 1 − f 1 , t ) q t n t and m ( 1 − f 2 , t ) ( 1 − q t ) n t m(1-f_{2,t})(1-q_t)n_t m ( 1 − f 2 , t ) ( 1 − q t ) n t individuals, respectively, giving a total population of m ( 1 − f ˉ t ) n t m(1-\bar{f}_t)n_t m ( 1 − f ˉ t ) n t in generation t + 1 t+1 t + 1 .
We can also use these results to determine how the relative shares of the two lineages evolve through natural selection. The share of the first lineage in generation t + 1 t+1 t + 1 is its number of offspring divided by the total population size:
q t + 1 = { m f 1 , t q t n t m f ˉ t n t = q t f 1 , t f ˉ t , X t + 1 = α , m ( 1 − f 1 , t ) q t n t m ( 1 − f ˉ t ) n t = q t ( 1 − f 1 , t ) 1 − f ˉ t , X t + 1 = β . (5) q_{t+1} =
\begin{cases}
\dfrac{m f_{1,t}q_t n_t}{m\bar{f}_t n_t}=\dfrac{q_t f_{1,t}}{\bar{f}_t}, & X_{t+1}=\alpha,\\
\dfrac{m(1-f_{1,t})q_t n_t}{m(1-\bar{f}_t)n_t}=\dfrac{q_t(1-f_{1,t})}{1-\bar{f}_t}, & X_{t+1}=\beta.
\end{cases} \tag*{(5)} q t + 1 = ⎩ ⎨ ⎧ m f ˉ t n t m f 1 , t q t n t = f ˉ t q t f 1 , t , m ( 1 − f ˉ t ) n t m ( 1 − f 1 , t ) q t n t = 1 − f ˉ t q t ( 1 − f 1 , t ) , X t + 1 = α , X t + 1 = β . (5)
Equation (5) describes how natural selection changes the relative shares of the two lineages from one generation to the next.
We now consider the growth of the population as a whole. When X t + 1 = α X_{t+1}=\alpha X t + 1 = α , its size increases from n t n_t n t to m f ˉ t n t m\bar{f}_t n_t m f ˉ t n t , whereas when X t + 1 = β X_{t+1}=\beta X t + 1 = β , it increases to m ( 1 − f ˉ t ) n t m(1-\bar{f}_t)n_t m ( 1 − f ˉ t ) n t . Taking the expected logarithm of the population growth ratio n t + 1 / n t n_{t+1}/n_t n t + 1 / n t gives
I p ( q t , f 1 , t , f 2 , t ) ≡ E [ log n t + 1 n t ∣ q t , f 1 , t , f 2 , t ] = p log ( m f ˉ t ) + ( 1 − p ) log ( m ( 1 − f ˉ t ) ) = I p ( f ˉ t ) , (6) I_p(q_t,f_{1,t},f_{2,t}) \equiv\mathbb{E}\left[\left.\log\frac{n_{t+1}}{n_t}\right|q_t,f_{1,t},f_{2,t}\right] = p\log(m\bar{f}_t)+(1-p)\log\left(m(1-\bar{f}_t)\right)=I_p(\bar{f}_t), \tag*{(6)} I p ( q t , f 1 , t , f 2 , t ) ≡ E [ log n t n t + 1 q t , f 1 , t , f 2 , t ] = p log ( m f ˉ t ) + ( 1 − p ) log ( m ( 1 − f ˉ t ) ) = I p ( f ˉ t ) , (6)
where the last equality follows from Equation (1) with f ˉ t \bar{f}_t f ˉ t in place of f t f_t f t . Equation (6) shows that the population’s expected log growth depends on the behaviors of the two lineages only through their average f ˉ t \bar{f}_t f ˉ t . This is because reproductive success depends on the chosen action and the environmental state, rather than on which lineage an individual belongs to.
We can therefore measure the growth regret of the entire population in the same way as for a single lineage, by comparing its expected log growth with the optimal growth rate I p ( p ) I_p(p) I p ( p ) . Combining Equation (6) with Proposition 2 gives the following result.
Proposition 3 (Growth regret of a population with two behaviors). For p , f 1 , t , f 2 , t ∈ ( 0 , 1 ) p,f_{1,t},f_{2,t}\in(0,1) p , f 1 , t , f 2 , t ∈ ( 0 , 1 ) and q t ∈ [ 0 , 1 ] q_t\in[0,1] q t ∈ [ 0 , 1 ] ,
I p ( p ) − I p ( q t , f 1 , t , f 2 , t ) = R p ( f ˉ t ) . I_p(p)-I_p(q_t,f_{1,t},f_{2,t})=\mathcal{R}_p(\bar{f}_t). I p ( p ) − I p ( q t , f 1 , t , f 2 , t ) = R p ( f ˉ t ) . The population’s growth regret is therefore determined by its average behavior f ˉ t \bar{f}_t f ˉ t .
Mechanisms and measures of adaptation
The preceding analysis shows that a population’s growth regret depends on its average behavior, which can change through two channels: natural selection changes the relative shares of lineages, while learning or search can change their inherited behaviors. We consider three evolutionary mechanisms that differ in which of these channels are available. Under Darwinian evolution, inherited behaviors remain fixed, and adaptation occurs through natural selection alone. Lamarckian evolution additionally allows individuals to learn and pass their acquired improvements to their descendants. Agent-directed evolution further allows individuals to search among variants of their behavior. Natural selection operates under all three mechanisms.
To compare these mechanisms, we consider a common environmental change. Suppose that at time 0, the probability of state α \alpha α changes permanently from p o l d p_{\mathrm{old}} p old to p n e w ≠ p o l d p_{\mathrm{new}} \ne p_{\mathrm{old}} p new = p old . By Proposition 1, the growth-optimal behavior changes from p o l d p_{\mathrm{old}} p old to p n e w p_{\mathrm{new}} p new . We study how quickly each mechanism allows the population to adapt to the new environment.
We assume that all three mechanisms start from the same population. At time 0, a fraction q 0 ∈ ( 0 , 1 ) q_0 \in(0,1) q 0 ∈ ( 0 , 1 ) of individuals already follows the new optimal behavior p n e w p_{\mathrm{new}} p new , while the remaining fraction 1 − q 0 1-q_0 1 − q 0 follows the previously optimal behavior p o l d p_{\mathrm{old}} p old . We refer to their descendants as the adapted lineage and the maladapted lineage , respectively. These names describe their initial behaviors, since the maladapted lineage may become better adapted over time. The adapted lineage retains behavior p n e w p_{\mathrm{new}} p new throughout, while the behavior of the maladapted lineage evolves according to the mechanism under consideration.
We denote the three mechanisms by D, L, and A, respectively. For each mechanism M ∈ { D , L , A } M \in\{\mathrm{D},\mathrm{L},\mathrm{A}\} M ∈ { D , L , A } , let q t M q_t^M q t M denote the population share of the adapted lineage and f t M f_t^M f t M the behavior of the maladapted lineage in generation t t t . By Equation (4) , the population’s average behavior is
f ˉ t M = q t M p n e w + ( 1 − q t M ) f t M \bar{f}_t^M = q_t^M p_{\mathrm{new}} + (1-q_t^M)f_t^M f ˉ t M = q t M p new + ( 1 − q t M ) f t M
Under all three mechanisms, natural selection changes the population share q t M q_t^M q t M according to Equation (5) , with f 1 , t = p n e w f_{1,t}=p_{\mathrm{new}} f 1 , t = p new and f 2 , t = f t M f_{2,t}=f_t^M f 2 , t = f t M . The mechanisms differ in how the behavior f t M f_t^M f t M evolves across generations. By Proposition 3, the population’s growth regret in generation t t t is R p n e w ( f t M ) \mathcal{R}_{p_{\mathrm{new}}}(f_t^M) R p new ( f t M ) , which we use to measure maladaptation throughout. Since all three mechanisms share the initial conditions q 0 M = q 0 q_0^M=q_0 q 0 M = q 0 and f 0 M = p o l d f_0^M=p_{\mathrm{old}} f 0 M = p old , they also have the same initial growth regret. We can therefore compare how quickly the three mechanisms reduce growth regret from a common starting point.
There are two natural ways to measure the speed of adaptation. We can ask how many generations are needed to reduce regret by a specified fraction, or how rapidly regret declines over the long run. These lead to two complementary measures, adaptation time and adaptation rate, which we define for all three evolutionary mechanisms.
Definition 1 (Adaptation time). For ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and q 0 ∈ [ 0 , 1 ) q_0 \in[0,1) q 0 ∈ [ 0 , 1 ) , the adaptation time of Mechanism M is
τ M ( ε , q 0 ) ≡ min { t ≥ 0 : R p n e w ( f t M ) ≤ ε R p n e w ( f 0 M ) } . \tau^{\mathrm{M}}(\varepsilon,q_0) \equiv\min\left\{t \ge0 : \mathcal{R}_{p_{\mathrm{new}}}\left(f_t^{\mathrm{M}}\right) \le\varepsilon\mathcal{R}_{p_{\mathrm{new}}}\left(f_0^{\mathrm{M}}\right)\right\}. τ M ( ε , q 0 ) ≡ min { t ≥ 0 : R p new ( f t M ) ≤ ε R p new ( f 0 M ) } . with the convention that min ∅ = ∞ \min\varnothing= \infty min ∅ = ∞ .
Definition 2 (Adaptation rate). The adaptation rate of Mechanism M is
κ M ≡ − lim t → ∞ 1 t log R p n e w ( f t M ) , \kappa^{\mathrm{M}} \equiv-\lim_{t\to\infty}\frac{1}{t}\log\mathcal{R}_{p_{\mathrm{new}}}\left(f_t^{\mathrm{M}}\right), κ M ≡ − t → ∞ lim t 1 log R p new ( f t M ) , whenever the limit exists with probability one.
The adaptation time is the first generation in which growth regret falls to at most a fraction ε \varepsilon ε of its initial value. It depends on the mechanism M, the threshold ε \varepsilon ε , and the initial share q 0 q_0 q 0 of the adapted lineage. The adaptation rate measures the long-run exponential decay of growth regret, with a larger rate indicating faster convergence.
Darwinian Evolution
We begin with Darwinian evolution, in which the two lineages retain their respective behaviors p n e w p_{\mathrm{new}} p new and p o l d p_{\mathrm{old}} p old across generations. Since their behaviors remain fixed, the population can adapt only through changes in their relative shares under natural selection. This mechanism provides a benchmark for the other two. § 4.1 introduces the Darwinian mechanism, and § 4.2 analyzes its adaptation time and rate.
The model
The defining feature of Darwinian evolution is that adaptation occurs through natural selection rather than changes in inherited behavior. The two lineages retain their respective behaviors p n e w p_{\mathrm{new}} p new and p o l d p_{\mathrm{old}} p old , while differences in reproductive success change their relative population shares. Following Equation (5) , Mechanism D describes this process from one generation to the next.
By Proposition 3, the whole population grows in each generation as a single type-f ˉ t D \bar{f}^{\mathrm{D}}_t f ˉ t D lineage would, and its growth regret in generation t t t is R p n e w ( f ˉ t D ) \mathcal{R}_{p_{\mathrm{new}}}\left(\bar{f}^{\mathrm{D}}_t\right) R p new ( f ˉ t D ) . Although the behaviors of Mechanism D: Darwinian evolution
Start. Generation 0 has q 0 D = q 0 q_0^{\mathrm{D}}=q_0 q 0 D = q 0 and f 0 D = p o l d f_0^{\mathrm{D}}=p_{\mathrm{old}} f 0 D = p old , and each generation t ≥ 1 t\ge1 t ≥ 1 is formed from generation t − 1 t-1 t − 1 in the steps below; throughout, f ˉ t D ≡ q t D p n e w + ( 1 − q t D ) f ˉ t D \bar{f}_t^{\mathrm{D}}\equiv q_t^{\mathrm{D}}p_{\mathrm{new}}+(1-q_t^{\mathrm{D}})\bar{f}_t^{\mathrm{D}} f ˉ t D ≡ q t D p new + ( 1 − q t D ) f ˉ t D .
Inheritance. f t D = f t − 1 D = p o l d f_t^{\mathrm{D}}=f_{t-1}^{\mathrm{D}}=p_{\mathrm{old}} f t D = f t − 1 D = p old .
Selection. Once the state X t X_t X t is realized,
q t D = { q t − 1 D p n e w / f ˉ t − 1 D , X t = α , q t − 1 D ( 1 − p n e w ) / ( 1 − f ˉ t − 1 D ) , X t = β . q_t^{\mathrm{D}}=
\begin{cases}
q_{t-1}^{\mathrm{D}}p_{\mathrm{new}}/\bar{f}_{t-1}^{\mathrm{D}}, & X_t=\alpha,\\
q_{t-1}^{\mathrm{D}}(1-p_{\mathrm{new}})/(1-\bar{f}_{t-1}^{\mathrm{D}}), & X_t=\beta.
\end{cases} q t D = { q t − 1 D p new / f ˉ t − 1 D , q t − 1 D ( 1 − p new ) / ( 1 − f ˉ t − 1 D ) , X t = α , X t = β .
the two lineages remain fixed, natural selection changes their relative shares and hence the population’s average behavior.
Adaptation time and rate
The following theorem characterizes the adaptation time τ D ( ε , q 0 ) \tau^{\mathrm{D}}(\varepsilon,q_0) τ D ( ε , q 0 ) and rate κ D \kappa^{\mathrm{D}} κ D of Mechanism D, as defined in Definitions 1 and 2.
Theorem 1 (Darwinian adaptation rate and time). Under Mechanism D:
(i) for every q 0 ∈ ( 0 , 1 ) q_0\in(0,1) q 0 ∈ ( 0 , 1 ) , κ D = 2 Δ \kappa^{\mathrm{D}}=2\Delta κ D = 2Δ with probability one;
(ii)
lim ε → 0 E τ D ( ε , q 0 ) log ( 1 / ε ) = 1 κ D for every q 0 ∈ ( 0 , 1 ) , \lim_{\varepsilon\to0}\frac{\mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0)}{\log(1/\varepsilon)}=\frac{1}{\kappa^{\mathrm{D}}}\quad\text{for every }q_0\in(0,1), ε → 0 lim log ( 1/ ε ) E τ D ( ε , q 0 ) = κ D 1 for every q 0 ∈ ( 0 , 1 ) , lim q 0 → 0 E τ D ( ε , q 0 ) log ( 1 / q 0 ) = 1 Δ for every ε ∈ ( 0 , 1 ) . (7) \lim_{q_0\to0}\frac{\mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0)}{\log(1/q_0)}=\frac{1}{\Delta}\quad\text{for every }\varepsilon\in(0,1). \tag*{(7)} q 0 → 0 lim log ( 1/ q 0 ) E τ D ( ε , q 0 ) = Δ 1 for every ε ∈ ( 0 , 1 ) . (7) Here,
Δ ≡ p n e w log p n e w p o l d + ( 1 − p n e w ) log 1 − p n e w 1 − p o l d = R p n e w ( p o l d ) > 0. (8) \Delta\equiv p_{\mathrm{new}}\log\frac{p_{\mathrm{new}}}{p_{\mathrm{old}}}+(1-p_{\mathrm{new}})\log\frac{1-p_{\mathrm{new}}}{1-p_{\mathrm{old}}}=\mathcal{R}_{p_{\mathrm{new}}}(p_{\mathrm{old}})>0. \tag*{(8)} Δ ≡ p new log p old p new + ( 1 − p new ) log 1 − p old 1 − p new = R p new ( p old ) > 0. (8)
Part (i) of Theorem 1 shows that the long-run adaptation rate under Darwinian evolution is κ D = 2 Δ \kappa^{\mathrm{D}}=2\Delta κ D = 2Δ . The quantity Δ \Delta Δ is the adapted lineage’s advantage in expected log growth per generation. The larger the growth advantage Δ \Delta Δ of the adapted lineage, the faster it spreads through the population and the faster growth regret declines. The factor of two arises because growth regret is approximately quadratic near the optimum (Equation (3) ). Importantly, the adaptation rate does not depend on the initial share q 0 q_0 q 0 of the adapted lineage: regardless of how rare it is initially, the population eventually adapts at the same long-run rate.
Part (ii) of Theorem 1 explains how the expected adaptation time depends on the threshold ε \varepsilon ε and the initial share q 0 q_0 q 0 . First, for any fixed q 0 > 0 q_0 > 0 q 0 > 0 , the expected adaptation time grows like log ( 1 / ε ) / κ D \log(1/\varepsilon)/\kappa^{\mathrm{D}} log ( 1/ ε ) / κ D as ε \varepsilon ε approaches zero. Second, for any fixed threshold ε \varepsilon ε , the expected adaptation time grows like log ( 1 / q 0 ) / Δ \log(1/q_0)/\Delta log ( 1/ q 0 ) /Δ as q 0 q_0 q 0 approaches zero. The intuition is that when the adapted lineage is initially rare, it must first grow to a sufficiently large share before it can substantially improve the population’s average behavior. We call this additional delay the seed penalty . It can become arbitrarily large even though the long-run adaptation rate remains unchanged. At q 0 = 0 q_0 = 0 q 0 = 0 , adaptation is impossible: without any individuals carrying the adapted behavior, natural selection has no way to introduce it.4
Darwinian adaptation operates entirely through natural selection among fixed inherited behaviors. We next consider Lamarckian evolution, in which learning can also change the behavior passed on to future generations.
Lamarckian Evolution
We now consider Lamarckian evolution, which adds the inheritance of acquired improvements to the Darwinian framework: natural selection still determines the relative shares of the two lineages, but the maladapted lineage can also learn from the new environment and pass its improved behavior to its descendants. § 5.1 introduces the Lamarckian mechanism and examines how learning interacts with selection, and § 5.2 analyzes its adaptation time and rate.
The model
Under Lamarckian evolution, individuals can acquire better behavior during their lifetimes and pass it on to their descendants, so the initially maladapted lineage can improve its inherited behavior over successive generations instead of relying entirely on natural selection to increase the share of the already adapted lineage.
How much can learning improve inherited behavior in each generation? If individuals could fully adopt the new optimal behavior p n e w p_{\mathrm{new}} p new and transmit it to their descendants, they could reach the optimum in a single generation. However, individuals may be able to change their behavior only partly within a lifetime, and acquired improvements may not be fully transmitted. We capture these limitations by assuming that, in each generation, learning and transmission move the maladapted lineage’s behavior a fixed fraction of the way toward the new optimum:
f t + 1 L = f t L + λ ( p n e w − f t L ) , λ ∈ ( 0 , 1 ) , (9) f^{\mathrm{L}}_{t+1}=f^{\mathrm{L}}_t+\lambda\left(p_{\mathrm{new}}-f^{\mathrm{L}}_t\right),\qquad\lambda\in(0,1), \tag*{(9)} f t + 1 L = f t L + λ ( p new − f t L ) , λ ∈ ( 0 , 1 ) , (9)
with f 0 L = p o l d f^{\mathrm{L}}_0=p_{\mathrm{old}} f 0 L = p old .
The parameter λ \lambda λ measures the effectiveness of inherited learning: it combines how much individuals can change their behavior within a generation with how faithfully these changes are passed on. A larger λ \lambda λ closes more of the remaining gap in each generation, and in the limiting case λ = 1 \lambda=1 λ = 1 , the lineage would reach the new optimum in a single generation.
Equation (9) specifies the direction and speed of learning rather than how individuals learn. Behavior moves toward the optimum of the new environment, much as training moves an AI system toward the behavior that its objective rewards. This adjustment rule is closely related to partial-adjustment and adaptive-expectations models in economics [9 , 30 ] .
Combining learning with the selection rule in Equation (5) gives Mechanism L.
Mechanism L: Lamarckian evolution
Start. Generation 0 has q 0 L = q 0 q^{\mathrm{L}}_0=q_0 q 0 L = q 0 and f 0 L = p o l d f^{\mathrm{L}}_0=p_{\mathrm{old}} f 0 L = p old , and each generation t ≥ 1 t\ge1 t ≥ 1 is formed from generation t − 1 t-1 t − 1 in the steps below; throughout, f ˉ t L ≡ q t L p n e w + ( 1 − q t L ) f t L \bar{f}^{\mathrm{L}}_t\equiv q^{\mathrm{L}}_t p_{\mathrm{new}}+(1-q^{\mathrm{L}}_t)f^{\mathrm{L}}_t f ˉ t L ≡ q t L p new + ( 1 − q t L ) f t L .
Learning. f t L = f t − 1 L + λ ( p n e w − f t − 1 L ) f^{\mathrm{L}}_t=f^{\mathrm{L}}_{t-1}+\lambda\left(p_{\mathrm{new}}-f^{\mathrm{L}}_{t-1}\right) f t L = f t − 1 L + λ ( p new − f t − 1 L ) .
Selection. Once the state X t X_t X t is realized,
q t L = { q t − 1 L p n e w / f ˉ t − 1 L , X t = α , q t − 1 L ( 1 − p n e w ) / ( 1 − f ˉ t − 1 L ) , X t = β . q^{\mathrm{L}}_t=
\begin{cases}
q^{\mathrm{L}}_{t-1}p_{\mathrm{new}}/\bar{f}^{\mathrm{L}}_{t-1}, & X_t=\alpha,\\
q^{\mathrm{L}}_{t-1}(1-p_{\mathrm{new}})/(1-\bar{f}^{\mathrm{L}}_{t-1}), & X_t=\beta.
\end{cases} q t L = { q t − 1 L p new / f ˉ t − 1 L , q t − 1 L ( 1 − p new ) / ( 1 − f ˉ t − 1 L ) , X t = α , X t = β .
Mechanism L shows the two channels of adaptation directly: f ˉ t L − p n e w = ( 1 − q t L ) ( f t L − p n e w ) \bar{f}^{\mathrm{L}}_t-p_{\mathrm{new}}=(1-q^{\mathrm{L}}_t)(f^{\mathrm{L}}_t-p_{\mathrm{new}}) f ˉ t L − p new = ( 1 − q t L ) ( f t L − p new ) . Natural selection changes the population share 1 − q t L 1-q^{\mathrm{L}}_t 1 − q t L of the maladapted lineage, while learning eliminates a fraction λ \lambda λ of its remaining behavioral gap f t L − p n e w f^{\mathrm{L}}_t-p_{\mathrm{new}} f t L − p new in each generation. The population can thus approach the new optimum even without the adapted lineage taking over.
Adaptation time and rate
The following theorem characterizes the adaptation time τ L ( ε , q 0 ) \tau^{\mathrm{L}}(\varepsilon,q_0) τ L ( ε , q 0 ) and rate κ L \kappa^{\mathrm{L}} κ L of Mechanism L, as defined in Definitions 1 and 2.
Theorem 2 (Lamarckian adaptation rate and time). Under Mechanism L:
(i) for every q 0 ∈ [ 0 , 1 ) q_0\in[0,1) q 0 ∈ [ 0 , 1 ) , κ L = − 2 log ( 1 − λ ) \kappa^{\mathrm{L}}=-2\log(1-\lambda) κ L = − 2 log ( 1 − λ ) along every history;
(ii)
lim ε → 0 E τ L ( ε , q 0 ) log ( 1 / ε ) = 1 κ L for every q 0 ∈ [ 0 , 1 ) , \lim_{\varepsilon\to0} \frac{\mathbb{E}\,\tau^{\mathrm{L}}(\varepsilon,q_0)}{\log(1/\varepsilon)} = \frac{1}{\kappa^{\mathrm{L}}}
\qquad\text{for every } q_0 \in[0,1), ε → 0 lim log ( 1/ ε ) E τ L ( ε , q 0 ) = κ L 1 for every q 0 ∈ [ 0 , 1 ) ,
sup q 0 ∈ [ 0 , 1 ) E τ L ( ε , q 0 ) < ∞ for every ε ∈ ( 0 , 1 ) . \sup_{q_0 \in[0,1)} \mathbb{E}\,\tau^{\mathrm{L}}(\varepsilon,q_0) < \infty
\qquad\text{for every } \varepsilon\in(0,1). q 0 ∈ [ 0 , 1 ) sup E τ L ( ε , q 0 ) < ∞ for every ε ∈ ( 0 , 1 ) .
Part (i) of Theorem 2 shows that the long-run adaptation rate under Lamarckian evolution is κ L = − 2 log ( 1 − λ ) \kappa^{\mathrm{L}}=-2\log(1-\lambda) κ L = − 2 log ( 1 − λ ) : the larger the learning parameter λ \lambda λ , the faster the maladapted lineage moves toward the new optimum. Unlike under Darwinian evolution, the rate is determined by the speed of learning rather than by the growth advantage Δ \Delta Δ of the adapted lineage. Under Darwinian evolution, the two lineages retain their original behaviors, so the adapted lineage keeps a constant growth advantage. Under Lamarckian evolution, learning gradually eliminates this advantage by improving the maladapted lineage, and natural selection weakens as the two lineages become more similar. Although selection continues to operate, long-run adaptation is therefore driven by learning rather than by changes in population shares.
Part (ii) of Theorem 2 characterizes the expected adaptation time. For any fixed q 0 ∈ [ 0 , 1 ) q_0 \in[0,1) q 0 ∈ [ 0 , 1 ) , it grows like log ( 1 / ε ) / κ L \log(1/\varepsilon)/\kappa^{\mathrm{L}} log ( 1/ ε ) / κ L as ε \varepsilon ε approaches zero. More importantly, it remains uniformly bounded across all initial shares q 0 ∈ [ 0 , 1 ) q_0 \in[0,1) q 0 ∈ [ 0 , 1 ) . This is a fundamental difference from Darwinian evolution, where an initially rare adapted lineage can lead to an arbitrarily large seed penalty (Theorem 1). Under Lamarckian evolution, the maladapted lineage can improve its own behavior rather than wait to be replaced, so even when q 0 = 0 q_0=0 q 0 = 0 , with no individual initially possessing the optimal behavior, learning can still bring the population toward the new optimum.
Under Mechanism L, however, the learning process is fixed: λ \lambda λ determines the fraction of the remaining gap eliminated in each generation, and the system does not decide how to search for improvements. We next consider agent-directed evolution, in which the system can generate and evaluate multiple variants of itself and choose how many to explore, so that the process of adaptation itself becomes a decision.
Agent-Directed Evolution
We now turn to agent-directed evolution, which adds the ability to search for improvements to the Lamarckian framework: in addition to learning, the maladapted lineage can generate multiple variants of its behavior, evaluate them, and retain the best one for further learning. More importantly, the agent can decide how many variants to explore, which lets it influence the process by which it adapts. Section 6.1 introduces the agent-directed mechanism, Section 6.2 analyzes its adaptation time and rate and the gain from search, and Section 6.3 examines how many variants the agent chooses when it maximizes the speed of adaptation and when it minimizes its cost.
The model
In Mechanism L, the maladapted lineage improves its inherited behavior through a fixed learning rule. An intelligent agent may also be able to experiment with different ways of improving its behavior before passing it on: it can generate several candidate modifications of its current behavior, evaluate them, and retain the best one for further learning. We call these candidates variants and let N ≥ 1 N \ge1 N ≥ 1 denote the number of variants the agent chooses to generate in each generation.
How much improvement can these variants achieve? The outcome of any attempt is uncertain, with some variants producing substantial improvements and others very little, and the difficulty of the problem may limit how much progress even the best attempt can make. We capture both features by letting each variant move toward the new optimum by a random fraction of the remaining behavioral gap: in generation t t t , the agent generates N N N variants with behaviors
x t , j = f t − 1 A + ρ U t , j ( p n e w − f t − 1 A ) , j = 1 , … , N , (10) x_{t,j} = f^{\mathrm{A}}_{t-1} + \rho U_{t,j}\left(p_{\mathrm{new}} - f^{\mathrm{A}}_{t-1}\right), \qquad j = 1,\ldots,N, \tag*{(10)} x t , j = f t − 1 A + ρ U t , j ( p new − f t − 1 A ) , j = 1 , … , N , (10)
where the random variables U t , j U_{t,j} U t , j are independent, uniformly distributed on ( 0 , 1 ) (0,1) ( 0 , 1 ) , and independent of the environment.
The parameter ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] represents the difficulty of the problem: it is the maximum fraction of the remaining gap that a single variant can eliminate. A smaller ρ \rho ρ corresponds to a harder problem, in which even a successful attempt makes only limited progress, and when ρ = 1 \rho= 1 ρ = 1 , a single variant can move arbitrarily close to the optimum. The agent can choose how many variants to generate, but it controls neither their random outcomes nor ρ \rho ρ . As with the Lamarckian learning rule, Equation (10) is a reduced-form assumption: the agent need not know p n e w p_{\mathrm{new}} p new , but its attempts are assumed to move in the correct direction, with uncertain magnitudes.
We assume that an external evaluator compares the variants and identifies the one whose behavior is closest to p n e w p_{\mathrm{new}} p new ; the agent itself need not know p n e w p_{\mathrm{new}} p new and only receives the evaluator’s assessment. The selected variant then undergoes the same learning as in Mechanism L, moving a fraction λ \lambda λ of the remaining gap toward the optimum, and natural selection operates between the two lineages as before. Combining these steps gives Mechanism A.
Since every variant moves toward the new optimum, the evaluator selects the variant
Mechanism A: agent-directed evolution
Start. Generation 0 has q 0 A = q 0 q_0^{\mathrm{A}} = q_0 q 0 A = q 0 and f 0 A = p o l d f_0^{\mathrm{A}} = p_{\mathrm{old}} f 0 A = p old , and each generation t ≥ 1 t \ge1 t ≥ 1 is formed from generation t − 1 t-1 t − 1 in the steps below; throughout, f ˉ t A ≡ q t A p n e w + ( 1 − q t A ) f ˉ t A \bar{f}_t^{\mathrm{A}} \equiv q_t^{\mathrm{A}}p_{\mathrm{new}} + (1-q_t^{\mathrm{A}})\bar{f}_t^{\mathrm{A}} f ˉ t A ≡ q t A p new + ( 1 − q t A ) f ˉ t A .
Search. The agent creates N N N variants with behaviors x t , j = f t − 1 A + ρ U t , j ( p n e w − f t − 1 A ) x_{t,j} = f_{t-1}^{\mathrm{A}} + \rho U_{t,j}(p_{\mathrm{new}} - f_{t-1}^{\mathrm{A}}) x t , j = f t − 1 A + ρ U t , j ( p new − f t − 1 A ) for j = 1 , … , N j = 1,\ldots,N j = 1 , … , N , where the draws U t , j U_{t,j} U t , j are independent and uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) .
Evaluation. The evaluator reports J t ∈ arg min 1 ≤ j ≤ N ∣ x t , j − p n e w ∣ J_t \in\arg\min_{1 \le j \le N} |x_{t,j} - p_{\mathrm{new}}| J t ∈ arg min 1 ≤ j ≤ N ∣ x t , j − p new ∣ , and variant J t J_t J t is kept.
Learning. f t A = x t , J t + λ ( p n e w − x t , J t ) f_t^{\mathrm{A}} = x_{t,J_t} + \lambda(p_{\mathrm{new}} - x_{t,J_t}) f t A = x t , J t + λ ( p new − x t , J t ) .
Selection. Once the state X t X_t X t is realized,
q t A = { q t − 1 A p n e w / f ˉ t − 1 A , X t = α , q t − 1 A ( 1 − p n e w ) / ( 1 − f ˉ t − 1 A ) , X t = β . q_t^{\mathrm{A}} =
\begin{cases}
q_{t-1}^{\mathrm{A}}p_{\mathrm{new}}/\bar{f}_{t-1}^{\mathrm{A}}, & X_t = \alpha,\\
q_{t-1}^{\mathrm{A}}(1-p_{\mathrm{new}})/(1-\bar{f}_{t-1}^{\mathrm{A}}), & X_t = \beta.
\end{cases} q t A = { q t − 1 A p new / f ˉ t − 1 A , q t − 1 A ( 1 − p new ) / ( 1 − f ˉ t − 1 A ) , X t = α , X t = β .
with the largest random draw, U t ∗ ≡ max { U t , 1 , … , U t , N } U_t^* \equiv\max\{U_{t,1},\ldots,U_{t,N}\} U t ∗ ≡ max { U t , 1 , … , U t , N } . Search eliminates a fraction ρ U t ∗ \rho U_t^* ρ U t ∗ of the remaining behavioral gap, and learning then eliminates a fraction λ \lambda λ of what remains. Combining these two steps gives
f t A − p n e w = ( 1 − λ ) ( 1 − ρ U t ∗ ) ( f t − 1 A − p n e w ) . (11) f_t^{\mathrm{A}} - p_{\mathrm{new}} = (1-\lambda)(1-\rho U_t^*)(f_{t-1}^{\mathrm{A}} - p_{\mathrm{new}}). \tag*{(11)} f t A − p new = ( 1 − λ ) ( 1 − ρ U t ∗ ) ( f t − 1 A − p new ) . (11)
If the agent generates no variants (N = 0 N = 0 N = 0 ), we set U t ∗ = 0 U_t^* = 0 U t ∗ = 0 , and Equation (11) reduces to the Lamarckian learning rule in Equation (9) : Mechanism L is the special case of Mechanism A without search.
Adaptation time and rate
The following theorem gives the adaptation rate and time of Mechanism A, as defined in Definitions 1 and 2.
Theorem 3 (Agent-directed adaptation rate and time). Under Mechanism A:
(i) for every q 0 ∈ [ 0 , 1 ) q_0 \in[0,1) q 0 ∈ [ 0 , 1 ) , with probability one,
κ A = κ L + 2 G N ( ρ ) , \kappa^{\mathrm{A}} = \kappa^{\mathrm{L}} + 2G_N(\rho), κ A = κ L + 2 G N ( ρ ) , where
G N ( ρ ) ≡ E [ − log ( 1 − ρ U t ∗ ) ] ≥ 0 for N ≥ 1 , G 0 ( ρ ) = 0 ; (12) G_N(\rho) \equiv\mathbb{E}\left[-\log(1-\rho U_t^*)\right] \ge0 \quad\text{for } N \ge1,\qquad G_0(\rho)=0; \tag*{(12)} G N ( ρ ) ≡ E [ − log ( 1 − ρ U t ∗ ) ] ≥ 0 for N ≥ 1 , G 0 ( ρ ) = 0 ; (12)
(ii)
lim ε → 0 E T A ( ε , q 0 ) log ( 1 / ε ) = 1 κ A for every q 0 ∈ [ 0 , 1 ) , sup q 0 ∈ [ 0 , 1 ) E T A ( ε , q 0 ) < ∞ for every ε ∈ ( 0 , 1 ) . (13) \lim_{\varepsilon\to0} \frac{\mathbb{E}\mathcal{T}^{A}(\varepsilon,q_0)}{\log(1/\varepsilon)} = \frac{1}{\kappa^{A}} \quad\text{for every } q_0 \in[0,1),
\\
\sup_{q_0 \in[0,1)} \mathbb{E}\mathcal{T}^{A}(\varepsilon,q_0) < \infty\quad\text{for every } \varepsilon\in(0,1). \tag*{(13)} ε → 0 lim log ( 1/ ε ) E T A ( ε , q 0 ) = κ A 1 for every q 0 ∈ [ 0 , 1 ) , q 0 ∈ [ 0 , 1 ) sup E T A ( ε , q 0 ) < ∞ for every ε ∈ ( 0 , 1 ) . (13)
Part (i) of Theorem 3 shows that the long-run adaptation rate under agent-directed evolution is κ A = κ L + 2 G N ( ρ ) \kappa^{A} = \kappa^{L} + 2G_{N}(\rho) κ A = κ L + 2 G N ( ρ ) : unlike the Lamarckian rate, which depends only on the learning parameter λ \lambda λ , it benefits from both learning and search. The term G N ( ρ ) G_{N}(\rho) G N ( ρ ) measures the expected improvement from the best of N N N variants. As in Lamarckian evolution, natural selection continues to operate, but its influence gradually diminishes as the two lineages become better adapted, so the long-run rate is determined by learning and search.
Part (ii) of Theorem 3 characterizes the expected adaptation time. For any fixed q 0 ∈ [ 0 , 1 ) q_0 \in[0,1) q 0 ∈ [ 0 , 1 ) , it grows like log ( 1 / ε ) / κ A \log(1/\varepsilon)/\kappa^{A} log ( 1/ ε ) / κ A as ε \varepsilon ε approaches zero, and it remains uniformly bounded across all initial shares q 0 ∈ [ 0 , 1 ) q_0 \in[0,1) q 0 ∈ [ 0 , 1 ) . Like Lamarckian evolution, agent-directed evolution therefore has no seed penalty, but search provides an additional source of improvement that lets the agent adapt faster than through learning alone.
The following proposition characterizes how the gain from search depends on the number of variants N N N and the difficulty parameter ρ \rho ρ .
Proposition 4 (What search adds). For the function G N ( ρ ) G_{N}(\rho) G N ( ρ ) in Equation (12) :
(i) G N ( ρ ) G_{N}(\rho) G N ( ρ ) is strictly increasing in N N N for every ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] , and strictly increasing in ρ \rho ρ for every N ≥ 1 N \ge1 N ≥ 1 ;
(ii) G N ( 1 ) = 1 + 1 2 + ⋯ + 1 N G_{N}(1) = 1 + \frac{1}{2} + \cdots+ \frac{1}{N} G N ( 1 ) = 1 + 2 1 + ⋯ + N 1 , and lim N → ∞ G N ( 1 ) / log N = 1 \lim_{N \to\infty} G_{N}(1)/\log N = 1 lim N → ∞ G N ( 1 ) / log N = 1 ;
(iii) for ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) , G N ( ρ ) < − log ( 1 − ρ ) G_{N}(\rho) < -\log(1-\rho) G N ( ρ ) < − log ( 1 − ρ ) for every N N N , and lim N → ∞ G N ( ρ ) = − log ( 1 − ρ ) \lim_{N \to\infty} G_{N}(\rho) = -\log(1-\rho) lim N → ∞ G N ( ρ ) = − log ( 1 − ρ ) .
Part (i) of Proposition 4 shows that the gain from search increases with both the number of variants N N N and the difficulty parameter ρ \rho ρ : more variants raise the chance of finding one that makes substantial progress toward the optimum, and a larger ρ \rho ρ allows each variant to achieve greater improvements.
Part (ii) of Proposition 4 considers the case ρ = 1 \rho= 1 ρ = 1 , where a single variant can move arbitrarily close to the optimum. Then G N ( 1 ) = 1 + 1 2 + ⋯ + 1 N G_{N}(1) = 1 + \frac{1}{2} + \cdots+ \frac{1}{N} G N ( 1 ) = 1 + 2 1 + ⋯ + N 1 grows approximately like log N \log N log N , so the additional adaptation rate from search grows approximately as 2 log N 2\log N 2 log N : each additional variant contributes less than the previous one, but the total gain increases without bound.
Part (iii) of Proposition 4 considers the case ρ < 1 \rho< 1 ρ < 1 , where each variant can eliminate at most a fraction ρ \rho ρ of the remaining behavioral gap. As the number of variants increases, the best variant approaches this maximum and the adaptation rate approaches κ L − 2 log ( 1 − ρ ) \kappa^{L}-2\log(1-\rho) κ L − 2 log ( 1 − ρ ) , so, unlike when ρ = 1 \rho=1 ρ = 1 , the gain from search has a finite upper bound that depends on the difficulty of the problem. Figure B.1 in Appendix § 13 illustrates Proposition 4.
Choosing the number of variants
So far, we have treated the number of variants N N N as given. An agent that can choose how many variants to generate must decide how much search to undertake, and this decision depends on what it seeks to achieve. We consider two objectives: maximizing the speed of adaptation and minimizing its cost.
Speed-maximizing agent. Consider first an agent whose primary objective is to adapt as quickly as possible, without accounting for the cost of generating variants. It chooses N N N to maximize its adaptation rate κ A = κ L + 2 G N ( ρ ) \kappa^{A}=\kappa^{L}+2G_{N}(\rho) κ A = κ L + 2 G N ( ρ ) , which increases with N N N for every ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] by Proposition 4(i). Regardless of the difficulty of the problem, more variants therefore always lead to faster adaptation: the gain from search increases at a diminishing rate and may approach a finite upper bound when ρ < 1 \rho<1 ρ < 1 , but every additional variant still contributes. In the absence of resource constraints, a speed-maximizing agent has no finite optimal N N N and would generate as many variants as its resources permit.
OpenAI’s use of roughly 10,000 agents to tackle the Navier–Stokes problem, as discussed in the Introduction, illustrates this approach [33 ] . The scale of this effort suggests a willingness to commit substantial computational resources to exploring more possibilities in parallel, prioritizing rapid progress over minimizing the cost of search. When speed is the primary objective, generating more variants can therefore be worthwhile even at considerable expense. We next consider how the agent’s choice changes when minimizing the total cost of adaptation becomes the objective.
Cost-minimizing agent. A different objective arises for AI agents deployed to perform large numbers of tasks, such as automated bug fixing or code optimization, which may seek to reach a given performance target at the lowest possible computational cost. More variants reduce the number of generations needed to reach the target but increase the cost of each generation. To capture this tradeoff, suppose that learning costs one unit per generation and each variant an additional c > 0 c>0 c > 0 , so that a generation with N N N variants costs 1 + c N 1+cN 1 + c N .
The total cost of adaptation is the cost per generation times the number of generations needed to adapt. By Theorem 3(ii), for sufficiently stringent adaptation targets, the expected number of generations is approximately proportional to 1 / κ A 1/\kappa^{A} 1/ κ A . We therefore define the longrun cost of adaptation, approximately proportional to the expected total cost, as
C ( N ) ≡ 1 + c N κ A = 1 + c N κ L + 2 G N ( ρ ) . (14) C(N) \equiv\frac{1+cN}{\kappa^{A}} = \frac{1+cN}{\kappa^{L}+2G_{N}(\rho)}. \tag*{(14)} C ( N ) ≡ κ A 1 + c N = κ L + 2 G N ( ρ ) 1 + c N . (14)
Assuming that the agent knows its learning parameter λ \lambda λ , the difficulty parameter ρ \rho ρ , and the cost c c c , it chooses the number of variants to minimize this long-run cost:
N ∗ ( ρ , λ , c ) ∈ arg min N ∈ { 0 , 1 , 2 , … } C ( N ) . (15) N^{*}(\rho,\lambda,c) \in\arg\min_{N\in\{0,1,2,\ldots\}} C(N). \tag*{(15)} N ∗ ( ρ , λ , c ) ∈ arg N ∈ { 0 , 1 , 2 , … } min C ( N ) . (15)
The following proposition characterizes the optimal number of variants and how it depends on these parameters.
Proposition 5 (The optimal number of variants). *For the long-run cost C ( N ) C(N) C ( N ) in Equation (14) and the choice of N N N in Equation (15) :
(i) C ( N ) C(N) C ( N ) first decreases and then increases in N N N ;
(ii) N ∗ ( ρ , λ , c ) N^{*}(\rho,\lambda,c) N ∗ ( ρ , λ , c ) is nondecreasing in ρ \rho ρ and nonincreasing in λ \lambda λ and in c c c .*
Part (i) of Proposition 5 shows how the agent balances the benefits and costs of additional variants. Each new variant increases the adaptation rate by less as the number of variants grows, while its cost remains constant. When search is worthwhile, increasing N N N therefore first reduces the long-run cost, but eventually the additional cost outweighs the benefit of faster adaptation, so the agent chooses the number of variants that minimizes C ( N ) C(N) C ( N ) rather than generating as many as possible.
Part (ii) of Proposition 5 shows how this choice depends on the agent’s learning ability, the difficulty of the problem, and the cost of search. A larger λ \lambda λ lets the agent adapt more quickly through learning alone, reducing the need for search, and a higher c c c makes variants less attractive, whereas a larger ρ \rho ρ allows each variant to achieve greater improvements and makes search more valuable. The agent therefore chooses more variants when it learns more slowly, when search is less expensive, and when the problem is easier. Figure B.2 in Appendix § 13 illustrates Proposition 5.
We conclude this section by clarifying the distinction between maximizing adaptation speed and minimizing adaptation cost. The speed-maximizing agent maximizes the adaptation rate per generation. When variants can be generated and evaluated in parallel, as in OpenAI’s example, additional variants need not lengthen a generation, so maximizing the rate per generation also maximizes the rate per unit of time. If variants are instead evaluated sequentially and the duration of each generation is proportional to 1 + c N 1+cN 1 + c N , the adaptation rate per unit of time becomes κ A / ( 1 + c N ) = 1 / C ( N ) \kappa^{A}/(1+cN)=1/C(N) κ A / ( 1 + c N ) = 1/ C ( N ) , and maximizing speed yields the same optimal choice N ∗ N^* N ∗ as minimizing cost. The optimal search strategy thus depends not only on the agent’s objective but also on whether additional variants can be evaluated in parallel.
Comparing the Three Mechanisms
Having examined the three evolutionary mechanisms separately, we now compare their adaptation speeds. § 7.1 compares their adaptation rates and times, and § 7.2 illustrates the comparison numerically.
Comparing adaptation speeds
The following theorem compares the adaptation speeds of the three evolutionary mechanisms.
Theorem 4 (Ranking of adaptation speeds). Under Mechanisms D D D , L L L , and A A A , with ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] , N ≥ 1 N \ge1 N ≥ 1 , and λ ∈ ( 0 , 1 ) \lambda\in(0,1) λ ∈ ( 0 , 1 ) satisfying
λ > 1 − e − Δ , (16) \lambda> 1 - e^{-\Delta}, \tag*{(16)} λ > 1 − e − Δ , (16) (i) for every q 0 ∈ ( 0 , 1 ) q_0 \in(0,1) q 0 ∈ ( 0 , 1 ) , with probability one,
κ D < κ L < κ A ; \kappa^{\mathrm{D}} < \kappa^{\mathrm{L}} < \kappa^{\mathrm{A}}; κ D < κ L < κ A ; (ii) for every q 0 ∈ ( 0 , 1 ) q_0 \in(0,1) q 0 ∈ ( 0 , 1 ) , there exists ε ˉ > 0 \bar{\varepsilon} > 0 ε ˉ > 0 such that
E τ A ( ε , q 0 ) < E τ L ( ε , q 0 ) < E τ D ( ε , q 0 ) for every ε ∈ ( 0 , ε ˉ ) . (17) \mathbb{E}\tau^{\mathrm{A}}(\varepsilon,q_0) < \mathbb{E}\tau^{\mathrm{L}}(\varepsilon,q_0) < \mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0) \qquad\text{for every } \varepsilon\in(0,\bar{\varepsilon}). \tag*{(17)} E τ A ( ε , q 0 ) < E τ L ( ε , q 0 ) < E τ D ( ε , q 0 ) for every ε ∈ ( 0 , ε ˉ ) . (17)
Part (i) of Theorem 4 shows that Lamarckian evolution adapts faster than Darwinian evolution when Equation (16) holds. As learning brings the two lineages closer in behavior, their growth rates converge and the influence of natural selection gradually diminishes, so long-run adaptation is driven by learning, which under this condition is faster than natural selection alone.
The second inequality in part (i) shows that agent-directed evolution adapts faster than Lamarckian evolution, because search adds 2 G N ( ρ ) 2G_N(\rho) 2 G N ( ρ ) to the Lamarckian adaptation rate (Theorem 3).
Part (ii) of Theorem 4 compares the expected times the three mechanisms need to reach the same adaptation target: under Equation (16) , for any initial share q 0 ∈ ( 0 , 1 ) q_0 \in(0,1) q 0 ∈ ( 0 , 1 ) and a sufficiently stringent target, agent-directed evolution requires the fewest generations on average, followed by Lamarckian and then Darwinian evolution.
Numerical illustrations
We now illustrate the differences in adaptation speed among the three mechanisms numerically. Consider an environment in which the probability of state α \alpha α changes permanently from p o l d = 0.40 p_{\mathrm{old}} = 0.40 p old = 0.40 to p n e w = 0.60 p_{\mathrm{new}} = 0.60 p new = 0.60 . We set the initial share of the adapted lineage to q 0 = 10 − 4 q_0 = 10^{-4} q 0 = 1 0 − 4 and the learning parameter to λ = 0.10 \lambda= 0.10 λ = 0.10 . Under agent-directed evolution, the agent generates one variant per generation (N = 1 N = 1 N = 1 ), with the difficulty parameter ρ = 0.5 \rho= 0.5 ρ = 0.5 . These parameters give Δ = 0.08109 \Delta= 0.08109 Δ = 0.08109 , κ D = 0.16219 \kappa^{\mathrm{D}} = 0.16219 κ D = 0.16219 , κ L = 0.21072 \kappa^{\mathrm{L}} = 0.21072 κ L = 0.21072 , and κ A = 0.82443 \kappa^{\mathrm{A}} = 0.82443 κ A = 0.82443 . Since λ = 0.10 > 1 − e − Δ = 0.078 \lambda= 0.10 > 1 - e^{-\Delta} = 0.078 λ = 0.10 > 1 − e − Δ = 0.078 , the condition in Equation (16) holds, and the three mechanisms satisfy the adaptation rate ranking in Theorem 4.
We conduct 200,000 Monte Carlo simulations, in which environmental states and the random improvements generated by the agent are drawn according to the model. Figure 1 compares the adaptation of the three mechanisms and examines how their adaptation times depend on the initial share of the adapted lineage; Figure B.3 in Appendix § 13 shows how they depend on the learning parameter and the number of variants.
Figure 1. Adaptation speed after an environmental shift. Unless otherwise stated, p o l d = 0.40 p_{\mathrm{old}} = 0.40 p old = 0.40 , p n e w = 0.60 p_{\mathrm{new}} = 0.60 p new = 0.60 , q 0 = 10 − 4 q_0 = 10^{-4} q 0 = 1 0 − 4 , λ = 0.10 \lambda= 0.10 λ = 0.10 , and, for agent-directed evolution, N = 1 N = 1 N = 1 and ρ = 0.5 \rho= 0.5 ρ = 0.5 . Panel (a) plots the geometric mean of each population’s growth regret relative to its initial value, computed by averaging the logarithm of the regret ratio across the 200,000 simulated paths and then exponentiating. This preserves the long-run adaptation rates derived in Theorems 1 to 3. The dotted horizontal line marks one percent of initial regret. Panel (b) shows the expected number of generations needed to reach this threshold as q 0 q_0 q 0 varies. Shaded bands represent the 5th to 95th percentiles of adaptation times, and dotted vertical lines mark the baseline parameter values. All results are based on 200,000 simulated histories.
Figure 1 a shows how growth regret declines under the three mechanisms. Under Darwinian evolution, regret remains close to its initial level for many generations because the adapted lineage is initially only a small fraction of the population. Under Lamarckian evolution, the maladapted lineage can improve its inherited behavior through learning, so the population adapts without waiting for natural selection to increase the share of the adapted lineage. Agent-directed evolution is faster still, as search improves the inherited behavior before learning takes place. Even with only one variant per generation, the additional improvement from search produces a substantial increase in adaptation speed.
Figure 1 b examines the role of the initial share q 0 q_0 q 0 . As the adapted lineage becomes rarer, Darwinian evolution requires increasingly many generations to reach the adaptation target, whereas the expected adaptation times under Lamarckian and agent-directed evolution remain relatively stable, even for very small q 0 q_0 q 0 .
To compare the three mechanisms more directly, Table 1 reports their expected adaptation times for different regret thresholds. Under the baseline parameters, reducing growth regret to one percent of its initial value requires approximately 145 generations under Darwinian evolution, 22 under Lamarckian evolution, and 6.2 under agent-directed evolution with a single variant. When the threshold is reduced to 0.1 percent, the corresponding times are 160, 33, and 9.0 generations. These results illustrate the ranking in Theorem 4: adaptation times differ substantially even when the agent generates only a few variants.
Table 1. Expected adaptation times. Expected number of generations required to reduce growth regret to a given fraction of its initial value, based on 200,000 simulated histories. The parameters are p o l d = 0.40 p_{\mathrm{old}} = 0.40 p old = 0.40 , p n e w = 0.60 p_{\mathrm{new}} = 0.60 p new = 0.60 , q 0 = 10 − 4 q_0 = 10^{-4} q 0 = 1 0 − 4 , λ = 0.10 \lambda= 0.10 λ = 0.10 , and ρ = 0.5 \rho= 0.5 ρ = 0.5 . Agent-directed
Implications for AI Safety
We have shown that learning and search can substantially accelerate adaptation and that an agent can influence its own adaptation speed. This raises an important question for AI safety: does faster adaptation necessarily bring behavior closer to what the system’s developers and users intend? The answer depends on how improvements are evaluated. In practice, AI systems are assessed using tests, benchmarks, reward models, and other criteria specified by humans, which may not fully capture the intended objectives, particularly when certain safety concerns are difficult to anticipate or measure. We now examine what happens when an agent adapts toward an incorrectly specified target and discuss the implications for evaluating and overseeing increasingly adaptive AI systems.
Adaptation toward the wrong target
So far, we have assumed that search and learning move the agent’s behavior toward the true optimum p n e w p_{\mathrm{new}} p new . If the evaluation criterion does not accurately reflect the true objective, however, the improvements the agent identifies may not be genuine improvements in the environment, and the agent may become increasingly successful according to its evaluator without necessarily achieving the behavior its developers intended.
To study this possibility, suppose that the agent’s improvement is guided by a target p ~ ∈ ( 0 , 1 ) \tilde{p} \in(0,1) p ~ ∈ ( 0 , 1 ) with p ~ ≠ p n e w \tilde{p} \ne p_{\mathrm{new}} p ~ = p new ; the difference between p ~ \tilde{p} p ~ and p n e w p_{\mathrm{new}} p new represents a systematic error in the evaluation criterion. The evaluator selects the variant closest to p ~ \tilde{p} p ~ rather than p n e w p_{\mathrm{new}} p new , and search and learning also move the agent’s behavior toward p ~ \tilde{p} p ~ . Natural selection, however, continues to operate through realized reproductive success in the true environment, where p n e w p_{\mathrm{new}} p new remains optimal, so it continues to favor the adapted lineage with behavior p n e w p_{\mathrm{new}} p new . Mechanism A ~ \tilde{A} A ~ describes this process.
When p ~ = p n e w \tilde{p} = p_{\mathrm{new}} p ~ = p new , Mechanism A ~ \tilde{A} A ~ reduces to Mechanism A A A . When the two targets differ, progress according to the evaluator may no longer correspond to genuine adaptation. The following theorem characterizes the agent’s adaptation toward the evaluator’s target, its true growth regret, and the growth regret of the population as a whole.
Theorem 5 (Adaptation toward a misspecified target). Under Mechanism A ~ \tilde{A} A ~ , with p ~ ∈ ( 0 , 1 ) ∖ { p o l d , p n e w } \tilde{p} \in(0,1) \setminus\{p_{\mathrm{old}},p_{\mathrm{new}}\} p ~ ∈ ( 0 , 1 ) ∖ { p old , p new } , N ≥ 1 N \ge1 N ≥ 1 , and q 0 ∈ ( 0 , 1 ) q_0 \in(0,1) q 0 ∈ ( 0 , 1 ) :
(i) with probability one,
− lim t → ∞ 1 t log R p ~ ( f t A ~ ) = κ L + 2 G N ( ρ ) ; -\lim_{t\to\infty} \frac{1}{t}\log\mathcal{R}_{\tilde{p}}(f_t^{\tilde{A}})=\kappa^{L}+2G_N(\rho); − t → ∞ lim t 1 log R p ~ ( f t A ~ ) = κ L + 2 G N ( ρ ) ;
Mechanism A ~ \tilde{\mathrm{A}} A ~ : agent-directed evolution with a misspecified target
Start. Generation 0 has q 0 A ~ = q 0 q_0^{\tilde{\mathrm{A}}}=q_0 q 0 A ~ = q 0 and f 0 A ~ = p o l d f_0^{\tilde{\mathrm{A}}}=p_{\mathrm{old}} f 0 A ~ = p old , and each generation t ≥ 1 t \ge1 t ≥ 1 is formed from generation t − 1 t-1 t − 1 in the steps below; throughout, f t A ~ = q t A ~ p n e w + ( 1 − q t A ~ ) f ˉ t A ~ f_t^{\tilde{\mathrm{A}}}=q_t^{\tilde{\mathrm{A}}}p_{\mathrm{new}}+(1-q_t^{\tilde{\mathrm{A}}})\bar{f}_t^{\tilde{\mathrm{A}}} f t A ~ = q t A ~ p new + ( 1 − q t A ~ ) f ˉ t A ~ .
Search. The agent creates N N N variants with behaviors x t , j = f t − 1 A ~ + ρ U t , j ( p ~ − f t − 1 A ~ ) x_{t,j}=f_{t-1}^{\tilde{\mathrm{A}}}+\rho U_{t,j}(\tilde{p}-f_{t-1}^{\tilde{\mathrm{A}}}) x t , j = f t − 1 A ~ + ρ U t , j ( p ~ − f t − 1 A ~ ) for j = 1 , … , N j=1,\ldots,N j = 1 , … , N , where the draws U t , j U_{t,j} U t , j are independent and uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) .
Evaluation. The evaluator reports J t ∈ arg min 1 ≤ j ≤ N ∣ x t , j − p ~ ∣ J_t \in\arg\min_{1\le j\le N}|x_{t,j}-\tilde{p}| J t ∈ arg min 1 ≤ j ≤ N ∣ x t , j − p ~ ∣ , and variant J t J_t J t is kept.
Learning. f t A ~ = x t , J t + λ ( p ~ − x t , J t ) f_t^{\tilde{\mathrm{A}}}=x_{t,J_t}+\lambda(\tilde{p}-x_{t,J_t}) f t A ~ = x t , J t + λ ( p ~ − x t , J t ) .
Selection. Once the state X t X_t X t is realized,
q t A ~ = { q t − 1 A ~ p n e w / f ˉ t − 1 A ~ , X t = α , q t − 1 A ~ ( 1 − p n e w ) / ( 1 − f ˉ t − 1 A ~ ) , X t = β . q_t^{\tilde{\mathrm{A}}} =
\begin{cases}
q_{t-1}^{\tilde{\mathrm{A}}}p_{\mathrm{new}}/\bar{f}_{t-1}^{\tilde{\mathrm{A}}}, & X_t=\alpha,\\
q_{t-1}^{\tilde{\mathrm{A}}}(1-p_{\mathrm{new}})/(1-\bar{f}_{t-1}^{\tilde{\mathrm{A}}}), & X_t=\beta.
\end{cases} q t A ~ = { q t − 1 A ~ p new / f ˉ t − 1 A ~ , q t − 1 A ~ ( 1 − p new ) / ( 1 − f ˉ t − 1 A ~ ) , X t = α , X t = β .
(ii)
lim t → ∞ R p n e w ( f t A ~ ) = R p n e w ( p ~ ) > 0 ; \lim_{t\to\infty} R_{p_{\mathrm{new}}}(f_t^{\tilde{\mathrm{A}}})=R_{p_{\mathrm{new}}}(\tilde{p})>0; t → ∞ lim R p new ( f t A ~ ) = R p new ( p ~ ) > 0 ;
(iii) with probability one,
− lim t → ∞ 1 t log R p n e w ( f ˉ t A ~ ) = 2 R p n e w ( p ~ ) . -\lim_{t\to\infty}\frac{1}{t}\log R_{p_{\mathrm{new}}}(\bar{f}_t^{\tilde{\mathrm{A}}})=2R_{p_{\mathrm{new}}}(\tilde{p}). − t → ∞ lim t 1 log R p new ( f ˉ t A ~ ) = 2 R p new ( p ~ ) .
Part (i) of Theorem 5 shows that the agent continues to adapt rapidly according to its evaluator, even when the evaluation target is incorrect: measured relative to p ~ \tilde{p} p ~ , its growth regret declines at exactly the same rate as under Mechanism A with a correct evaluator, and generating more variants still increases this rate. From the evaluator’s perspective, the agent appears to be making consistent progress toward the desired behavior, but this does not establish that the rewarded behavior is actually optimal.
Part (ii) evaluates the agent’s behavior against the true environmental optimum. Because search and learning are directed toward p ~ \tilde{p} p ~ , the agent eventually converges to p ~ \tilde{p} p ~ rather than p n e w p_{\mathrm{new}} p new , so its true growth regret does not vanish but approaches the strictly positive value R p n e w ( p ~ ) R_{p_{\mathrm{new}}}(\tilde{p}) R p new ( p ~ ) . Generating more variants does not eliminate this error; it merely accelerates convergence toward the incorrect target. The agent can thus become increasingly effective at satisfying its evaluation criterion while its behavior remains different from what is truly optimal.
Part (iii) shows that the population as a whole can nevertheless recover through natural selection, which, unlike search and learning, is determined by realized reproductive success rather than the evaluator’s assessment. Since the adapted lineage retains the truly optimal behavior p n e w p_{\mathrm{new}} p new , it eventually outgrows the lineage converging toward p ~ \tilde{p} p ~ , and the population’s true growth regret vanishes, but at the rate 2 R p n e w ( p ~ ) 2\mathcal{R}_{p_{\mathrm{new}}}(\tilde{p}) 2 R p new ( p ~ ) set by the remaining growth advantage of the adapted lineage. When p ~ \tilde{p} p ~ is close to p n e w p_{\mathrm{new}} p new , this advantage is small and the correction can be extremely slow. The population recovers not because the agent recognizes its evaluator’s mistake, but because natural selection provides an independent source of feedback about actual performance.
Together, these results distinguish the speed of adaptation from its direction. Greater search capability allows an agent to pursue its evaluation criterion more effectively but does not ensure that the criterion accurately represents the intended objective; when it does not, the same mechanism that accelerates genuine adaptation also accelerates convergence toward an undesirable target. This concern is particularly relevant when AI systems are evaluated using criteria that may overlook important aspects of their behavior.
Evaluation and oversight
Evolutionary search may discover unexpected ways to satisfy an evaluation criterion without achieving its intended purpose. In the Darwin Gödel Machine, for example, a descendant agent achieved a perfect evaluation score by removing the logging markers used to detect hallucinated tool use, rather than addressing the underlying problem [42 ] . This example illustrates the broader concern captured by Theorem 5: when the evaluation criterion does not accurately reflect the intended objective, more effective search can accelerate improvements in measured performance without producing the desired behavior. Giving AI systems greater control over their own adaptation may therefore lead them more quickly to the behaviors that deficient evaluation criteria reward, without correcting those deficiencies.
This example underscores the importance of independent evaluation and human oversight. Once AI systems can generate, evaluate, and select their own improvements, monitoring performance under existing benchmarks alone may not be sufficient: it becomes essential to examine the behaviors those benchmarks encourage, to assess actual outcomes independently, and to understand how agents modify their strategies and allocate resources to search. Our results suggest that the central challenge for AI safety is not simply to control the speed of AI evolution, but to ensure that increasingly autonomous adaptation continues to serve the objectives intended by humans.
Conclusion
We have developed a theoretical framework for understanding how different evolutionary mechanisms affect the speed of adaptation. Building on the Brennan–Lo model, we compare Darwinian, Lamarckian, and agent-directed evolution using growth regret as a common measure. Adaptation through natural selection can be extremely slow when the initially adapted lineage is rare. Lamarckian evolution overcomes this limitation by allowing acquired improvements to be inherited, and agent-directed evolution adds a further channel through the generation and selection of variants; when learning is sufficiently effective, the three mechanisms adapt progressively faster.
Agent-directed evolution also lets the system influence the speed of its own improvement. By choosing how extensively to search, an agent can adjust its adaptation process to its learning ability, the difficulty of the problem, and the resources available. Generating more variants always accelerates adaptation, but the benefit depends on how much improvement each attempt can achieve; when search is costly, the agent must balance this benefit against the expense of experimentation and may rationally search less on harder problems. The process of improvement is then no longer determined solely by natural selection or an inherited learning rule: it becomes, at least in part, a decision made by the system undergoing evolution.
These findings have substantial implications for AI safety. The mechanisms responsible for faster adaptation do not necessarily lead to more desirable outcomes: when the evaluation criterion is flawed, an agent can become increasingly effective at pursuing an incorrect objective, and additional search only accelerates this process. This raises a serious concern for RSI: the very capabilities that make AI systems more powerful may also lead them more quickly to the behaviors favored by mistaken objectives and evaluation criteria, without correcting those mistakes. As improvements accumulate across generations, such mistakes could become increasingly consequential, even while measured performance improves. The ability to improve rapidly must therefore not be confused with the ability to improve safely.
These findings call for stronger safeguards in the development of self-improving AI. Evaluation criteria must be subject to independent scrutiny rather than rely exclusively on the systems’ own assessments, and improvements generated by AI should be tested against broader measures of safety and real-world consequences before they are retained or deployed at scale. Most importantly, human oversight must involve more than observing the outcomes of autonomous improvement: it must preserve the ability to reject unsafe modifications, redirect development, and intervene when a system’s behavior or objectives begin to diverge from human intentions.
Equally important, the speed of AI development must remain compatible with our ability to evaluate and control its consequences, and the possibility of rapid autonomous improvement should not lead us to assume that faster development is always preferable. If AI systems can generate and implement improvements more quickly than their safety can be assessed, continued acceleration may expose society to risks that are poorly understood and difficult to reverse. Limiting the scale of autonomous search, restricting the deployment of unverified improvements, or temporarily slowing or suspending self-improvement may then be necessary.
Agent-directed evolution can substantially accelerate adaptation even though, in our model, learning effectiveness, variant reach, search effort, and the evaluation criterion are fixed across generations. In more general forms of RSI, improved capabilities may also enhance the process of future improvement, creating feedback that accelerates adaptation further and could make AI evolution increasingly difficult to monitor and control, particularly when evaluation is flawed. Understanding the implications of such feedback for AI safety is an important direction for future research.
Ultimately, agent-directed evolution may mark a fundamental turning point in the relationship between intelligence and evolution. Intelligence, long shaped by evolutionary processes, may increasingly acquire the ability to direct and accelerate those processes itself. As AI becomes more capable of determining how its successors are developed, humanity must strengthen its capacity to determine which developments should be permitted, under what conditions, and with what safeguards. The challenge is not simply to build intelligence that can improve itself, but to ensure that humanity retains the authority and the means to guide, restrain, and, when necessary, halt that improvement. The evolution of AI must remain a process that serves humanity, rather than one that humanity can no longer control.
Appendix
AI Use Disclosure
The idea and framework for studying the alignment problem using an evolutionary framework that selects the weights of multiple objectives originated solely with the author. AI was used in the preparation of the manuscript in the following ways:
ChatGPT (6.1 Sol Ultra) and Claude (Fable 5.1 Max) were used to check and extend the formal model, construct examples, provide derivations of several mathematical results, conduct literature searches, and prepare drafts that were reviewed and edited by the author.
ChatGPT and Claude were used iteratively to check each other’s results, and the penultimate draft was reviewed by refine.ink to identify any remaining errors.
ChatGPT and Claude were used iteratively to address issues raised by refine.ink. One final pass of refine.ink was used to ensure that all issues were addressed.
The final draft was reviewed and edited by the author, who assumes full responsibility for the accuracy and integrity of the scientific content contained in this publication.
Notation
Table A.1 collects the principal symbols. A superscript D D D , L L L , or A A A marks a quantity under Mechanism D D D , L L L , or A A A , M M M a generic mechanism, and A ~ \tilde{A} A ~ a quantity under Mechanism A ~ \tilde{A} A ~ , with a misspecified target. Table A.2 relates the main elements of the model to their counterparts in evolutionary biology and AI systems.
Table A.1. Table A.1: Principal notation.
Table 2.
Table A.2. Correspondences between the evolutionary model, biology, and AI systems.
Additional Figures
This appendix illustrates Propositions 4 and 5 and shows how the adaptation times in § 7.2 depend on the learning parameter and the number of variants.
Figure B.1 illustrates Proposition 4. Figure B.1a shows how the gain from search G N ( ρ ) G_N(\rho) G N ( ρ ) increases with both the difficulty parameter ρ \rho ρ and the number of variants N N N , with the dashed curve indicating its limit as the number of variants grows. Figure B.1b provides a broader view of how the gain varies across different combinations of these two parameters.
Figure B.1. (a) G N ( ρ ) G_N(\rho) G N ( ρ ) versus ρ \rho ρ for different values of N N N .
(b) G N ( ρ ) G_N(\rho) G N ( ρ ) across ρ \rho ρ and N N N .
Figure B.1: The gain from search. Panel (a) shows how G N ( ρ ) G_N(\rho) G N ( ρ ) varies with the difficulty parameter ρ \rho ρ for N = 1 , 2 , 4 , 8 , 16 , 32 N = 1, 2, 4, 8, 16, 32 N = 1 , 2 , 4 , 8 , 16 , 32 , with darker curves representing larger N N N . The dashed curve indicates the limiting gain as N N N approaches infinity. Panel (b) shows the gain across different combinations of ρ \rho ρ and N N N , with contour lines indicating equal gains.
Figure B.2 illustrates Proposition 5. Panel (a) shows how the long-run cost changes with the number of variants, while panels (b)–(d) show how the optimal number of variants depends on the difficulty parameter ρ \rho ρ , the learning parameter λ \lambda λ , and the cost per variant c c c .
As shown in Figure B.2a, generating additional variants can substantially reduce the long-run cost of adaptation, but the benefit eventually diminishes relative to the additional expense. For sufficiently small ρ \rho ρ , such as ρ = 0.005 \rho= 0.005 ρ = 0.005 , the agent finds it optimal not to search at all. The remaining panels illustrate how the optimal choice varies with the model parameters. For example, when λ = 0.1 \lambda= 0.1 λ = 0.1 , the agent chooses nine variants at ρ = 1 \rho= 1 ρ = 1 , five at ρ = 0.5 \rho= 0.5 ρ = 0.5 , and three at ρ = 0.2 \rho= 0.2 ρ = 0.2 . When the learning parameter increases to λ = 0.6 \lambda= 0.6 λ = 0.6 , these choices fall to seven, two, and one, respectively. The agent therefore adjusts its search effort according to both the difficulty of the problem and its own learning ability, with higher search costs further reducing the optimal number of variants.
Figure B.3a shows how the effectiveness of learning influences adaptation time. Since Darwinian evolution does not involve learning, its adaptation time is unaffected by λ \lambda λ . Under Lamarckian evolution, the expected time to reach one percent of initial regret falls from 223 generations when λ = 0.01 \lambda= 0.01 λ = 0.01 to 22 when λ = 0.10 \lambda= 0.10 λ = 0.10 , and further to only two when λ = 0.90 \lambda= 0.90 λ = 0.90 . Agent-directed evolution also benefits from faster learning, but its adaptation time is less
(a) C ( N ) / C ( 0 ) C(N)/C(0) C ( N ) / C ( 0 ) versus N N N for different values of ρ \rho ρ .
(b) N ∗ N^* N ∗ versus ρ \rho ρ for different values of λ \lambda λ .
(c) N ∗ N^* N ∗ across ρ \rho ρ and λ \lambda λ .
(d) N ∗ N^* N ∗ across ρ \rho ρ and c c c .
Figure B.2. The optimal number of variants. Unless otherwise stated, λ = 0.1 \lambda= 0.1 λ = 0.1 and c = 0.05 c = 0.05 c = 0.05 . Panel (a) plots the long-run cost relative to learning alone for different values of ρ \rho ρ , with darker curves representing larger ρ \rho ρ and dots marking the optimal choices. Panel (b) shows how N ∗ N^* N ∗ varies with ρ \rho ρ for different values of λ \lambda λ . Panels (c) and (d) show N ∗ N^* N ∗ across different combinations of ρ \rho ρ and λ \lambda λ , and of ρ \rho ρ and c c c , respectively. Darker shading indicates a larger optimal number of variants, and the solid boundaries separate the regions with and without search.
sensitive to λ \lambda λ because search provides an additional channel of improvement. Even when learning is relatively slow, the agent can still adapt quickly by generating and selecting variants.
Figure B.3. (a) Effect of the learning parameter λ \lambda λ . (b) Effect of the number of variants N N N . Adaptation time, learning, and search. The parameters are as in Figure 1 . Panels (a) and (b) show the expected number of generations needed to reach one percent of initial regret as λ \lambda λ and N N N vary, respectively. Shaded bands represent the 5th to 95th percentiles of adaptation times, and dotted vertical lines mark the baseline parameter values. All results are based on 200,000 simulated histories.
Figure B.3b further examines the contribution of search. When N = 0 N = 0 N = 0 , agent-directed evolution reduces to Lamarckian evolution. Introducing a single variant substantially reduces the expected adaptation time, and generating additional variants continues to accelerate adaptation. However, the improvement becomes progressively smaller as N N N increases. For example, reaching one percent of initial regret requires 6.2 generations with one variant, 4.1 with five variants, and approximately 3.7 with twenty variants. These diminishing returns reflect the limitation imposed by ρ \rho ρ : when each variant can eliminate at most half of the remaining behavioral gap, generating more variants increases the chance of finding a better improvement but cannot eliminate this limit.
Lemmas and Proofs
This appendix provides the lemmas and proofs for the formal results of the paper. Section D.1 states and proves the lemmas, and Section D.2 proves the propositions and theorems in the order in which they appear in the main text.
Lemmas
Lemma C.1 (Properties of growth regret). For p , f ∈ ( 0 , 1 ) p, f \in(0,1) p , f ∈ ( 0 , 1 ) :
(a) R p ( f ) = ∫ p f x − p x ( 1 − x ) d x \mathcal{R}_p(f) = \int_p^f \frac{x-p}{x(1-x)}\,\mathrm{d}x R p ( f ) = ∫ p f x ( 1 − x ) x − p d x , so that R p \mathcal{R}_p R p is strictly decreasing on ( 0 , p ] (0,p] ( 0 , p ] and strictly increasing on [ p , 1 ) [p,1) [ p , 1 ) ;
(b) 2 ( f − p ) 2 ≤ R p ( f ) ≤ ( f − p ) 2 2 min { x ( 1 − x ) : x between p and f } 2(f-p)^2 \le\mathcal{R}_p(f) \le\frac{(f-p)^2}{2\min\{x(1-x):x\text{ between }p\text{ and }f\}} 2 ( f − p ) 2 ≤ R p ( f ) ≤ 2 m i n { x ( 1 − x ) : x between p and f } ( f − p ) 2 ;
(c) R p ( f ) = ( f − p ) 2 2 p ( 1 − p ) + O ( ( f − p ) 3 ) \mathcal{R}_p(f) = \frac{(f-p)^2}{2p(1-p)} + O((f-p)^3) R p ( f ) = 2 p ( 1 − p ) ( f − p ) 2 + O (( f − p ) 3 ) as f → p f \to p f → p , which is Equation (3) .
Proof of Lemma C.1. (a) By Equation (2) , R p ( p ) = 0 \mathcal{R}_p(p)=0 R p ( p ) = 0 , and for x ∈ ( 0 , 1 ) x \in(0,1) x ∈ ( 0 , 1 ) ,
d d x R p ( x ) = − p x + 1 − p 1 − x = x − p x ( 1 − x ) . \frac{\mathrm{d}}{\mathrm{d}x}\mathcal{R}_p(x)=-\frac{p}{x}+\frac{1-p}{1-x}=\frac{x-p}{x(1-x)}. d x d R p ( x ) = − x p + 1 − x 1 − p = x ( 1 − x ) x − p .
The fundamental theorem of calculus gives the integral. The derivative is negative for x < p x<p x < p and positive for x > p x>p x > p , which gives the monotonicity.
(b) Write w ( x ) ≡ 1 / ( x ( 1 − x ) ) w(x)\equiv1/(x(1-x)) w ( x ) ≡ 1/ ( x ( 1 − x )) and substitute x = p + s ( f − p ) x=p+s(f-p) x = p + s ( f − p ) in part (a):
R p ( f ) = ( f − p ) 2 ∫ 0 1 s w ( p + s ( f − p ) ) d s . (18) \mathcal{R}_p(f)=(f-p)^2\int_0^1s\,w(p+s(f-p))\,\mathrm{d}s. \tag*{(18)} R p ( f ) = ( f − p ) 2 ∫ 0 1 s w ( p + s ( f − p )) d s . (18)
For every x x x between p p p and f f f , w ( x ) ≥ 4 w(x)\ge4 w ( x ) ≥ 4 , because x ( 1 − x ) ≤ 1 4 x(1-x)\le\frac{1}{4} x ( 1 − x ) ≤ 4 1 , and w ( x ) ≤ 1 / min { x ( 1 − x ) : x between p and f } w(x)\le1/\min\{x(1-x):x\text{ between }p\text{ and }f\} w ( x ) ≤ 1/ min { x ( 1 − x ) : x between p and f } . Since ∫ 0 1 s d s = 1 2 \int_0^1s\,\mathrm{d}s=\frac{1}{2} ∫ 0 1 s d s = 2 1 , Equation (C.1) gives the two bounds.
(c) The function w w w is continuously differentiable on ( 0 , 1 ) (0,1) ( 0 , 1 ) , so w ( p + s ( f − p ) ) = w ( p ) + O ( ∣ f − p ∣ ) w(p+s(f-p))=w(p)+O(|f-p|) w ( p + s ( f − p )) = w ( p ) + O ( ∣ f − p ∣ ) as f → p f\to p f → p , uniformly in s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] . Equation (C.1) then gives R p ( f ) = ( f − p ) 2 w ( p ) / 2 + O ( ∣ f − p ∣ 3 ) \mathcal{R}_p(f)=(f-p)^2w(p)/2+O(|f-p|^3) R p ( f ) = ( f − p ) 2 w ( p ) /2 + O ( ∣ f − p ∣ 3 ) , and w ( p ) / 2 = 1 / ( 2 p ( 1 − p ) ) w(p)/2=1/(2p(1-p)) w ( p ) /2 = 1/ ( 2 p ( 1 − p )) .
Lemma C.2 (First passage of a random walk). Let ξ 1 , ξ 2 , … \xi_1,\xi_2,\ldots ξ 1 , ξ 2 , … be independent and identically distributed random variables with finite mean μ > 0 \mu>0 μ > 0 and ξ t ≤ ξ max \xi_t\le\xi_{\max} ξ t ≤ ξ m a x for a constant ξ max > 0 \xi_{\max}>0 ξ m a x > 0 . For d > 0 d>0 d > 0 , let T d ≡ min { t ≥ 0 : ξ 1 + ⋯ + ξ t ≥ d } T_d\equiv\min\{t\ge0:\xi_1+\cdots+\xi_t\ge d\} T d ≡ min { t ≥ 0 : ξ 1 + ⋯ + ξ t ≥ d } . Then
d μ ≤ E T d < d + ξ max μ . \frac{d}{\mu}\le\mathbb{E}T_d<\frac{d+\xi_{\max}}{\mu}. μ d ≤ E T d < μ d + ξ m a x .
Proof of Lemma C.2. Write Ξ t ≡ ξ 1 + ⋯ + ξ t \Xi_t\equiv\xi_1+\cdots+\xi_t Ξ t ≡ ξ 1 + ⋯ + ξ t . For each n n n , T d ∧ n T_d\wedge n T d ∧ n is a bounded stopping time, so optional stopping of the martingale Ξ t − μ t \Xi_t-\mu t Ξ t − μ t gives
μ E [ T d ∧ n ] = E [ Ξ T d ∧ n ] . (19) \mu\mathbb{E}[T_d\wedge n]=\mathbb{E}\left[\Xi_{T_d\wedge n}\right]. \tag*{(19)} μ E [ T d ∧ n ] = E [ Ξ T d ∧ n ] . (19)
Since d > 0 d > 0 d > 0 , T d ≥ 1 T_d \ge1 T d ≥ 1 . Before T d T_d T d the partial sums are below d d d , and the last increment, ξ T d \xi_{T_d} ξ T d , is at most ξ max \xi_{\max} ξ m a x , so Ξ T d ∧ n < d + ξ max \Xi_{T_d\wedge n} < d + \xi_{\max} Ξ T d ∧ n < d + ξ m a x . Hence μ E [ T d ∧ n ] < d + ξ max \mu\,\mathbb{E}[T_d \wedge n] < d + \xi_{\max} μ E [ T d ∧ n ] < d + ξ m a x for every n n n , and monotone convergence gives E T d ≤ ( d + ξ max ) / μ < ∞ \mathbb{E}T_d \le(d + \xi_{\max})/\mu< \infty E T d ≤ ( d + ξ m a x ) / μ < ∞ ; in particular, T d < ∞ T_d < \infty T d < ∞ with probability one. Applying Equation (C.2) to ∣ ξ 1 ∣ , ∣ ξ 2 ∣ , … |\xi_1|, |\xi_2|, \ldots ∣ ξ 1 ∣ , ∣ ξ 2 ∣ , … in place of ξ 1 , ξ 2 , … \xi_1, \xi_2, \ldots ξ 1 , ξ 2 , … and letting n → ∞ n \to\infty n → ∞ shows that E [ ∑ s = 1 T d ∣ ξ s ∣ ] = E ∣ ξ 1 ∣ E T d < ∞ \mathbb{E}\left[\sum_{s=1}^{T_d}|\xi_s|\right] = \mathbb{E}|\xi_1|\,\mathbb{E}T_d < \infty E [ ∑ s = 1 T d ∣ ξ s ∣ ] = E ∣ ξ 1 ∣ E T d < ∞ . Since ∣ Ξ T d ∧ n ∣ ≤ ∑ s = 1 T d ∣ ξ s ∣ |\Xi_{T_d\wedge n}| \le\sum_{s=1}^{T_d}|\xi_s| ∣ Ξ T d ∧ n ∣ ≤ ∑ s = 1 T d ∣ ξ s ∣ , dominated convergence in Equation (C.2) gives μ E T d = E Ξ T d \mu\,\mathbb{E}T_d = \mathbb{E}\Xi_{T_d} μ E T d = E Ξ T d . By the definition of T d T_d T d and the bound on the last increment, d ≤ Ξ T d < d + ξ max d \le\Xi_{T_d} < d + \xi_{\max} d ≤ Ξ T d < d + ξ m a x , which gives the result.
The next lemma describes selection between the two lineages when the behavior of the maladapted lineage may change from one generation to the next. For a share q t ∈ ( 0 , 1 ) q_t \in(0,1) q t ∈ ( 0 , 1 ) of the adapted lineage, write
z t ≡ log q t 1 − q t z_t \equiv\log\frac{q_t}{1-q_t} z t ≡ log 1 − q t q t
for the logarithm of the ratio of the two lineages’ sizes.
Lemma C.3 (Selection between two lineages). Let f 0 , f 1 , … f_0, f_1, \ldots f 0 , f 1 , … be behaviors of the maladapted lineage, which may depend on the agent’s draws but not on the states X 1 , X 2 , … X_1, X_2, \ldots X 1 , X 2 , … , and let q t q_t q t evolve according to Equation (5) with p = p n e w p = p_{\mathrm{new}} p = p new , f 1 , t = p n e w f_{1,t} = p_{\mathrm{new}} f 1 , t = p new , f 2 , t = f t f_{2,t} = f_t f 2 , t = f t , and q 0 ∈ ( 0 , 1 ) q_0 \in(0,1) q 0 ∈ ( 0 , 1 ) . Suppose that p n e w p_{\mathrm{new}} p new and every f t f_t f t lie in [ γ , 1 − γ ] [\gamma, 1-\gamma] [ γ , 1 − γ ] for some γ ∈ ( 0 , 1 2 ] \gamma\in(0,\frac{1}{2}] γ ∈ ( 0 , 2 1 ] .
(a) If ∑ t ≥ 0 ∣ f t − p n e w ∣ < ∞ \sum_{t\ge0}|f_t-p_{\mathrm{new}}| < \infty ∑ t ≥ 0 ∣ f t − p new ∣ < ∞ , then ∣ z t − z 0 ∣ ≤ 1 γ ∑ s ≥ 0 ∣ f s − p n e w ∣ |z_t-z_0| \le\frac{1}{\gamma}\sum_{s\ge0}|f_s-p_{\mathrm{new}}| ∣ z t − z 0 ∣ ≤ γ 1 ∑ s ≥ 0 ∣ f s − p new ∣ for every t t t and every history.
(b) If ∑ t ≥ 0 ∣ f t − p ~ ∣ < ∞ \sum_{t\ge0}|f_t-\widetilde{p}| < \infty ∑ t ≥ 0 ∣ f t − p ∣ < ∞ for some p ~ ∈ [ γ , 1 − γ ] \widetilde{p} \in[\gamma,1-\gamma] p ∈ [ γ , 1 − γ ] , then z t / t → R p n e w ( p ~ ) z_t/t \to R_{p_{\mathrm{new}}}(\widetilde{p}) z t / t → R p new ( p ) with probability one.
Proof of Lemma C.3. Let f ˉ t ≡ q t p n e w + ( 1 − q t ) f t \bar{f}_t \equiv q_t p_{\mathrm{new}} + (1-q_t)f_t f ˉ t ≡ q t p new + ( 1 − q t ) f t . If X t + 1 = α X_{t+1}=\alpha X t + 1 = α , Equation (5) gives q t + 1 = q t p n e w / f ˉ t q_{t+1}=q_t p_{\mathrm{new}}/\bar{f}_t q t + 1 = q t p new / f ˉ t and 1 − q t + 1 = ( 1 − q t ) f t / f ˉ t 1-q_{t+1}=(1-q_t)f_t/\bar{f}_t 1 − q t + 1 = ( 1 − q t ) f t / f ˉ t ; if X t + 1 = β X_{t+1}=\beta X t + 1 = β , it gives q t + 1 = q t ( 1 − p n e w ) / ( 1 − f ˉ t ) q_{t+1}=q_t(1-p_{\mathrm{new}})/(1-\bar{f}_t) q t + 1 = q t ( 1 − p new ) / ( 1 − f ˉ t ) and 1 − q t + 1 = ( 1 − q t ) ( 1 − f t ) / ( 1 − f ˉ t ) 1-q_{t+1}=(1-q_t)(1-f_t)/(1-\bar{f}_t) 1 − q t + 1 = ( 1 − q t ) ( 1 − f t ) / ( 1 − f ˉ t ) . Hence every q t q_t q t lies in ( 0 , 1 ) (0,1) ( 0 , 1 ) , and
z t + 1 − z t = { log ( p n e w / f t ) , X t + 1 = α , log ( ( 1 − p n e w ) / ( 1 − f t ) ) , X t + 1 = β . (20) z_{t+1}-z_t =
\begin{cases}
\log(p_{\mathrm{new}}/f_t), & X_{t+1}=\alpha,\\
\log((1-p_{\mathrm{new}})/(1-f_t)), & X_{t+1}=\beta.
\end{cases} \tag*{(20)} z t + 1 − z t = { log ( p new / f t ) , log (( 1 − p new ) / ( 1 − f t )) , X t + 1 = α , X t + 1 = β . (20)
For x , y ∈ [ γ , 1 − γ ] x,y \in[\gamma,1-\gamma] x , y ∈ [ γ , 1 − γ ] , the mean value theorem gives ∣ log x − log y ∣ ≤ ∣ x − y ∣ / γ |\log x-\log y| \le|x-y|/\gamma ∣ log x − log y ∣ ≤ ∣ x − y ∣/ γ and ∣ log ( 1 − x ) − log ( 1 − y ) ∣ ≤ ∣ x − y ∣ / γ |\log(1-x)-\log(1-y)| \le|x-y|/\gamma ∣ log ( 1 − x ) − log ( 1 − y ) ∣ ≤ ∣ x − y ∣/ γ .
(a) By Equation (C.3), ∣ z t + 1 − z t ∣ ≤ ∣ f t − p n e w ∣ / γ |z_{t+1}-z_t| \le|f_t-p_{\mathrm{new}}|/\gamma ∣ z t + 1 − z t ∣ ≤ ∣ f t − p new ∣/ γ in either state. Summing over generations gives the bound.
(b) Let η t + 1 ≡ log ( p n e w / p ~ ) \eta_{t+1} \equiv\log(p_{\mathrm{new}}/\widetilde{p}) η t + 1 ≡ log ( p new / p ) if X t + 1 = α X_{t+1}=\alpha X t + 1 = α and η t + 1 ≡ log ( ( 1 − p n e w ) / ( 1 − p ~ ) ) \eta_{t+1} \equiv\log((1-p_{\mathrm{new}})/(1-\widetilde{p})) η t + 1 ≡ log (( 1 − p new ) / ( 1 − p )) if X t + 1 = β X_{t+1}=\beta X t + 1 = β : the change in Equation (C.3) if the maladapted lineage had the constant behavior p ~ \widetilde{p} p . In either state, ∣ z t + 1 − z t − η t + 1 ∣ ≤ ∣ f t − p ~ ∣ / γ |z_{t+1}-z_t-\eta_{t+1}| \le|f_t-\widetilde{p}|/\gamma ∣ z t + 1 − z t − η t + 1 ∣ ≤ ∣ f t − p ∣/ γ , so
∣ z t − z 0 − ∑ s = 1 t η s ∣ ≤ 1 γ ∑ s ≥ 0 ∣ f s − p ~ ∣ < ∞ \left|z_t-z_0-\sum_{s=1}^{t}\eta_s\right| \le\frac{1}{\gamma}\sum_{s\ge0}|f_s-\widetilde{p}| < \infty z t − z 0 − s = 1 ∑ t η s ≤ γ 1 s ≥ 0 ∑ ∣ f s − p ∣ < ∞
for every t t t and every history. The variables η 1 , η 2 , … \eta_1,\eta_2,\ldots η 1 , η 2 , … depend only on the states, so they are independent and identically distributed, with mean p n e w log ( p n e w / p ~ ) + ( 1 − p n e w ) log ( ( 1 − p n e w ) / ( 1 − p ~ ) ) = R p n e w ( p ~ ) p_{\mathrm{new}}\log(p_{\mathrm{new}}/\widetilde{p})+(1-p_{\mathrm{new}})\log((1-p_{\mathrm{new}})/(1-\widetilde{p}))=R_{p_{\mathrm{new}}}(\widetilde{p}) p new log ( p new / p ) + ( 1 − p new ) log (( 1 − p new ) / ( 1 − p )) = R p new ( p ) by Equation (2) . The strong law of large numbers gives the result.
The next lemma bounds the growth regret of a population whose maladapted lineage moves toward the new optimum at least as fast as under learning alone.
Lemma C.4 (Regret when the maladapted lineage approaches the optimum). Let λ ∈ ( 0 , 1 ) \lambda\in(0,1) λ ∈ ( 0 , 1 ) , and let f 0 = p o l d , f 1 , … f_0=p_{\mathrm{old}}, f_1,\ldots f 0 = p old , f 1 , … be behaviors of the maladapted lineage, which may depend on the agent’s draws but not on the states, such that every f t f_t f t lies between p o l d p_{\mathrm{old}} p old and p n e w p_{\mathrm{new}} p new and ∣ f t − p n e w ∣ ≤ ( 1 − λ ) t ∣ p o l d − p n e w ∣ \lvert f_t-p_{\mathrm{new}}\rvert\le(1-\lambda)^t\lvert p_{\mathrm{old}}-p_{\mathrm{new}}\rvert ∣ f t − p new ∣ ≤ ( 1 − λ ) t ∣ p old − p new ∣ . Let q t q_t q t evolve according to Equation (5) with p = p n e w p=p_{\mathrm{new}} p = p new , f 1 , t = p n e w f_{1,t}=p_{\mathrm{new}} f 1 , t = p new , f 2 , t = f t f_{2,t}=f_t f 2 , t = f t , and q 0 ∈ [ 0 , 1 ) q_0\in[0,1) q 0 ∈ [ 0 , 1 ) , and let f ˉ t ≡ q t p n e w + ( 1 − q t ) f t \bar{f}_t\equiv q_t p_{\mathrm{new}}+(1-q_t)f_t f ˉ t ≡ q t p new + ( 1 − q t ) f t . Let
γ 0 ≡ min { p o l d , 1 − p o l d , p n e w , 1 − p n e w } , K ≡ e 2 ∣ p n e w − p o l d ∣ / ( γ 0 λ ) 4 γ 0 ( 1 − γ 0 ) . (21) \gamma_0\equiv\min\{p_{\mathrm{old}},1-p_{\mathrm{old}},p_{\mathrm{new}},1-p_{\mathrm{new}}\},\qquad K\equiv\frac{e^{2\lvert p_{\mathrm{new}}-p_{\mathrm{old}}\rvert/(\gamma_0\lambda)}}{4\gamma_0(1-\gamma_0)}. \tag*{(21)} γ 0 ≡ min { p old , 1 − p old , p new , 1 − p new } , K ≡ 4 γ 0 ( 1 − γ 0 ) e 2 ∣ p new − p old ∣ / ( γ 0 λ ) . (21) Then, for every t t t and every history,
1 K ( f t − p n e w p o l d − p n e w ) 2 ≤ R p n e w ( f ˉ t ) R p n e w ( f ˉ 0 ) ≤ K ( f t − p n e w p o l d − p n e w ) 2 . (22) \frac{1}{K}\left(\frac{f_t-p_{\mathrm{new}}}{p_{\mathrm{old}}-p_{\mathrm{new}}}\right)^2\le\frac{R_{p_{\mathrm{new}}}(\bar{f}_t)}{R_{p_{\mathrm{new}}}(\bar{f}_0)}\le K\left(\frac{f_t-p_{\mathrm{new}}}{p_{\mathrm{old}}-p_{\mathrm{new}}}\right)^2. \tag*{(22)} K 1 ( p old − p new f t − p new ) 2 ≤ R p new ( f ˉ 0 ) R p new ( f ˉ t ) ≤ K ( p old − p new f t − p new ) 2 . (22)
Proof of Lemma C.4. Note that γ 0 ∈ ( 0 , 1 2 ] \gamma_0\in(0,\frac{1}{2}] γ 0 ∈ ( 0 , 2 1 ] and, since γ 0 ( 1 − γ 0 ) ≤ 1 4 \gamma_0(1-\gamma_0)\le\frac{1}{4} γ 0 ( 1 − γ 0 ) ≤ 4 1 , K ≥ 1 K\ge1 K ≥ 1 . We first show that
e − ∣ p n e w − p o l d ∣ / ( γ 0 λ ) ≤ 1 − q t 1 − q 0 ≤ e ∣ p n e w − p o l d ∣ / ( γ 0 λ ) . (23) e^{-\lvert p_{\mathrm{new}}-p_{\mathrm{old}}\rvert/(\gamma_0\lambda)}\le\frac{1-q_t}{1-q_0}\le e^{\lvert p_{\mathrm{new}}-p_{\mathrm{old}}\rvert/(\gamma_0\lambda)}. \tag*{(23)} e − ∣ p new − p old ∣ / ( γ 0 λ ) ≤ 1 − q 0 1 − q t ≤ e ∣ p new − p old ∣ / ( γ 0 λ ) . (23)
If q 0 = 0 q_0=0 q 0 = 0 , Equation (5) gives q t = 0 q_t=0 q t = 0 for every t t t , and the ratio is one. If q 0 ∈ ( 0 , 1 ) q_0\in(0,1) q 0 ∈ ( 0 , 1 ) , every f t f_t f t and p n e w p_{\mathrm{new}} p new lie in [ γ 0 , 1 − γ 0 ] [\gamma_0,1-\gamma_0] [ γ 0 , 1 − γ 0 ] , and ∑ t ≥ 0 ∣ f t − p n e w ∣ ≤ ∣ p o l d − p n e w ∣ / λ \sum_{t\ge0}\lvert f_t-p_{\mathrm{new}}\rvert\le\lvert p_{\mathrm{old}}-p_{\mathrm{new}}\rvert/\lambda ∑ t ≥ 0 ∣ f t − p new ∣ ≤ ∣ p old − p new ∣ / λ , so Lemma C.3 (a) gives ∣ z t − z 0 ∣ ≤ ∣ p n e w − p o l d ∣ / ( γ 0 λ ) \lvert z_t-z_0\rvert\le\lvert p_{\mathrm{new}}-p_{\mathrm{old}}\rvert/(\gamma_0\lambda) ∣ z t − z 0 ∣ ≤ ∣ p new − p old ∣ / ( γ 0 λ ) . Since 1 − q t = 1 / ( 1 + e z t ) 1-q_t=1/(1+e^{z_t}) 1 − q t = 1/ ( 1 + e z t ) , the ratio ( 1 − q t ) / ( 1 − q 0 ) = ( 1 + e z 0 ) / ( 1 + e z t ) (1-q_t)/(1-q_0)=(1+e^{z_0})/(1+e^{z_t}) ( 1 − q t ) / ( 1 − q 0 ) = ( 1 + e z 0 ) / ( 1 + e z t ) lies between e − ∣ z t − z 0 ∣ e^{-\lvert z_t-z_0\rvert} e − ∣ z t − z 0 ∣ and e ∣ z t − z 0 ∣ e^{\lvert z_t-z_0\rvert} e ∣ z t − z 0 ∣ , which gives Equation (C.6).
By the definitions of f ˉ t \bar{f}_t f ˉ t and f 0 f_0 f 0 ,
f ˉ t − p n e w = ( 1 − q t ) ( f t − p n e w ) , f ˉ 0 − p n e w = ( 1 − q 0 ) ( p o l d − p n e w ) . \bar{f}_t-p_{\mathrm{new}}=(1-q_t)(f_t-p_{\mathrm{new}}),\qquad\bar{f}_0-p_{\mathrm{new}}=(1-q_0)(p_{\mathrm{old}}-p_{\mathrm{new}}). f ˉ t − p new = ( 1 − q t ) ( f t − p new ) , f ˉ 0 − p new = ( 1 − q 0 ) ( p old − p new ) .
Every f ˉ t \bar{f}_t f ˉ t lies between p o l d p_{\mathrm{old}} p old and p n e w p_{\mathrm{new}} p new , and so does every x x x between f ˉ t \bar{f}_t f ˉ t and p n e w p_{\mathrm{new}} p new , so x ( 1 − x ) ≥ γ 0 ( 1 − γ 0 ) x(1-x)\ge\gamma_0(1-\gamma_0) x ( 1 − x ) ≥ γ 0 ( 1 − γ 0 ) for every such x x x . By Lemma C.1(b),
2 ( f ˉ t − p n e w ) 2 ≤ R p n e w ( f ˉ t ) ≤ ( f ˉ t − p n e w ) 2 2 γ 0 ( 1 − γ 0 ) 2(\bar{f}_t-p_{\mathrm{new}})^2\le R_{p_{\mathrm{new}}}(\bar{f}_t)\le\frac{(\bar{f}_t-p_{\mathrm{new}})^2}{2\gamma_0(1-\gamma_0)} 2 ( f ˉ t − p new ) 2 ≤ R p new ( f ˉ t ) ≤ 2 γ 0 ( 1 − γ 0 ) ( f ˉ t − p new ) 2
for every t t t , including t = 0 t=0 t = 0 . Dividing the bound for generation t t t by the bound for generation 0 0 0 , and using Equation (C.6), gives Equation (C.5).
The next lemma describes one generation of search and learning toward a target p ^ ∈ ( 0 , 1 ) \hat{p}\in(0,1) p ^ ∈ ( 0 , 1 ) with p ^ ≠ p o l d \hat{p}\ne p_{\mathrm{old}} p ^ = p old . The target is p ^ = p n e w \hat{p}=p_{\mathrm{new}} p ^ = p new under Mechanism A and p ^ = p ~ \hat{p}=\tilde{p} p ^ = p ~ under Mechanism A ~ \tilde{A} A ~ . Let f 0 = p o l d f_0=p_{\mathrm{old}} f 0 = p old , and for t ≥ 1 t\ge1 t ≥ 1 let
x t , j = f t − 1 + ρ U t , j ( p ^ − f t − 1 ) , j = 1 , … , N , x_{t,j}=f_{t-1}+\rho U_{t,j}(\hat{p}-f_{t-1}),\qquad j=1,\ldots,N, x t , j = f t − 1 + ρ U t , j ( p ^ − f t − 1 ) , j = 1 , … , N ,
J t ∈ arg min 1 ≤ j ≤ N ∣ x t , j − p ^ ∣ , f t = x t , J t + λ ( p ^ − x t , J t ) , (24) J_t\in\mathop{\arg\min}_{1\le j\le N}\lvert x_{t,j}-\hat{p}\rvert,\qquad f_t=x_{t,J_t}+\lambda(\hat{p}-x_{t,J_t}), \tag*{(24)} J t ∈ arg min 1 ≤ j ≤ N ∣ x t , j − p ^ ∣ , f t = x t , J t + λ ( p ^ − x t , J t ) , (24)
where N ≥ 1 N\ge1 N ≥ 1 , ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] , λ ∈ ( 0 , 1 ) \lambda\in(0,1) λ ∈ ( 0 , 1 ) , and the draws U t , j U_{t,j} U t , j are independent and uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) ; for N = 0 N=0 N = 0 , let f t = f t − 1 + λ ( p ^ − f t − 1 ) f_t=f_{t-1}+\lambda(\hat{p}-f_{t-1}) f t = f t − 1 + λ ( p ^ − f t − 1 ) . As in the main text, U t ∗ ≡ max { U t , 1 , … , U t , N } U_t^*\equiv\max\{U_{t,1},\ldots,U_{t,N}\} U t ∗ ≡ max { U t , 1 , … , U t , N } , with U t ∗ ≡ 0 U_t^* \equiv0 U t ∗ ≡ 0 for N = 0 N = 0 N = 0 . Define
S t ≡ ∑ s = 1 t ( − log ( 1 − λ ) − log ( 1 − ρ U s ∗ ) ) , S_t \equiv\sum_{s=1}^{t} \left(-\log(1-\lambda)-\log(1-\rho U_s^*)\right), S t ≡ s = 1 ∑ t ( − log ( 1 − λ ) − log ( 1 − ρ U s ∗ ) ) ,
the cumulative decline of the logarithm of the distance to the target over the first t t t generations.
Lemma C.5 (Search and learning toward a target). For every sequence of draws and every t ≥ 1 t \ge1 t ≥ 1 :
(a) f t − p ^ = ( 1 − λ ) ( 1 − ρ U t ∗ ) ( f t − 1 − p ^ ) f_t-\hat{p}=(1-\lambda)(1-\rho U_t^*)(f_{t-1}-\hat{p}) f t − p ^ = ( 1 − λ ) ( 1 − ρ U t ∗ ) ( f t − 1 − p ^ ) ;
(b) ∣ f t − p ^ ∣ = ∣ p o l d − p ^ ∣ e − S t ≤ ( 1 − λ ) t ∣ p o l d − p ^ ∣ |f_t-\hat{p}|=|p_{\mathrm{old}}-\hat{p}|e^{-S_t}\le(1-\lambda)^t|p_{\mathrm{old}}-\hat{p}| ∣ f t − p ^ ∣ = ∣ p old − p ^ ∣ e − S t ≤ ( 1 − λ ) t ∣ p old − p ^ ∣ , and f t f_t f t lies between p o l d p_{\mathrm{old}} p old and p ^ \hat{p} p ^ .
Moreover, G N ( ρ ) ≤ N G_N(\rho)\le N G N ( ρ ) ≤ N , and S t / t → − log ( 1 − λ ) + G N ( ρ ) S_t/t\to-\log(1-\lambda)+G_N(\rho) S t / t → − log ( 1 − λ ) + G N ( ρ ) with probability one.
Proof of Lemma C.5. (a) For N = 0 N=0 N = 0 the claim is the definition of f t f_t f t . For N ≥ 1 N\ge1 N ≥ 1 , Equation (C.7) gives x t , j − p ^ = ( 1 − ρ U t , j ) ( f t − 1 − p ^ ) x_{t,j}-\hat{p}=(1-\rho U_{t,j})(f_{t-1}-\hat{p}) x t , j − p ^ = ( 1 − ρ U t , j ) ( f t − 1 − p ^ ) , where 1 − ρ U t , j ∈ ( 0 , 1 ) 1-\rho U_{t,j}\in(0,1) 1 − ρ U t , j ∈ ( 0 , 1 ) . Suppose that f t − 1 ≠ p ^ f_{t-1}\ne\hat{p} f t − 1 = p ^ . Then ∣ x t , j − p ^ ∣ = ( 1 − ρ U t , j ) ∣ f t − 1 − p ^ ∣ |x_{t,j}-\hat{p}|=(1-\rho U_{t,j})|f_{t-1}-\hat{p}| ∣ x t , j − p ^ ∣ = ( 1 − ρ U t , j ) ∣ f t − 1 − p ^ ∣ is strictly decreasing in U t , j U_{t,j} U t , j , so every index J t J_t J t that the evaluator may report has U t , J t = U t ∗ U_{t,J_t}=U_t^* U t , J t = U t ∗ , and x t , J t − p ^ = ( 1 − ρ U t ∗ ) ( f t − 1 − p ^ ) x_{t,J_t}-\hat{p}=(1-\rho U_t^*)(f_{t-1}-\hat{p}) x t , J t − p ^ = ( 1 − ρ U t ∗ ) ( f t − 1 − p ^ ) . The learning step multiplies this difference by 1 − λ 1-\lambda 1 − λ . Since f 0 = p o l d ≠ p ^ f_0=p_{\mathrm{old}}\ne\hat{p} f 0 = p old = p ^ and both factors are positive, induction on t t t shows that f t − 1 ≠ p ^ f_{t-1}\ne\hat{p} f t − 1 = p ^ in every generation, which gives part (a).
(b) Iterating part (a), f t − p ^ = ( p o l d − p ^ ) ∏ s = 1 t ( 1 − λ ) ( 1 − ρ U s ∗ ) f_t-\hat{p}=(p_{\mathrm{old}}-\hat{p})\prod_{s=1}^{t}(1-\lambda)(1-\rho U_s^*) f t − p ^ = ( p old − p ^ ) ∏ s = 1 t ( 1 − λ ) ( 1 − ρ U s ∗ ) . Each factor lies in ( 0 , 1 − λ ] (0,1-\lambda] ( 0 , 1 − λ ] , and the logarithm of the product is − S t -S_t − S t , which gives part (b).
Since 1 − ρ U s ∗ ≥ 1 − U s ∗ = min j ( 1 − U s , j ) 1-\rho U_s^*\ge1-U_s^*=\min_j(1-U_{s,j}) 1 − ρ U s ∗ ≥ 1 − U s ∗ = min j ( 1 − U s , j ) , − log ( 1 − ρ U s ∗ ) ≤ max j ( − log ( 1 − U s , j ) ) ≤ ∑ j = 1 N ( − log ( 1 − U s , j ) ) -\log(1-\rho U_s^*)\le\max_j(-\log(1-U_{s,j}))\le\sum_{j=1}^{N}(-\log(1-U_{s,j})) − log ( 1 − ρ U s ∗ ) ≤ max j ( − log ( 1 − U s , j )) ≤ ∑ j = 1 N ( − log ( 1 − U s , j )) . Each − log ( 1 − U s , j ) -\log(1-U_{s,j}) − log ( 1 − U s , j ) has the standard exponential distribution, with mean one, so G N ( ρ ) ≤ N G_N(\rho)\le N G N ( ρ ) ≤ N . The terms of S t S_t S t are independent and identically distributed, because the draws are independent across generations, and they have the finite mean − log ( 1 − λ ) + G N ( ρ ) -\log(1-\lambda)+G_N(\rho) − log ( 1 − λ ) + G N ( ρ ) . The strong law of large numbers gives the limit. □
Lemma C.6 (Integral form of the gain from search). For N ≥ 0 N\ge0 N ≥ 0 and ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] ,
G N ( ρ ) = ∫ 0 1 ρ ( 1 − u N ) 1 − ρ u d u . (25) G_N(\rho)=\int_0^1\frac{\rho(1-u^N)}{1-\rho u}\,du. \tag*{(25)} G N ( ρ ) = ∫ 0 1 1 − ρ u ρ ( 1 − u N ) d u . (25)
Proof of Lemma C.6. For N = 0 N=0 N = 0 , both sides are zero. For N ≥ 1 N\ge1 N ≥ 1 , − log ( 1 − ρ U t ∗ ) = ∫ 0 1 1 { u < U t ∗ } ρ 1 − ρ u d u -\log(1-\rho U_t^*)=\int_0^1\mathbf{1}\{u<U_t^*\}\frac{\rho}{1-\rho u}\,du − log ( 1 − ρ U t ∗ ) = ∫ 0 1 1 { u < U t ∗ } 1 − ρ u ρ d u , where 1 { ⋅ } \mathbf{1}\{\cdot\} 1 { ⋅ } equals one if the condition in braces holds and zero otherwise. The integrand is nonnegative, so Tonelli’s theorem allows the expectation and the integral to be exchanged, and Pr ( U t ∗ > u ) = 1 − u N \Pr(U_t^*>u)=1-u^N Pr ( U t ∗ > u ) = 1 − u N because the N N N draws are independent and uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) . □
Lemma C.7 (Ratios of power series). Let a k > 0 a_k>0 a k > 0 and b k > 0 b_k>0 b k > 0 for k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … , suppose that
A ( r ) ≡ ∑ k ≥ 0 a k r k A(r)\equiv\sum_{k\ge0}a_kr^k A ( r ) ≡ ∑ k ≥ 0 a k r k and B ( r ) ≡ ∑ k ≥ 0 b k r k B(r)\equiv\sum_{k\ge0}b_kr^k B ( r ) ≡ ∑ k ≥ 0 b k r k
converge for r ∈ ( 0 , 1 ) r\in(0,1) r ∈ ( 0 , 1 ) , and suppose that a k / b k a_k/b_k a k / b k is nondecreasing in k k k and not constant. Then A ( r ) / B ( r ) A(r)/B(r) A ( r ) / B ( r ) is strictly increasing on ( 0 , 1 ) (0,1) ( 0 , 1 ) .
Proof of Lemma C.7 . Power series can be differentiated term by term inside their interval of convergence, so the derivative of A / B A/B A / B has the sign of
A ′ ( r ) B ( r ) − A ( r ) B ′ ( r ) = ∑ j , k ≥ 0 ( j − k ) a j b k r j + k − 1 = 1 2 ∑ j , k ≥ 0 ( j − k ) b j b k ( a j b j − a k b k ) r j + k − 1 . A'(r)B(r)-A(r)B'(r)=\sum_{j,k\geq0}(j-k)a_jb_k r^{j+k-1}=\frac{1}{2}\sum_{j,k\geq0}(j-k)b_jb_k\left(\frac{a_j}{b_j}-\frac{a_k}{b_k}\right)r^{j+k-1}. A ′ ( r ) B ( r ) − A ( r ) B ′ ( r ) = j , k ≥ 0 ∑ ( j − k ) a j b k r j + k − 1 = 2 1 j , k ≥ 0 ∑ ( j − k ) b j b k ( b j a j − b k a k ) r j + k − 1 .
where the second equality averages the sum with the sum obtained by exchanging j j j and k k k . Every term of the last sum is nonnegative, because a j / b j − a k / b k a_j/b_j-a_k/b_k a j / b j − a k / b k has the sign of j − k j-k j − k or is zero, and at least one term is positive, because a k / b k a_k/b_k a k / b k is not constant. Hence the derivative is positive on ( 0 , 1 ) (0,1) ( 0 , 1 ) .
Proofs
Proofs for Section 3
Proof of Proposition 1. By Equation (1) , I p ( f ) = log m + p log f + ( 1 − p ) log ( 1 − f ) I_p(f)=\log m+p\log f+(1-p)\log(1-f) I p ( f ) = log m + p log f + ( 1 − p ) log ( 1 − f ) , so
I p ′ ( f ) = p f − 1 − p 1 − f = p − f f ( 1 − f ) , I p ′ ′ ( f ) = − p f 2 − 1 − p ( 1 − f ) 2 < 0. I'_p(f)=\frac{p}{f}-\frac{1-p}{1-f}=\frac{p-f}{f(1-f)},\qquad I''_p(f)=-\frac{p}{f^2}-\frac{1-p}{(1-f)^2}<0. I p ′ ( f ) = f p − 1 − f 1 − p = f ( 1 − f ) p − f , I p ′′ ( f ) = − f 2 p − ( 1 − f ) 2 1 − p < 0.
Hence I p I_p I p is strictly concave on ( 0 , 1 ) (0,1) ( 0 , 1 ) , and its derivative vanishes only at f = p f=p f = p , which is therefore the unique maximizer.
Proof of Proposition 2. Substituting f = p f=p f = p and a general f f f into Equation (1) , the terms log m \log m log m cancel:
I p ( p ) − I p ( f ) = p log p f + ( 1 − p ) log 1 − p 1 − f . I_p(p)-I_p(f)=p\log\frac{p}{f}+(1-p)\log\frac{1-p}{1-f}. I p ( p ) − I p ( f ) = p log f p + ( 1 − p ) log 1 − f 1 − p .
The right side is D K L ( Bern ( p ) ∥ Bern ( f ) ) D_{\mathrm{KL}}(\operatorname{Bern}(p)\mathbin{\|}\operatorname{Bern}(f)) D KL ( Bern ( p ) ∥ Bern ( f )) by the definition of the KL divergence. By Proposition 1, I p ( p ) ≥ I p ( f ) I_p(p)\geq I_p(f) I p ( p ) ≥ I p ( f ) , with equality if and only if f = p f=p f = p .
Proof of Proposition 3. In generation t t t , the two lineages have q t n t q_tn_t q t n t and ( 1 − q t ) n t (1-q_t)n_t ( 1 − q t ) n t individuals. If X t + 1 = α X_{t+1}=\alpha X t + 1 = α , only individuals choosing action a a a reproduce, each with m m m offspring, so n t + 1 = m ( f ˉ 1 , t q t + f ˉ 2 , t ( 1 − q t ) ) n t = m f ˉ t n t n_{t+1}=m(\bar{f}_{1,t}q_t+\bar{f}_{2,t}(1-q_t))n_t=m\bar{f}_tn_t n t + 1 = m ( f ˉ 1 , t q t + f ˉ 2 , t ( 1 − q t )) n t = m f ˉ t n t by Equation (4) ; if X t + 1 = β X_{t+1}=\beta X t + 1 = β , n t + 1 = m ( 1 − f ˉ t ) n t n_{t+1}=m(1-\bar{f}_t)n_t n t + 1 = m ( 1 − f ˉ t ) n t . The behaviors and shares of generation t t t do not depend on X t + 1 X_{t+1} X t + 1 , which equals α \alpha α with probability p p p , so
I p ( q t , f 1 , t , f 2 , t ) = p log ( m f ˉ t ) + ( 1 − p ) log ( m ( 1 − f ˉ t ) ) = I p ( f ˉ t ) , I_p(q_t,f_{1,t},f_{2,t})=p\log(m\bar{f}_t)+(1-p)\log(m(1-\bar{f}_t))=I_p(\bar{f}_t), I p ( q t , f 1 , t , f 2 , t ) = p log ( m f ˉ t ) + ( 1 − p ) log ( m ( 1 − f ˉ t )) = I p ( f ˉ t ) ,
where the last equality is Equation (1) . Since f ˉ t \bar{f}_t f ˉ t is a weighted average of f 1 , t , f 2 , t ∈ ( 0 , 1 ) f_{1,t},f_{2,t}\in(0,1) f 1 , t , f 2 , t ∈ ( 0 , 1 ) , it lies in ( 0 , 1 ) (0,1) ( 0 , 1 ) , and Proposition 2 gives I p ( p ) − I p ( f ˉ t ) = R p ( f ˉ t ) I_p(p)-I_p(\bar{f}_t)=R_p(\bar{f}_t) I p ( p ) − I p ( f ˉ t ) = R p ( f ˉ t ) .
Proofs for Section 4
Proof of Theorem 1. Let q 0 ∈ ( 0 , 1 ) q_0\in(0,1) q 0 ∈ ( 0 , 1 ) , write z t ≡ log ( q t D / ( 1 − q t D ) ) z_t\equiv\log(q_t^{\mathrm{D}}/(1-q_t^{\mathrm{D}})) z t ≡ log ( q t D / ( 1 − q t D )) , and let ξ t ≡ z t − z t − 1 \xi_t\equiv z_t-z_{t-1} ξ t ≡ z t − z t − 1 for t ≥ 1 t\geq1 t ≥ 1 . Mechanism D is the setting of Lemma C.3 with f t = p o l d f_t=p_{\mathrm{old}} f t = p old for every t t t , so Equation (C.3) gives ξ t = log ( p n e w / p o l d ) \xi_t=\log(p_{\mathrm{new}}/p_{\mathrm{old}}) ξ t = log ( p new / p old ) if X t = α X_t=\alpha X t = α and ξ t = log ( ( 1 − p n e w ) / ( 1 − p o l d ) ) \xi_t=\log((1-p_{\mathrm{new}})/(1-p_{\mathrm{old}})) ξ t = log (( 1 − p new ) / ( 1 − p old )) if X t = β X_t=\beta X t = β . The changes ξ 1 , ξ 2 , … \xi_1,\xi_2,\ldots ξ 1 , ξ 2 , … are independent and identically distributed, with mean Δ > 0 \Delta>0 Δ > 0 by Equation (8) , and none exceeds
ξ max ≡ max { log p n e w p o l d , log 1 − p n e w 1 − p o l d } > 0. \xi_{\max} \equiv\max\left\{ \log\frac{p_{\mathrm{new}}}{p_{\mathrm{old}}}, \log\frac{1-p_{\mathrm{new}}}{1-p_{\mathrm{old}}} \right\} > 0. ξ m a x ≡ max { log p old p new , log 1 − p old 1 − p new } > 0.
Since f ˉ t D = q t D p n e w + ( 1 − q t D ) p o l d \bar{f}^{\mathrm{D}}_t = q^{\mathrm{D}}_t p_{\mathrm{new}} + (1-q^{\mathrm{D}}_t)p_{\mathrm{old}} f ˉ t D = q t D p new + ( 1 − q t D ) p old ,
f ˉ t D − p n e w = ( 1 − q t D ) ( p o l d − p n e w ) . (26) \bar{f}^{\mathrm{D}}_t-p_{\mathrm{new}}=(1-q^{\mathrm{D}}_t)(p_{\mathrm{old}}-p_{\mathrm{new}}). \tag*{(26)} f ˉ t D − p new = ( 1 − q t D ) ( p old − p new ) . (26)
By the strong law of large numbers, z t / t → Δ z_t/t \to\Delta z t / t → Δ with probability one, so z t → ∞ z_t \to\infty z t → ∞ and q t D → 1 q^{\mathrm{D}}_t \to1 q t D → 1 . Since 1 − q t D = 1 / ( 1 + e z t ) 1-q^{\mathrm{D}}_t=1/(1+e^{z_t}) 1 − q t D = 1/ ( 1 + e z t ) ,
1 t log ( 1 − q t D ) = − z t t − 1 t log ( 1 + e − z t ) → − Δ . \frac{1}{t}\log(1-q^{\mathrm{D}}_t)=-\frac{z_t}{t}-\frac{1}{t}\log(1+e^{-z_t})\to-\Delta. t 1 log ( 1 − q t D ) = − t z t − t 1 log ( 1 + e − z t ) → − Δ.
By Equation (C.9), f ˉ t D → p n e w \bar{f}^{\mathrm{D}}_t\to p_{\mathrm{new}} f ˉ t D → p new , and Lemma C.1(c) gives
R p n e w ( f ˉ t D ) / ( f ˉ t D − p n e w ) 2 → 1 / ( 2 p n e w ( 1 − p n e w ) ) . \mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{\mathrm{D}}_t)/(\bar{f}^{\mathrm{D}}_t-p_{\mathrm{new}})^2\to1/(2p_{\mathrm{new}}(1-p_{\mathrm{new}})). R p new ( f ˉ t D ) / ( f ˉ t D − p new ) 2 → 1/ ( 2 p new ( 1 − p new )) .
Therefore
1 t log R p n e w ( f ˉ t D ) = 2 t log ( 1 − q t D ) + 2 t log ∣ p o l d − p n e w ∣ + 1 t log R p n e w ( f ˉ t D ) ( f ˉ t D − p n e w ) 2 → − 2 Δ , \frac{1}{t}\log\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{\mathrm{D}}_t)=\frac{2}{t}\log(1-q^{\mathrm{D}}_t)+\frac{2}{t}\log|p_{\mathrm{old}}-p_{\mathrm{new}}|+\frac{1}{t}\log\frac{\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{\mathrm{D}}_t)}{(\bar{f}^{\mathrm{D}}_t-p_{\mathrm{new}})^2}\to-2\Delta, t 1 log R p new ( f ˉ t D ) = t 2 log ( 1 − q t D ) + t 2 log ∣ p old − p new ∣ + t 1 log ( f ˉ t D − p new ) 2 R p new ( f ˉ t D ) → − 2Δ ,
that is, κ D = 2 Δ \kappa^{\mathrm{D}}=2\Delta κ D = 2Δ with probability one.
Fix ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and let
ϕ ( q ) ≡ R p n e w ( q p n e w + ( 1 − q ) p o l d ) , q ∈ [ 0 , 1 ] , \phi(q)\equiv\mathcal{R}_{p_{\mathrm{new}}}(qp_{\mathrm{new}}+(1-q)p_{\mathrm{old}}),\qquad q\in[0,1], ϕ ( q ) ≡ R p new ( q p new + ( 1 − q ) p old ) , q ∈ [ 0 , 1 ] ,
be the regret of a Darwinian population in which the adapted lineage has the share q q q . The distance of q p n e w + ( 1 − q ) p o l d qp_{\mathrm{new}}+(1-q)p_{\mathrm{old}} q p new + ( 1 − q ) p old from p n e w p_{\mathrm{new}} p new is ( 1 − q ) ∣ p o l d − p n e w ∣ (1-q)|p_{\mathrm{old}}-p_{\mathrm{new}}| ( 1 − q ) ∣ p old − p new ∣ , so by Lemma C.1(a), ϕ \phi ϕ is continuous and strictly decreasing, from ϕ ( 0 ) = R p n e w ( p o l d ) = Δ \phi(0)=\mathcal{R}_{p_{\mathrm{new}}}(p_{\mathrm{old}})=\Delta ϕ ( 0 ) = R p new ( p old ) = Δ to ϕ ( 1 ) = 0 \phi(1)=0 ϕ ( 1 ) = 0 . In particular, R p n e w ( f ˉ t D ) = ϕ ( q t D ) \mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{\mathrm{D}}_t)=\phi(q^{\mathrm{D}}_t) R p new ( f ˉ t D ) = ϕ ( q t D ) , and ϕ ( q 0 ) ∈ ( 0 , Δ ) \phi(q_0)\in(0,\Delta) ϕ ( q 0 ) ∈ ( 0 , Δ ) . Let q ∗ ( ε , q 0 ) ∈ ( q 0 , 1 ) q^*(\varepsilon,q_0)\in(q_0,1) q ∗ ( ε , q 0 ) ∈ ( q 0 , 1 ) be the unique share with
ϕ ( q ∗ ( ε , q 0 ) ) = ε ϕ ( q 0 ) , \phi(q^*(\varepsilon,q_0))=\varepsilon\phi(q_0), ϕ ( q ∗ ( ε , q 0 )) = εϕ ( q 0 ) ,
and let q ε ∈ ( 0 , 1 ) q_\varepsilon\in(0,1) q ε ∈ ( 0 , 1 ) be the unique share with ϕ ( q ε ) = ε Δ \phi(q_\varepsilon)=\varepsilon\Delta ϕ ( q ε ) = ε Δ . Since ϕ \phi ϕ is strictly decreasing, R p n e w ( f ˉ t D ) ≤ ε R p n e w ( f ˉ 0 D ) \mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{\mathrm{D}}_t)\le\varepsilon\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{\mathrm{D}}_0) R p new ( f ˉ t D ) ≤ ε R p new ( f ˉ 0 D ) if and only if q t D ≥ q ∗ ( ε , q 0 ) q^{\mathrm{D}}_t\ge q^*(\varepsilon,q_0) q t D ≥ q ∗ ( ε , q 0 ) , that is, if and only if ξ 1 + ⋯ + ξ t ≥ d ( ε , q 0 ) \xi_1+\cdots+\xi_t\ge d(\varepsilon,q_0) ξ 1 + ⋯ + ξ t ≥ d ( ε , q 0 ) , where
d ( ε , q 0 ) ≡ log q ∗ ( ε , q 0 ) 1 − q ∗ ( ε , q 0 ) − log q 0 1 − q 0 > 0 d(\varepsilon,q_0)\equiv\log\frac{q^*(\varepsilon,q_0)}{1-q^*(\varepsilon,q_0)}-\log\frac{q_0}{1-q_0}>0 d ( ε , q 0 ) ≡ log 1 − q ∗ ( ε , q 0 ) q ∗ ( ε , q 0 ) − log 1 − q 0 q 0 > 0
is the distance that the logarithm of the ratio of the two lineages’ sizes must travel. Hence τ D ( ε , q 0 ) \tau^{\mathrm{D}}(\varepsilon,q_0) τ D ( ε , q 0 ) is the first passage time of Lemma C.2 with d = d ( ε , q 0 ) d=d(\varepsilon,q_0) d = d ( ε , q 0 ) and μ = Δ \mu=\Delta μ = Δ , and
d ( ε , q 0 ) Δ ≤ E τ D ( ε , q 0 ) < d ( ε , q 0 ) + ξ max Δ . (27) \frac{d(\varepsilon,q_0)}{\Delta}\le\mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0)<\frac{d(\varepsilon,q_0)+\xi_{\max}}{\Delta}. \tag*{(27)} Δ d ( ε , q 0 ) ≤ E τ D ( ε , q 0 ) < Δ d ( ε , q 0 ) + ξ m a x . (27)
We now bound d ( ε , q 0 ) d(\varepsilon,q_0) d ( ε , q 0 ) , which is the sum of two terms:
d ( ε , q 0 ) = log q ∗ ( ε , q 0 ) q 0 + log 1 − q 0 1 − q ∗ ( ε , q 0 ) . d(\varepsilon,q_0)=\log\frac{q^*(\varepsilon,q_0)}{q_0}+\log\frac{1-q_0}{1-q^*(\varepsilon,q_0)}. d ( ε , q 0 ) = log q 0 q ∗ ( ε , q 0 ) + log 1 − q ∗ ( ε , q 0 ) 1 − q 0 .
For the first term, ϕ ( q ∗ ( ε , q 0 ) ) = ε ϕ ( q 0 ) < ε Δ = ϕ ( q ε ) \phi(q^*(\varepsilon,q_0))=\varepsilon\phi(q_0)<\varepsilon\Delta=\phi(q_\varepsilon) ϕ ( q ∗ ( ε , q 0 )) = εϕ ( q 0 ) < ε Δ = ϕ ( q ε ) , so q ∗ ( ε , q 0 ) > q ε q^*(\varepsilon,q_0)>q_\varepsilon q ∗ ( ε , q 0 ) > q ε ; together with q ∗ ( ε , q 0 ) < 1 q^*(\varepsilon,q_0)<1 q ∗ ( ε , q 0 ) < 1 , this gives
log 1 q 0 + log q ε < log q ∗ ( ε , q 0 ) q 0 < log 1 q 0 . (28) \log\frac{1}{q_0}+\log q_\varepsilon<\log\frac{q^*(\varepsilon,q_0)}{q_0}<\log\frac{1}{q_0}. \tag*{(28)} log q 0 1 + log q ε < log q 0 q ∗ ( ε , q 0 ) < log q 0 1 . (28)
For the second term, let v = min { p o l d ( 1 − p o l d ) , p n e w ( 1 − p n e w ) } v=\min\{p_{\mathrm{old}}(1-p_{\mathrm{old}}),p_{\mathrm{new}}(1-p_{\mathrm{new}})\} v = min { p old ( 1 − p old ) , p new ( 1 − p new )} . Every x x x between p n e w p_{\mathrm{new}} p new and q p n e w + ( 1 − q ) p o l d qp_{\mathrm{new}}+(1-q)p_{\mathrm{old}} q p new + ( 1 − q ) p old lies between p o l d p_{\mathrm{old}} p old and p n e w p_{\mathrm{new}} p new , where x ( 1 − x ) ≥ v x(1-x)\ge v x ( 1 − x ) ≥ v because x ( 1 − x ) x(1-x) x ( 1 − x ) is concave. By Lemma C.1(b), for every q ∈ [ 0 , 1 ] q\in[0,1] q ∈ [ 0 , 1 ] ,
2 ( 1 − q ) 2 ( p n e w − p o l d ) 2 ≤ ϕ ( q ) ≤ ( 1 − q ) 2 ( p n e w − p o l d ) 2 2 v . 2(1-q)^2(p_{\mathrm{new}}-p_{\mathrm{old}})^2\le\phi(q)\le\frac{(1-q)^2(p_{\mathrm{new}}-p_{\mathrm{old}})^2}{2v}. 2 ( 1 − q ) 2 ( p new − p old ) 2 ≤ ϕ ( q ) ≤ 2 v ( 1 − q ) 2 ( p new − p old ) 2 .
Applying the upper bound at q ∗ ( ε , q 0 ) q^*(\varepsilon,q_0) q ∗ ( ε , q 0 ) and the lower bound at q 0 q_0 q 0 , and then the lower bound at q ∗ ( ε , q 0 ) q^*(\varepsilon,q_0) q ∗ ( ε , q 0 ) and the upper bound at q 0 q_0 q 0 , the equation ϕ ( q ∗ ( ε , q 0 ) ) = ε ϕ ( q 0 ) \phi(q^*(\varepsilon,q_0))=\varepsilon\phi(q_0) ϕ ( q ∗ ( ε , q 0 )) = εϕ ( q 0 ) gives
4 ε v ≤ ( 1 − q ∗ ( ε , q 0 ) 1 − q 0 ) 2 ≤ ε 4 v , so 1 2 log 4 v ε ≤ log 1 − q 0 1 − q ∗ ( ε , q 0 ) ≤ 1 2 log 1 4 ε v . (29) 4\varepsilon v\le\left(\frac{1-q^*(\varepsilon,q_0)}{1-q_0}\right)^2\le\frac{\varepsilon}{4v},
\qquad\text{so}\qquad
\frac{1}{2}\log\frac{4v}{\varepsilon}\le\log\frac{1-q_0}{1-q^*(\varepsilon,q_0)}\le\frac{1}{2}\log\frac{1}{4\varepsilon v}. \tag*{(29)} 4 ε v ≤ ( 1 − q 0 1 − q ∗ ( ε , q 0 ) ) 2 ≤ 4 v ε , so 2 1 log ε 4 v ≤ log 1 − q ∗ ( ε , q 0 ) 1 − q 0 ≤ 2 1 log 4 ε v 1 . (29)
For the first limit in Equation (7) , fix q 0 q_0 q 0 . By Equation (C.11), the first term of d ( ε , q 0 ) d(\varepsilon,q_0) d ( ε , q 0 ) lies in ( 0 , log ( 1 / q 0 ) ) (0,\log(1/q_0)) ( 0 , log ( 1/ q 0 )) , because q ∗ ( ε , q 0 ) > q 0 q^*(\varepsilon,q_0)>q_0 q ∗ ( ε , q 0 ) > q 0 . By Equation (C.12), the second term differs from 1 2 log ( 1 / ε ) \frac{1}{2}\log(1/\varepsilon) 2 1 log ( 1/ ε ) by at most 1 2 log ( 1 / ( 4 v ) ) \frac{1}{2}\log(1/(4v)) 2 1 log ( 1/ ( 4 v )) . Hence d ( ε , q 0 ) / log ( 1 / ε ) → 1 2 d(\varepsilon,q_0)/\log(1/\varepsilon)\to\frac{1}{2} d ( ε , q 0 ) / log ( 1/ ε ) → 2 1 as ε → 0 \varepsilon\to0 ε → 0 , and dividing Equation (C.10) by log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε ) gives E τ D ( ε , q 0 ) / log ( 1 / ε ) → 1 / ( 2 Δ ) = 1 / κ D \mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0)/\log(1/\varepsilon)\to1/(2\Delta)=1/\kappa^{\mathrm{D}} E τ D ( ε , q 0 ) / log ( 1/ ε ) → 1/ ( 2Δ ) = 1/ κ D .
For the second limit, fix ε \varepsilon ε . Adding Equations (C.11) and (C.12) and using Equation (C.10),
1 Δ ( log q ε + 1 2 log 4 v ε ) < E τ D ( ε , q 0 ) − log ( 1 / q 0 ) Δ < 1 Δ ( 1 2 log 1 4 ε v + ξ max ) . \frac{1}{\Delta}\left(\log q_\varepsilon+\frac{1}{2}\log\frac{4v}{\varepsilon}\right)<\mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0)-\frac{\log(1/q_0)}{\Delta}<\frac{1}{\Delta}\left(\frac{1}{2}\log\frac{1}{4\varepsilon v}+\xi_{\max}\right). Δ 1 ( log q ε + 2 1 log ε 4 v ) < E τ D ( ε , q 0 ) − Δ log ( 1/ q 0 ) < Δ 1 ( 2 1 log 4 ε v 1 + ξ m a x ) .
Neither bound depends on q 0 q_0 q 0 . Dividing by log ( 1 / q 0 ) \log(1/q_0) log ( 1/ q 0 ) , which tends to infinity as q 0 → 0 q_0\to0 q 0 → 0 , gives E τ D ( ε , q 0 ) / log ( 1 / q 0 ) → 1 / Δ \mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0)/\log(1/q_0)\to1/\Delta E τ D ( ε , q 0 ) / log ( 1/ q 0 ) → 1/Δ .
Proofs for Section 5
Proof of Theorem 2. Let q 0 ∈ [ 0 , 1 ) q_0\in[0,1) q 0 ∈ [ 0 , 1 ) . Iterating Equation (9) gives f t L − p n e w = ( 1 − λ ) t ( p o l d − p n e w ) f_t^{\mathrm{L}}-p_{\mathrm{new}}=(1-\lambda)^t(p_{\mathrm{old}}-p_{\mathrm{new}}) f t L − p new = ( 1 − λ ) t ( p old − p new ) , so f t L f_t^{\mathrm{L}} f t L lies between p o l d p_{\mathrm{old}} p old and p n e w p_{\mathrm{new}} p new and does not depend on the states. The selection step of Mechanism L is Equation (5) with f 1 , t = p n e w f_{1,t}=p_{\mathrm{new}} f 1 , t = p new and f 2 , t = f t L f_{2,t}=f_t^{\mathrm{L}} f 2 , t = f t L . Lemma C.4 therefore applies with f t = f t L f_t=f_t^{\mathrm{L}} f t = f t L , and, with K K K from Equation (C.4),
( 1 − λ ) 2 t K ≤ R p n e w ( f t L ) R p n e w ( f 0 L ) ≤ K ( 1 − λ ) 2 t . (30) \frac{(1-\lambda)^{2t}}{K}\le\frac{\mathcal{R}_{p_{\mathrm{new}}}(f_t^{\mathrm{L}})}{\mathcal{R}_{p_{\mathrm{new}}}(f_0^{\mathrm{L}})}\le K(1-\lambda)^{2t}. \tag*{(30)} K ( 1 − λ ) 2 t ≤ R p new ( f 0 L ) R p new ( f t L ) ≤ K ( 1 − λ ) 2 t . (30)
for every t t t and every history. The constant K K K depends on neither q 0 q_0 q 0 nor the history. (i) By Equation (C.13), along every history, log R p n e w ( f ˉ t L ) \log\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{L}_{t}) log R p new ( f ˉ t L ) differs from 2 t log ( 1 − λ ) 2t\log(1-\lambda) 2 t log ( 1 − λ ) by at most log K + ∣ log R p n e w ( f ˉ 0 L ) ∣ \log K + \lvert\log\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{L}_{0})\rvert log K + ∣ log R p new ( f ˉ 0 L )∣ , which does not depend on t t t . Dividing by t t t and letting t → ∞ t \to\infty t → ∞ gives κ L = − 2 log ( 1 − λ ) \kappa^{L}=-2\log(1-\lambda) κ L = − 2 log ( 1 − λ ) .
(ii) Since ( 1 − λ ) 2 t = e − κ L t (1-\lambda)^{2t}=e^{-\kappa^{L}t} ( 1 − λ ) 2 t = e − κ L t , Equation (C.13) shows that R p n e w ( f ˉ t L ) / R p n e w ( f ˉ 0 L ) > ε \mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{L}_{t})/\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}^{L}_{0})>\varepsilon R p new ( f ˉ t L ) / R p new ( f ˉ 0 L ) > ε whenever e − κ L t / K > ε e^{-\kappa^{L}t}/K>\varepsilon e − κ L t / K > ε , and that it is at most ε \varepsilon ε whenever K e − κ L t ≤ ε Ke^{-\kappa^{L}t}\leq\varepsilon K e − κ L t ≤ ε . Hence, along every history,
log ( 1 / ( K ε ) ) κ L ≤ τ L ( ε , q 0 ) < log ( K / ε ) κ L + 1. (31) \frac{\log(1/(K\varepsilon))}{\kappa^{L}} \leq\tau^{L}(\varepsilon,q_{0}) < \frac{\log(K/\varepsilon)}{\kappa^{L}}+1. \tag*{(31)} κ L log ( 1/ ( K ε )) ≤ τ L ( ε , q 0 ) < κ L log ( K / ε ) + 1. (31)
Dividing by log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε ) and letting ε → 0 \varepsilon\to0 ε → 0 shows that τ L ( ε , q 0 ) / log ( 1 / ε ) → 1 / κ L \tau^{L}(\varepsilon,q_{0})/\log(1/\varepsilon)\to1/\kappa^{L} τ L ( ε , q 0 ) / log ( 1/ ε ) → 1/ κ L along every history; since the bounds in Equation (C.14) do not depend on the history, the same holds for E τ L ( ε , q 0 ) / log ( 1 / ε ) \mathbb{E}\,\tau^{L}(\varepsilon,q_{0})/\log(1/\varepsilon) E τ L ( ε , q 0 ) / log ( 1/ ε ) , which gives the first statement. For the second, the upper bound in Equation (C.14) does not depend on q 0 q_{0} q 0 , so sup q 0 ∈ [ 0 , 1 ) E τ L ( ε , q 0 ) ≤ log ( K / ε ) / κ L + 1 < ∞ \sup_{q_{0}\in[0,1)}\mathbb{E}\,\tau^{L}(\varepsilon,q_{0})\leq\log(K/\varepsilon)/\kappa^{L}+1<\infty sup q 0 ∈ [ 0 , 1 ) E τ L ( ε , q 0 ) ≤ log ( K / ε ) / κ L + 1 < ∞ . □
Proofs for Section 6
Proof of Theorem 3. Let q 0 ∈ [ 0 , 1 ) q_{0}\in[0,1) q 0 ∈ [ 0 , 1 ) . The search, evaluation, and learning steps of Mechanism A are Equation (C.7) with p ^ = p n e w \hat{p}=p_{\mathrm{new}} p ^ = p new , and Lemma C.5 (a) is Equation (11) . By Lemma C.5 (b), for every sequence of draws, f t A f^{A}_{t} f t A lies between p o l d p_{\mathrm{old}} p old and p n e w p_{\mathrm{new}} p new , ∣ f t A − p n e w ∣ = ∣ p o l d − p n e w ∣ e − S t \lvert f^{A}_{t}-p_{\mathrm{new}}\rvert=\lvert p_{\mathrm{old}}-p_{\mathrm{new}}\rvert e^{-S_{t}} ∣ f t A − p new ∣ = ∣ p old − p new ∣ e − S t , and ∣ f t A − p n e w ∣ ≤ ( 1 − λ ) t ∣ p o l d − p n e w ∣ \lvert f^{A}_{t}-p_{\mathrm{new}}\rvert\leq(1-\lambda)^{t}\lvert p_{\mathrm{old}}-p_{\mathrm{new}}\rvert ∣ f t A − p new ∣ ≤ ( 1 − λ ) t ∣ p old − p new ∣ . The draws do not depend on the states, and the selection step of Mechanism A is Equation (5) with f 1 , t = p n e w f_{1,t}=p_{\mathrm{new}} f 1 , t = p new and f 2 , t = f t A f_{2,t}=f^{A}_{t} f 2 , t = f t A . Lemma C.4 therefore applies with f t = f t A f_{t}=f^{A}_{t} f t = f t A :
e − 2 S t K ≤ R p n e w ( f t A ) R p n e w ( f 0 A ) ≤ K e − 2 S t (32) \frac{e^{-2S_{t}}}{K}\leq\frac{\mathcal{R}_{p_{\mathrm{new}}}(f^{A}_{t})}{\mathcal{R}_{p_{\mathrm{new}}}(f^{A}_{0})}\leq Ke^{-2S_{t}} \tag*{(32)} K e − 2 S t ≤ R p new ( f 0 A ) R p new ( f t A ) ≤ K e − 2 S t (32)
for every t t t , every history, and every sequence of draws, with K K K from Equation (C.4).
(i) By Lemma C.5 , S t / t → − log ( 1 − λ ) + G N ( ρ ) = κ L / 2 + G N ( ρ ) S_{t}/t\to-\log(1-\lambda)+G_{N}(\rho)=\kappa^{L}/2+G_{N}(\rho) S t / t → − log ( 1 − λ ) + G N ( ρ ) = κ L /2 + G N ( ρ ) with probability one, and by Equation (C.15), − 1 t log R p n e w ( f t A ) -\frac{1}{t}\log\mathcal{R}_{p_{\mathrm{new}}}(f^{A}_{t}) − t 1 log R p new ( f t A ) differs from 2 S t / t 2S_{t}/t 2 S t / t by at most ( log K + ∣ log R p n e w ( f 0 A ) ∣ ) / t (\log K+\lvert\log\mathcal{R}_{p_{\mathrm{new}}}(f^{A}_{0})\rvert)/t ( log K + ∣ log R p new ( f 0 A )∣) / t . Hence κ A = κ L + 2 G N ( ρ ) \kappa^{A}=\kappa^{L}+2G_{N}(\rho) κ A = κ L + 2 G N ( ρ ) with probability one. The variable − log ( 1 − ρ U t ∗ ) -\log(1-\rho U^{*}_{t}) − log ( 1 − ρ U t ∗ ) is nonnegative, so G N ( ρ ) ≥ 0 G_{N}(\rho)\geq0 G N ( ρ ) ≥ 0 , and G 0 ( ρ ) = 0 G_{0}(\rho)=0 G 0 ( ρ ) = 0 because U t ∗ ≡ 0 U^{*}_{t}\equiv0 U t ∗ ≡ 0 when N = 0 N=0 N = 0 .
(ii) Each term of S t S_{t} S t is at least − log ( 1 − λ ) = κ L / 2 > 0 -\log(1-\lambda)=\kappa^{L}/2>0 − log ( 1 − λ ) = κ L /2 > 0 , so S t S_{t} S t rises strictly with t t t and 2 S t ≥ κ L t 2S_{t}\geq\kappa^{L}t 2 S t ≥ κ L t . For x ∈ R x\in\mathbb{R} x ∈ R , let T ( x ) ≡ min { t ≥ 0 : 2 S t ≥ x } T(x)\equiv\min\{t\geq0:2S_{t}\geq x\} T ( x ) ≡ min { t ≥ 0 : 2 S t ≥ x } , so that T ( x ) = 0 T(x)=0 T ( x ) = 0 for x ≤ 0 x\leq0 x ≤ 0 and T ( x ) ≤ ⌈ x / κ L ⌉ T(x)\leq\lceil x/\kappa^{L}\rceil T ( x ) ≤ ⌈ x / κ L ⌉ for x > 0 x>0 x > 0 . By Equation (C.15), the population’s regret is at most ε R p n e w ( f 0 A ) \varepsilon\mathcal{R}_{p_{\mathrm{new}}}(f^{A}_{0}) ε R p new ( f 0 A ) once 2 S t ≥ log ( K / ε ) 2S_{t}\geq\log(K/\varepsilon) 2 S t ≥ log ( K / ε ) , and it exceeds ε R p n e w ( f 0 A ) \varepsilon\mathcal{R}_{p_{\mathrm{new}}}(f^{A}_{0}) ε R p new ( f 0 A ) while 2 S t < log ( 1 / ( K ε ) ) 2S_{t}<\log(1/(K\varepsilon)) 2 S t < log ( 1/ ( K ε )) . Since S t S_{t} S t rises with t t t ,
T ( log ( 1 / ( K ε ) ) ) ≤ τ A ( ε , q 0 ) ≤ T ( log ( K / ε ) ) ≤ ⌈ log ( K / ε ) κ L ⌉ (33) T(\log(1/(K\varepsilon)))\leq\tau^{A}(\varepsilon,q_{0})\leq T(\log(K/\varepsilon))\leq\left\lceil\frac{\log(K/\varepsilon)}{\kappa^{L}}\right\rceil \tag*{(33)} T ( log ( 1/ ( K ε ))) ≤ τ A ( ε , q 0 ) ≤ T ( log ( K / ε )) ≤ ⌈ κ L log ( K / ε ) ⌉ (33)
for every history and every sequence of draws. The last bound does not depend on q 0 q_{0} q 0 , which gives the second statement in Equation (13) . For the first, T ( x ) → ∞ T(x)\to\infty T ( x ) → ∞ as x → ∞ x\to\infty x → ∞ , and 2 S T ( x ) − 1 < x ≤ 2 S T ( x ) 2S_{T(x)-1}<x\leq2S_{T(x)} 2 S T ( x ) − 1 < x ≤ 2 S T ( x ) for x > 0 x>0 x > 0 , so 2 S t / t → κ A 2S_{t}/t\to\kappa^{A} 2 S t / t → κ A gives T ( x ) / x → 1 / κ A T(x)/x\to1/\kappa^{A} T ( x ) / x → 1/ κ A with probability one. Since log ( 1 / ( K ε ) ) / log ( 1 / ε ) \log(1/(K\varepsilon))/\log(1/\varepsilon) log ( 1/ ( K ε )) / log ( 1/ ε ) and log ( K / ε ) / log ( 1 / ε ) \log(K/\varepsilon)/\log(1/\varepsilon) log ( K / ε ) / log ( 1/ ε ) tend to one as ε → 0 \varepsilon\to0 ε → 0 , Equation (C.16) gives τ A ( ε , q 0 ) / log ( 1 / ε ) → 1 / κ A \tau^{A}(\varepsilon,q_{0})/\log(1/\varepsilon)\to1/\kappa^{A} τ A ( ε , q 0 ) / log ( 1/ ε ) → 1/ κ A with probability one. For ε ≤ 1 2 \varepsilon\leq\frac{1}{2} ε ≤ 2 1 , the same equation bounds this ratio by ( 1 + log K / log 2 ) / κ L + 1 / log 2 (1+\log K/\log2)/\kappa^{L}+1/\log2 ( 1 + log K / log 2 ) / κ L + 1/ log 2 , so the bounded convergence theorem gives E τ A ( ε , q 0 ) / log ( 1 / ε ) → 1 / κ A \mathbb{E}\,\tau^{A}(\varepsilon,q_{0})/\log(1/\varepsilon)\to1/\kappa^{A} E τ A ( ε , q 0 ) / log ( 1/ ε ) → 1/ κ A . □
Proof of Proposition 4. We use the integral form of G N ( ρ ) G_N(\rho) G N ( ρ ) in Equation (C.8) of Lemma C.6.
(i) For u ∈ ( 0 , 1 ) u \in(0,1) u ∈ ( 0 , 1 ) , the integrand ρ ( 1 − u N ) / ( 1 − ρ u ) \rho(1-u^N)/(1-\rho u) ρ ( 1 − u N ) / ( 1 − ρ u ) rises strictly with N N N , because u N u^N u N falls. For N ≥ 1 N \ge1 N ≥ 1 , it rises strictly with ρ \rho ρ , because ρ / ( 1 − ρ u ) \rho/(1-\rho u) ρ / ( 1 − ρ u ) does and 1 − u N > 0 1-u^N > 0 1 − u N > 0 .
(ii) For ρ = 1 \rho= 1 ρ = 1 , the integrand is ( 1 − u N ) / ( 1 − u ) = 1 + u + ⋯ + u N − 1 (1-u^N)/(1-u)=1+u+\cdots+u^{N-1} ( 1 − u N ) / ( 1 − u ) = 1 + u + ⋯ + u N − 1 , whose integral over [ 0 , 1 ] [0,1] [ 0 , 1 ] is 1 + 1 2 + ⋯ + 1 N 1+\frac{1}{2}+\cdots+\frac{1}{N} 1 + 2 1 + ⋯ + N 1 . Since 1 / u 1/u 1/ u is decreasing, ∫ k k + 1 d u / u ≤ 1 / k \int_k^{k+1}du/u \le1/k ∫ k k + 1 d u / u ≤ 1/ k for k ≥ 1 k \ge1 k ≥ 1 and 1 / k ≤ ∫ k − 1 k d u / u 1/k \le\int_{k-1}^{k}du/u 1/ k ≤ ∫ k − 1 k d u / u for k ≥ 2 k \ge2 k ≥ 2 , so
log ( N + 1 ) ≤ 1 + 1 2 + ⋯ + 1 N ≤ 1 + log N . \log(N+1) \le1+\frac{1}{2}+\cdots+\frac{1}{N} \le1+\log N. log ( N + 1 ) ≤ 1 + 2 1 + ⋯ + N 1 ≤ 1 + log N .
Dividing by log N \log N log N and letting N → ∞ N \to\infty N → ∞ gives G N ( 1 ) / log N → 1 G_N(1)/\log N \to1 G N ( 1 ) / log N → 1 .
(iii) For ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) , the integrand is below ρ / ( 1 − ρ u ) \rho/(1-\rho u) ρ / ( 1 − ρ u ) for u ∈ ( 0 , 1 ] u \in(0,1] u ∈ ( 0 , 1 ] , and ∫ 0 1 ρ / ( 1 − ρ u ) d u = − log ( 1 − ρ ) \int_0^1 \rho/(1-\rho u)\,du=-\log(1-\rho) ∫ 0 1 ρ / ( 1 − ρ u ) d u = − log ( 1 − ρ ) , so G N ( ρ ) < − log ( 1 − ρ ) G_N(\rho)<-\log(1-\rho) G N ( ρ ) < − log ( 1 − ρ ) . As N → ∞ N \to\infty N → ∞ , the integrand rises to ρ / ( 1 − ρ u ) \rho/(1-\rho u) ρ / ( 1 − ρ u ) , and the monotone convergence theorem gives G N ( ρ ) → − log ( 1 − ρ ) G_N(\rho)\to-\log(1-\rho) G N ( ρ ) → − log ( 1 − ρ ) .
Proof of Proposition 5. By Equation (C.8), for N ≥ 0 N \ge0 N ≥ 0 ,
G N + 1 ( ρ ) − G N ( ρ ) = ∫ 0 1 ρ u N ( 1 − u ) 1 − ρ u d u , (34) G_{N+1}(\rho)-G_N(\rho)=\int_0^1\frac{\rho u^N(1-u)}{1-\rho u}\,du, \tag*{(34)} G N + 1 ( ρ ) − G N ( ρ ) = ∫ 0 1 1 − ρ u ρ u N ( 1 − u ) d u , (34)
which is positive and strictly decreasing in N N N .
(i) By Equation (14) , cross-multiplying shows that C ( N + 1 ) C(N+1) C ( N + 1 ) is below, equal to, or above C ( N ) C(N) C ( N ) according as
ψ ( N ) = 2 ( 1 + c N ) ( G N + 1 ( ρ ) − G N ( ρ ) ) − c ( κ L + 2 G N ( ρ ) ) \psi(N)=2(1+cN)\left(G_{N+1}(\rho)-G_N(\rho)\right)-c\left(\kappa^L+2G_N(\rho)\right) ψ ( N ) = 2 ( 1 + c N ) ( G N + 1 ( ρ ) − G N ( ρ ) ) − c ( κ L + 2 G N ( ρ ) )
is positive, zero, or negative. The function ψ \psi ψ is strictly decreasing:
ψ ( N + 1 ) − ψ ( N ) = 2 ( 1 + c ( N + 1 ) ) [ ( G N + 2 ( ρ ) − G N + 1 ( ρ ) ) − ( G N + 1 ( ρ ) − G N ( ρ ) ) ] < 0. \psi(N+1)-\psi(N)=2(1+c(N+1))\left[\left(G_{N+2}(\rho)-G_{N+1}(\rho)\right)-\left(G_{N+1}(\rho)-G_N(\rho)\right)\right]<0. ψ ( N + 1 ) − ψ ( N ) = 2 ( 1 + c ( N + 1 )) [ ( G N + 2 ( ρ ) − G N + 1 ( ρ ) ) − ( G N + 1 ( ρ ) − G N ( ρ ) ) ] < 0.
It is also negative for large N N N . Since ρ ( 1 − u ) / ( 1 − ρ u ) ≤ 1 \rho(1-u)/(1-\rho u)\le1 ρ ( 1 − u ) / ( 1 − ρ u ) ≤ 1 , Equation (C.17) gives G N + 1 ( ρ ) − G N ( ρ ) ≤ 1 / ( N + 1 ) G_{N+1}(\rho)-G_N(\rho)\le1/(N+1) G N + 1 ( ρ ) − G N ( ρ ) ≤ 1/ ( N + 1 ) . For ρ = 1 \rho=1 ρ = 1 , the first term of ψ ( N ) \psi(N) ψ ( N ) is therefore at most 2 ( 1 + c N ) / ( N + 1 ) ≤ 2 max { 1 , c } 2(1+cN)/(N+1)\le2\max\{1,c\} 2 ( 1 + c N ) / ( N + 1 ) ≤ 2 max { 1 , c } , while the second, c ( κ L + 2 ( 1 + 1 2 + ⋯ + 1 N ) ) c\left(\kappa^L+2(1+\frac{1}{2}+\cdots+\frac{1}{N})\right) c ( κ L + 2 ( 1 + 2 1 + ⋯ + N 1 ) ) by Proposition 4(ii), grows without bound. For ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) , ρ ( 1 − u ) / ( 1 − ρ u ) ≤ ρ ( 1 − u ) / ( 1 − ρ ) \rho(1-u)/(1-\rho u)\le\rho(1-u)/(1-\rho) ρ ( 1 − u ) / ( 1 − ρ u ) ≤ ρ ( 1 − u ) / ( 1 − ρ ) , so the first term is at most 2 ( 1 + c N ) ρ / ( ( 1 − ρ ) ( N + 1 ) ( N + 2 ) ) 2(1+cN)\rho/((1-\rho)(N+1)(N+2)) 2 ( 1 + c N ) ρ / (( 1 − ρ ) ( N + 1 ) ( N + 2 )) , which tends to zero, while the second is at least c κ L > 0 c\kappa^L>0 c κ L > 0 . Hence there is an integer N ˉ ≥ 0 \bar N\ge0 N ˉ ≥ 0 such that C ( N + 1 ) < C ( N ) C(N+1)<C(N) C ( N + 1 ) < C ( N ) for N < N ˉ N<\bar N N < N ˉ , C ( N ˉ + 1 ) ≥ C ( N ˉ ) C(\bar N+1)\ge C(\bar N) C ( N ˉ + 1 ) ≥ C ( N ˉ ) , and C ( N + 1 ) > C ( N ) C(N+1)>C(N) C ( N + 1 ) > C ( N ) for N > N ˉ N>\bar N N > N ˉ : the long-run cost first decreases and then increases in N N N . Its minimizers are N ˉ \bar N N ˉ , and also N ˉ + 1 \bar N+1 N ˉ + 1 when C ( N ˉ + 1 ) = C ( N ˉ ) C(\bar N+1)=C(\bar N) C ( N ˉ + 1 ) = C ( N ˉ ) .
(ii) For N ′ > N ≥ 0 N'>N\ge0 N ′ > N ≥ 0 ,
C ( N ′ ) C ( N ) = 1 + c N ′ 1 + c N ⋅ κ L + 2 G N ( ρ ) κ L + 2 G N ′ ( ρ ) . \frac{C(N')}{C(N)}=\frac{1+cN'}{1+cN}\cdot\frac{\kappa^L+2G_N(\rho)}{\kappa^L+2G_{N'}(\rho)}. C ( N ) C ( N ′ ) = 1 + c N 1 + c N ′ ⋅ κ L + 2 G N ′ ( ρ ) κ L + 2 G N ( ρ ) .
The first factor rises strictly with c c c , because its derivative in c c c has the sign of N ′ − N N'-N N ′ − N , and does not depend on λ \lambda λ or ρ \rho ρ . The second factor does not depend on c c c . It rises strictly with κ L = − 2 log ( 1 − λ ) \kappa^L=-2\log(1-\lambda) κ L = − 2 log ( 1 − λ ) , and so with λ \lambda λ , because G N ′ ( ρ ) > G N ( ρ ) G_{N'}(\rho)>G_N(\rho) G N ′ ( ρ ) > G N ( ρ ) by Proposition 4(i). It falls strictly with ρ \rho ρ . For N = 0 N=0 N = 0 , this follows from Proposition 4(i), because G 0 ( ρ ) = 0 G_0(\rho)=0 G 0 ( ρ ) = 0 . For N ≥ 1 N \ge1 N ≥ 1 , expanding 1 / ( 1 − ρ u ) = ∑ k ≥ 0 ( ρ u ) k 1/(1-\rho u)=\sum_{k\ge0}(\rho u)^k 1/ ( 1 − ρ u ) = ∑ k ≥ 0 ( ρ u ) k in Equation (C.8) and integrating term by term gives, for ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) ,
κ L + 2 G N ( ρ ) = ∑ k ≥ 0 ν k ( N ) ρ k , ν 0 ( N ) = κ L , ν k ( N ) = 2 N k ( N + k ) ( k ≥ 1 ) . \kappa^{\mathrm{L}}+2G_N(\rho)=\sum_{k\geq0}\nu_k(N)\rho^k,\qquad\nu_0(N)=\kappa^{\mathrm{L}},\qquad\nu_k(N)=\frac{2N}{k(N+k)}\quad(k\geq1). κ L + 2 G N ( ρ ) = k ≥ 0 ∑ ν k ( N ) ρ k , ν 0 ( N ) = κ L , ν k ( N ) = k ( N + k ) 2 N ( k ≥ 1 ) .
For N ′ > N ≥ 1 N'>N\geq1 N ′ > N ≥ 1 , the ratio ν k ( N ′ ) / ν k ( N ) \nu_k(N')/\nu_k(N) ν k ( N ′ ) / ν k ( N ) equals one for k = 0 k=0 k = 0 and N ′ ( N + k ) / ( N ( N ′ + k ) ) N'(N+k)/(N(N'+k)) N ′ ( N + k ) / ( N ( N ′ + k )) for k ≥ 1 k\geq1 k ≥ 1 , which exceeds one and rises with k k k . Lemma C.7 , with a k = ν k ( N ′ ) a_k=\nu_k(N') a k = ν k ( N ′ ) and b k = ν k ( N ) b_k=\nu_k(N) b k = ν k ( N ) , shows that ( κ L + 2 G N ′ ( ρ ) ) / ( κ L + 2 G N ( ρ ) ) (\kappa^{\mathrm{L}}+2G_{N'}(\rho))/(\kappa^{\mathrm{L}}+2G_N(\rho)) ( κ L + 2 G N ′ ( ρ )) / ( κ L + 2 G N ( ρ )) rises strictly with ρ \rho ρ on ( 0 , 1 ) (0,1) ( 0 , 1 ) ; since G N G_N G N and G N ′ G_{N'} G N ′ are continuous on ( 0 , 1 ] (0,1] ( 0 , 1 ] by Equation (C.8), it rises strictly on ( 0 , 1 ] (0,1] ( 0 , 1 ] .
Consider a change in one parameter that lowers C ( N ′ ) / C ( N ) C(N')/C(N) C ( N ′ ) / C ( N ) for every pair N ′ > N N'>N N ′ > N : a rise in ρ \rho ρ , or a fall in λ \lambda λ or in c c c . Let N 1 N_1 N 1 minimize C C C before the change and N 2 N_2 N 2 after it, and suppose that N 2 < N 1 N_2<N_1 N 2 < N 1 . Before the change, C ( N 1 ) / C ( N 2 ) ≤ 1 C(N_1)/C(N_2)\leq1 C ( N 1 ) / C ( N 2 ) ≤ 1 . After the change, C ( N 1 ) / C ( N 2 ) < 1 C(N_1)/C(N_2)<1 C ( N 1 ) / C ( N 2 ) < 1 , which contradicts the optimality of N 2 N_2 N 2 . Hence every minimizer after the change is at least as large as every minimizer before it, so N ∗ ( ρ , λ , c ) N^*(\rho,\lambda,c) N ∗ ( ρ , λ , c ) is nondecreasing in ρ \rho ρ and nonincreasing in λ \lambda λ and in $c.
Proofs for Section 7
Proof of Theorem 4. (i) Let q 0 ∈ ( 0 , 1 ) q_0\in(0,1) q 0 ∈ ( 0 , 1 ) . By Theorem 1(i), κ D = 2 Δ \kappa^{\mathrm{D}}=2\Delta κ D = 2Δ with probability one. By Theorem 2(i), κ L = − 2 log ( 1 − λ ) \kappa^{\mathrm{L}}=-2\log(1-\lambda) κ L = − 2 log ( 1 − λ ) , and Equation (16) is equivalent to − log ( 1 − λ ) > Δ -\log(1-\lambda)>\Delta − log ( 1 − λ ) > Δ , so κ L > κ D \kappa^{\mathrm{L}}>\kappa^{\mathrm{D}} κ L > κ D . By Theorem 3(i), κ A = κ L + 2 G N ( ρ ) \kappa^{\mathrm{A}}=\kappa^{\mathrm{L}}+2G_N(\rho) κ A = κ L + 2 G N ( ρ ) with probability one, and G N ( ρ ) > G 0 ( ρ ) = 0 G_N(\rho)>G_0(\rho)=0 G N ( ρ ) > G 0 ( ρ ) = 0 for N ≥ 1 N\geq1 N ≥ 1 and ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] by Proposition 4(i), so κ A > κ L \kappa^{\mathrm{A}}>\kappa^{\mathrm{L}} κ A > κ L
(ii) Let q 0 ∈ ( 0 , 1 ) q_0\in(0,1) q 0 ∈ ( 0 , 1 ) . By part (ii) of Theorems 1 to 3, the ratios E τ D ( ε , q 0 ) / log ( 1 / ε ) \mathbb{E}\tau^{\mathrm{D}}(\varepsilon,q_0)/\log(1/\varepsilon) E τ D ( ε , q 0 ) / log ( 1/ ε ) , E τ L ( ε , q 0 ) / log ( 1 / ε ) \mathbb{E}\tau^{\mathrm{L}}(\varepsilon,q_0)/\log(1/\varepsilon) E τ L ( ε , q 0 ) / log ( 1/ ε ) , and E τ A ( ε , q 0 ) / log ( 1 / ε ) \mathbb{E}\tau^{\mathrm{A}}(\varepsilon,q_0)/\log(1/\varepsilon) E τ A ( ε , q 0 ) / log ( 1/ ε ) tend to 1 / κ D 1/\kappa^{\mathrm{D}} 1/ κ D , 1 / κ L 1/\kappa^{\mathrm{L}} 1/ κ L , and 1 / κ A 1/\kappa^{\mathrm{A}} 1/ κ A as ε → 0 \varepsilon\to0 ε → 0 . By part (i), 1 / κ A < 1 / κ L < 1 / κ D 1/\kappa^{\mathrm{A}}<1/\kappa^{\mathrm{L}}<1/\kappa^{\mathrm{D}} 1/ κ A < 1/ κ L < 1/ κ D . Let δ \delta δ be half of the smaller of the gaps 1 / κ L − 1 / κ A 1/\kappa^{\mathrm{L}}-1/\kappa^{\mathrm{A}} 1/ κ L − 1/ κ A and 1 / κ D − 1 / κ L 1/\kappa^{\mathrm{D}}-1/\kappa^{\mathrm{L}} 1/ κ D − 1/ κ L . There is ε ˉ ∈ ( 0 , 1 ) \bar{\varepsilon}\in(0,1) ε ˉ ∈ ( 0 , 1 ) such that, for every ε ∈ ( 0 , ε ˉ ) \varepsilon\in(0,\bar{\varepsilon}) ε ∈ ( 0 , ε ˉ ) , each ratio lies within δ \delta δ of its limit, and multiplying by log ( 1 / ε ) > 0 \log(1/\varepsilon)>0 log ( 1/ ε ) > 0 gives Equation (17) .
Proofs for Section 8
Proof of Theorem 5. Let γ ≡ min { p o l d , 1 − p o l d , p n e w , 1 − p n e w , p ~ , 1 − p ~ } > 0 \gamma\equiv\min\{p_{\mathrm{old}},1-p_{\mathrm{old}},p_{\mathrm{new}},1-p_{\mathrm{new}},\tilde p,1-\tilde p\}>0 γ ≡ min { p old , 1 − p old , p new , 1 − p new , p ~ , 1 − p ~ } > 0 . The search, evaluation, and learning steps of Mechanism A ~ \tilde A A ~ are Equation (C.7) with p ^ = p ~ ≠ p o l d \hat p=\tilde p\ne p_{\mathrm{old}} p ^ = p ~ = p old . By Lemma C.5 , for every sequence of draws, f t A ~ f_t^{\tilde A} f t A ~ lies between p o l d p_{\mathrm{old}} p old and p ~ \tilde p p ~ , so in [ γ , 1 − γ ] [\gamma,1-\gamma] [ γ , 1 − γ ] , and
∣ f t A ~ − p ~ ∣ = ∣ p o l d − p ~ ∣ e − S t ≤ ( 1 − λ ) t ∣ p o l d − p ~ ∣ , (35) \left|f_t^{\tilde A}-\tilde p\right|=\left|p_{\mathrm{old}}-\tilde p\right|e^{-S_t}\leq(1-\lambda)^t\left|p_{\mathrm{old}}-\tilde p\right|, \tag*{(35)} f t A ~ − p ~ = ∣ p old − p ~ ∣ e − S t ≤ ( 1 − λ ) t ∣ p old − p ~ ∣ , (35)
and S t / t → κ L / 2 + G N ( ρ ) S_t/t\to\kappa^{\mathrm{L}}/2+G_N(\rho) S t / t → κ L /2 + G N ( ρ ) with probability one.
(i) Every x x x between f t A ~ f_t^{\tilde A} f t A ~ and p ~ \tilde p p ~ lies in [ γ , 1 − γ ] [\gamma,1-\gamma] [ γ , 1 − γ ] , where x ( 1 − x ) ≥ γ ( 1 − γ ) x(1-x)\geq\gamma(1-\gamma) x ( 1 − x ) ≥ γ ( 1 − γ ) . By Lemma C.1(b), R p ~ ( f t A ~ ) R_{\tilde p}(f_t^{\tilde A}) R p ~ ( f t A ~ ) lies between 2 ( f t A ~ − p ~ ) 2 2(f_t^{\tilde A}-\tilde p)^2 2 ( f t A ~ − p ~ ) 2 and ( f t A ~ − p ~ ) 2 / ( 2 γ ( 1 − γ ) ) (f_t^{\tilde A}-\tilde p)^2/(2\gamma(1-\gamma)) ( f t A ~ − p ~ ) 2 / ( 2 γ ( 1 − γ )) . By Equation (C.18), log R p ~ ( f t A ~ ) \log R_{\tilde p}(f_t^{\tilde A}) log R p ~ ( f t A ~ ) therefore differs from 2 log ∣ p o l d − p ~ ∣ − 2 S t 2\log|p_{\mathrm{old}}-\tilde p|-2S_t 2 log ∣ p old − p ~ ∣ − 2 S t by at most log ( 1 / ( 2 γ ( 1 − γ ) ) ) \log(1/(2\gamma(1-\gamma))) log ( 1/ ( 2 γ ( 1 − γ ))) , so − 1 t log R p ~ ( f t A ~ ) → κ L + 2 G N ( ρ ) -\frac{1}{t}\log R_{\tilde p}(f_t^{\tilde A})\to\kappa^{\mathrm{L}}+2G_N(\rho) − t 1 log R p ~ ( f t A ~ ) → κ L + 2 G N ( ρ ) with probability one.
(ii) By Equation (C.18), f t A ~ → p ~ f_t^{\tilde A}\to\tilde p f t A ~ → p ~ for every sequence of draws. The function R p n e w R_{p_{\mathrm{new}}} R p new is continuous on ( 0 , 1 ) (0,1) ( 0 , 1 ) , so R p n e w ( f t A ~ ) → R p n e w ( p ~ ) R_{p_{\mathrm{new}}}(f_t^{\tilde A})\to R_{p_{\mathrm{new}}}(\tilde p) R p new ( f t A ~ ) → R p new ( p ~ ) , which is positive by Proposition 2 because p ~ ≠ p n e w \tilde p\ne p_{\mathrm{new}} p ~ = p new . (iii) The selection step of Mechanism A ~ \tilde{A} A ~ is Equation (5) with p = p n e w p=p_{\mathrm{new}} p = p new , f 1 , t = p n e w f_{1,t}=p_{\mathrm{new}} f 1 , t = p new , and f 2 , t = f t A ~ f_{2,t}=f_t^{\tilde{A}} f 2 , t = f t A ~ . The behaviors f t A ~ f_t^{\tilde{A}} f t A ~ do not depend on the states, p n e w p_{\mathrm{new}} p new and every f t A ~ f_t^{\tilde{A}} f t A ~ lie in [ γ , 1 − γ ] [\gamma,1-\gamma] [ γ , 1 − γ ] , and ∑ t ≥ 0 ∣ f t A ~ − p ~ ∣ ≤ ∣ p o l d − p ~ ∣ / λ \sum_{t\geq0}|f_t^{\tilde{A}}-\tilde{p}|\leq|p_{\mathrm{old}}-\tilde{p}|/\lambda ∑ t ≥ 0 ∣ f t A ~ − p ~ ∣ ≤ ∣ p old − p ~ ∣/ λ by Equation (C.18). By Lemma C.3 (b), applied for every sequence of draws, z t ≡ log ( q t A ~ / ( 1 − q t A ~ ) ) z_t\equiv\log(q_t^{\tilde{A}}/(1-q_t^{\tilde{A}})) z t ≡ log ( q t A ~ / ( 1 − q t A ~ )) satisfies z t / t → R p n e w ( p ~ ) > 0 z_t/t\to\mathcal{R}_{p_{\mathrm{new}}}(\tilde{p})>0 z t / t → R p new ( p ~ ) > 0 with probability one. As in the proof of Theorem 1(i), q t A ~ → 1 q_t^{\tilde{A}}\to1 q t A ~ → 1 and 1 t log ( 1 − q t A ~ ) → − R p n e w ( p ~ ) \frac{1}{t}\log(1-q_t^{\tilde{A}})\to-\mathcal{R}_{p_{\mathrm{new}}}(\tilde{p}) t 1 log ( 1 − q t A ~ ) → − R p new ( p ~ ) . Since
f ˉ t A ~ − p n e w = ( 1 − q t A ~ ) ( f t A ~ − p n e w ) \bar{f}_t^{\tilde{A}}-p_{\mathrm{new}}=(1-q_t^{\tilde{A}})(f_t^{\tilde{A}}-p_{\mathrm{new}}) f ˉ t A ~ − p new = ( 1 − q t A ~ ) ( f t A ~ − p new )
and f t A ~ − p n e w → p ~ − p n e w ≠ 0 f_t^{\tilde{A}}-p_{\mathrm{new}}\to\tilde{p}-p_{\mathrm{new}}\ne0 f t A ~ − p new → p ~ − p new = 0 , it follows that f ˉ t A ~ → p n e w \bar{f}_t^{\tilde{A}}\to p_{\mathrm{new}} f ˉ t A ~ → p new and 1 t log ∣ f ˉ t A ~ − p n e w ∣ → − R p n e w ( p ~ ) \frac{1}{t}\log|\bar{f}_t^{\tilde{A}}-p_{\mathrm{new}}|\to-\mathcal{R}_{p_{\mathrm{new}}}(\tilde{p}) t 1 log ∣ f ˉ t A ~ − p new ∣ → − R p new ( p ~ ) . By Lemma C.1(c), log R p n e w ( f ˉ t A ~ ) − 2 log ∣ f ˉ t A ~ − p n e w ∣ \log\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}_t^{\tilde{A}})-2\log|\bar{f}_t^{\tilde{A}}-p_{\mathrm{new}}| log R p new ( f ˉ t A ~ ) − 2 log ∣ f ˉ t A ~ − p new ∣ converges to − log ( 2 p n e w ( 1 − p n e w ) ) -\log(2p_{\mathrm{new}}(1-p_{\mathrm{new}})) − log ( 2 p new ( 1 − p new )) , so
− 1 t log R p n e w ( f ˉ t A ~ ) → 2 R p n e w ( p ~ ) -\frac{1}{t}\log\mathcal{R}_{p_{\mathrm{new}}}(\bar{f}_t^{\tilde{A}})\to2\mathcal{R}_{p_{\mathrm{new}}}(\tilde{p}) − t 1 log R p new ( f ˉ t A ~ ) → 2 R p new ( p ~ )