Markov decision process

A Markov decision process is the formal board game that reinforcement learning is played on. It pins down five things: the set of situations you can be in (states), the moves you can make (actions), the rule for which situation comes next after a move (transitions, possibly random), the score each move earns (rewards), and how much you care about the future versus now (the discount). Once a problem is written this way, the whole machinery of RL clicks into place.

The defining feature — the 'Markov' part — is a memorylessness assumption: the next state depends only on the current state and action, not on the entire history of how you got here. In a board game like chess this is literally true: the current arrangement of pieces tells you everything you need; it doesn't matter in what order they arrived. This assumption is what makes the math tractable, because the agent only ever has to look at 'where am I now,' not 'everything that ever happened.'

The honest catch is that the real world is rarely so polite. A self-driving car's single camera frame doesn't tell you another car's speed — you need the previous frames too, so the snapshot alone isn't 'Markov.' Practitioners patch this by stuffing more into the state (stacking several frames, adding velocity) until it behaves Markov-enough. When you genuinely can't see the full state, the problem becomes a 'partially observable' MDP, which is markedly harder.