Dynamic programming in constrained Markov decision

• Autorzy: Piunovskiy A. B.
• Języki publikacji: EN

Abstrakty

EN

We consider a discounted Markov Decision Process (MDP) supplemented with the requirement that another discounted loss must not exceed a specified value, almost surely. We show that he problem can be reformulated as a standard MDP and solved using the Dynamic Programming approach. An example on a controlled queue is presented. In the last section, we briefly reinforce the connection of the Dynamic Programming approach to another close problem statement and present the corresponding example. Several other types of constraints are discussed, as well.

Słowa kluczowe

EN

Markov decision process (MDP); constraints; optimization; dynamic programming; myopic control strategy; queuing system

PL

optymalizacja; programowanie dynamiczne; system kolejek

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 645--660
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Piunovskiy A. B.

• Department of Mathematical Sciences M & O Building, The University of Liverpool, Liverpool, L69 7ZL, UK,

Bibliografia

• ALTMAN, E. (1999) Constrained Markov Decision Processes. Chapman and Hall, London.
• BERTSEKAS, D.P. and SHREVE, S.E. (1978) Stochastic Optimal Control. Academic Press, New York.
• CHEN, R. (2004) Constrained stochastic control with probabilistic criteria and search optimization. Preprints of the 43-th IEEE Conf. on Decision and Control, Bahamas.
• CHEN, R.C. and BLANKENSHIP. G.L. (2004) Dynamic programming equations for discounted constrained stochastic control. IEEE Trans, on Aut. Control 49, 699-709.
• FEINBERG, E.A. and SHWARTZ, A. (1995) Constrained Markov decision models with discounted rewards. Math, of Oper. Res. 20, 302-320.
• FEINBERG, E.A. and SHWARTZ, A. (1999) Constrained dynamic programming with two discount factors: applications and an algorithm. IEEE Trans, on Aut. Control 44, 628-631.
• KRAWCZYK, J.B. (1990) On variance constrained programming. Asia-Pacific J. of Oper. Res. 7, 190-206.
• PIUNOVSKIY, A.B. (1997) Optimal Control of Random Sequences in Problems with Constraints. Kluwer Academic Publishers, Dordrecht-Boston-London.
• PIUNOVSKIY, A.B. (1998) Controlled random sequences: the convex analytic approach and constrained problems. Russ. Math. Surveys 53, 1233-1293.
• PIUNOVSKIY, A.B. and MAO, X. (2000) Constrained Markov decision processes: the dynamic programming approach. Oper. Res. Letters 27, 119-126.
• SNIEDOVICH, M. (1980) A variance-constrained reservoir control problem. Water Resources Research 16, 271-274.
• TANAKA, K. (1991) On discounted dynamic programming with constraints. J. of Mathem. Anal, and Appl. 155, 264-277.
• YAKOWITZ, S. (1982) Dynamic programming applications in water resources. Water Resources Research 18, 673-696.