Asymptotically efficient strategies for a stochastic scheduling problem with order constraints
成果类型：
Article
署名作者：
Fuh, CD; Hu, IC
署名单位：
Academia Sinica - Taiwan; Hong Kong University of Science & Technology
刊物名称：
ANNALS OF STATISTICS
ISSN/ISSBN：
0090-5364
发表日期：
2000
页码：
1670-1695
关键词：
摘要：
Motivated by an application in computerized adaptive tests, we consider the following sequential design problem. There are J jobs to be processed according to a predetermined order. A single machine is available to process these J jobs. Each job under processing evolves stochastically as a Markov chain and earns rewards as it is processed, not otherwise. The Markov chain has transition probabilities parameterized by an unknown parameter theta. The objective is to determine how long each job should be processed so that the total expected rewards over an extended time interval is maximized. We define the regret associated with a strategy as the shortfall from the maximum expected reward under complete information on theta. Therefore the problem is equivalent to minimizing the regret. The asymptotic lower bound for the regret associated with any uniformly good strategy is characterized by a deterministic constraint minimization problem. In ignorance of the parameter value, we construct a class of efficient strategies, which achieve the lower bound, based on the theory of sequential testing.