Deep Reinforcement Learning

Markov Decision Processes

Published: 2026-07-18

Level: postgraduate

Audience: Postgraduate students in Deep Reinforcement Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Reward and return — covered in Lecture 1 (From Reward to Return, 1.8)
Policy — covered in Lecture 1 (Policy: The Agent's Way of Working, 1.9)
Value function — covered in Lecture 1 (Value Function: Long-Term Desirability, 1.10)
Greedy action selection — covered in Lecture 1 (Choosing Moves: Greedy Action Selection, 1.16)
Epsilon-greedy exploration — covered in Lecture 1 (A Common Exploration Strategy: epsilon-Greedy, 1.22) and Lecture 2 (epsilon-Greedy Action Selection, 2.17)
Agent-environment interface — covered in Lecture 2 (The Agent-Environment Interface, 2.2)
State value function V(s) — covered in Lecture 2 (State Value Function V(s), 2.4)
Action value function Q(s, a) — covered in Lecture 2 (Action Value Function Q(s, a), 2.5)
Why multi-armed bandits are stateless — covered in Lecture 2 (Why MAB is "Stateless", 2.13)
Non-stationary bandit problems — covered in Lecture 3 (Non-Stationary Bandit Problems, 3.4)
Upper Confidence Bound (UCB) — covered in Lecture 3 (Upper Confidence Bound Action Selection, 3.8)
Contextual bandits — covered in Lecture 2 (When MAB is Not Enough: Contextual Bandits, 2.34) and Lecture 3 (Contextual Bandits: Bridging MAB and Full RL, 3.10)

Markov Decision Processes

4.1 Recap and Transition to Full Reinforcement Learning

4.1.1 What We Have Covered So Far

Hook: You have been playing a slot machine with many arms. You learned which arm pays best. But what if the best arm changes depending on where you are standing? That is the jump we are about to make.

Before looking at full RL, let us recap the key ideas from the multi-armed bandit formulation. These ideas carry forward and will appear again.

A multi-armed bandit is a simplified RL problem. You have several actions (arms). You pull one and get a reward. You track how good each action is — this is the value of an action. You learn which arm pays best over time.

You learned two ways to pick actions:

Greedy — always pick the best-known action.
Random — sometimes explore other actions to see if they are better.

This creates the exploration versus exploitation trade-off. You start knowing nothing, so you must explore. As you learn, you want to exploit what you know. Epsilon-greedy action selection (ε-greedy) handles this: with probability ε you explore randomly, with probability 1−ε you pick the best-known action. The UCB (Upper Confidence Bound) method is smarter — it balances exploration by accounting for uncertainty in action-value estimates. Arms you have not tried much get a bonus because their true value is uncertain.

You also covered stationary versus non-stationary problems. In a stationary problem, the reward distributions never change. In a non-stationary problem, they shift over time. Your learning approach must adapt — for example, by using a step-size parameter that weights recent rewards more heavily.

Finally, you looked at contextual bandits. Here, extra information (context) helps inform your action choice. But the choice is still not tied to a state — the context does not change based on your action.

Q: Is UCB particularly important for the exam?

A: Yes — UCB, exploration versus exploitation, epsilon-greedy, and the stationary/non-stationary distinction are the things you should be very well versed with and revisit before the exam.

4.1.2 Entering Full Reinforcement Learning: States

Hook: In a bandit, you stand in one spot and pull arms. In full RL, the world around you changes based on what you do. Your next decision depends on where you ended up.

In the multi-armed bandit problem, there is no notion of states. You simply pull one of the available actions and track values. Now we add a new ingredient: states. You must select actions in the context of a state.

Think of autonomous driving. The car is driving uphill. The slope is steep. There is a vehicle ahead. All these contribute to the state. When you want to know what action to take, you look at the current state. In soccer-playing robots, each robot must choose actions based on the current game state. In portfolio management, the system must consider what is happening in the world, in the company, and in your profile to recommend buy, sell, or hold.

Intuition + Analogy: A bandit is like a fixed slot machine — you stand in one place and pull levers. Full RL is like navigating a maze — each move changes your position, and the right move depends on where you are now. The analogy breaks down because in RL the maze itself can be stochastic: the same move might land you in different places.

The key shift: your job is always to take an action given a state. You never take an action in isolation. The action selection is coupled with states. In bandits, you estimate $q (a)$ — the value of action $a$ . In full RL, you estimate $q (s, a)$ — the value of action $a$ in state $s$ . That extra dimension is what makes RL richer and harder.

4.2 Course Roadmap

4.2.1 Next Three Classes

The next three classes follow a logical chain:

Markov Decision Processes (MDP) — a formal, mathematical way to define an RL problem. You will learn what an MDP is, how to model a problem using it, and study key mathematical definitions including Bellman equations.
Solving MDPs — once the problem is specified as an MDP, you can solve it using dynamic programming, learning-based approaches, data-driven statistical solutions, and more.
Dynamic Programming (DP) solution — the first solution approach, applied when the full MDP is known.

Think of it as: define the problem (MDP), write the equations (Bellman), then solve them (DP). These three steps are what you will cover.

4.2.2 Agent-Environment Interface Refresher

Hook: Every RL problem has the same shape — an agent acts, the world responds, and the agent learns from the feedback. Understanding this loop is the foundation for everything that follows.

Before looking at MDP, recall the agent-environment interface. The agent is at the center of every RL problem. The agent interacts with the environment. The environment gives feedback. The agent chooses actions to maximize the cumulative rewards it accumulates over the long term — the return.

It is not merely about the immediate reward. Sometimes a large immediate reward leads to nothing afterward. Smaller sustained rewards over time can add up to much more.

Intuition + Analogy: Think of a chess game. Each move (action) changes the board (state). You get no reward until the end (win/lose/draw). A flashy sacrifice might feel good but lead to a loss. The agent must think long-term, not just about the next move. The analogy breaks because in RL rewards can come at every step, not just at the end.

The interaction sequence looks like this:

Start at state $S_{0}$
Take action $A_{0}$
Environment responds with reward $R_{1}$ and new state $S_{1}$
Take action $A_{1}$
Environment responds with reward $R_{2}$ and new state $S_{2}$
Take action $A_{2}$
Environment responds with reward $R_{3}$ and new state $S_{3}$

And this repeats. This trajectory — $S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, S_{2}, A_{2}, R_{3}, \dots$ — is the fundamental sequence of RL. Every concept in this lecture builds on it.

4.3 The Markov Property

4.3.1 Definition and Intuition

Hook: How much of the past do you need to remember to make a good decision right now? The Markov property says: only the present matters.

When you take an action at a given point — say at state $S_{3}$ — you look only at the most recent state. You do not look at the entire history ( $S_{0} \to S_{1} \to S_{2} \to S_{3}$ ). The state must satisfy the Markov property: it must contain everything necessary to make an action decision.

Intuition + Analogy: Think of a board game like chess. To decide your next move, you only need the current board position — not the sequence of moves that led to it. The board position is Markov because it captures everything relevant. If you also needed to know "how many moves ago did the opponent castle?" then the board alone would not be Markov — you would need to add that information to the state. The analogy breaks because in RL the "board" can include hidden information like battery levels or sensor readings.

The state must cover, must represent, everything that is necessary to make an action selection. If you need to know battery level, the state must include battery level. If the road condition matters, the state must capture it.

Formally, the Markov property holds when:

$Pr {S_{t + 1} ∣ S_{t}, A_{t}} = Pr {S_{t + 1} ∣ S_{0}, A_{0}, S_{1}, A_{1}, \dots, S_{t}, A_{t}}$

This means: given the current state $S_{t}$ and action $A_{t}$ , knowing the full history does not add any extra information about what comes next. The current state is a sufficient summary of the past.

Pitfall: The Markov property is a property of the state representation, not of the problem itself. If your state does not capture enough information, the Markov property fails. The fix is to redesign the state — add the missing information. For example, if the agent's speed matters but is not in the state, add it.

4.3.2 Testing the Markov Property: Battery Level

Consider a grid world. The simplest state description is just your location — where you are now (row and column). But suppose the battery is almost dead. If you take no action and wait, you might get recharged. If you move left or right blindly, you might fall into a pit and lose a large penalty.

So sometimes including battery level as part of the state helps. It lets the agent make smarter decisions.

Worked Example: Suppose you are at cell (2, 3) in a grid world.

State = location only: (2, 3). The agent does not know the battery level. It might move and drain the battery, falling into a pit.
State = location + battery: (2, 3, low). Now the agent knows the battery is low. It can choose to wait and recharge instead of moving blindly.

The second state is Markov — it contains everything needed for a good decision. The first is not Markov — the missing battery info could change the best action.

The state description is a design choice: location alone or location plus battery level. You must check: does my state capture everything that affects what happens next? If yes, it is Markov. If no, add the missing information.

The Markov property is about sufficiency. The state must be a sufficient summary of the past for predicting the future. If it is not, enrich it.

4.4 Grid World Example

4.4.1 Environment Setup

Hook: Imagine a maze where the floor might crumble under your feet. You cannot always control where you end up. That is the grid world — a simple playground where we test RL ideas before scaling up to real problems.

Here is a grid world. An agent starts somewhere in the grid. The grid has:

Cells where the agent can be at any time.
A pit — if the agent steps in, there is no way out. No matter which direction you move, you stay trapped.
Terminal states — reaching one specific state gives +1, another gives −1.
The agent cannot leave the environment — walls block movement.

Intuition + Analogy: Think of the grid world as a board game on a chessboard. Some squares are safe, some are traps (the pit), and some are goals (+1 or −1). The agent is a game piece. The twist: when you try to move, the piece might slide in a different direction. The analogy breaks because in a real board game you control your piece exactly — here, actions are noisy.

4.4.2 Actions

The agent has four actions: up, down, left, right. These actions are noisy — not deterministic. If you press up:

80% of the time, you go up as intended.
20% of the time, the move fails and you go to one of the other three directions (10% to left, 10% to right — the exact split across remaining directions depends on the specification).

Pitfall: Do not confuse "noisy actions" with "wrong actions." The agent is not making a mistake — the environment is stochastic. Even the best action can fail. This is why we need probabilities, not just rules.

This uncertainty captures that in the real world, actions do not always work as planned. When you press the brake in a car, 99% of the time the car stops. 1% of the time, something unexpected happens. When you drive in bumper-to-bumper traffic in first gear, things usually move as expected, but there is a chance the clutch gets stuck. You can factor that uncertainty in.

4.4.3 Rewards

The environment gives back rewards. To encourage reaching the goal quickly (before the "battery dies"), you give −1 for every step the agent takes. Reaching a good terminal gives +1. Reaching a bad terminal gives −1 (or even −100 if you want to heavily penalize it).

Worked Example: Suppose the agent is 3 steps from the +1 goal and 2 steps from the −1 pit.

Path to goal: 3 steps × (−1) + (+1) = −2
Path to pit: 2 steps × (−1) + (−1) = −3

The agent should prefer the goal path (−2 > −3). But with noisy actions, it might accidentally fall into the pit. The agent must plan for uncertainty.

Sense-check: The per-step penalty of −1 makes the agent prefer shorter paths. Without it, the agent might wander forever.

This reward design is intentional. The −1 per step acts like a ticking battery — it nudges the agent to find the shortest path. It is a common trick in RL: small negative rewards for each step encourage efficiency.

4.5 The Elements of MDP

4.5.1 Overview

Hook: Every RL problem, from a game of chess to a self-driving car, can be broken into the same five ingredients. Learn these five, and you can model any sequential decision problem.

To model a problem as an MDP, you must pin down these elements:

State space — the set of all possible states.
Action space — the set of all possible actions, and whether they are deterministic or noisy.
Model dynamics (transition probabilities) — how the environment behaves in response to your action.
Reward function — what the environment gives back.

These are the first four elements. The fifth — policy — is what you want to learn. Let us examine each.

4.5.2 Element 1: State Space

The state space $S$ is the set of all possible states. The state is what you track about the environment. In the grid world, it can be just your location (row, column) or location plus battery level. The choice of what goes into the state is a design decision.

Intuition + Analogy: The state is like a medical chart. A doctor decides what information to include — blood pressure, heart rate, allergies. Include too little, and you miss something critical. Include too much, and the chart is hard to read. The art is choosing the right level of detail. The analogy breaks because in RL the state must satisfy the Markov property — it must be sufficient for the decision at hand.

For a traffic signal control problem, the state might include queue lengths at each lane, average waiting times, and current phase. For a video game, the state might be the last three frames concatenated — this captures motion direction, not just a static image.

4.5.3 Element 2: Action Space

The action space $A (s)$ lists all possible actions available in state $s$ . Actions may be:

Deterministic: the outcome is always the same.
Noisy (stochastic): the outcome has a probability distribution.

For the traffic signal, actions might be: extend the current phase, or switch from phase 1 to phase 2 (if admissible). There are eight possible phases (valid green-light combinations for the intersection).

4.5.4 Element 3: Reward Function

The reward function maps state-action-next-state triples to a scalar number. The reward is a single scalar signal. The environment does not give back a detailed report card — it gives one number. That number is the basis for all learning.

Pitfall: The reward signal is not the place to tell the agent how to achieve the goal. It should only signal what the goal is. If you reward sub-goals (like "take opponent's pieces" in chess), the agent might exploit those rewards without winning the game.

The reward signal must indicate what is expected good behavior. If you reward wrong actions, you train a wrong agent. For example, in an office, if you are never penalized for poor performance, your behavior adjusts accordingly. The reward function should direct the agent toward the desired behavior.

Designing the right reward function often requires significant expertise. In traffic signal control, if your objective is to give a reasonable waiting time to all lanes:

Reward could be the negative of average delay. If delay is more, the negative reward is worse.
Or it could be the negative of queue length.

Q: Who decides the rewards when programming an RL system?

A: The signals come from the environment. In autonomous driving where your priority is a smooth drive, moderate speed, and respecting lane lines, you must take all these aspects, weight them, and make one number. The world does not give you a single ready-to-use number. The RL engineer extracts cues from the world and formulates that single scalar reward.

Exam note: The reward function drives the learning. A badly designed reward function trains a badly behaving agent. Expect questions on how to design rewards for specific tasks.

4.5.5 Element 4: Model Dynamics (Transition Probabilities)

4.5.5.1 Formal Definition

Symbol Registry — Model Dynamics

$s$ — current state — $s \in S$ — one of the finite set of states
$a$ — action taken — $a \in A (s)$ — one of the actions available in state $s$
$s^{'}$ — next state — $s^{'} \in S$ — the state the environment transitions to
$r$ — reward — $r \in R$ — scalar reward
$p (s^{'}, r ∣ s, a)$ — model dynamics — $Pr {S_{t + 1} = s^{'}, R_{t + 1} = r ∣ S_{t} = s, A_{t} = a}$ — probability of landing in $s^{'}$ with reward $r$

The model dynamics is a big table of probabilities. It says: if you are in state $s$ and take action $a$ , what is the probability of ending up in state $s^{'}$ with reward $r$ ?

$p (s^{'}, r ∣ s, a) = Pr {S_{t + 1} = s^{'}, R_{t + 1} = r ∣ S_{t} = s, A_{t} = a}$

Intuition: Think of the model dynamics as a weather forecast for every possible day. If today is sunny (state) and you carry an umbrella (action), what is the chance you end up dry (next state) with happiness (reward)? The model dynamics is that complete forecast for every state-action pair.

For all states and all possible actions in each state, if this behavior is defined, you have a complete description of how the environment behaves — you have an MDP.

The textbook (Sutton & Barto, §3.1) defines this as equation (3.2) and notes that $p$ is a deterministic function of four arguments. The probabilities from a given $(s, a)$ pair must sum to 1:

$s^{'} \in S \sum r \in R \sum p (s^{'}, r ∣ s, a) = 1$

This is the normalization constraint. It ensures the model dynamics is a valid probability distribution.

4.5.5.2 Interpreting the Model Dynamics Table

Worked Example: You are in state $R$ . The actions available are start and stop.

$s$	$a$	$s^{'}$	$r$	$p (s^{'}, r ∣ s, a)$
$R$	start	$W$	4	0.6
$R$	start	$W$	2	0.2
$R$	start	$R$	0	0.2
$R$	stop	$T$	1	1.0

Verifying a proper table: For a given $(s, a)$ pair, all probabilities must sum to 1.

For $(R, start)$ : $0.6 + 0.2 + 0.2 = 1.0$ . Valid.

For $(R, stop)$ : $1.0 = 1.0$ . Valid.

Sense-check: From $R$ , taking start can lead to $W$ (with reward 4 or 2) or stay at $R$ (with reward 0). Taking stop always goes to $T$ with reward 1. The table captures all possible outcomes.

4.5.5.3 Visualization of Model Dynamics

Assume you are in state $s$ and you take action $a$ . There are two ways to visualize what happens:

Deterministic case (probability = 1):

$p (s_{1}, 7 ∣ s, a) = 1$

You go to $s_{1}$ with reward 7 for sure.

Stochastic case:

Pressing the brake in a car — you are in a state and take action "brake":

With probability 0.95, the car stops ( $s_{1}$ ), reward +100.
With probability 0.05, the car does not stop ( $s_{2}$ ), reward −1000.

$p (s_{1}, 100 ∣ s, brake) = 0.95$

$p (s_{2}, - 1000 ∣ s, brake) = 0.05$

The model dynamics captures this uncertainty. Think of applying for a promotion. The outcomes could be: get promoted with 5% increment, get promoted with 20% increment, or not get promoted. Each has a probability.

Q: In the car braking example, is the 5% failure (sliding/skidding) an inherent property of the car itself, or is it due to driving on a snowy road?

A: The answer lies in what the state captures. If the state says "snowy road," the model dynamics for the same brake action should evoke different behavior from the environment. The state must describe the road condition. The model dynamics can be different for the same action in different states.

Q: The model dynamics table shows discrete rewards, but rewards are often continuous. How do we handle that?

A: For ease of explanation, we are discussing finite Markov Decision Processes where states, actions, and rewards are all finite and discrete. This is an assumption made for communication. Real-world problems often have continuous states and rewards — those go beyond finite MDPs.

Scope: Everything in this lecture assumes a finite MDP. The state space $S$ , action space $A$ , and reward set $R$ are all finite. This is a simplification for learning. Real problems often need continuous spaces and function approximators.

The model dynamics $p (s^{'}, r ∣ s, a)$ is the complete description of how the environment works. If you know it, you know everything about the problem. The challenge is that in most real problems, you do not know it — you must learn it or work around it.

4.6 Deriving Quantities from Model Dynamics

4.6.1 State Transition Probabilities

Hook: The model dynamics table gives you the full picture — next state AND reward together. But often you only care about where you end up, not the reward. Can you extract just the movement probabilities? Yes, by summing over rewards.

From the full model dynamics table, you can sum over all possible rewards to get the state transition probability:

$p (s^{'} ∣ s, a) = r \in R \sum p (s^{'}, r ∣ s, a)$

Intuition: Think of it like this: you applied for a promotion (action) from your current role (state). The model dynamics tells you the chance of each outcome and each reward together. But if you only want to know "what is the chance I get promoted?" — regardless of the increment amount — you sum over all possible rewards. This collapses the joint probability into a marginal over next states.

Worked Example: Using the table from section 4.5:

From $R$ , taking start, going to $W$ :

$p (W ∣ R, start) = p (W, 4 ∣ R, start) + p (W, 2 ∣ R, start) = 0.6 + 0.2 = 0.8$

From $R$ , taking start, going to $R$ :

$p (R ∣ R, start) = p (R, 0 ∣ R, start) = 0.2$

From $R$ , taking stop, going to $T$ :

$p (T ∣ R, stop) = p (T, 1 ∣ R, stop) = 1.0$

Verification: For $(R, start)$ : $0.8 + 0.2 = 1.0$ . For $(R, stop)$ : $1.0$ . Both sum to 1. Valid.

Sense-check: From $R$ , taking start, you go to $W$ with 80% chance and stay at $R$ with 20% chance. This matches the intuition that start usually moves you forward.

The textbook (Sutton & Barto, §3.1, eq. 3.4) defines this as:

$p (s^{'} ∣ s, a) ≐ Pr {S_{t} = s^{'} ∣ S_{t - 1} = s, A_{t - 1} = a} = r \in R \sum p (s^{'}, r ∣ s, a)$

This is a marginalization — you collapse the reward dimension out of the joint distribution.

4.6.2 Expected Immediate Reward

You can compute the expected immediate reward for a given state-action pair. This tells you: on average, how much reward do I get right now if I take action $a$ in state $s$ ?

$r (s, a) = E [R_{t + 1} ∣ S_{t} = s, A_{t} = a] = r \in R \sum r s^{'} \in S \sum p (s^{'}, r ∣ s, a)$

The outer sum is over all possible rewards. The inner sum is over all possible next states. For each reward value $r$ , you weight it by the total probability of getting that reward (summed over all next states).

Worked Example: For $(R, start)$ :

$r (R, start) = 4 \cdot p (W, 4 ∣ R, start) + 2 \cdot p (W, 2 ∣ R, start) + 0 \cdot p (R, 0 ∣ R, start) = 4 \times 0.6 + 2 \times 0.2 + 0 \times 0.2 = 2.4 + 0.4 + 0 = 2.8$

For $(R, stop)$ :

$r (R, stop) = 1 \times 1.0 = 1.0$

Sense-check: Starting from $R$ and taking start gives an average reward of 2.8. Taking stop gives 1.0. The start action is more rewarding on average, which makes sense — it leads to outcomes with rewards 4 and 2 most of the time.

The textbook (Sutton & Barto, §3.1, eq. 3.5) defines this as:

$r (s, a) ≐ E [R_{t} ∣ S_{t - 1} = s, A_{t - 1} = a] = r \in R \sum r s^{'} \in S \sum p (s^{'}, r ∣ s, a)$

Note: the textbook uses $R_{t}$ with the previous state $S_{t - 1}$ , while the lecture uses $R_{t + 1}$ with $S_{t}$ . Both are equivalent — just a difference in time-indexing convention. The lecture convention is more common in RL courses.

4.6.3 Expected Reward for a Specific Transition

Hook: Sometimes you want to know: "I am in state $R$ , I took action start, and I ended up in state $W$ . What reward should I expect?" This is a conditional expectation — conditioned on a specific next state.

You can ask: "I applied for promotion, and I got promoted. What is my expected increment?"

Chances of getting promoted = $p (W ∣ R, start) = 0.8$ .

Among the 80% of cases where you get promoted:

60% of the time, the reward is 4.
20% of the time, the reward is 2.

Worked Example: The expected reward given the promotion happens is:

$r (R, start, W) = \frac{p ( W , 4 ∣ R , start )}{p ( W ∣ R , start )} \times 4 + \frac{p ( W , 2 ∣ R , start )}{p ( W ∣ R , start )} \times 2 = \frac{0.6}{0.8} \times 4 + \frac{0.2}{0.8} \times 2 = 0.75 \times 4 + 0.25 \times 2 = 3.0 + 0.5 = 3.5$

Sense-check: Given that you got promoted, the expected increment is 3.5. This is between 2 and 4, weighted toward 4 because the higher increment (4) is more likely (75% vs 25%).

More formally, the expected reward for a state-action-next-state triple is:

$r (s, a, s^{'}) = E [R_{t + 1} ∣ S_{t} = s, A_{t} = a, S_{t + 1} = s^{'}] = \frac{\sum _{r \in R} r \cdot p ( s ^{'} , r ∣ s , a )}{p ( s ^{'} ∣ s , a )}$

This is Bayes' rule in action. You divide the joint probability of $(s^{'}, r)$ by the marginal probability of $s^{'}$ to get the conditional expectation of $r$ given $s^{'}$ .

The textbook (Sutton & Barto, §3.1, eq. 3.6) defines this equivalently.

The model dynamics table lets you compute many things beyond what is directly written in it.

4.6.4 Complete Numerical Example: Start–Stop MDP & Deterministic Special Case

Step-by-Step Derivation of All Quantities (Start–Stop MDP):

Step 1: Check Probability Validity

For $(R, start)$ : $p (W, 4 ∣ R, start) + p (W, 2 ∣ R, start) + p (R, 0 ∣ R, start) = 0.6 + 0.2 + 0.2 = 1.0$ .

For $(R, stop)$ : $p (T, 1 ∣ R, stop) = 1.0$ . Valid probability model.

Step 2: Transition Probabilities $p (s^{'} ∣ s, a)$

$p (W ∣ R, start) = 0.6 + 0.2 = 0.8$

$p (R ∣ R, start) = 0.2$

$p (T ∣ R, stop) = 1.0$

Step 3: Expected Immediate Rewards $r (s, a)$

$r (R, start) = 4 (0.6) + 2 (0.2) + 0 (0.2) = 2.4 + 0.4 + 0 = 2.8$

$r (R, stop) = 1 (1.0) = 1.0$

Step 4: All Conditional Expected Rewards $r (s, a, s^{'})$

$r (R, start, W) = \frac{4 ( 0.6 ) + 2 ( 0.2 )}{0.8} = \frac{2.8}{0.8} = 3.5$

$r (R, start, R) = \frac{0 ( 0.2 )}{0.2} = 0$

$r (R, stop, T) = \frac{1 ( 1.0 )}{1.0} = 1.0$

Step 5: Deterministic Special Case

If both actions have exactly one deterministic outcome:

$p (W, 4 ∣ R, start) = 1.0 ⟹ p (W ∣ R, start) = 1.0, r (R, start) = 4$

$p (T, 1 ∣ R, stop) = 1.0 ⟹ p (T ∣ R, stop) = 1.0, r (R, stop) = 1$

Summary Comparison Table of Quantities:

Quantity	Mathematical Formula	Meaning in Start–Stop Example
$p (s^{'}, r ∣ s, a)$	$Pr {S_{t} = s^{'}, R_{t} = r ∣ S_{t - 1} = s, A_{t - 1} = a}$	Full joint probability of next state and reward together (e.g., $p (W, 4 ∣ R, start) = 0.6$ ).
$p (s^{'} ∣ s, a)$	$\sum_{r \in R} p (s^{'}, r ∣ s, a)$	Transition probability after marginalizing out reward (e.g., $p (W ∣ R, start) = 0.8$ ).
$r (s, a)$	$\sum_{r} r \sum_{s^{'}} p (s^{'}, r ∣ s, a)$	Average immediate reward for choosing action $a$ in state $s$ (e.g., $r (R, start) = 2.8$ ).
$r (s, a, s^{'})$	$\frac{\sum _{r} r p ( s ^{'} , r ∣ s , a )}{p ( s ^{'} ∣ s , a )}$	Average immediate reward when next state $s^{'}$ is also fixed (e.g., $r (R, start, W) = 3.5$ ).

From the single model dynamics function $p (s^{'}, r ∣ s, a)$ , you can derive: state transition probabilities $p (s^{'} ∣ s, a)$ , expected immediate rewards $r (s, a)$ , and conditional expected rewards $r (s, a, s^{'})$ . The model dynamics is the master table.

4.7 Finite vs Infinite MDP

4.7.1 The Finite MDP Assumption

Hook: We have been talking about tables of probabilities. But what if the table has a billion rows? You cannot store it. That is the gap between finite MDPs and the real world.

For communication purposes, the discussion focuses on finite MDPs where the sets of states, actions, and rewards are all finite. This is not the general case. Real-world problems may have:

Continuous state spaces (sensor readings, camera inputs, queue lengths).
Continuous rewards (not just discrete numbers like 4, 2, 0, 1).

Intuition + Analogy: A finite MDP is like a board game with a fixed number of squares and dice outcomes. You can list every possibility. A continuous MDP is like driving on a highway — your speed, position, and the distances to other cars are real numbers. You cannot list every possible state. The analogy breaks because even continuous problems can sometimes be discretized for approximation.

In the traffic signal example, queue lengths and waiting times are real numbers, not discrete categories. The reward is the negative of delay, which is continuous. The state space is huge. You cannot enumerate all states to build a table — the transition dynamics must be modeled differently (e.g., using a function approximator).

Scope: The finite MDP assumption is a teaching tool. It lets us define $p (s^{'}, r ∣ s, a)$ as a table. In practice, most interesting problems violate this assumption. But the concepts — states, actions, rewards, transitions, policies, value functions — carry over to the continuous case. You just need different computational tools (function approximators, neural networks, etc.).

But starting with finite MDPs teaches the core ideas before scaling up.

Finite MDPs are the foundation. The concepts generalize to continuous spaces, but the math tools change. Learn the finite case first.

4.8 Example MDP Formulations

4.8.1 Video Game (Atari-style)

Hook: How would you teach a computer to play a video game it has never seen? You define what it sees (state), what it can do (actions), and what "doing well" means (reward). That is MDP formulation.

MDP Formulation — Atari Video Game:

State: Representation of recent frames. The current frame alone, or the last three to five frames concatenated. Including multiple frames lets the agent model motion direction — a single frame is a static image, but three frames show which way things are moving.
Actions: Left, right, up, down (joystick moves).
Reward: The score increment shown on screen. If the score goes from 20 to 23, the reward is +3. If you lose a life, it goes negative.
Transition: The emulator takes your action, applies it to the game, and returns the new screen configuration. The transition is deterministic given the game engine — but the agent does not know the engine, so it must learn.
Policy: A rule that maps the current state (screen frames) to an action (joystick move).

Worked Example: Suppose the current score is 150. The agent moves right and destroys an enemy. The new score is 160. The reward is $160 - 150 = + 10$ . The new state is the new screen (or the last 3 frames including this one).

If the agent moves right and gets hit by an enemy, the score drops from 150 to 150 (no change) but a life is lost. The reward might be −100 (penalty for losing a life).

4.8.2 Traffic Signal Control

MDP Formulation — Traffic Signal Control:

State: Queue lengths and average waiting times for each lane. These are extracted from camera inputs and reduced to numbers. For a four-lane intersection, the state is a vector of queue lengths plus a vector of waiting times.
Actions: The intersection has eight possible phases (valid green-light combinations). Actions are: extend the current phase, or switch from the current phase to an admissible next phase.
Reward: Depends on the objective — negative of average delay, negative of maximum queue length, or maximization of throughput. The choice requires domain expertise. The reward function drives the learning, so it must be designed carefully.
Transition: Highly complex — cannot be stored as a table. Requires a probabilistic function or simulator. Traffic flow depends on time of day, events, weather, and more.
Policy: What the learning produces — a mapping from current state to action.

Pitfall: The state space for traffic signals is enormous. Queue lengths are real numbers. You cannot enumerate all states. This is where finite MDP theory breaks down in practice — you need function approximators (like neural networks) to handle it.

4.8.3 Recycling Robot (Textbook Example 3.3)

Symbol Registry — Recycling Robot

High — high battery level — state
Low — low battery level — state
search — action: actively look for cans — available in both High and Low
wait — action: stay in place and wait for cans — available in both High and Low
recharge — action: recharge the battery — available in Low only
$α$ — probability battery stays High after searching — $p (High ∣ High, search)$
$β$ — probability battery stays Low after searching — $p (Low ∣ Low, search)$
$R_{search}$ — reward for searching (securing a can) — scalar
$R_{wait}$ — reward for waiting — scalar (smaller than $R_{search}$ )
$R_{recharge}$ — penalty (−3) when battery is fully exhausted and must be rescued — scalar

This is Example 3.3 (boxed) from the Sutton & Barto textbook. It is a high-level decision-making agent. A recycling robot has sensors to detect cans and an arm with a gripper to pick them up and drop them in a bin. It runs on a rechargeable battery. The objective is to decide how to search for cans based on the current battery charge level.

Intuition: The recycling robot is like a person with a phone battery. When the battery is high, you can browse freely. When it is low, you must decide: keep browsing (search), put the phone down (wait), or plug it in (recharge). If you browse too long at low battery, the phone dies and you lose time (the −3 penalty for being rescued).

States: Two battery levels — high and low. (The state only tracks battery because battery drives all decisions.)

Actions:

When battery is High: search or wait.
When battery is Low: search, wait, or recharge.
Recharging is not allowed when the battery is already high.

Rewards: The robot gets nothing most of the time. It gets a reward only when it secures a can. Searching yields far more cans than waiting — waiting means a can is dropped next to the robot by someone else. The reward for searching ( $R_{search}$ ) is greater than the reward for waiting ( $R_{wait}$ ).

Model Dynamics (visualized as a graph):

From High, taking wait: with probability 1, you stay in High and get reward $R_{wait}$ . Only one outcome.
From High, taking search: two outcomes.
- Battery stays High with probability $α$ , reward $R_{search}$ .
- Battery goes Low with probability $1 - α$ , reward $R_{search}$ .
From Low, taking wait: with probability 1, you stay in Low and get $R_{wait}$ .
From Low, taking search: two outcomes.
- Battery stays Low with probability $β$ , reward $R_{search}$ .
- Battery gets fully exhausted with probability $1 - β$ . The robot is rescued, gets a penalty of −3, and is taken back to High (battery recharged by the rescuer).
From Low, taking recharge: with probability 1, go to High. Get no cans (reward = 0).

Worked Example — Transition Table:

$s$	$a$	$s^{'}$	$p (s^{'} ∣ s, a)$	$r (s, a, s^{'})$
High	search	High	$α$	$R_{search}$
High	search	Low	$1 - α$	$R_{search}$
High	wait	High	1	$R_{wait}$
Low	search	Low	$β$	$R_{search}$
Low	search	High	$1 - β$	−3
Low	wait	Low	1	$R_{wait}$
Low	recharge	High	1	0

Verification: Each $(s, a)$ pair has probabilities summing to 1. For (High, search): $α + (1 - α) = 1$ . For (Low, search): $β + (1 - β) = 1$ . Valid.

Sense-check: Searching from High is safe (no risk of exhaustion). Searching from Low risks the −3 penalty. Recharging is safe but yields no reward. The robot must balance collecting cans against the risk of running out of battery.

Q: Does this MDP formulation resemble finite state machines from automata theory?

A: At a high level of abstraction, yes — both use states, actions, and transitions. But there is a critical difference: Turing machines and automata are deterministic — a given input always produces the same output. MDPs are probabilistic. The same action from the same state can lead to different outcomes with different probabilities. Keep these separate for now.

Q: How is this different from a contextual bandit?

A: In a true contextual bandit, actions are not tied to the context. Context provides additional information for your decision — like knowing it is raining might change your playlist choice in the car but not your driving actions. In MDP, the action you take depends directly on what the current state is. The action is always taken given the state ( $A ∣ S$ — never separated). Your driving actions (brake, accelerate) depend on the road state. Your playlist choice depends on the passenger context. These are two different decision layers. The line is subtle, and you must be careful when modeling — decide whether a factor is a context (additional info) or a state (drives action choice).

Pitfall: Do not confuse contextual bandits with MDPs. In a contextual bandit, the context does not change based on your action. In an MDP, the state transitions depend on what you do. The key test: does your action affect the next state? If yes, it is an MDP. If no, it is a contextual bandit.

Any sequential decision problem can be formulated as an MDP by defining states, actions, transitions, and rewards. The art is choosing the right level of detail for states and the right reward function.

4.9 Reward Hypothesis and Return

4.9.1 The Reward Hypothesis

Hook: What is the one thing every RL agent cares about? A single number. That number is the reward. Everything else — states, actions, policies — exists to maximize that number over time.

The Reward Hypothesis: Every RL problem can be thought of as the maximization of the expected value of the cumulative sum of the received scalar signal (reward).

Breaking this down:

Reward — a scalar number the environment gives back.
Cumulative sum — we add up rewards over time, not just the immediate one.
Expected value — the future is unknown, so we maximize what we expect to get, on average.

The textbook (Sutton & Barto, §3.2) states this as: "all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (called reward)."

If the reward function is formulated wrongly, the entire learning goes wrong. The cumulative sum matters because you want sustained good behavior, not just one lucky reward spike.

Pitfall: Do not reward sub-goals. If you reward a chess agent for taking pieces, it might take pieces and still lose. The reward should reflect the true goal: winning the game.

4.9.2 Return: Simple Sum

The return $G_{t}$ is the sum of all future rewards from time step $t$ . It is what the agent wants to maximize.

Assume you are at time step $t$ and in state $S_{t}$ . The return is:

$G_{t} = R_{t + 1} + R_{t + 2} + R_{t + 3} + \dots = k = 0 \sum \infty R_{t + k + 1}$

This is a simple sum. Every future reward is weighted equally.

Intuition: Think of the return as your total salary over a career. If you earn ₹50,000 every month for 30 years, your return is $50, 000 \times 360 = 1, 80, 00, 000$ . Every month counts the same.

The problem: if the horizon is infinite and rewards are positive, this sum can diverge to infinity. That is where discounting comes in.

4.9.3 Return: Discounted Sum

A more common definition uses a discount factor $γ$ (gamma, between 0 and 1) to give more importance to the present than the future:

$G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots = k = 0 \sum \infty γ^{k} R_{t + k + 1}$

Every symbol named:

$G_{t}$ — the return from time step $t$
$R_{t + k + 1}$ — the reward received $k + 1$ steps into the future
$γ$ — the discount factor, $0 \leq γ \leq 1$
$k$ — the index of summation, starting from 0

The discount factor $γ$ controls how much you value future rewards:

$γ = 0$ : You are a hedonist — only the immediate reward matters. Everything beyond now is ignored. $G_{t} = R_{t + 1}$ .
$γ = 1$ : You are a yogi — present and future are equal. No discounting. $G_{t} = R_{t + 1} + R_{t + 2} + R_{t + 3} + \dots$ .
Typically, $γ$ is close to 1 (e.g., 0.9, 0.95, 0.99) — you care about the future but discount it slightly.

Why discount?

Mathematical guarantee: With an infinite horizon, a simple (undiscounted) sum can go to infinity. If every reward is 1, the sum $\sum 1 = \infty$ . With discounting ( $γ < 1$ ): $\sum_{k = 0}^{\infty} γ^{k} = \frac{1}{1 - γ}$ . For $γ = 0.9$ , this is $\frac{1}{0.1} = 10$ — a finite number. This ensures you can always compare values between states without facing infinities.
Intuition: ₹1000 today is worth more than ₹1000 two years from now. The further into the future, the less certain the outcome, so you discount it.
Practical comparison: Consider choosing between a 20 km detour for great coffee versus nearby average coffee. Even though the great coffee is "better," the cost of the detour diminishes its net value. Discounting captures this intuition.

Worked Example — Discounted Sum: Suppose $γ = 0.5$ and the reward sequence is $R_{1} = - 1$ , $R_{2} = 2$ , $R_{3} = 6$ , $R_{4} = 3$ , $R_{5} = 2$ , with $T = 5$ .

Working backwards:

$G_{5} G_{4} G_{3} G_{2} G_{1} G_{0} = 0 (terminal) = R_{5} + γ G_{5} = 2 + 0.5 \times 0 = 2 = R_{4} + γ G_{4} = 3 + 0.5 \times 2 = 3 + 1 = 4 = R_{3} + γ G_{3} = 6 + 0.5 \times 4 = 6 + 2 = 8 = R_{2} + γ G_{2} = 2 + 0.5 \times 8 = 2 + 4 = 6 = R_{1} + γ G_{1} = - 1 + 0.5 \times 6 = - 1 + 3 = 2$

Sense-check: $G_{0} = 2$ means the total discounted return from the start is 2. The early negative reward is outweighed by the later positive rewards.

Q: Why discount the future? Why not discount the past?

A: The past is irrelevant — you are in state $s$ now. What happened before you got there does not matter for what you should do next. Only what comes after matters. And discounting the future prevents infinite sums when the horizon is unlimited.

Q: How far ahead do we sum? The number of steps is undefined.

A: You do not need to define a stopping point. The discount factor ensures the sum converges to a finite value. In continuous control (like a nuclear reactor that runs forever), you never stop — but with $γ < 1$ , the sum is mathematically guaranteed to be finite. In episodic tasks where the horizon is known and finite (e.g., 1000 steps), discounting is less critical — a simple sum works. But the standard formalism uses discounted return for consistency across both episodic and continuous problems.

Exam note: The discounted return formula $G_{t} = \sum_{k = 0}^{\infty} γ^{k} R_{t + k + 1}$ and the recursive form $G_{t} = R_{t + 1} + γ G_{t + 1}$ are fundamental. Expect to compute returns by hand given a reward sequence and a discount factor.

4.9.4 Recursive Form of Return

The discounted return has a clean recursive form:

$G_{t} = R_{t + 1} + γ G_{t + 1}$

This is one of the most important equations in RL. It says: the return from now equals the immediate reward plus the discounted return from one step later.

The derivation is straightforward:

$G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots = R_{t + 1} + γ (R_{t + 2} + γ R_{t + 3} + \dots) = R_{t + 1} + γ G_{t + 1}$

Step by step:

Write out the full discounted sum.
Factor $γ$ out of everything after the first term.
Recognize that the bracketed expression is $G_{t + 1}$ .

Intuition: Think of Russian nesting dolls. The big doll ( $G_{t}$ ) contains the immediate reward ( $R_{t + 1}$ ) and a smaller doll ( $G_{t + 1}$ ) scaled down by $γ$ . That smaller doll contains its own immediate reward and an even smaller doll, and so on. Each doll is a scaled copy of the next.

This recursion is fundamental. It will appear again in the Bellman equations. The current return equals the immediate reward plus the discounted return from the next state onward. $G_{t + 1}$ summarizes the entire future.

Pitfall: Do not forget that $G_{t}$ depends on the rewards from time $t + 1$ onward, not from $t$ . The reward $R_{t}$ is not part of $G_{t}$ . The return $G_{t}$ is the sum starting with $R_{t + 1}$ .

4.10 Episodic vs Continuous Tasks

4.10.1 Classification

Hook: Does the game ever end? That single question changes how you define the return, how you design the reward, and whether you need a discount factor.

Tasks fall into two categories:

Episodic tasks: The interaction has a natural endpoint. Each episode ends in a terminal state. After the episode ends, you reset and start a new one. Example: a game of chess — it ends at checkmate or draw. Another example: a maze — the episode ends when you reach the exit or fall into a trap.
Continuous tasks: The interaction goes on forever with no natural endpoint. Example: controlling a nuclear reactor, or a robot that must balance a pole indefinitely.

Intuition + Analogy: Episodic tasks are like rounds in a boxing match. Each round ends, you rest, and a new round starts. Continuous tasks are like a marathon — you run until you cross the finish line, but there is no "restart" in the middle. The analogy breaks because in RL, continuous tasks literally never end.

The textbook (Sutton & Barto, §3.3) notes that in episodic tasks, the return is a finite sum (up to the terminal time step $T$ ), while in continuous tasks, the return is an infinite sum that needs discounting to stay finite.

4.10.2 Cart-Pole Balancing Example

Worked Example — Cart-Pole as Episodic vs Continuous:

Consider the cart-pole problem. A pole is mounted on a cart. The cart must move left and right to keep the pole balanced. The pole can fall in either direction.

Episodic modeling:

Episode starts with pole upright.
Episode ends when the pole falls past a threshold angle.
Reward: +1 for every time step the pole stays up.
Return: total number of steps before failure. No discounting needed ( $γ = 1$ works because the episode is finite).
Goal: maximize the length of the episode.

Continuous modeling:

The task runs forever — the pole is reset instantly when it falls.
Reward: 0 for each step the pole is balanced, −1 when it falls.
Return: $G_{t} = \sum_{k = 0}^{\infty} γ^{k} R_{t + k + 1}$ with $γ < 1$ .
Goal: maximize the fraction of time the pole is balanced.

You can model it either way. The choice affects your reward design and whether you use a discount factor.

Scope: The choice between episodic and continuous is a modeling decision, not a property of the physical task. The same cart-pole can be modeled either way. The choice affects reward design, discount factor, and the algorithms you can use.

Exam note: Think about reward and gamma choices for episodic vs continuous modeling. If episodic, $γ = 1$ is often fine. If continuous, you must have $γ < 1$ . The textbook notes that the convention $G_{T} = 0$ (return at the terminal state is zero) makes the recursive form $G_{t} = R_{t + 1} + γ G_{t + 1}$ work even at the last step before termination.

4.11 Policy

4.11.1 Definition

Hook: The agent is in a state. What should it do? The policy is the answer — it is the agent's playbook, telling it what to do in every situation.

A policy $π$ is the agent's behavior rule. It maps states to actions. Formally:

$π (a ∣ s) = Pr {A_{t} = a ∣ S_{t} = s}$

This is the probability of taking action $a$ given that you are in state $s$ .

Every symbol named:

$π$ — the policy (the agent's behavior rule)
$a$ — a specific action
$s$ — a specific state
$π (a ∣ s)$ — the probability of choosing action $a$ in state $s$
$A_{t}$ — the random variable for the action at time $t$
$S_{t}$ — the random variable for the state at time $t$

The textbook (Sutton & Barto, §3.5) defines policy as "a mapping from states to probabilities of selecting each possible action." The notation $π (a ∣ s)$ uses the "|" to remind us that it defines a probability distribution over actions for each state — just like conditional probability notation.

Intuition: Think of a policy as a recipe book. Each page (state) lists the ingredients (actions) and how likely you are to use each one. A deterministic policy is a recipe that says "always use flour." A stochastic policy says "70% flour, 30% cornstarch."

4.11.2 Types of Policies

Stochastic policy: The policy gives a probability distribution over actions. Multiple actions have nonzero probability.

Example: In a grid, from state $s$ :

$π (up ∣ s) = 0.9$
$π (left ∣ s) = 0.03$
$π (right ∣ s) = 0.03$
$π (down ∣ s) = 0.04$

These sum to 1: $0.9 + 0.03 + 0.03 + 0.04 = 1.0$ .

Deterministic policy: One action gets probability 1, all others get 0.

Example: $π (up ∣ s) = 1$ , everything else = 0. Always go up from this state.

When a policy is deterministic, you simply follow it. When stochastic, you must sample from the distribution.

Worked Example: Suppose you are in state $s$ with the stochastic policy above. You roll a random number between 0 and 1.

If the number is in [0, 0.9): go up. This happens 90% of the time.
If in [0.9, 0.93): go left. This happens 3% of the time.
If in [0.93, 0.96): go right. This happens 3% of the time.
If in [0.96, 1.0]: go down. This happens 4% of the time.

Over 1000 steps from state $s$ , you would go up about 900 times, left about 30 times, right about 30 times, and down about 40 times.

4.11.3 Policy and Value: Visual Intuition

Consider a small grid with terminal states whose values are shown. Inside each cell is a value — a number representing the expected return from that state. The arrows indicate the dominant action from the policy — the direction with the highest probability. The policy points toward states with higher values, because following that path maximizes expected return.

Intuition: Imagine a hiker on a foggy hillside. The hiker cannot see the summit but can feel the slope under their feet. The policy is the hiker's strategy: "always walk uphill." The value of each position is how close it is to the summit. The policy points uphill because that is where the value is higher.

For a given state $S_{1}$ , the value is: if you are in that state and continue acting (according to the policy), what is the expected discounted sum of future rewards? If reaching a terminal gives +1 and intermediate rewards are 0 (discounted by $γ$ each step), the value might be something like 0.64.

Key insight: you decide a policy based on these value numbers. Formally define the value function, then use it to decide the policy. This is the foundation of RL: estimate values, then act greedily on those estimates.

The policy $π$ is the agent's behavior rule. It can be stochastic (probabilities over actions) or deterministic (one action with probability 1). The policy is what the agent learns — and value functions tell the agent which policy is better.

4.12 Value Functions

4.12.1 State-Value Function

Hook: How good is it to be in this state? The state-value function answers that — it tells you the expected return if you start here and follow your policy.

The state-value function $V_{π} (s)$ is the expected return starting from state $s$ and following policy $π$ :

$V_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$

Every symbol named:

$V_{π} (s)$ — the value of state $s$ under policy $π$
$π$ — the policy being followed
$s$ — the state we are evaluating
$E_{π}$ — the expected value over trajectories generated by following $π$
$G_{t}$ — the return (discounted sum of future rewards)
$S_{t} = s$ — the condition that we start in state $s$ at time $t$

This is textbook equation (3.12) in Sutton & Barto. The notation $V_{π} (s)$ uses the subscript $π$ to emphasize that the value depends on the policy. A different policy gives different values for the same state.

Intuition: Think of an office. The value of your office is not the furniture — it is the expected outcome of working there. If your office is next to the boss, you might get promoted faster (higher value). If it is next to the noisy printer, you might get less done (lower value). The value is the expected return from being in that office and following your usual work routine (policy).

Pitfall: Never write $V (s)$ without the $π$ subscript. The value of a state is meaningless without specifying the policy. $V (s)$ is ambiguous; $V_{π} (s)$ is precise. Always ask: "value under which policy?"

Exam note: The state-value function $V_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$ is fundamental. Be ready to define it, name every symbol, and explain why the policy subscript matters.

4.12.2 Action-Value Function

The action-value function $Q_{π} (s, a)$ is the expected return starting from state $s$ , taking action $a$ , and then following policy $π$ :

$Q_{π} (s, a) = E_{π} [G_{t} ∣ S_{t} = s, A_{t} = a]$

Every symbol named:

$Q_{π} (s, a)$ — the value of taking action $a$ in state $s$ under policy $π$
$s$ — the state we are in
$a$ — the action we take first
$π$ — the policy followed after the first action
$E_{π}$ — the expected value over trajectories
$G_{t}$ — the return
$S_{t} = s, A_{t} = a$ — the condition that we start in state $s$ and take action $a$

This is textbook equation (3.13). The "Q" stands for "quality" — the quality of taking a particular action in a particular state.

Intuition: Think of a job. The value of your current job (state) is the expected career outcome. But the action-value asks: "If I take this specific job offer (action) and then follow my usual career strategy (policy), what is the expected outcome?" The action-value evaluates a specific choice, not just the situation.

Pitfall: Do not confuse $V$ and $Q$ . $V_{π} (s)$ asks "how good is it to be here?" $Q_{π} (s, a)$ asks "how good is it to do this specific thing here?" $V$ is a function of one argument (state). $Q$ is a function of two arguments (state and action). The relationship: $V_{π} (s) = \sum_{a} π (a ∣ s) Q_{π} (s, a)$ — the state value is the policy-weighted average of action values.

The state-value function $V_{π} (s)$ evaluates states; the action-value function $Q_{π} (s, a)$ evaluates state-action pairs. Both depend on the policy $π$ . These two functions are the backbone of every RL algorithm.

4.13 Bellman Expectation Equations

4.13.1 Bellman Expectation Equation for State-Value $v_{π} (s)$

Hook: How does the value of where you are right now relate to the values of where you might land next? The Bellman expectation equation breaks down the value of a state into immediate reward plus discounted successor values.

The Bellman expectation equation for $v_{π}$ is a fundamental self-consistency relationship:

$v_{π} (s) ≐ E_{π} [G_{t} ∣ S_{t} = s] = E_{π} [R_{t + 1} + γ G_{t + 1} ∣ S_{t} = s] = a \in A (s) \sum π (a ∣ s) s^{'} \in S \sum r \in R \sum p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})]$

Every symbol named:

$v_{π} (s)$ — expected return from state $s$ under policy $π$
$π (a ∣ s)$ — probability of choosing action $a$ in state $s$ (policy averaging)
$p (s^{'}, r ∣ s, a)$ — probability of environment transitioning to $s^{'}$ with reward $r$ (environment dynamics averaging)
$r$ — immediate scalar reward received on transition
$γ$ — discount factor ( $0 \leq γ \leq 1$ )
$v_{π} (s^{'})$ — value of the successor state $s^{'}$

Derivation Step-by-Step:

Start with definition: $v_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$ .
Substitute recursive return $G_{t} = R_{t + 1} + γ G_{t + 1}$ : $v_{π} (s) = E_{π} [R_{t + 1} + γ G_{t + 1} ∣ S_{t} = s]$ .
Condition on first action $a$ , immediate reward $r$ , and next state $s^{'}$ : average over policy choices $π (a ∣ s)$ and environment dynamics $p (s^{'}, r ∣ s, a)$ .
By the law of total expectation, $E_{π} [G_{t + 1} ∣ S_{t + 1} = s^{'}] = v_{π} (s^{'})$ . Substituting gives equation (3.14) in Sutton & Barto.

Backup Diagram for $v_{π}$ :

A backup diagram visualizes how values flow backward from future state-action outcomes to the current state:

Root node: state $s$ (open circle).
Branches: action choices $a$ selected according to policy $π (a ∣ s)$ (solid dots).
Sub-branches: environment transitions to next states $s^{'}$ (open circles) returning reward $r$ with probability $p (s^{'}, r ∣ s, a)$ .

The value at root $s$ is the expected average over all branches.

4.13.2 Bellman Expectation Equation for Action-Value $q_{π} (s, a)$

Similarly, the Bellman expectation equation for $q_{π}$ is:

$q_{π} (s, a) ≐ E_{π} [G_{t} ∣ S_{t} = s, A_{t} = a] = s^{'} \in S \sum r \in R \sum p (s^{'}, r ∣ s, a) r + γ a^{'} \in A (s^{'}) \sum π (a^{'} ∣ s^{'}) q_{π} (s^{'}, a^{'})$

Here, after taking action $a$ in state $s$ , the environment moves to state $s^{'}$ with reward $r$ . From $s^{'}$ , future action choices $a^{'}$ are selected according to $π (a^{'} ∣ s^{'})$ .

4.13.3 Conversion Between $v_{π} (s)$ and $q_{π} (s, a)$

The state-value function is the policy-weighted average of action-value functions:

$v_{π} (s) = a \in A (s) \sum π (a ∣ s) q_{π} (s, a)$

Conversely, the action-value function is the environment-weighted expectation of immediate reward plus discounted successor state-value:

$q_{π} (s, a) = s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})]$

4.14 Gridworld Example and Bellman Verification

4.14.1 5×5 Gridworld Setup & Exceptional Dynamics

Consider the classic 5×5 Gridworld benchmark (Sutton & Barto Example 3.5). The grid cells represent states $S$ . At each cell, four actions are available: $A = {north, south, east, west}$ .

Equiprobable random policy: $π (a ∣ s) = 0.25$ for all four directions in every state.
Discount factor: $γ = 0.9$ .
Ordinary moves: Stepping within the grid yields reward $r = 0$ .
Off-grid moves: Actions that would push the agent off the grid leave the agent in its current location and yield reward $r = - 1$ .
Special State A (row 1, col 2): Any action yields immediate reward $r = + 10$ and transports the agent to state $A^{'}$ (row 5, col 2).
Special State B (row 1, col 4): Any action yields immediate reward $r = + 5$ and transports the agent to state $B^{'}$ (row 3, col 4).

4.14.2 Worked Verification 1: Ordinary Interior Cell (3, 3)

Worked Example — Bellman Verification for Cell (3, 3):

The displayed value for cell (3, 3) is $0.7$ . Its four neighboring cell values in the grid are:

Up (2, 3): $v_{π} (2, 3) = 2.3$
Right (3, 4): $v_{π} (3, 4) = 0.4$
Down (4, 3): $v_{π} (4, 3) = - 0.4$
Left (3, 2): $v_{π} (3, 2) = 0.7$

Applying the Bellman expectation equation with $π (a ∣ s) = 0.25$ , $r = 0$ , and $γ = 0.9$ :

$v_{π} (3, 3) = \frac{1}{4} [(0 + 0.9 \cdot 2.3) + (0 + 0.9 \cdot 0.4) + (0 + 0.9 \cdot (- 0.4)) + (0 + 0.9 \cdot 0.7)] = \frac{1}{4} [2.07 + 0.36 - 0.36 + 0.63] = \frac{1}{4} (2.70) = 0.675 \approx 0.7$

The Bellman expectation calculation perfectly matches the displayed grid value!

4.14.3 Worked Verification 2: Special State A (1, 2)

Worked Example — Bellman Verification for Special State A:

From state $A$ , every action yields reward $+ 10$ and moves to $A^{'}$ (row 5, col 2), whose displayed value is $v_{π} (A^{'}) = - 1.3$ . The displayed value of $A$ is $8.8$ .

$v_{π} (A) = a \sum \frac{1}{4} [10 + 0.9 \cdot v_{π} (A^{'})] = 10 + 0.9 (- 1.3) = 10 - 1.17 = 8.83 \approx 8.8$

Intuition: Why is $v_{π} (A) < 10$ even though immediate reward is $+ 10$ ? Because state $A$ teleports the agent to $A^{'}$ near the bottom edge where random movement frequently hits the boundary, incurring negative rewards.

4.14.4 Worked Verification 3: Special State B (1, 4)

Worked Example — Bellman Verification for Special State B:

From state $B$ , every action yields reward $+ 5$ and moves to $B^{'}$ (row 3, col 4), whose displayed value is $v_{π} (B^{'}) = 2.3$ . The value of $B$ is:

$v_{π} (B) = 5 + 0.9 (2.3) = 5 + 2.07 = 7.07 \approx 7.1$

4.15 Optimal Policies and Bellman Optimality Equations

4.15.1 Partial Ordering and Definition of Optimal Policy

Value functions define a partial ordering over policies. A policy $π$ is defined to be better than or equal to a policy $π^{'}$ if its expected return is greater than or equal to that of $π^{'}$ in all states:

$π \geq π^{'} ⟺ v_{π} (s) \geq v_{π^{'}} (s) \forall s \in S$

An optimal policy $π_{*}$ is a policy that is better than or equal to all other policies in every state. There is always at least one optimal policy. All optimal policies share the same optimal value functions, denoted $v_{*}$ and $q_{*}$ .

4.15.2 Optimal Value Functions $v_{}$ and $q_{}$

The optimal state-value function $v_{*} (s)$ is the maximum state value achievable under any policy:

$v_{*} (s) ≐ π max v_{π} (s) \forall s \in S$

The optimal action-value function $q_{*} (s, a)$ is the maximum action value achievable under any policy:

$q_{*} (s, a) ≐ π max q_{π} (s, a) \forall s \in S, a \in A (s)$

4.15.3 Bellman Optimality Equation for $v_{*} (s)$

The Bellman optimality equation for $v_{*}$ replaces policy averaging with action maximization:

$v_{*} (s) = a \in A (s) max q_{*} (s, a) = a max E [R_{t + 1} + γ v_{*} (S_{t + 1}) ∣ S_{t} = s, A_{t} = a] = a max s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ v_{*} (s^{'})]$

This equation states that under an optimal policy, the value of a state must equal the expected return from the single best action available in that state.

Backup Diagram for $v_{*}$ :

The backup diagram for $v_{*}$ is identical to $v_{π}$ , except the policy branching arc is replaced by an arc labeled "max" over the actions, signaling that the agent greedily chooses the single best action choice.

4.15.4 Bellman Optimality Equation for $q_{*} (s, a)$

The Bellman optimality equation for $q_{*}$ is:

$q_{*} (s, a) = E [R_{t + 1} + γ a^{'} max q_{*} (S_{t + 1}, a^{'}) ∣ S_{t} = s, A_{t} = a] = s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ a^{'} max q_{*} (s^{'}, a^{'})]$

4.15.5 Greedy Policy Improvement & One-Step Lookahead

If you know $v_{*}$ and the environment dynamics $p (s^{'}, r ∣ s, a)$ , an optimal policy $π_{*}$ can be determined via one-step lookahead:

$π_{*} (a ∣ s) = {10 if a = ar g max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{*} (s^{'})] otherwise$

Key Insight: If you know $q_{*} (s, a)$ , selecting the optimal action does NOT require knowing the environment dynamics $p (s^{'}, r ∣ s, a)$ ! You simply pick $ar g max_{a} q_{*} (s, a)$ . This is why model-free RL algorithms (like Q-learning) estimate $q_{*}$ directly.

4.16 Optimality and Approximation

4.16.1 Tabular Solvability vs Real-World Complexity

For small finite MDPs, the Bellman expectation equations form a set of linear equations that can be solved directly using linear algebra or iterative dynamic programming. The Bellman optimality equations form a non-linear system (due to the $max$ operator) that can be solved via Dynamic Programming (Value Iteration or Policy Iteration).

However, exact solution requires three conditions:

Accurate model dynamics $p (s^{'}, r ∣ s, a)$ must be known.
Sufficient computational power to solve the system of equations.
Memory to store values for all states (Markov property).

4.16.2 Bridge to Approximate Methods and Deep RL

In realistic applications (Atari games, autonomous vehicles, traffic signal grids), the state space is continuous or astronomically large. Exact tabular solutions become impossible (curse of dimensionality). The goal shifts from exact tabular optimality to useful approximation using neural network function approximators $V_{θ} (s) \approx v_{*} (s)$ and $Q_{θ} (s, a) \approx q_{*} (s, a)$ .

4.17 Summary

4.17.1 Framework Recap

In this lecture, we built the complete framework of a Markov Decision Process. The five core elements are:

State ( $S$ ) — what the agent perceives. The Markov property means the future depends only on the current state, not the history.
Action ( $A$ ) — what the agent can do.
Model / Dynamics ( $p, r$ ) — the transition probabilities $p (s^{'} ∣ s, a)$ and expected rewards $r (s, a, s^{'})$ .
Reward ( $R$ ) — the scalar signal. The reward hypothesis says all goals reduce to maximizing expected cumulative reward.
Policy ( $π$ ) — the behavior rule mapping states to actions.

We also derived state transition probabilities $p (s^{'} ∣ s, a)$ , expected rewards $r (s, a)$ , conditional expected rewards $r (s, a, s^{'})$ , discounted return $G_{t} = R_{t + 1} + γ G_{t + 1}$ , Bellman expectation equations, and Bellman optimality equations.

4.17.2 Review of Key Terms

Term	Short Definition
Finite MDP	An MDP with finite state $S$ , action $A$ , and reward $R$ sets.
State ( $S_{t}$ )	The information used at time step $t$ to make decisions and predict future outcomes.
Action ( $A_{t}$ )	The decision selected by the agent at time step $t$ .
Dynamics ( $p (s^{'}, r ∣ s, a)$ )	Probability of next state $s^{'}$ and reward $r$ given current state $s$ and action $a$ .
Transition Probability ( $p (s^{'} ∣ s, a)$ )	Probability of next state $s^{'}$ after action $a$ in state $s$ , marginalizing over rewards.
Expected Reward ( $r (s, a)$ )	Average immediate reward expected after action $a$ in state $s$ .
Policy ( $π (a ∣ s)$ )	Probability of selecting action $a$ in state $s$ .
Return ( $G_{t}$ )	Total accumulated future reward from time step $t$ onward, discounted by $γ$ .
Discount Factor ( $γ$ )	Parameter in $[0, 1]$ controlling the present value of future rewards.
State-Value Function ( $v_{π}$ )	Expected return starting from state $s$ and following policy $π$ .
Action-Value Function ( $q_{π}$ )	Expected return starting from state $s$ , taking action $a$ , then following policy $π$ .
Bellman Equation	A self-consistency recursive equation relating a value to expected immediate reward and successor values.
*Optimal Value Function ( $v_{}, q_{}$ )*	The maximum achievable value function over all possible policies.
Backup Diagram	Graphical tree representation showing how values back up from successor states/actions.

4.17.3 Looking Ahead to Dynamic Programming

Hook for next class: We have defined MDPs and Bellman equations. Next, we will learn how to solve MDPs using Dynamic Programming (Policy Evaluation, Policy Iteration, and Value Iteration) when the model dynamics are fully known!

4.18 Review Questions and Practice Problems

Question 1: Define a finite MDP. Explain why the finiteness of $S$ , $A$ , and $R$ is useful in tabular reinforcement learning.

Solution: A finite MDP is a Markov Decision Process where the state space $S$ , action space $A$ , and reward set $R$ all contain a finite number of elements. Finiteness ensures that the model dynamics $p (s^{'}, r ∣ s, a)$ , policies $π (a ∣ s)$ , and value functions $v_{π} (s)$ / $q_{π} (s, a)$ can be represented explicitly as lookup tables, and all expectations reduce to finite exact summations.

Question 2: Explain the agent-environment interface using the trajectory $S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, \dots$ . Why is the reward following $A_{t}$ written as $R_{t + 1}$ ?

Solution: At time step $t$ , the agent observes state $S_{t}$ and chooses action $A_{t}$ . The environment responds at discrete time step $t + 1$ by transitioning to state $S_{t + 1}$ and generating reward $R_{t + 1}$ . The subscript $t + 1$ emphasizes that reward is received after the action is executed and arrives together with the next state $S_{t + 1}$ .

Question 3: State the Markov property in the context of an MDP. What must the state representation contain for this assumption to be reasonable?

Solution: The Markov property states that $Pr {S_{t + 1} = s^{'}, R_{t + 1} = r ∣ S_{t}, A_{t}, S_{t - 1}, A_{t - 1}, \dots} = Pr {S_{t + 1} = s^{'}, R_{t + 1} = r ∣ S_{t}, A_{t}}$ . To be Markov, the state representation must summarize all historical information required to predict future states and rewards without needing past history.

Question 4: Given the dynamics table below for state $s$ and action $a$ , compute $p (s_{1} ∣ s, a)$ , $p (s_{2} ∣ s, a)$ , and $r (s, a)$ .

$s^{'}$	$r$	$p (s^{'}, r ∣ s, a)$
$s_{1}$	2	0.30
$s_{1}$	0	0.20
$s_{2}$	4	0.10
$s_{2}$	1	0.40

Solution:

$p (s_{1} ∣ s, a) = p (s_{1}, 2 ∣ s, a) + p (s_{1}, 0 ∣ s, a) = 0.30 + 0.20 = 0.50$

$p (s_{2} ∣ s, a) = p (s_{2}, 4 ∣ s, a) + p (s_{2}, 1 ∣ s, a) = 0.10 + 0.40 = 0.50$

$r (s, a) = r \sum r s^{'} \sum p (s^{'}, r ∣ s, a) = 2 (0.30) + 0 (0.20) + 4 (0.10) + 1 (0.40) = 0.60 + 0.00 + 0.40 + 0.40 = 1.40$

Question 5: Compute the discounted return for the reward sequence 2, 0, 3, 5 with $γ = 0.8$ . Then compute it again with $γ = 0$ and interpret the difference.

Solution:

For $γ = 0.8$ with $R_{1} = 2, R_{2} = 0, R_{3} = 3, R_{4} = 5$ :

$G_{0} = R_{1} + γ R_{2} + γ^{2} R_{3} + γ^{3} R_{4} = 2 + 0.8 (0) + 0. 8^{2} (3) + 0. 8^{3} (5) = 2 + 0 + 0.64 (3) + 0.512 (5) = 2 + 1.92 + 2.56 = 6.48$

For $γ = 0$ : $G_{0} = R_{1} = 2$ . When $γ = 0$ , the agent considers only the immediate reward and ignores all future consequences.

Question 6: A continuing traffic-control task gives reward equal to negative total vehicle delay every minute. Explain why discounting is useful, and mention one drawback of choosing $γ$ too small.

Solution: In a continuing task, the horizon is infinite. Without discounting ( $γ = 1$ ), the cumulative sum of negative rewards would diverge to $- \infty$ , making strategy comparisons impossible. Discounting with $γ < 1$ guarantees a finite return. However, choosing $γ$ too small (e.g. $γ \approx 0$ ) makes the agent short-sighted (myopic) — it may clear a small queue immediately while causing catastrophic traffic gridlock five minutes later.

Question 7: Consider state $s$ with two actions. Action $a_{1}$ gives reward 2 and moves to $s_{1}$ ( $p = 1$ ). Action $a_{2}$ gives reward 0 and moves to $s_{2}$ ( $p = 1$ ). If $γ = 0.9$ , $v (s_{1}) = 5$ , and $v (s_{2}) = 8$ , which action is greedy with respect to these values? Show the one-step lookahead calculation.

Solution:

Calculate one-step lookahead expected return $q (s, a) = r + γ v (s^{'})$ :

$q (s, a_{1}) = 2 + 0.9 (5) = 2 + 4.5 = 6.5$

$q (s, a_{2}) = 0 + 0.9 (8) = 0 + 7.2 = 7.2$

Since $7.2 > 6.5$ , action $a_{2}$ is greedy with respect to these value estimates.

Question 8: In the recycling robot example, identify the states, actions, rewards, and one stochastic transition. Why does the transition table define a finite MDP?

Solution: States: $S = {High, Low}$ . Actions: $A = {search, wait, recharge}$ . Rewards: $R_{search}, R_{wait}, 0, - 3$ . Stochastic transition: Searching from Low battery remains in Low with probability $β$ (reward $R_{search}$ ) and drops to High (rescuing) with probability $1 - β$ (reward $- 3$ ). It is a finite MDP because state, action, and reward sets are all finite.

Question 9: For the recycling robot, suppose from state Low, action search gives reward $R_{search} = 4$ and remains in Low with probability $β = 0.6$ , but moves to High with probability $1 - β = 0.4$ with reward $- 3$ . If $v (Low) = 5$ , $v (High) = 8$ , and $γ = 0.9$ , compute the one-step expected return for search from Low.

Solution:

$q (Low, search) = s^{'}, r \sum p (s^{'}, r ∣ Low, search) [r + γ v (s^{'})] = β [R_{search} + γ v (Low)] + (1 - β) [- 3 + γ v (High)] = 0.6 [4 + 0.9 (5)] + 0.4 [- 3 + 0.9 (8)] = 0.6 [4 + 4.5] + 0.4 [- 3 + 7.2] = 0.6 (8.5) + 0.4 (4.2) = 5.10 + 1.68 = 6.78$

Question 10: Formulate an Atari game as an MDP. Specify state representation, actions, rewards, terminal condition, and why function approximation becomes necessary.

Solution: State: stacked recent screen frames (e.g. 4 consecutive frames of 84×84 pixels) to capture velocity. Actions: discrete joystick buttons (up, down, left, right, fire). Reward: change in game score. Terminal condition: losing all lives or completing level. Function approximation is necessary because state space size ( $25 6^{84 \times 84 \times 4}$ ) makes tabular storage impossible.

Question 11: Formulate a traffic signal control problem as a finite MDP after discretization. Clearly specify states, actions, rewards, and transition behavior.

Solution: State: discretized vehicle queue counts and waiting time brackets per lane. Actions: select next signal phase or extend current green light phase. Reward: negative sum of total vehicle delay across lanes. Transitions: governed by stochastic vehicle arrival and departure rates.

Question 12: Write the Bellman equation for $v_{π}$ and explain in words why it averages over both the policy and the environment dynamics.

Solution: $v_{π} (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})]$ . It averages over the policy $π (a ∣ s)$ because the agent stochastically picks actions, and averages over environment dynamics $p (s^{'}, r ∣ s, a)$ because the environment stochastically responds with a next state and reward.

Question 13: Derive the Bellman optimality equation for $v_{*}$ from the idea that the optimal value of a state is obtained by the best first action followed by optimal behavior.

Solution: The optimal value $v_{*} (s)$ is the maximum expected return under any action choice. Taking action $a$ yields expected immediate reward plus discounted optimal return $\sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{*} (s^{'})]$ . Maximizing over all available actions $a \in A (s)$ gives $v_{*} (s) = max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{*} (s^{'})]$ .

Question 14: In the gridworld example, verify the Bellman relation for special state B using reward $+ 5$ , $γ = 0.9$ , and the displayed value of B' ( $2.3$ ).

Solution: From B, all actions give reward $+ 5$ and transport to B' with value $v_{π} (B^{'}) = 2.3$ . Bellman expectation: $v_{π} (B) = 5 + 0.9 (2.3) = 5 + 2.07 = 7.07 \approx 7.1$ . The displayed value matches the expectation.

Question 15: Explain the difference between exact optimality and useful approximation. Why is approximation unavoidable in large MDPs such as video games or traffic networks?

Solution: Exact optimality computes the exact value function $v_{*} (s)$ or policy $π_{*}$ for every state. Useful approximation estimates $v_{*} (s)$ using parameterized function approximators like deep neural networks $V_{θ} (s)$ . Approximation is unavoidable in large MDPs because state spaces are far too large to store or compute in tabular memory.

Exam Guidance Summary

1. Exploration vs Exploitation: UCB (Upper Confidence Bound) and epsilon-greedy are the two standard strategies. UCB balances exploration by adding a confidence bonus to less-visited actions. Epsilon-greedy takes a random action with probability $ϵ$ .

2. Policy subscript matters: Always write $π$ as a subscript on value functions: $V_{π} (s)$ and $Q_{π} (s, a)$ . Never write $V (s)$ or $Q (s, a)$ without the policy.

3. Model dynamics, Bellman equations, and value functions: Master the master dynamics $p (s^{'}, r ∣ s, a)$ , transition probabilities $p (s^{'} ∣ s, a)$ , expected rewards $r (s, a)$ and $r (s, a, s^{'})$ , discounted return recursion $G_{t} = R_{t + 1} + γ G_{t + 1}$ , and Bellman expectation/optimality equations for $v_{π}, q_{π}, v_{*}, q_{*}$ .

4. Tabular Gridworld Verification: Practice numerical Bellman expectation verifications for ordinary cells ( $v_{π} (3, 3) = 0.675 \approx 0.7$ ) and jump states ( $v_{π} (A) = 8.83 \approx 8.8$ , $v_{π} (B) = 7.07 \approx 7.1$ ).

5. Episodic vs Continuous tasks and terminal convention: Episodic tasks end in a terminal state where $G_{T} = 0$ and $γ = 1$ can be used. Continuous tasks run indefinitely and require $γ < 1$ .

Key Industry Applications

The MDP framework is not just theory. It underlies a wide range of real-world systems:

Autonomous driving: States are sensor readings (camera, lidar); actions are steering, acceleration, braking; rewards reflect safety, progress, and comfort.
Portfolio management: States are market conditions; actions are buy/sell/hold; rewards are profit (or risk-adjusted return).
RoboCup soccer: Robots learn to play soccer by treating each game as an MDP with states (positions, ball location), actions (move, kick), and rewards (goals scored).
Recommendation systems: States are user context; actions are which item to show next; rewards are engagement (clicks, watch time).
Video games: Atari-style games (the example from 4.8.1) where states are screen frames, actions are joystick moves, and rewards are score.
Traffic signal control: The example from 4.8.2 — states are queue lengths, actions are signal phases, rewards are negative delay.
Recycling robots: The textbook example from 4.8.3 — states are battery levels, actions are search/wait/recharge, rewards are cans collected.
Nuclear reactor control: A continuous task — states are reactor readings, actions are control adjustments, rewards reflect stability and safety. Runs indefinitely.
Cart-pole balancing: The classic control benchmark from 4.10.2 — states are pole angle and cart position, actions are left/right force, rewards reflect balance.

DRL Lecture 4 Notes · Markov Decision Processes

Deep Reinforcement Learning· postgraduate· 2026-07-18

Sections Breakdown

1Recap and Transition to Full Reinforcement Learning

From multi-armed bandits to full RL with states; the agent-environment interaction loop.

2Course Roadmap

The next three classes: MDP, solving MDPs, and dynamic programming.

3The Markov Property

Definition, intuition, and testing whether a state representation is Markov.

4Grid World Example

A noisy grid world with pits, terminal states, and step penalties.

5The Elements of MDP

State space, action space, reward function, and model dynamics.

6Deriving Quantities from Model Dynamics

State transition probabilities, expected immediate reward, conditional expected reward, and Start-Stop numerical example.

7Finite vs Infinite MDP

Why we assume finite MDPs and where the assumption breaks down.

8Example MDP Formulations

Video games, traffic signals, and the recycling robot textbook example.

9Reward Hypothesis and Return

The reward hypothesis, simple and discounted return, and the recursive form.

10Episodic vs Continuous Tasks

Classifying tasks and the cart-pole balancing example.

11Policy

Definition, stochastic versus deterministic policies, and the value-policy link.

12Value Functions

State-value and action-value functions under a policy.

13Bellman Expectation Equations

Derivation and structure of Bellman expectation equations for v_pi and q_pi, with backup diagrams.

14Gridworld Example and Bellman Verification

5x5 gridworld setup, special states A and B, and exact numerical Bellman expectation calculations.

15Optimal Policies and Bellman Optimality Equations

Partial ordering of policies, optimal value functions v* and q*, Bellman optimality equations, and one-step lookahead.

16Optimality vs Approximation

Exact tabular solution vs function approximation in high-dimensional or continuous MDPs.

17Summary

Recap of the five MDP elements, table of key terms, and a look ahead to solving MDPs.

18Review Questions and Practice Problems

Complete 15 worked review questions covering all aspects of finite MDPs.

Postgraduate students in Deep Reinforcement Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review — but if something doesn't make sense, go back to the full explanation in the main content.

Markov Property

Must-know: A state is Markov if it is a sufficient summary of the past: knowing the full history adds nothing about the next state beyond the current state. The property is about the state representation, not the problem.

$Pr {S_{t + 1} ∣ S_{t}, A_{t}} = Pr {S_{t + 1} ∣ S_{0}, A_{0}, S_{1}, A_{1}, \dots, S_{t}, A_{t}}$

⚠️ Top pitfall: Thinking the Markov property is a property of the problem. If your state omits needed information (e.g. battery level), the property fails — you must enrich the state.

Self-check: If two agents are in the same board position but reached it by different move sequences, can a Markov state still make the right decision? Why?

Connects to: Elements of MDP, Model Dynamics, State Space.

MDP Elements

Must-know: An MDP is specified by states, actions, model dynamics (transition probabilities and rewards), and the reward function. The policy is the fifth element you want to learn.

$p (s^{'}, r ∣ s, a) = Pr {S_{t + 1} = s^{'}, R_{t + 1} = r ∣ S_{t} = s, A_{t} = a}$

⚠️ Top pitfall: Forgetting that the reward function signals what the goal is, not how to achieve it. Rewarding sub-goals can train a misbehaving agent.

Self-check: Name the four elements you must pin down to model a problem as an MDP, and the fifth you learn.

Connects to: Model Dynamics, Reward Hypothesis, Finite vs Infinite MDP.

Model Dynamics & Derivations

Must-know: The model dynamics $p (s^{'}, r ∣ s, a)$ is the master table of the environment. From it you derive state transition probabilities $p (s^{'} ∣ s, a)$ , expected immediate rewards $r (s, a)$ , and conditional rewards $r (s, a, s^{'})$ . Probabilities from any $(s, a)$ must sum to 1.

$p (s^{'} ∣ s, a) = r \sum p (s^{'}, r ∣ s, a), r (s, a) = r \sum r s^{'} \sum p (s^{'}, r ∣ s, a)$

⚠️ Top pitfall: Confusing the joint $p (s^{'}, r ∣ s, a)$ with the marginal $p (s^{'} ∣ s, a)$ . Sum over rewards to get the transition probability.

Self-check: Given $p (W, 4 ∣ R, start) = 0.6$ and $p (W, 2 ∣ R, start) = 0.2$ , what is $p (W ∣ R, start)$ ?

Connects to: State Transition Probabilities, Expected Immediate Reward, Conditional Rewards.

Return (Discounted) & Recursion

Must-know: The return $G_{t}$ is the discounted sum of future rewards starting from time $t + 1$ . The recursive relation $G_{t} = R_{t + 1} + γ G_{t + 1}$ expresses current return in terms of next step's return.

$G_{t} = k = 0 \sum \infty γ^{k} R_{t + k + 1} = R_{t + 1} + γ G_{t + 1}$

⚠️ Top pitfall: Forgetting that $G_{t}$ starts at $R_{t + 1}$ , not $R_{t}$ , or using $γ = 1$ for an infinite continuous task.

Self-check: With $γ = 0.5$ and rewards $- 1, 2, 6, 3, 2$ over $T = 5$ , compute $G_{0}$ by working backwards.

Connects to: Episodic vs Continuous, Policy, Value Functions.

Bellman Expectation Equations

Must-know: The Bellman expectation equation relates the value of a state (or state-action pair) to the expected reward and discounted values of successor states under a given policy $π$ .

$v_{π} (s) = a \sum π (a ∣ s) s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})]$

⚠️ Top pitfall: Forgetting that $v_{π}$ averages over BOTH the policy (action choice) and environment dynamics (next state and reward).

Self-check: Write the relationship between $V_{π} (s)$ and $Q_{π} (s, a)$ .

Connects to: State-Value Function, Action-Value Function, Backup Diagrams.

Gridworld Bellman Verification

Must-know: In tabular gridworlds, the Bellman expectation equation allows exact numeric verification of state values under equiprobable random policies by averaging neighboring cell values.

$v_{π} (1, 2) = 10 + 0.9 \times (- 1.3) = 8.83 \approx 8.8 (Special State A)$

⚠️ Top pitfall: Forgetting off-grid penalties or failing to account for exceptional jump state dynamics.

Self-check: Why does special state A have a high value ( $8.8$ ) even though its destination A' has a negative value ( $- 1.3$ )?

Connects to: Bellman Expectation Equations, State-Value Function.

Bellman Optimality Equations

Must-know: The Bellman optimality equation replaces policy averaging with maximization over actions. The optimal value $v_{*} (s)$ is the maximum expected return achievable by any policy from state $s$ .

$v_{*} (s) = a max s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ v_{*} (s^{'})]$

⚠️ Top pitfall: Confusing Bellman expectation equations (linear, policy-dependent) with Bellman optimality equations (non-linear system due to the max operator).

Self-check: If $q_{*} (s, a)$ is known for all actions, how do you pick the optimal action in state $s$ ?

Connects to: Optimal Policy, One-Step Lookahead, Action-Value Function.

Exact Optimality vs Approximation

Must-know: Bellman optimality equations can be solved exactly for small tabular MDPs, but large state spaces (e.g., Atari, traffic networks) require value function approximation and Deep RL.

$∣ S ∣ \to \infty ⟹ V_{θ} (s) \approx v_{*} (s)$

⚠️ Top pitfall: Thinking exact DP solutions can be stored for continuous or combinatorial state spaces without neural network approximations.

Self-check: Why is exact tabular calculation impossible for traffic signal control with continuous waiting times?

Connects to: MDP Formulations, Deep Reinforcement Learning.

Previous LectureLecture 03 · Multi-Armed Bandit: Advanced Topics

Next LectureLecture 05 · Markov Decision Processes and Dynamic Programming

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

Markov Decision Processes

4.1 Recap and Transition to Full Reinforcement Learning

4.1.1 What We Have Covered So Far

4.1.2 Entering Full Reinforcement Learning: States

4.2 Course Roadmap

4.2.1 Next Three Classes

4.2.2 Agent-Environment Interface Refresher

4.3 The Markov Property

4.3.1 Definition and Intuition

4.3.2 Testing the Markov Property: Battery Level

4.4 Grid World Example

4.4.1 Environment Setup

4.4.2 Actions

4.4.3 Rewards

4.5 The Elements of MDP

4.5.1 Overview

4.5.2 Element 1: State Space

4.5.3 Element 2: Action Space

4.5.4 Element 3: Reward Function

4.5.5 Element 4: Model Dynamics (Transition Probabilities)

4.5.5.1 Formal Definition

4.5.5.2 Interpreting the Model Dynamics Table

4.5.5.3 Visualization of Model Dynamics

4.6 Deriving Quantities from Model Dynamics

4.6.1 State Transition Probabilities

4.6.2 Expected Immediate Reward

4.6.3 Expected Reward for a Specific Transition

4.6.4 Complete Numerical Example: Start–Stop MDP & Deterministic Special Case

4.7 Finite vs Infinite MDP

4.7.1 The Finite MDP Assumption

4.8 Example MDP Formulations

4.8.1 Video Game (Atari-style)

4.8.2 Traffic Signal Control

4.8.3 Recycling Robot (Textbook Example 3.3)

4.9 Reward Hypothesis and Return

4.9.1 The Reward Hypothesis

4.9.2 Return: Simple Sum

4.9.3 Return: Discounted Sum

4.9.4 Recursive Form of Return

4.10 Episodic vs Continuous Tasks

4.10.1 Classification

4.10.2 Cart-Pole Balancing Example

4.11 Policy

4.11.1 Definition

4.11.2 Types of Policies

4.11.3 Policy and Value: Visual Intuition

4.12 Value Functions

4.12.1 State-Value Function

4.12.2 Action-Value Function

4.13 Bellman Expectation Equations

4.13.1 Bellman Expectation Equation for State-Value vπ​(s)

4.13.2 Bellman Expectation Equation for Action-Value qπ​(s,a)

4.13.3 Conversion Between vπ​(s) and qπ​(s,a)

4.14 Gridworld Example and Bellman Verification

4.14.1 5×5 Gridworld Setup & Exceptional Dynamics

4.14.2 Worked Verification 1: Ordinary Interior Cell (3, 3)

4.14.3 Worked Verification 2: Special State A (1, 2)

4.14.4 Worked Verification 3: Special State B (1, 4)

4.15 Optimal Policies and Bellman Optimality Equations

4.15.1 Partial Ordering and Definition of Optimal Policy

4.15.2 Optimal Value Functions v∗​ and q∗​

4.15.3 Bellman Optimality Equation for v∗​(s)

4.15.4 Bellman Optimality Equation for q∗​(s,a)

4.15.5 Greedy Policy Improvement & One-Step Lookahead

4.16 Optimality and Approximation

4.16.1 Tabular Solvability vs Real-World Complexity

4.16.2 Bridge to Approximate Methods and Deep RL

4.17 Summary

4.17.1 Framework Recap

4.17.2 Review of Key Terms

4.17.3 Looking Ahead to Dynamic Programming

4.18 Review Questions and Practice Problems

Exam Guidance Summary

Key Industry Applications

DRL Lecture 4 Notes · Markov Decision Processes

Sections Breakdown

Exam Revision Notes

Markov Property

4.13.1 Bellman Expectation Equation for State-Value $v_{π} (s)$

4.13.2 Bellman Expectation Equation for Action-Value $q_{π} (s, a)$

4.13.3 Conversion Between $v_{π} (s)$ and $q_{π} (s, a)$

4.15.2 Optimal Value Functions $v_{}$ and $q_{}$

4.15.3 Bellman Optimality Equation for $v_{*} (s)$

4.15.4 Bellman Optimality Equation for $q_{*} (s, a)$