Multi-Armed Bandits and Exploration Strategies¶

Goal: Understand and implement fundamental exploration strategies (ε-greedy, UCB, Thompson Sampling) in the k-armed bandit setting, the simplest reinforcement learning problem.

Prerequisites: Basic probability and statistics (Bernoulli and Gaussian distributions, expected value, Bayes' rule).

Theory Link: Theory Guide

In [1]:

import random

import matplotlib.pyplot as plt
import numpy as np

%load_ext autoreload
%autoreload 2

SEED = 42
random.seed(SEED)
rng = np.random.default_rng(SEED)

plt.rcParams["figure.dpi"] = 90

import random import matplotlib.pyplot as plt import numpy as np %load_ext autoreload %autoreload 2 SEED = 42 random.seed(SEED) rng = np.random.default_rng(SEED) plt.rcParams["figure.dpi"] = 90

1. Problem Setup — WHY¶

The exploration-exploitation dilemma is the most fundamental challenge in Reinforcement Learning (RL). When an agent acts in an unknown environment, it must balance:

• Exploitation: Choosing the action known to yield the highest reward to maximize immediate payoff.
• Exploration: Choosing unknown or less-tried actions to gather information, potentially finding a better action for the future.

The k-armed bandit is the simplest RL setting because it isolates this dilemma: there is only one state, and the reward is immediate.

Real-world examples:

• A/B Testing: Showing different website versions to see which maximizes click-through rate.
• Ad Placement: Deciding which ad to show a user.
• Clinical Trials: Assigning patients to treatments to maximize recovery rates while identifying the best treatment.

2. Mathematical Core — WHAT¶

The $k$-armed bandit problem: We have $k$ actions (arms). Each action $a \in \{1, \dots, k\}$ has a reward distribution with an unknown expected value, called its action-value $Q(a)$: $$ Q(a) = \mathbb{E}[R | A = a] $$

Our goal is to maximize the expected total reward over $T$ time steps, which is equivalent to minimizing Regret $R_T$. If $\mu^\ast$ is the expected reward of the optimal action, regret is: $$ R_T = T\mu^\ast - \sum_{t=1}^T \mathbb{E}[R_{A_t}] $$

Upper Confidence Bound (UCB): Instead of just using the estimated value $Q_t(a)$, UCB adds an exploration bonus based on how uncertain we are. By Hoeffding's inequality: $$ A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln(t)}{N_t(a)}} \right] $$ where $N_t(a)$ is the number of times arm $a$ was pulled, and $c$ controls exploration.

Thompson Sampling: A Bayesian approach. For Bernoulli rewards, we maintain a Beta posterior distribution for each arm's success probability, parameterized by successes $\alpha_a$ and failures $\beta_a$. We sample a value from each arm's posterior and pick the arm with the highest sample.

3. Solution Method — HOW¶

• $\varepsilon$-greedy: Most of the time ($1-\varepsilon$), we exploit by picking the action with the highest estimated value. With probability $\varepsilon$, we pick a random action uniformly to explore.
• UCB1: Implements "optimism in the face of uncertainty." The bonus term shrinks as we try an action more, naturally shifting from exploration to exploitation.
• Thompson Sampling: We sample from the posterior Beta distribution. Arms we are uncertain about have wide distributions, so they occasionally produce high samples and get explored. As we gather data, the distributions narrow around the true means.

4. Implementation — BUILD¶

Let's implement the environment and agents using only NumPy.

In [2]:

class BanditEnvironment:
    """k-armed bandit with configurable reward distributions."""
    def __init__(self, k=10, dist_type='gaussian', seed=42):
        self.k = k
        self.dist_type = dist_type
        self.rng = np.random.default_rng(seed)
        
        if dist_type == 'gaussian':
            # True means for each arm drawn from standard normal
            self.true_means = self.rng.standard_normal(k)
        elif dist_type == 'bernoulli':
            # True success probabilities uniform between 0.1 and 0.9
            self.true_means = self.rng.uniform(0.1, 0.9, k)
        else:
            raise ValueError("dist_type must be 'gaussian' or 'bernoulli'")
            
        self.optimal_arm = np.argmax(self.true_means)
        self.optimal_value = np.max(self.true_means)
        
    def pull(self, arm):
        if self.dist_type == 'gaussian':
            # Reward is true mean + unit variance noise
            return self.true_means[arm] + self.rng.standard_normal()
        elif self.dist_type == 'bernoulli':
            # Reward is 1 with prob true_means[arm], 0 otherwise
            return 1.0 if self.rng.random() < self.true_means[arm] else 0.0

class BanditEnvironment: """k-armed bandit with configurable reward distributions.""" def __init__(self, k=10, dist_type='gaussian', seed=42): self.k = k self.dist_type = dist_type self.rng = np.random.default_rng(seed) if dist_type == 'gaussian': # True means for each arm drawn from standard normal self.true_means = self.rng.standard_normal(k) elif dist_type == 'bernoulli': # True success probabilities uniform between 0.1 and 0.9 self.true_means = self.rng.uniform(0.1, 0.9, k) else: raise ValueError("dist_type must be 'gaussian' or 'bernoulli'") self.optimal_arm = np.argmax(self.true_means) self.optimal_value = np.max(self.true_means) def pull(self, arm): if self.dist_type == 'gaussian': # Reward is true mean + unit variance noise return self.true_means[arm] + self.rng.standard_normal() elif self.dist_type == 'bernoulli': # Reward is 1 with prob true_means[arm], 0 otherwise return 1.0 if self.rng.random() < self.true_means[arm] else 0.0

In [3]:

class EpsilonGreedyAgent:
    def __init__(self, k, epsilon=0.1):
        self.k = k
        self.epsilon = epsilon
        self.q_estimates = np.zeros(k)
        self.action_counts = np.zeros(k)
        
    def select_action(self, t):
        # Explore
        if rng.random() < self.epsilon:
            return rng.integers(0, self.k)
        # Exploit
        # Break ties randomly to avoid bias towards lower index arms
        return rng.choice(np.flatnonzero(self.q_estimates == self.q_estimates.max()))
        
    def update(self, action, reward):
        self.action_counts[action] += 1
        # Incremental update rule: Q_{n+1} = Q_n + 1/n * (R_n - Q_n)
        alpha = 1.0 / self.action_counts[action]
        self.q_estimates[action] += alpha * (reward - self.q_estimates[action])

class UCBAgent:
    def __init__(self, k, c=2.0):
        self.k = k
        self.c = c
        self.q_estimates = np.zeros(k)
        self.action_counts = np.zeros(k)
        
    def select_action(self, t):
        # Pull each arm at least once initially
        if t < self.k:
            return t
            
        # UCB formula
        exploration_bonus = self.c * np.sqrt(np.log(t) / self.action_counts)
        ucb_values = self.q_estimates + exploration_bonus
        return rng.choice(np.flatnonzero(ucb_values == ucb_values.max()))
        
    def update(self, action, reward):
        self.action_counts[action] += 1
        alpha = 1.0 / self.action_counts[action]
        self.q_estimates[action] += alpha * (reward - self.q_estimates[action])

class ThompsonSamplingAgent:
    def __init__(self, k):
        self.k = k
        # Beta(1,1) prior for each arm (uniform distribution)
        self.alpha = np.ones(k)
        self.beta = np.ones(k)
        
    def select_action(self, t):
        # Sample from the posterior distribution of each arm
        samples = rng.beta(self.alpha, self.beta)
        return np.argmax(samples)
        
    def update(self, action, reward):
        # Update the Beta posterior
        # For Bernoulli rewards, reward is 0 or 1
        if reward == 1.0:
            self.alpha[action] += 1
        else:
            self.beta[action] += 1

class EpsilonGreedyAgent: def __init__(self, k, epsilon=0.1): self.k = k self.epsilon = epsilon self.q_estimates = np.zeros(k) self.action_counts = np.zeros(k) def select_action(self, t): # Explore if rng.random() < self.epsilon: return rng.integers(0, self.k) # Exploit # Break ties randomly to avoid bias towards lower index arms return rng.choice(np.flatnonzero(self.q_estimates == self.q_estimates.max())) def update(self, action, reward): self.action_counts[action] += 1 # Incremental update rule: Q_{n+1} = Q_n + 1/n * (R_n - Q_n) alpha = 1.0 / self.action_counts[action] self.q_estimates[action] += alpha * (reward - self.q_estimates[action]) class UCBAgent: def __init__(self, k, c=2.0): self.k = k self.c = c self.q_estimates = np.zeros(k) self.action_counts = np.zeros(k) def select_action(self, t): # Pull each arm at least once initially if t < self.k: return t # UCB formula exploration_bonus = self.c * np.sqrt(np.log(t) / self.action_counts) ucb_values = self.q_estimates + exploration_bonus return rng.choice(np.flatnonzero(ucb_values == ucb_values.max())) def update(self, action, reward): self.action_counts[action] += 1 alpha = 1.0 / self.action_counts[action] self.q_estimates[action] += alpha * (reward - self.q_estimates[action]) class ThompsonSamplingAgent: def __init__(self, k): self.k = k # Beta(1,1) prior for each arm (uniform distribution) self.alpha = np.ones(k) self.beta = np.ones(k) def select_action(self, t): # Sample from the posterior distribution of each arm samples = rng.beta(self.alpha, self.beta) return np.argmax(samples) def update(self, action, reward): # Update the Beta posterior # For Bernoulli rewards, reward is 0 or 1 if reward == 1.0: self.alpha[action] += 1 else: self.beta[action] += 1

5. Agent Comparison¶

We will run all 3 agents on the same Bernoulli bandit and plot the cumulative regret.

In [4]:

def run_experiment(agent_class, env, steps, **kwargs):
    agent = agent_class(k=env.k, **kwargs)
    
    regret = np.zeros(steps)
    actions = np.zeros(steps, dtype=int)
    cumulative_regret = 0.0
    
    for t in range(steps):
        action = agent.select_action(t)
        reward = env.pull(action)
        agent.update(action, reward)
        
        # Calculate regret for this step
        step_regret = env.optimal_value - env.true_means[action]
        cumulative_regret += step_regret
        regret[t] = cumulative_regret
        actions[t] = action
        
    return regret, actions, agent

def plot_comparison():
    k = 10
    steps = 1000
    runs = 10  # Average over multiple runs to smooth curves
    
    plt.style.use('seaborn-v0_8-whitegrid')
    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(15, 5))
    
    agents = [
        ('Epsilon-Greedy (0.1)', EpsilonGreedyAgent, {'epsilon': 0.1}),
        ('UCB (c=2.0)', UCBAgent, {'c': 2.0}),
        ('Thompson Sampling', ThompsonSamplingAgent, {})
    ]
    
    for name, agent_cls, kwargs in agents:
        avg_regret = np.zeros(steps)
        all_actions = []
        
        for i in range(runs):
            env = BanditEnvironment(k=k, dist_type='bernoulli', seed=SEED+i)
            regret, actions, _ = run_experiment(agent_cls, env, steps, **kwargs)
            avg_regret += regret
            if i == 0:  # Save actions for the first run to plot heatmap
                all_actions = actions
                
        avg_regret /= runs
        ax1.plot(avg_regret, label=name)
        
        # Calculate selection frequency for heatmap (binned over time)
        bins = 20
        chunk_size = steps // bins
        freq = np.zeros((k, bins))
        for b in range(bins):
            chunk = all_actions[b*chunk_size:(b+1)*chunk_size]
            for action in range(k):
                freq[action, b] = np.sum(chunk == action) / chunk_size
                
        if name == 'Thompson Sampling':
            im = ax2.imshow(freq, aspect='auto', cmap='YlOrRd', origin='lower')
            ax2.set_title('Arm Selection Frequency (Thompson Sampling)')
            ax2.set_xlabel('Time (x50 steps)')
            ax2.set_ylabel('Arm Index')
            fig.colorbar(im, ax=ax2)
            
            # Mark optimal arm for the first run
            optimal = env.optimal_arm
            ax2.axhline(optimal, color='green', linestyle='--', label='Optimal Arm')
            ax2.legend()
            
    ax1.set_title('Average Cumulative Regret (Bernoulli Bandit)')
    ax1.set_xlabel('Steps')
    ax1.set_ylabel('Cumulative Regret')
    ax1.legend()
    
    plt.tight_layout()
    plt.show()

