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:
“A country grows in history not only because of the heroism of its troops on the field of battle, it grows also when it turns to justice and to right for the conservation of its interests.”
—Aristide Briand (1862–1932)
“Don’t give your opinions about Art and the Purpose of Life. They are of little interest and, anyway, you can’t express them. Don’t analyse yourself. Give the relevant facts and let your readers make their own judgments. Stick to your story. It is not the most important subject in history but it is one about which you are uniquely qualified to speak.”
—Evelyn Waugh (1903–1966)
“Boys forget what their country means by just reading “the land of the free” in history books. Then they get to be men, they forget even more. Liberty’s too precious a thing to be buried in books.”
—Sidney Buchman (1902–1975)