Markov Decision Process

Definition

A Markov Decision Process (MDP) is a mathematical framework for modeling sequential decision-making, defined by states, actions, transition probabilities, and rewards, used as the formal foundation of reinforcement learning.

Overview

An MDP formalizes an agent interacting with an environment over discrete time steps: at each step the agent observes a state, chooses an action, receives a reward, and the environment transitions to a new state according to a probability distribution that depends only on the current state and action — the Markov property. Formally, an MDP is the tuple (S, A, P, R, γ), where S is the state space, A the action space, P the transition function, R the reward function, and γ a discount factor that weighs future rewards against immediate ones. The goal in an MDP is to find a policy — a mapping from states to actions — that maximizes expected cumulative discounted reward. The value function and the Bellman equation are central tools for this: they express the value of a state (or state-action pair) recursively in terms of immediate reward plus the discounted value of successor states, which is what makes dynamic-programming methods like value iteration and policy iteration possible when the model is fully known. When the transition and reward functions are unknown, reinforcement learning algorithms such as Q-learning, SARSA, and policy gradient methods estimate optimal behavior directly from experience rather than from a known model. MDPs also generalize to partially observable MDPs (POMDPs) when the agent cannot fully observe the state, which connects the framework back to hidden-state models like HMMs. The MDP formalism underlies applications from robotics and game-playing agents like AlphaGo to resource allocation, inventory management, and recommendation systems, anywhere a sequence of decisions must be optimized under uncertainty.

Key Concepts

• Formal tuple of states, actions, transition probabilities, rewards, and discount factor
• Markov property — transitions depend only on the current state and action
• Policies map states to actions to maximize expected cumulative reward
• Bellman equation provides a recursive definition of state and action values
• Value iteration and policy iteration solve MDPs when the model is known
• Discount factor balances immediate versus future rewards
• Extends to partially observable MDPs (POMDPs) for hidden-state settings
• Foundational formalism underlying modern reinforcement learning

Use Cases

Frequently Asked Questions

Related in AI Fundamentals