Multi-Armed Bandits: Exploration vs. Exploitation in Production ML

Every major recommendation system, ad server, and clinical trial platform runs some form of multi-armed bandit. You have K slot machines (arms), each with an unknown reward distribution. At each round, you pull one arm and observe a reward. Your goal is to maximize total reward over T rounds. The tension between trying new arms (exploration) and sticking with the best-known arm (exploitation) is the core dilemma.

Bandits are the simplest instance of reinforcement learning, but they're not RL. In bandits, actions don't affect future states or reward distributions. This makes them tractable for rigorous analysis. The regret—the difference between your cumulative reward and that of an oracle who always pulls the best arm—is the standard performance metric.

Production systems rarely face the textbook stationary setting. Reward distributions drift, feedback is delayed, and arms have finite lifetimes. Engineers must adapt algorithms like Thompson sampling with Bayesian priors or use EXP3 for adversarial shifts. Ignoring these realities leads to catastrophic regret.

This article covers the theory, algorithms, and production patterns you need to deploy bandits at scale. We'll dissect regret bounds, walk through debugging a real-world incident, and give you a cheat sheet for common failures.

The Multi-Armed Bandit Problem: Formal Definition and Regret

The multi-armed bandit (MAB) problem formalizes sequential decision-making under uncertainty. You have K slot machines (arms), each with an unknown reward distribution. At each discrete time step t = 1,...,T, you pull one arm and observe a reward drawn from that arm's distribution. Your goal is to maximize cumulative reward over T rounds. This is equivalent to minimizing regret: the difference between the reward you would have gotten by always pulling the best arm and what you actually collected. Formally, let μ = max_i μ_i be the mean of the best arm and μ_i(t) be the mean of the arm you pulled at time t. The expected regret after T rounds is R_T = T·μ - E[∑_{t=1}^T μ_{I(t)}]. This definition captures the cost of not knowing which arm is best upfront. The reward distributions are typically assumed to be subgaussian (e.g., bounded in [0,1] or Bernoulli). The problem is stochastic: each arm's distribution is fixed but unknown. There is also an adversarial variant where rewards can change arbitrarily, but the stochastic setting is the canonical starting point. The key mathematical object is the regret bound, which quantifies how quickly an algorithm converges to optimal performance.

import numpy as np

def simulate_bandit(arm_means, T, policy):
    K = len(arm_means)
    rewards = np.zeros(T)
    chosen = np.zeros(T, dtype=int)
    counts = np.zeros(K)
    sums = np.zeros(K)
    for t in range(T):
        arm = policy(t, counts, sums)
        reward = np.random.binomial(1, arm_means[arm])
        chosen[t] = arm
        rewards[t] = reward
        counts[arm] += 1
        sums[arm] += reward
    return rewards, chosen

# Example: random policy (baseline)
def random_policy(t, counts, sums):
    return np.random.randint(len(counts))

arm_means = [0.1, 0.5, 0.9]
rewards, _ = simulate_bandit(arm_means, 1000, random_policy)
print(f"Total reward (random): {rewards.sum():.0f}")
print(f"Optimal possible: {1000 * max(arm_means):.0f}")
print(f"Regret: {1000 * max(arm_means) - rewards.sum():.0f}")

Exploration vs. Exploitation: The Core Tradeoff

The fundamental tension in bandits is between exploration (trying arms to learn their reward distributions) and exploitation (pulling the arm that currently seems best). If you exploit too early, you might get stuck on a suboptimal arm. If you explore too much, you waste pulls on bad arms and incur high regret. The optimal balance depends on the horizon T and the gap between arms. For example, if the best arm is 0.9 and second best is 0.89, you need many samples to distinguish them, so you must explore more. If the gap is large (0.9 vs 0.1), you can quickly identify the best arm and exploit. The exploration-exploitation tradeoff is not just a philosophical issue—it has concrete mathematical consequences. Algorithms like epsilon-greedy explicitly separate exploration (random pulls) from exploitation (greedy pulls). Others like UCB and Thompson Sampling implicitly balance both by using confidence bounds or posterior sampling. The key insight: you must explore enough to ensure that with high probability, you identify the best arm, but not so much that you waste linear regret. The optimal regret is O(log T), which means the number of suboptimal pulls grows only logarithmically with time.

import numpy as np

