|
|
|
|
|
|
|
2. The Robustness of Plans  |
|
|
|
|
|
|
|
|
It might seem that the natural first step in establishing the robustness of an adaptive plan would be to show that it will ultimately converge to an optimal structure. However, as early as section 1.5 it was possible to make a good argument against convergence as a criterion for distinguishing useful plans. Enumerative plans converge, yet in all but the most restricted circumstances they are useless either as hypotheses or algorithms. Moreover, when data can be retained by no more than M structures and M < | |, no plan for searching can yield convergence. More formally, for any M < ||, there exists  such that as T ®¥, |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
where  is a subset of consisting of one or more structures with optimal mean performance (i.e., structures  such that the mean of the random variable µE(A') is at least as high as the mean for any  ). This is so because for any finite sequence of trials of a suboptimal structure in , there is a non-zero probability that its observed average performance will exceed the observed performance of the optimal structure(s) (assuming overlapping distributions). Clearly, if enough of the structures being tested exhibit observed performances above that of the optimal structure(s) (again an event with a non-zero probability), the result will be the deletion of data concerning the optimal structure. Thus, unless possible convergence to a suboptimal structure is to be allowed, each structure must be repeatedly tested (infinitely often in the limit). But this repeated testing (and the law of large numbers) assures that suboptimal structures which have a finite probability of displacing an optimal structure will do so with a limiting frequency approaching that probability. Hence, for M < ||, no plan can yield (1/T)STP(, t) ® 1. At the same time,  (even when M' < ||) because of two effects: |
|
|
|
 |
|
|
|
|
(i) the more copies there are of a suboptimal structure A in a given generation, the smaller the variance of the associated average payoff µA(t) (making it less likely that  ), |
|
|
|
|
|
|
|
|
(ii) more generations are required to displace A' in the whole population (meaning that  has to exceed  over a longer period, a progressively less likely event). |
|
|
|
|
|
|
|
|
At the cost of a small increase in the complexity of the algorithms we can assure that they converge when M > || (as, for example, in the |
|
|
|
|
|