This page contains exercise answers and teaching guidance for
Step 10 — ML Extension (Q-Learning).
Not linked from the student pages.
Students: please go back and try the activities first.
STEP 10 OF 10 · FACILITATOR NOTES · FINAL STEP 🏆
Students apply Reinforcement Learning — specifically Q-Learning — to train a Snake AI agent. No neural network is involved: the Q-table is a Python defaultdict, making the entire algorithm inspectable and debuggable by hand. The goal is conceptual mastery: students should understand the feedback loop (state → action → reward → update), not implement a full Snake simulator from scratch.
| Item | Detail |
|---|---|
| Topic | Q-Learning (tabular RL) applied to Snake |
| Duration | ~90 minutes (can extend to 2 sessions for Tier 3/4) |
| Prerequisite | Step 9 — OOP Refactor (Snake/Food/Game classes) |
| Activity type | Code completion → Debugging → Compose → Create |
| GAS tab | Act_10 |
| LMS localStorage key | lms_step10 |
| Post-survey | Students go to survey-post.html after submitting Journal |
| Difficulty | Highest in the series — Bellman equation, epsilon decay are new concepts |
survey-post.html is live and accessible before this session. This is the last activity — students proceed directly to the post-survey after completing the Journal.| # | Objective | Assessed in |
|---|---|---|
| 1 | Explain what the Q-table stores and why defaultdict is suitable | CQ Q5, Journal JR1 |
| 2 | Implement the epsilon-greedy action selection rule correctly | T1 B2, T2 Bug 2, CQ Q2 |
| 3 | Apply the Bellman equation to update Q-values | T1 B5/B6, T3, CQ Q3 |
| 4 | Assign correct reward signals for eat / die / survive events | T1 B4, T2 Bug 3 |
| 5 | Implement epsilon decay and explain its rationale | T4, Journal JR2 |
| 6 | Analyse how reward shaping changes snake behaviour | Journal JR4 |
from collections import defaultdict
import random
# ── Data structures ──────────────────────────────────────────
q_table = defaultdict(float) # {(state, action): Q-value}
# defaultdict returns 0.0 for unseen keys
# ── Hyperparameters ──────────────────────────────────────────
EPSILON = 0.1 # exploration rate (10% random, 90% exploit)
ALPHA = 0.2 # learning rate (how fast Q-values update)
GAMMA = 0.9 # discount factor (how much future reward matters)
ACTIONS = ['UP', 'DOWN', 'LEFT', 'RIGHT']
# ── Action selection: epsilon-greedy ─────────────────────────
def choose_action(state):
if random.random() < EPSILON: # explore (10%)
return random.choice(ACTIONS)
return max(ACTIONS, key=lambda a: q_table[(state, a)]) # exploit
# ── Reward function ──────────────────────────────────────────
def reward(ate_food, died):
if died: return -10 # large negative: death is bad
if ate_food: return 10 # large positive: food is good
return -0.1 # tiny negative: penalise inefficiency
# ── Bellman update ───────────────────────────────────────────
def update_q(state, action, r, next_state):
old_q = q_table[(state, action)]
best_future = max(q_table[(next_state, a)] for a in ACTIONS)
target = r + GAMMA * best_future # TD target
q_table[(state, action)] = old_q + ALPHA * (target - old_q)
defaultdict(float) — any unseen (state, action) key returns 0.0 automatically. A plain {} raises KeyError on the very first new state, crashing training.random() < EPSILON, not >.The activity checks these exact strings (case-insensitive after trimming). If a student types Default_dict it will fail — only defaultdict passes.
| Blank | Correct answer | Common wrong answer | Why |
|---|---|---|---|
B1 — from collections import ___ |
defaultdict |
dict, default_dict |
The only collections class that auto-initialises missing keys to a default factory (float → 0.0). A plain dict raises KeyError immediately. |
B2 — ___ = 0.1 |
EPSILON |
epsilon (lowercase), EPSILION |
Python constants by convention use SCREAMING_SNAKE_CASE. The activity is case-insensitive but the concept of naming conventions matters here. |
B3 — return ___(q_table[(state, a)] for a in ACTIONS) |
max |
min, argmax, np.max |
The exploit branch returns the action with the highest Q-value. min would make the snake actively seek death. |
B4 — return ±___ (food / death magnitude) |
10 |
1, 100 |
Both food (+10) and death (−10) share the same magnitude. Relative magnitudes shape learning speed; any consistent non-zero value technically works but 10 is standard in tutorial implementations. |
B5 — old_q + ___ * (target − old_q) |
ALPHA |
alpha, GAMMA, lr |
ALPHA (the learning rate) controls how fast Q-values shift. ALPHA=1 means full replacement; ALPHA=0 means no learning. |
B6 — target = reward + ___ * best |
GAMMA |
gamma, ALPHA, 0.9 |
GAMMA (the discount factor) weighs future rewards. GAMMA=0 → only immediate reward counts; GAMMA=0.9 → agent plans up to ~10 steps ahead. |
q_table = {}q_table = defaultdict(float)Why it matters: A plain {} raises KeyError the first time the agent sees a new (state, action) pair — which happens immediately on episode 1. defaultdict(float) returns 0.0 for any unseen key, which is the correct initial Q-value (no prior knowledge).
if random.random() > EPSILON:if random.random() < EPSILON:Why it matters: With >, random() exceeds 0.1 about 90% of the time — the agent explores randomly 90% of the time and exploits only 10%. This completely inverts the intended behaviour. With EPSILON=0.1, the agent should explore only 10% of the time.
if died: return 10if died: return -10Why it matters: A positive reward for dying means the agent learns to seek death. After many training episodes it would find the fastest path to a wall. Ask students: "What score would you expect after 10 000 episodes with this bug?"
random.random() less than 0.1?" This usually resolves it without giving away the answer.Students must write the body of update_q() from scratch. Accept any equivalent formulation that correctly implements the Bellman update.
def update_q(state, action, reward, next_state):
old_q = q_table[(state, action)] # current Q-value for this pair
best_future = max(q_table[(next_state, a)] # best Q-value reachable from next state
for a in ACTIONS)
target = reward + GAMMA * best_future # TD target (Bellman RHS)
q_table[(state, action)] = old_q + ALPHA * (target - old_q) # weighted blend
| Mistake | Consequence |
|---|---|
Omitting old_q — replacing rather than blending | Agent has no memory of past; learns only from the last episode step |
Using min instead of max for best_future | Agent learns to avoid the worst action, not seek the best one |
q_table[...] = target (missing the ALPHA blend) | Equivalent to ALPHA=1; single-step replacement causes oscillation |
| Swapping ALPHA and GAMMA roles in the equation | Discount factor effectively becomes the learning rate — very slow/unstable learning |
q_table[state][action] (nested dict syntax) | KeyError — the key must be the tuple (state, action), not nested dicts |
Students add epsilon decay to the training loop. Requirements: start 0.5, multiply by 0.995 each episode, clamp minimum at 0.01, print every 500 episodes.
NUM_EPISODES = 5000
EPSILON = 0.5 # start exploring 50% of the time
for episode in range(NUM_EPISODES):
run_episode() # run one episode using current EPSILON
# --- Add your epsilon decay code below this line ---
EPSILON = max(0.01, EPSILON * 0.995) # decay and clamp
# --- End of your addition ---
if episode % 500 == 0:
print(f"Episode {episode}: epsilon = {EPSILON:.4f}")
The activity uses 0-indexed option numbering internally. The correct indices are shown below.
| Q | Index | Correct option text | Key teaching point |
|---|---|---|---|
| Q1 | 1 | "The estimated long-term reward for taking each action in each state" | Q-values are estimates of long-run return, not immediate reward. Distractor 0 (pixel colours) points at DQN/CNN vision models, not tabular RL. |
| Q2 | 0 | "The agent picks a random action (explores)" | When random() < EPSILON is True the agent explores. This is exactly what the Bug 2 fix addresses. Students who fixed Bug 2 correctly should ace this question. |
| Q3 | 2 | "It discounts future rewards relative to immediate ones" | GAMMA is the discount factor. Distractor 0 (learning rate) is the classic ALPHA/GAMMA confusion. Distractor 1 (exploration probability) is EPSILON. |
| Q4 | 1 | "To penalise inefficiency and teach the snake to reach food quickly" | Without a step penalty the agent can survive indefinitely by circling. The small negative encourages shorter paths to food. Distractor 0 (Q-table memory) is unrelated to the reward signal. |
| Q5 | 0 | "Any unseen (state, action) pair automatically gets Q-value 0.0, so no KeyError is raised" | This is precisely the purpose of defaultdict(float). Distractor 1 (integer conversion) is false — floats are stored as-is. |
Use these notes when giving verbal or written feedback on student journal entries.
| Prompt | What a strong answer contains | Red flags |
|---|---|---|
| JR1 Q-table & snake decisions |
Q(s,a) stores estimated cumulative reward; the snake looks up all four actions for the current state and picks the one with the highest Q-value. The dictionary is ideal because the state space (2¹¹ = 2 048 entries) is large but sparse — most state-action pairs may never appear in training. | Confusing Q-values with immediate reward; saying the dict "stores the game state" rather than the Q-values. |
| JR2 Epsilon decay rationale |
EPSILON=0 early → agent exploits suboptimal strategies it found by luck; EPSILON=1 always → agent never uses learned knowledge. Decay allows a transition from exploration (learn everything) to exploitation (use what was learned). Too fast: locks in bad strategies. Never decays: never converges. | Addressing only one extreme; not connecting decay to the training lifecycle or episode count. |
| JR3 RL vs human learning |
Maps agent → learner, state → situation, action → choice, reward → consequence. Key difference: humans use prior knowledge, intuition, and language; the agent starts with a blank Q-table and learns purely from trial-and-error feedback. Similarity: both improve through repeated experience. | Vague analogies with no mapping to RL terms; confusing supervised learning ("teacher gives examples") with RL ("feedback from environment"). |
| JR4 Step penalty −1.0 vs −0.1 |
A step penalty of −1.0 makes the snake extremely impatient: dying (−10) is only 10 steps of survival, so the snake may prefer short suicidal routes over longer safe ones. The snake might circle back toward food and clip a wall rather than take a longer safe path. Contrast: with −0.1, dying costs 100 equivalent steps, so survival is strongly preferred. | Simply saying "snake moves faster" (the physics don't change); not reasoning about the relative magnitudes of death vs survival penalty. |
| JR5 Q-values for food-right, no-danger state |
After 5 000 episodes, Q("food right, no danger", RIGHT) should be the highest value (~+8 to +10) because RIGHT leads immediately to food. The other three actions would have lower Q-values, possibly negative if they have led to death in training. Students should reason from the Bellman equation: high immediate reward + positive future rewards → high Q-value. | Wild guesses with no reasoning; not connecting Q-value magnitude to the Bellman update or reward signal. |
| Symptom | Likely cause | Suggested intervention |
|---|---|---|
| "My Q-table is always empty after training" | Bug 1 — used plain {}; KeyError crashes training silently |
Ask them to print the Q-table after episode 1. If empty or error, walk through the Bug 1 fix together. |
| "Snake never improves after 10 000 episodes" | Bug 2 — flipped epsilon. Agent explores 90% of the time forever. | Have them print "EXPLORE" vs "EXPLOIT" for the first 20 steps. Should be ~10% explore with EPSILON=0.1. |
| "Snake actively avoids all food" | Bug 3 — positive reward for dying. Agent learned to seek death to collect +10. | Ask: "What reward does your code give when the snake eats food? What about when it dies?" Signs should be opposite. |
| Confusing ALPHA and GAMMA | Two float hyperparameters in the same equation | Memory trick: ALPHA → Adjust (learning speed); GAMMA → Gaze (future-planning distance). |
| "What is the state tuple again?" | Students may have skipped step-10.html |
Direct them to step-10.html → "State representation" section. 3 danger bits + 4 direction one-hot + 4 food-direction bits = 11 bits total. |
| "Epsilon never reaches 0.01 minimum" | Tier 4: missing the max(0.01, ...) clamp |
"What is 0.5 × 0.995 after 1 000 episodes?" — it approaches 0 without a floor. max(lower_bound, value) is the standard pattern. |
KeyError: (state, action) in Tier 3 |
Using q_table[state][action] (nested dict) instead of tuple key |
Demonstrate: defaultdict(float) maps a tuple to a float. q_table[(state, action)] is one lookup; q_table[state][action] expects a nested structure. |
| Phase | Duration | Facilitator action |
|---|---|---|
| Introduction / concept framing | 10 min | Explain RL feedback loop on whiteboard: state → agent → action → environment → reward → state. Draw the Snake board as the environment. |
| Pre-calibration | 3 min | Let students fill in independently. Encourage honest predictions. |
| Tier 1 — Fill blanks | 12 min | Circulate. The ALPHA/GAMMA swap is the most common confusion — don't give the answer; ask guiding questions. |
| Tier 2 — Debugging | 12 min | After Bug 1, discuss: "Why would a plain dict fail here?" — connect to Python's KeyError mechanism. |
| Mid-reflection | 5 min | Pair share — "What breaks if epsilon is always 0 or always 1?" |
| Tier 3 — Bellman equation | 15 min | Write on board: Q(s,a) ← Q(s,a) + α[r + γ max Q(s′,a′) − Q(s,a)]. Ask students to translate each term into Python. |
| Tier 4 — Epsilon decay | 12 min | Most students can attempt independently. Prompt: "Where in the loop does each episode end? That's where to decay." |
| Concept check | 5 min | Independent. Allow re-attempt — focus on understanding, not score anxiety. |
| Journal writing | 10 min | Encourage extended reflection for JR4 (reward shaping) and JR5 (Q-value prediction). These are the deepest thinking prompts in the series. |
| Post-calibration & submit | 5 min | Confirm all fields filled. Students then navigate to survey-post.html — confirm the link is live before this step. |
| Buffer / wrap-up | ±10 min | Optional: show a trained agent running in real time if you have a demo video. Discuss what comes after Q-Learning (DQN, neural networks, PPO). |
These are the 44 columns written to the Act_10 tab by handleAct10Record() in the GAS script.
if (t === 'act_10' || data.tab === 'Act_10') return handleAct10Record(data, ss);