History
Questions about the optimal stopping policies in the context of clinical trials have been open from the 1940s and in the 1960s a few authors analyzed simple models leading to optimal index policies, but it was only in the 1970s that Gittins and his collaborators demonstrated in a markovian framework that the optimal solution of the general case is an index policy whose "dynamic allocation index" is computable in principle for every state of each project as a function of the single project's dynamics.
Soon after the seminal paper of Gittins, Peter Whittle demonstrated that the index emerges as a lagrangian multiplier from a dynamic programming formulation of the problem called retirement process and conjectured that the same index would be a good heuristic in a more general setup named Restless bandit. The question of how to actually calculate the index for Markov chains was first addressed by Varaiya and his collaborators with an algorithm that computes the indexes from the largest first down to the smallest and by Chen and Katehakis who showed that standard LP could be used to calculate the index of a state without requiring its calculation for all states with higher index values. LCM Kallenberg provided a parametric LP implementation to compute the indices for all states of a Markov chain. Further, Katehakis and Veinott demonstrated that the index is the expected reward of a Markov decision process constructed over the Markov chain and known as Restart in State and can be calculated exactly by solving that problem with the policy iteration algorithm, or approximately with the value iteration algorithm. This approach also has the advantage of calculating the index for one specific state without having to calculate all the greater indexes and it is valid under more general conditions. A faster algorithm for the calculation of the indexes has been obtained in 2004 by Sonin as a consequence of his elimination algorithm for the optimal stopping of a Markov chain. In this algorithm the termination probability of the process may depend on the current state rather than being a fixed factor. A faster algorithm has been proposed in 2007 by Niño-Mora by exploiting the structure of a parametric simplex to reduce the computational effort of the pivot steps and thereby achieving the same complexity as the gaussian elimination algorithm.
Read more about this topic: Gittins Index
Famous quotes containing the word history:
“I am ashamed to see what a shallow village tale our so-called History is. How many times must we say Rome, and Paris, and Constantinople! What does Rome know of rat and lizard? What are Olympiads and Consulates to these neighboring systems of being? Nay, what food or experience or succor have they for the Esquimaux seal-hunter, or the Kanaka in his canoe, for the fisherman, the stevedore, the porter?”
—Ralph Waldo Emerson (1803–1882)
“Most events recorded in history are more remarkable than important, like eclipses of the sun and moon, by which all are attracted, but whose effects no one takes the trouble to calculate.”
—Henry David Thoreau (1817–1862)
“When the history of guilt is written, parents who refuse their children money will be right up there in the Top Ten.”
—Erma Brombeck (20th century)