plot_comparison()

def run_experiment(agent_class, env, steps, **kwargs): agent = agent_class(k=env.k, **kwargs) regret = np.zeros(steps) actions = np.zeros(steps, dtype=int) cumulative_regret = 0.0 for t in range(steps): action = agent.select_action(t) reward = env.pull(action) agent.update(action, reward) # Calculate regret for this step step_regret = env.optimal_value - env.true_means[action] cumulative_regret += step_regret regret[t] = cumulative_regret actions[t] = action return regret, actions, agent def plot_comparison(): k = 10 steps = 1000 runs = 10 # Average over multiple runs to smooth curves plt.style.use('seaborn-v0_8-whitegrid') fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(15, 5)) agents = [ ('Epsilon-Greedy (0.1)', EpsilonGreedyAgent, {'epsilon': 0.1}), ('UCB (c=2.0)', UCBAgent, {'c': 2.0}), ('Thompson Sampling', ThompsonSamplingAgent, {}) ] for name, agent_cls, kwargs in agents: avg_regret = np.zeros(steps) all_actions = [] for i in range(runs): env = BanditEnvironment(k=k, dist_type='bernoulli', seed=SEED+i) regret, actions, _ = run_experiment(agent_cls, env, steps, **kwargs) avg_regret += regret if i == 0: # Save actions for the first run to plot heatmap all_actions = actions avg_regret /= runs ax1.plot(avg_regret, label=name) # Calculate selection frequency for heatmap (binned over time) bins = 20 chunk_size = steps // bins freq = np.zeros((k, bins)) for b in range(bins): chunk = all_actions[b*chunk_size:(b+1)*chunk_size] for action in range(k): freq[action, b] = np.sum(chunk == action) / chunk_size if name == 'Thompson Sampling': im = ax2.imshow(freq, aspect='auto', cmap='YlOrRd', origin='lower') ax2.set_title('Arm Selection Frequency (Thompson Sampling)') ax2.set_xlabel('Time (x50 steps)') ax2.set_ylabel('Arm Index') fig.colorbar(im, ax=ax2) # Mark optimal arm for the first run optimal = env.optimal_arm ax2.axhline(optimal, color='green', linestyle='--', label='Optimal Arm') ax2.legend() ax1.set_title('Average Cumulative Regret (Bernoulli Bandit)') ax1.set_xlabel('Steps') ax1.set_ylabel('Cumulative Regret') ax1.legend() plt.tight_layout() plt.show() plot_comparison()

