Markov Decision Process (MDP)

A Markov decision process (MDP) is the mathematical model of a sequential decision problem: an agent observes a state, chooses an action, receives a reward, and lands in a next state that depends partly on its choice and partly on chance. Formally, an MDP consists of a set of states, a set of actions, transition probabilities P(s′ | s, a), a reward function R(s, a), and usually a discount factor γ between 0 and 1. Solving it means finding a policy, a rule that picks an action in every state, that maximizes the expected discounted sum of future rewards. MDPs came out of operations research in the 1950s, where Richard Bellman's dynamic programming supplied the methods to solve them, and they are the standard problem statement for reinforcement learning (RL).

The Markov Property#

The defining assumption is the Markov property: the next state and reward depend only on the current state and action, not on the path that led there. That makes the state the agent's complete summary of everything relevant. A single camera frame breaks the assumption for a moving object, because it shows position but not velocity, so DeepMind's Atari-playing DQN fed its network the last four frames stacked together to let it see motion.

When the agent cannot observe the full state, as with a robot whose sensors are noisy or occluded, the problem is a partially observable MDP (POMDP). The agent then acts on a belief about the state, maintained with a filter or a recurrent network, instead of on the state itself.

Components of an MDP#

• States: The situations the agent can be in, such as a robot's joint angles and the position of the object it is reaching for.
• Actions: The choices available in each state. The action space can be discrete (turn left, turn right) or continuous (a steering angle in degrees).
• Transition probabilities: The chance of each next state after an action, which captures slipping wheels, other drivers, and every other source of randomness.
• Rewards: The immediate numeric feedback for a transition. The designer's choice of rewards defines the task, and a careless one invites reward hacking.
• Discount factor: How much future rewards count relative to immediate ones. With γ = 0.9, a reward ten steps away is worth 0.9¹⁰ ≈ 0.35 of the same reward now.

Every time step repeats the same interaction until the episode ends:

Solving an MDP#

The value of a state is the expected return from it under a policy, and the optimal values satisfy the Bellman equation: each state's value equals the best action's immediate reward plus the discounted, probability-weighted value of the states it leads to. When the transition probabilities and rewards are known, dynamic programming solves that equation directly. Value iteration (Bellman, 1957) applies it repeatedly until the values stop changing, and policy iteration (Howard, 1960) alternates between evaluating a policy and improving it.

This NumPy example runs value iteration on the recycling robot from Sutton and Barto's Reinforcement Learning: An Introduction, a robot that must choose between searching for cans, waiting, and recharging on a high or low battery:

import numpy as np

# Recycling robot MDP: states 0 = high battery, 1 = low battery; actions 0 = search, 1 = wait, 2 = recharge
gamma = 0.9  # discount factor
P = np.zeros((2, 3, 2))  # P[s, a, s'] = probability of reaching s' after taking a in s
P[0, 0] = [0.7, 0.3]  # searching on a high battery may drain it to low
P[1, 0] = [0.4, 0.6]  # searching on a low battery may run it flat (robot is rescued and recharged)
P[:, 1] = np.eye(2)  # waiting keeps the battery level unchanged
P[:, 2] = [1.0, 0.0]  # recharging always restores a high battery
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # expected R[s, a]; low-battery search: 0.6 * 2 + 0.4 * -3 = 0

# Value iteration: apply the Bellman optimality update until the values stop changing
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # value of each action in each state
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

It prints values of 15.75 for a high battery and 14.17 for a low one, and a policy that searches on a high battery and recharges on a low one: the 40% risk of a −3 rescue penalty makes searching on a low battery worth less than recharging.

When the transition probabilities are unknown, reinforcement learning estimates the same values from experience. Q-learning updates action values from sampled transitions, policy-gradient methods adjust a policy directly, and deep reinforcement learning uses neural networks when the state space is too large to list. Planning algorithms such as Monte Carlo tree search solve huge MDPs online by simulating only the futures reachable from the current state.

MDPs vs. Related Models#

• Markov chain: A sequence of random states with no actions or rewards. An MDP adds the choices and the objective.
• Hidden Markov model (HMM): A Markov chain whose states are observed only through noisy signals. A POMDP stands in the same relation to an MDP.
• Multi-armed bandit: An MDP with a single state, where each action pays off independently of the past.
• Reinforcement learning: The family of methods that learn to act well in an MDP from interaction, without being given its transition probabilities.

Applications#

• Robotics and control: Grasping, walking, and navigation are formulated as MDPs, and their policies are often trained in simulation. In camera-based control, a detector such as Ultralytics YOLO26 can supply the state, turning each frame into a short list of object classes and box coordinates, a far smaller input for the policy than raw pixels.
• Language model training: RLHF and RLVR treat text generation as an MDP whose state is the prompt plus the tokens so far, whose action is the next token, and whose reward arrives when the response is complete.
• Operations research: Inventory reordering, equipment maintenance, and dynamic pricing are classic MDPs, and Ronald Howard developed policy iteration while optimizing Sears catalog mailings.