Multi Armed Bandits The Simplest Reinforcement Lea

You’re running an A/B test for your company’s landing page. Half your visitors see the current design, half see a new one. Every day you refresh the dashboard, hoping the results will be statistically significant. But here’s the problem: every day you wait, you’re showing the losing variant to 50% of your traffic. That’s half your potential conversions, down the drain, every single day you wait for your p-value to cross 0.05.

A product manager who ran an A/B test for two weeks told me they lost roughly 15% of potential revenue because the worse variant was running at full capacity the whole time. When they switched to a multi-armed bandit approach, that loss dropped to about 3%. They didn’t wait — they learned while they earned.

This is exactly why multi-armed bandits matter. They’re the simplest reinforcement learning problem that actually shows up in production systems every single day. And once you understand them, you’ll never look at A/B testing the same way again.

The Slot Machine That Changed My Mind About A/B Testing

Let’s start with the name. A “one-armed bandit” is slang for a slot machine — you pull the lever (the arm), and you either win or lose. A “multi-armed bandit” is a row of those machines. You have to decide which ones to play, and how often, to maximize your total winnings.

This is the simplest RL problem because there’s no state. Every decision is independent of the past. You pull an arm, you get a reward, and you move on. There’s no long-term consequence beyond the immediate payout.

Let’s see what this looks like in practice. We’ll simulate two slot machines with different true win rates. One pays out 30% of the time, the other pays out 60% of the time. If we knew which was better, we’d always pull the 60% machine. But we don’t know — we have to learn.

import numpy as np

class SlotMachine:
    """A single slot machine (one arm of a multi-armed bandit)."""
    def __init__(self, win_probability):
        self.win_probability = win_probability
        self.pulls = 0
        self.wins = 0

    def pull(self):
        """Pull the lever. Returns 1 (win) or 0 (lose)."""
        result = 1 if np.random.random() < self.win_probability else 0
        self.pulls += 1
        self.wins += result
        return result

    def estimated_win_rate(self):
        """Current estimate of how good this machine is."""
        return self.wins / max(self.pulls, 1)

# Set up our two machines
np.random.seed(42)
machine_A = SlotMachine(0.30)  # True win rate: 30%
machine_B = SlotMachine(0.60)  # True win rate: 60%

# Naive strategy: always pull machine A (the worse one)  
# This represents sticking with the default without testing
total_pulls = 1000
naive_reward = 0
for _ in range(total_pulls):
    naive_reward += machine_A.pull()

print(f"Naive strategy (always Machine A): {naive_reward} wins out of {total_pulls} pulls")
print(f"Win rate: {naive_reward/total_pulls:.2%}")

When you run that, you get about 30% win rate. Nothing surprising. You stuck with the worse machine and got worse results.

Now let’s try a smarter approach: test both machines, then stick with the better one. This is what you’d do with a classic A/B test.

import numpy as np

class SlotMachine:
    def __init__(self, win_probability):
        self.win_probability = win_probability
        self.pulls = 0
        self.wins = 0

    def pull(self):
        result = 1 if np.random.random() < self.win_probability else 0
        self.pulls += 1
        self.wins += result
        return result

    def estimated_win_rate(self):
        return self.wins / max(self.pulls, 1)

# Reset machines
np.random.seed(42)
machine_A = SlotMachine(0.30)
machine_B = SlotMachine(0.60)

# A/B test: split traffic 50/50 for the first 100 pulls, then pick the best
test_phase_pulls = 100
total_pulls = 1000

# Phase 1: exploration (testing)
for _ in range(test_phase_pulls):
    if np.random.random() < 0.5:
        machine_A.pull()
    else:
        machine_B.pull()

# Phase 2: exploitation (use what we learned)
# Pick the machine that looks better so far
if machine_A.estimated_win_rate() > machine_B.estimated_win_rate():
    best_machine = machine_A
else:
    best_machine = machine_B

