Issue #01: All about Reinforcement Learning(1)

Before you begin reading this post, I originally intended it to be a comprehensive discussion on Reinforcement Learning as a whole. However, during the process, I decided to divide it into multiple posts to explore various RL topics. This will be a bi-weekly series until my next issue/topic, which will focus on optimizers.

The Exploration Dilemma:Should You Order the Usual?

Before an agent can learn to play Go or fly a drone, it must solve a far more fundamental problem — one that Netflix, Spotify, and every rational mind faces every day. This is the Exploration vs. Exploitation trade-off, and it is the central bottleneck of all reinforcement learning.

The Netflix Problem

Imagine you open Netflix on a Friday night. The algorithm could show you Interstellar — a film you've seen twice and love — or a documentary about competitive cheese rolling you've never heard of. What should it do?

An agent that only exploits what it knows will never discover something better. An agent that only explores never benefits from what it has already learned. Each movie is an arm of a slot machine. Netflix pulls one arm per session. The "reward" is whether you watch for more than 10 minutes.

This is the Multi-Armed Bandit problem — named after a row of slot machines (one-armed bandits) in a casino. The goal: maximise total reward across T pulls, without knowing which machine pays best upfront.

Strategy 1 — ε-greedy: Mostly Stick, Sometimes Stray

The simplest approach is brutally practical. Most of the time, pick the arm with the highest estimated reward (greedy/exploit). But with probability ε (epsilon), throw a dart randomly at any arm.

Action = argmax_a Q(a)    with probability 1 - ε

Action = random(A)         with probability ε

Q(a) = estimated mean reward for arm a

Setting ε to 0 is pure greed — exploit forever, discover nothing. ε = 1 is pure chaos — explore randomly, never benefit from knowledge. The sweet spot is typically between 0.05 and 0.20.

THE NETFLIX TRANSLATION

With ε = 0.10, Netflix shows you a safe bet 90% of the time — your proven favourites. For 1 in 10 sessions, it throws in a wildcard you've never interacted with. If you love it, that arm's estimated reward jumps. If you don't, no big loss.

The core flaw of ε-greedy

ε-greedy explores blindly. It allocates the same fraction of pulls to a terrible arm it has sampled 200 times as to a promising arm it has only tried twice. It doesn't know what it doesn't know.

Figure 1 — Arm pull distribution after 1,000 steps. ε-greedy wastes pulls on sub-optimal arms uniformly; UCB concentrates on the best arm while still exploring.

Strategy 2 — UCB: Optimism Under Uncertainty

Upper Confidence Bound is smarter. Instead of randomly deciding when to explore, it bakes uncertainty directly into each arm's score. Arms that haven't been pulled much get a bonus — an optimistic boost that says "maybe you're actually great, and we just haven't seen it yet."

UCB_t(a)  =  Q(a)  +  c · sqrt( ln t / N_t(a) )

Q(a) = estimated reward  ·  N_t(a) = times arm pulled  ·  c = confidence level  ·  t = total pulls

The square-root term is the uncertainty bonus. When N_t(a) is small, the bonus is large — driving exploration. As you pull an arm more, the bonus shrinks — driving exploitation. The log(t) numerator ensures even well-sampled arms get revisited occasionally as time grows.

THE NETFLIX TRANSLATION

A new thriller just dropped. Netflix has only shown it to 50 users. Its mean rating is 7.8/10 — decent but uncertain. UCB adds a "curiosity bonus" based on its low sample count, pushing it above your usual 8.2/10 recommendation. If 10,000 people rate it 9.5/10, great. If it tanks, its UCB score collapses. Exploration was earned, not random.

Figure 2 — UCB score decomposition at t = 50. Purple = estimated Q(a); orange = uncertainty bonus. Under-sampled arms get a large boost, directing exploration purposefully.

Head-to-Head: Regret Over Time

Regret measures the total reward you missed by not always pulling the best arm. A great policy has sub-linear regret — it keeps falling behind the optimal agent, but more and more slowly. UCB achieves logarithmic regret, a theoretical guarantee proven by Lai & Robbins (1985) that ε-greedy cannot match.

Figure 3 — Cumulative regret over 1,000 steps, averaged across 5 random seeds. UCB (green) accumulates regret significantly slower than ε-greedy (purple) or pure greedy (red/dashed).

The effect of epsilon

Too little exploration and you get stuck in local optima. Too much and you waste pulls on arms you've already proven are bad. The chart below shows how optimal arm selection peaks at a moderate ε and then drops off.

Figure 4 — Optimal arm selection rate across epsilon values. Peak performance emerges around ε ≈ 0.05–0.10; beyond that, over-exploration hurts.

Why This Matters for Full RL

In a real RL environment — an Atari game, a robot arm, a stock trading agent — the agent faces this same dilemma at every single timestep, but with a vastly more complex action space and a reward signal that is delayed and noisy.

Deep Q-Networks (DQN), the landmark paper from DeepMind, uses ε-greedy on top of a neural network estimating Q(a) for every action. The network is the Q-function; the ε-greedy wrapper is the exploration policy. Later architectures like Rainbow and PPO use more sophisticated exploration bonuses — but they are all descendants of UCB's core idea: optimism in the face of uncertainty.

Key Takeaways

• ε-greedy is simple and robust, but explores blindly — it treats all unknowns equally

• UCB is principled — it quantifies uncertainty and directs exploration where it is most valuable

• Regret is the right metric: not accuracy, not reward, but opportunity cost over time

• Both strategies live on inside DQN, PPO, and every modern deep RL agent

• Netflix, Spotify, Google Ads — they are all running some variant of this exact algorithm right now

  (The images were generated in matplotlib, and excuse me for LaTex errors. Have a good day!)

Based on Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow, 3rd Ed., Chapter 18  ·  Aurélien Géron  ·  O'Reilly Media