Markov Decision Processes
Also known as: MDP
Sequential decision framework with states, actions, transition probabilities, and rewards.
Markov Decision Processes (MDPs) are the mathematical framework for modeling sequential decision-making in stochastic environments where outcomes are partly random and partly under the control of a decision maker. An MDP is specified by: a set of states S; a set of actions A; transition probabilities P(s'|s,a) — probability of next state s' given current state s and action a; reward function R(s,a) — immediate reward for taking action a in state s; discount factor γ in [0,1] for valuing future vs immediate rewards. The Markov property — that transition probabilities depend only on current state and action, not on history — is the central simplifying assumption. Solving an MDP means finding an optimal policy — a mapping from states to actions — that maximizes expected discounted cumulative reward. The framework was substantially developed by Richard Bellman in his 1957 Dynamic Programming, introducing the Bellman equation and the principle of optimality, and elaborated by Ronald Howard's 1960 Dynamic Programming and Markov Processes. MDPs are foundational to operations research, control theory, and reinforcement learning (where the agent typically doesn't know transition probabilities or rewards in advance and must learn them through interaction). Modern reinforcement learning — Sutton and Barto's foundational Reinforcement Learning: An Introduction (1998, 2018), Q-learning (Watkins 1989), policy gradient methods, deep reinforcement learning (DeepMind's DQN 2013, AlphaGo 2016) — substantially builds on MDP foundations. Variants include Partially Observable MDPs (POMDPs, where the agent doesn't directly observe state), continuous-state and continuous-action MDPs, and risk-sensitive MDPs.
Core components
- States, actions, transition probabilities, rewards, discount factor
- Markov property (transition probabilities depend only on current state-action)
- Policy as state-to-action mapping
- Value functions (state value V, action value Q)
- Bellman equation and Bellman optimality equation
- Dynamic programming solutions (value iteration, policy iteration)
- Distinction from POMDPs (partial observability)
- Connection to reinforcement learning (where transitions and rewards are learned)
- Continuous-state and continuous-action variants
Primary use case
Foundation of modern reinforcement learning; operations research and stochastic optimization; control theory; foundation for substantial AI work including game-playing agents (AlphaGo, AlphaZero), robotics, autonomous vehicles, recommendation systems; medical decision-making (treatment policies under uncertainty); resource management and scheduling; foundation for many modern AI products and research directions.
Common criticisms
- Markov property assumption — that future depends only on current state, not on history — is often violated in real systems
- modeling problems as MDPs requires substantial state-space engineering that can be brittle
- high-dimensional state spaces face the 'curse of dimensionality' that classical dynamic programming can't handle
- reward specification (reward hacking, reward misspecification) is a substantial practical problem in reinforcement learning
- partial observability (POMDPs) substantially complicates the framework
- sample complexity for reinforcement-learning algorithms can be enormous
- transferring learned policies across environments is genuinely difficult
- commercial reinforcement-learning applications often face large gaps between simulation performance and real-world performance
- AI safety research has substantial concerns about reward misspecification and Goodhart's law in MDP-based agents
- the framework's clean mathematical structure can mask the substantial practical engineering required for real applications.
Lineage
- Child of
- Decision Theory
- Siblings
- Decision Theory, Bayesian Inference
- Derived from
- Decision Theory