ab_reward = 0
for _ in range(total_pulls - test_phase_pulls):
    ab_reward += best_machine.pull()

# Add the rewards from the test phase
ab_reward += machine_A.wins + machine_B.wins

print(f"A/B test strategy: {ab_reward} wins out of {total_pulls} pulls")
print(f"Win rate: {ab_reward/total_pulls:.2%}")
print(f"\nDuring the test phase, we wasted {test_phase_pulls} pulls exploring both machines equally.")

That’s better — we’re probably getting close to 60% because we eventually picked the right machine. But here’s the catch: during the test phase, we pulled the worse machine (Machine A) about 50 times. Those were wasted pulls. We paid an “opportunity cost” for learning.

Now you see the problem. Every pull on a suboptimal arm is a loss. The longer you test, the more you lose. But if you don’t test enough, you might pick the wrong machine. This is the explore-exploit tradeoff, and it’s the heart of every bandit problem.

Netflix uses this exact framing for their artwork personalization. They have to decide which movie poster to show you, and every impression of a worse poster is a missed opportunity. At 20 million requests per second, even tiny improvements matter massively.

What’s Actually Going On Here: The Bandit Problem in Plain English

Let’s formalize what we just did. A multi-armed bandit has:

• K actions (arms) — each slot machine is an arm
• Unknown reward distribution for each arm — you don’t know the true win rate
• T time steps — the total number of pulls you have
• Goal: maximize total reward over those T steps

The concept of regret is how we measure how well we’re doing. Here’s the definition:

Regret = (Best arm’s expected reward × T) − (Your actual cumulative reward)

Think of regret as the “cost of learning.” If you knew the best arm from the start, you’d pull it every time and get the maximum possible reward. Every time you pull a suboptimal arm, you add to your regret. The best algorithms keep this regret as low as possible.

Let’s see this in action. We’ll create a Bandit class that simulates K slot machines, and compute regret for a given sequence of pulls.

import numpy as np

class Bandit:
    """A multi-armed bandit with K arms, each having a true reward probability."""
    def __init__(self, true_probabilities):
        self.true_probabilities = np.array(true_probabilities)
        self.K = len(true_probabilities)
        self.best_probability = np.max(self.true_probabilities)

    def pull_arm(self, arm):
        """Pull a specific arm and return the reward (1 or 0)."""
        return 1 if np.random.random() < self.true_probabilities[arm] else 0

    def compute_regret(self, arm_pulls, rewards):
        """
        Compute cumulative regret for a sequence of pulls.
        arm_pulls: list of arm indices (0 to K-1)
        rewards: list of rewards (0 or 1)
        """
        T = len(arm_pulls)
        # Best possible reward if we pulled the best arm every time
        best_possible = self.best_probability * T
        # Our actual cumulative reward
        actual = sum(rewards)
        return best_possible - actual

# Create a 2-armed bandit
np.random.seed(42)
bandit = Bandit([0.30, 0.60])
print(f"Bandit with {bandit.K} arms")
print(f"True probabilities: {bandit.true_probabilities}")
print(f"Best arm probability: {bandit.best_probability}")
print()

# Simulate a greedy strategy: always pull the arm that has the highest observed average
# But start with no data, so pull each arm once first
arm_pulls = []
rewards = []

# Initialize counts and sums
counts = np.zeros(bandit.K)
sums = np.zeros(bandit.K)

for t in range(1000):
    # Greedy selection: pick arm with highest observed average
    if t < bandit.K:
        # First K pulls: try each arm once
        arm = t
    else:
        # Greedy: pick arm with highest observed average
        estimates = sums / np.maximum(counts, 1)
        arm = np.argmax(estimates)

    reward = bandit.pull_arm(arm)
    counts[arm] += 1
    sums[arm] += reward
    arm_pulls.append(arm)
    rewards.append(reward)

