AIM-05-002-P · Primer — Markov Decision Processes

The idea in one sentence

A Markov Decision Process (MDP) is the formal model of a reinforcement‑learning problem, consisting of states, actions, transition probabilities, and rewards.

Why it exists

Think of navigating a city: each intersection (state) lets you choose a direction (action), and the next intersection you reach and any toll you pay (reward) depend only on where you are and which road you take, not on how you arrived there. This captures the everyday need to make sequential decisions without remembering the entire past. In RL, the MDP formalism solves the problem of defining a clear, mathematically tractable environment for an agent to learn optimal behavior.

How it works

At each time step the agent observes its current state, selects an action, and the environment uses a transition function to move to a new state while emitting a reward from a reward function. For example, in a gridworld the state is the cell coordinates, actions are up/down/left/right, and reaching the goal cell yields a reward of +1 while all other moves give 0. The transition probabilities might be 0.8 for moving in the intended direction and 0.2 for slipping sideways. The agent repeats this loop, building a policy that maps states to actions to maximize expected cumulative reward. Because the Markov property holds, the next state and reward depend only on the current cell and chosen move, not on the path taken to get there.

If the transition dynamics are deterministic, the MDP simplifies to a planning problem; if they are stochastic, we often use a discounted‑reward version to ensure convergence. Partially observable MDPs (POMDPs) relax the Markov assumption by allowing hidden state information.

See it — the MDP tuple

flowchart LR
  S["State s"] -->|action a| T["Transition P"]
  T --> S2["Next state s'"]
  T --> R["Reward r"]

The one gotcha

A common mistake is assuming any state representation automatically satisfies the Markov property; if important information (like remaining battery level) is omitted, the process is no longer Markov and learning algorithms will perform poorly. The fix is to enrich the state so it fully captures everything that influences future transitions and rewards.

The one-line takeaway

An MDP gives a clean, step‑by‑step recipe for decision making by encoding everything needed in the current state.

Where you'll meet it

Practitioners encounter MDPs when defining environments in OpenAI Gym, building simulators for robotics, or modeling customer journeys in marketing analytics. Tools such as RLlib or TensorFlow Agents expect you to specify the state, action, transition, and reward functions as an MDP before training agents.