Markov decision processes

Markov decision processes (MDPs), also known as controlled Markov chains, constitute a basic framework for dynamically controlling systems that evolve in a stochastic way. MDPs are thus a generalization of (non-controlled) Markov chains, and many useful properties of Markov chains carry over to controlled Markov chains. In deterministic models, where the transition probabilities are only zero or one, the controller can fully predict the evolution of the state of the system as a result of applying a sequence of actions, if it knows the initial state. This chapter concludes that the Markov policies are sufficiently rich so that a cost that can be achieved by an arbitrary policy can also be achieved by a Markov policy.