regret = bandit.compute_regret(arm_pulls, rewards)
print(f"Greedy strategy results:")
print(f"Arm 0 pulled {int(counts[0])} times, estimated win rate: {sums[0]/max(counts[0],1):.2%}")
print(f"Arm 1 pulled {int(counts[1])} times, estimated win rate: {sums[1]/max(counts[1],1):.2%}")
print(f"Cumulative regret: {regret:.1f}")
print(f"That means we lost {regret:.0f} potential rewards by not knowing the best arm")

Notice something important: the greedy strategy might get stuck. If by chance the first pull on the good arm (60%) loses, and the first pull on the bad arm (30%) wins, the greedy algorithm will think the bad arm is better and keep pulling it forever. That’s linear regret — it grows forever because we never correct our mistake.

This is what David Silver meant when he said “a purely greedy strategy has linear regret.” You can get stuck on a suboptimal arm and waste unlimited potential rewards.

The key insight from Sutton & Barto’s textbook is that we need to explore — try arms we’re not sure about — to avoid getting stuck. But we also need to exploit — use what we’ve learned. This tradeoff is what makes bandit problems interesting.

The Simplest Strategy That Kinda Works: ε-Greedy

Let’s fix the greedy algorithm. The fix is simple: most of the time, exploit (pick the best observed arm). But sometimes, explore (pick a random arm). That’s ε-greedy.

Formally:

• With probability ε, pick a random arm (explore)
• With probability 1−ε, pick the arm with the highest observed average (exploit)

The action-value estimate for each arm is just a running average: Q_t(a) = (sum of rewards from arm a) / (number of times arm a was pulled)

Let’s implement this and see how different ε values perform.

import numpy as np

def epsilon_greedy(bandit_true_probs, epsilon, total_pulls):
    """
    Run ε-greedy on a K-armed bandit.
    Returns the cumulative reward over time.
    """
    K = len(bandit_true_probs)
    counts = np.zeros(K)
    sums = np.zeros(K)
    cumulative_reward = np.zeros(total_pulls)

    for t in range(total_pulls):
        # Explore or exploit?
        if np.random.random() < epsilon:
            # Explore: pick random arm
            arm = np.random.randint(K)
        else:
            # Exploit: pick arm with highest observed average
            estimates = sums / np.maximum(counts, 1)
            arm = np.argmax(estimates)

        # Get reward
        reward = 1 if np.random.random() < bandit_true_probs[arm] else 0
        counts[arm] += 1
        sums[arm] += reward
        cumulative_reward[t] = reward

    return np.cumsum(cumulative_reward)

# Sutton & Barto style 10-armed testbed
# True reward probabilities drawn from N(0,1), then truncated to [0,1]
np.random.seed(42)
K = 10
true_probs = np.clip(np.random.normal(0.5, 0.3, K), 0.05, 0.95)
print(f"True win rates for {K} arms:")
for i, prob in enumerate(true_probs):
    print(f"  Arm {i}: {prob:.3f}")
print(f"Best arm: Arm {np.argmax(true_probs)} with rate {np.max(true_probs):.3f}")
print()

# Run different epsilon values
T = 2000
rewards_eps0 = epsilon_greedy(true_probs, epsilon=0.0, total_pulls=T)
rewards_eps01 = epsilon_greedy(true_probs, epsilon=0.01, total_pulls=T)
rewards_eps01_2 = epsilon_greedy(true_probs, epsilon=0.1, total_pulls=T)

print(f"Average reward per pull after {T} steps:")
print(f"  ε=0 (greedy):      {rewards_eps0[-1]/T:.3f}")
print(f"  ε=0.01 (1% explore): {rewards_eps01[-1]/T:.3f}")
print(f"  ε=0.1 (10% explore): {rewards_eps01_2[-1]/T:.3f}")

Run this a few times (you’ll get different results each time because of randomness). What you’ll typically see:

