What is a Markov Decision Process (MDP)?

A Markov Decision Process (MDP) is a way to describe a problem where an agent makes decisions step by step, each decision changes the situation, and each step brings a reward. It is the standard way to write down a reinforcement learning problem.

In this blog, we will learn about what a Markov Decision Process (MDP) is. We will also see the basic setup of reinforcement learning, the Markov property, the five parts of an MDP using one robot example, how a policy and the return with discounting work, the difference between episodic and continuing tasks, and how an LLM generating text can be seen as an MDP.

We will cover the following:

• The Reinforcement Learning Setup
• What is the Markov Property?
• What is a Markov Decision Process (MDP)?
• Our Example: A Robot Going to Its Charging Dock
• The Five Parts of an MDP
• What is a Policy?
• What is the Return?
• Episodic vs Continuing Tasks
• An LLM Generating Text as an MDP

I am Amit Shekhar, Founder @ Outcome School, I have taught and mentored many developers, and their efforts landed them high-paying tech jobs, helped many tech companies in solving their unique problems, and created many open-source libraries being used by top companies. I am passionate about sharing knowledge through open-source, blogs, and videos.

I teach AI and Machine Learning at Outcome School.

Let's get started.

The Reinforcement Learning Setup

Before jumping into the MDP, we must know the setup in which it is used.

Reinforcement Learning is a way of learning where a learner tries things, sees what happens, and gets a score for it. Over time, it learns to do more of what brings a good score.

There are four words we will use again and again:

• Agent: The learner that makes the decisions. For example, a cleaning robot.
• Environment: The world the agent lives in and acts upon. For example, the house the robot moves in.
• Action: A choice the agent makes. For example, "Forward".
• Reward: A number the environment gives back after an action. A positive number is good, and a negative number is bad.

The agent and the environment talk to each other in a loop. The agent looks at the current situation, picks an action, and the environment replies with a new situation and a reward. The current situation is called the state.

Let's see this as a diagram:

┌─────────────────────────┐
│          Agent          │
│     state: Kitchen      │
│     picks an action     │
└─────────────────────────┘
             ↓
      action: Forward
             ↓
┌─────────────────────────┐
│       Environment       │
│ (the house, its rules)  │
└─────────────────────────┘
             ↓
      new state: Hall
        reward: -1
             ↓
┌─────────────────────────┐
│          Agent          │
│       state: Hall       │
│  picks the next action  │
└─────────────────────────┘
             ↓
     the loop repeats

Here, we can see that the robot starts in the Kitchen, chooses Forward, and the environment moves it to the Hall with a reward of -1. Then, the robot picks again from the Hall. Nobody tells the agent the right answer. It only gets a reward number after acting, and it must learn from these numbers which actions are good.

Now, the question is: how much of the past must the state include? Here comes the Markov property into the picture.

What is the Markov Property?

The Markov property says that the future depends only on the present state, and not on how we reached that state.

Let's take an example of a game of chess. If we look at the board right now, we know everything we need to decide the next move. It does not matter which moves were played to reach this board. The current board is enough.

Means, a state has the Markov property when it holds all the useful information about the past. Once we know the current state, the history adds nothing more.

So, the agent does not need to remember a long history. It needs to look only at the current state to decide what to do.

To learn Reinforcement Learning from the ground up, check out our AI and Machine Learning Program at Outcome School.

What is a Markov Decision Process (MDP)?

A Markov Decision Process (MDP) is a mathematical way to describe a decision-making problem using five parts: states, actions, transition probabilities, rewards, and a discount factor.

The word Markov in the name comes from the Markov property. In an MDP, where the agent lands next depends only on the current state and the action it takes.

The best way to learn this is by taking an example.

Our Example: A Robot Going to Its Charging Dock

Let's say we have a cleaning robot in a house. Its battery is low, and it wants to reach its charging dock.

The house has these places:

• Kitchen: Where the robot starts.
• Hall: The middle of the house.
• Corridor: A longer but safe path around the stairs.
• Dock: The charging dock. This is the goal.
• Stairs: If the robot falls down the stairs, it breaks. This is bad.

From the Hall, the robot has two choices:

• Straight: The short path to the Dock. But the floor near the stairs is slippery. 80% of the time it reaches the Dock, and 20% of the time it slips and falls down the Stairs.
• Around: The long path through the Corridor. It is safe, but it takes one extra step.

From the Kitchen, the robot can only go Forward to the Hall. From the Corridor, it can only go Forward to the Dock.

Every normal move costs -1, because it uses battery. Reaching the Dock gives +10. Falling down the Stairs gives -10.

Let's see this as a diagram:

                   ┌─────────────────┐
                   │     Kitchen     │
                   │     (start)     │
                   └─────────────────┘
                            ↓
                     action: Forward
                      prob 1.0, -1
                            ↓
                   ┌─────────────────┐
                   │      Hall       │
                   └─────────────────┘
                            ↓
              ┌─────────────┴──────────────┐
              ↓                            ↓
      action: Straight              action: Around
              ↓                            ↓
      ┌───────┴──────┐               prob 1.0, -1
      ↓              ↓                     ↓
prob 0.8, +10  prob 0.2, -10        ┌───────────────┐
      ↓              ↓              │   Corridor    │
 ┌─────────┐    ┌─────────┐         └───────────────┘
 │  Dock   │    │ Stairs  │                 ↓
 │  (end)  │    │  (end)  │         action: Forward
 └─────────┘    └─────────┘          prob 1.0, +10
                                           ↓
                                   ┌───────────────┐
                                   │     Dock      │
                                   │     (end)     │
                                   └───────────────┘

Here, each label under an action shows the chance of that outcome and the reward for it. For example, prob 0.8, +10 means that 80% of the time the robot reaches the Dock and gets +10. We can see that the Kitchen, the Hall, and the Corridor are normal states. The Dock and the Stairs are end states. Once the robot reaches one of them, the run is over.

Planning your move into AI?

No matter which tech domain you work in today, with your effort, you can transition to these roles:

• AI Engineer
• Forward Deployed Engineer
• AI Agent Engineer
• Harness Engineer
• Voice AI Engineer
• AI Architect
• LLM Engineer
• LLM Inference Engineer
• Gen AI Engineer
• MLOps Engineer
• ML Engineer
• Deep Learning Engineer

Our AI and Machine Learning Program at Outcome School takes you there.

The Five Parts of an MDP

Every MDP is made of five parts. Let's understand each one using our robot.

1. States (S)

States are all the situations the agent can be in.

In our example, the states are: Kitchen, Hall, Corridor, Dock, and Stairs. The Dock and the Stairs are end states, also called terminal states.

2. Actions (A)

Actions are all the choices the agent can make.

In our example, the actions are: Forward, Straight, and Around. Not every action is available in every state. In the Hall, the robot can choose Straight or Around. In the Kitchen and the Corridor, it can only choose Forward.

3. Transition Probabilities (P)

Transition probabilities tell us the chance of landing in each next state, when the agent takes an action in a state.

We write it as P(next state | state, action). We read it as "the chance of reaching the next state, given the current state and the action".

In our example:

• P(Hall | Kitchen, Forward) = 1.0
• P(Dock | Hall, Straight) = 0.8
• P(Stairs | Hall, Straight) = 0.2
• P(Corridor | Hall, Around) = 1.0
• P(Dock | Corridor, Forward) = 1.0

Here, we can notice that the same action in the same state does not always lead to the same place. Taking Straight from the Hall leads to the Dock most of the time, but not always. The transition probabilities capture this uncertainty. For each state and action, the chances add up to 1.

This is also where the Markov property comes in. The chances depend only on the current state and the action. It does not matter how the robot reached the Hall.

We have a detailed blog on How do World Models work? that explains how an AI can learn to predict the next state and the reward by itself.

4. Rewards (R)

Rewards are the numbers the agent gets after each step.

In our example:

• Moving to the Hall or the Corridor: -1
• Reaching the Dock: +10
• Falling down the Stairs: -10

The reward is how we tell the agent what we want. We never tell the robot "go around". We only say "the Dock is good, the Stairs are bad, and wasting battery is a little bad". The agent must find the best way by itself.

5. Discount Factor (gamma)

The discount factor, written as gamma, is a number between 0 and 1. It tells the agent how much to care about future rewards compared to rewards right now.

