Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 37 ยท MDPs and Bellman Equations

Markov Decision Processes

Learn the MDP, the mathematical model behind reinforcement learning: states, actions, transition probabilities, rewards, the Markov property and how to simulate one in Python.

In the first chapter you met agents, environments, rewards and the exploration problem. To reason about them precisely we need a model. The standard one is the Markov decision process, or MDP. Almost every algorithm in this course, from dynamic programming to deep Q-networks, is a method for solving an MDP or for learning to behave well in one without being told its details.

An MDP says: at each step the world is in some state, the agent picks an action, and the world responds with a reward and a new state. The response may be random, but it depends only on the current state and action. That last sentence is the whole idea, and this lesson unpacks it.

The five ingredients

A finite MDP is a tuple (S, A, P, R, gamma):

  • S: the set of states (for example, the squares of a grid).
  • A: the set of actions (up, down, left, right). Sometimes the available actions depend on the state.
  • P: the transition model, P(s' | s, a), the probability of landing in s' after doing a in s.
  • R: the reward, R(s, a, s') or its expected value R(s, a).
  • gamma: a discount factor between 0 and 1, covered in the next lesson.

The agent does not control P or R; it controls only which action to pick. A rule for picking actions is called a policy, and we meet it properly in Policies and Value Functions.

The Markov property

A state has the Markov property if it contains everything about the past that matters for the future:

P(next state, reward | S_t, A_t, S_{t-1}, A_{t-1}, ...) = P(next state, reward | S_t, A_t)

Chess positions are Markov: the board tells you everything, not how it was reached. A single video-game frame is not Markov, because one image does not show velocity. Practitioners fix this by stacking the last few frames into the state. When you design an RL problem, the question "does my state contain enough information?" decides whether the MDP model applies at all.

flowchart LR
    S["state s"] --> A["agent picks action a"]
    A --> E["environment: P and R"]
    E -->|"reward r"| A
    E -->|"next state s'"| S

Writing an MDP as data

For small problems we store the model as a nested dictionary: P[s][a] is a list of (probability, next_state, reward) triples. Here is a tiny maintenance robot with three states. In working it can wait (safe, small reward) or push (risky: 30% chance of overheating, which is a penalty). From hot it can cool back to working, or push on with a 50% chance of breaking. broken is a terminal state with no actions.

Python A three-state MDP as a dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking that probabilities sum to 1 is a habit worth keeping: a typo in a hand-written model silently corrupts every algorithm that uses it.

Simulating a trajectory

An MDP is a generator of experience. Starting from some state and following a policy, we get a trajectory: S0, A0, R1, S1, A1, R2, S2, .... Note the indexing: the reward that follows action A_t is called R_{t+1}, because it arrives together with the next state.

Python Sampling episodes from the model

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Change the seed and you will see that the reckless robot sometimes earns more and sometimes breaks. Which policy is better on average is exactly what the rest of the chapter teaches you to compute.

Kinds of MDPs

  • Episodic vs continuing. Episodic tasks end in a terminal state (a game is won or lost). Continuing tasks run forever (a thermostat).
  • Deterministic vs stochastic. In a deterministic MDP every P is 0 or 1. Most textbook grid worlds are deterministic; real robots are not.
  • Finite vs continuous. With finitely many states and actions we can use tables. Otherwise we need function approximation, covered in chapter 6.
  • Known vs unknown model. Dynamic programming (chapter 3) needs P and R. Monte Carlo and TD methods (chapter 4 onward) learn from sampled experience alone, which is the usual situation.

Common mistakes

  • Forgetting that the reward depends on the transition. Rewards are often modelled as R(s, a), but R(s, a, s') is more general.
  • Calling a problem an MDP when the state hides crucial information. Such problems are partially observable (POMDPs) and need memory or belief states.
  • Giving terminal states outgoing actions. Treat them as absorbing with value zero, as the dictionary above does.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Markov property say?

    The current state summarizes everything about the past that is relevant for predicting what happens next.
  2. 2. In the notation S_t, A_t, R_{t+1}, S_{t+1}, when does reward R_{t+1} arrive?

    The reward is the environment's response to the action, so it shares the time index of the next state.
  3. 3. Which ingredient of an MDP does the agent NOT control?

    The agent chooses actions; the environment supplies the dynamics P and the rewards R.
  4. 4. A single Atari frame does not show how fast the ball moves. What is the usual fix?

    Stacking frames restores velocity information, making the state (approximately) Markov.

Summary

  • An MDP is (S, A, P, R, gamma): states, actions, transition probabilities, rewards and a discount.
  • The Markov property: the future depends on the present state and action, not on the earlier history.
  • Small MDPs can be stored as P[s][a] = [(prob, next_state, reward), ...] and sampled to produce trajectories.
  • Episodic tasks end; continuing tasks do not. Known models allow planning; unknown models require learning from experience.

Next: Returns and Discounting