def epsilon_greedy(t, counts, sums, epsilon=0.1):
    if np.random.random() < epsilon:
        return np.random.randint(len(counts))
    else:
        return np.argmax(sums / (counts + 1e-10))

arm_means = [0.2, 0.8, 0.6]
T = 5000
rewards, chosen = simulate_bandit(arm_means, T, lambda t,c,s: epsilon_greedy(t,c,s,epsilon=0.1))
print(f"Total reward (eps=0.1): {rewards.sum():.0f}")
print(f"Optimal: {T * max(arm_means):.0f}")
print(f"Regret: {T * max(arm_means) - rewards.sum():.0f}")
# Count pulls per arm
counts = np.bincount(chosen, minlength=3)
print(f"Pulls per arm: {counts}")

Classic Algorithms: Epsilon-Greedy, UCB, and Thompson Sampling

Three algorithms dominate practice. Epsilon-Greedy: with probability epsilon, pull a random arm; otherwise pull the arm with highest empirical mean. Simple but suboptimal because it explores uniformly even after learning. Upper Confidence Bound (UCB): at each step, pull arm i that maximizes μ̂_i + sqrt(2 log t / n_i), where μ̂_i is empirical mean and n_i is number of pulls. This uses Hoeffding's inequality to create an optimistic estimate. UCB achieves O(log T) regret. Thompson Sampling: a Bayesian approach. Maintain a Beta posterior for each arm (assuming Bernoulli rewards). At each step, sample a mean from each posterior and pull the arm with the highest sample. This naturally balances exploration and exploitation. Thompson Sampling also achieves O(log T) regret and often outperforms UCB in practice, especially with small samples. All three are simple to implement. UCB requires no tuning (except the confidence level). Thompson Sampling requires a prior (uniform Beta(1,1) works well). Epsilon-Greedy needs epsilon tuning. For non-Bernoulli rewards, use Gaussian posteriors or bootstrap.

import numpy as np

def ucb(t, counts, sums):
    n = counts + 1e-10
    means = sums / n
    bonus = np.sqrt(2 * np.log(t + 1) / n)
    return np.argmax(means + bonus)

def thompson_sampling(t, counts, sums):
    # Beta posterior: alpha = sums + 1, beta = counts - sums + 1
    samples = np.random.beta(sums + 1, counts - sums + 1)
    return np.argmax(samples)

arm_means = [0.1, 0.5, 0.9]
T = 10000

# UCB
rewards_ucb, _ = simulate_bandit(arm_means, T, ucb)
print(f"UCB total reward: {rewards_ucb.sum():.0f}, regret: {T*0.9 - rewards_ucb.sum():.0f}")

# Thompson Sampling
rewards_ts, _ = simulate_bandit(arm_means, T, thompson_sampling)
print(f"TS total reward: {rewards_ts.sum():.0f}, regret: {T*0.9 - rewards_ts.sum():.0f}")

Regret Bounds: Why O(log T) Matters and How to Achieve It

The optimal regret for stochastic bandits is Θ(log T). This means that the number of times you pull a suboptimal arm grows only logarithmically with the total number of rounds. Why is this important? Linear regret (e.g., from always exploring with constant probability) means you lose a constant fraction of reward forever. Logarithmic regret means the per-round regret goes to zero as T grows. The Lai-Robbins lower bound shows that for any algorithm, regret is at least O(log T) times a constant that depends on the KL divergence between arms. UCB1 achieves O(log T) regret: specifically, for suboptimal arm i, the expected number of pulls is at most (2 log T) / Δ_i^2, where Δ_i = μ* - μ_i. This comes from the concentration inequality: the UCB bonus ensures that after enough pulls, the UCB of a suboptimal arm falls below the true mean of the best arm. Thompson Sampling also achieves O(log T) regret, with a similar bound but often better constants. The key to achieving O(log T) is to explore suboptimal arms only logarithmically often. Algorithms that explore with constant probability (like epsilon-greedy) incur linear regret. Algorithms that explore based on uncertainty (UCB, TS) achieve logarithmic regret. In practice, the constant matters: algorithms with smaller constants (like TS) perform better in finite samples.

import numpy as np
import matplotlib.pyplot as plt

