Optimal Adaptive Policies for Sequential Allocation Problems

✍ Scribed by Apostolos N. Burnetas; Michael N. Katehakis

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 301 KB
• Volume: 17
• Category: Article
• ISSN: 0196-8858
• DOI: 10.1006/aama.1996.0007

✦ Synopsis

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 g ⌰, it is shown that there exists a class C of R Ž . adaptive policies with the following properties: i The expected n horizon reward 0 Ž . 0 Ž . Ž . Ž . V under any policy in C is equal to n* y M log n q o log n , as n R Ž . Ž . Ž . n ª ϱ, where * is the largest population mean and M is a constant. ii Policies in C are asymptotically optimal within a larger class C of ''uniformly R UF 0 Ž Ž . Ž .. fast convergent'' policies in the sense that limnªϱ n* y V r n Ž Ž . Ž .. Ž . n* y V F 1, for any g C and any g ⌰ such that M ) 0. n UF

Policies in C are specified via easily computable indices, defined as unique R Ž . solutions to dual problems that arise naturally from the functional form of M . 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.