• A gamma close to 0 means the agent cares mostly about the very next reward.
• A gamma close to 1 means the agent cares about future rewards almost as much as the current one.

Let's say someone offers us 100 rupees today or 100 rupees after one year. Most of us prefer it today. A reward that comes later is worth a little less to us. Gamma captures this same idea.

In our example, we will use gamma = 0.9.

A quick note for you

No matter which tech domain you work in, get familiar with these topics:

• LLM
• RAG
• MCP
• Agent
• Fine-tuning
• Quantization

We put it all together in one video:

AI Engineering Explained: LLM, RAG, MCP, Agent, Fine-Tuning, and Quantization

No need to stop reading - bookmark it and watch later when you get time. Future you will thank you.

Now, let's get back to the topic.

What is a Policy?

Now that we have learned about the five parts of an MDP, it's time to learn about the policy.

A policy is the rule the agent follows to pick an action in each state.

In our example, here are two possible policies:

• Policy A: Kitchen -> Forward, Hall -> Straight
• Policy B: Kitchen -> Forward, Hall -> Around, Corridor -> Forward

A policy can also be based on chances. For example, "in the Hall, choose Straight 30% of the time and Around 70% of the time". This is called a stochastic policy. Stochastic means "based on chance".

The goal of reinforcement learning is to find the best policy. The best policy is the one that collects the most total reward on average. To compare policies, we need a way to add up the rewards of a run into one number. This number is called the return.

What is the Return?

The return is the total reward the agent collects from now on, where future rewards are multiplied by gamma once for every step of delay.

We can write it as below:

G = R_1 + gamma * R_2 + gamma^2 * R_3 + gamma^3 * R_4 + ...

Here, G is the return, R_1 is the first reward, R_2 is the second reward, and so on. The first reward counts fully. The second reward is multiplied by gamma once. The third reward is multiplied by gamma twice, and so on.

Let's calculate the return for one run of our robot with Policy B and gamma = 0.9.

The robot goes Kitchen -> Hall -> Corridor -> Dock. It gets these rewards: -1, -1, +10.

Step 1: The first reward is -1. It counts fully, so it adds -1.

Step 2: The second reward is -1. We multiply it by gamma once: 0.9 * (-1) = -0.9.

Step 3: The third reward is +10. We multiply it by gamma twice: 0.9 * 0.9 * 10 = 0.81 * 10 = 8.1.

Step 4: We add them all: -1 + (-0.9) + 8.1 = 6.2.

So, the return for this run is 6.2.

We can calculate the same in Python as below:

rewards = [-1, -1, 10]
gamma = 0.9

G = 0
for t, r in enumerate(rewards):
    G += (gamma ** t) * r

print(round(G, 2))

This will print the following:

6.2

Here, t is the step number starting from 0, so the first reward is multiplied by gamma ** 0 = 1, the second by gamma ** 1 = 0.9, and the third by gamma ** 2 = 0.81.

Now, let's use the return to compare the two choices in the Hall. We start counting from the Hall itself.

Straight: 80% of the time, the robot gets +10. 20% of the time, it gets -10. On average, it gets 0.8 * 10 + 0.2 * (-10) = 8 - 2 = 6. This average return is called the expected return.

Around: The robot always gets -1 first, and then +10 one step later. So, its expected return is -1 + 0.9 * 10 = -1 + 9 = 8.

So, with gamma = 0.9, Around is better (8 is more than 6). The best policy is Policy B.

Now, let's change gamma to 0.5. This means the agent cares much less about the future.

• Straight still gives 6, because its reward comes right away.
• Around gives -1 + 0.5 * 10 = -1 + 5 = 4.

Now, Straight is better (6 is more than 4). Here, we can see that the same MDP with a different gamma has a different best policy. An impatient agent takes the risky short path. A patient agent takes the safe long path.

If we want to go deep into Reinforcement Learning and the algorithms like PPO and GRPO that find the best policy, our AI and Machine Learning Program at Outcome School covers it in depth.

Episodic vs Continuing Tasks

There are two kinds of tasks in an MDP.

Episodic tasks have an end. One full run from the start to an end state is called an episode. Our robot task is episodic. Every episode ends when the robot reaches the Dock or falls down the Stairs. Then, a new episode starts again from the Kitchen.