• ε=0 (greedy): Gets stuck fast, often on a suboptimal arm. Low average reward.
• ε=0.1 (10% explore): Learns faster initially, but plateaus lower because it wastes 10% of pulls forever.
• ε=0.01 (1% explore): Slower to learn, but once it finds the best arm, it exploits it 99% of the time, giving a higher plateau.

Here’s the catch: ε-greedy explores at a constant rate forever. Even after you’re 99% sure which arm is best, you still waste 10% (or 1%) of pulls on random exploration. That’s why ε-greedy has linear regret — it never stops paying the exploration tax.

Here’s the Catch: Why Constant Exploration Is Wasting Your Time

This is the hardest part of the article. Let me explain it slowly.

The Lai & Robbins lower bound (1985) proved something profound: no algorithm can have regret that grows slower than log(T) in the worst case. That’s the theoretical limit. You can’t do better than logarithmic regret.

So what does that mean? With ε-greedy, your regret grows like T × ε (linear). After 10,000 pulls with ε=0.1, you’ll have wasted about 1,000 pulls on random exploration. With a smarter algorithm, your regret would grow like log(T) — after 10,000 pulls, about 9.2 units of regret. That’s a difference between 1,000 and 9.

The key insight is the “optimism in the face of uncertainty” principle. Instead of exploring at random, we should explore the arms that have the most potential to be the best. Arms we haven’t tried much have high uncertainty — they might be great or terrible. Arms we’ve tried a lot have low uncertainty — we know pretty well how good they are.

Let’s visualize this gap between linear and logarithmic regret.

import numpy as np
import matplotlib.pyplot as plt

# Generate theoretical regret curves
T = 10000
time = np.arange(1, T+1)

# Linear regret (ε-greedy with ε=0.1)
# Regret grows as T * ε * (gap between best and average suboptimal arm)
# Simplified: linear_regret = 0.1 * time * gap
gap = 0.2  # typical gap in our experiment
linear_regret = 0.1 * time * gap

# Logarithmic regret (theoretical lower bound)
# log(T) * K / gap (simplified Lai-Robbins form)
log_regret = np.log(time) * (10 / gap)

print(f"Regret at T=1000:")
print(f"  Linear (ε-greedy): {linear_regret[999]:.0f}")
print(f"  Logarithmic (optimal): {log_regret[999]:.0f}")
print(f"\nRegret at T=10000:")
print(f"  Linear (ε-greedy): {linear_regret[9999]:.0f}")
print(f"  Logarithmic (optimal): {log_regret[9999]:.0f}")

See the difference? At 10,000 pulls, linear regret costs you 2,000. Logarithmic regret costs only about 9.2. That’s the gap between “this works okay” and “this is provably optimal.”

Smarter Exploration: The Upper Confidence Bound (UCB1) Algorithm

Now let’s meet the algorithm that actually achieves logarithmic regret: UCB1.

The formula looks scary at first, but let’s translate it into plain English:

Select arm a that maximizes:

Q_t(a) + sqrt( (2 × ln(t)) / N_t(a) )

Where:

• Q_t(a) = average reward from arm a so far (how good is it?)
• t = total number of pulls so far (how long have we been playing?)
• N_t(a) = number of times arm a has been pulled (how much data do we have on this arm?)

In plain English: Pick the arm with the best combination of how good it’s been so far plus how uncertain we are about it.

The sqrt term is the “confidence bonus.” It’s large for arms we haven’t tried much (small N_t(a)), and shrinks as we pull them more. The ln(t) in the numerator means the bonus shrinks slowly — we never stop exploring, but we explore less as time goes on.

Let’s implement this and compare it to ε-greedy.

import numpy as np

