First time studying this topic?

Launch the interactive walkthrough to discover each component, including the 3D Q-Sphere Lab & Python in Colab.

Topic 4.4

State Representation & The Markov Property

Understand the mathematical definition of State and the foundational Markov Property: the future depends only on the present.

Learning Objectives

✓Define the Markov Property: P(s_{t+1}|s_t, a_t) = P(s_{t+1}|s_t, a_t, s_{t-1}, ...)
✓Understand why historical path independence enables tractable dynamic programming
✓Address partial state representation using frame stacking and recurrence

📖Let's Begin with a Story

Suppose you are playing a game of Pong. A camera takes a single still photograph of the ball in the middle of the screen. Is that single photo a complete Markov State? NO! You know where the ball is, but you have no idea which direction it is moving or how fast! If you don't know velocity, you cannot decide whether to move your paddle up or down. To make it a true Markov state, DeepMind stacked 4 consecutive image frames together. Now, the 4 frames contain both position and velocity. The future is once again completely predictable from the present observation alone.

Why Should You Learn State Representation & The Markov Property?

🎯 Practical & Engineering Stakes

The cornerstone of RL mathematics

Every equation in dynamic programming, Bellman backups, and Q-learning assumes the Markov Property. If your state representation violates this property, standard algorithms will fail.

What Is It?

Simple Explanation

The Markov Property means: "The present state contains all the information you need to predict the future. The past doesn't matter." Think of a game of chess: you only need to look at where the pieces are right now to pick your next move. You don't need to know whether the knight moved 5 turns ago or 10 turns ago.

Technical Explanation

A state

S_t

is Markov if and only if:

\mathbb{P}(S_{t+1} = s', R_{t+1} = r \mid S_t = s_t, A_t = a_t, S_{t-1} = s_{t-1}, \dots, S_0 = s_0) = \mathbb{P}(S_{t+1} = s', R_{t+1} = r \mid S_t = s_t, A_t = a_t)

The state transitions are conditionally independent of the historical trajectory given the current state.

📚 Key Terms

Markov Property

Simple: The future depends only on the present, not on the past path taken to get here.

Technical: Conditional independence of future states from past states given the present state.

Frame Stacking

Simple: Grouping the last 4 frames together so the AI can see motion and speed.

Technical: Concatenating

k

sequential sensory observations along the channel axis to recover velocity vectors in non-Markovian observations.

📐 Mathematical Foundation

LaTeX KaTeX

P(S_{t+1} = s_{t+1} \mid S_t = s_t, A_t = a_t)

What does it mean?

The Markov Transition Probability: the next state depends exclusively on current state S_t and action A_t, discarding all earlier history S_{t-1}, S_{t-2}...

Understanding the Symbols

Symbol / Term	Meaning	Beginner Interpretation
$S_t$	Current state	Everything needed to decide next move
$A_t$	Current action	The agent’s chosen move
$S_{t+1}$	Next state	Resulting state

📊 Numerical Example

In Chess, knowing the board layout right now is sufficient to predict all valid future moves.

P(\text{Next} \mid \text{Current Board}) \text{ requires zero knowledge of prior moves}

Result: Board configuration is a valid Markov state

⚙️ How Does It Work?

State Formulation

Identify physical variables (positions, velocities, angles, accelerations).

Markov Validation

Confirm that knowing current state s_t is sufficient to compute transition probabilities.

Augmentation if Needed

If velocity is missing, append historical frames or use recurrent LSTM/GRU memory.

🌍 Where Is It Used?

Atari Deep Q-Networks (DQN)

Problem: A single 2D Atari game screen lacks ball velocity.

Solution: Stacking 4 consecutive grayscale frames (84x84x4) transforms the observation into a clean Markov state.

🎯 Try It Yourself

Which of the following contains sufficient information to be considered a true Markov state for a flying drone?

Interactive activity component

🐍 Python Hands-On: Frame Stacking for Velocity Recovery in Python

Demonstrate how stacking two scalar positions allows computing velocity.

Open Colab

1Install Required Packages

For Google Colab or Jupyter notebooks, run this shell command to install the required dependencies:

Terminal / Notebook Install Commandbash

!pip install numpy

Packages:

numpy

2Import Libraries

Import Statementspython

1 import numpy as np

import numpy as np → NumPy arrays

3Demonstration Code & Logic

Python Execution Codepython

1 # Consecutive positions of a ball in meters at t=0, t=1, t=2
2 positions = [10.0, 15.0, 22.0]
3 dt = 1.0 # 1 second per step
4  
5 # A single position is incomplete (we do not know speed)
6 single_state_t1 = np.array([positions[1]])
7  
8 # Stack 2 frames: [position_prev, position_current]
9 stacked_state_t1 = np.array([positions[0], positions[1]]) # [10.0, 15.0]
10 velocity_t1 = (stacked_state_t1[1] - stacked_state_t1[0]) / dt
11  
12 print("Single Position State:", single_state_t1)
13 print("Stacked 2-Frame State:", stacked_state_t1)
14 print(f"Recovered Velocity from Stacking: {velocity_t1:.1f} m/s")

