"""Lesson 3 -- Neural Network with Semi-gradient Descent. θ ← θ + α·[ r + γ·Vθ(s′) − Vθ(s) ]·∇θ Vθ(s) """ import random import statistics from collections import defaultdict, deque from enum import Enum, auto import numpy as np GAMMA = 0.9 ALPHA = 0.1 JUMP_SUCCESS_PROBABILITY = 0.60 class Action(Enum): THRUST = 0 JUMP = 1 # --- The game, behind a wall ------------------------------------------------ # MODEL-FREE WALL: the learning loop below may call step() and NOTHING else. # It never reads JUMP_SUCCESS_PROBABILITY and never consults a transition # table. step() is the only window onto the dynamics, and each call returns a # single *sampled* (s_next, reward, done) -- exactly what a real environment # hands you. That wall is the definition of "model-free." def step(s, a): # -> (s_next, reward, done) if s == 10: raise ValueError( "state 10 is terminal; no action should be applied to it" ) if a == Action.THRUST: if s == 9: return 10, 1.0, True return s + 1, 0.0, False # JUMP if random.random() <= JUMP_SUCCESS_PROBABILITY: if s >= 7: # +3 lands on or past 10 -> win return 10, 1.0, True return s + 3, 0.0, False return max(0, s - 2), 0.0, False # misfire: slide back 2, floor at 0 # Ground truth from Lesson 1 value iteration -- used ONLY for scoring. The # learner never looks at it; that would be peeking through the wall. TRUE_V = [ 0.5219919679553231, 0.5482046378586254, 0.5706240497071444, 0.6186571735660003, 0.6671991520804588, 0.7087165778019958, 0.7801916910708641, 0.8551379656365434, 0.9, 1.0, 0.0, ] EPISODES = 50_000 WINDOW = 2_000 # rolling window for the steady-state bias/noise estimate EPSILON = 0.10 # exploration probability def neural_prediction() -> tuple[np.array, list[int], list[deque]]: """ The full write-up and stub land when this session runs. The shape of the assignment: A tiny network from scratch. One hidden layer, implemented as plain matrix multiplies — forward pass, a squared-error loss against the TD target, and the backward pass computed by hand. Gradient-check it. Compare your analytic gradients to numerical finite differences, so you know the backprop is right before trusting it. Re-learn Asteroid Hop's V with the network instead of the 11-entry table, and confirm it reproduces the Lesson 1 values — same toy, known ground truth, now via function approximation. Predictions first, as always — including what the deadly triad (bootstrapping + function approximation + off-policy data) might do to convergence. """ # θ ← θ + α·[ r + γ·max(Vθ(s′, a) for all a in s') − (Vθ(s, a)]·∇θ Vθ(s, a) # intialize values to between 0 and 1 θ = np.linspace(-1, 1, 8) # correspends to a_0, a_1, a_2, a_3 # W1 = np.random.randn(3, 4) # (in, out) # W2 = np.random.rand(4, 2) def get_features(s, a): s_n = s / 10 # a.value == 0 for THRUST, 1 for JUMP return np.array( [ 1, s_n, s_n**2, s_n**3, a.value, a.value * s_n, a.value * s_n**2, a.value * s_n**3, ] ) def get_action(s, θ): q_max = -999999 for a in [Action.THRUST, Action.JUMP]: q = get_Q(s, a, θ) if q > q_max: best_action = a q_max = q if random.random() < EPSILON: # explore: pick the other action if best_action == Action.THRUST: return Action.JUMP else: return Action.THRUST else: return best_action def get_best_q(s, θ): return max(get_Q(s, Action.THRUST, θ), get_Q(s, Action.JUMP, θ)) def get_Q(s, a, θ): features = get_features(s, a) return features @ θ def get_gradient(θ, s, a) -> np.array: # normalize s so that steps don't explode return get_features(s, a) visits = [0] * 11 actions_chosen = defaultdict(int) def get_deque(): return deque(maxlen=WINDOW) recent = defaultdict(get_deque) for _ in range(EPISODES): s = 0 while True: a = get_action(s, θ) visits[s] += 1 actions_chosen[(s, a)] += 1 s_next, reward, done = step(s, a) # ∇θ Vθ(s) == grad # ∇θ Vθ(s) means "gradient with respect to theta" grad = get_gradient(θ, s, a) # θ ← θ + α·[ r + γ·Vθ(s′) − Vθ(s) ]·∇θ Vθ(s) θ = ( θ + ALPHA * ( reward + GAMMA * (0 if done else get_best_q(s_next, θ)) - get_Q(s, a, θ) ) * grad ) recent[s].append(get_best_q(s, θ) - TRUE_V[s]) s = s_next if done: break V = [get_best_q(s, θ) for s in range(11)] return V, visits, recent def report(V, visits, recent): """Print learned V beside ground truth, with per-state bias/noise and the worst-fit state. `recent[s]` holds the last WINDOW signed errors at s: its mean is the steady-state bias, its stdev the noise floor. """ print( f"{'s':>2} {'visits':>8} {'V_learned':>10} {'V_true':>8} " f"{'bias':>8} {'noise':>8}" ) worst_s, worst_err = None, -1.0 for s in range(10): bias = statistics.mean(recent[s]) if recent[s] else float("nan") noise = statistics.stdev(recent[s]) if len(recent[s]) > 1 else 0.0 err = abs(V[s] - TRUE_V[s]) if err > worst_err: worst_s, worst_err = s, err print( f"{s:>2} {visits[s]:>8} {V[s]:>10.3f} {TRUE_V[s]:>8.3f} " f"{bias:>+8.3f} {noise:>8.3f}" ) print( f"\nworst-fit state: {worst_s} (|error| = {worst_err:.3f}, " f"{visits[worst_s]} visits)" ) if __name__ == "__main__": random.seed(0) V, visits, recent = neural_prediction() report(V, visits, recent) # ============================================================================ # BONUS (Lesson 3.2) — turn this into a real two-layer neural network # ============================================================================ # # PROMPT: # The version above is *linear* function approximation — V_θ(s) = θ·φ(s), # which is just one layer (and the hand-built cubic features do all the # work). Make it a genuine two-layer net: one hidden layer with a # nonlinearity, so the network learns its OWN features instead of you # picking s, s², s³ by hand. Same Asteroid Hop, same TD target, same δ — # only ∇θ V_θ(s) changes (now it comes from backprop). Gradient-check the # backward pass against finite differences before trusting it. # # CHEAT SHEET — neural networks in NumPy (scalar-output value net): # # # --- params (shapes) --- # W1 = np.random.randn(n_in, n_hid) * 0.1 # b1, W2 likewise # b1 = np.zeros(n_hid) # bias = per-neuron additive offset # W2 = np.random.randn(n_hid) * 0.1 # output is scalar -> 1-D # b2 = 0.0 # # # --- forward --- # z = x @ W1 + b1 # bias just adds; lets each neuron shift its threshold # h = np.tanh(z) # nonlinearity (the whole reason for a hidden layer) # V = h @ W2 + b2 # scalar # # # --- backward: grads of V w.r.t. each param (chain rule) --- # dV_db2 = 1.0 # dV_dW2 = h # V = h·W2 -> ∂/∂W2 = h # dV_dz = W2 * (1 - h**2) # through tanh: d tanh = 1 - tanh² # dV_db1 = dV_dz # bias grad = the incoming delta (∂(·+b)/∂b = 1) # dV_dW1 = np.outer(x, dV_dz) # ∂(x·W1)/∂W1 = outer(input, delta) # # # --- semi-gradient TD update: θ ← θ + α·δ·∇θV --- # W2 += ALPHA * δ * dV_dW2; b2 += ALPHA * δ * dV_db2 # W1 += ALPHA * δ * dV_dW1; b1 += ALPHA * δ * dV_db1 # # Three things to anchor: # - BIAS is a learnable constant added after the matmul. Its gradient is # always just the delta flowing into that layer (∂(stuff + b)/∂b = 1), so # dV_db = dV_dz. # - BACKPROP is the chain rule applied right-to-left: start with ∂V/∂V = 1, # push it back through each op, multiplying by that op's local derivative # (W2 for the matmul, 1−h² for tanh). # - Same δ as before — backprop only changes the ∇θV part; the TD error out # front is unchanged. # # Web write-up: web/templates/lesson_3_bonus.html (/lessons/3/bonus)