THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department CONVERGENCE PROPERTIES OF A CLASS OF PROBABILISTIC ADAPTIVE SCHEMES CALLED SEQUENTIAL REPRODUCTIVE PLANS Nancy Martin July 1973 Technical Report No. 146 with assistance from National Science Foundation Grant No. GJ-443X to the Institute for Mathematical Studies in the Social Sciences Stanford University and by National Science Fotamtion Grant No. GJ-2g9m tX the Logic of Co s 6~oup University of lichign

ABSTRACT CONVERGENCE PROPERTIES OF A CLASS OF PROBABILISTIC ADAPTIVE SCHEMES CALLED SEQUENTIAL REPRODUCTIVE PLANS by Nancy Martin Chairman: John H. Holland A reproductive plan is a mathematical model describing certain aspects of the duplication and selection processes in natural genetic adaptation. These models occur in artificial genetics, which is the use of ideas from genetics to develop general problem solving techniques for computers. A reproductive plan is a sequential stochastic process involving n-tuples which correspond to chromosomes in genetics. The individual elements of the n-tuples, which correspond to genes, may be simple numeric constants or may be such complex structures as computer algorithms. The plan also involves a sequence of probability distributions defined over the n-tuples. At each step of the stochastic process, one of the n-tuples is selected using the current probability distribution. The "value" of the selected n-tuple is then obtained from an external function or subroutine. This value is then used to define a new probability distribution for the next step of the process. A particular reproductive plan is said to converge if the distributions developed at each step converge to a distribution which selects the most valuable n-tuple. We analyse the convergence properties of several subclasses of reproductive plans. We show that in a suitably restricted problem domain one subclass, SR1 plans, converges. We also show that the convergence is not fast enough to achieve finite loss.

By relating reproductive plans to a class of models used in mathematical psychology, linear additive models, we show that several subclasses of reproductive plans do not converge.

ACKNOWLEDGEMENTS I would like to express my deepest gratitude to John Holland for introducing me to the area of genetic adaptation, for many helpful and stimulating conversations on this work and for his encouragement, support and patience. Several times when I have been ready to leave academic work, Patrick Suppes not only encouraged me to continue but helped with financial assistance and exciting projects. He has been a great source of inspiration for many years and I will always be grateful. I would like to thank Joyce Friedman for her careful reading of this manuscript and her many useful suggestions. I am extremely grateful for the support and encouragement she has given me. I would also like to thank the other members of my reading committee, Bernard Zeigler, Robert Bjork and James Greeno for their helpful comments and suggestions. There are many other people who have contributed to the completion of this work. I would particularly like to thank Tom Cover, Mary Harris, and Leslie Hefner. Jan McDougall and Monna Whipp have done an excellent job typing the manuscript. Cleve Moler has contributed to my education and to the completion of this manuscript more than any other individual. I am grateful for the many happy hours we have spent studying and working together. His many suggestions have helped to make this manuscript more readable. To Cleve, Teresa, and Kathryn I am greatly indebted for their patience, understanding and love. This work was supported in part by National Science Foundation Grant No. GJ-443X to the Institute for Mathematical Studies in the Social ii

Sciences, Stanford University, and by National Science Foundation Grant No. GJ-29989X to the Logic of Computers Group, University of Michigan. 11i

TABLE OF CONTENTS Page CHAPTER 1 INTRODUCTION 1 ChAPTER 2 REPRODUCTIVE PLANS 6 CHAPTER 3 DETERMINISTIC PROBLEM BASES 16 CHAPTER 4 29 SECTION 1. The search for an arena 29 SECTION 2. The linear additive model 36 SECTION 3. Linear models and pure problem Bases 39 CHAPTER 5 CONCLUSIONS 46 APPENDIX A 48 REFERENCES 52 iv

CHAPTER I INTRODUCTION The Logic of Computers Group at The University of Michigan has been studying methods of applying the techniques of natural genetic adaptation to develop adaptive techniques for problem solving with computers. We will use the term artificial genetics to refer to this process. We give here a very brief description of the genetic approach to problem solving in order to demonstrate the origins of the adaptive procedures we have investigated. For a thorough introduction we recommend Holland [to be published]. Chapter 1 of Hollstien (1971) relates the artificial genetic approach to adaptive control processes. Chapter 1 of Cavicchio (1970) relates the artificial genetic approach to pattern recognition and problems in artificial intelligence. We separate the world of the adaptive process into two parts: the adaptive algorithm and the environment with which it must interact. If an algorithm is to be adaptive then something internal to the structure of the algorithm must change as time progresses. The first problem is to find an adequate method of representing that which will change. As in natural genetics, artificial genetics assumes that there is a set, t., of "chromosomes". Each chromosome or string A E.is an n-tuple, (a1,..,a ) where the ai can be simple constants or quite complex structures such as the instructions for a computer subroutine. The ai are referred to as genes. Hollstien (1971) has investigated the use of Gray codes (also known as reflected codes) and Hash codes to make the representation of information in the n-tuple more efficient. 1

