Optimal adaptive policies for sequential allocation problems

Consider the problem of sequential sampling from m statistical populations to maximize the expected sum of outcomes in the long run. Under suitable assumptions on the unknown parameters <(<theta))double under bar> is an element of Theta, it is shown that there exists a class C-R of adaptive policies with the following properties: (i) The expected n horizon reward V-n(pi 0)(<(theta)double under bar>) under any policy pi(0) in C-R is equal to n mu*(<(theta)double under bar>) - M(<(theta)double under bar>)log n + o(log n), as n --> infinity, where mu*(<(theta)double under bar>) is the largest population mean and M(<(theta)double under bar>) is a constant. (ii) Policies in C-R are asymptotically optimal within a larger class C-UF of ''uniformly fast convergent'' policies in the sense that lim(n-->x)(n mu*(<(theta)double under bar>) - V-n(pi 0)(<(theta)double under bar>)/(n mu*(<(theta)double under bar>) - V-n(pi)(<(theta)double under bar>) less than or equal to 1, for any pi is an element of C-UF and any <(theta)double under bar> is an element of Theta such that M(<(theta)double under bar>) > 0. Policies in C-R are specified via easily computable indices, defined as-unique solutions to dual problems that arise naturally from the functional form of M(<(theta)double under bar>). In addition, the assumptions are verified for populations specified by nonparametric discrete univariate distributions with finite support. In the case of normal populations with unknown means and variances, we leave as an open problem the verification of one assumption. (C) 1996 Academic Press, Inc.