Artificial Intelligence: A Conceptual Learner's Series
Part 8: Reinforcement learning
Supervised learning needs the right answer for every example. Reinforcement learning needs only a score, often delayed, and the agent must work out for itself which actions earned it.
Concept 1: Learning from reward
In one line: In reinforcement learning, an agent learns what to do by trying actions and receiving rewards or penalties, gradually discovering which behavior pays off over time.
Example: You're training a dog to fetch. You can't explain the rules in words. The dog tries things: runs off, sniffs the grass, eventually brings the ball back. You give a treat. Over many tries, it learns the sequence that earns treats. The hard part is that the treat comes at the end, so the dog must figure out which of its many earlier actions actually mattered.
Formally:
At each time step the agent observes a state, takes an action and receives a reward and a new state from the environment.
The goal is to maximize the return: the total (usually discounted) reward over time, not just the next reward.
A policy maps states to actions. A value function estimates the expected return from a state (V) or from taking an action in a state (Q).
The setting is formalized as a Markov decision process whose transitions and rewards the agent does not know in advance.
Credit assignment: deciding which earlier actions deserve credit for a delayed reward.
Connections: This is the MDP from Part 5, Concept 3, solved by experience instead of by calculation from a known model.
Watch out:
Reward is not the goal itself. Agents optimize the reward you wrote, loopholes included (Part 1, Concept 8).
Sparse rewards are hard. If reward comes only on rare success, random exploration may almost never find it.
Concept 2: Exploration versus exploitation
In one line: An agent must balance using what it already knows works with trying new things that might work better, because it can't learn about options it never tries.
Example: You've moved to a new town and found a pretty good taco place. Do you keep going there, or try the other twelve restaurants? If you never explore, you might miss a great spot down the street. If you always explore, you eat a lot of bad meals. A sensible approach: mostly go to your favorite, occasionally try somewhere new, and try new places more often early on, when you know little.
Formally:
Exploitation: choose the action currently believed best. Exploration: choose an action to learn more about it.
The multi-armed bandit problem isolates this trade-off: several slot machines with unknown payout rates, one pull at a time.
ε-greedy: pick the best-known action most of the time, and a random action with small probability ε.
Upper confidence bound (UCB): prefer actions whose value could plausibly be high, adding a bonus for uncertainty that shrinks as an action is tried more.
Thompson sampling: sample a plausible value for each action from your current belief and pick the best sample.
Regret measures how much reward was lost compared with always choosing the best action.
Connections: Exploration is the value of information (Part 5, Concept 2) in practice: trying an option is worth it when what you'd learn could change future choices.
Watch out:
Never exploring locks in early luck. A first good experience can hide a much better option.
Exploration has real costs. In medicine or finance, "trying something random" may be unacceptable, so safe exploration is a research area of its own.
Concept 3: Learning values from experience
In one line: An agent can learn how good each situation is by comparing its prediction with what actually happened a moment later and correcting the difference, without waiting until the end.
Example: You drive home from work and normally expect a 30-minute trip. Five minutes in, you hit a traffic jam and revise your estimate to 45 minutes. You don't wait until you arrive to update your sense of how long "leaving at 5 p.m." takes; you adjust right away based on your new, better-informed guess. Learning from one guess to the next is the key idea.
Formally:
Monte Carlo methods update value estimates using the actual total return after an episode ends.
Temporal-difference (TD) learning updates after each step, nudging the estimate toward the reward received plus the estimated value of the next state. This is called bootstrapping: learning a guess from a guess.
Q-learning learns action values directly:
In words: move Q(s, a) a fraction α toward the reward plus the discounted value of the best next action. The bracketed term is the TD error: how surprised the agent was.
Q-learning is off-policy: it learns about the best policy even while behaving exploratorily. SARSA is the on-policy counterpart.
Connections: The Q-learning update is a sampled version of the Bellman equation (Part 5, Concept 3), with real experience in place of a known transition model.
Watch out:
Bootstrapping can be unstable. Learning guesses from guesses, especially with function approximation, can make values spiral out of control.
Tables don't scale. Storing a value for every state is impossible for large problems, which motivates Concept 5.
Concept 4: Learning policies directly
In one line: Instead of learning how good each action is and then picking the best, an agent can directly adjust its behavior, doing more of whatever led to high reward and less of whatever led to low reward.
Example: A beginner learning to shoot free throws doesn't compute the value of every possible arm angle. After each shot, they make small adjustments: that one went in, so do more of that motion; that one clanked off the rim, so do less. Over hundreds of shots, the motion itself improves. A coach watching and saying "that was better than your average" helps them learn faster than the make-or-miss result alone.
Formally:
Policy-based methods represent the policy directly with parameters θ (for example, a neural network outputting action probabilities) and improve θ by gradient ascent on expected return.
Policy gradient (the REINFORCE algorithm is the simplest form) increases the probability of actions in proportion to the return that followed them.
A baseline, such as the average return, reduces the noise of these updates: reinforce actions that did better than expected.
Actor–critic methods combine both approaches: the actor is the policy; the critic learns a value function and tells the actor how much better or worse each action was than expected.
Policy methods handle continuous actions (like steering angles) and stochastic policies naturally. Popular modern algorithms include PPO.
Connections: The critic is TD learning (Concept 3); the actor uses gradient ascent like the training methods in Part 7, Concept 2.
Watch out:
High variance. Raw policy gradients are noisy and need many samples; baselines and critics are essential in practice.
Big updates can wreck a good policy. Methods like PPO deliberately limit how far each update moves the policy.
Concept 5: Deep and model-based reinforcement learning
In one line: Combining reinforcement learning with deep neural networks lets agents handle raw, high-dimensional inputs like pixels, and learning a model of the world lets them plan ahead instead of learning everything by trial and error.
Example: An agent learns to play classic video games from the screen pixels and the score alone, with no rules explained. A deep network looks at the screen and estimates the value of each joystick move. Separately, a board-game agent learns a model of how moves change the board, so it can mentally simulate thousands of continuations before moving, like a chess player thinking ahead, combined with learned intuition about which positions are promising.
Formally:
Function approximation replaces value tables with a learned function, often a neural network, that generalizes across similar states.
Deep Q-networks (DQN) stabilized this with experience replay (training on a shuffled memory of past transitions) and a slowly updated target network.
Model-based RL learns a transition model and uses it to plan or to generate simulated experience. It is usually far more sample-efficient than model-free RL.
Systems like AlphaZero combine a learned policy-and-value network with Monte Carlo tree search (Part 2, Concept 5), learning entirely through self-play.
Reinforcement learning from human feedback (RLHF) trains a reward model from human preference judgments and uses it to fine-tune language models.
Connections: This combines Part 7's deep networks with the value and policy methods above, and brings in search from Part 2.
Watch out:
Sample hunger. Model-free deep RL can need millions of trials, fine in a simulator and impractical for a physical robot.
Simulation-to-reality gaps. Policies learned in simulation often fail on real hardware because the simulator differs in small ways.
Retention kit
Answer from memory, then check. Review at about 1 day, 3 days, 1 week, 2 weeks and 1 month.
What is the return, and why is credit assignment hard?
Describe ε-greedy and UCB. Why does never exploring cause problems?
Write the Q-learning update and explain the TD error in words.
How do policy gradient methods differ from value-based ones? What do the actor and critic each do?
What two tricks made deep Q-networks stable, and why is model-based RL more sample-efficient?
Build exercise (1–2 hours): Implement a 10-armed bandit with random payout rates. Compare ε-greedy (ε = 0.01, 0.1) and UCB over 1,000 pulls, averaged across 500 runs, plotting average reward over time. Then implement tabular Q-learning on the warehouse grid from Part 5 and compare its learned policy with your value-iteration policy.
Python algorithms
A 10-armed bandit comparing pure greed, ε-greedy and UCB (Concept 2), tabular Q-learning on a corridor (Concept 3), and REINFORCE with a baseline (Concept 4). Needs Python 3 and NumPy.
import numpy as np
# 1. Multi-armed bandit: epsilon-greedy vs UCB
def run_bandit(strategy, true_means, pulls=1000, eps=0.1, seed=0):
rng = np.random.default_rng(seed)
k = len(true_means)
counts, values, total = np.zeros(k), np.zeros(k), 0.0
for t in range(1, pulls + 1):
if strategy == "eps" and rng.random() < eps:
arm = rng.integers(k) # explore
elif strategy == "ucb":
if (counts == 0).any():
arm = int(np.argmin(counts)) # try each arm once
else:
arm = int(np.argmax(values + np.sqrt(2 * np.log(t) / counts)))
else:
arm = int(np.argmax(values)) # exploit
r = rng.normal(true_means[arm], 1)
counts[arm] += 1
values[arm] += (r - values[arm]) / counts[arm] # running average
total += r
return total / pulls
# 2. Tabular Q-learning on a corridor: start at 0, reward +1 at the right end
def q_learning(n=6, episodes=500, alpha=0.1, gamma=0.9, eps=0.1, seed=0):
rng = np.random.default_rng(seed)
Q = np.zeros((n, 2)) # actions: 0 left, 1 right
for _ in range(episodes):
s = 0
while s != n - 1:
a = rng.integers(2) if rng.random() < eps or Q[s, 0] == Q[s, 1] else int(np.argmax(Q[s]))
s2 = max(0, s - 1) if a == 0 else s + 1
r = 1.0 if s2 == n - 1 else 0.0
target = r + gamma * Q[s2].max() * (s2 != n - 1)
Q[s, a] += alpha * (target - Q[s, a]) # TD error drives the update
s = s2
return Q
# 3. REINFORCE (policy gradient) with a baseline on a 3-armed bandit
def reinforce(true_means=(0.2, 0.5, 0.9), steps=3000, lr=0.1, seed=0):
rng = np.random.default_rng(seed)
theta, baseline = np.zeros(3), 0.0
for _ in range(steps):
probs = np.exp(theta) / np.exp(theta).sum() # softmax policy
a = rng.choice(3, p=probs)
r = rng.normal(true_means[a], 0.5)
grad = -probs; grad[a] += 1 # gradient of log pi(a)
theta += lr * (r - baseline) * grad # better than expected -> more likely
baseline += 0.01 * (r - baseline)
return np.exp(theta) / np.exp(theta).sum()
if __name__ == "__main__":
means = np.random.default_rng(42).normal(0, 1, 10)
for name, kw in [("greedy", dict(strategy="greedy")), ("eps 0.01", dict(strategy="eps", eps=0.01)),
("eps 0.1", dict(strategy="eps", eps=0.1)), ("UCB", dict(strategy="ucb"))]:
avg = np.mean([run_bandit(true_means=means, seed=s, **kw) for s in range(100)])
print(f"{name:9s} average reward: {avg:.3f} (best arm: {means.max():.3f})")
Q = q_learning()
print("Learned policy (R = right):", "".join("R" if q[1] > q[0] else "L" for q in Q[:-1]))
print("REINFORCE action probabilities:", np.round(reinforce(), 3))Output when run:
greedy average reward: 0.612 (best arm: 0.941)
eps 0.01 average reward: 0.690 (best arm: 0.941)
eps 0.1 average reward: 0.733 (best arm: 0.941)
UCB average reward: 0.836 (best arm: 0.941)
Learned policy (R = right): RRRRR
REINFORCE action probabilities: [0.001 0.002 0.996]Pure greed locks onto whichever arm looked good early; a little exploration helps, and UCB's uncertainty bonus helps most. Q-learning discovers that moving right everywhere reaches the reward, and REINFORCE shifts nearly all probability to the best arm.
Try it:
Raise
pullsto 10,000 and see which strategy gets closest to the best arm's 0.941.Remove the baseline from
reinforce(userinstead ofr - baseline) and compare how noisy learning becomes across seeds.