Machine Learning Full Course · Episode 55. Every code sample below was run with Python 3.13 and NumPy 2.5.3; the output shown is the real output. The banner order rates and the robot's lane are made up for teaching.
The big idea: sometimes nobody can tell the model the right answer; it can only try an action and get a reward. Learning which actions bring the most reward by trying them is reinforcement learning (RL). With three banners and unknown order rates (a multi-armed bandit), pure greedy choosing gets stuck on a wrong banner in 180 of 200 simulated weeks (118.9 orders vs 240 possible). Mixing in a little random exploration (epsilon-greedy, ε = 0.1) lifts it to 207 orders. When actions change what happens next (a delivery robot on a lane), we add states, episodes, the return and the discount factor γ, write the problem as a Markov decision process (MDP), and learn Q-values with Q-learning: the robot learns to walk five cells to the +10 door (values 6.56, 7.29, 8.1, 9.0, 10.0), unless it never explores, or is too impatient (γ = 0.5).
Sources: C. J. C. H. Watkins and P. Dayan, "Technical Note: Q-Learning", Machine Learning 8, 279-292 (1992), which proves that Q-learning converges to the optimal action values with probability 1, provided all actions are repeatedly sampled in all states and the values are stored in a table (record); R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, second edition, MIT Press, 2018 (publisher listing).
Words you need first
- Supervised learning (Episode 1): learning from examples that come with the right answer, the label: house → price, email → spam or not.
- Probability (Episode 9): a number from 0 to 1 for how likely something is; 0.12 = 12 out of 100.
- Expected value / expectation (Episode 10): the long-run average of a random quantity: an order rate of 0.12 over 2,000 visitors gives about 240 orders.
- Learning rate (Episode 8): how big a step you take each time you update a number towards a target.
- argmax: the position of the biggest value:
np.argmax([0.1, 0.4, 0.2])is 1. - Simulation: a program that imitates a real process with random numbers, so we can repeat an experiment hundreds of times.
Learning from rewards, not labels
Ravi learning to ride a cycle has no table of correct handlebar angles. He tries; a fall is a bad score, staying up is a good score; he keeps what worked.
- Reward: a number that says how good the result of an action was (fall = −1, smooth ride = +1, an order = 1, no order = 0).
- Reinforcement learning (RL): learning which actions bring the most reward, by trying actions and observing rewards, with no labels.
- The difference from supervised learning: we only find out how good the action we took was, never what the best action would have been.
Multi-armed bandits: Meera's three banners
Meera's tiffin app has three home-page banners (thali, biryani and dosa offers). 2,000 visitors a week; each sees one banner; the only feedback is "ordered (1) or not (0)".
- An old slot machine was nicknamed a one-armed bandit: pull the arm, maybe win.
- Multi-armed bandit: a row of arms, each paying out with an unknown probability. Each arm is an action (a banner); the reward is 1 if the visitor orders. Goal: the most total reward while still learning.
- In our simulation the true order rates are 5%, 8% and 12%; banner 2 is best, but the app cannot see these numbers.
The obvious attempt: greedy
Show each banner once, then always show the banner with the best order rate so far.
import numpy as np; rng = np.random.default_rng(55)
rates = [0.05, 0.08, 0.12] # true order rate of each banner (hidden from the app)
def greedy(visitors=2000):
shown, orders = np.zeros(3), np.zeros(3)
for t in range(visitors):
if t < 3: a = t # show each banner once
else: a = np.argmax(orders / shown) # then always the best so far
shown[a] += 1; orders[a] += rng.random() < rates[a]
return orders.sum(), np.argmax(shown)
runs = [greedy() for _ in range(200)] # 200 simulated weeks
print("average orders per 2000 visitors:", np.mean([o for o, _ in runs]).round(1))
print("best possible (always banner 2) :", 2000 * 0.12)
print("weeks stuck on the WRONG banner :", sum(b != 2 for _, b in runs), "of 200")
Output:
average orders per 2000 visitors: 118.9
best possible (always banner 2) : 240.0
weeks stuck on the WRONG banner : 180 of 200
Half the possible orders, and stuck on a wrong banner in 180 of 200 weeks.
Why it failed: with order rates near 10%, one visitor per banner usually gives 0 orders for all three; the estimates are noise. np.argmax of three zeros picks banner 0, and greedy never looks at the other banners again, so it never discovers its mistake.
Exploration vs exploitation
- Exploitation: choosing the action that looks best right now (your usual dhaba).
- Exploration: trying another action to learn more about it (the new restaurant down the road).
- Exploration-exploitation trade-off: exploit only and you can be stuck for ever; explore only and you waste visitors on bad choices. Good strategies mix both.
Epsilon-greedy
- ε (epsilon): a small probability such as 0.1.
- Epsilon-greedy: with probability ε pick a random action (explore); otherwise pick the action with the best estimate so far (exploit). Like rolling a dice every Friday: a 1 means try a new place.
- Estimate of an arm = rewards so far ÷ times shown. ε = 0 is pure greedy; ε = 1 is pure random.
import numpy as np; rng = np.random.default_rng(55)
rates = [0.05, 0.08, 0.12] # true order rate of each banner (hidden from the app)
def play(eps, visitors=2000):
shown, orders = np.ones(3), np.zeros(3) # pretend each banner was shown once
for t in range(visitors):
if rng.random() < eps: a = rng.integers(3) # explore: a random banner
else: a = np.argmax(orders / shown) # exploit: the best estimate so far
shown[a] += 1; orders[a] += rng.random() < rates[a]
return orders.sum(), np.argmax(orders / shown)
for eps in [0.0, 0.01, 0.1, 0.3, 1.0]:
runs = [play(eps) for _ in range(200)]
print(f"epsilon {eps:4}: orders {np.mean([o for o, _ in runs]):6.1f} found banner 2 in",
sum(b == 2 for _, b in runs), "of 200 weeks")
Output:
epsilon 0.0: orders 100.0 found banner 2 in 0 of 200 weeks
epsilon 0.01: orders 150.8 found banner 2 in 105 of 200 weeks
epsilon 0.1: orders 207.0 found banner 2 in 179 of 200 weeks
epsilon 0.3: orders 210.0 found banner 2 in 197 of 200 weeks
epsilon 1.0: orders 167.2 found banner 2 in 199 of 200 weeks
| ε | Orders (of 240 possible) | Found the best banner | Reading |
|---|---|---|---|
| 0 | 100.0 | 0 of 200 | stuck for ever |
| 0.01 | 150.8 | 105 of 200 | a little exploration already helps a lot |
| 0.1 | 207.0 | 179 of 200 | good balance |
| 0.3 | 210.0 | 197 of 200 | about the same |
| 1.0 | 167.2 | 199 of 200 | knows the best banner but keeps showing bad ones |
(We start each banner's count at 1 shown, 0 orders, so the first division is never 0/0.)
The delivery robot: when actions change the future
A robot stands in cell 1 of a lane of seven cells (0-6). Cell 0 is a chai stall worth +1, one step away. Cell 6 is the customer's door worth +10, five steps away. Every other cell gives 0. Unlike the banners, each move changes where the robot is next, and the big reward arrives only at the end, so a step to the right earns nothing by itself.
The words of RL
| Term | Meaning | In the lane |
|---|---|---|
| Agent | the learner and decision maker | the robot |
| Environment | everything the agent acts on; it replies with a new state and a reward | the lane |
| State | the situation right now | which cell (0-6) |
| Action | one of the choices the agent can make | left (0) or right (1) |
| Reward | the number the environment returns after an action | +1, +10 or 0 |
| Episode | one full run from the start to an end state | start in cell 1 until the stall or the door |
| Policy | the agent's rule: state → action | "in every cell, go right" |
The loop: agent sees the state → picks an action → environment returns the next state and a reward → repeat until the episode ends.
Return and the discount factor
- Return G: the sum of the rewards from now to the end of the episode.
- Discount factor γ (gamma), 0 ≤ γ ≤ 1: later rewards are multiplied by γ once per step of delay:
G = r1 + γ·r2 + γ²·r3 + γ³·r4 + ...
- Like money: ₹100 today is worth more than ₹100 next year. Small γ = an impatient agent; γ near 1 = plans far ahead.
# Robot on a lane of 7 cells: 0 = chai stall (+1), 6 = customer's door (+10). Robot starts in cell 1.
for gamma in [0.9, 0.5]:
left = 1 # 1 step left, reward +1 right away
right = sum(gamma**t * r for t, r in enumerate([0, 0, 0, 0, 10])) # 5 steps right, +10 at the end
print(f"gamma {gamma}: return going left = {left}, going right = {right:.3f}")
Output:
gamma 0.9: return going left = 1, going right = 6.561
gamma 0.5: return going left = 1, going right = 0.625
Going right is worth 10 × 0.9⁴ = 6.561 with γ = 0.9, but only 10 × 0.5⁴ = 0.625 with γ = 0.5: the discount factor changes which plan is best.
Markov decision process (MDP)
An MDP is the standard way to write an RL problem: a set of states, a set of actions, the rewards, the transitions (which state an action leads to, possibly with chance involved) and the discount factor γ.
- Markov property: the next state and reward depend only on the current state and action, not on the history. In chess, the board in front of you is enough; how the pieces got there doesn't matter.
- A bandit is an MDP with a single state.
Value function and Q-values
- Value function V(s): the return you can expect starting from state s, if you act well afterwards. Cell 5 (one step from +10): V = 10. Cell 4: 10 × 0.9 = 9.
- Q-value Q(s, a): the expected return if you take action a in state s, then act well. In cell 1 with γ = 0.9: Q(1, left) = 1, Q(1, right) = 6.56.
- V(s) = the biggest Q(s, a) over the actions. If you know Q, the best policy is easy: in each state take the action with the largest Q.
Q-learning from scratch
- Q-table: one number per (state, action) pair, starting at 0.
- Each step: in state s pick action a with epsilon-greedy; observe reward r and next state s'; then
text
target = r + γ · max Q(s', ·) (just r if the episode ended)
Q(s, a) ← Q(s, a) + α · (target − Q(s, a))
- α (alpha): the learning rate, the fraction of the gap closed each time.
- The best future is borrowed from the table itself, so the +10 at the door flows backwards cell by cell over many episodes.
- Watkins and Dayan (1992) proved this reaches the optimal Q-values provided every action keeps being tried in every state, which is exactly why exploration matters.
import random; random.seed(55); N, START = 7, 1 # lane cells 0..6; the robot starts in cell 1
def step(s, a): # the environment. a = 0 (left) or 1 (right)
s2 = s - 1 if a == 0 else s + 1
if s2 == 0: return s2, 1, True # chai stall: +1, episode over
if s2 == N - 1: return s2, 10, True # customer's door: +10, episode over
return s2, 0, False # empty road: 0
def q_learning(gamma, eps, episodes=1000, alpha=0.5):
Q = [[0.0, 0.0] for _ in range(N)] # the Q-table: Q[state][action], starts at zero
for ep in range(episodes):
s, done = START, False
while not done:
best = 0 if Q[s][0] > Q[s][1] else 1 if Q[s][1] > Q[s][0] else random.randrange(2) # ties: coin flip
a = random.randrange(2) if random.random() < eps else best # epsilon-greedy
s2, r, done = step(s, a); target = r if done else r + gamma * max(Q[s2]) # reward + future
Q[s][a] += alpha * (target - Q[s][a]); s = s2 # nudge Q to target
return Q
for gamma, eps in [(0.9, 0.0), (0.9, 0.5), (0.5, 0.5)]:
Q = q_learning(gamma, eps); pol = " ".join("<>"[Q[s][1] > Q[s][0]] for s in range(1, N - 1))
print(f"gamma {gamma} eps {eps}: {pol} V:", " ".join(f"{max(Q[s]):.2f}" for s in range(1, N - 1)))
Output:
gamma 0.9 eps 0.0: < < < < < V: 1.00 0.00 0.00 0.00 0.00
gamma 0.9 eps 0.5: > > > > > V: 6.56 7.29 8.10 9.00 10.00
gamma 0.5 eps 0.5: < > > > > V: 1.00 1.25 2.50 5.00 10.00
- ε = 0: its first trips go left (a coin flip on ties, but cell 1 is next to the stall), Q(1, left) becomes 1, and it never tries right again. The door's value stays 0: it has never seen it.
- ε = 0.5: it learns "right" everywhere, with V = 10 × 0.9^(steps left): 6.56, 7.29, 8.1, 9.0, 10.0.
- γ = 0.5: in cell 1 the door is worth only 0.625 < 1, so it takes the chai; from cell 2 onwards (V = 1.25, 2.5, 5, 10) it goes right.
- Off-policy learning: Q-learning learns the values of the best policy even while it behaves randomly half the time.
- With huge state spaces (a game screen), the table is replaced by a neural network that predicts Q-values: the next episodes build neural networks.
Where RL fits
- Bandits: choosing banners, offers, notification times, A/B tests that shift traffic towards the winner.
- Full RL: games, robot control, any sequence of decisions with a reward at the end.
- Warnings: RL needs a huge number of tries, so it is usually trained in a simulator; and the reward must be designed carefully, because the agent optimises exactly the number you give it, including shortcuts you did not intend.
Common mistakes
| Mistake | Exact message / symptom | Why | Fix |
|---|---|---|---|
| Pure greedy (ε = 0) | weeks stuck on the WRONG banner : 180 of 200 |
never explores after a noisy start | epsilon-greedy |
| ε = 1 for ever | epsilon 1.0: orders 167.2 vs 207.0 at ε = 0.1 |
never cashes in on what it knows | small ε (0.05-0.2) or decay it |
| Dividing by zero shows | RuntimeWarning: invalid value encountered in divide (0/0 = nan) |
an arm never shown | start counts at 1, or show each arm once |
| Judging a move by its immediate reward | every step to the right scores 0 | rewards arrive later | use returns and Q-values |
| γ too small | gamma 0.5 eps 0.5: < > > > > |
the future barely counts | γ near 1 to plan ahead |
| Q-learning without exploration | gamma 0.9 eps 0.0: < < < < < |
never sees the +10 | ε > 0 |
| Careless reward | the agent finds a loophole | it maximises exactly that number | design and test the reward |
Mini project: decaying epsilon
Explore a lot at the start, when you know nothing, and less later: ε = 1 / (1 + t / 100).
import numpy as np; rng = np.random.default_rng(55)
rates = [0.05, 0.08, 0.12]
def play(schedule, visitors=2000):
shown, orders = np.ones(3), np.zeros(3)
for t in range(visitors):
eps = schedule(t)
a = rng.integers(3) if rng.random() < eps else np.argmax(orders / shown)
shown[a] += 1; orders[a] += rng.random() < rates[a]
return orders.sum(), np.argmax(orders / shown)
for name, sch in [("fixed 0.1", lambda t: 0.1), ("decaying 1/(1 + t/100)", lambda t: 1 / (1 + t / 100))]:
runs = [play(sch) for _ in range(200)]
print(f"{name:24}: orders {np.mean([o for o, _ in runs]):6.1f} found banner 2 in {sum(b == 2 for _, b in runs)} of 200")
Output:
fixed 0.1 : orders 203.7 found banner 2 in 172 of 200
decaying 1/(1 + t/100) : orders 217.5 found banner 2 in 186 of 200
The decaying schedule explores heavily at first and then mostly exploits: more orders (217.5 vs 203.7) and the best banner found more often.
Practice
1. Bandit with ε = 0.05 and ε = 0.2.
Solution
Same program as the epsilon-greedy one, with for eps in [0.05, 0.2]:.
Output:
epsilon 0.05: orders 195.1 found banner 2 in 169 of 200 weeks
epsilon 0.2: orders 208.7 found banner 2 in 196 of 200 weeks
Both beat greedy by far; 0.2 explores enough to find banner 2 in 196 of 200 weeks.
2. Lane: add a cost of −1 for every step.
Solution
import random; random.seed(55); N, START = 7, 1
def make_step(left_r=1, door_r=10, cost=0):
def step(s, a):
s2 = s - 1 if a == 0 else s + 1
if s2 == 0: return s2, left_r + cost, True
if s2 == N - 1: return s2, door_r + cost, True
return s2, cost, False
return step
def q_learning(step, gamma, eps, episodes=1000, alpha=0.5):
Q = [[0.0, 0.0] for _ in range(N)]
for ep in range(episodes):
s, done = START, False
while not done:
best = 0 if Q[s][0] > Q[s][1] else 1 if Q[s][1] > Q[s][0] else random.randrange(2)
a = random.randrange(2) if random.random() < eps else best
s2, r, done = step(s, a); target = r if done else r + gamma * max(Q[s2])
Q[s][a] += alpha * (target - Q[s][a]); s = s2
return Q
def show(label, Q):
pol = " ".join("<>"[Q[s][1] > Q[s][0]] for s in range(1, N - 1))
print(f"{label}: policy {pol} V(s) {[round(max(Q[s]), 2) for s in range(1, N - 1)]}")
show("cost -1 per step, gamma 0.9", q_learning(make_step(cost=-1), 0.9, 0.5))
show("cost -1 per step, gamma 1.0", q_learning(make_step(cost=-1), 1.0, 0.5))
Output:
cost -1 per step, gamma 0.9: policy > > > > > V(s) [2.47, 3.85, 5.39, 7.1, 9.0]
cost -1 per step, gamma 1.0: policy > > > > > V(s) [5.0, 6.0, 7.0, 8.0, 9.0]
With γ = 1 the values are simply 10 minus the steps taken (5 steps from cell 1: 10 − 5 = 5). A step cost makes the agent prefer short routes even without discounting.
3. Lane: make the door worth only +3. Which way now (γ = 0.9)?
Solution
Using the make_step, q_learning and show functions from Practice 2:
show("door +3, gamma 0.9", q_learning(make_step(door_r=3), 0.9, 0.5))
print("going right from cell 1 is worth 3 * 0.9**4 =", round(3 * 0.9**4, 3))
Output:
door +3, gamma 0.9: policy > > > > > V(s) [1.97, 2.19, 2.43, 2.7, 3.0]
going right from cell 1 is worth 3 * 0.9**4 = 1.968
Still right: 3 × 0.9⁴ = 1.968 is more than the chai's 1.
4. Q-learning with α = 0.1 vs α = 0.9, after 50 and 1,000 episodes.
Solution
for alpha in [0.1, 0.9]:
for episodes in [50, 1000]:
show(f"alpha {alpha}, {episodes:4} episodes", q_learning(make_step(), 0.9, 0.5, episodes=episodes, alpha=alpha))
Output:
alpha 0.1, 50 episodes: policy < < < < < V(s) [0.99, 0.68, 0.13, 0.01, 0.0]
alpha 0.1, 1000 episodes: policy > > > > > V(s) [6.56, 7.29, 8.1, 9.0, 10.0]
alpha 0.9, 50 episodes: policy < < < < < V(s) [1.0, 0.9, 0.81, 0.73, 0.65]
alpha 0.9, 1000 episodes: policy > > > > > V(s) [6.56, 7.29, 8.1, 9.0, 10.0]
After only 50 episodes neither has found the door's value yet (the robot starts next to the stall). With enough episodes both reach the same answer, because this lane is deterministic; in a noisy environment a large α makes the values jump around.
Quick quiz
An episode gives rewards 0, 0, 8 with γ = 0.5. What is the return?
Answer
2. G = 0 + 0.5 × 0 + 0.5² × 8 = 0.25 × 8 = 2.
More questions:
- Why is a banner choice a bandit and the robot lane a full RL problem?
Answer
A banner choice doesn't change the next visitor (one state); the robot's moves change its next state, and rewards are delayed. - What does ε = 0 do in epsilon-greedy?
Answer
Pure greedy: it never explores and can be stuck on a wrong action for ever. - With γ = 0.9, what is V(cell 3) in the lane?
Answer
Three steps to the door: 10 × 0.9² = 8.1 (the move into the door earns the 10). - What is the Markov property?
Answer
The next state and reward depend only on the current state and action, not on the history. - In the Q-learning update, what is the target?
Answer
The reward just received plus γ times the best Q-value in the next state (just the reward if the episode ended).
Interview questions
- How is RL different from supervised learning? No labels: the agent acts, receives rewards, and must find which actions maximise long-term reward; feedback is only for the action taken and may be delayed.
- Explain exploration vs exploitation. Exploit uses the best-known action; explore tries others to improve estimates. Too little exploration locks in mistakes; too much wastes reward. Epsilon-greedy, decaying ε and upper-confidence methods balance them.
- What is an MDP? States, actions, transition probabilities, rewards and a discount factor, with the Markov property.
- What is the discount factor for? It weights future rewards (γᵗ), keeps infinite sums finite, and sets how far ahead the agent plans.
- V(s) vs Q(s, a)? V is the expected return from a state; Q is the expected return from taking a given action in that state; V(s) = max over a of Q(s, a) for the optimal policy.
- Write the Q-learning update. Q(s,a) ← Q(s,a) + α [r + γ max Q(s',·) − Q(s,a)]. It is off-policy: it learns the greedy policy's values while following an exploratory one.
- When does tabular Q-learning break down? When there are too many states to store or visit; then a function approximator (for example a neural network) predicts Q.
Glossary
| Term | Meaning (plain words + example) |
|---|---|
| Reinforcement learning (RL) | Learning which actions bring the most reward by trying them; no labels (Ravi learning to cycle) |
| Reward | A number the environment gives after an action: +10 at the door, 1 for an order |
| Agent | The learner that makes decisions: the delivery robot |
| Environment | Everything the agent acts on; returns the next state and a reward: the lane |
| State | The current situation: the robot is in cell 3 |
| Action | A choice the agent can make: left or right; show banner 2 |
| Episode | One full run from start to an end state: cell 1 until the stall or the door |
| Policy | The agent's rule from state to action: "in every cell go right" |
| Return (G) | Sum of (discounted) rewards from now to the end of the episode |
| Discount factor (γ) | Number from 0 to 1 that shrinks later rewards: with 0.9, a +10 four steps later counts 6.561 |
| Markov decision process (MDP) | States, actions, rewards, transitions and γ, where the next step depends only on the current state and action |
| Transition | Which state an action leads to (possibly random) |
| Markov property | The future depends only on the present state, not on the history (a chess position) |
| Value function V(s) | Expected return from state s when acting well: V(cell 5) = 10 |
| Q-value Q(s, a) | Expected return after taking action a in state s: Q(cell 1, right) = 6.56 |
| Q-table | A table with one Q-value per (state, action) pair |
| Q-learning | Learn Q by moving each Q(s, a) towards r + γ max Q(s', ·) |
| Learning rate (α) | Fraction of the gap to the target closed in each update: 0.5 |
| Off-policy | Learning the best policy's values while behaving differently (randomly part of the time) |
| Exploration | Trying an action to learn about it: a new restaurant |
| Exploitation | Using the action that currently looks best: your usual dhaba |
| Exploration-exploitation trade-off | The balance between the two |
| Epsilon-greedy | Random action with probability ε, best-known action otherwise |
| Epsilon (ε) | The small exploration probability, e.g. 0.1 |
| Greedy | Always picking the current best estimate (ε = 0) |
| Multi-armed bandit | Choosing repeatedly among actions with unknown payout chances; a one-state RL problem |
| Arm | One action of a bandit: one banner |
| Decaying epsilon | ε that shrinks over time: explore early, exploit later |
| Simulator | A program that imitates the environment so an agent can practise safely |
Summary
- RL learns from rewards, not labels: try, score, adjust.
- Bandits: greedy got stuck (118.9 of 240 orders); epsilon-greedy with ε = 0.1 got 207.0. Explore and exploit.
- Agent, environment, state, action, reward, episode, policy are the parts of every RL problem, written as an MDP.
- Return with a discount factor γ: a +10 five steps away is 6.561 at γ = 0.9 but 0.625 at γ = 0.5.
- V(s) and Q(s, a) measure how good states and actions are; Q-learning learns Q from its own tries and found the door (6.56 → 10.0), as long as it explored.
Next episode: Neural networks from scratch 1: the perceptron, artificial neurons, activation functions, layers and the forward pass.