2 We may view the problem of adaptation as a transformation problem: from a set of strings t obtain a new set of strings e<t+l by applying a set of operators based on some evaluation of the strings in'2t. We assume that external to the adaptive process there is an evaluation function that evaluates the elements of fit and that the results of this evaluation are available to the genetic process. In an artificial genetic adaptive scheme the operators are modeled after the natural genetic operators: duplication, crossover, inversion, mutation and dominance. In the approach taken by Holland (to be published), the process is divided into two stages. The duplication operator is applied to it to provide a new set't containing multiple copies of some of the strings of Jt. The number of copies made of a particular string depends on the evaluation of that string. So duplication is a copying process that does not alter the individual strings. In the second state of the process, the other operators are applied to the set't to form a new set of strings. Then the evaluation process is used to reduce the size of this set to form dI t+l' The crossover operator is a function which takes two strings as arguments and creates two new strings by interchanging genes of one string with the corresponding genes of the other string. For example if A = (al,...,a) and B = (b1... bn) then the result of a simple crossover operator might be the strings (a1,... *,ai,bi+l, *,bn) and (b",... b.,a,i.,al~- n).

3 The result of a "double" crossover operator might be (al,... *aibi+l,...,bk,ak+l,...,an) and (bl""'bi'ai+l""'ak'b k+l..'bbn). The inversion operator is a function of a single string which reverses the order of some segment of the string. For example, the result of applying an inversion operator to string A above might be the string (al,.,aaiak, ak _l,...,ai+ laak+l,,a-an). The mutation operator makes random changes in the genes. The dominance operator is only applicable when the chromosomes have a more specific structure. Essentially, it chooses which copy of a gene will be effective if there is more than one representation for the same gene in the string. The mutation, crossover and inversion operators can also be applied at the gene level to change the structure of the individual a.'s. A review of some of the algebraic aspects of these operators is presented in Foo and Bosworth (1972). Experimental work with artificial genetic adaptation has been carried out by Hollstien (1971), Cavicchio (1970), Bosworth, Foo and Zeigler (1972) and Dan Frantz (1972). Holland began the theoretical investigation by analyzing the duplication phase of the process in (1969) and (1970). The present work is limited to this first phase of the adaptive scheme. In order to capture the notion of duplication theoretically, a new algorithm called a Reproductive Plan was developed which did not use the other operators. It was intended that this algorithm could act as a driver program for the total genetic scheme. A Reproductive Plan is a sequential stochastic process. If we view adaptation as a decision theory problem, then we must decide at

4 each time step which elements of ctto choose. The problem is to find a suitable process to maximize the sum of all the outcomes or to find a process that eventually only chooses the "best" element of T., according to some measure of "best". One method of making this decision is to have a probability vector over the space edwhich changes with experience. There are many methods, both linear and nonlinear for changing the values of the probability vector according to past performances. Many of these methods have been explored using different terminology by mathematical psychologists in searching for a model of behavior. While we are not interested in modeling any actual observed behavior, we are interested in taking advantage of the analysis that has been made and extending it to our particular requirements. Shapiro and Narendra (1969) have compared the performance of several mathematical psychology models in the problem of function optimization with noise. Norman (1970) has done extensive work in analyzing a model which we show is very close to the reproductive plans of Holland. Non-probabilistic methods of choosing among the elements of eXl have also been studied. A special problem of the type we are considering is called the n-armed bandit problem. This problem is generally stated as follows: we are given n coins with unknown probabilities Pl1"..pn of heads. At each time step we are to choose which coin to toss. The objective is to find a sequential decision procedure that maximizes the limiting proportion of heads. Robbins (1952) was one of the first statisticians to examine the problem of sequential testing. He developed a successful rule for the case n = 2 which used the sample mean of the previous t tosses to choose the coin for the (t+l)st toss. The rule included a provision that prevented a coin from only being tested a

finite number of times. Later Robbins (1956) restated the problem allowing only a fixed number of previous tosses to be used in the decision making process. This problem is referred to as the bandit problem with finite memory. The exact interpretation of the term finite memory has been discussed in the literature and related to automata theory. For example see Cover (1969) and Hellman and Cover (1970, 1971). In the present work we develop the conditions for convergence of reproductive plans and relate this to the models of mathematical psychology and statistical decision theory.

CHAPTER 2 REPRODUCTIVE PLANS In this chapter we define a class of algorithms for adaptation similar to those developed by Holland (1970). This class of algorithms treats adaptation as a decision theory problem. There is a set of possible strategies and a probability vector over the strategies. There is also an evaluation function which measures the "worth" of a strategy at a particular time. A procedure sequentially chooses a strategy according to the probability vector. The procedure does not have direct access to the evaluation function but receives the resulting value of the function applied to the strategy choosen. This value is used to update the probability vector for the next choice. The object is to have the probability of the "best" strategy in S approach one as the number of trials increases. If a procedure is such that the probability of choosing any particular strategy in S goes to one with the number of trials, we say the procedure converges to that strategy. We now give definitions to make these notions precise. Definition 2.1: <A,],S> is a problem basis where A is a set of possible or admissible structures, 1 is a function that assigns to each structure in A a random variable. We restrict the choice to the set of finite real random variables whose moment generating functions exist, S is a set of strategies for choosing structures from the space A. A strategy in S is a method for determining a trajectory or set of trajectories through the space A. 6

7 Example 2.2: In a zero-sum, two person game, let the structures of A be the pure strategies for player one, IAI = M, M T = {(Pl"''* PM) 0 < Pi - 1, i=lPi = 1}, let f:S - T be 1-1, onto and for s c S, s chooses structure a. of A with probability Pi where Pi is 1 1i the ith component of the probability vector f(s). Note that in this example the word "strategy" is being used in two senses: first in its usual game theoretic sense and second to refer to elements of S which are "strategies for choosing strategies". For a E A, the random variable ii(a) would be the "payoff" function of a. If we assume that player two always uses the same mixed strategy, then i(a) is a simple random variable as in Definition 2.1 and <A,P,S> is a problem basis. However, if player two changes his strategy with time i(a) no longer satisfies Definition 2.1. Definition 2.3: A problem basis <A,i,S> is deterministic if for each a C A, P (a) is a finite constant (hence its variance is zero), and the strategies s ~ S are not probabilistic. Example 2.4: If the structures in the set A are vectors in n-space, then any one of the standard function maximization algorithms of numerical analysis would be a nonprobabilistic strategy for determining a new structure of A given one or more "previous'' structures and their function values i(ai). A collection of such algorithms could be the set S in a deterministic problem basis. Definition 2.5: A strategy s ~ S is a pure strategy if s always selects the same element of A. Definition 2.6: A problem basis <A,u,S> is pure if S is a set of pure strategies and the variances of the random variables u(a), a ~ A, are nonzero.

8 The problem of maximizing a real valued function defined on a finite set of points where there is random noise in the function evaluation can be considered a pure problem basis. Here A = {al,...,an is a set of n points on the real line, p(ai), i = 1,...,n, is uniformly distributed with mean Pi in the interval [pi-2,pi+2] and S is the set of pure strategies such that there is one and only one strategy in S for each element of A. This problem was discussed by Shapiro and Narendra (1969). The n-armed bandit problem is an example of a pure problem basis with A the set of n arms, 1 with probability Pi v (ai ) = 1ii I0 with probability 1-pi. Again, S is the set of pure strategies such that there is one and only one strategy in S for each element of A. Definition 2.7: A sequential adaptive scheme, SAS, over the problem basis <A,a,S> is an algorithm for choosing 1. An initial starting structure of A denoted A0 2. At each time step, t, a strategy from S to be used to obtain a new structure. Definition 2.8: A probabilistic sequential adaptive scheme, PSAS, is an SAS with the strategy at time t chosen according to a probability distribution over S. Definition 2.9: A PSAS over a problem basis <A,Hi,S> is said to converge to the set HCS if lim z P = 1 where P is the probability of t- choosingEH ss a t time t choosing strategy s at time t.

9 We will use the following notation: t time variable. N(t) the number of distinct strategies an SAS has selected prior to time t. s. the jth distinct strategy selected by an SAS. S(t) the set of distinct strategies selected prior to time t. S(t) = s1,s 2,'. SN(t) }. tj the time strategy sj is first selected. As(k) the structure that would result if strategy s were being selected by an SAS for the kth time. Pt the probability of selecting strategy s at time t. PO t the probability of selecting a strategy from S-S(t) at time t. w(s,t) the number of times strategy s has been selected up to and including time t. an abbreviation for i(As(w(s,t))), the random variable resulting from the choice of structure made by strategy s at time t. PS(t) the probability distribution by which a strategy may be selected from S-S(t) at time t. P is an initial probability distribution over S. I SI cardinality of the set S. a the mean of the distribution v (a) for a c A. t* is the lub Pa where the lub is over the set {al for some strategy s c S, A (t) = a}. Us,t is Ust if strategy s is actually selected at time t and 1w(qt) if strategy s is not selected but strategy q is selected at time t.

10 In all of the above notation, if the strategy referred to is in the set S(t), we often use only the subscript. For example we abbreviate As (k) to Aj(k), w(sj t) to w(j,t), and p to Pj, t We now have enough notation to define a general sequential reproductive plan. There are two calculations which are external to the procedure. The first is the calculation which determines, given the strategy selected by the plan, which structure in A is choosen. In a pure problem basis this calculation always results in the same structure for a given strategy. The second is the calculation of the "payoff" of the structure. These calculations are represented by the functions STRUCTURE and PAYOFF in step 2 of the procedure. The exact method of selecting new strategies from S-S(t) is not specified in the SRP procedure. We put the following restrictions on the function FIND of step 2 of the procedure. The original probability distribution P over S must be modified to be a distribution PS(t) over S-S(t). We will assume that for ISt finite, if P0(s) > 0 for a particular strategy s and if s ~ S(t), then P(t) (s) > P0(s). For IS[ infinite, if P0(W) > 0 for a particular subset WCS and if WQnS(t) = 0, then PS(t) (W) > P0(W). Our first procedure is a general form which will be altered in subsequent definitions by changing the variables v and v* and by altering the calculation in step 3.10. Definition 2.10: SRP, a sequential reproductive plan, is a PSAS over a problem basis <A,va,S> where: 1. The values assumed by the random variables are in an interval (r1,r2) where r1,r2 are finite real numbers.

11 2. The procedure requires the following functions: 2.1 SELECT(PN(t),j) which assigns a value to j according to the probability vector PN(t)' That is, if PN(t) = (POPl",'. PN(t)) then j is assigned the value i with probability Pi. 2.2 FIND(P0,S(t),sj) which chooses a new strategy from S-S(t) according to the restrictions above and labels it s. 2.3 STRUCTURE(sj,Aj (t) A0) which applies strategy sj to obtain a new structure Aj (t). 2.4 PAYOFF(A.j(t),v,v*) which uses Aj(t) to obtain values for v and v*. 3. The operation of the procedure is as follows: 3.1 Choose 0 > 0, kl > rl+I, k2 > 0 P0. 3.2 Choose at random an initial structure A0. 3.3 Set N(1) = 0, t = 0, S(t) = 0. 3.4 Set t = t+l. 3.5 Calculate PN(t = (P P ) by 3.5.1 [N(t)+l]-(1+0) if N(t)+l < ISI P = P0,t 0 otherwise 3.5.2 If N(t) > 0 for 1 $ i < N(t) calculate: Prod. Pi = (1-Po, ),N(t-1 Z Prodh t 1 h=l,t1 3.6 SELECT(PN~t),j)

12 3.7 If j is 0 then Set N(t+l) = N(t)+l, j = N(t+l), FIND(P0,S(t ), P= S(t) U {s.}, Prod. = Pj,t-l j,t. otherwise set N(t+l) = N(t), S(t+l) = S(t). 3.8 STRUCTURE(sj,Aj (t),A0). 3.9 PAYOFF(Aj (t),v,*). 3.10 Calculate: for 1 < i < N(t+l) 3.10.1 ) v for i = j v* for i ~ j 3.10.2 k2 Prod = Prodtl *(i+k ) i,t i,t-l1 1' 3.11 GOTO step 3.4. Definition 2.11: An SRla is an SRP where the value returned by PAYOFF for v is.jt and the value for v* is (j An SRlb is an SRP where the value returned by PAYOFF for v is jtt and the value for v* is max(p t)'~ V t) ) An SR1 is an SRla or an SRlb. maw(j.9t,t The definition of an SR1 differs in several respects from that of Holland (1970). We have allowed the,u(a) to be random variables. In the original development j was a single valued function from A to a finite subset of the reals (rl,r2). This restriction does not allow the application of the algorithm to such problems as the n-armed bandit problem. In the Holland paper the notion of a set of environments & was included. However, since all of the theoretical work was done with respect to a fixed element E c 6, this aspect of the plan has been discarded. The notion of environment could easily be incorporated in the functions 1u since they are external to the algorithm, or in the structural description of the elements of A. The calculation of the probabilities P. in the 1i,t

13 SR1 algorithm can be expressed as: t-l k Pi,tit't. (i,t,+k) 2 Equation 2.12: P. = (l-Pot) N(t) t-l k h=lh'thtot (eh,t,+kl) 2 h=l h.th t' = t This is similar to the calculation in the 1970 paper except for the upper limit of the products in the numerator and denominator. In the 1970 paper this limit is t, in equation 2.12 the limit is t-l. We cannot use.it until it has been calculated and in our algorithm this calculation comes in step 3.10 and the calculation of P. in step 3.5.'i,t The values of the P0,t determine how often a new strategy is to be tried. One of the weaknesses of this algorithm is that P9 t is not dependent on the performance of the strategies that have already been used. It would be preferable to have P,t be relatively large if the strategies used so far were not performing well, small if they were doing well. However, this definition does insure that with probability 1, when ISI is finite all of the strategies will be tried by some Tf < a. When |SI is infinite, there is no finite time after which no new plans are tried. We observe from equation 2.12 that for an SR1, if <A,ui,S> is deterministic, Pjt cannot increase as a result of using strategy j, except of course, the first time it is used. Also, if the jth strategy is used at time t, ijt = w(jt)' and strategy j has been used before, the probabilities Pi t do not change. The purpose of using such a method to change the probability vector over S(t) is to allow the vector to be more responsive to the performance of the strategy over time. We wish to avoid converging to false strategies due to their early behavior. However, it is exactly this property which makes it impossible for the

14 algorithm to have all of the convergence properties claimed in Holland (1970). Let us now consider a modified form of Equation 2.12 for an SRla procedure for finite S. We know that after some time Tf, each of the strategies will have been used at least once. We also note that the P. and Ph in the numerator and denominator of Equation 2.12 are 1,ti,th constant factors that do not influence the convergence properties of the Pj.t as t -+ c In fact, they reinforce the bias of the original distribution P0 over S. If this distribution is not a good measure of the value of the strategies, the Pj in the formula could slow down convergence but never prevent it. If we neglect these factors, and let -jt = (,$t+k )"2 we have: Equation 2.13: for t > Tf+l t-l nI (j n=t.,n Pjt N(t) t-l h=l n=th h,n * +)k2 Let i be the strategy actually used at time t and = (i t+k t w(it)+ Then Equation 2.13 can be expressed as: Equation 2.14: for t > T if i = j: j,t 3,t-l1 - t-l~t if i # j: j,t j,t-l 1 + Pi't-i* 1 ))

15 Equation 2.13 has a familiar form. With different interpretations of the a, this is the form of the Beta Model of mathematical psychology. This model has been studied extensively by Luce (1959), Lamperti and Suppes (1960), Lamperti (1960), Norman (1970) and others. Although their terminology and interpretations of the model differ from those of Holland, the mathematical analysis applies to both. The Holland work claims that under certain restrictions of the problem basis <A,1,S> the model not only converges but converges in such a special way that "bad" strategies are used only a finite number of times. However, the studies by the mathematical psychologists show that the Beta model (without Holland's restrictions) does not always converge. We will show that under restrictions similar to Holland's the SR1 plan does converge, but riot as strongly as he claimed. Then we will examine convergence under other restrictions and relate our results to those of Norman (1970).

CHAPTER 3 DETERMINISTIC PROBLEM BASES This chapter examines the convergence properties of the SRi algorithm over deterministic problem bases. Definition 3.1: A strategy in a deterministic problem basis is optimal iff 3T - p (As(t)) = * for t > T. Definition 3.2: A strategy s in a deterministic problem basis is asymptoticaZZy optimal iff z [p - p(AS(t))] <. t=l t If s is optimal, s is asymptotically optimal. Definition 3.3: An arena is a deterministic problem basis <A,p,S> such that there exists a set HCS, P0(H) > 0 and glb p(As(t)) > P* - Xt where Z Xt = NE < o t=l It is not hard to show that <A,p,S> is an arena if and only if S contains asymptotically optimal strategies with nonzero initial probability. Definition 3.4: SE, the arena set for the arena <A,p,S>, is the set of all asymptotically optimal strategies. To avoid trivial situations we henceforth assume SE is a proper subset of S. At this point it would appear that if our problem basis is an arena then the optimum algorithm in searching S would converge to the arena set. Because of the lack of limitation on the sequence ~ this is not necessarily the case. As presently defined, pt is the bet' ta n igesrtg ol oi sdttms t best that any single strategy could do if used t times. It is not necessarily the optimum value that any algorithm could achieve at time 16

17 t. It is possible that a PSAS which selects an element of S according to a fixed vector (Pl,P2,...,p) with Pi Z 0 for at least one i not in the arena set could have a higher payoff than a similar PSAS with Pi = 0 for all strategies not in the arena set. We give an example where this is the case. Example 3.5: Let strategy 1 have payoff 100/k the kth time it is used, strategy 2 have payoff 99/k the kth time it is used. Then vt is 100/t and we have an arena set consisting of strategy 1. However, a PSAS that uses strategy 1 all of the time will not have as good a payoff as one that uses an appropriate mix of the strategies 1 and 2. Let p be the probability of choosing strategy 1, l-p the probability of choosing strategy 2, where p is fixed for all t and 1 > p > 1-p. Then if M is the number of choices of strategy 1 in N trials and N > M >.01N, the payoff would be M N-M N Z 100/k + z 99/k > z 100/k. k=l k=l k=l For p > l-p, the expected payoff of the mixed strategy is greater than the payoff of the arena set. To have strategies in a deterministic problem basis have the payoffs indicated, both the set A and the strategies would be quite unnatural. However, such problem bases are not eliminated by the definition of an arena. Consequently we introduce the following notion. Definition 3.6: An arena <A,,',S> is a restricted arena if there exists a time T such that no PSAS over <A,vp,S> can obtain a payoff at time t > T higher than pt. The rest of this section develops the results necessary to show that in fact the losses associated with an SR1 algorithm even over a

18 restricted arena cannot be finite. Definition 3.7: The absolute loss of strategy s is 00 AL = t* - * (As(t)). 5 t~lt If a strategy s is in the arena set for <A,i,S> then ALS is finite, otherwise ALs is infinite. Definition 3.8: The actual Zoss of the strategy s during any particular use of an algorithm is D -(*) s,t (w(i,t) - s,t) where si is the strategy selected at time t. The accumulated actual loss 00 is D = D s t=l s,t According to Definition 3.8, a strategy s has zero loss at time t if it is not selected at time t. Therefore when we speak of the actual loss incurred by a particular strategy, we only mean the loss resulting from the actual selection of that strategy by an algorithm. Lemma 3.9: Let SE be the arena set for an SR1 over a restricted arena <A,p,S>. If s ~ SE, then the accumulated actual loss Ds is finite. If s' I SE and s' is, with probability 1, selected infinitely often, then the accumulated actual loss, Dc,, is infinite with probability 1. Proof: The first part of the lemma follows directly from the definitions of an arena set and of asymptotically optimal strategies. For the second part observe that: 00 oo D = Z * (11 = - s' t=l w(i,t) st k=l w(s'nk) s' where nk is the infinite set of indices where strategy s is actually

19 selected. But w(s',nk) = k so Ps',nk p(A (W(s,n))) (As(k)) and 00 sD -k=l k (,(k))) = ALs The definition of actual loss incorporates many of the ideas expressed in Holland (1970). A strategy is to be measured against how well other strategies would have done if they had been used the same number of times. However, there is no guarantee that the actual loss directly represents the loss of using a strategy under SR1 compared with some optimal scheme. Definition 3.10: The Zoss incurred by an SRl algorithm over a finite modified arena is o SI D = E (P * s ) t=l s=l t st Lemma 3.11: The loss of an SR1 algorithm over a finite restricted arena is infinite if the total accumulated actual loss over all strategies is Isl infinite. That is D = co if Z D = O. s=l ~ Proof: There exists T; for t > T, s C S, by Definition 3.6 > w t) where si is used at time t. t w (i,t) t - s,t = w(i,t) Ps,t 00 0o g g (vt > Z Z C* t=T sES, s t t=T sES w(i,t) - s,t) The left hand side is D-K, the right hand side is Z Ds-K' where sES K and K' are finite constants. Therefore D-K > Z D -K' = co = sS S and D = cO.

20 From Lemma 3.9 the accumulated actual loss is not finite if some strategy s' not in SE is used infinitely often. We now explore the conditions under which this happens. Definition 3;12: H is a Zimiting set of a PSAS over the arena <A,P,S> if HCS and there is some time T such that for t > T, with probability 1, only strategies from the set H are selected for use. If S is finite and there are no proper subsets, HCS, such that H is a limiting set and P0(H) < 1, then each of the strategies in S with nonzero initial probability must be used infinitely often. We want to develop conditions under which a limiting set does not exist. Let Q be a PSAS over <A,p,S>, HCS and {Xi.} a sequence of random variables defined by 1 if a strategy in H is selected by Q at time i X. = I,1:O0 otherwise. We can now represent the choices of strategies of Q as an infinite vector of the Xi. The space of all 0-1 valued infinite vectors is then the underlying space representing all possible sequences of choices by Q. The probability distribution over these vectors is dependent on the vectors PN(t) = {POt P P }. In order to have a limiting set, we are interested in those vectors of the X. which from some point on have entries of 1 only. Let Bm = {(X1,X2,.. XX...)I Xj = 1 for all j > m} and B = lim B m mIf the probability of the set B is, then H is not a limiting set for If the probability of the set B is 0, then H is not a limiting set for

21 Q. Let AP = P(X m+ = 1IXi * X m_ =-l' 1) - (X m= l1X1..-x. m -) Then AP is the increment in the probability of choosing an element m of the set H given that an element in H was chosen at the previous time step, and irrespective of the other past choices. Intuitively, if AP is negative, one would not expect H to be a limiting set. m This is in fact the case. Theorem 3.13: Let Q be a PSAS over <A,I,S>, HCS and Xi, Bm, and B defined as above relative to H and Q. If there is a time T such that, for m > T, AP < 0, and if P(X = 1) < 1 for all finite m then P(B) = 0 m m and H is not a limiting set for Q. Proof: for m > T, P(B ) = lim P(Xi = 1, m < i < niX1,..,Xm_l) m i=' no lim P(X = 1X1l..,X m1 1, =X 1,...,X = 1) n-o ~P(X lX = 1X1. X mXn_2 = 1).*P(X, = 1lix x Xm-1) Since AP < 0, P(Bm) < lim [P(X = liXi, X n-m- 1 no = 0 So, for arbitrary m > T, P(B ) = 0. But B = lim B and the B are a sequence of increasing events. m m m-fly Therefore, P(B) = lim P(Bm)[see 1.3.1 Neveu (1965)1 so P(B) = 0. Since P(B) is 0, with probability 1 H is not a limiting set of Q. Lemma 3.14: Let Q be an SR1 algorithm over a restricted arena <A,v,S> with finite S. Let H be the arena set of S, H # S and P (H) # 1. Then

22 (a) P(X = 1) < 1 and (b) AP < 0 for m > Tf. Proof: (a) If P(Xt = 1) = 1 then, letting Pt(H) denote the probability of choosing an element of H at t, Pt(H) = 1. Therefore P (S-H) = 0. 1. If one of the strategies in S-H, say sj, has been used at least once, Pt(S-H) > Pj,t But Pj. 0 if CN(t).l f 1 since the pj t > 1. Since strategy s.j has been used once prior to t, CN(t)+l # 1 by definition. Therefore Pt(S-H) # 0. 2. If none of the strategies in S-H have been used then Pt(S-H) = PO,t PS(t) (S-H). But PS(t) (S-H) > P (S-H) > 0. P,t = 0 only when all strategies have been used. This would imply that H = S and our assumption is that H J S. Therefore Pt(S-H) $ 0 and P(Xt = 1) < 1. (b) Let Tf be the time by which with probability 1 each strategy in S has been used at least once. If strategy s.i H is used at time m > Tf + 1 then for j # i from Equation 2.14 we have, P+ = Pj,.61 where 6 = j,m-l ],m 1 1 - - i,m _ Pim+l =P..6 where = iJm1+l 1,m 2 2 -i i'mm i,m since 61 > 1, 0 < 62 < 1, P. < P. P. > P.,m j,m' i,m+l -,m Let AP. = P. -P AP. = P. -P, jm,m+l j,m',m,m+l z,m Then AP. > 0, AP <O 0

23 Z AP = AP +AP. + E HAP = 0 skeS k,m s.fH j, im skiS-H k,m S AP jm sk -H k,m- Therefore, for arbitrary si c H used at time m AP = E AP m s.%H j,m < 0 With probability 1, Tf is finite and therefore, AP < 0 for all f M m > Tf, Tf finite. Corollary 3.15: The arena set SE of a finite arena <A,ui,S> cannot be a limiting set for an SR1. In fact, no HCS such that P0(H) < 1 can be a limiting set and each strategy in S with nonzero initial probability P0(s) will be used infinitely often by the SR1 algorithm. We now show that the loss incurred by an SR1 algorithm over a finite restricted deterministic arena is infinite. Theorem 3.16: With probability 1, the loss incurred by an SRI algorithm over a finite restricted arena <A,U,S> is not finite. That is with probability 1, Isl Z D = o s=l and therefore D = 0O Proof: By Corollary 3.15, the arena set SE of <A,p,S> is not a limiting set. Therefore with probability 1, at least one strategy s' 4 SE is used infinitely often. Therefore Lemma 3.9 shows that for s', with

24 probability 1, 00 Z D s',t t=l since. Ds,t = w(i p ) > 0 for all s,t,i St w(it) S(,t = Isl00 IsI 0 =D = Z D > Z D =00 =l tl s=l s,t t=l' t Isl By Lemma 3.11, Z D = m => D =. s=l We have shown now that an SR1 over a restricted deterministic arena will, with probability 1, not achieve fifitte losses. However, the theorem in Holland (1970) is interpreted as showing that a reproductive plan would, with probability 1, achieve finite losses. Let us define the "expected" loss of the algorithm to be: 3.17 EL " N (t) 3.17 t t kl lk,t k,t 0t S where X S(t) is the expected payoff resulting from strategies in S-S(t) and the Pk t are defined as in 2.10. Now Holland's result in our notation states: Proposition 3.18: (Holland) An SR1 algorithm over a restricted arena <A,p,S> will, with probability 1, satisfy the following criteria: T (1) lim E ELt < o if ISI=is finite; T-4o t=l T T T (2) lim ( Z * - Z ELt)/ Z p* = 1 otherwise. T+oo t=l t=l t=l t This proposition would appear to conflict with our results. However, this expression for expected loss, ELt is less than the loss the algorithm would actually receive at any time t. That is for ISI

25 finite and t > Tf 11S ELt * - t p = - Pt. )P strategy s. used t k k,t t j,t) j,t trategy sj used at time t. < vt - 1Jt t jt Therefore, showing that Z ELt is finite in no way implies that any t=l actual use of the algorithm will achieve finite losses, and ELt is not an adequate expression for the expected loss of the algorithm. We could change the definition of an SR1 algorithm so that the strategies in S were used in a more parallel fashion. That is, the strategy chosen at time t actually would calculate the element of A it would calculate if it were being used for the t th time. If we define (A k (t)) if sk is used at time t Yk,t ip* potherwise t Yk,t represents the evaluation a strategy would receive if it had actually been used t times, whether it had or not. This would be possible if the strategies in S did not use the "feedback" evaluation, p(As(t-l)), of the element of A selected at time t-l to decide which element of A to select at time t. Definition 3.19: An SR2 is an SRP where the function PAYOFF returns the value ~p(Aj(t)) for v and pt1 21 t The expected loss defined analogous to 3.17, N(t) 3.20 EL' = k-l YkstPk,,t S-S(t) is still less than the actual loss on any particular use of the algorithm. However, we cannot guarantee that the loss would be

26 infinite. Even though each plan will be used infinitely often, it is possible that for some s' j SE, {k n the infinite set of times at which s' is used, ( s k) (p - p(As'(kn)) < 00 n=l kn' lkn n-1 kn 5 n If this happens for all strategies in S, then the loss will be finite. We see immediately, however, that the loss is not finite if even one strategy in S has an evaluation strictly bounded away from t' We finish this chapter by demonstrating that under the restrictions we have been imposing, an SR1 algorithm will converge, with probability 1, to a subset of the arena set of S. Theorem 3.21: An SR1 over a finite, restricted deterministic arena <A,pS> converges with probability 1 to a set HqSE, where S is the arena set of S. That is, with probability 1, lim z P. = 1. J,t t-+o s.EH Proof: By Corollary 3.15, every strategy in S with a nonzero initial probability must be used infinitely often by the SR1 algorithm. Consider the products t-l v'. t-l j1 +k J w -n= n n tj w(k,n)+k n L if z $ j, the numerator and the denominator are equal. If mq, q=l,...,M, are the times at which k = j; that is, the times at

27 which strategy j is actually used, then w(j,mq) = q and I (Aj (q))+k Ej,t-l 1 q=l +k M (A (q))+k 1 Then lim. = lim.*+k t- ]jt- 1 q +kl 1 } (A(q)+k (A (q)) Now. =1 - N'q+k1 1+k oo00 I* -(A (q)) for s. E S < [p*(A(q)))] < E q=l Aq=l q l q 1 0 *-}(A(q)) 1 for s g SE q (A )) q=l q A1 2 +k1 q=l q We now recall the following basic result [Theorem 7, page 96 of Knopp (1956)]: A product of the form E (l-av), with 0 < av < 1, is convergent v=l - 00 (to a nonzero value) if, and only if, Z av converges. v=l Applying this we find that M (A (q))+k1 (a) for s. c SE lim H. -ti- N - > =0 +k E jOt -1 qlk: M i(A.(q))+kl (b) for s. / S lim E. = lim = 0 J E J9t- 1 >.m q= Pq+k t-j B+~ qt M qkl tj 1. O. t* n-1 u j,t -1 Now lim P. = lim n t- o j t t IS I tQ 1=l O,t n=l n,t-l

28 The denominator is always nonzero since we are in an arena and SE is not empty. from (b) if s SE lim Pjt 0 P N o,t. ~,j n=l P from (a) if sj ~ SE lim Pt t j REt N,tll- 1 Bt n With probability 1, the times t are finite for those Z E HCSE such that P(Z) > 0 and therefore lim Pj. # 0. t-.oo Therefore, lim Z P. 1. t-m jFSE jt Now we have shown that an SRl algorithm converges to a set of good strategies in a very restricted problem basis. However, the proof of Theorem 3.20 does not generalize to a problem basis that is not an arena. This is obvious because if <A,P,S> is not an arena, we cannot guarantee the convergence for any of the Ejct. The proof also assumes that i'> vi(Aj(t)). This assumption is not always justified in a nondeterministic problem basis.

CHAPTER 4 PURE PROBLEM BASES Section I: The Search for an Arena Let us now consider a pure problem basis, <A,,S>, where S is a set of pure strategies and the variances of the random variables v(a), a C A are non-zero. We suppose there is a one-to-one, onto mapping between A and S. We will use pS for pa, the mean of the function i(a). We will denote i (a) by i. We note that = lub ps is not dependent sES on the time variable since we are dealing with pure strategies in a nonvariable problem basis. Let us propose some definitions for asymptotically optimal strategies in this basis. If we can find such definitions we can then define an arena and an arena set over a pure problem basis similar to Definitions 3.3 and 3.4 for a deterministic problem basis. If not, we must find other ways to explore the convergence of SR type algorithms over pure problem bases. The two most obvious candidates for such a definition are: A. A strategy s c S in a pure problem basis <A,p,S> is asymptotically n optimal if I lim Z ( S*-s t) < +o a.s. n-*+ t1 s,t B. A strategy s c S in a pure problem basis <A,ip,S> is n asymptotically optimal if |lim Z (v* S < a.s n-+oo t= where vt = max (v,t' ) t SC's t' If we accept either of these definitions, there are no asymptotically optimal strategies in a pure problem basis. We prove this statement in the following theorems. 29

30 Lemma 4.1: Let {Yt} be a sequence of independent identically distributed real random variables, then a. If 3 E > 0, 6 > 0, N such that for all t > N, P(Yt > E) > 6, n then lim Z Y a.s. does not exist. n-~ t=l b. If 3 C < 0, 6 > 0, N such that for all t > N, P(Yt < s) > 6, n then lim Z Y a.s. does not exist. n-+00 n-*) t=l t Proof: (a) from the hypothesis Z P(Y > s) = +. Since the Yt are t=l independent identically distributed real random variables (iidrrv), the Borel-Cantelli theorem tells us that with probability 1, Yt > infinitely often. Therefore the terms of the sequence {Yt } do not go to zero and n the lim E Y. a.s. does not exist. The proof of part b is similar. n-o t=l Theorem 4.2: There are no strategies in a pure problem basis which are asymptotically optimal according to definition A. Proof: Let Ys t = ( *-v1 t). Then E[Yt] = > O. VAR[Y] = VAR ] > C s,t sYt t s and the Y are iidrrv. Therefore, there is an e, 6 and an N satisfying s,t part 1 of Lemma 4.1 and the theorem follows immediately. Theorem 4.3: There are no strategies in a pure problem basis which are asymptotically optimal according to definition B. Proof: Let Y = (v By definition of, Y > 0. Since s,t t- st' s,t the Y are iidrrv and VAR[ps] = 6 > 0, VAR[Y ] = 61 > 0 and we n can again apply part (a) of the lemma to show that lim Z Yst a.s. n-o t=l,t does not exist. In fact, since all of the terms in the sequence are n non-negative, lim Z Y = +o a.s. n-+ t=l s,t These results are intuitive and essentially just illustrate that the ~st are independent samples of the real random variable us

31 Theorems 4.2 and 4.3 show that the concept of asymptotically optimal strategies in a pure problem basis as defined by A and B is vacuous. We now consider using the sample mean as the payoff of a strategy as suggested in Holland (1970). This may be done in two ways. We can require that the algorithm perform the calculation of the sample mean. The algorithm then has the additional task of storing the necessary information to calculate the sample mean for each strategy. Alternatively we could change to a variable problem basis where the calculation of the sample mean is made outside the algorithm in the evaluation of the function payoff. The algorithm would treat the sample mean as the "payoff" for the strategy. The exact implementation is not critical to the question under investigation: Are there asymptotically optimal strategies under Definitions A or B when st is replaced by the sample mean for strategy s? We will formulate a new version of the SR algorithm which calculates the sample mean and uses this value to calculate the probability vector over the strategy set. Definition 4.4: An SR3A (SR3B) is an SRP with the following changes: PAYOFF returns the value vjPt for v, P* for v*. In step 3.7 of the definition of an SRP (Def. 2,1O),if j is 0 set Xj0 = 0. Step 3.10 of definition 2.10 is replaced by: 3.10 Calculate: X. (w (j t)( 1)+ 1. Xj~w~j,t= 2. for 1 < i < N(t+l) j,w(j,t) i= j i,t V* i. i

32 We define SR3B as above except step 3.10.2 is:.j,w(j,t) i j i = max(v*, Xj,w(j,t)) i # j The algorithms SR3A and SR3B suggest the following definitions for asymptotically optimal strategies: C. A strategy s c S, in a pure problem basis <A,p,S> is n asymptotically optimal if I lim t (p*-Xs ) < +00 a.s. n-*,w t Ii I o t D. A strategy s 6 S in a pure problem basis <A,p,S> is n asymptotically optimal if tlim Z (v*-X ) < +00 a.s. t=l t t where Vt = max( I*,s,t) We now show that definition C cannot be satisfied by any strategy in a pure problem basis. Lemma 4..5: Let <A,p,S> be a pure problem basis. For those strategies n s E S such that ps # N*, lim Z (p* X ) a.s. does not exist. n-~ t=l s,t Proof: E [ji*- t] = P*-p* > 0. Choose ~ so that pi*-ps > > 0, then P((p*-X st) > E) 2 6 for 6 > 0 and Lemma 4.1 a. shows that n lim E (V1*-X ) a.s. does not exist. n->- t=l st Lemma 4.5 shows that strategies which do not obtain the maximum mean cannot be asymptotically optimal. The next lemma shows that even if strategies do obtain the maximal mean they cannot by asymptotically optimal by definition C. Lemma 4.6: Let i1v2,..., t... be independent identically distributed real random variables with nonzero variance.

33 t Let E[Pt] = 1* X = t Then it is not the case that n lim E (P*-Xt) < co with probability 1, n-o t=l Proof: Let Y be the nth partial sum. Then rearranging terms n n n (*- ) 1 1/i + *** + (p*-n) 1/n. 1 i=l n Let Xn= (*- ) z 1/i; Z Y X ( 1) i=l n n n X and Z are independent random variables since the Pt are independent. n n 00 Since Z 1/i does not converge and the variance of pt is nonzero, for i=l any M there is an N1, and 61, such that for n > N1 P(Xn > 2M) > 61 P(Xn < -2M) > 61 where 261 < 1. Suppose that the lim Y = N < X with probability 1. Then for C = 1/361, m-~oo there is an N2 such that for n > N2 P(IYnI > M) < c =(1/3)61 Let N = max(Nl,N2). There are two mutually exclusive events (not exhaustive) that give I Y > M namely, {Xm > 2M and Zm > -M} and {Xm < -2M and Zm < HI}. Therefore we know that P(Xm > 2M Zm > -M) <(1/3)6 P(Zm > -M) <(1/3)6i/P(Xm > 2M) < 1/3 P(Zm < -M) > 2/3 Similarly: P(Zm > +M) > 2/3

34 Since {Zm -M} and {Zm > +M} are exclusive events, this is impossible. m - m - n Therefore the assumption about the convergence of lim Z (pu*-Xt) is n-*o t=l false and the theorem results. Theorem 4.7: There are no strategies in a pure problem basis which are asymptotically optimal according to definition C. Proof: The proof follows immediately from Lemma 4.5 and 4.6. We would like an even stronger result than Theorem 4.7. We would like to be able to say that the limit in definition C is nonconvergent with probability 1 even for strategies with optimal mean. Similarly, we would like to be able to say that the limit in definition D is nonconvergent with probability 1. The following two theorems are the result of collaboration with B. Koopmann, C. Oualls, P. Pathok. The proofs are contained in Appendix A. Theorem 4.8: Let {it} be a sequence of independent identically distributed random variables with nonzero variance and finite second moments, let n E[p ] = *, then lim E Z (v*-X) c a.s. where i=l t Theorem 4.9: Let {pt} be a sequence of independent identically distributed random variables with nonzero variance and let E[pt] = l*, then one of the following three conditions hold: S S i) n + + a.s. ii) Z + ~co a.s. or n n S S n n iii) lim E + - a.s., lim Z y - _ a.s. In all three cases S n Z diverges a.s. where S = Z t. n n,=1 t~~

35 We can now obtain the theorem we need concerning definition D: Theorem 4.10: There are no strategies in a pure problem basis which are asymptotically optimal according to definition D. Proof: Theorem 4.8 shows that strategies having optimal means (Ps = I*) cannot be asymptotically optimal according to definition D. Let s be a strategy with ps < v*, then t - X ~t > Pt s Xt for all t, where vt = max(p*,Xst), t = ax(p,t n n Therefore lim (*-X,t) > lim ( ) + a.s. n-_o t=l t st n — t=l t st Thus no strategies can be asymptotically optimal according to D. We have shown that using knowledge of the true means of the distribution of the pj does not provide a definition for asymptotic optimality. However, we could use an estimate of the means as a value for P*. Let f be a function of the sample means, we want to know if f can be defined so that for strategies tj with pj = p* 0o tEl[f(Xlt S,t) - Xt] < a.s. and for strategies ti with pi < * tl [f(Xt.. It) - it] = a.s. We have been exploring this problem but have as yet not developed a function satisfying these conditions. In order to examine the convergence of SRP algorithms over pure problem bases, we conclude that we must employ other means than we used for deterministic bases. The next section introduces the notion of Linear Additive Models, and in Section III of this chapter we show that in most cases the SRI procedures do not converge in a pure problem bases.

36 Section II: The Linear Additive Model In this section we will summarize the development of the Linear Additive Model, a generalization of the Beta Model, given by Norman [1970]. It should be noted that Norman's results are only for the case ISI = 2. This may appear to be a very limited analysis. However, all of the major problems of convergence can be found in this "two dimensional" case. In the psychological interpretation of the model, one is usually interested in the two choice situation. Lamperti [1960] has obtained some results for the Beta Model for the general case. Several of the results presented in this section will be used later on. In Section III we relate Norman's assumptions to the SRP plans we have defined. Assumptions (Norman): 4.11 Qi' i = 1,2, is a probability distribution over the Borel subsets of R, such that Mi(i) = 5exists for - Oo c in some open interval J containing 0. 4.12 p is a measurable mapping of R into I = [0,1], such that p(L) + 1 as L — +, p(L) -* 0 as L -* -o, and p is bounded away from 0 and 1 on any finite interval. Let q = 1-p. 4.13 Tt = (Lt,Xt), t > 1, is a bivariate stochastic process in R x (1,2}, such that P(Xt = 1|Lt'Tt- 1.' T1) = Pt (Pt = P(Lt)) P(Xt = 2ILtTt T1) qt (qt = q( Lt) ) and for any B P(ALt C BITtTt i1'',T1) = QX (B) almost surely. The means of the conditional distributions of Lt are very important. In fact, their values determine the convergence or divergence of the sequence Lt Let mi = ( xdQi(x), then mi = M (0), for i = 1,2.

37 In order for the sequence Pt to converge, Lt must be absorbed at either +0c or -m. Lemmas 4.14 and 4.15 state conditions for absorption and reflection if the m. are nonzero and are constant. Lemma 4.16 removes the possibility for convergence of Lt to some finite limit, with nonzero m.. 1 Lemma 4.14: (Norman) a. If m1 < O, lim inf Lt< m a.s. For any 6 > 0 such that M1(6) < 1, there is a constant B(6) such that lim sup EL[v6]' B(6). b. If m2 > ~, lim sup Ln > -o a.s. For any 6 < 0, such that M2(6) < 1, there is a constant B(6) such that lim sup EL[vt] < B(6). Lemma 4.15: (Norman) a. If mi > 0, then lim sup Lt = o implies lim Lt = a.s., and go(L) = PL(lim Ln = -~) as L+ A b. If m2 < 0, then lim inf Lt = -a implies lim Lt = -a a.s. and gl(L) = PL(lim Lt = ~~) +0 as L -m. Lemma 4.16: (Norman) a. If mI > 0 or m2 > 0, P(lim sup Lt c R) = 0. b. If m1 < 0 or m2 < 0, P(lim inf Lt c R) = 0. With these lemmas, four possibilities for the asymptotic behavior of Pt can be distinguished provided that the mi are nonzero and that the Qi are not dependent upon t. Either Pt converges to 1 a.s., converges to 0 a.s., does not converge to any limit, or has a probability T of converging to 0 and a probability 1-r of converging to 1. Theorem 4.17. (Norman) a. If m1 > and m2 > 0, lim Pt = 1 a.s. b. If m1 < 0 and m2 < 0, lim Pt = 0 a.s. c. If mi > O and m2 < O, gl(L) + g2(L) = 1, where gl (L) = PL(lim pt = 1),

38 g2(L) = PL(lim Pt = 0). In addition gl(L) > 0, g2(L) > 0, gl(L) + 1 as L + + and g2(L) -+ 1 as L -a. d. If m1 < 0 and m2 > 0, lim sup Pt = 1 and lim inf Pt = 0 a.s. These results are independent of the initial value of L1. Variations of this theorem for the Beta Model can be found in LampQrti and Suppes [1960]. Two relations are developed by Norman which will prove useful Lt later: Let vt = e, then Equation 4.18: E[(vt+1 Vt)I vt] = M(X)Pt + M2(k)qt Equation 4.19: E[v Ivn] = vn[M( X)Pn + M0(X)qn]

39 Section III: Linear Models and Pure Problem Bases Now we relate Norman's assumptions to the SR1 algorithm where ISt = 2. Let Tf be the time at which the second strategy is selected. This time is finite with probability one. Let Tf P +k LTf = f ln(jl t 1 =L = — L + 1 for t > T t =1t-l +l +k 2,t-l 1 Then from 2.12 and 2.13 we obtain: Equation 4.20 for t < T P = 1-2-(+0) f l,t P 2-(1+6) 2,t for t > Tf (1+)ek2Lt= P = _ _ (l+) k p(L l,t 2(l+O)ek2Lt +1 t 2,t =l-p(Lt) = q(Lt) For t > Tf, assumption 4.12 of Norman is certainly satisfied by equation 4. 20. Let t t+AL L Lt and Qi, be the probability distribution of'i t* If strategy i is used at time t we use the notation AL.. Let 1,t Equation 4.21. Mi() = eCAL it dQi (i, ) i= 1,2. Since pilt + kl > 1 and by the assumption that the moment generating functions of the ii(a) exist (definition 2.1) Mit(C) exists for C in some open interval J containing 0. Therefore, assumption 4.11 is satisfied if we replace Qit with Qi. If the set S of strategies is a set of pure strategies then we can remove the dependence on the time variable and satisfy assumption 4.11. Assumption 4.13 follows from the

40 definitions of Pit, Lt and Qi in a straight forward manner. Unfortunately, SRP plans do not fall simply into the categories for convergence outlined by Norman. Therefore, we must first extend his results to include the cases where the m. might be 0. Lemma 4.22. If ml = 0, a1 > 0, or n = 0, a2 > 0, then (a) P(lim sup Ltc R) = 0. (b) P(lim inf Lte R) = 0. Proof: Norman's proof of Lemma 4.16 relies on the observation that if mi > 0, then Qi([ 2e,o)) > 0 for some ~ > 0 and Qi([2C,-o)) > 0 for some E < 0. This same observation holds if m. = 0 and we know that ai > 0. Once we have made this observation, Norman's proof applies to the present lemma. Lemma 4.23. a) if m1 = 0, 1 # 0 then lim Lt # +-. b) if m2 = 0, a2 0 then lim Lt c - Proof: a) Suppose lim Lt = +a.s. Since m = O., we can chose a X < 0 and an ~ > 0 such that M1(X) > 1+c. Then lim X L = - t-*oo XLt lime te = 0 and lim [M1(X) Pt + M2(X) qtJ = M1(X) t-+cx Given s we can find N such that for all t > N 0o M1(X) Pt + M2(X) qt > M1(X) -E by Equation 4.19 E[eLt+i] > (Ml(X)s)t-No- l(min[Ml(X),M2())])No X L1 lim E[eXLt+l] > K lim (M1(X) -) t-No-l where k > 0. t-oo t-*o

41 But lim E[e Lt+l] = 0 so K lim (M1(X) -E)t-N -1 0 By our choice of X and ~, M1(X) - is a constant greater than 1. Since K is positive, the limit cannot be less than or equal to 0. Therefore we have a contradiction and our original assumption that Lt = is incorrect. The proof of b) is similar. Theorem 4.24 a) If ml = O. m2 > O, i > then lim sup t = 1 and lim inf.pt = 0. b) If m1 < 0, m2 = 0, oi > 0 then lim sup Pt = 1 and lim inf Pt = 0. c) If m = O. m2 = 0 i > 0 then lim sup t = 1 and lim inf Pt = 0. d) If ml = 0, m2 < 0, ai > 0 then lim Pt = 0 a.s. e) If ml > 0O m2 = 0, a. > 0 then lim Pt = 1 a.s. Proof: a) From lemma 4.14b, lim sup Lt > -ooa.s., lemma 4.22a shows that p(lim sup L tR) = 0. Therefore lim sup Lt = +oa.s. and by 4.12, lim sup Pt = 1. From Lemma 4.22b P(lim inf Lt R) = 0. If lim inf Lt - +oa.s., then since lim sup Lt = +0a.s., lim Lt = +oa.s. But since o1 f 0 this contradicts Lemma 2.23a. Therefore lim inf Lt = -oa.s, and by 4.12 lim inf Pt = 0. b) proof is similar to a. c) By lemma 4.22, P(lim sup LtcR) = 0, P(lim inf L tR) = 0. By lemma 4.23 lim Lt ~ +c and lim Lt -c.o Therefore, lim sup Lt f lim inf Lt and lim sup Lt = +a.s., lim inf L = -Ca.s. and the theorem follows. d) By lemma 4.22, lim inf Lt R a.s. and lim sup Lt R a.s. If lim inf Lt = + then lim sup Lt = +c and lim L = +X. But this contradicts lemma 4.23a. Therefore lim inf Lt = -a and by lemma 4.15b, and m2 < 0, lim Lt = -a.s., and by assumption 4.12 lim Pt = () a.s. t ~~, =0as