def simulate_and_plot(arm_means, T, policies, labels):
    regrets = {}
    for name, policy in policies.items():
        rewards, _ = simulate_bandit(arm_means, T, policy)
        optimal = T * max(arm_means)
        cumulative_regret = optimal - np.cumsum(rewards)
        regrets[name] = cumulative_regret
    # Plot (not shown in output, but code is runnable)
    for name, cum_reg in regrets.items():
        plt.plot(cum_reg, label=name)
    plt.legend()
    plt.xlabel('Round')
    plt.ylabel('Cumulative Regret')
    plt.title('Regret Growth')
    plt.show()

arm_means = [0.2, 0.8, 0.6]
T = 5000
policies = {
    'epsilon=0.1': lambda t,c,s: epsilon_greedy(t,c,s,epsilon=0.1),
    'UCB': ucb,
    'Thompson': thompson_sampling
}
# Just compute final regret
for name, policy in policies.items():
    rewards, _ = simulate_bandit(arm_means, T, policy)
    regret = T*0.8 - rewards.sum()
    print(f"{name}: regret = {regret:.0f}")

Adversarial Bandits and EXP3: Handling Non-Stationary Environments

Stochastic bandits assume each arm’s reward distribution is fixed. In production, that assumption is often violated: user preferences drift, ad click-through rates change seasonally, and competitor actions shift the landscape. Adversarial bandits drop the stationarity assumption entirely—rewards can be chosen by an adversary (nature or a competitor) who knows your algorithm. The canonical algorithm is EXP3 (Exponential-weight algorithm for Exploration and Exploitation). EXP3 maintains a weight w_i for each arm, initialized to 1. At each round t, it computes a probability distribution p_i(t) = (1-γ) w_i(t) / Σ w_j(t) + γ/K, where γ ∈ (0,1] is the exploration parameter. It samples an arm i ~ p(t), observes reward r_i(t) ∈ [0,1], and updates w_i(t+1) = w_i(t) exp(γ r_i(t) / (K p_i(t))). The division by p_i(t) is an importance-weighting trick that yields unbiased estimates even under non-stationary rewards. EXP3 achieves expected regret O(√(T K log K)) against any adversary, which is optimal up to log factors. The key trade-off: smaller γ reduces exploration but increases vulnerability to adversarial shifts; larger γ stabilizes regret but wastes samples. In practice, set γ = min(1, √(K log K / (T(e-1)))) if you know T, or use a doubling trick. EXP3 is not without cost—it can have high variance due to importance weighting, especially when p_i(t) is tiny. For non-stationary but not fully adversarial environments, consider EXP3 with a sliding window or EXP3.S (with a discount factor). Never use EXP3 when you have strong evidence of stationarity; it will underperform UCB or Thompson sampling by a constant factor.

import numpy as np

def exp3(K, T, gamma=None):
    if gamma is None:
        gamma = min(1.0, np.sqrt(K * np.log(K) / ((np.e - 1) * T)))
    w = np.ones(K)
    rewards = np.zeros(T)
    for t in range(T):
        # compute probabilities with uniform mixing
        p = (1 - gamma) * w / w.sum() + gamma / K
        # sample arm
        arm = np.random.choice(K, p=p)
        # observe reward (simulated: random 0/1)
        reward = np.random.binomial(1, 0.5 + 0.1 * (arm == 0))
        rewards[t] = reward
        # importance-weighted update
        estimated_reward = reward / p[arm]
        w[arm] *= np.exp(gamma * estimated_reward / K)
    return rewards

if __name__ == '__main__':
    np.random.seed(42)
    rewards = exp3(K=5, T=10000)
    print(f'Total reward: {rewards.sum():.0f}, Avg: {rewards.mean():.3f}')

Contextual Bandits: Personalization with Side Information

Plain multi-armed bandits treat all users identically—the same arm is pulled regardless of who is interacting. In reality, user behavior depends on context: time of day, device type, browsing history, location. Contextual bandits incorporate this side information (a feature vector x_t) to personalize decisions. The most common approach is LinUCB, which assumes the expected reward of arm a is linear in the context: E[r | x, a] = x^T θ_a. LinUCB maintains a ridge regression estimate for each arm: θ̂_a = (X_a^T X_a + λI)^{-1} X_a^T y_a, where X_a is the design matrix of contexts where arm a was chosen, and y_a the observed rewards. At each step, it computes an upper confidence bound: UCB_a(x) = x^T θ̂_a + α √(x^T (X_a^T X_a + λI)^{-1} x). The second term is the standard deviation of the estimate scaled by α (typically 1-2). The algorithm selects the arm with highest UCB. LinUCB achieves regret O(d √T) under linear realizability, where d is the context dimension. In production, context dimensionality can be 100-1000; use incremental updates (Sherman-Morrison) to avoid O(d^3) matrix inversions per step. A simpler alternative is to discretize context into buckets and run separate bandits per bucket—this works when context is low-dimensional and you have enough data per bucket. For non-linear rewards, use neural bandits (e.g., NeuralUCB) or Bayesian approaches like Thompson sampling with a Gaussian process. Contextual bandits are the standard tool of personalization: ad selection, news recommendation, and dynamic pricing. The key challenge is exploration—you must explore contexts you haven't seen much, not just arms. Always log context, action, and reward for offline evaluation (e.g., inverse propensity scoring).

