Master the foundations of Reinforcement Learning: Markov Decision Processes, Q-Learning, value functions, and policy optimization. Learn how agents learn to make decisions through trial and error.
Reinforcement Learning (RL) is how machines learn to make sequential decisions by interacting with an environment. Unlike supervised learning where you provide labeled examples, RL agents learn through trial and error, receiving rewards or penalties for their actions.
This is how DeepMind's AlphaGo defeated world champions, how OpenAI's Dota 2 bots mastered complex strategy games, and how robots learn to walk. RL is the closest we've come to replicating how humans and animals learn through experience.
In October 2025, RL continues to power breakthrough applications: autonomous vehicles navigating traffic, robotic manipulation in factories, personalized recommendation systems, and AI assistants that adapt to user preferences. This lesson provides comprehensive coverage of RL fundamentals—the foundation for understanding modern RL systems.
Reinforcement Learning (RL) is learning what to do—how to map situations to actions—so as to maximize a cumulative reward signal.
1┌──────────────────────────────────────────────────────┐
2│ AGENT-ENVIRONMENT INTERACTION │
3├──────────────────────────────────────────────────────┤
4│ │
5│ State (Sₜ) │
6│ │ │
7│ ▼ │
8│ ┌────────┐ │
9│ │ AGENT │ │
10│ └────────┘ │
11│ │ │
12│ │ Action (Aₜ) │
13│ ▼ │
14│ ┌──────────────┐ │
15│ │ ENVIRONMENT │ │
16│ └──────────────┘ │
17│ │ │
18│ ├─► Reward (Rₜ₊₁) │
19│ └─► Next State (Sₜ₊₁) │
20│ │
21└──────────────────────────────────────────────────────┘1. Agent: The learner/decision maker
2. Environment: Everything outside the agent
3. State (S): Complete description of the environment
4. Action (A): What the agent can do
5. Reward (R): Immediate feedback signal
6. Policy (π): Agent's behavior strategy
1# SUPERVISED LEARNING
2# Given: (input, label) pairs
3X_train = [[1, 2], [3, 4], ...] # Features
4y_train = [0, 1, ...] # Labels
5model.fit(X_train, y_train) # Learn mapping
6
7# UNSUPERVISED LEARNING
8# Given: input data only (no labels)
9X = [[1, 2], [3, 4], ...] # Data
10clusters = kmeans.fit_predict(X) # Find patterns
11
12# REINFORCEMENT LEARNING
13# Given: environment interactions only
14for episode in range(num_episodes):
15 state = env.reset()
16 while not done:
17 action = agent.select_action(state) # Choose action
18 next_state, reward, done = env.step(action) # Get feedback
19 agent.learn(state, action, reward, next_state) # Update policy
20 state = next_stateKey Differences:
Challenge: Which past actions led to current reward?
1t=0: Move Right (reward=0)
2t=1: Move Up (reward=0)
3t=2: Move Right (reward=0)
4t=3: Move Down (reward=0)
5t=4: Move Right (reward=+10) ← Goal reached!
6
7Question: Which actions were good?
8Answer: All of them! (they led to the goal)RL algorithms must solve this temporal credit assignment problem—propagating reward information backward to earlier actions.
Markov Decision Processes (MDPs) provide the mathematical framework for modeling sequential decision-making in RL.
An MDP is a tuple (S, A, P, R, γ) where:
S: Set of states (finite or infinite)
A: Set of actions (finite or infinite)
P: Transition probability function
R: Reward function
γ: Discount factor (0 ≤ γ ≤ 1)
Key Assumption: The future depends only on the present (not the past)
1P(Sₜ₊₁ | Sₜ, Sₜ₋₁, ..., S₀) = P(Sₜ₊₁ | Sₜ)The current state Sₜ contains all relevant information for predicting the future. Past states provide no additional information.
Example - Grid World MDP:
1Grid:
2┌───┬───┬───┬───┐
3│ S │ │ │ G │ S = Start, G = Goal (+1 reward)
4├───┼───┼───┼───┤
5│ │ X │ │ │ X = Wall (impassable)
6├───┼───┼───┼───┤
7│ │ │ │ H │ H = Hole (-1 reward)
8└───┴───┴───┴───┘
9
10States (S): All grid positions
11Actions (A): {North, South, East, West}
12Transitions (P): Deterministic (always move in chosen direction, unless wall)
13Rewards (R): +1 at Goal, -1 at Hole, -0.01 per step (encourage efficiency)
14Discount (γ): 0.99 (value long-term rewards)Return (Gₜ): Total discounted reward from time t onward
1Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + ...
2 = Σ γᵏRₜ₊ₖ₊₁ (k from 0 to ∞)Why Discount?:
State Value Function V^π(s):
Expected return starting from state s and following policy π
1V^π(s) = E_π[Gₜ | Sₜ = s]
2 = E_π[Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + ... | Sₜ = s]Action Value Function Q^π(s, a):
Expected return starting from state s, taking action a, then following policy π
1Q^π(s, a) = E_π[Gₜ | Sₜ = s, Aₜ = a]Relationship:
1V^π(s) = Σ π(a|s) Q^π(s, a)
2 = Expected Q-value under policy πBellman Equation for V^π(s) (recursive relationship):
1V^π(s) = Σ π(a|s) Σ P(s'|s,a) [R(s,a,s') + γV^π(s')]
2 ↑ ↑ ↑ ↑
3 policy dynamics immediate discounted futureIntuition: Value of state = immediate reward + discounted value of next state
Bellman Equation for Q^π(s, a):
1Q^π(s, a) = Σ P(s'|s,a) [R(s,a,s') + γΣ π(a'|s') Q^π(s', a')]Python Example:
1# Simple MDP: 3 states, 2 actions
2import numpy as np
3
4# States: {0, 1, 2}
5# Actions: {0, 1}
6
7# Transition probabilities P(s'|s,a)
8# Shape: (states, actions, next_states)
9P = np.array([
10 [[0.7, 0.3, 0.0], [0.4, 0.6, 0.0]], # From state 0
11 [[0.0, 0.2, 0.8], [0.0, 0.9, 0.1]], # From state 1
12 [[0.0, 0.0, 1.0], [0.0, 0.0, 1.0]], # From state 2 (terminal)
13])
14
15# Rewards R(s, a, s')
16R = np.array([
17 [[0, 0, 0], [0, 0, 0]], # From state 0
18 [[0, 0, 1], [0, 0, 1]], # From state 1
19 [[0, 0, 0], [0, 0, 0]], # From state 2
20])
21
22gamma = 0.9 # Discount factor
23
24# Deterministic policy: always take action 0
25policy = np.array([0, 0, 0])
26
27# Compute V^π using Bellman equation (iterative method)
28V = np.zeros(3)
29for _ in range(100): # Value iteration
30 V_new = np.zeros(3)
31 for s in range(3):
32 a = policy[s]
33 V_new[s] = np.sum(P[s, a, :] * (R[s, a, :] + gamma * V))
34 V = V_new
35
36print(f"State values: {V}")
37# Output: [0.81, 9.0, 0.0] (approximate)This shows state 1 has highest value—it's closest to the rewarding terminal state.
Q-Learning is a model-free RL algorithm that learns the optimal action-value function Q* without needing a model of environment dynamics.
Problem with Dynamic Programming:
Q-Learning Solution:
Goal: Learn Q*(s, a) — the expected return for taking action a in state s and acting optimally thereafter
Optimal Q-Function:
1Q*(s, a) = max_π Q^π(s, a)Bellman Optimality Equation:
1Q*(s, a) = Σ P(s'|s,a) [R(s,a,s') + γ max_a' Q*(s', a')]Q-Learning Update Rule:
1Q(s, a) ← Q(s, a) + α [Rₜ₊₁ + γ max_a' Q(s', a') - Q(s, a)]
2 ↑ ↑ ↑ ↑
3 old Q learn rate TD target TD errorWhere:
1Initialize Q(s, a) arbitrarily for all s, a
2Initialize α (learning rate), γ (discount), ε (exploration)
3
4For each episode:
5 s = initial_state
6
7 While s is not terminal:
8 # Choose action using ε-greedy policy
9 if random() < ε:
10 a = random_action() # Explore
11 else:
12 a = argmax_a Q(s, a) # Exploit
13
14 # Take action, observe result
15 s', r = environment.step(s, a)
16
17 # Update Q-value
18 Q(s, a) = Q(s, a) + α[r + γ max_a' Q(s', a') - Q(s, a)]
19
20 s = s'1import numpy as np
2import random
3
4class QLearningAgent:
5 """
6 Q-Learning agent for discrete state and action spaces
7 """
8
9 def __init__(self, n_states, n_actions, learning_rate=0.1,
10 discount=0.99, epsilon=0.1):
11 # Initialize Q-table with zeros
12 self.Q = np.zeros((n_states, n_actions))
13
14 self.alpha = learning_rate # Learning rate
15 self.gamma = discount # Discount factor
16 self.epsilon = epsilon # Exploration rate
17
18 self.n_states = n_states
19 self.n_actions = n_actions
20
21 def select_action(self, state):
22 """
23 Select action using ε-greedy policy
24 """
25 if random.random() < self.epsilon:
26 # Explore: random action
27 return random.randint(0, self.n_actions - 1)
28 else:
29 # Exploit: best action
30 return np.argmax(self.Q[state, :])
31
32 def update(self, state, action, reward, next_state, done):
33 """
34 Q-Learning update rule
35 """
36 # Current Q-value
37 current_q = self.Q[state, action]
38
39 # TD target
40 if done:
41 # No future rewards if episode ended
42 target_q = reward
43 else:
44 # Bellman update with max Q-value of next state
45 target_q = reward + self.gamma * np.max(self.Q[next_state, :])
46
47 # TD error
48 td_error = target_q - current_q
49
50 # Update Q-value
51 self.Q[state, action] = current_q + self.alpha * td_error
52
53 def decay_epsilon(self, decay_rate=0.995):
54 """
55 Gradually reduce exploration over time
56 """
57 self.epsilon = max(0.01, self.epsilon * decay_rate)
58
59
60# Simple Grid World Environment
61class GridWorld:
62 """
63 4x4 Grid World
64
65 Grid:
66 S . . G
67 . X . .
68 . . . H
69 . . . .
70
71 S = Start (0,0)
72 G = Goal (0,3) → reward +1
73 H = Hole (2,3) → reward -1
74 X = Wall (1,1) → impassable
75 """
76
77 def __init__(self):
78 self.grid_size = 4
79 self.n_states = 16 # 4x4 grid
80 self.n_actions = 4 # {up, down, left, right}
81
82 self.start_state = 0 # (0, 0)
83 self.goal_state = 3 # (0, 3)
84 self.hole_state = 11 # (2, 3)
85 self.wall_state = 5 # (1, 1)
86
87 self.state = self.start_state
88
89 def reset(self):
90 """Reset environment to start state"""
91 self.state = self.start_state
92 return self.state
93
94 def _state_to_coords(self, state):
95 """Convert state index to (row, col)"""
96 return state // 4, state % 4
97
98 def _coords_to_state(self, row, col):
99 """Convert (row, col) to state index"""
100 return row * 4 + col
101
102 def step(self, action):
103 """
104 Take action, return (next_state, reward, done)
105
106 Actions: 0=up, 1=down, 2=left, 3=right
107 """
108 row, col = self._state_to_coords(self.state)
109
110 # Apply action
111 if action == 0: # Up
112 row = max(0, row - 1)
113 elif action == 1: # Down
114 row = min(3, row + 1)
115 elif action == 2: # Left
116 col = max(0, col - 1)
117 elif action == 3: # Right
118 col = min(3, col + 1)
119
120 next_state = self._coords_to_state(row, col)
121
122 # Check for wall collision (stay in place)
123 if next_state == self.wall_state:
124 next_state = self.state
125
126 # Compute reward
127 if next_state == self.goal_state:
128 reward = 1.0
129 done = True
130 elif next_state == self.hole_state:
131 reward = -1.0
132 done = True
133 else:
134 reward = -0.01 # Small penalty for each step
135 done = False
136
137 self.state = next_state
138 return next_state, reward, done
139
140
141# Training Q-Learning Agent
142def train_q_learning():
143 env = GridWorld()
144 agent = QLearningAgent(
145 n_states=env.n_states,
146 n_actions=env.n_actions,
147 learning_rate=0.1,
148 discount=0.99,
149 epsilon=0.3
150 )
151
152 n_episodes = 1000
153 rewards_per_episode = []
154
155 for episode in range(n_episodes):
156 state = env.reset()
157 total_reward = 0
158 done = False
159 steps = 0
160
161 while not done and steps < 100:
162 # Select and take action
163 action = agent.select_action(state)
164 next_state, reward, done = env.step(action)
165
166 # Update Q-table
167 agent.update(state, action, reward, next_state, done)
168
169 state = next_state
170 total_reward += reward
171 steps += 1
172
173 rewards_per_episode.append(total_reward)
174
175 # Decay exploration rate
176 agent.decay_epsilon(decay_rate=0.995)
177
178 if (episode + 1) % 100 == 0:
179 avg_reward = np.mean(rewards_per_episode[-100:])
180 print(f"Episode {episode+1}: Avg Reward = {avg_reward:.3f}, ε = {agent.epsilon:.3f}")
181
182 return agent, rewards_per_episode
183
184# Run training
185agent, rewards = train_q_learning()
186
187# Test learned policy
188print("\nTesting learned policy:")
189env = GridWorld()
190state = env.reset()
191path = [state]
192done = False
193steps = 0
194
195while not done and steps < 20:
196 action = np.argmax(agent.Q[state, :]) # Greedy policy
197 state, reward, done = env.step(action)
198 path.append(state)
199 steps += 1
200
201print(f"Path taken: {path}")
202print(f"Steps to goal: {len(path) - 1}")1. Off-Policy Learning:
2. Bootstrapping:
3. Guaranteed Convergence:
4. Works with Function Approximation:
The exploration-exploitation dilemma is fundamental to RL: Should the agent try new actions (explore) or stick with known good actions (exploit)?
Exploitation: Choose action with highest Q-value
Exploration: Try actions you haven't tried much
Example - Restaurant Selection:
1Option A: Exploit
2→ Go to your favorite restaurant (guaranteed satisfaction)
3→ But you'll never discover potentially better restaurants
4
5Option B: Explore
6→ Try a new restaurant (might be better or worse)
7→ Gain information for future decisions1. ε-Greedy Policy (most common)
1def epsilon_greedy(Q, state, epsilon=0.1):
2 """
3 With probability ε: random action (explore)
4 With probability 1-ε: best action (exploit)
5 """
6 if random.random() < epsilon:
7 return random.choice(range(len(Q[state]))) # Explore
8 else:
9 return np.argmax(Q[state]) # Exploit
10
11# Typical values: ε ∈ [0.01, 0.3]
12# Often decay ε over time: start high, end low2. Boltzmann (Softmax) Exploration
1def boltzmann_policy(Q, state, temperature=1.0):
2 """
3 Sample action proportional to exp(Q/T)
4
5 High T: nearly uniform (lots of exploration)
6 Low T: greedy (mostly exploitation)
7 """
8 logits = Q[state] / temperature
9 exp_logits = np.exp(logits - np.max(logits)) # Numerical stability
10 probs = exp_logits / np.sum(exp_logits)
11 return np.random.choice(len(Q[state]), p=probs)
12
13# Temperature annealing: start T=10, decay to T=0.13. Upper Confidence Bound (UCB)
1def ucb_action_selection(Q, N, state, c=2.0, t=1):
2 """
3 Choose action with highest upper confidence bound
4
5 UCB = Q(s,a) + c * sqrt(log(t) / N(s,a))
6 ↑ ↑
7 mean value uncertainty bonus
8
9 N(s,a) = number of times action a taken in state s
10 t = total timesteps
11 c = exploration constant
12 """
13 ucb_values = Q[state] + c * np.sqrt(np.log(t + 1) / (N[state] + 1))
14 return np.argmax(ucb_values)
15
16# Automatically balances exploration and exploitation
17# Explores actions with high uncertainty4. Optimistic Initial Values
1# Instead of Q(s,a) = 0 initially, set Q(s,a) = large_value
2Q = np.ones((n_states, n_actions)) * 10.0
3
4# Effect: Agent tries all actions early (they all look good)
5# As Q-values update, agent discovers true values
6# Simple but effective for encouraging early explorationDecay Strategies for ε-greedy:
1# 1. Linear decay
2epsilon = max(epsilon_min, epsilon_start - episode * decay_rate)
3
4# 2. Exponential decay
5epsilon = max(epsilon_min, epsilon_start * (decay_rate ** episode))
6
7# 3. Step decay
8if episode % 100 == 0:
9 epsilon *= 0.5
10
11# 4. Adaptive decay (based on performance)
12if avg_reward_increasing:
13 epsilon *= 0.99 # Exploit more
14else:
15 epsilon *= 1.01 # Explore more1import numpy as np
2import matplotlib.pyplot as plt
3
4class MultiArmedBandit:
5 """
6 K-armed bandit problem
7
8 K slot machines, each with different (unknown) reward probability
9 Goal: maximize total reward over T pulls
10 """
11
12 def __init__(self, k=10):
13 self.k = k
14 # True reward probabilities (unknown to agent)
15 self.true_probs = np.random.uniform(0, 1, k)
16 self.optimal_action = np.argmax(self.true_probs)
17
18 def pull(self, action):
19 """Pull arm, get reward (1 or 0)"""
20 return 1 if np.random.random() < self.true_probs[action] else 0
21
22
23def compare_exploration_strategies(n_steps=1000):
24 """Compare ε-greedy, softmax, and UCB"""
25
26 strategies = {
27 'ε-greedy (0.1)': 'epsilon_greedy',
28 'Softmax (T=1)': 'softmax',
29 'UCB': 'ucb'
30 }
31
32 results = {name: [] for name in strategies}
33
34 for strategy_name, strategy_type in strategies.items():
35 bandit = MultiArmedBandit(k=10)
36 Q = np.zeros(10) # Estimated values
37 N = np.zeros(10) # Action counts
38
39 rewards = []
40
41 for t in range(n_steps):
42 # Select action based on strategy
43 if strategy_type == 'epsilon_greedy':
44 if np.random.random() < 0.1:
45 action = np.random.randint(10)
46 else:
47 action = np.argmax(Q)
48
49 elif strategy_type == 'softmax':
50 temp = 1.0
51 probs = np.exp(Q / temp) / np.sum(np.exp(Q / temp))
52 action = np.random.choice(10, p=probs)
53
54 elif strategy_type == 'ucb':
55 if t < 10: # Try each action once
56 action = t
57 else:
58 ucb = Q + 2 * np.sqrt(np.log(t) / (N + 1e-5))
59 action = np.argmax(ucb)
60
61 # Pull arm, get reward
62 reward = bandit.pull(action)
63
64 # Update estimates
65 N[action] += 1
66 Q[action] += (reward - Q[action]) / N[action] # Incremental mean
67
68 rewards.append(reward)
69
70 results[strategy_name] = rewards
71
72 # Plot results
73 plt.figure(figsize=(12, 5))
74 for name, rewards in results.items():
75 cumulative = np.cumsum(rewards)
76 plt.plot(cumulative, label=name, linewidth=2)
77
78 plt.xlabel('Steps', fontweight='bold')
79 plt.ylabel('Cumulative Reward', fontweight='bold')
80 plt.title('Exploration Strategy Comparison', fontweight='bold', fontsize=14)
81 plt.legend()
82 plt.grid(True, alpha=0.3)
83 plt.show()
84
85compare_exploration_strategies()Early Training: High exploration
Mid Training: Moderate exploration
Late Training / Deployment: Low exploration
Production Systems: Minimal exploration
Beyond basic Q-Learning, modern RL includes powerful extensions and real-world applications.
Problem: Q-tables don't scale to large state spaces
Solution: Function approximation with neural networks
1import torch
2import torch.nn as nn
3
4class DQN(nn.Module):
5 """
6 Deep Q-Network: Neural network approximates Q(s, a)
7 """
8
9 def __init__(self, state_dim, action_dim):
10 super().__init__()
11 self.network = nn.Sequential(
12 nn.Linear(state_dim, 128),
13 nn.ReLU(),
14 nn.Linear(128, 128),
15 nn.ReLU(),
16 nn.Linear(128, action_dim) # Output Q-value for each action
17 )
18
19 def forward(self, state):
20 """Return Q-values for all actions"""
21 return self.network(state)
22
23# Usage
24state_dim = 4 # CartPole: position, velocity, angle, angular velocity
25action_dim = 2 # Left or Right
26
27dqn = DQN(state_dim, action_dim)
28state = torch.randn(1, 4) # Single state
29q_values = dqn(state) # Output: [Q(s,left), Q(s,right)]
30action = torch.argmax(q_values) # Choose best actionDQN Innovations (2015, Nature paper):
Alternative Approach: Directly optimize policy π_θ(a|s)
1# Policy gradient: maximize expected return
2θ = θ + α ∇_θ J(θ)
3
4# Where J(θ) = E[Σ γ^t R_t] (expected cumulative reward)Advantages:
Algorithms:
1. Autonomous Vehicles
1State: Camera images, LIDAR, speed, GPS
2Actions: Steering angle, acceleration, braking
3Reward: Stay in lane (+), smooth driving (+), collision (-)
4Algorithm: Deep RL with safety constraints2. Robotics
3. Game Playing
4. Recommender Systems
1State: User history, context
2Actions: Item to recommend
3Reward: Click (+), purchase (++), engagement time
4Algorithm: Contextual bandits, Deep RL5. Resource Management
6. Finance
7. Healthcare
1. Sample Efficiency
2. Reward Engineering
3. Exploration in Large Spaces
4. Partial Observability
5. Safety
Trends:
Open Research Questions:
In Lesson 19: Deep Reinforcement Learning, you'll learn:
You'll build RL agents that master Atari games, control continuous systems, and learn complex behaviors from pixels!
Implement a complete Q-Learning agent that learns to navigate a grid world environment. The agent will discover the optimal path to the goal while avoiding obstacles through trial and error.
1# Complete Q-Learning Implementation
2# Agent learns to navigate grid world environment
3
4import numpy as np
5import matplotlib.pyplot as plt
6from collections import defaultdict
7import random
8
9# ============================================================================
10# PART 1: Grid World Environment
11# ============================================================================
12
13class GridWorldEnv:
14 """
15 Grid World Environment
16
17 Grid Layout (5x5):
18 S . . . .
19 . X X . .
20 . . . X .
21 . X . . .
22 . . . . G
23
24 S = Start (0,0)
25 G = Goal (4,4) → +10 reward
26 X = Wall → impassable
27 . = Empty → -0.1 reward per step
28 """
29
30 def __init__(self, size=5):
31 self.size = size
32 self.n_states = size * size
33 self.n_actions = 4 # up, down, left, right
34
35 # Special positions
36 self.start_pos = (0, 0)
37 self.goal_pos = (4, 4)
38 self.walls = {(1, 1), (1, 2), (2, 3), (3, 1)}
39
40 self.current_pos = self.start_pos
41
42 def reset(self):
43 """Reset to start position"""
44 self.current_pos = self.start_pos
45 return self._pos_to_state(self.current_pos)
46
47 def _pos_to_state(self, pos):
48 """Convert (row, col) to state index"""
49 return pos[0] * self.size + pos[1]
50
51 def _state_to_pos(self, state):
52 """Convert state index to (row, col)"""
53 return (state // self.size, state % self.size)
54
55 def step(self, action):
56 """
57 Take action, return (next_state, reward, done)
58
59 Actions:
60 0 = UP, 1 = DOWN, 2 = LEFT, 3 = RIGHT
61 """
62 row, col = self.current_pos
63
64 # Apply action
65 if action == 0: # UP
66 new_pos = (max(0, row - 1), col)
67 elif action == 1: # DOWN
68 new_pos = (min(self.size - 1, row + 1), col)
69 elif action == 2: # LEFT
70 new_pos = (row, max(0, col - 1))
71 elif action == 3: # RIGHT
72 new_pos = (row, min(self.size - 1, col + 1))
73 else:
74 new_pos = self.current_pos
75
76 # Check for wall collision
77 if new_pos in self.walls:
78 new_pos = self.current_pos # Stay in place
79 reward = -0.5 # Penalty for hitting wall
80 elif new_pos == self.goal_pos:
81 reward = 10.0 # Big reward for reaching goal
82 else:
83 reward = -0.1 # Small penalty for each step
84
85 self.current_pos = new_pos
86 next_state = self._pos_to_state(new_pos)
87 done = (new_pos == self.goal_pos)
88
89 return next_state, reward, done
90
91 def render(self, q_values=None, policy=None):
92 """
93 Visualize grid world
94
95 Can optionally show Q-values or learned policy
96 """
97 grid = np.zeros((self.size, self.size))
98
99 # Mark walls
100 for wall in self.walls:
101 grid[wall] = -1
102
103 # Mark goal
104 grid[self.goal_pos] = 2
105
106 # Mark current position
107 grid[self.current_pos] = 1
108
109 plt.figure(figsize=(8, 8))
110 plt.imshow(grid, cmap='RdYlGn', alpha=0.7)
111
112 # Draw grid lines
113 for i in range(self.size + 1):
114 plt.axhline(i - 0.5, color='black', linewidth=1)
115 plt.axvline(i - 0.5, color='black', linewidth=1)
116
117 # Add labels
118 for i in range(self.size):
119 for j in range(self.size):
120 if (i, j) == self.start_pos:
121 plt.text(j, i, 'S', ha='center', va='center',
122 fontsize=20, fontweight='bold', color='blue')
123 elif (i, j) == self.goal_pos:
124 plt.text(j, i, 'G', ha='center', va='center',
125 fontsize=20, fontweight='bold', color='green')
126 elif (i, j) in self.walls:
127 plt.text(j, i, 'X', ha='center', va='center',
128 fontsize=20, fontweight='bold', color='red')
129
130 # Draw policy arrows if provided
131 if policy is not None:
132 arrows = ['↑', '↓', '←', '→']
133 for i in range(self.size):
134 for j in range(self.size):
135 if (i, j) not in self.walls and (i, j) != self.goal_pos:
136 state = self._pos_to_state((i, j))
137 action = policy[state]
138 plt.text(j, i + 0.3, arrows[action],
139 ha='center', va='center',
140 fontsize=16, color='purple')
141
142 plt.title('Grid World Environment', fontsize=14, fontweight='bold')
143 plt.xticks([])
144 plt.yticks([])
145 plt.tight_layout()
146 plt.show()
147
148
149# ============================================================================
150# PART 2: Q-Learning Agent
151# ============================================================================
152
153class QLearningAgent:
154 """
155 Q-Learning Agent with ε-greedy exploration
156 """
157
158 def __init__(self, n_states, n_actions, learning_rate=0.1,
159 discount=0.99, epsilon=0.3):
160 # Initialize Q-table
161 self.Q = np.zeros((n_states, n_actions))
162
163 # Hyperparameters
164 self.alpha = learning_rate
165 self.gamma = discount
166 self.epsilon = epsilon
167 self.epsilon_min = 0.01
168 self.epsilon_decay = 0.995
169
170 self.n_states = n_states
171 self.n_actions = n_actions
172
173 # For tracking
174 self.training_history = {
175 'episodes': [],
176 'rewards': [],
177 'steps': [],
178 'epsilon': []
179 }
180
181 def select_action(self, state, training=True):
182 """
183 ε-greedy action selection
184
185 During training: explore with probability ε
186 During testing: always exploit (greedy)
187 """
188 if training and random.random() < self.epsilon:
189 # Explore: random action
190 return random.randint(0, self.n_actions - 1)
191 else:
192 # Exploit: best known action
193 return np.argmax(self.Q[state, :])
194
195 def update(self, state, action, reward, next_state, done):
196 """
197 Q-Learning update rule
198
199 Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)]
200 """
201 # Current Q-value
202 current_q = self.Q[state, action]
203
204 # Compute TD target
205 if done:
206 # No future rewards if episode ended
207 td_target = reward
208 else:
209 # Bellman update
210 max_next_q = np.max(self.Q[next_state, :])
211 td_target = reward + self.gamma * max_next_q
212
213 # Compute TD error
214 td_error = td_target - current_q
215
216 # Update Q-value
217 self.Q[state, action] = current_q + self.alpha * td_error
218
219 return td_error
220
221 def decay_epsilon(self):
222 """Reduce exploration rate over time"""
223 self.epsilon = max(self.epsilon_min,
224 self.epsilon * self.epsilon_decay)
225
226 def get_policy(self):
227 """Extract greedy policy from Q-table"""
228 return np.argmax(self.Q, axis=1)
229
230 def get_value_function(self):
231 """Extract state value function V(s) = max_a Q(s,a)"""
232 return np.max(self.Q, axis=1)
233
234
235# ============================================================================
236# PART 3: Training Loop
237# ============================================================================
238
239def train_agent(n_episodes=500, verbose=True):
240 """
241 Train Q-Learning agent on Grid World
242 """
243 # Initialize environment and agent
244 env = GridWorldEnv()
245 agent = QLearningAgent(
246 n_states=env.n_states,
247 n_actions=env.n_actions,
248 learning_rate=0.1,
249 discount=0.99,
250 epsilon=0.3
251 )
252
253 print("=" * 70)
254 print("TRAINING Q-LEARNING AGENT")
255 print("=" * 70)
256 print(f"Environment: {env.size}x{env.size} Grid World")
257 print(f"States: {env.n_states}, Actions: {env.n_actions}")
258 print(f"Episodes: {n_episodes}")
259 print()
260
261 # Training loop
262 for episode in range(n_episodes):
263 # Reset environment
264 state = env.reset()
265 total_reward = 0
266 steps = 0
267 done = False
268
269 # Episode loop
270 while not done and steps < 100: # Max 100 steps per episode
271 # Select action
272 action = agent.select_action(state, training=True)
273
274 # Take action
275 next_state, reward, done = env.step(action)
276
277 # Update Q-values
278 td_error = agent.update(state, action, reward, next_state, done)
279
280 # Move to next state
281 state = next_state
282 total_reward += reward
283 steps += 1
284
285 # Decay exploration rate
286 agent.decay_epsilon()
287
288 # Record training stats
289 agent.training_history['episodes'].append(episode)
290 agent.training_history['rewards'].append(total_reward)
291 agent.training_history['steps'].append(steps)
292 agent.training_history['epsilon'].append(agent.epsilon)
293
294 # Print progress
295 if verbose and (episode + 1) % 50 == 0:
296 avg_reward = np.mean(agent.training_history['rewards'][-50:])
297 avg_steps = np.mean(agent.training_history['steps'][-50:])
298 print(f"Episode {episode+1:4d} | "
299 f"Avg Reward: {avg_reward:6.2f} | "
300 f"Avg Steps: {avg_steps:5.1f} | "
301 f"ε: {agent.epsilon:.3f}")
302
303 print()
304 print("Training complete!")
305 print()
306
307 return agent, env
308
309
310# ============================================================================
311# PART 4: Evaluation and Visualization
312# ============================================================================
313
314def evaluate_agent(agent, env, n_episodes=10):
315 """
316 Test learned policy
317 """
318 print("=" * 70)
319 print("EVALUATING LEARNED POLICY")
320 print("=" * 70)
321 print()
322
323 total_rewards = []
324 total_steps = []
325
326 for episode in range(n_episodes):
327 state = env.reset()
328 episode_reward = 0
329 steps = 0
330 done = False
331 path = [state]
332
333 while not done and steps < 100:
334 # Greedy action selection (no exploration)
335 action = agent.select_action(state, training=False)
336 next_state, reward, done = env.step(action)
337
338 path.append(next_state)
339 episode_reward += reward
340 state = next_state
341 steps += 1
342
343 total_rewards.append(episode_reward)
344 total_steps.append(steps)
345
346 print(f"Episode {episode+1}: Reward = {episode_reward:.2f}, "
347 f"Steps = {steps}, Success = {done}")
348
349 print()
350 print(f"Average Reward: {np.mean(total_rewards):.2f} ± {np.std(total_rewards):.2f}")
351 print(f"Average Steps: {np.mean(total_steps):.2f} ± {np.std(total_steps):.2f}")
352 print(f"Success Rate: {sum(1 for r in total_rewards if r > 0) / len(total_rewards) * 100:.1f}%")
353 print()
354
355
356def visualize_training(agent):
357 """
358 Plot training curves
359 """
360 history = agent.training_history
361
362 fig, axes = plt.subplots(2, 2, figsize=(14, 10))
363 fig.suptitle('Q-Learning Training Progress', fontsize=16, fontweight='bold')
364
365 # Rewards over time
366 ax = axes[0, 0]
367 window = 20
368 smoothed = np.convolve(history['rewards'],
369 np.ones(window)/window, mode='valid')
370 ax.plot(history['episodes'][:len(smoothed)], smoothed,
371 linewidth=2, color='blue')
372 ax.set_xlabel('Episode', fontweight='bold')
373 ax.set_ylabel('Reward (smoothed)', fontweight='bold')
374 ax.set_title('Episode Rewards', fontweight='bold')
375 ax.grid(True, alpha=0.3)
376
377 # Steps over time
378 ax = axes[0, 1]
379 smoothed = np.convolve(history['steps'],
380 np.ones(window)/window, mode='valid')
381 ax.plot(history['episodes'][:len(smoothed)], smoothed,
382 linewidth=2, color='green')
383 ax.set_xlabel('Episode', fontweight='bold')
384 ax.set_ylabel('Steps (smoothed)', fontweight='bold')
385 ax.set_title('Steps to Goal', fontweight='bold')
386 ax.grid(True, alpha=0.3)
387
388 # Epsilon decay
389 ax = axes[1, 0]
390 ax.plot(history['episodes'], history['epsilon'],
391 linewidth=2, color='red')
392 ax.set_xlabel('Episode', fontweight='bold')
393 ax.set_ylabel('Epsilon', fontweight='bold')
394 ax.set_title('Exploration Rate (ε)', fontweight='bold')
395 ax.grid(True, alpha=0.3)
396
397 # Value function heatmap
398 ax = axes[1, 1]
399 V = agent.get_value_function().reshape(5, 5)
400 im = ax.imshow(V, cmap='viridis')
401 ax.set_title('Learned Value Function V(s)', fontweight='bold')
402 plt.colorbar(im, ax=ax)
403
404 for i in range(5):
405 for j in range(5):
406 ax.text(j, i, f'{V[i,j]:.1f}',
407 ha='center', va='center',
408 color='white', fontsize=10, fontweight='bold')
409
410 plt.tight_layout()
411 plt.show()
412
413
414# ============================================================================
415# PART 5: Run Complete Demo
416# ============================================================================
417
418print("\n" + "=" * 70)
419print("REINFORCEMENT LEARNING: Q-LEARNING DEMO")
420print("=" * 70)
421print()
422
423# Show environment
424print("Step 1: Environment Setup")
425env = GridWorldEnv()
426env.render()
427print()
428
429# Train agent
430print("Step 2: Training Agent...")
431agent, env = train_agent(n_episodes=500, verbose=True)
432
433# Visualize training
434print("Step 3: Training Visualization")
435visualize_training(agent)
436
437# Evaluate agent
438print("Step 4: Testing Learned Policy")
439evaluate_agent(agent, env, n_episodes=10)
440
441# Show learned policy
442print("Step 5: Learned Policy Visualization")
443policy = agent.get_policy()
444env.reset()
445env.render(policy=policy)
446
447print()
448print("=" * 70)
449print("✅ Q-LEARNING DEMO COMPLETE")
450print("=" * 70)
451print()
452print("Key Takeaways:")
453print(" • Q-Learning learns optimal policy through trial and error")
454print(" • ε-greedy balances exploration and exploitation")
455print(" • Agent discovers shortest path to goal without being told")
456print(" • Learned Q-values represent expected future rewards")
457print(" • Works without model of environment dynamics")
458print()This comprehensive example demonstrates Q-Learning—a fundamental model-free RL algorithm—applied to a grid world navigation task.
1. Complete RL System
The implementation includes all components of a working RL system:
2. Q-Learning Algorithm
The update rule implements temporal difference learning:
1Q(s,a) ← Q(s,a) + α[R + γ max_a' Q(s',a') - Q(s,a)]This bootstrapping update propagates reward information backward from the goal to earlier states, allowing the agent to learn which actions lead to high long-term rewards.
3. Exploration-Exploitation Trade-off
The ε-greedy policy balances:
4. Learning Without a Model
Q-Learning is model-free—it learns directly from experience without knowing:
The agent discovers optimal behavior purely through trial and error.
5. Value Function Convergence
Over training, Q-values converge to optimal values Q*(s,a):
Episode 1-50: Random exploration
Episode 51-200: Effective learning
Episode 201-500: Policy refinement
This simple example demonstrates principles that power:
In Lesson 19, you'll extend these concepts to deep RL, continuous actions, and policy gradient methods!
Outstanding work! You've mastered the fundamentals of Reinforcement Learning—understanding how agents learn optimal policies through trial-and-error interaction with environments.
Next: In Lesson 19: Deep Reinforcement Learning, you'll extend these concepts to high-dimensional spaces using neural networks. You'll learn:
You'll build agents that master Atari games from pixels, control continuous systems like CartPole and Pendulum, and implement PPO for complex tasks.
Your RL Journey: From Q-tables (today) → Deep Q-Networks (next) → Policy Gradients → PPO → Real-world applications!
Ready to scale RL to complex, high-dimensional problems? Let's dive into Deep RL! 🚀
Your progress is saved in this browser, on this device only.