← AI Terminology
MDP - Markov Decision Process
A Markov Decision Process is a mathematical framework for sequential decision-making under uncertainty — defined by a set of states S, actions A, transition probabilities P(s'|s,a), and rewards R(s,a,s') — providing the formal foundation for reinforcement learning.
"Markov" means future states depend only on the current state, not history.
"Markov" means future states depend only on the current state, not history.
Why It Matters in AI
MDPs provide the mathematical language of reinforcement learning: every RL problem is an MDP (or a partially observable variant). Defining the state space, action space, reward function, and transition dynamics IS the problem specification. Reward design — defining R correctly — is one of the hardest parts of RL: poorly designed rewards produce agents that achieve the letter but not the spirit of the goal (reward hacking).
Key Points
| Aspect | Description |
|---|---|
| POMDP | Partially Observable MDP — agent cannot observe full state (robotics, dialogue systems) |
| Tuple | (S, A, P, R, γ) — states, actions, transition dynamics, reward function, discount factor |
| Policy π | Mapping from states to actions: π(a |
| Discount γ | 0 < γ < 1 — how much future rewards are worth relative to immediate rewards |
| Value function | V(s) = expected cumulative discounted reward from state s following policy π |
| Markov property | P(sₜ₊₁ |
Simple Analogy
A chess game: the board position is the state, legal moves are actions, the rules determine transitions (P), and winning/losing is the reward. The Markov property holds: the best next move depends on the current board, not on how the game reached that position.
Common Usage Examples
- OpenAI Gym:
env.step(action)returns(next_state, reward, done, info)— MDP interface - GridWorld MDP: states = grid cells, actions = {up, down, left, right}, reward = +1 at goal
value_iteration(P, R, gamma=0.99)— exact MDP solver for small state spaces- RL training: RLHF frames LLM token generation as an MDP: state = conversation, action = next token
gym.make("CartPole-v1")— classic MDP RL environment (balance a pole on a cart)
Summary
In short: The Markov Decision Process is the formal mathematical foundation of reinforcement learning — defining states, actions, rewards, and transitions to specify any sequential decision problem in a rigorous framework.