Markov Decision Process (MDP)

A Markov Decision Process (MDP) is a compact way to describe a situation where an agent repeatedly chooses actions, the world responds, and the agent receives rewards. It gives reinforcement learning a precise picture of what “learning to act” means, from a robot choosing movements to a game-playing agent choosing its next move.

The pieces of the decision problem
An MDP is commonly written as (S, A, P, R, γ):

States (S): the information describing the current situation.
Actions (A): choices available to the agent.
Transitions (P): probabilities governing the next state after an action.
Rewards (R): immediate feedback for a transition or action.
Discount factor (γ): how much future reward counts relative to reward now.

The word Markov carries the central assumption: once the current state is known, the future does not depend on the earlier history. In other words, a good state contains all the information needed for choosing well. An agent’s policy maps states to actions, and RL seeks a policy that maximizes expected discounted total reward, not merely the next reward.

Why this structure matters
Consider a navigation agent in a Gymnasium maze. Moving toward a shiny coin might give an immediate reward, while taking a longer corridor reaches the exit and yields far more reward later. The MDP makes that delayed trade-off explicit through transitions, rewards, and discounting. Algorithms such as DQN estimate action values from this structure; PPO improves a policy by collecting trajectories from it.

Where reality pushes back
An MDP is only as useful as its state representation. If a driving agent sees a camera frame but cannot infer another car’s speed, the frame is not truly Markov: relevant history is missing. Its value estimates can become inconsistent because identical-looking “states” lead to different futures. Agents then use frame stacks, recurrent networks, or belief states to approximate the missing information. The MDP is therefore both a mathematical model and a practical test: does the agent observe enough to make today’s decision without needing to remember everything?

A Markov Decision Process (MDP) is a formal model for sequential decision-making, defined by states, actions, transition probabilities, rewards, and a discount factor. Its Markov property states that the current state contains all information needed to predict the next state and reward given an action. MDPs define the objective of finding a policy that maximizes expected cumulative reward, providing the foundation for value functions and RL algorithms.

Think of learning to drive in a new city. At each intersection, you look at where you are, choose a turn, and then see what happens: perhaps you get closer to your destination, hit traffic, or take a wrong road. A Markov Decision Process (MDP) is a simple way of describing this kind of situation for an AI.

It lays out the important pieces: the current situation, the choices available, what may happen after each choice, and the rewards or setbacks that follow. The key idea is that the current situation contains the information needed to make a sensible next decision. An MDP gives AI researchers a clear picture of the decision-making world an agent is learning to navigate.