What Is a Markov Decision Process?

Why we need a formal blueprint

Before you can train an agent, you have to describe the problem precisely enough that a computer can reason about it. Reinforcement learning borrows one tidy description for almost everything: the Markov decision process (MDP). An MDP is the mathematical container that holds a world, an agent's choices, and the consequences of those choices. Once a problem is written as an MDP, a huge toolbox of algorithms suddenly applies to it.

Think of the MDP as the rules of a board game written down in full: which squares exist, which moves are legal, what happens when you make a move, and how points are scored. The MDP does the same job for sequential decision problems, from a robot crossing a room to a recommender choosing what to show next.

The five pieces

An MDP is usually written as a tuple of five things. None of them is hard on its own; the power comes from how they click together.

1. States — the state space is the set of all situations the world can be in. A chess position, a robot's pose, a customer's profile.
2. Actions — the action space is what the agent can do in a state: move left, place a piece, recommend item #7.
3. Transitions — the transition dynamics say what state you land in after taking an action. Often this is random: the same move can lead to different outcomes.
4. Rewards — the reward function hands out a number after each step, encoding what we want. Plus for reaching a goal, minus for crashing.
5. Discount — the discount factor (γ) controls how much future rewards matter compared to immediate ones. We give it a guide of its own.

That's the whole formalism: a state space, an action space, transitions, a reward function, and a discount. Five pieces, and you can describe most of the problems people throw at RL.

The whole MDP as one tuple: a state space 𝒮, an action space 𝒜, transitions P, a reward R, and the discount γ — the five pieces.

A concrete example: a robot in a grid

Picture a 4×4 grid. A robot sits on a square (that's the state). It can move up, down, left, or right (the actions). Floors are slippery, so 'move right' lands it right 80% of the time and slips sideways 20% (the transitions — random!). It earns +10 on the exit square and −1 every other step to nudge it to hurry (the rewards).

states  = [(r, c) for r in range(4) for c in range(4)]
actions = ["up", "down", "left", "right"]

def reward(state):
    if state == (3, 3):   # the exit
        return +10
    return -1             # cost of dwelling

def transition(state, action):
    # returns a list of (next_state, probability)
    intended = move(state, action)
    sideways = [move(state, a) for a in slips(action)]
    return [(intended, 0.8), (sideways[0], 0.1), (sideways[1], 0.1)]

Everything an algorithm needs is now on the table. It doesn't need to understand robots or floors — only the transitions and rewards. That deliberate ignorance is exactly what makes one algorithm work across robots, games, and ads.

The quiet assumption that makes it work

Tucked inside the word 'Markov' is a strong promise: the Markov property. It says the current state already contains everything you need to predict the future — the whole past adds nothing once you know now. In the grid, where the robot stands tells you all the transition needs; how it got there is irrelevant.

This assumption is why the math stays clean. If the future depended on the entire history, every algorithm would drown in ever-growing records. The Markov property lets us reason one step at a time. The next guide is devoted to it — when it holds, when it secretly breaks, and how to design states so it holds on purpose.