Modeling Sequential Decisions with MDPs

1. From Deterministic Games to Probabilistic Worlds

In Minimax, the world is straightforward. If you move a piece to a square, it lands on that square. Your opponent's move is the only uncertainty, and Minimax handles that by assuming they play optimally against you.

But many real-world problems aren't so clean. Imagine programming a robot to navigate a room. You might command it to "move forward," but due to wheel slippage or an uneven floor, it might actually move forward 80% of the time, veer slightly left 10% of the time, and veer slightly right 10% of the time.

This is the core difference:

• Minimax: Deals with turn-based, deterministic environments. The solution is the single best move to make now.
• MDPs: Handle sequential, probabilistic environments. The solution is a policy, a complete plan telling the agent what to do for every possible situation it might encounter.

2. The Agent-Environment Interaction Loop

To formalize this, we introduce the concept of an agent operating within an environment. The interaction is a continuous loop:

1. The agent observes the current state of the environment.
2. Based on the state, the agent chooses an action.
3. The environment processes the action, transitions to a new state, and gives the agent a reward.
4. The loop repeats.

This interaction is the heart of reinforcement learning.

To understand the core components of this loop, let's watch a short video that introduces the framework.

A crucial concept mentioned in the video is the Markov Property. In simple terms, it means the future is independent of the past, given the present. All the information needed to make the best decision is contained in the current state s. We don't need to know the entire history of how we got to s. This assumption dramatically simplifies the problem of modeling the world.

3. The Five Components of an MDP

To use the MDP framework, we must precisely define the problem. An MDP is formally described by a tuple of five components: $(S,A,P,R,\gamma )$. As a computer science student, you'll appreciate how this formal structure allows us to apply general algorithms to specific problems.

Let's break down each component, using the excellent Gibberblot article as a guide.

Let's summarize those key components:

• $S$: State Space

  • The set of all possible states the agent can be in. A state is a snapshot of the world containing all relevant information.
  • Example: In a GPS navigation app, a state could be your current (latitude, longitude) coordinates.

• $A$: Action Space

  • The set of all possible actions the agent can take. This can be specific to a state, e.g., $A(s)$.
  • Example: From a given intersection, your actions might be {Turn Left, Go Straight, Turn Right}.

• $P$: Transition Probability Function

  • $P(s^{\prime }|s,a)$ defines the probability of transitioning to state $s^{\prime }$ if the agent takes action $a$ in state $s$. This is the "uncertainty" part of the model. The sum of probabilities for all possible next states $s^{\prime }$ must equal 1.
  • Example: If you choose "Go Straight" ($a$) at an intersection ($s$), the probability of ending up in the next block ($s^{\prime }$) might be 0.9, but there might be a 0.1 probability you get stuck in traffic and remain in the same state ($s$).

• $R$: Reward Function

  • $r(s,a,s^{\prime })$ is the immediate reward the agent receives after transitioning from state $s$ to $s^{\prime }$ by taking action $a$. The agent's goal is to maximize the cumulative reward over time, not just the next immediate reward.
  • Example: Reaching your destination gives a large positive reward (+100). Each minute spent driving gives a small negative reward (-1) to encourage efficiency.

• $\gamma$: Discount Factor

  • A number between 0 and 1 that determines the importance of future rewards. A reward received k steps in the future is only worth ${\gamma }^{k-1}$ times what it would be worth now.
  • This models the idea that immediate rewards are often better than future rewards. It also ensures that our math works out for infinite sequences of rewards.

This graphical representation can help you visualize how these components connect.

4. Modeling a Problem: Grid World

Let's make this concrete by modeling a classic AI problem called Grid World. Imagine an agent on a grid, trying to reach a goal.

The Computerphile video below does an excellent job of building up from a simple deterministic problem (like we've seen before) to a full probabilistic MDP, using a daily commute as an analogy.

Now, let's define our own Grid World MDP based on the example in the Gibberblot article you read earlier:

• Environment: A 4x3 grid. One cell is a wall, one is a goal (+1 reward), and one is a pit (-1 reward).
• States (S): The set of all (x, y) coordinates for the cells the agent can be in. E.g., (0,0), (0,1), ... (3,2).
• Actions (A): {Up, Down, Left, Right}.
• Transition Probabilities (P): This is the core of the model. If the agent chooses 'Up':
  • 80% chance it moves one cell up.
  • 10% chance it 'slips' and moves one cell left.
  • 10% chance it 'slips' and moves one cell right.
  • If a move would take it into a wall or off the grid, it stays in the same cell.
• Rewards (R):
  • A small negative reward for every step (e.g., -0.04) to encourage finding the shortest path.
  • A large positive reward for entering the goal cell (+1).
  • A large negative reward for entering the pit cell (-1).
• Discount Factor ($\gamma$): Let's say 0.9, meaning we value future rewards but prefer them sooner rather than later.

By defining these five components, we have successfully modeled the Grid World problem as an MDP. We haven't solved it yet, but we have translated a vague goal ("get to the green square") into a precise mathematical structure that an algorithm can work with.

5. The Solution to an MDP: A Policy

So, if the solution isn't a single move or a single path, what is it? The solution to an MDP is a policy, denoted by $\pi$.

A policy is a complete strategy that tells the agent which action to take in every single state.

• Policy $\pi$: $S\to A$

A good policy will tell the agent in the Grid World "if you are at (0,0), go Right," and "if you are at (2,1), go Up." The goal of reinforcement learning algorithms is to find the optimal policy (${\pi }^{\ast }$), which is the policy that maximizes the expected cumulative discounted reward.

Conclusion

In this lesson, you have learned how to bridge the gap from deterministic problems to the more realistic world of uncertainty. You can now take a sequential decision-making problem and structure it as a formal Markov Decision Process.

Key Takeaways:

• MDPs are a framework for modeling sequential decision-making problems where outcomes are probabilistic.
• An MDP is defined by five components: States ($S$), Actions ($A$), Transition Probabilities ($P$), Rewards ($R$), and a Discount Factor ($\gamma$).
• The Markov Property simplifies modeling by assuming the current state contains all necessary information about the past.
• To model a problem as an MDP, you must define all five components based on the problem's characteristics and the agent's goals.
• The solution to an MDP is not a single move but a policy ($\pi$), which is a complete plan specifying the best action to take in any given state.

Preview of the Next Lesson:

We have now formally defined the problem. The natural next question is, "How do we find that optimal policy?" The next lesson, "Explain core reinforcement learning concepts: states, actions, rewards, and policies," will serve as a bridge. We'll solidify the concepts you learned today and begin to explore the fundamental ideas behind the algorithms, like Value Iteration and Policy Iteration, that are used to solve MDPs and find that all-important optimal policy.