Formulating Problems as MDPs

Hello! Welcome to the first lesson of our module on Reinforcement Learning Foundations.

In our last module, we explored the cutting-edge architectures of modern language models, like LLaMA and Mixture of Experts (MoE). A key theme in that discussion was aligning these powerful models to be helpful and harmless. One of the most important techniques for this alignment is Reinforcement Learning from Human Feedback (RLHF). To understand RLHF and many other state-of-the-art AI systems, we first need to build a solid foundation in Reinforcement Learning (RL) itself.

This module will provide that foundation. We'll start today with the most fundamental concept in RL: the Markov Decision Process (MDP). An MDP is the mathematical framework used to describe almost every reinforcement learning problem. Our goal for this lesson is to learn how to take a problem—whether it's a game, a robot's task, or even managing a system—and formally describe it as an MDP.

1. The Reinforcement Learning Framework

At its heart, Reinforcement Learning is about learning from interaction. It describes a situation where an agent (the learner or decision-maker) exists within an environment. The agent takes actions, which change the environment's state and provide the agent with a reward (or penalty). The agent's goal is to learn a strategy, or policy, to maximize its total cumulative reward over time.

This interaction creates a continuous feedback loop, which is the cornerstone of all RL.

This simple framework can model an incredibly diverse range of problems.

2. From Simple Choices to Sequential Decisions

Before we define the full MDP, it's helpful to build up to it from simpler decision-making problems. This will clarify what makes an MDP distinct and powerful.

The key takeaway from that progression is the concept of agency over the future.

• In a Multi-Armed Bandit, you just have to figure out which slot machine in a casino pays out the most on average. There's only one "state" (you're at the casino).
• In a Contextual Bandit, the casino might have different rooms (contexts/states), and the best machine might be different in each room. An external force teleports you from room to room. Your choice of machine in one room has no bearing on which room you'll be in next.
• A Markov Decision Process finally gives the agent control. Your action not only gives you a reward but also influences which state you find yourself in next. Choosing to walk through a door (action) changes your location (state). This is the essence of sequential decision-making.

3. The Five Pillars of a Markov Decision Process

An MDP formalizes this sequential process with a specific set of components. Any problem you want to solve with RL must first be mapped onto these components.

As the video explains, an MDP is a tuple $(S,A,P,R,\gamma )$. Let's formalize and expand on each of these components.

• S: The Set of States
  A state $s\in S$ is a complete description of the world that is relevant to the decision-making task. It must be sufficient to make a decision without needing any past information. This is the Markov Property: the future is independent of the past, given the present state.

  • Example (Chess): The state is the position of all pieces on the board and whose turn it is. You don't need to know the sequence of moves that led to this position.
  • Example (Robot Navigation): The state could be the robot's (x, y) coordinates and velocity.

• A: The Set of Actions
  An action $a\in A$ is a choice the agent can make in a given state. The set of available actions can be dependent on the current state, denoted as $A(s)$.

  • Example (Chess): All legal moves from the current board position.
  • Example (Robot Navigation): {move_north, move_south, turn_left, apply_brakes}.

• P: The Transition Probability Function
  This is the "physics" or dynamics of the environment. The transition function $P(s^{\prime }|s,a)$ gives the probability of transitioning to a new state $s^{\prime }$ after taking action $a$ in state $s$.

  • It defines the consequences of actions. These consequences can be stochastic (uncertain).
  • Example (Robot Navigation): If the robot takes the action move_north, the transition function might specify: P(\text{position} + (0,1) | \text{current_pos}, \text{move_north}) = 0.8. But due to slippery wheels, there might also be a P(\text{position} + (-1,0) | \text{current_pos}, \text{move_north}) = 0.1 and P(\text{position} + (1,0) | \text{current_pos}, \text{move_north}) = 0.1.

• R: The Reward Function
  The reward function $R(s,a,s^{\prime })$ specifies the immediate reward the agent receives for transitioning from state $s$ to state $s^{\prime }$ by taking action $a$. The agent's ultimate goal is to maximize the cumulative sum of these rewards.

  • This is the most critical part of the formulation, as it defines the agent's goal. A poorly designed reward function can lead to unintended behavior.
  • Example (Chess): A simple reward could be +1 for winning, -1 for losing, and 0 for all other moves.
  • Example (Robot Navigation): +100 for reaching the destination, -10 for bumping into a wall, and -0.1 for every single move (to encourage efficiency). This small negative reward is often called a "living penalty" or "step cost".

• γ: The Discount Factor
  The discount factor $\gamma$ (gamma) is a number between 0 and 1 that determines the present value of future rewards. A reward received $t$ steps in the future is discounted by a factor of ${\gamma }^t$.

  • Why discount?
    1. Economic Intuition: A reward today is worth more than the same reward tomorrow (you could invest it).
    2. Behavioral Control: A low $\gamma$ (e.g., 0.1) makes the agent "myopic" or short-sighted, caring only about immediate rewards. A high $\gamma$ (e.g., 0.99) makes the agent "far-sighted," planning for rewards far in the future.
    3. Mathematical Convenience: It ensures that the sum of rewards in an infinite-horizon problem is finite and converges.

