Introduction to Markov Decision Processes

Introduction

Welcome to the first lesson of our module on Reinforcement Learning (RL) Foundations. In the previous modules, we explored the intricate architectures of modern Transformers, from efficient attention mechanisms like MLA to massive scaling with Mixture-of-Experts. We learned how these models are built. Now, we shift our focus to teaching them how to act.

A pre-trained language model is a powerful token predictor, but it doesn't inherently know how to follow instructions, solve problems, or control a robot. To bridge this gap, we use alignment techniques, and the most powerful and prevalent of these are rooted in RL.

This lesson begins our journey into RL by introducing its most fundamental concept: the Markov Decision Process (MDP). An MDP is the mathematical framework used to model virtually all sequential decision-making problems under uncertainty. Your goal for this lesson is to define the components of a Markov Decision Process: states, actions, transition dynamics, and rewards.

By the end of this lesson, you will understand:

What the Markov Property is and why it's a crucial assumption.
The definitions of states, actions, rewards, and transition probabilities.
How these components come together to formally define the environment in which an RL agent operates.

1. The Core Challenge: Decision-Making Under Uncertainty

In the world of classic search algorithms, the environment is predictable. If an agent in state $s$ takes action $a$ , it moves to a known successor state $s^{'}$ . However, the real world, and the complex problems we want to solve (like autonomous driving), are filled with uncertainty. An action might not always lead to the intended outcome.

This is the core problem that MDPs are designed to model. To build intuition, let's start with a high-level introduction.

Markov Decision Processes 1 - Value Iteration | Stanford CS221: AI (Autumn 2019)

This video from Stanford's CS221 course introduces the motivation for MDPs by contrasting deterministic search problems with the uncertain nature of real-world tasks.

Watch from 01:35 to 07:47. First, focus on the distinction made between deterministic search and decision-making under uncertainty. Then, pay close attention to the 'volcano crossing' example. Note how the optimal decision changes as the 'slip probability' (the uncertainty) increases. This illustrates why we need a formal way to handle probabilistic outcomes.

The volcano example highlights the essential elements: you have a state (your location on the grid), you can take actions (move North, South, etc.), your actions have uncertain outcomes (you might slip), and you receive rewards or penalties (reaching the scenic view or falling into the volcano). An MDP provides the mathematical language to describe this entire setup.

2. The Markov Property: A Foundational Assumption

Before we can define the full MDP, we must understand its cornerstone: the Markov property. Simply put, this property states that the future is independent of the past, given the present.

In the context of RL, this means the current state $s_{t}$ captures all information from the history $(s_{0}, a_{0}, s_{1}, a_{1}, \dots, s_{t})$ that is relevant for predicting the future. Once you know the current state, you can throw away the past.

A system that adheres to this is called a Markov Process or a Markov Chain. It's the simplest piece of our framework, consisting of just two components:

A set of states ( $S$ ).
Transition probabilities ( $P$ ), which define the probability of moving from one state to another, $P (s_{t + 1} ∣ s_{t})$ .

RL Course by David Silver - Lecture 2: Markov Decision Process

Let's watch a segment from David Silver's classic RL course, where he introduces the Markov Process and the Markov property.

Watch from the beginning (00:02) to 10:34. Focus on the formal definition of the Markov property and how a Markov Process is defined by a state space and a transition probability matrix. The 'Student Markov Chain' example is a great way to see these concepts in action.

3. Introducing Rewards: The Markov Reward Process (MRP)

A Markov Process tells us how we might move through states, but it doesn't tell us what's desirable. To do that, we introduce rewards. By adding rewards to a Markov Process, we get a Markov Reward Process (MRP).

An MRP is defined by:

States ( $S$ )
Transition probabilities ( $P$ )
A reward function ( $R$ )
A discount factor ( $γ$ )

The reward function, $R (s)$ , specifies the immediate reward received for being in state $s$ . The discount factor, $γ$ (a value between 0 and 1), determines the present value of future rewards. A reward received $k$ steps in the future is discounted by $γ^{k}$ . This is both mathematically convenient and intuitively appealing—a reward today is often worth more than a reward tomorrow.

The agent's goal is to maximize the return, which is the total discounted reward accumulated over a sequence of states.

RL Course by David Silver - Lecture 2: Markov Decision Process

Let's return to David Silver's lecture, where he extends the student example into a Markov Reward Process.

Watch from 13:01 to 29:10. Observe how reward values are assigned to each state (e.g., -2 for being in class, +10 for passing). Pay attention to the definitions of 'return' (the cumulative discounted reward) and the 'value function' (the expected return from a state).

An MRP is a useful stepping stone, but it's still missing a key ingredient: agency. The agent in an MRP is a passive observer, moved through the world by probabilistic transitions. To give the agent control, we must introduce actions.

4. Full Agency: The Markov Decision Process (MDP)

We finally arrive at the complete framework. A Markov Decision Process (MDP) is an MRP where the agent can choose actions. This single change is what enables decision-making.

The components of an MDP are:

States ( $S$ ): A set of all possible states the agent can be in.
Actions ( $A$ ): A set of all possible actions the agent can take.
Transition Probability Function ( $P$ ): $P (s^{'} ∣ s, a)$ defines the probability of transitioning to state $s^{'}$ after taking action $a$ in state $s$ . This models the environment's dynamics.
Reward Function ( $R$ ): $R (s, a, s^{'})$ defines the immediate reward received after transitioning from state $s$ to state $s^{'}$ due to action $a$ .
Discount Factor ( $γ$ ): The same discount factor as in an MRP.

Let's see how adding actions changes our examples.

RL Course by David Silver - Lecture 2: Markov Decision Process

In this clip, David Silver transforms the 'Student MRP' into a full 'Student MDP' by adding actions.

Watch from 42:59 to 46:17. Notice how the probabilistic transitions (e.g., 50% chance of going to Facebook) are replaced by choices (the red labels 'study' vs. 'Facebook'). The agent now has control over its path through the state space.

Now, for a more formal definition and a different example, we'll turn back to the Stanford lecture.

Markov Decision Processes 1 - Value Iteration | Stanford CS221: AI (Autumn 2019)

This segment provides a clear, formal definition of the MDP components using a simple gambling game.

Watch from 13:17 to 18:22. The lecturer explicitly defines the states, actions, transition function T(S, A, S'), and reward function R(S, A, S'). This is a perfect formal summary of the concepts we've been building.

To summarize and consolidate these definitions, please read the following text.

Part 1: Key Concepts in RL

The OpenAI Spinning Up documentation provides a concise, formal definition of an MDP as a 5-tuple. This is the standard mathematical representation you will encounter in research papers.

Read the short section titled '(Optional) Formalism'. It lists each component of the 5-tuple (S, A, R, P, rho_0) and defines it. Note that it uses rho_0 for the starting state distribution, which is another common component of the formal definition.

5. A Concrete Example: Grid World

Let's tie all these components together with the classic "Grid World" example. This is a common tool for illustrating RL concepts because it's so intuitive.

Markov Decision Process (MDP) Diagram — A diagram illustrating a Markov Decision Process (MDP). Here, the states are the cells in the grid, actions are movements, transition probabilities model the slippery ground, and rewards are given for reaching certain cells.

Let's break down the Grid World example from the provided text resource, which is slightly different but illustrates the same concepts.

Markov Decision Processes — Mastering Reinforcement Learning

This resource provides another version of the Grid World example and even shows how its components would be implemented in Python code.

Read the section 'Example MDP: Grid World' to understand the scenario. Then, look at the Python code in the next section, specifically the get_transitions and get_reward methods. Notice how these methods are concrete implementations of the abstract P and R functions from our MDP definition.

In this Grid World:

States ( $S$ ): The $(x, y)$ coordinates of the agent on the grid.
Actions ( $A$ ): {Up, Down, Left, Right}.
Transition Probabilities ( $P (s^{'} ∣ s, a)$ ): The core of the problem's uncertainty. If the agent chooses action 'Up', there is an 80% chance it moves up, but a 10% chance it slips and moves left, and a 10% chance it slips and moves right. If a move would result in hitting a wall, the agent stays in its current state.
Rewards ( $R (s, a, s^{'})$ ): In this example, rewards are given for reaching the green (+1) or red (-1) terminal states. A small negative reward is often given for every non-terminal step to encourage efficiency.

This simple grid contains all the necessary components of an MDP, providing a complete definition of the problem our agent needs to solve.

Conclusion

In this lesson, we have laid the groundwork for our study of Reinforcement Learning by defining its core framework, the Markov Decision Process.

Key Takeaways:

An MDP is a mathematical framework for modeling sequential decision-making in a probabilistic environment.
The Markov Property is a key assumption, stating that the current state provides all necessary information to make a decision, rendering the past irrelevant.
An MDP is formally defined by a 5-tuple:
- States ( $S$ ): The situations the agent can be in.
- Actions ( $A$ ): The choices available to the agent.
- Transition Probabilities ( $P (s^{'} ∣ s, a)$ ): The probability of the environment moving to state $s^{'}$ given the agent took action $a$ in state $s$ .
- Reward Function ( $R (s, a, s^{'})$ ): The feedback signal from the environment.
- Discount Factor ( $γ$ ): A value that prioritizes immediate rewards over future ones.

It is crucial to remember that the MDP defines the problem, not the solution. It describes the "rules of the game" for the environment. The goal of a reinforcement learning algorithm is to find a solution within this framework.

Preview of the Next Lesson:

Now that we understand the environment, how does an agent actually make decisions? The agent's "brain" or strategy is called a policy. In our next lesson, we will explain what a policy is, how it maps states to actions, and why stochastic policies are a cornerstone of modern RL algorithms.

Recommended resources

Introduction

1. The Core Challenge: Decision-Making Under Uncertainty

2. The Markov Property: A Foundational Assumption

3. Introducing Rewards: The Markov Reward Process (MRP)

4. Full Agency: The Markov Decision Process (MDP)

5. A Concrete Example: Grid World

Conclusion