A Markov decision process (MDP) is a mathematical framework for sequential decision-making under uncertainty, in which an agent observes a state, chooses an action, receives a reward and moves to a new state according to fixed transition probabilities. In reinforcement learning, the MDP is the standard problem definition: algorithms from value iteration to proximal policy optimization are all methods for finding a good policy in some MDP, whether its dynamics are known or must be learned from experience.
The framework originates in operations research and optimal control and remains central to artificial intelligence because it separates what the problem is from how it is solved. Writing a task as an MDP forces precise answers to four questions: what the agent can observe, what it can do, how the world responds and what counts as success.
The components of a Markov decision process
An MDP is usually written as the tuple (S, A, P, R, γ). Each element has a precise role, and most modeling mistakes trace back to an element that was defined loosely. The table below lists them.
| Element | Definition | Practical question it answers |
|---|---|---|
| State space S | All situations the agent can be in | What information describes the situation? |
| Action space A | All choices available to the agent | What can the agent actually do? |
| Transition function P | P(s′ | s, a), probability of the next state | How does the environment respond? |
| Reward function R | R(s, a) or R(s, a, s′), a scalar signal | What outcome is desirable? |
| Discount factor γ | A number in [0, 1] | How much do future rewards matter? |
The defining assumption is the Markov property: the next state and reward depend only on the current state and action, not on the earlier history. The state therefore must be a sufficient summary of the past. When that summary is incomplete, for example when a robot sees only one camera frame and cannot infer velocity, the problem becomes a partially observable Markov decision process instead.
Policies, returns and value functions in an MDP
A policy π maps states to actions or to probability distributions over actions. The goal is to find a policy that maximizes the expected cumulative reward, called the return, typically the discounted sum G = r₁ + γr₂ + γ²r₃ + …. With γ below 1, the return stays finite even in endless tasks, and the effective planning horizon is roughly 1 / (1 − γ) steps, so γ = 0.99 corresponds to about 100 steps.
Two functions evaluate a policy. The state-value function V(s) gives the expected return from state s, and the action-value function Q(s, a), or Q-function, gives the expected return after taking action a in s. Both satisfy the Bellman equation, which expresses a value as the immediate reward plus the discounted value of the successor state. A fundamental result guarantees that every finite MDP has at least one optimal deterministic stationary policy, which is why searching for a single best rule per state is well founded.
| Setting | Horizon and objective | Typical example |
|---|---|---|
| Episodic, finite horizon | Fixed number of steps, often γ = 1 | A board game or one delivery route |
| Infinite horizon, discounted | Endless, discount factor below 1 | Inventory control, recommendation |
| Average reward | Endless, long-run reward per step | Network routing, queue management |
| Continuous state and action | Real-valued vectors, any objective | Robot arm torque control |
How Markov decision processes are solved
Solution methods split according to whether the transition and reward functions are known. When they are known and the state space is small, dynamic programming computes the optimal policy exactly. When they are unknown, reinforcement learning estimates values or policies from sampled interaction.
| Approach | Requires a model | Representative methods |
|---|---|---|
| Dynamic programming | Yes, exact P and R | Value iteration, policy iteration |
| Linear programming | Yes, exact P and R | LP formulation of the Bellman optimality conditions |
| Model-free value-based learning | No | Q-learning, SARSA, deep Q-network |
| Model-free policy optimization | No | REINFORCE, actor-critic, PPO |
| Model-based learning and planning | Learned from data | Dyna-style methods, Monte Carlo tree search |
Exact methods scale polynomially in the number of states and actions, but the number of states grows exponentially with the number of state variables. This curse of dimensionality is why practical systems replace tables with function approximation, usually neural networks, at the price of losing the convergence guarantees of the tabular case.
Related models and extensions
The MDP sits in a family of models that relax or tighten its assumptions. Choosing the right one avoids forcing a problem into a framework that misrepresents it.
- Markov chain: states and transitions without actions or rewards; an MDP with a fixed policy reduces to one.
- Contextual bandit: a one-step MDP in which actions do not influence future states.
- Partially observable MDP (POMDP): the agent receives observations instead of states and must maintain a belief over states.
- Semi-Markov decision process: actions take variable time, which underpins options in hierarchical reinforcement learning.
- Markov game: several agents act at once, the basis of multi-agent reinforcement learning.
- Constrained MDP: the agent maximizes reward subject to cost limits, a common formulation in safe reinforcement learning.
Modeling pitfalls and limitations
Most failures of reinforcement learning projects begin with a poorly specified MDP, not with the learning algorithm. The table below lists frequent symptoms and their remedies.
| Mistake | Symptom | Fix |
|---|---|---|
| Non-Markov state | Unstable learning, contradictory values | Add history, velocity or memory to the state |
| Misaligned reward | Agent exploits loopholes | Redesign the reward, test for reward hacking |
| Sparse reward | No learning signal for long periods | Careful reward shaping or curriculum |
| Discount factor too low | Short-sighted, greedy behavior | Raise γ to match the real horizon |
| Oversized action space | Slow exploration, poor coverage | Restrict or factor the actions |
The framework also assumes stationary dynamics. If the environment changes over time, as markets and user behavior do, a policy optimal for yesterday’s transition function can degrade quietly, so deployed systems need monitoring and periodic retraining.
Understanding it simply
A Markov decision process is a way of describing a choice-making problem precisely so that a computer can learn to solve it. It lists where you can be, what you can do, what tends to happen next and how good or bad each result is.
Picture a board game. Your position on the board is the state, your move is the action, the dice decide where you land, and points are the reward. The rule is that only the current position matters, not how you got there. Learning a good strategy means learning which move works best from every square.
Applied in practice
A regional warehouse operator wants to automate daily restocking of 40 fast-moving products. The engineers model the task as an MDP: the state holds current stock, open orders and the day of the week; the action is the order quantity per product; transitions follow observed demand; and the reward is sales margin minus holding and stockout costs, discounted with γ = 0.97.
Because the demand history covers three years, they first fit a demand model and apply value iteration on a simplified version to obtain a baseline policy, then refine it with a model-free actor-critic method in a simulator. After a two-month pilot on half of the products, stockouts fall by roughly a third while average inventory stays flat, and the operator extends the policy to the remaining products with weekly retraining.