Test your understanding!

Imagine you are formulating the game of Tic-Tac-Toe as an MDP. How would you define each of the five components (S, A, P, R, γ)?

Show answer

• States (S): The set of all possible board configurations (approx. 5,478 valid states), plus whose turn it is. A terminal state is one where the board is full or one player has won.
• Actions (A): The set of all empty squares on the current board where a player can place their mark (X or O).
• Transition Probability (P): The transitions are deterministic in Tic-Tac-Toe. If you are in state $s$ and take action $a$ (place your mark in a specific square), there is a 100% probability of moving to the resulting board state $s^{\prime }$. So, $P(s^{\prime }|s,a)=1$ for the correct next state and 0 for all others.
• Reward (R): A simple reward function could be:
  • +1 for any transition that results in a win.
  • -1 for any transition that results in a loss.
  • 0 for a draw.
  • 0 for all non-terminal moves.
• Discount Factor (γ): Since Tic-Tac-Toe is a short, finite game, we can often set $\gamma =1$, meaning all future rewards are valued equally. A value slightly less than 1 could also be used to encourage winning faster.

4. Case Study: The Grid World

The "Grid World" is the canonical example for teaching RL. It's simple enough to be intuitive but complex enough to illustrate all the components of an MDP.

Let's consider the classic Grid World problem described in the resource Markov Decision Processes — Mastering Reinforcement ....

By studying this example, you can see the full formulation process:

1. The problem is described: an agent navigating a grid with rewards, penalties, and uncertain movement.
2. The States (S) are defined as the (x, y) coordinates of the agent.
3. The Actions (A) are defined as {UP, DOWN, LEFT, RIGHT}.
4. The Transition Probabilities (P) are defined by the noisy movement: 80% chance of going in the intended direction, 10% to the left of it, 10% to the right. The logic also handles bumping into walls (staying in place).
5. The Rewards (R) are assigned: +1 for the goal state, -1 for the penalty state, and a small cost for every other move.
6. A Discount Factor (γ), like 0.9, is chosen to make the agent care about future rewards but still prefer shorter paths.

This process of translation from a problem description to the formal $(S,A,P,R,\gamma )$ tuple is exactly the learning outcome for today.

5. How Formulation Choices Shape Behavior

The choices you make when formulating an MDP—especially the reward function and the discount factor—have a profound impact on the final behavior of the agent. A slight tweak can be the difference between an agent that is cautious and one that is reckless.

This is best demonstrated with another grid world scenario.

Let's review the exercise!

The setup is a grid world with two exits: a close one with reward +1 and a distant one with reward +10. There is a dangerous cliff of fire pits along the bottom.

• Scenario A: Prefer close exit (+1), risk the cliff.
  • Requires: Low discount γ (to devalue the distant +10) and no noise (so risking the cliff is not actually risky). This matches Setting 2: γ=0.1, noise=0.
• Scenario B: Prefer close exit (+1), avoid the cliff.
  • Requires: Low discount γ (to prefer the +1) and high noise (so taking the path near the cliff is too dangerous). This matches Setting 4: γ=0.1, noise=0.2.
• Scenario C: Prefer distant exit (+10), risk the cliff.
  • Requires: High discount γ (so the +10 is still valuable despite being further away) and no noise (to make the cliff path safe). This matches Setting 1: γ=0.9, noise=0.
• Scenario D: Prefer distant exit (+10), avoid the cliff.
  • Requires: High discount γ (to want the +10) and high noise (to make the safe, roundabout path the only viable option). This matches Setting 3: γ=0.9, noise=0.2.

This exercise perfectly demonstrates that formulating an MDP is not just a mechanical translation; it's an act of design that encodes the desired priorities and risk tolerance into the problem itself.

Conclusion

In this lesson, we have laid the cornerstone for our study of Reinforcement Learning. We've established that the Markov Decision Process is the universal language for describing problems of sequential decision-making under uncertainty.

Key Takeaways:

• RL problems are modeled as an agent interacting with an environment through a loop of states, actions, and rewards.
• An MDP is formally defined by a 5-tuple: States (S), Actions (A), Transition Probabilities (P), a Reward Function (R), and a Discount Factor (γ).
• The core challenge in applying RL is to correctly formulate your problem in terms of these five components.
• The choices made during formulation, especially for the reward function and discount factor, directly shape the agent's goals and resulting behavior (e.g., short-sighted vs. far-sighted, risk-averse vs. risk-seeking).

Preview of the Next Lesson:

Now that we know how to describe a problem as an MDP, the next logical question is: how do we solve it? How do we find the best possible strategy or "policy" for our agent? In the next lesson, we will introduce the central equations of RL: the Bellman equations. These equations provide a way to calculate the "value" of being in a particular state and are the key to unlocking algorithms that can solve for the optimal policy.