6. Experiments and Failures — VERIFY¶

In [5]:

# Experiment 2: Epsilon sensitivity
plt.figure(figsize=(10, 5))
epsilons = [0.01, 0.1, 0.3, 0.5]
steps = 1000
env = BanditEnvironment(k=10, dist_type='gaussian', seed=SEED)

for eps in epsilons:
    regret, _, _ = run_experiment(EpsilonGreedyAgent, env, steps, epsilon=eps)
    plt.plot(regret, label=f'epsilon={eps}')

plt.title('Epsilon-Greedy: Sensitivity to Epsilon Parameter (Gaussian Bandit)')
plt.xlabel('Steps')
plt.ylabel('Cumulative Regret')
plt.legend()
plt.show()

# Experiment 2: Epsilon sensitivity plt.figure(figsize=(10, 5)) epsilons = [0.01, 0.1, 0.3, 0.5] steps = 1000 env = BanditEnvironment(k=10, dist_type='gaussian', seed=SEED) for eps in epsilons: regret, _, _ = run_experiment(EpsilonGreedyAgent, env, steps, epsilon=eps) plt.plot(regret, label=f'epsilon={eps}') plt.title('Epsilon-Greedy: Sensitivity to Epsilon Parameter (Gaussian Bandit)') plt.xlabel('Steps') plt.ylabel('Cumulative Regret') plt.legend() plt.show()

