Optimal Adaptive Policies for Sequential Allocation Problems

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


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 \underline{\underline{\theta}}\in\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}(\underline{\underline{\theta}}) under any policy pi 0 in C R is equal to n\mu^*(\underline{\underline{\theta}})-M(\underline{\underline{\theta}})\log n+o(\log n) , as n -<[infinity], where \mu^*(\underline{\underline{\theta}}) is the largest population mean and M(\underline{\underline{\theta}}) 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 \varlimsup_{n\to\infty}(n\mu^*(\underline{\underline{\theta}})-V_n^{\pi^0}(\unde rline{\underline{\theta}}))/(n\mu^*(\underline{\underline{\theta}})-V_n^{\pi}(\u nderline{\underline{\theta}}))\le1 , for any pi∈ C UF and any \underline{\underline{\theta}}\in\Theta such that M(\underline{\underline{\theta}})>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(\underline{\underline{\theta}}) . 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.

Document Type: Research Article

Affiliations: 1: Department of Operations Research, Case Western Reserve University, Cleveland, Ohio, 44106-7235 2: GSM and RUTCOR, Rutgers University, Newark, New Jersey, 07102-1895

Publication date: June 1, 1996

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more