Asymptotically efficient strategies for a stochastic scheduling problem with order constraints
Authors:
- Cheng-Der FuhCFCheng-Der Fuh
- Inchi HuIHInchi Hu
Open Access
- 1 December 2000
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Statistics
- Vol. 28 (6) , 1670-1695
Abstract
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.
Keywords
This publication has 16 references indexed in Scilit:
- Poisson equation, moment inequalities and quick convergence for Markov random walksStochastic Processes and their Applications, 2000
- A NEW METHOD OF CONTROLLING ITEM EXPOSURE IN COMPUTERIZED ADAPTIVE TESTINGETS Research Report Series, 1995
- Markov Chains and Stochastic Stability1993
- A dependent data extension of Wald's identity and its application to sequential test performance computationIEEE Transactions on Information Theory, 1989
- Asymptotically efficient adaptive allocation schemes for controlled i.i.d. processes: finite parameter spaceIEEE Transactions on Automatic Control, 1989
- Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: I.I.D. rewardsIEEE Transactions on Automatic Control, 1987
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Bandit problems1985
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952
- A Method for Obtaining and Analyzing Sensitivity DataJournal of the American Statistical Association, 1948