In [6]:

# Experiment 4: UCB c parameter sweep
plt.figure(figsize=(10, 5))
c_values = [0.5, 1.0, 2.0, 5.0]
steps = 1000
env = BanditEnvironment(k=10, dist_type='gaussian', seed=SEED)

for c in c_values:
    regret, _, _ = run_experiment(UCBAgent, env, steps, c=c)
    plt.plot(regret, label=f'c={c}')

plt.title('UCB: Sensitivity to c Parameter (Gaussian Bandit)')
plt.xlabel('Steps')
plt.ylabel('Cumulative Regret')
plt.legend()
plt.show()

# Experiment 4: UCB c parameter sweep plt.figure(figsize=(10, 5)) c_values = [0.5, 1.0, 2.0, 5.0] steps = 1000 env = BanditEnvironment(k=10, dist_type='gaussian', seed=SEED) for c in c_values: regret, _, _ = run_experiment(UCBAgent, env, steps, c=c) plt.plot(regret, label=f'c={c}') plt.title('UCB: Sensitivity to c Parameter (Gaussian Bandit)') plt.xlabel('Steps') plt.ylabel('Cumulative Regret') plt.legend() plt.show()

In [7]:

# Experiment 3: Non-stationary bandit failure
class NonStationaryBandit(BanditEnvironment):
    def __init__(self, k=10, seed=42):
        super().__init__(k=k, dist_type='bernoulli', seed=seed)
        
    def pull_non_stationary(self, arm, t):
        # Swap the best and worst arms at t=500
        if t == 500:
            best_arm = np.argmax(self.true_means)
            worst_arm = np.argmin(self.true_means)
            self.true_means[best_arm], self.true_means[worst_arm] = \
                self.true_means[worst_arm], self.true_means[best_arm]
            self.optimal_arm = worst_arm  # Update optimal arm
            self.optimal_value = np.max(self.true_means)
            
        return 1.0 if self.rng.random() < self.true_means[arm] else 0.0