Continuing tasks never end. For example, an agent that controls the temperature of a building keeps working forever. There is no end state.

In continuing tasks, gamma becomes very important. If the agent gets a reward of 1 at every step forever, the plain sum 1 + 1 + 1 + ... keeps growing without any limit. With gamma = 0.9, the return becomes 1 + 0.9 + 0.81 + 0.729 + ..., and this adds up to exactly 1 / (1 - 0.9) = 10. Because each new reward counts for less, the sum stays finite. This is why continuing tasks use a gamma less than 1.

In episodic tasks, gamma can be 1, because the sum always ends.

Stay updated: Subscribe to our newsletter to get our latest AI and Machine Learning blogs straight to your inbox.

An LLM Generating Text as an MDP

Now, let's see how the same idea applies to an LLM (Large Language Model).

An LLM writes text one token at a time. A token is a small piece of text, such as a word or a part of a word. At each step, the LLM looks at all the text so far and picks the next token.

We can describe this as an MDP:

Let's say the prompt is "The capital of France is". Let's see the steps as a diagram:

┌─────────────────────────────────────┐
│               State 1               │
│     "The capital of France is"      │
└─────────────────────────────────────┘
                   ↓
         action: token "Paris"
                   ↓
┌─────────────────────────────────────┐
│               State 2               │
│  "The capital of France is Paris"   │
└─────────────────────────────────────┘
                   ↓
           action: token "."
                   ↓
┌─────────────────────────────────────┐
│               State 3               │
│  "The capital of France is Paris."  │
└─────────────────────────────────────┘
                   ↓
           action: end token
                   ↓
┌─────────────────────────────────────┐
│            Episode ends             │
│   reward: +1 (answer is correct)    │
└─────────────────────────────────────┘

Here, we can see that each action adds one token to the text, and the new text becomes the next state. When the LLM picks the special end token, the episode ends. Only then, a reward is given for the full answer. It comes from a reward model (another model trained to score answers) or from a checker that can tell if the answer is correct.

Here, we can notice a few things:

• The state includes the full text so far, so it has the Markov property. The next state depends only on this text and the chosen token.
• The transitions are certain. Adding a token always gives one exact new text. The only uncertainty is in which token the policy picks.
• The LLM gives a chance to every possible next token and then picks one, so it is a stochastic policy.
• This is an episodic task. Every answer ends with the end token or when it hits a maximum length.

This is how reinforcement learning methods can train an LLM. They treat the LLM as a policy, give a reward for good answers, and update the LLM so that it picks tokens that lead to a higher return. We have detailed blogs on Proximal Policy Optimization (PPO) and Group Relative Policy Optimization (GRPO) that explain this training step by step.

Now we must have understood what a Markov Decision Process (MDP) is, its five parts, how a policy and the return work, and how an LLM generating text fits into it.

Frequently Asked Questions

Does an agent in an MDP need to remember the full history?

No. An agent in an MDP does not need to remember the full history. Because of the Markov property, the current state holds all the useful information about the past. Where the agent lands next depends only on the current state and the action it takes, so the agent looks only at the current state to decide what to do.

Why can a different discount factor change the best policy?

A different discount factor changes how much the agent cares about future rewards. In the robot example, with gamma = 0.9, the safe long path gives an expected return of 8 and beats the risky short path at 6. With gamma = 0.5, the long path drops to 4, so the risky short path wins. An impatient agent takes the risky path, and a patient agent takes the safe one.

Can the discount factor be equal to 1?

Yes, but only in episodic tasks. In an episodic task, the sum of rewards always ends, so gamma can be 1. In a continuing task, the plain sum of rewards can keep growing without any limit, so we use a gamma less than 1. Then each new reward counts for less, and the return stays finite.

Where does the reward come from when an LLM is trained as an MDP?

The reward usually comes at the end of the full answer. It is often 0 for every token, and one score is given only when the episode ends. That score comes from a reward model, which is another model trained to score answers, or from a checker that can tell if the answer is correct.

That's it for now.

Thanks

Amit Shekhar
Founder @ Outcome School

You can connect with me on:

• X
• LinkedIn
• GitHub

Follow Outcome School on:

• X
• YouTube
• LinkedIn
• GitHub

Read all of our high-quality blogs here.