Markov Decision Process (MDP)

• Also called: MDP
• Category: Learning & autonomy › RL & simulation
• Tags: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

The standard mathematical model of sequential decision making: states, actions, transition probabilities, rewards and a discount factor, with the next state depending only on the current state and action.

Definition

A Markov decision process (MDP) describes an agent that repeatedly observes a state, chooses an action, receives a reward and moves to a new state. It is usually written as a tuple (S, A, P, R, γ), often with an initial state distribution ρ₀: the state space, the action space, the transition probabilities P(s′ | s, a), the reward function R(s, a), and a discount factor γ between 0 and 1 that weights future rewards against immediate ones. The defining assumption is the Markov property: the distribution of the next state depends only on the current state and action, not on the history that led there. Richard Bellman's work on dynamic programming in the 1950s established the framework.

The goal in an MDP is a policy, a mapping from states to actions (or to distributions over actions), that maximizes the expected discounted sum of rewards. The value function V(s) and the action-value function Q(s, a) give that expected return from a state, or from a state and action, under a policy. They satisfy the Bellman equations, which express the value of a state as the immediate reward plus the discounted value of the states that follow. When P and R are known and the state space is small, value iteration and policy iteration solve the MDP exactly. When they are unknown, or the spaces are large and continuous, reinforcement learning estimates values and policies from sampled experience.

MDPs are the formal basis for almost all of reinforcement learning, and a large share of planning under uncertainty. Many variants relax one of the assumptions: a partially observable MDP (POMDP) drops the assumption that the agent sees the true state; constrained MDPs add cost limits; semi-MDPs allow actions that take variable time; and multi-agent extensions such as Markov games model several decision makers. Choosing what goes into the state is an engineering decision: if important information such as velocities, contact status or the intent of other agents is left out, the process is no longer Markov from the agent's point of view.

Why it matters

Every reinforcement learning paper and most decision-making methods in robotics state their problem as an MDP or a variant of one. Knowing the parts of the tuple, and which assumption each method relies on, makes it possible to read those papers, design states and rewards for a real robot, and recognize when a problem is really partially observable.

Key applications

• Formulating reinforcement learning problems for manipulation and locomotion
• Planning under uncertainty with value iteration and policy iteration
• Reward design and inverse reinforcement learning, which infer or shape R
• Model-based reinforcement learning, which learns the transition function P
• Modeling interaction with other agents through Markov games and latent intent variables

In practice

A team training a robot arm to push a block to a target frames the task as an MDP. The state contains the joint angles and velocities, the block pose and the target position; the action is a change in end-effector position each control step; the reward is the negative distance from block to target with a bonus on success; and γ is set close to 1 because the task spans many steps. In early tests the policy behaves erratically when the block is moving, because the state includes the block pose but not its velocity. Adding the block velocity, or stacking the last few observations, restores the Markov property closely enough for a standard algorithm such as SAC or PPO to learn reliably.

Common misconceptions

• An MDP requires discrete states and actions — continuous state and action spaces are common in robotics, with sums replaced by integrals and tabular methods replaced by function approximation
• The Markov property is a fact about the world — it is a property of the chosen state; leaving out velocities or hidden variables can make a physical system non-Markov from the agent's point of view
• The discount factor only reflects impatience — it also bounds the return in infinite-horizon problems and affects the variance and stability of learning, so it is often tuned like a hyperparameter
• Solving an MDP needs a model of P — reinforcement learning methods find good policies from sampled transitions without ever writing P down

Who should know this

• Reinforcement learning practitioners and researchers
• Robot learning engineers designing states, actions and rewards
• Planning and decision-making researchers
• Robotics students starting with robot learning

Related technologies

• Bellman Equation
• Value Iteration
• Policy Iteration
• Q-Learning
• Gymnasium
• Dynamic Programming

Related terms

• Reinforcement Learning
• Partially Observable Markov Decision Process (POMDP)
• Hamilton-Jacobi-Bellman Equation (HJB)
• Inverse Reinforcement Learning
• Offline Reinforcement Learning
• Proximal Policy Optimization

Related projects

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• MuJoCo: DeepMind physics engine for robotics and ML research
• PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
• OpenPI: Physical Intelligence VLA foundation models for general robot control
• Microduck: Pollen Robotics' $399 walking duck robot: open-source software, closed hardware
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim

Videos

• Markov Decision Processes - Computerphile: Computerphile