42 e) By lemma 4.22, lim inf Lt P R a.s. and lim sup Lt o R a.s. If lim sup Lt = -0 then lim inf Lt = -' and lim Lt = -0. But this contradicts lemma 4.23b. Therefore lim sup Lt = +0 and by lemma 4.15a and m1 > 0, lim Lt = + a.s. and by assumption 4.12, lim Pt = 1 a.s. The intuitive character of the distinction between conditions d and e of the theorem and the other three conditions should be clear. If m1 > O then probability one of selection of strategy 1 is an absorbing barrier. If m1 < O then probability one of selection of strategy 1 is a reflecting barrier. Similarly if m2 < 0 then probability zero of selection of strategy 1 is an absorbing barrier. If m2 > 0 then probability zero of selection of strategy 1 is a reflecting barrier. Definition 4.25: A function f(x) is strictZy concave if the tangent to f(x) at any x lies above the graph of f. That is, f" < 0. Lemma 4.26: If f is a real, continuous and strictly concave function defined on an interval (a,b) of the real line, X a real random variable defined on (a,b), then Elf(X)] < f(E[X]). Proof: Since f is concave: f(x). f(E[X]) + f'(E[X])(x-E[X]) b b 5f(x)dP < S (f(E[X]) + f'(E[X])(x-E[X]))dP a a E[f(X)] < f(E[X]). Corollary 4.27: The natural logarithm is a concave function and therefore E[ln(X) ] d In(E[X]).

43 Now we consider the convergence of SRl a and b plans. Let IS| = 2 and suppose that strategy 1 is such that p1 = p* (the case P2 = p* is symmetric). Then we first need to calculate the values of m1 and m2 for an SRla. I'll +K m = E[AL t] = E[lnpl*k ] = E[ln(il,t+kl)] - ln(p*-kl) applying 4.27, m1 <0. = E[AL2 t] = E[ln +k m2 A2 ~ 1122,t+k 1 = ln(p*+kl) - E[ln (2,t+kl)] applying 4.27, ln(p*+kl) - ln(p2+kl) and since p* > p2 m2 >'. We now have the conditions necessary to apply theorems 4.17d, 4.24a and b and obtain: Theorem 4.28: An SRla plan over a pure problem basis <A,v,S> with ISI = 2 will not converge to the strategy with higher mean. In fact, lim sup P 1 and lim inf Pt = 0. Let \t = max(p*,'j,t) where j is the strategy used at time t. Then for the SRlb plan we have vt+ k m2= E[AL2,t] = E[lnu +k ] 2,t 1 = E[ln(t+kl)] - E[ln(i2, kl)] by 4.27 ~ E[ln(3t+kl)] - ln(P2+kl)

44 since Ot > p2, ln( t+kI) > ln(p2+k1) and E[ln(Ot+kl)] > ln(P2+kl) therefore, m2 0 ~ ml = E[ln'+k ] = E[ln(Glt +k1)] - E[ln(t +k )]. ln(p*+kl) - E[ln(Dt+kl)] since Vt > p*, ln(vt+kl) > ln(p*+kl), and E[ln(;t+kl)] > ln(p*+kl) therefore, mln 0. Again applying theorem 4.17d, 4.24a and b we obtain: Theorem 4.29: An SRlb plan over a pure problem basis <A,p,S> with ISI = 2 will not converge to the strategy with the higher mean. In fact lim sup Plt 1 and lim inf P = t 0. We now investigate the convergence properties of SR3 A and B plans with ISI = 2. Again we assume that p1 = p* (the case 2 = P* is symmetric). First, we calculate the values of the m. for SR3A: xlt+k 1 ml,t= E[L1,t] = E[ln0.+ki ] = E[ln(Xl t+kl)] - E[ln(p*+kl)] < ln(E[Xlt+kl]) - ln(p*+kl) by 4.27.. For m2 t we find: P*+k m2 t = E[AL2 t] = E[ln + ]1 = E[ln(p*+kl)] - E[ln(X2,t+k )]

45 m2,t > ln(p*+k1) - ln(p2+kl) m2,t O By similar calculations for the SR3B plans with 9t = max(p*,X t) ~t ~ ~ j, where j is the strategy used at time t, we find that the same relations hold and mlt 4< while m2,t >, 0. Lemma 4.30: If m1lt. 0, m2t > 0 for all t, ao > 0 and o20t > 0 then lim sup Pt = 1, and lim inf Pt = 0. Proof: the proof is similar to that for theorem 4.24 and relies on 4.24 part c. Now we have shown the following: Theorem 4.31: SR3A and SR3B plans over a pure problem basis <A,>i,S> with ISI = 2 will not converge to the strategy with the higher mean. In fact lim sup P,t = 1 and lim inf Pl,t = 0.

CHAPTER S CONCLUS IONS In this work we have examined the convergence properties of a class of probabilistic sequential adaptive schemes called sequential reproductive plans, type I (SRP). Theorem 3.21 shows that a subclass, the SR1 plan over a finite restricted deterministic arena, converges with probability 1 to a set of "good" strategies. However Theorem 3.16 shows that these plans do not converge fast enough to achieve the finite loss claimed in Holland [1970]. We have shown in Chapter 4 (Theorems 4.2, 4.3, 4.7, and 4.10) that there is not an intuitive analogue in pure problem bases for the notions of optimal strategy and arena which were defined for deterministic bases. In fact, by extending results in mathematical psychology, we have shown that several large subclasses of SRP plans do not converge in pure problem bases. (Theorems 4.28, 4.29, 4.31) Because of the convergence problems of SRP type I plans,'we suggest that they are not adequate models of the duplication process in genetic adaptation. Two further plans have been studied as a result of these findings. A plan which we call SRP Type II, has been developed by Holland and Moler [unpublished] which uses the concept of an arena as a foundation for a non probabilistic, block structured sampling scheme. This plan does overcome many of the difficulties of SRP Type I plans. However, since it relies on the concept of an arena, there are convergence problems in non-deterministic bases. Holland [1973] has examined the convergence of a much simpler implementation of the duplication process. Extensions of this work may be made in several directions. The 46

47 results we have obtained on Linear Additive models could be extended to n dimensions. Further models of the duplication operator can be studied and incorporated in a detailed theoretical study of the other genetic operators in the artificial adaptive framework. We are presently working on a theoretical comparison of artificial genetic techniques with numerical analysis techniques in n dimensional function maximization.

APPENDIX A* Theorem: Let X1, X2,... be a sequence of independent identically distributed real random variables, not identically zero. Then Sn,?, n diverges a.s. n=l and a certain trichotomy holds. Proof: 1. Suppose first that P(X1 > 0) > 0 and P(X1 < 0) > 0. m S m Writing n = X Z (l/i)+ Ym, we note that nWln 1 i=l i -m m [lim y < M, X 1 tZ (l/i) + -0] C [nS (S n/n) -o m m [lim Ym >, X1 t-l (1/i) +o- ] C [n-l (Sn/n) i +o] m' 1 m m [lim Y = -+, X = (l/i) + -+] C [ lim E (S /n) -c]..m' m 1 n1 n- n m m [lim Y = - lm Y = +w X (l/i) +M] C [ lim nEl (Sn/n) - +] 2. By the Hewitt-Savage 0-1 law, the four events on the right hand side of the above implications have 0 or 1 probabilities. Now m m P 1l iZ1 (l/i) - -o) > 0 and P(X1 iEl (l/i) - +w) > 0 and at least one of the following is true: P(lim Ym < w) > O, P(lim Ym < -) > 0 or P(lim Ym = -0, lim Ym = +o) > 0. Consequently we have the following trichotomy: m S i) n + -OOa.s. n=l n m S ii). n + +a.s. n=l n * See Koopmans et al. [to be published]. 48

49 S S iii) lim E n + _ and lim z n- + +a.s. n n S S+ S- SWriting EZ- = E - -, we see that in case i) Z = n n n n S+ S- S+ in case ii) - + oo and in case iii) Z. = o and z n =. n n n S S- S+ 3. If P(X1 i 0) = 1, then case i) with Z n = _ Z 00 = -a. and Z-n 0 n n n S S+ Sn n n If P(X1 O) = 1, then case ii) with s- = n = c0a. s. and s- O S In all three cases, Z-n is divergent a.s. n Theorem: Let X1,X2,... be i.i.d. with E[X1] = 0, and O < o < ~. Let S X +..+X S+ = max (0,S) and S- = max (0,-S ) n 1 n n n n n cO S+ x Sn n Then Z- =a +-a. s. and Z -= -a. s. 1 n 1 n Proof: From the previous theorem it follows that either co S+ o _n = oo as. n Z n = oo a.s. n To S+ co SSuppose that E n = oa.s. and Z n does not diverge. n S Then E — n- = +w a.s. P( E n.. ++o) = 1 N S N Let T =Z =X /i +...-X N N 1 n /i.. +XN1/ N Z CkN Xk k=l

