We present our equations in the univariate setting. All results in the paper apply equally to the multivariate case.

As described earlier, we could also have selected queries by hillclimbing on 190#190; in this low dimensional problem it was more computationally efficient to consider a random candidate set.

The times reported are ``per reference point'' and ``per candidate per reference point''; overall time must be computed from the number of candidates and reference points examined. In the case of the LOESS model, for example, with 100 training points, 64 reference points and 64 candidate points, the time required to select an action would be 194#194seconds, or about 0.3 seconds.

It is worth mentioning that approximately half of the training time for the mixture of Gaussians is spent computing the correction factor in Equation 8. Without the correction, the learner still computes 195#195, but does so by modeling the training set distribution rather than the reference distribution. We have found however, that for the problems examined, the performance of such ``uncorrected'' learners does not differ appreciably from that of the ``corrected'' learners.

David Cohn
Mon Mar 25 09:20:31 EST 1996