Markov decision process (MDP)

Imagine a robot in a gridworld. At every moment it is in some situation, picks a move, lands somewhere new, and collects a small reward or penalty. A Markov decision process is just the bookkeeping that makes this precise: it is the standard mathematical box almost every reinforcement-learning problem is poured into.

Formally an MDP is a five-part tuple: a set of states S, a set of actions A, transition dynamics that say where each action lands you, a reward function giving the payoff, and a discount factor weighing the future. The agent's job is to choose actions, step by step, to maximise the total discounted reward it expects to collect.

The power of the formalism is that everything from playing chess to steering a power grid fits the same skeleton, so one set of algorithms can attack all of them. The cost is that you must commit to clean states, actions and rewards up front, and real problems rarely hand you those for free.