Step-by-Step Code Breakdown:

# Consecutive positions of a ball in meters at t=0, t=1, t=2

Positions

positions = [10.0, 15.0, 22.0]

Distance traveled

dt = 1.0 # 1 second per step

Time delta

# A single position is incomplete (we do not know speed)

Incomplete state

single_state_t1 = np.array([positions[1]])

Just [15.0]

# Stack 2 frames: [position_prev, position_current]

Stacked state

stacked_state_t1 = np.array([positions[0], positions[1]]) # [10.0, 15.0]

Frame stack

velocity_t1 = (stacked_state_t1[1] - stacked_state_t1[0]) / dt

Computed velocity

print("Single Position State:", single_state_t1)

Print single

print("Stacked 2-Frame State:", stacked_state_t1)

Print stacked

print(f"Recovered Velocity from Stacking: {velocity_t1:.1f} m/s")

Show velocity

📋 Complete Script (All-in-One)

Click "Copy for Colab", open Google Colab, paste into a single cell, and run.

Google Colab Notebook Scriptpython

1 # =========================================================
2 # Frame Stacking for Velocity Recovery in Python
3 # Prepared for Google Colab (Run with Shift + Enter)
4 # =========================================================
5  
6 # Step 1: Install required packages
7 !pip install numpy
8  
9 # Step 2: Import libraries
10 import numpy as np
11  
12 # Step 3: Run Demonstration
13 # Consecutive positions of a ball in meters at t=0, t=1, t=2
14 positions = [10.0, 15.0, 22.0]
15 dt = 1.0 # 1 second per step
16  
17 # A single position is incomplete (we do not know speed)
18 single_state_t1 = np.array([positions[1]])
19  
20 # Stack 2 frames: [position_prev, position_current]
21 stacked_state_t1 = np.array([positions[0], positions[1]]) # [10.0, 15.0]
22 velocity_t1 = (stacked_state_t1[1] - stacked_state_t1[0]) / dt
23  
24 print("Single Position State:", single_state_t1)
25 print("Stacked 2-Frame State:", stacked_state_t1)
26 print(f"Recovered Velocity from Stacking: {velocity_t1:.1f} m/s")

⚡ How to Run in Google Colab (3 Quick Steps)

Click "Copy for Google Colab" above.
Click Open New Google Colab Notebook (opens in a new tab).
Click on the first empty code cell, press Ctrl + V (or Cmd + V) to paste, then press Shift + Enter to execute!

Launch Blank Colab Notebook

🔄 Algorithmic Execution Flow

Single State

Shows position 15.0 with zero velocity information.

→

Frame Stacking

Shows [10.0, 15.0], allowing the agent to immediately compute +5.0 m/s velocity.

📥 Input / Initial State

Sequence of scalar positions [10, 15, 22]

📤 Expected Output

Single Position State: [15.]
Stacked 2-Frame State: [10. 15.]
Recovered Velocity from Stacking: 5.0 m/s

💡 What Does This Demonstration Show?

Frame stacking satisfies the Markov property by encoding temporal derivatives directly into the sensory observation tensor.

Course Learning Resource • Slide DeckLesson 612 Slides

Lesson 6: Reinforcement Learning Foundations

Q-learning, Q-table updates, DQN architectures, and exploration-exploitation trade-offs.

Author: Dr. Syed Muzamil Basha• FDP Approved Curriculum

Open in New Tab

📝 Learning Check

Test your understanding with these questions. Remember, this is for learning, not examination!

Question 1: What is the core statement of the Markov Property?

Question 2: What is a state in RL?

Question 3: What is the difference between state and observation?

Question 4: What is a terminal state?

Question 5: How is state space dimensionality a challenge in RL?

Previous: The Environment: Dynamics, Observability & Gym Next: Action Spaces: Discrete vs Continuous

1	# =========================================================
2	# Frame Stacking for Velocity Recovery in Python
3	# Prepared for Google Colab (Run with Shift + Enter)
4	# =========================================================
5
6	# Step 1: Install required packages
7	!pip install numpy
8
9	# Step 2: Import libraries
10	import numpy as np
11
12	# Step 3: Run Demonstration
13	# Consecutive positions of a ball in meters at t=0, t=1, t=2
14	positions = [10.0, 15.0, 22.0]
15	dt = 1.0 # 1 second per step
16
17	# A single position is incomplete (we do not know speed)
18	single_state_t1 = np.array([positions[1]])
19
20	# Stack 2 frames: [position_prev, position_current]
21	stacked_state_t1 = np.array([positions[0], positions[1]]) # [10.0, 15.0]
22	velocity_t1 = (stacked_state_t1[1] - stacked_state_t1[0]) / dt
23
24	print("Single Position State:", single_state_t1)
25	print("Stacked 2-Frame State:", stacked_state_t1)
26	print(f"Recovered Velocity from Stacking: {velocity_t1:.1f} m/s")