Chapter 122 · Practice Challenges, Solved¶
Five reinforcement-learning exercises on the Chapter 122 GridWorld and ad-bandit, worked in pure numpy.
import numpy as np, pandas as pd, matplotlib.pyplot as plt
import seaborn as sns # seaborn = high-level statistical plots (heatmaps, pairplots, count/bar plots)
from matplotlib.colors import ListedColormap
EM="#4338ca"; DEEP="#3730a3"; LIGHT="#c7d2fe"; INK="#1a2138"; GRID="#e6e9f2"; RED="#ef4444"; AMBER="#d97706"; GREEN="#059669"; BLUE="#2563eb"; PUR="#9333ea"; GREY="#94a3b8"; SLATE="#475569"; ORG="#4338ca"; CYAN="#0891b2"
plt.rcParams.update({"figure.facecolor":"white","axes.facecolor":"white","figure.dpi":110,"font.size":11,
"axes.edgecolor":GRID,"axes.grid":True,"grid.color":GRID,"axes.axisbelow":True,"axes.spines.top":False,
"axes.spines.right":False,"axes.titlesize":12,"axes.titleweight":"bold","legend.frameon":False})
sns.set_style("whitegrid")
BASE="https://raw.githubusercontent.com/johnfisher-ai/Statistics-Data-Science-AI-Visual-Book/main/data/"
rng = np.random.default_rng(7)
GRID = 5; start, goal, trap = (0,0), (4,4), (2,2); walls = {(1,3),(2,3),(3,1)}
MOVES = {0:(-1,0), 1:(0,1), 2:(1,0), 3:(0,-1)}
def step(rc, a):
r,c = rc; dr,dc = MOVES[a]; nr,nc = r+dr, c+dc
if nr<0 or nr>=GRID or nc<0 or nc>=GRID or (nr,nc) in walls: nr,nc = r,c
if (nr,nc)==goal: return (nr,nc), 10.0, True
if (nr,nc)==trap: return (nr,nc), -10.0, True
return (nr,nc), -0.1, False
def run_episode(policy, max_steps=100):
s = start; total = 0.0
for _ in range(max_steps):
a = policy(s); s, r, done = step(s, a); total += r
if done: break
return total
scores = [run_episode(lambda s: rng.integers(4)) for _ in range(200)]
print('random agent average return = %.2f' % np.mean(scores))
random agent average return = -10.47
Solution. A random agent earns a badly negative return, it stumbles into the trap or wastes steps, since it has no notion of which actions are good.
def train(gamma=0.95, episodes=600, eps=0.1, alpha=0.1):
Q = np.zeros((GRID,GRID,4))
for ep in range(episodes):
s = start
for _ in range(100):
a = rng.integers(4) if rng.random()<eps else int(np.argmax(Q[s[0],s[1]]))
s2, r, done = step(s, a)
best_next = 0.0 if done else np.max(Q[s2[0],s2[1]])
Q[s[0],s[1],a] += alpha*(r + gamma*best_next - Q[s[0],s[1],a])
s = s2
if done: break
return Q
Q = train()
greedy = lambda s: int(np.argmax(Q[s[0],s[1]]))
print('trained agent average return = %.2f' % np.mean([run_episode(greedy) for _ in range(200)]))
trained agent average return = 9.30
Solution. After a few hundred episodes the agent reliably reaches the goal for a strongly positive return, learned entirely from rewards, with no labeled examples of correct moves.
names = {0:'up',1:'right',2:'down',3:'left'}
pi = Q.argmax(axis=2)
print('best action at start (0,0):', names[int(pi[0,0])])
print('value at start V(0,0) = %.2f' % Q[0,0].max())
best action at start (0,0): right value at start V(0,0) = 6.38
Solution. The greedy policy points the agent off the start cell along the highest-value route to the goal; the state value V(start) is clearly positive, meaning the agent expects to win from there.
g0 = train(gamma=0.0); g9 = train(gamma=0.95)
gr = lambda Q: (lambda s: int(np.argmax(Q[s[0],s[1]])))
print('gamma=0.00 (myopic) average return = %.2f' % np.mean([run_episode(gr(g0)) for _ in range(200)]))
print('gamma=0.95 (far-sighted) average return = %.2f' % np.mean([run_episode(gr(g9)) for _ in range(200)]))
gamma=0.00 (myopic) average return = -10.00 gamma=0.95 (far-sighted) average return = 9.30
Solution. With gamma=0 the agent only values the immediate reward and cannot 'see' the distant goal through the small step costs, so it struggles; a high gamma lets future reward propagate back, which is what makes long-horizon planning work.
try: ads = pd.read_excel('../../data/reinforcement-learning-primer--bandit.xlsx', sheet_name='Data')
except FileNotFoundError: ads = pd.read_excel(BASE + 'reinforcement-learning-primer--bandit.xlsx', sheet_name='Data')
ctr = ads['true_ctr'].values; K=len(ctr); best=int(np.argmax(ctr)); T=4000
def run(strat):
Q=np.zeros(K); N=np.zeros(K)
for t in range(1,T+1):
a = int(np.argmax(Q)) if strat=='greedy' else (rng.integers(K) if rng.random()<0.1 else int(np.argmax(Q)))
rw = 1.0 if rng.random()<ctr[a] else 0.0; N[a]+=1; Q[a]+=(rw-Q[a])/N[a]
return N[best]/T*100
print('pure greedy -> %.0f%% of traffic to the best ad' % run('greedy'))
print('epsilon-greedy -> %.0f%% of traffic to the best ad' % run('eps'))
pure greedy -> 0% of traffic to the best ad epsilon-greedy -> 90% of traffic to the best ad
Solution. Pure greedy starts with every estimate at zero, keeps showing the first ad and never tries the others, so it never finds the real winner; epsilon-greedy keeps exploring, so it identifies AD2 and concentrates most traffic there. Exploration is not wasted, it is how the agent learns what to exploit.