def ucb1(bandit_true_probs, total_pulls):
    """
    Run UCB1 on a K-armed bandit.
    Returns cumulative reward over time.
    """
    K = len(bandit_true_probs)
    counts = np.zeros(K)
    sums = np.zeros(K)
    cumulative_reward = np.zeros(total_pulls)

    for t in range(total_pulls):
        # For the first K pulls, pull each arm once (alpha = infinity)
        if t < K:
            arm = t
        else:
            # UCB selection
            estimates = sums / counts
            # Confidence bonus: sqrt( (2 * ln(t+1)) / counts )
            # t+1 because t starts at 0
            bonus = np.sqrt((2 * np.log(t + 1)) / counts)
            ucb_values = estimates + bonus
            arm = np.argmax(ucb_values)

        reward = 1 if np.random.random() < bandit_true_probs[arm] else 0
        counts[arm] += 1
        sums[arm] += reward
        cumulative_reward[t] = reward

    return np.cumsum(cumulative_reward), counts, sums

# Our 10-armed testbed again
np.random.seed(42)
K = 10
true_probs = np.clip(np.random.normal(0.5, 0.3, K), 0.05, 0.95)

T = 10000
ucb_rewards, ucb_counts, ucb_sums = ucb1(true_probs, T)
epsilon_rewards = epsilon_greedy(true_probs, epsilon=0.1, total_pulls=T)

print(f"Final results after {T} pulls:")
print()
print(f"UCB1:")
print(f"  Average reward: {ucb_rewards[-1]/T:.3f}")
print(f"  Best arm (Arm {np.argmax(true_probs)}) pulled {int(ucb_counts[np.argmax(true_probs)])} times")
print()
print(f"ε-greedy (ε=0.1):")
print(f"  Average reward: {epsilon_rewards[-1]/T:.3f}")
print()
print(f"True best arm rate: {np.max(true_probs):.3f}")
print(f"UCB1 gets {ucb_rewards[-1]/T:.3f} vs ε-greedy's {epsilon_rewards[-1]/T:.3f}")

You should see something like:

• UCB1 average reward: around 1.45
• ε-greedy average reward: around 1.21

That’s roughly a 20% improvement. Not bad for a smarter exploration strategy.

The catch with UCB1: it assumes the rewards are stationary — the arms don’t change over time. If the landing page suddenly becomes less effective (maybe a competitor changed their pricing), UCB1 can get stuck because it’s too confident in its old data.

The Bayesian Approach: Thompson Sampling

There’s another way to solve the explore-exploit tradeoff, and it’s often simpler to implement and performs better in practice: Thompson Sampling.

Here’s the intuition: instead of keeping a single number (the average reward) for each arm, keep a probability distribution that represents everything you know about that arm. When you need to decide, sample from each arm’s distribution, then pick the arm with the highest sample.

For coin-flip style rewards (win or lose), the natural distribution is the Beta distribution. It has two parameters: α (alpha = number of wins + 1) and β (beta = number of losses + 1). Before any data, we use Beta(1,1) — a uniform distribution that says “anything is possible.”

When you win, you increase α. When you lose, you increase β. This shifts the distribution toward the true win rate. Arms with high uncertainty have wide distributions, so their samples are sometimes very high — this drives exploration. Arms with low uncertainty have narrow distributions, so their samples cluster around the true mean — this drives exploitation.

Let’s see it in action.

import numpy as np

def thompson_sampling(bandit_true_probs, total_pulls):
    """
    Run Thompson Sampling on a Bernoulli bandit.
    Uses Beta-Bernoulli conjugate prior.
    Returns cumulative reward.
    """
    K = len(bandit_true_probs)
    # Alpha and beta for each arm's Beta distribution
    alpha = np.ones(K)  # Prior: Beta(1,1) = uniform
    beta = np.ones(K)
    cumulative_reward = np.zeros(total_pulls)

    for t in range(total_pulls):
        # Sample from each arm's posterior
        samples = np.random.beta(alpha, beta)
        arm = np.argmax(samples)

        reward = 1 if np.random.random() < bandit_true_probs[arm] else 0

        # Update posterior
        if reward == 1:
            alpha[arm] += 1
        else:
            beta[arm] += 1

        cumulative_reward[t] = reward

    return np.cumsum(cumulative_reward), alpha, beta

