Markov decision process

A Markov decision process (MDP) is a mathematical model of an agent making a sequence of decisions in an environment whose next state depends only on the current state and action. It is the formal setting in which almost all of reinforcement learning is defined, analysed and solved.

Definition

An MDP is a tuple $(\mathcal{S},\mathcal{A},P,R,\gamma )$: a set of states $\mathcal{S}$, a set of actions $\mathcal{A}$, a transition function, a reward function and a discount factor $\gamma \in [0,1)$. The transition function gives the probability of each next state:

and $R(s,a)$ is the expected reward for taking action $a$ in state $s$. The word "Markov" refers to the assumption that this probability does not depend on anything earlier than $(S_t,A_t)$. An agent acts through a policy $\pi (a\mid s)$, and the goal is to find a policy that maximises the expected discounted return ${\mathbb{E}}_{\pi }\left[{\sum }_t{\gamma }^t{R}_{t+1}\right]$.

Worked example

A cleaning robot has two states, charged and low, and two actions, clean and dock. Cleaning while charged earns reward 2 and leaves the battery charged with probability 0.7, otherwise it drops to low. Cleaning while low earns 2 with probability 0.6 and strands the robot (reward $-10$) with probability 0.4. Docking earns 0 and always returns the robot to charged. The expected immediate reward of cleaning when low is $0.6\times 2+0.4\times (-10)=-2.8$, so a sensible policy docks when low and cleans when charged. Writing the problem down this way turns "be a good robot" into something you can compute with.

Common variants

• Finite-horizon MDPs stop after $H$ steps and often use $\gamma =1$.
• POMDPs hide the state behind observations (see state).
• Constrained MDPs add cost functions with budgets, the usual formalism for safe RL.
• Bandits are MDPs with a single state (see multi-armed bandit).

Why it matters

The MDP is what makes reinforcement learning precise. Once a problem is an MDP, the Bellman equations hold, optimal policies exist, and algorithms such as value iteration, Q-learning and policy gradients come with guarantees. It is also where many real failures start: if the reward function $R$ leaves out something you care about, the optimal policy of the MDP you wrote is not the behaviour you wanted. Most of the safety questions in RL are questions about whether the written MDP matches the intended one.

Related terms

• State
• Action
• Policy
• Bellman equation
• Constrained MDP (CMDP)
• Discount factor

Sources

1. Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net
2. Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994. doi.org