Markov decision process

Also known as: MDP

On this page 7

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.

ElementDefinitionPractical question it answers
State space SAll situations the agent can be inWhat information describes the situation?
Action space AAll choices available to the agentWhat can the agent actually do?
Transition function PP(s′ | s, a), probability of the next stateHow does the environment respond?
Reward function RR(s, a) or R(s, a, s′), a scalar signalWhat outcome is desirable?
Discount factor γA number in [0, 1]How much do future rewards matter?
Elements of the MDP tuple

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.

SettingHorizon and objectiveTypical example
Episodic, finite horizonFixed number of steps, often γ = 1A board game or one delivery route
Infinite horizon, discountedEndless, discount factor below 1Inventory control, recommendation
Average rewardEndless, long-run reward per stepNetwork routing, queue management
Continuous state and actionReal-valued vectors, any objectiveRobot arm torque control
Common MDP settings and how they differ

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.

ApproachRequires a modelRepresentative methods
Dynamic programmingYes, exact P and RValue iteration, policy iteration
Linear programmingYes, exact P and RLP formulation of the Bellman optimality conditions
Model-free value-based learningNoQ-learning, SARSA, deep Q-network
Model-free policy optimizationNoREINFORCE, actor-critic, PPO
Model-based learning and planningLearned from dataDyna-style methods, Monte Carlo tree search
Solution approaches for an MDP

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.

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.

MistakeSymptomFix
Non-Markov stateUnstable learning, contradictory valuesAdd history, velocity or memory to the state
Misaligned rewardAgent exploits loopholesRedesign the reward, test for reward hacking
Sparse rewardNo learning signal for long periodsCareful reward shaping or curriculum
Discount factor too lowShort-sighted, greedy behaviorRaise γ to match the real horizon
Oversized action spaceSlow exploration, poor coverageRestrict or factor the actions
Modeling mistakes, symptoms and fixes

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.