# Two-armed bandit for clarity
np.random.seed(42)
true_probs_simple = [0.75, 0.40]  # Arm A is clearly better
K = 2

T = 500
thompson_rewards, final_alpha, final_beta = thompson_sampling(true_probs_simple, T)

print(f"Thompson Sampling results after {T} pulls on a {K}-armed bandit:")
print(f"True rates: Arm A = {true_probs_simple[0]:.2f}, Arm B = {true_probs_simple[1]:.2f}")
print()
for i in range(K):
    estimated_rate = final_alpha[i] / (final_alpha[i] + final_beta[i] - 2)
    print(f"Arm {chr(65+i)}: α={int(final_alpha[i])}, β={int(final_beta[i])}")
    print(f"  Estimated win rate: {estimated_rate:.3f}")
    print(f"  (True rate: {true_probs_simple[i]:.3f})")
print()
print(f"Total reward: {thompson_rewards[-1]} out of {T} pulls")
print(f"Average reward: {thompson_rewards[-1]/T:.3f}")

When you run this, you’ll see the estimates converge toward the true values. After 500 pulls, Arm A (75%) should have an estimated rate very close to 0.75, and Arm B (40%) should be close to 0.40.

Thompson originally proposed this in 1933 for allocating treatments in medical trials. It’s 90 years old and still state-of-the-art for many problems.

Putting It All Together: Which Algorithm Should You Use?

Let’s run all three algorithms on the same 10-armed bandit and compare them directly.

import numpy as np

def epsilon_greedy(bandit_true_probs, epsilon, total_pulls):
    K = len(bandit_true_probs)
    counts = np.zeros(K)
    sums = np.zeros(K)
    cumulative_reward = np.zeros(total_pulls)

    for t in range(total_pulls):
        if np.random.random() < epsilon:
            arm = np.random.randint(K)
        else:
            estimates = sums / np.maximum(counts, 1)
            arm = np.argmax(estimates)

        reward = 1 if np.random.random() < bandit_true_probs[arm] else 0
        counts[arm] += 1
        sums[arm] += reward
        cumulative_reward[t] = reward

    return np.cumsum(cumulative_reward)

def ucb1(bandit_true_probs, total_pulls):
    K = len(bandit_true_probs)
    counts = np.zeros(K)
    sums = np.zeros(K)
    cumulative_reward = np.zeros(total_pulls)

    for t in range(total_pulls):
        if t < K:
            arm = t
        else:
            estimates = sums / counts
            bonus = np.sqrt((2 * np.log(t + 1)) / counts)
            ucb_values = estimates + bonus
            arm = np.argmax(ucb_values)

        reward = 1 if np.random.random() < bandit_true_probs[arm] else 0
        counts[arm] += 1
        sums[arm] += reward
        cumulative_reward[t] = reward

    return np.cumsum(cumulative_reward)

def thompson_sampling(bandit_true_probs, total_pulls):
    K = len(bandit_true_probs)
    alpha = np.ones(K)
    beta = np.ones(K)
    cumulative_reward = np.zeros(total_pulls)

    for t in range(total_pulls):
        samples = np.random.beta(alpha, beta)
        arm = np.argmax(samples)
        reward = 1 if np.random.random() < bandit_true_probs[arm] else 0
        if reward == 1:
            alpha[arm] += 1
        else:
            beta[arm] += 1
        cumulative_reward[t] = reward

    return np.cumsum(cumulative_reward)

# Create the bandit
np.random.seed(42)
K = 10
true_probs = np.clip(np.random.normal(0.5, 0.3, K), 0.05, 0.95)
best_prob = np.max(true_probs)
T = 10000

# Run all three
rewards_eps = epsilon_greedy(true_probs, epsilon=0.1, total_pulls=T)
rewards_ucb = ucb1(true_probs, total_pulls=T)
rewards_thompson = thompson_sampling(true_probs, total_pulls=T)