import numpy as np

class LinUCB:
    def __init__(self, K, d, alpha=1.0, lam=1.0):
        self.K = K
        self.d = d
        self.alpha = alpha
        self.lam = lam
        self.A = [lam * np.eye(d) for _ in range(K)]
        self.b = [np.zeros(d) for _ in range(K)]

    def select_arm(self, x):
        x = np.array(x)
        ucb = np.zeros(self.K)
        for a in range(self.K):
            A_inv = np.linalg.inv(self.A[a])
            theta = A_inv @ self.b[a]
            ucb[a] = x @ theta + self.alpha * np.sqrt(x @ A_inv @ x)
        return np.argmax(ucb)

    def update(self, arm, x, reward):
        x = np.array(x)
        self.A[arm] += np.outer(x, x)
        self.b[arm] += reward * x

if __name__ == '__main__':
    np.random.seed(0)
    K, d, T = 3, 5, 2000
    model = LinUCB(K, d, alpha=1.5)
    total_reward = 0
    for t in range(T):
        x = np.random.randn(d)
        arm = model.select_arm(x)
        reward = 1 if np.random.rand() < 0.5 + 0.1 * (arm == 0) else 0
        model.update(arm, x, reward)
        total_reward += reward
    print(f'Total reward: {total_reward}')

Production Patterns: Monitoring, Delayed Feedback, and Arm Fatigue

Deploying bandits in production is not just about picking the right algorithm—it's about the operational scaffolding. Three patterns dominate real-world pain: monitoring, delayed feedback, and arm fatigue. Monitoring: You must track per-arm reward rates, selection counts, and regret (estimated via inverse propensity scoring). Set alerts for when an arm's reward drops below a threshold (e.g., 2σ from historical mean) or when selection counts become too imbalanced (e.g., Gini coefficient > 0.8). Use dashboards with rolling windows (1h, 24h, 7d) to catch drift. Delayed feedback: In many systems (e.g., ad conversions, loan repayments), reward arrives hours or days after the action. Naively ignoring pending feedback biases estimates downward. Solution: use a 'delayed feedback' model that maintains two counters—observed rewards and pending impressions. Adjust exploration to account for uncertainty in pending feedback. Alternatively, use importance sampling with a propensity model for the delay. Arm fatigue: Users get tired of seeing the same arm (e.g., same ad, same recommendation). This violates the stationarity assumption—reward decreases with repeated exposure. Mitigate by adding a 'fatigue' feature to the context (e.g., count of times shown in last 24h) or by implementing a 'diversity' constraint that forces exploration across arms even when one dominates. In practice, arm fatigue is the most common reason bandits fail in production—users churn because they see the same thing too often. Always include a freshness heuristic: decay the weight of arms that have been shown too frequently in a short window.

import numpy as np
from collections import defaultdict

class BanditMonitor:
    def __init__(self, K, window_size=1000):
        self.K = K
        self.window_size = window_size
        self.rewards = defaultdict(list)
        self.selections = defaultdict(int)

    def log(self, arm, reward):
        self.rewards[arm].append(reward)
        self.selections[arm] += 1
        # keep window
        if len(self.rewards[arm]) > self.window_size:
            self.rewards[arm].pop(0)

    def report(self):
        total = sum(self.selections.values())
        print(f'Total selections: {total}')
        for arm in range(self.K):
            n = len(self.rewards[arm])
            if n == 0:
                continue
            avg = np.mean(self.rewards[arm])
            std = np.std(self.rewards[arm])
            print(f'Arm {arm}: selections={self.selections[arm]}, avg_reward={avg:.3f}, std={std:.3f}')
        # Gini coefficient for imbalance
        counts = np.array([self.selections[a] for a in range(self.K)])
        if counts.sum() > 0:
            sorted_counts = np.sort(counts)
            n = len(sorted_counts)
            gini = (2 * np.sum((np.arange(1, n+1) * sorted_counts)) - (n+1) * sorted_counts.sum()) / (n * sorted_counts.sum())
            print(f'Selection Gini: {gini:.3f}')

