MDP — Markov Decision Process

Core Concept

An MDP is a formal model for making a sequence of decisions in an uncertain world. At each step, an agent sees a state, chooses an action, and the environment responds with a reward and a new state. The "Markov" property means the future depends only on the present state, not the full history. Solving an MDP means finding the policy that maximizes long-run reward.

Key Components

States & Actions (S, A)

The situations the agent can be in, and the choices available in each.

Transition P(s′|s,a)

The probability of landing in state s′ after taking action a in state s.

Reward R & Discount γ

Immediate feedback for each step; γ (0–1) weights future vs. present reward.

Policy π & Value V

π maps states→actions; V(s) is the expected total reward from state s onward.

How It Works

Define the tuple (S, A, P, R, γ) that describes your problem.
The agent follows a policy π: observe state → pick action → get reward + next state.
Evaluate each state's worth with the Bellman equation, which links a state's value to its successors' values.
Improve the policy by acting greedily on those values — repeat until it stops changing.
This loop is value iteration / policy iteration: dynamic programming that converges to the optimal policy π*.

Bellman optimality:
V*(s) = max_a [ R(s,a) + γ · Σ_s′ P(s′|s,a) · V*(s′) ]

Optimal policy: π*(s) = argmax_a [ R(s,a) + γ · Σ_s′ P(s′|s,a) · V*(s′) ]

Real-World Applications

🤖 Robotics & motion planning 🎮 Game-playing agents (RL) 📦 Inventory & supply chains 💊 Treatment-decision policies 🚗 Autonomous navigation 📈 Portfolio & resource allocation

Checkpoint Questions

What is a policy, and what does the value function represent about a state?
Why does the discount factor γ matter — what changes as γ moves from near 0 toward 1?
In plain words, what is the Bellman equation saying about how a state's value relates to its neighbors?

Markov Decision Process (MDP)