def run_non_stationary(agent_class, steps=1000, **kwargs):
    env = NonStationaryBandit(k=10, seed=SEED)
    agent = agent_class(k=env.k, **kwargs)
    regret = np.zeros(steps)
    cumulative = 0
    
    for t in range(steps):
        action = agent.select_action(t)
        reward = env.pull_non_stationary(action, t)
        agent.update(action, reward)
        
        cumulative += (env.optimal_value - env.true_means[action])
        regret[t] = cumulative
    return regret

plt.figure(figsize=(10, 5))
plt.plot(run_non_stationary(EpsilonGreedyAgent, epsilon=0.1), label='Epsilon-Greedy')
plt.plot(run_non_stationary(UCBAgent, c=2.0), label='UCB')
plt.plot(run_non_stationary(ThompsonSamplingAgent), label='Thompson Sampling')
plt.axvline(x=500, color='red', linestyle='--', label='Environment Shift')
plt.title('Performance on Non-Stationary Bandit')
plt.xlabel('Steps')
plt.ylabel('Cumulative Regret')
plt.legend()
plt.show()

# Experiment 3: Non-stationary bandit failure class NonStationaryBandit(BanditEnvironment): def __init__(self, k=10, seed=42): super().__init__(k=k, dist_type='bernoulli', seed=seed) def pull_non_stationary(self, arm, t): # Swap the best and worst arms at t=500 if t == 500: best_arm = np.argmax(self.true_means) worst_arm = np.argmin(self.true_means) self.true_means[best_arm], self.true_means[worst_arm] = \ self.true_means[worst_arm], self.true_means[best_arm] self.optimal_arm = worst_arm # Update optimal arm self.optimal_value = np.max(self.true_means) return 1.0 if self.rng.random() < self.true_means[arm] else 0.0 def run_non_stationary(agent_class, steps=1000, **kwargs): env = NonStationaryBandit(k=10, seed=SEED) agent = agent_class(k=env.k, **kwargs) regret = np.zeros(steps) cumulative = 0 for t in range(steps): action = agent.select_action(t) reward = env.pull_non_stationary(action, t) agent.update(action, reward) cumulative += (env.optimal_value - env.true_means[action]) regret[t] = cumulative return regret plt.figure(figsize=(10, 5)) plt.plot(run_non_stationary(EpsilonGreedyAgent, epsilon=0.1), label='Epsilon-Greedy') plt.plot(run_non_stationary(UCBAgent, c=2.0), label='UCB') plt.plot(run_non_stationary(ThompsonSamplingAgent), label='Thompson Sampling') plt.axvline(x=500, color='red', linestyle='--', label='Environment Shift') plt.title('Performance on Non-Stationary Bandit') plt.xlabel('Steps') plt.ylabel('Cumulative Regret') plt.legend() plt.show()

In [8]:

# Deterministic Assertion Checks
print("Running assertions...")
test_env = BanditEnvironment(k=5, dist_type='bernoulli', seed=1)
assert test_env.k == 5
assert 0 <= test_env.optimal_value <= 1

eps_agent = EpsilonGreedyAgent(k=5)
eps_agent.update(0, 1.0)
assert eps_agent.q_estimates[0] == 1.0
assert eps_agent.action_counts[0] == 1

ucb_agent = UCBAgent(k=5)
assert ucb_agent.select_action(0) == 0
assert ucb_agent.select_action(4) == 4

ts_agent = ThompsonSamplingAgent(k=5)
ts_agent.update(0, 1.0)
assert ts_agent.alpha[0] == 2.0
assert ts_agent.beta[0] == 1.0