if __name__ == '__main__':
    monitor = BanditMonitor(K=5)
    np.random.seed(42)
    for _ in range(5000):
        arm = np.random.choice(5, p=[0.1, 0.1, 0.2, 0.3, 0.3])
        reward = np.random.binomial(1, 0.3 + 0.1 * arm)
        monitor.log(arm, reward)
    monitor.report()

Debugging Bandits: A Real-World Incident and Cheat Sheet

Incident: A major e-commerce site deployed a Thompson sampling bandit for homepage banner selection. After two weeks, click-through rates (CTR) dropped 15%. Investigation revealed that the bandit had converged to a single arm (banner A) with high confidence, but banner A's CTR was actually declining due to user fatigue. The algorithm's posterior was too narrow—it didn't explore enough to detect the drift. The fix: add a 'novelty bonus' to the prior variance for arms that had been selected many times, and implement a forced exploration schedule (every 100th impression, pick a random arm). The lesson: Bayesian bandits are not immune to non-stationarity; their posteriors can become overconfident. Debugging cheat sheet: (1) Check selection counts—if one arm dominates >80%, suspect over-exploitation. (2) Plot rolling average reward per arm—if any arm shows a downward trend, you have non-stationarity or fatigue. (3) Compute empirical regret using a holdout set or offline evaluation—if regret is increasing, your exploration is insufficient. (4) Verify reward distribution assumptions—if rewards are not bounded (e.g., revenue), clip or normalize them. (5) Test with synthetic data where you know the optimal arm—if your algorithm can't find it, there's a bug. (6) For contextual bandits, check feature importance—if context features are not predictive, the bandit reduces to a plain one. (7) Monitor for 'feedback loops': if the bandit's decisions affect future context (e.g., recommendations change user behavior), you need a causal model. Common pitfalls: using a fixed exploration parameter without tuning, ignoring delayed feedback, and not logging enough data for post-hoc analysis. Always log (timestamp, context, arm, reward, algorithm parameters) to a data warehouse for debugging.

import numpy as np

def debug_bandit(logs, K):
    """
    logs: list of dicts with keys 'arm', 'reward', 'timestamp'
    """
    logs = sorted(logs, key=lambda x: x['timestamp'])
    selections = np.zeros(K, dtype=int)
    rewards = np.zeros(K)
    rolling_rewards = {i: [] for i in range(K)}
    window = 100
    for i, log in enumerate(logs):
        arm = log['arm']
        reward = log['reward']
        selections[arm] += 1
        rewards[arm] += reward
        rolling_rewards[arm].append(reward)
        if len(rolling_rewards[arm]) > window:
            rolling_rewards[arm].pop(0)
    print('=== Debug Report ===')
    print(f'Total logs: {len(logs)}')
    for arm in range(K):
        avg = rewards[arm] / max(selections[arm], 1)
        rolling_avg = np.mean(rolling_rewards[arm]) if rolling_rewards[arm] else 0
        print(f'Arm {arm}: selections={selections[arm]}, avg_reward={avg:.3f}, rolling_avg={rolling_avg:.3f}')
    # check for dominance
    total = selections.sum()
    if total > 0:
        max_frac = selections.max() / total
        if max_frac > 0.8:
            print('WARNING: Arm dominance >80% - possible over-exploitation')
    # check for downward trends
    for arm in range(K):
        if len(rolling_rewards[arm]) >= window:
            first_half = np.mean(rolling_rewards[arm][:window//2])
            second_half = np.mean(rolling_rewards[arm][window//2:])
            if second_half < first_half - 0.05:
                print(f'WARNING: Arm {arm} shows downward trend')

if __name__ == '__main__':
    np.random.seed(0)
    logs = []
    for t in range(2000):
        arm = np.random.choice(3, p=[0.7, 0.2, 0.1])
        reward = np.random.binomial(1, 0.5 - 0.001 * t * (arm == 0))  # arm 0 degrades
        logs.append({'arm': arm, 'reward': reward, 'timestamp': t})
    debug_bandit(logs, K=3)