AI Glossary / AI and machine learning / Advanced
Markov decision process
Definition
A Markov decision process is the standard mathematical frame for sequential decisions under uncertainty: states, actions, transition probabilities and rewards, with the next state depending only on the current state and action.
What it means
The frame answers a specific kind of question: what should an agent do now, when today's action changes tomorrow's situation. Inventory, routing, pricing and maintenance all have this shape.
Its pieces are plain: a set of states describing where things stand, actions available in each state, probabilities for where an action lands you next, and rewards that score each step. A policy, the answer, maps states to actions.
The Markov part is the simplifying promise: the future depends on the present state, not on the history behind it. That promise keeps the mathematics tractable and is also the frame's main honesty test.
Solving one means finding a policy that maximizes long-run reward, typically with value iteration or reinforcement learning. The solution balances immediate reward against future position, which is the genuinely hard trade in sequential decisions.
For a business, the value is often the framing itself: forcing a fuzzy sequential problem into states, actions, transitions and rewards exposes what is known, what is guessed and what is missing.
How it works
Define states that capture everything relevant about the current situation, and only that, honoring the Markov promise.
List the actions available in each state, including the passive ones like waiting.
Estimate transition probabilities: given state and action, where does the process land next, with what chances.
Assign rewards to steps, encoding both immediate gains and costs, and choose a horizon and a discount rate.
Solve for a policy with dynamic programming or learn one by reinforcement learning, then stress-test it against the assumptions that built it.
Three practical examples
- A warehouse restocking problem: states are stock levels, actions are order quantities, transitions follow demand, rewards are margin minus holding cost.
- A ride-hailing dispatch problem: states are driver locations, actions are assignments, and rewards combine pickup speed with future coverage.
- A maintenance planner: states are machine condition grades, actions are run, inspect or overhaul, and rewards are uptime minus repair cost.
Think of it this way
Think of a board game where your position on the board, not the path you took to reach it, decides your legal moves and your chances: the whole history is summarized in the current square.
Worked example
a two-state inventory policy
Suppose a shop's stock is either low or adequate, demand is uncertain, and the owner can order or wait. The figures are illustrative.
Ordering from low costs a fixed fee but avoids stockouts; waiting saves the fee but risks an empty shelf with a known probability.
Solving the small process shows ordering from low and waiting when adequate maximizes long-run margin, and the discount rate decides how much tomorrow's stockouts weigh against today's fees.
The policy is a simple rule, but it came from the frame: states, actions, transitions and rewards made the trade-off computable instead of instinctive.
Illustrative case study
A fictional delivery firm modeled its fleet as a Markov decision process with states so coarse that two very different situations, rush hour and midnight, shared one state.
The learned policy behaved oddly at the boundaries, because the Markov promise was false for the chosen states: history mattered and had been discarded.
The invented lesson: the frame is only as honest as its states. When the present does not summarize the past, enrich the state before blaming the solver.
Common misconceptions and mistakes
- It requires perfect probability estimates. Estimates can be rough; the frame still disciplines thinking, and sensitivity checks show where precision matters.
- It is only for robotics and games. Any repeated decision under uncertainty, inventory, staffing, pricing, has the same shape.
- The Markov promise is a fact about the world. It is a modeling choice: true or false depending on how richly you define the state.
- More states always help. Each state adds estimation burden; the right state space is the smallest one that keeps the Markov promise honest.
Business use
Use the frame in planning workshops: naming states, actions, transitions and rewards clarifies fuzzy sequential problems fast.
Test the Markov assumption before solving: if history clearly matters beyond the state, the state is too poor.
Prefer a small honest model over a large false one; a two-state policy you trust beats a thousand-state policy built on guesses.
When buying reinforcement learning, ask how the vendor defined states and rewards before asking about the algorithm.
People also ask
What does the Markov promise say?
That the next state depends only on the current state and action, not on how the process arrived there.
What is a policy?
A rule mapping each state to the action to take in it; solving the process means finding the best policy.
How is this different from reinforcement learning?
The process is the problem's frame; reinforcement learning is one way to solve it when transitions are unknown.
Do I need the math to benefit?
No: structuring a decision into states, actions, transitions and rewards is valuable even without solving it formally.
What does the discount rate do?
It sets how much future rewards count against immediate ones, encoding how patient the decision-maker is.
Check your understanding
What makes a problem fit the Markov decision process frame?
Answer: A sequence of decisions where each action changes the situation, outcomes are partly uncertain, rewards accumulate over time, and a state can be defined that summarizes everything relevant about the present.
Related terms
Learn next
AI for Business Owners shows how to turn structured decision framing into better vendor and build choices: https://aiforbusinessandlife.com/academy/ai-for-business-owners. [C2]
More in AI and machine learning
- Manifold regularization - Manifold regularization is a learning framework that encourages a prediction function to vary smoothly along the geometric structure inferred from data.
- Margin classifier - A margin classifier is a classifier whose predictions or training objective use a margin separating the correct class from a decision boundary or competing...
- Margin-infused relaxed algorithm - The margin-infused relaxed algorithm, or MIRA, is an online learning algorithm introduced by Crammer and Singer for classification.
- Markov random field - A Markov random field, or MRF, is an undirected probabilistic graphical model that represents conditional-dependence structure among variables.
- Matrix regularization - Matrix regularization is the use of penalties or constraints to control the structure of a matrix estimated from data.
- Matrix semantics - Matrix semantics is the discipline of keeping track of what the rows, columns and cells of a data matrix mean: which axis is which entity, in which units...
Sources
[S1] Russell and Norvig, AIMA glossary; [S11] Murphy, Probabilistic Machine Learning: An Introduction. Full URLs are in the source ledger. Verified 11 October 2026.
Previous: Markov chain Monte Carlo Next: Markov localization