50 where Ck = /N k,N Consider TN N. X= Z Y N ~ dk,N k k= k,N N 2 k=l k k=l It is easy to see that dl,N d2 N > > dN,N and lim d 0 N,N and {Y 1 k N, N N 1} are uniformly small random variables. Let Fk N be the distribution function of YkN' Then by the Lindeberg-Feller criterion: TN iZ C 2 is asymptotically normal with zero mean and k N k=l unit variance, if N lim Z 9 y2dF = 0 N-+o k=l But N 2 Z )dkN Xk dFk where Fk is the d.f. of Xk k=l k,N k k k k k=l l dkNX kI >.. =Z d~N X dFk (Xk) = dk N < Z d,N dF(X) X2dF (X) Id1,NX) > c d1.NXI > e

51 + 0 as Nco since lim d = 0 1,N N-+o So the central limit theorem holds and hence TN 1 lim P[ > 0] = /2 N-c FVk,N i.e. lim P[TN > 0] = /2 N-o but this contradicts what we had before, namely; 00 S lim T =E = +oo a. s N->o N 1 STherefore, the assumption that E n does not diverge is false. Hence both S- S+ E n and Z -n diverge a.s. n n

REFERENCES 1. Bosworth, J.; Foo, N.; and Zeigler, B.P. "Comparison of Genetic Algorithms with Conjugate Gradient Methods" Computer and:Communication Sciences, The University of Michigan, 1972. 2. iCavicchio, D.J. "Adaptive Search Using Simulated Evolution".Doctoral Dissertation, Computer and Communications Sciences, The University of Michigan, 1970. 3. Cover, T.M. "Hypothesis Testing with Finite Statistics" The Annals of Mathematical Statistics, 40, 3, pp. 828-835, 1969. 4. Foo, N.; and Bosworth, J. "Algebraic, Geometric, and Stochastic Aspects of Genetic Operators'.' Computer and Communication Sciences, The University of Michigan, 1972. 5. Frantz, Daniel R. "Non-linearities in Genetic Adaptive Search" Doctoral Dissertation, Computer and Communication Sciences, The University of Michigan, 1972. 6 Hellman, M.E. and Cover, T.M. "Learning with Finite Memory" The Annals of Mathematical Statistics, 41, 3, pp. 765-782, 1970. 7., "On Memory Saved by Randomization" The Annals of Mathematical Statistics, 42,, pp., 1971. 8. Holland, J. "A New Kind of Turnpike Theorem" BuZZ. of the Amer. Math. Society, 75, 6, pp. 1311-1317, 1969. 9., "Robust Algorithms for Adaptation Set in a General Formal Framework" Proceedings of the Ninth IEEE Symposium on Adaptive Processes, "Decision and Control", Austin, Texas, 1970. 1Q., "Genetic Algorithms and the Optimal'Allocation of Trials" SIAM Journal, 2, 2, 1973. 11., Introduction to Adaptation in NaturaZ and Artificial Systems, to be published. 12. Hollstien, R.B. "Artificial Genetic Adaptation in Computer Control Systems" Doctoral Dissertation, Computer, Information and Control Engineering, The UniVersity of Michigan, 1971. 13. Knopp, K. Infinite Sequences and Series, Dover Publications, New York, 1956. 14. Koopmans, L.H., N. Moler, P. Pathak, and C. Qualls, "On The Divergence of a Certain Random Series," Submitted for publication. 15. Lamperti, J. "Criteria for the Recurrence of Transience of Stochastic Process. I" J. of Math. AnaZysis and Applications, 2, pp. 314-330, 1960. 52

53 16. Lamperti, J. and Suppes, P. "Some Asymptotic Properties of Luce's Beta Learning Model" Psych'emtrita:,. 25;, 3;, pp. 233-241, 1960. 17. Luce, R.D. Tndividual Choice Behavior. New York: Wiley, 1959. 18. Neveu, J. Mathematical Foundations of the Calculus of Probability, Holden-Day, Inc. 1965. 19, Norman, M.F. "Limit Theorems for Additive Learning Models" J. Math. Psychology, 7, 1, pp. 1-11, 1970. 20. Robbins, H.E. "Some Aspects of the Sequential Design of Experiments" BullZZ. Am. Math. Soc., 55, pp. 527-535, 1952. 21., "A Sequential Decision Problem with a Finite Memory" Proc. Nat. Acad. Sci., 42, pp. 920-923, 1956. 22. Shapiro, I.J. and Narendra, K.S. "Use of Stochastic Automata for Parameter Self-Optimization with Multimodal Performance Criteria" IEEE Trans. on SSC, SSC-5, 4, pp. 352-360, 1969.

UNIVERSITY OF MICHIGAN 31111111 90111111111111111 0 951111111111 3 9015 03095 0573