A Markov Decision Process is commonly represented by the tuple (S, A, P, R, γ). S represents the set of possible states, and A represents the available actions. P describes the probability of transitioning from one state to another after an action. R describes the reward associated with a transition or state-action pair, depending on the chosen convention. The discount factor γ determines how strongly future rewards contribute to the agent's objective. The defining Markov property states that the distribution of the next state depends on the current state and action, rather than the complete history, when the state representation is sufficient. An agent follows a policy to select actions. The optimal policy maximizes expected cumulative discounted reward. MDPs are useful for formalizing problems in robotics, scheduling, games, and resource management. In real applications, the transition probabilities may be unknown, which is why reinforcement learning algorithms attempt to learn useful policies through interaction. A partially observable problem is often modeled using a Partially Observable Markov Decision Process (POMDP), which explicitly accounts for incomplete observations.
Markov Decision Processes
A Markov Decision Process (MDP) is a mathematical framework for modeling sequential decision-making under uncertainty. It describes states, actions, transition probabilities, rewards, and a discount factor.
P(S_{t+1}=s' | S_t=s, A_t=a)
Explanation
Variables
| Symbol | Meaning |
|---|---|
S | Set of possible states |
A | Set of possible actions |
P | State transition probability function |
R | Reward function |
γ | Discount factor |
s | Current state |
a | Selected action |
s' | Possible next state |
Example or application
A robot navigating a grid has a set of possible positions as its states and four movement directions as actions. Because movement may be imperfect, choosing to move north could result in the robot moving north, remaining in place, or moving slightly sideways with different probabilities.
Text
An MDP represents a decision problem in which an agent chooses actions, the environment changes probabilistically, and rewards are received. It provides a formal foundation for many reinforcement learning algorithms.
Key Points
An MDP formally describes sequential decision-making.
Its main components are states, actions, transitions, rewards, and discounting.
The Markov property means the current state contains sufficient information for predicting the next state given an action.
Transition probabilities represent uncertainty in environmental outcomes.
A policy determines the agent's behavior.
POMDPs extend the framework to partially observable environments.
Applications
Robot navigation
Autonomous control
Inventory management
Scheduling and planning
Game-playing systems
Resource allocation
Learning Outcomes
Define a Markov Decision Process.
Identify the five main components of an MDP.
Explain the Markov property.
Understand state transition probabilities.
Distinguish an MDP from a partially observable MDP.
Practice Questions
What does MDP stand for?
What are the five components of an MDP?
What does the Markov property mean?
Why are transition probabilities important?
How does a POMDP differ from an MDP?
Related Concepts
Reinforcement Learning
Markov Property
Transition Probability
Reward Function
Policy
Partially Observable Markov Decision Process
Common Mistakes
Assuming that every transition is deterministic.
Confusing transition probabilities with rewards.
Believing that the Markov property means the environment cannot change.
Ignoring whether the chosen state representation contains sufficient information.
Confusing a policy with a transition model.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley.
- Sutton, R. S., and Barto, A. G. (2018). Reinforcement Learning: An Introduction, Second Edition. MIT Press.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning