Dynamic programming in constrained Markov decision processes

A discounted Markov Decision Process (MDP) is considered, supplemented with the requirement that the discounted loss must not exceed a specified value, almost surely. It is shown that the 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, a brief reinforcement is outlined of the connection between the Dynamic Programming approach and another close problem statement, and a corresponding example is presented. Several other types of constraints are discussed as well.