Hostname: page-component-6bf8c574d5-xtvcr Total loading time: 0 Render date: 2025-02-23T04:44:04.505Z Has data issue: false hasContentIssue false
  • English
  • Français

Multiobjective Stopping Problem for Discrete-Time Markov Processes: Convex Analytic Approach

Part of: Markov processes

Published online by Cambridge University Press:  14 July 2016

F. Dufour  and
A. B. Piunovskiy
F. Dufour*
Affiliation:
Université Bordeaux I
A. B. Piunovskiy*
Affiliation:
University of Liverpool
*
∗Postal address: Université Bordeaux I and INRIA Bordeaux Sud Ouest, Institut de Mathématiques de Bordeaux, 351 cours de la Liberation, 33405 Talence Cedex, France. Email address: [email protected]
∗∗Postal address: Department of Mathematical Sciences, University of Liverpool, L69 7ZL, Liverpool, UK. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The purpose of this paper is to study an optimal stopping problem with constraints for a Markov chain with general state space by using the convex analytic approach. The costs are assumed to be nonnegative. Our model is not assumed to be transient or absorbing and the stopping time does not necessarily have a finite expectation. As a consequence, the occupation measure is not necessarily finite, which poses some difficulties in the analysis of the associated linear program. Under a very weak hypothesis, it is shown that the linear problem admits an optimal solution, guaranteeing the existence of an optimal stopping strategy for the optimal stopping problem with constraints.

Keywords

Optimal stoppingconstrained controlMarkov chainlinear programconvex analytic approachMarkov decision processoccupation measure

MSC classification

Secondary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 4 , December 2010 , pp. 947 - 966
Copyright
Copyright © Applied Probability Trust 2010 

Footnotes

Research partially supported by the Royal Society, grant no. TG091905.

References

[1] Altman, E (1999). Constrained Markov Decision Processes. Chapman and Hall, Boca Raton, FL.Google Scholar
[2] Bertsekas, D. P. and Shreve, S. E. (1978). Stochastic Optimal Control (Math. Sci. Eng. 139). Academic Press, New York.Google Scholar
[3] Borkar, V. S., Pinto, J. and Prabhu, T. (2009). A new learning algorithm for optimal stopping. Discrete Event Dyn. Systems 19, 91–113.CrossRefGoogle Scholar
[4] Boyarchenko, S. and Levendorski{ı˘, S.} (2007). Irreversible Decisions Under Uncertainty (Stud. Econom. Theory 27). Springer, Berlin.Google Scholar
[5] Cho, M. J. and Stockbridge, R. H. (2002). Linear programming formulation for optimal stopping problems. SIAM J. Control Optimization 40, 1965–1965.CrossRefGoogle Scholar
[6] De Saporta, B., Dufour, F. and Gonzalez, K. (2010). Numerical method for optimal stopping of piecewise deterministic Markov processes. Ann. Appl. Prob. 20, 1607–1637.CrossRefGoogle Scholar
[7] Dufour, F. and Miller, B. (2004). Singular stochastic control problems. SIAM J. Control Optim. 43, 708–730.CrossRefGoogle Scholar
[8] El Karoui, N., Huu Nguyen, D. and Jeanblanc-Picqué, M. (1987). Compactification methods in the control of degenerate diffusions: existence of an optimal control. Stochastics 20, 169–219.Google Scholar
[9] Guo, X. and Piunovskiy, A. (2010). Discounted continuous-time Markov decision processes with constraints: unbounded transition and loss rates. To appear in Math. Operat. Res. Google Scholar
[10] Haussmann, U. and Lepeltier, J.-P. (1990). On the existence of optimal controls. SIAM J. Control Optimization 28, 851–902.CrossRefGoogle Scholar
[11] Hernández-Lerma, O. and Lasserre, J. B. (1996). Discrete-time Markov Control Processes (Appl. Math. 30). Springer, New York.CrossRefGoogle Scholar
[12] Hernández-Lerma, O. and Lasserre, J. B. (1999). Further Topics on Discrete-Time Markov Control Processes (Appl. Math. 42). Springer, New York.CrossRefGoogle Scholar
[13] Horiguchi, M. (2001). Markov decision processes with a stopping time constraint. Math. Meth. Operat. Res. 53, 279–295.CrossRefGoogle Scholar
[14] Horiguchi, M. (2001). Stopped Markov decision processes with multiple constraints. Math. Meth. Operat. Res. 54, 455–469.CrossRefGoogle Scholar
[15] Kallenberg, L. C. M. (1994). Survey of linear programming for standard and nonstandard Markovian control problems. I. Theory. Z. Operat. Res. 40, 1–42.Google Scholar
[16] Novikov, A. and Shiryaev, A. (2007). On solution of the optimal stopping problem for processes with independent increments. Stochastics 79, 393–406.CrossRefGoogle Scholar
[17] Piunovskiy, A. B. (1997). Optimal Control of Random Sequences in Problems with Constraints (Math. Appl. 410). Kluwer, Dordrecht.CrossRefGoogle Scholar
[18] Piunovskiy, A. B. (1998). Controlled random sequences: methods of convex analysis and problems with functional constraints. Russian Math. Surveys 53, 1233–1293.CrossRefGoogle Scholar
[19] Piunovskiy, A. B. (2005). Discounted continuous time Markov decision processes: the convex analytic approach. In Proc. 16th Triennial IFAC World Congress (Praha, Czech. Republic).CrossRefGoogle Scholar
[20] Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley, New York.CrossRefGoogle Scholar
[21] Rieder, U. (1975). On stopped decision processes with discrete time parameter. Stoch. Process. Appl. 3, 365–383.CrossRefGoogle Scholar
[22] Schäl, M. (1975). On dynamic programming: compactness of the space of policies. Stoch. Process. Appl. 3, 345–364.CrossRefGoogle Scholar