The elimination algorithm for the problem of optimal stopping

MaRDI QIDQ1299925zbMATH OpenFDO

Authors Isaac Sonin

Publication date 25 April 2000

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

zbMATH Keywords

discrete timeelimination algorithmMarkov chainoptimal stoppingsecretary problemsequential analysis discounting

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40)

Review text

The author presents a new method for solving the optimal stopping problem [cf. \textit{Y. S. Chow, H. Robbins} and \textit{D. Siegmund}, ``Great expectations: The theory of optimal stopping (1971; Zbl 0233.60044)] of Markov chains with countable state spaces. The algorithm is based on the idea of elimination of states where stopping is nonoptimal and the corresponding recomputation of transition probabilities. After a short review of the main existing algorithms (direct solution of the Bellman equation, value iteration, and linear programming), the elimination algorithm (Theorem 1) is proved, and three examples of its application are given, including solution of the classical secretary problem [cf. \textit{T. S. Ferguson}, Stat. Sci. 4, No. 3, 282-296 (1989; Zbl 0788.90080)].

Recommendations

• scientific article; zbMATH DE number 5066282
• On optimal stopping of random sequences modulated by Markov chain
• Combination of optimal stopping algorithms
• A new approach to the solution of optimal stopping problem in a discrete time

Cited in

(15)

• On a duration problem with unbounded geometrical horizon
• Efficient solutions for a class of optimal stopping problems
• Parallel computing for Markov chains with islands and ports
• A model of a 2-player stopping game with priority and asynchronous observation
• Combination of optimal stopping algorithms
• On optimal stopping of random sequences modulated by Markov chain
• Optimal stopping of Markov chains and three abstract optimization problems
• A new approach to the solution of optimal stopping problem in a discrete time
• Solution of optimal stopping problem based on a modification of payoff function
• Optimal stopping of seasonal observations and projection of a Markov chain
• scientific article; zbMATH DE number 3995078 (Why is no real title available?)
• On the forward algorithm for stopping problems on continuous-time Markov chains
• An alternative way to solve optimal stopping problems
• A Forward Algorithm for Solving Optimal Stopping Problems
• A generalized Gittins index for a Markov chain and its recursive calculation

This page was built for publication: The elimination algorithm for the problem of optimal stopping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1299925)