We briefly review the main ingredients of Markov Decision Problems or MDPs, which, as we discuss in Chapter 6, can be viewed as single-agent stochastic games. The literature on MDPs is rich, and the reader is referred to the many textbooks on the subject for further reading.

The model

An MDP is a model for decision making in an uncertain, dynamic world. The (single) agent starts out in some state, takes an action, and receives some immediate rewards. The state then transitions probabilistically to some other state and the process repeats. Formally speaking, an MDP is a tuple (S,A,p,R). S is a set of states and A is a set of actions. The function p : S × A × S ↦ ℝ specifies the transition probability among states: p(s, a, s′) is the probability of ending in state s′ when taking action a in state s. Finally, the function R : S × A ↦ ℝ returns the reward for each state-action pair.