Multi-Armed Bandits: Exploration vs Exploitation

🎯 Learning Objectives

• Formulate the multi-armed bandit problem
• Implement ε-greedy, UCB, and Thompson sampling strategies
• Understand regret as a performance metric
• Distinguish stationary from non-stationary bandit problems

📋 Prerequisites

• Probability (expected value, distributions)
• Basic optimization concepts

---

1. 📖 Core Content

1.1 The Bandit Problem

• Exploitation: Pull the machine you believe is best (maximize immediate reward)
• Exploration: Pull other machines to gather more information (might find a better machine)

1.2 Formal Definition

• Actions: $A_t \in \{1, 2, ..., k\}$ at time t
• Rewards: $R_t \sim \mathcal{D}_{A_t}$ (unknown distribution for each action)
• Value: $q_*(a) = \mathbb{E}[R_t | A_t = a]$
• Estimated value: $Q_t(a) \approx q_*(a)$
• Regret: $\rho = T \cdot q_*(a^*) - \sum_{t=1}^T R_t$ Goal: Minimize regret (maximize cumulative reward)

1.3 Action-Value Estimation

1.4 ε-Greedy

python
Run Inline
# runnable
import numpy as np
import matplotlib.pyplot as plt
class EpsilonGreedy:
    def __init__(self, n_arms, epsilon=0.1):
        self.n_arms = n_arms
        self.epsilon = epsilon
        self.Q = np.zeros(n_arms)  # Estimated values
        self.counts = np.zeros(n_arms)  # Times each arm pulled
    def select_action(self):
        """Select action using ε-greedy"""
        if np.random.random() < self.epsilon:
            return np.random.randint(self.n_arms)  # Explore
        else:
            return np.argmax(self.Q)  # Exploit
    def update(self, arm, reward):
        """Incremental update of action value"""
        self.counts[arm] += 1
        n = self.counts[arm]
        self.Q[arm] = self.Q[arm] + (1/n) * (reward - self.Q[arm])
# Simulate
np.random.seed(42)
n_arms = 5
# True reward probabilities (unknown to the agent)
true_probs = [0.3, 0.5, 0.7, 0.4, 0.6]
agent = EpsilonGreedy(n_arms, epsilon=0.1)
rewards = []
for step in range(1000):
    arm = agent.select_action()
    reward = 1 if np.random.random() < true_probs[arm] else 0
    agent.update(arm, reward)
    rewards.append(reward)
print(f"True best arm: {np.argmax(true_probs)} (prob={max(true_probs):.2f})")
print(f"Estimated values: {np.round(agent.Q, 3)}")
print(f"Chosen most: arm {np.argmax(agent.counts)} ({int(agent.counts[np.argmax(agent.counts)])} times)")

1.5 Upper Confidence Bound (UCB)

$$A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]$$

• $c$: Exploration parameter
• $N_t(a)$: Number of times action a has been selected
• The square root term: uncertainty estimate (decreases as action is tried more) Key property: UCB has logarithmic regret: $\lim_{T \to \infty} \rho(T) / \ln T = \text{constant}$

1.6 Thompson Sampling

1. Maintain a posterior distribution over each arm's value
2. At each step, sample from the posterior of each arm
3. Choose the arm with the highest sample For Bernoulli rewards (0/1): Beta distribution prior, Beta posterior.

$$\alpha_t(a) = \alpha_0 + \text{wins}, \quad \beta_t(a) = \beta_0 + \text{losses}$$

python
Run Inline
# runnable
import numpy as np
class ThompsonSampling:
    def __init__(self, n_arms, alpha=1, beta=1):
        self.n_arms = n_arms
        self.alpha = np.ones(n_arms) * alpha  # Beta prior parameters
        self.beta = np.ones(n_arms) * beta
    def select_action(self):
        """Sample from posterior and pick best"""
        samples = np.random.beta(self.alpha, self.beta)
        return np.argmax(samples)
    def update(self, arm, reward):
        """Update Beta posterior"""
        self.alpha[arm] += reward  # Win
        self.beta[arm] += 1 - reward  # Loss
# Compare strategies
np.random.seed(42)
strategies = {
    'ε-greedy(0.1)': EpsilonGreedy(5, 0.1),
    'ε-greedy(0.01)': EpsilonGreedy(5, 0.01),
    'Thompson': ThompsonSampling(5),
}
results = {}
for name, agent in strategies.items():
    regrets = []
    optimal_reward = max(true_probs)
    cumulative_regret = 0
    for step in range(1000):
        arm = agent.select_action() if hasattr(agent, 'select_action') else agent.select_action()
        reward = 1 if np.random.random() < true_probs[arm] else 0
        agent.update(arm, reward)
        cumulative_regret += optimal_reward - reward
        regrets.append(cumulative_regret)
    results[name] = regrets
    print(f"{name}: Final regret = {cumulative_regret:.2f}")

---

📝 Practice Questions

Q1

<strong>Q1</strong>: For ε=0.1, over 1000 steps, what fraction of actions are exploratory (on average)?

100% × 0.1 = 10% of actions are exploratory = ~100 steps

But during exploration, the agent may still select the greedy action (if the random action happens to be the best). So actual exploration rate is ε overall.

In the limit, ε-greedy with constant ε achieves linear regret because it never stops exploring. Q2

<strong>Q2

<strong>Q2</strong>: In UCB, what happens when an action has never been tried (N_t(a) = 0)?

When N_t(a) = 0, the term c × √(ln t / 0) = c × ∞ = ∞. This means all untried actions have infinite UCB values and will be selected before any tried action is re-selected.

This guarantees that every action is tried at least once — an important property for regret bounds. Q3

<strong>Q3

<strong>Q3</strong>: Derive the incremental update formula Q_{t+1} = Q_t + (1/n)(R_t - Q_t) from the sample average.

Start with: Q_n = (R_1 + R_2 + ... + R_{n-1}) / (n-1)

Q_{n+1} = (R_1 + ... + R_{n-1} + R_n) / n = ((n-1)Q_n + R_n) / n = Q_n + (R_n - Q_n)/n

This incremental form is O(1) per update (instead of O(n)), and works for non-stationary problems when using constant α instead of 1/n. Q4

<strong>Q4

<strong>Q4

<strong>Q4</strong>: Compare the regret growth rates of ε-greedy, UCB, and Thompson sampling.

UCB and Thompson sampling both achieve logarithmic regret — the best possible. Thompson sampling often has a better constant factor in practice.

</details> * * * ## 🔗 Cross-References - **Next**: [Markov Decision Processes](/notes/04-degree-electives-bsda5007-reinforcement-learning-week02-02-mdps) - **Video**: BSDA5007 Week 1 transcripts [Join Discord](https://discord.gg/gE2m4Qrdqv) [Next**MDPs & Bellman Equations**](/notes/04-degree-electives-bsda5007-reinforcement-learning-week02-02-mdps)