mathematics//decision theory//Markov decision process

A Markov decision process (MDP) is a model of chained decisions under uncertainty, made of states, actions, transition probabilities, a reward and a discount factor, in which each action changes where the system lands and therefore what it can do next; it is the frame behind optimal maintenance, inventory policies, mission planning and all of reinforcement learning. A warehouse robot choosing its route and when to recharge is the everyday picture: going for one more order now may leave it too far from the charger later.

A Markov decision process (MDP) is a model of chained decisions under uncertainty, made of states, actions, transition probabilities, a reward and a discount factor, in which each action changes where the system lands and therefore what it can do next; it is the frame behind optimal maintenance, inventory policies, mission planning and all of reinforcement learning. A warehouse robot choosing its route and when to recharge is the everyday picture: going for one more order now may leave it too far from the charger later.

Its parts are states sss, actions aaa, transitions P(s′∣s,a)P(s'\mid s,a)P(s′∣s,a) (the probability of landing in s′s's′ after doing aaa in sss), a reward R(s,a)R(s,a)R(s,a) and a discount factor γ∈[0,1)\gamma\in[0,1)γ∈[0,1) that says how much the future is worth against the present. A policy π(s)\pi(s)π(s) says what to do in each state, and the value function V(s)V(s)V(s) is the discounted reward expected from sss onward. The process is called Markov because the current state is all the past that matters: where you can go next depends only on where you are, and how you got there adds nothing.

A small case shows the whole machinery. A machine has five wear levels, from new to broken. Each shift you either keep producing, earning less the more worn it is and risking one more level of wear, or repair it, paying 150 euros to make it new. Producing earns 100, 90, 70 and 40 euros at levels 0 to 3, a broken machine loses 500, and each shift it wears one level with probability 0.2. Solved by value iteration with γ=0.95\gamma=0.95γ=0.95, the policy that comes out is to repair at level 3, one step before it breaks.

The optimal values satisfy the Bellman equation, the best immediate reward plus the discounted value of where the action leaves you, and the optimal policy falls out of it by taking the best action in each state. Value iteration and dynamic programming solve it when the model is known; Q-learning learns it from experience when it is not.

Lowering γ\gammaγ makes the agent myopic: rewards a few steps away fade, and the policy grabs what is close. It also speeds convergence, since every sweep of value iteration shrinks the error by a factor γ\gammaγ.

Fix the policy and the choice disappears: what is left is a Markov chain, whose long-run behaviour is that chain's stationary distribution. When the state cannot be seen, the process becomes a POMDP, decided on beliefs.

Its state is a decision state, chosen so that the Markov property holds for the purpose of choosing actions; it overlaps with the sufficient state of a dynamical model without being guaranteed to be the same thing. And it is exact only while the states are few, because the state count multiplies across variables (curse of dimensionality).