# Behavioral check: exploration must beat the pure-greedy baseline on cumulative regret.
# Pure greedy (epsilon=0) locks onto whichever arm succeeds first, so averaged over many
# seeded bandits its final regret is far above epsilon-greedy and above UCB.
rng = np.random.default_rng(SEED)  # re-seed so this check is deterministic in isolation
n_runs, n_steps = 20, 1000
final_regret = {'greedy': [], 'eps-greedy': [], 'ucb': []}
for i in range(n_runs):
    for name, agent_cls, kwargs in [('greedy', EpsilonGreedyAgent, {'epsilon': 0.0}),
                                    ('eps-greedy', EpsilonGreedyAgent, {'epsilon': 0.1}),
                                    ('ucb', UCBAgent, {'c': 2.0})]:
        check_env = BanditEnvironment(k=10, dist_type='bernoulli', seed=SEED + i)
        regret_curve, _, _ = run_experiment(agent_cls, check_env, n_steps, **kwargs)
        final_regret[name].append(regret_curve[-1])

mean_regret = {name: np.mean(values) for name, values in final_regret.items()}
for name, value in mean_regret.items():
    print(f"Mean final cumulative regret over {n_runs} bandits — {name}: {value:.1f}")

assert mean_regret['eps-greedy'] < 0.5 * mean_regret['greedy'], (
    "Epsilon-greedy should at least halve the pure-greedy baseline regret"
)
assert mean_regret['ucb'] < mean_regret['greedy'], (
    "UCB should beat the pure-greedy baseline regret"
)

print("All assertions passed!")

# Deterministic Assertion Checks print("Running assertions...") test_env = BanditEnvironment(k=5, dist_type='bernoulli', seed=1) assert test_env.k == 5 assert 0 <= test_env.optimal_value <= 1 eps_agent = EpsilonGreedyAgent(k=5) eps_agent.update(0, 1.0) assert eps_agent.q_estimates[0] == 1.0 assert eps_agent.action_counts[0] == 1 ucb_agent = UCBAgent(k=5) assert ucb_agent.select_action(0) == 0 assert ucb_agent.select_action(4) == 4 ts_agent = ThompsonSamplingAgent(k=5) ts_agent.update(0, 1.0) assert ts_agent.alpha[0] == 2.0 assert ts_agent.beta[0] == 1.0 # Behavioral check: exploration must beat the pure-greedy baseline on cumulative regret. # Pure greedy (epsilon=0) locks onto whichever arm succeeds first, so averaged over many # seeded bandits its final regret is far above epsilon-greedy and above UCB. rng = np.random.default_rng(SEED) # re-seed so this check is deterministic in isolation n_runs, n_steps = 20, 1000 final_regret = {'greedy': [], 'eps-greedy': [], 'ucb': []} for i in range(n_runs): for name, agent_cls, kwargs in [('greedy', EpsilonGreedyAgent, {'epsilon': 0.0}), ('eps-greedy', EpsilonGreedyAgent, {'epsilon': 0.1}), ('ucb', UCBAgent, {'c': 2.0})]: check_env = BanditEnvironment(k=10, dist_type='bernoulli', seed=SEED + i) regret_curve, _, _ = run_experiment(agent_cls, check_env, n_steps, **kwargs) final_regret[name].append(regret_curve[-1]) mean_regret = {name: np.mean(values) for name, values in final_regret.items()} for name, value in mean_regret.items(): print(f"Mean final cumulative regret over {n_runs} bandits — {name}: {value:.1f}") assert mean_regret['eps-greedy'] < 0.5 * mean_regret['greedy'], ( "Epsilon-greedy should at least halve the pure-greedy baseline regret" ) assert mean_regret['ucb'] < mean_regret['greedy'], ( "UCB should beat the pure-greedy baseline regret" ) print("All assertions passed!")

Running assertions...

Mean final cumulative regret over 20 bandits — greedy: 210.5
Mean final cumulative regret over 20 bandits — eps-greedy: 71.8
Mean final cumulative regret over 20 bandits — ucb: 169.6
All assertions passed!

7. Connections & Takeaways¶

• Bandits to Full RL: Bandits are RL with only one state. When we add multiple states and long-term consequences (MDPs), exploration strategies like $\varepsilon$-greedy directly transfer (e.g., in Q-Learning).
• UCB beyond Bandits: The idea of an exploration bonus based on uncertainty is widely used in deep RL (e.g., adding bonus rewards for reaching novel states).
• Thompson Sampling: A powerful Bayesian approach that naturally handles exploration/exploitation by maintaining belief distributions. It extends to more complex settings like contextual bandits.
• Non-stationarity: Standard UCB and Thompson Sampling assume stationary environments. If the world changes, they fail because they become too confident. $\varepsilon$-greedy (with a constant step size) or modified UCB/TS (with forgetting mechanisms) are needed for non-stationary problems.