1. Courses
  2. Reinforcement Learning
  3. Lecture 3
Lecture 3 of 1418 minInteractiveFree lecture

Markov decision processes

Most decisions change the situation you face next. Markov decision processes give such problems a precise shape — states, actions, transition probabilities, rewards and a discount — so that we can reason about the best long-term strategy.

In this lecture you will

  • Name the five components of a Markov decision process
  • Explain the Markov property and why it makes planning tractable
  • Read a transition diagram with probabilities and rewards
  • Compare policies by the average reward they collect over time

The bandits of the last lecture had one situation, repeated forever. Real problems are different: moving the robot changes where it is, a chess move changes the board, and a discount offered today changes what the customer does tomorrow. We need a framework in which actions have consequences.

That framework is the Markov decision process (MDP) — the mathematical backbone of reinforcement learning.

The five ingredients

AnimationBuilding an MDP
Loading animation…
  1. States SEvery situation the agent can be in. In the grid world, each open tile is a state, labeled by its row and column.
  2. Actions AThe choices available in each state. Here, the same four moves are available everywhere.
  3. Transitions PThe probability of each next state after an action. On slippery ice, “up” succeeds 80% of the time and slips sideways otherwise — and a slip into a wall leaves the robot where it is.
  4. Rewards RThe immediate reward for each transition: +10 at the goal, −10 in a pit and −1 for any other move.
  5. Discount γHow much future rewards count compared with immediate ones. With γ = 0.9, a reward one step away is worth 90% of its face value, two steps away 81%, and so on.
  6. The Markov propertyThe robot’s path to its current tile does not affect what happens next. The current state contains everything needed to predict the future.

Formally, an MDP is the tuple (S,A,P,R,γ)(S, A, P, R, \gamma). The transition function

P(s′∣s,a)P(s' \mid s, a)

gives the probability of landing in state s′s' after taking action aa in state ss. Deterministic worlds are the special case where one outcome has probability 1.

Uncertain outcomes

In many real problems the same action does not always have the same effect: a robot’s wheels slip, a customer ignores an offer, a network packet is lost. Try the slippery grid below.

InteractiveSlippery ice: transition probabilitiesClick a tile · choose an action
Loading visual…

Arrow thickness shows probability. Slips into walls or the edge leave the robot in place. Sampling 50 moves shows the probabilities as frequencies.

Randomness is why the agent maximizes the expected return — the average over all the ways the future might unfold — rather than the return of one lucky episode.

The Markov property

An MDP assumes that the state summarizes everything relevant about the past:

P(st+1∣st,at)=P(st+1∣s0,a0,s1,a1,…,st,at)P(s_{t+1} \mid s_t, a_t) = P(s_{t+1} \mid s_0, a_0, s_1, a_1, \dots, s_t, a_t)

A chess position has this property: to choose the next move you need the board, not the order in which the pieces arrived. A robot’s position may not — if the floor is slippery only after it has been mopped, the state should include “recently mopped”. Designing a state that is Markov is often the most important modeling decision in an RL project.

Policies and their value: the recycling robot

A classic example from the reinforcement-learning literature: a robot that collects empty cans. Its battery is either high or low. It can search for cans (more reward, but it drains the battery), wait for someone to bring cans (less reward, no drain), or — when low — recharge. If it searches on a low battery and runs flat, it must be rescued, which costs −3.

InteractiveThe recycling-robot MDPChoose actions to step through the MDP
Loading visual…

Solid lines lead from a state to an action (black dot); dashed arrows lead to the possible next states, labeled with probability p and reward r.

Play a few steps by hand, then press Compare policies. Each policy is simulated for 10,000 steps:

  • Always wait earns exactly +1 per step — safe but unambitious.
  • Always search earns more while the battery is high, but rescues drag its average down.
  • Search, then recharge when low does best: it takes the profitable risk in the high state and avoids the costly one in the low state.
Policy π(a | s)
The agent’s decision rule — possibly random — giving the probability of each action in each state.
Deterministic policy
Always takes the same action in a given state, such as “recharge when low”.
Expected return
The average return over all possible random outcomes, starting from a state and following a policy.
Optimal policy π*
A policy whose expected return is at least as high as any other policy’s, from every state.

Comparing policies by simulation works for two states. For thousands of states we need a smarter way to compute how good each state is under the best policy. That is the Bellman equation — the subject of the next lecture.

Key takeaways

  • An MDP is defined by states, actions, transition probabilities, rewards and a discount factor.
  • Transitions can be random — the same action in the same state may lead to different outcomes.
  • The Markov property says the future depends only on the present state and action, not on the history.
  • Different policies produce different long-run rewards; the job of RL is to find the best one.

Check your understanding

4 questions · answers explained

Q1Which of these is NOT one of the components of a Markov decision process?

An MDP consists of states, actions, transition probabilities, rewards and a discount factor. There is no labeled dataset — the agent learns from rewards.

Q2What does the Markov property state?

If the state captures everything relevant, the past adds no extra information. That is what makes it possible to compute good decisions state by state.

Q3On slippery ice, the robot intends to move up but ends up moving right. How does an MDP describe this?

Transitions in an MDP are probabilistic. The intended move might happen 80% of the time, with sideways slips making up the rest.

Q4In the recycling-robot MDP, why can “search, then recharge when low” beat “always search”?

The best action depends on the state. Searching is profitable when the battery is high, but in the low state the risk of a costly rescue outweighs the extra cans.