|
|
|
|
|
|
|
5. The Optimal Allocation of Trials |
|
|
|
|
|
|
|
|
In the last chapter a schema x was defined as potentially useful when  , the observed average performance of instances of that schema, was significantly greater than the overall average performance. However, is basically a sample average for a random variable (or sequence of random variables) and, as such, is subject to sampling error. For any two schemata x and x', there is always a non-zero probability that µx' > µx even though  . This reintroduces in a sharp form the conflict of exploiting what is known vs. obtaining new information. Confidence that the ranking reflects a true ranking µx > µx' can be increased significantly only by allocating additional trials to both x and x'. Thus, we can allocate a trial to exploit the observed best or we can allocate a trial to reduce the probability of error as much as possible but we cannot generally do both at once. Given a string-represented domain  , it is important to have some idea of what proportion of trials should be allocated to each purpose as the number of trials increases. |
|
|
|
|
|
|
|
|
Corresponding to each of these objectivesexploitation vs. new informationthere is a source of loss. A trial allocated to the observed best may actually incur a loss because of sampling error, the observed best being in fact less than the best among the alternatives examined. On the other hand trials intended to maximally reduce the probability of error will generally be allocated to a schema other than the observed best. This means a performance less on the average than the best among known alternatives, when the observations reflect the true ranking. Stated succinctly, more information means a performance loss, while exploitation of the observed best runs the risk of error perpetuated. |
|
|
|
|
|
|
|
|
Competing sources of loss suggest the possibility of optimizationminimizing expected losses by a proper allocation of trials. If we can determine the optimal allocation for arbitrary numbers of trials, then we can determine the minimum losses to be expected as a function of the number of trials. This in turn can be used as a criterion against which to measure the performance of suggested adaptive plans. Such a criterion will be particularly useful in determining the worth of plans |
|
|
|
|
|