Optimal stopping of Markov chains and three abstract optimization problems

Abstract

There is a well-known connection between the three problems related to the optimal stopping of Markov chains and the equality of three corresponding indices: the classical Gittins index (GI) in the ratio maximization problem, the Kathehakis–Veinott index in a restart problem and Whittle index in a family of retirement problems.

In Sonin [Statist. Probab. Lett. 78 (12,1) (2008), pp. 1526–1533], these three problems and these three indices were generalized in such a way that it became possible to use the state elimination algorithm [Sonin, Math. Meth of Oper. Res. (1999), pp. 111–123] to calculate this common generalized GI α.

The main goal of this note is to demonstrate that the equality of these (generalized) indices is a special case of a more general relation between three simple abstract optimization problems.

Keywords:

• Gittins index
• Markov chain
• optimal stopping
• the elimination algorithm

AMS Subject Classification::

• primary 60J22
• 62L15
• secondary 65C40
• 90C40

Acknowledgements

The author would like to thank Robert Andersen, Joseph Quinn and Ernst Presman, who read the first version of this paper and made valuable comments, and two anonymous referees for helpful suggestions.