|
|
|
|
|
|
|
use of the central limit theorem. To see the form of the error, let us follow Frantz by using Fn(x)to designate the distribution of the normalized sum of the observations of the random variable X. For the 2-armed bandit, F is the distribution of the difference of the two random variables of interest. Using the notation of chapter 5, q(n) = 1 - Fn(x)when x = bn½. That is, 1 - Fn(x)gives the probability of a decision error, q(n),after n trials out of N have been allocated to the random variable observed to be second best. Because x is a function of n,the proof given in chapter 5 implicitly assumes that, as n ®¥, the ratio |
|
|
|
|
|
|
|
|
where 1 - F(x) is the area under the tail of a normal distribution. However, standard sources (see Feller 1966, for example) show that this is only true when x varies with n as o(n1/6). This is manifestly untrue for Theorem 5.1, where x = bn½. |
|
|
|
|
|
|
|
|
The main result of theorem 5.1 can be recovered by using the theory of large deviations instead of the central limit theorem. The theory of large deviations makes the additional requirement that the moment-generating functions for the random variables exist, but this is satisfied for the random variables of interest here. Let the moment-generating functions for the two random variables, corresponding to the two arms of the bandit, be m1(t)and m2(t). Then the moment-generating function for X, the difference, is m(t) = m1(-t)*m2(t). There is a uniquely defined constant c such that |
|
|
|
|
|
|
|
|
Define S(n)to be the sum of n samples of X. Then the appropriate theorem on large deviations yields |
|
|
|
|
|
|
|
|
where log dn = o(1). Making appropriate provision for ties, this yields |
|
|
|
|
|
|
|
|
where b'is a constant that depends upon whether or not X is a lattice variable. This relation for q(n)is of the same form (except for constants) as that obtained for q(n)under the inappropriate use of the central limit theorem. Substituting, and proceeding as before, Frantz obtains |
|
|
|
|
|