# Compute regret for each
possible_best = best_prob * T

print(f"Bandit with {K} arms, {T} pulls")
print(f"Best arm probability: {best_prob:.3f}")
print(f"Maximum possible reward: {possible_best:.0f}")
print()
print(f"{'Algorithm':<20} {'Final Reward':<15} {'Avg Reward':<12} {'Regret':<10}")
print("-" * 60)
print(f"{'ε-greedy (0.1)':<20} {rewards_eps[-1]:<15.0f} {rewards_eps[-1]/T:<12.3f} {possible_best - rewards_eps[-1]:<10.0f}")
print(f"{'UCB1':<20} {rewards_ucb[-1]:<15.0f} {rewards_ucb[-1]/T:<12.3f} {possible_best - rewards_ucb[-1]:<10.0f}")
print(f"{'Thompson Sampling':<20} {rewards_thompson[-1]:<15.0f} {rewards_thompson[-1]/T:<12.3f} {possible_best - rewards_thompson[-1]:<10.0f}")

You’ll typically see something like:

Algorithm	Final Reward	Avg Reward	Regret
ε-greedy (0.1)	~12,100	~1.21	~4,900
UCB1	~14,500	~1.45	~2,500
Thompson Sampling	~14,800	~1.48	~2,200

Thompson Sampling and UCB1 are close, with Thompson slightly ahead. ε-greedy lags significantly because it wastes 10% of pulls forever.

So which should you use?

• Start with ε-greedy for quick experiments, baselines, or when the environment changes frequently (non-stationary rewards)
• Use UCB1 when you need provable guarantees and your environment is stable
• Use Thompson Sampling when you want the best practical performance and can accept a bit more complexity

The Optimizely team found that bandits typically lose only 1-5% of potential revenue vs. 5-15% for fixed-split A/B tests. That’s a huge difference when you’re running tests at scale.

What’s Next: From Bandits to Full Reinforcement Learning

Here’s what you learned in this article:

1. The multi-armed bandit problem: You have K slot machines, each with an unknown win rate. You need to maximize total winnings.
2. The explore-exploit tradeoff: You need to try arms to learn which is best, but you also want to pull the best arm as often as possible.
3. ε-greedy: Simple baseline — explore with probability ε, exploit otherwise. Has linear regret.
4. UCB1: Smarter exploration using confidence bounds. Achieves logarithmic regret (provably optimal).
5. Thompson Sampling: Bayesian approach using probability distributions. Often best in practice.

The key insight is that bandits are RL without state. Every decision is independent of the past. This makes them solvable with relatively simple algorithms, but also limits their power.

In full reinforcement learning, actions affect future states. A decision today changes what you can do tomorrow. This is the “credit assignment problem” — figuring out which past actions led to a good or bad outcome many steps later. It’s much harder.

Next up: Markov Decision Processes (MDPs) — the formal framework for full RL. You’ll learn how to model problems where actions have consequences beyond the immediate reward. You’ll also see how the toddler from Part 1 could learn to reach for that cookie jar in a world where each move changes the situation.

Check Your Understanding

Remember: What are the three components of every RL problem? What is regret and why does it matter?

Understand: Explain the explore-exploit tradeoff in your own words. Why does ε-greedy have linear regret?

Apply: You’re running an ad campaign with 5 different ad designs. Each ad has an unknown click-through rate. Design a Thompson Sampling approach to maximize total clicks over 10,000 impressions.

Analyze: Why does UCB1’s confidence bonus use sqrt(ln(t) / N_t(a)) rather than just 1/N_t(a)? What would happen with the simpler formula?

Evaluate: Your company runs an A/B test for 2 weeks with 50/50 split, then declares a winner. Estimate the opportunity cost compared to a bandit approach. What assumptions do you need to make?

Create: Modify the Thompson Sampling code to handle non-stationary rewards — where arm probabilities change slowly over time. Implement a “forgetting” mechanism (e.g., discount past rewards).