Multi-Armed Bandits: Modern Theory

Sparse Linear Bandits

Real-world problems often exhibit sparsity: among many potential features, only a few truly matter for the reward function. This sparsity can be exploited for improved learning rates and better interpretability. The challenge lies in simultaneously identifying which features matter and quantifying their importance.

In sparse linear bandits, we assume the parameter vector $\theta^* \in \mathbb{R}^d$ has at most $s \ll d$ non-zero entries, corresponding to the small number of features that actually affect rewards. The reward model remains $r_t = \langle \theta^*, x_{I_t} \rangle + \eta_t$, but now we can potentially achieve learning rates that depend on the sparsity level $s$ rather than the full feature dimension $d$.

The key insight is that standard LinUCB doesn't exploit sparsity - its confidence sets scale with all features even when only a few matter for rewards. We need algorithms that adapt to unknown sparsity in the reward function.

Lasso-UCB Algorithm

Lasso-UCB replaces standard regression with Lasso (L1-regularized) estimation to encourage sparse solutions, automatically identifying which features matter for rewards:

The Lasso estimator enjoys sparse recovery guarantees under appropriate conditions. If the design matrix satisfies the Restricted Eigenvalue (RE) condition - meaning the relevant features are not too correlated - the Lasso estimate satisfies:

$$\|\hat{\theta}_t - \theta^*\|_2 \leq \frac{4\lambda_t \sqrt{s}}{\text{RE}}$$

with high probability. The RE condition requires that the design provides sufficient diversity to distinguish between relevant features - a key requirement for reliable sparse recovery.

This bound has two key improvements over standard LinUCB:

1. Sparsity dependence: Scales with number of relevant features $s$ rather than all features $d$
2. High-dimensional scaling: $\log d$ dependence enables high-dimensional problems with minimal performance penalty

The challenge is that the confidence set $C_t$ is no longer ellipsoidal, making arm optimization computationally challenging. Recent work has developed efficient approximations using techniques from high-dimensional statistics.

OFUL-L1 Algorithm

OFUL-L1 (Optimism in the Face of Uncertainty - L1) provides an alternative approach using L1-regularized confidence sets directly:

$$C_t = \left\{\theta : \left\|\theta - \hat{\theta}_t^{\text{LS}}\right\|_{V_t} \leq \beta_t \text{ and } \|\theta\|_1 \leq B \right\}$$

This hybrid approach combines the computational tractability of least-squares with L1 constraints to encourage sparsity. The resulting optimization problem can be solved efficiently using convex optimization techniques.

import numpy as np
from sklearn.linear_model import Lasso
from scipy.optimize import minimize

def lasso_ucb(features, rewards, lam=None, s=None, T=None):
    """
    Lasso-UCB for sparse linear bandits

    Args:
        features: T x K x d tensor of arm features
        rewards: T x K matrix of rewards (observed online)
        lam: Lasso regularization parameter
        s: sparsity level (if known)
        T: time horizon

    Returns:
        cumulative_regret: regret at each time step
    """
    T, K, d = features.shape

    if lam is None and s is not None:
        lam = np.sqrt(np.log(d) / T)  # Adaptive choice

    # Initialize
    X_history = []
    y_history = []
    cumulative_regret = np.zeros(T)

    # Unknown true theta for regret computation
    true_theta = np.zeros(d)
    if s is not None:
        indices = np.random.choice(d, s, replace=False)
        true_theta[indices] = np.random.randn(s)

    for t in range(T):
        if t == 0:
            # Random initialization
            arm = np.random.choice(K)
        else:
            # Compute Lasso estimate
            if len(X_history) > 0:
                X_matrix = np.vstack(X_history)
                y_vector = np.array(y_history)

                lasso = Lasso(alpha=lam, fit_intercept=False)
                lasso.fit(X_matrix, y_vector)
                theta_hat = lasso.coef_

                # Confidence width (simplified)
                beta = np.sqrt(2 * np.log(d) + 2 * np.log(t))

                # Compute optimistic rewards for each arm
                ucb_values = np.zeros(K)
                for k in range(K):
                    x = features[t, k]
                    # Optimistic estimate (simplified)
                    ucb_values[k] = np.dot(theta_hat, x) + beta * np.linalg.norm(x) * np.sqrt(s)

                arm = np.argmax(ucb_values)
            else:
                arm = 0

        # Observe reward
        x_chosen = features[t, arm]
        reward = rewards[t, arm]

        # Update history
        X_history.append(x_chosen)
        y_history.append(reward)

        # Compute regret
        optimal_reward = np.max([np.dot(true_theta, features[t, k]) for k in range(K)])
        actual_reward = np.dot(true_theta, x_chosen)
        regret = optimal_reward - actual_reward
        cumulative_regret[t] = cumulative_regret[t-1] + regret if t > 0 else regret

    return cumulative_regret

# Sparse vector generation utility
def generate_sparse_vector(d, s, noise_level=1.0):
    """Generate s-sparse vector in R^d"""
    theta = np.zeros(d)
    support = np.random.choice(d, s, replace=False)
    theta[support] = noise_level * np.random.randn(s)
    return theta, support

Lower Bounds for Stochastic Linear Bandits

What are the fundamental limits for sparse linear bandits? The answer depends critically on the geometry of the arm set and the structure of sparsity.

For standard linear bandits with arbitrary arm sets, the minimax regret is $\Omega(d\sqrt{T})$. But with sparsity, we can hope for improvement. The question is whether we can achieve $O(s\sqrt{T})$ regret, or if dimension must enter in some way.

Lower Bound Construction

The key insight is that the arm set geometry matters crucially. Consider two cases:

Case 1: Rich arm set. If the arm set contains the standard basis vectors $\{e_1, \ldots, e_d\}$, then we can achieve $O(s \sqrt{T \log d})$ regret. The algorithm can efficiently identify which coordinates of $\theta^*$ are non-zero.

Case 2: Constrained arm set. If arms lie in a subspace or have restricted structure, sparsity may not help. For example, if all arms lie in a $k$-dimensional subspace, we cannot distinguish between sparse and dense $\theta^*$ in that subspace.

This reveals a phase transition: when $s \ll \sqrt{d/\log d}$, sparsity provides significant benefits. When $s \gtrsim \sqrt{d/\log d}$, the benefits diminish.

The proof constructs a hard instance by considering $\binom{d}{s}$ possible support sets for $\theta^*$. The algorithm must distinguish between these using observations that depend on $\theta^*$ only through projections onto arm features. When the arm set is rich enough, this can be done efficiently; otherwise, many support sets are indistinguishable.

Mutual Coherence and Recovery Conditions

The performance of sparse linear bandits depends critically on the mutual coherence of the arm set:

$$\mu(X) = \max_{i \neq j} \frac{|\langle x_i, x_j \rangle|}{\|x_i\|_2 \|x_j\|_2}$$

When mutual coherence is small, different arms probe different directions, making sparse recovery easier. High mutual coherence means arms are correlated, making it harder to identify the relevant features.

The Restricted Eigenvalue condition provides a more general characterization:

$$\text{RE}(s, X) = \min_{\|\theta\|_0 \leq s, \|\theta\|_2 = 1} \frac{\|X\theta\|_2^2}{n}$$

When $\text{RE}(s, X)$ is bounded away from zero, sparse recovery is possible with high probability.

Adversarial Linear Bandits

Adversarial linear bandits combine the robustness requirements of adversarial bandits with the structure of linear rewards. The adversary can choose loss vectors $\ell_t \in \mathbb{R}^d$ at each round, and the loss for arm $x$ at time $t$ is $\langle \ell_t, x \rangle$.

This setting captures scenarios where:

• The environment can adapt to our choices
• Rewards have linear structure in known features
• We want robustness against model misspecification

The challenge is that we observe only $\langle \ell_t, x_{I_t} \rangle$, not the full loss vector $\ell_t$. This makes it harder to estimate losses for unchosen arms compared to finite-armed adversarial bandits.

Exp2 Algorithm

Exp2 extends EXP3 to linear bandits by maintaining a distribution over arms and using the linear structure for importance-weighted estimation:

The key insight is that $\mathbb{E}[\hat{\ell}_t | X_t] = \ell_t$, so the loss vector estimates are unbiased. The algorithm essentially runs online gradient descent on the importance-weighted loss estimates.

Compared to adversarial finite-armed bandits with regret $O(\sqrt{KT})$, Exp2 can provide exponential improvements when the arm set is large but has small intrinsic dimension.

Online Gradient Descent Perspective

Exp2 can be viewed as online gradient descent in the dual space. The primal problem is:

$$\min_{x \in \mathcal{X}} \sum_{t=1}^T \langle \ell_t, x \rangle$$

The dual problem involves distributions over arms, and Exp2 performs mirror descent with the entropic regularizer in this dual space.

This connection reveals why linear structure helps: instead of learning about $K$ arms independently, we learn about the $d$-dimensional loss vectors that determine all arm losses simultaneously.

Adversarial Linear Bandits and the Curious Case of Linear Bandits on the Unit Ball

When the arm set is the unit ball $\mathcal{X} = \{x \in \mathbb{R}^d : \|x\|_2 \leq 1\}$, adversarial linear bandits exhibit surprising behavior. This case is particularly clean because any direction can be explored.

The regret lower bound for this setting is $\Omega(\sqrt{dT})$, achieved by an adversary that chooses $\ell_t$ to be roughly orthogonal to the algorithm's choices. But the upper bound analysis reveals subtleties.

The Geometric Challenge

The unit ball presents a geometric challenge: how should the exploration distribution $\mu$ be chosen? Natural choices include:

1. Uniform on sphere: $\mu$ uniform on $\partial\mathcal{B}_d$
2. Gaussian distribution: $\mu = \mathcal{N}(0, I/d)$ normalized
3. Uniform on ball: $\mu$ uniform on $\mathcal{B}_d$

Each choice leads to different exploration properties and regret constants. The key insight is that we need to balance exploration across all directions while maintaining computational tractability.

Improved Analysis via Self-Concordance

Recent work has refined the analysis using self-concordant barriers and interior point methods. The idea is to use the logarithmic barrier function:

$$F(w) = -\log(1 - \|w\|_2^2)$$

This barrier is self-concordant, meaning its third derivative is controlled by its second derivative. This property enables refined regret analysis:

The improved analysis removes logarithmic factors in the leading term and provides better constants. The self-concordance property ensures that the Hessian of the barrier provides a good local metric for the geometry.

Computational Considerations

Implementing Exp2 for continuous arm sets requires solving the optimization problem:

$$X_t = \arg\max_{x \in \mathcal{X}} \langle w_t, x \rangle + \gamma \log \mu(x)$$

For the unit ball, this often has closed-form solutions, but for general convex sets, it may require numerical optimization at each round.

def exp2_unit_ball(losses, eta=None, gamma=None, T=None, d=None):
    """
    Exp2 for adversarial linear bandits on unit ball

    Args:
        losses: T x d matrix of loss vectors (revealed online)
        eta: learning rate
        gamma: exploration parameter
        T: time horizon
        d: dimension

    Returns:
        cumulative_regret: regret at each time step
    """
    T, d = losses.shape

    if eta is None:
        eta = 1 / np.sqrt(T)
    if gamma is None:
        gamma = np.sqrt(d * np.log(d) / T)

    # Initialize weight vector
    w = np.zeros(d)
    cumulative_regret = np.zeros(T)

    # Best fixed arm for comparison
    best_arm = -np.sum(losses, axis=0)
    best_arm = best_arm / np.linalg.norm(best_arm)  # Project to unit ball
    best_reward = -np.sum([np.dot(losses[t], best_arm) for t in range(T)])

    for t in range(T):
        # Compute optimal arm under current weights
        if np.linalg.norm(w) < 1e-10:
            # Random initialization
            x_star = np.random.randn(d)
            x_star = x_star / np.linalg.norm(x_star)
        else:
            x_star = w / np.linalg.norm(w)

        # Add exploration: mix with random direction
        if np.random.random() < gamma:
            x_t = np.random.randn(d)
            x_t = x_t / np.linalg.norm(x_t)
        else:
            x_t = x_star

        # Observe loss
        loss_value = np.dot(losses[t], x_t)

        # Compute regret
        regret = loss_value - (-np.dot(losses[t], best_arm))
        cumulative_regret[t] = cumulative_regret[t-1] + regret if t > 0 else regret

        # Update weights using importance-weighted gradient
        prob_exploration = gamma / (4 * np.pi)  # Rough approximation for uniform on sphere
        prob_exploitation = 1 - gamma
        prob_t = prob_exploration + prob_exploitation if np.allclose(x_t, x_star) else prob_exploration

        gradient_estimate = loss_value / prob_t * x_t
        w = w - eta * gradient_estimate

        # Project to ensure numerical stability
        if np.linalg.norm(w) > 10:
            w = 10 * w / np.linalg.norm(w)

    return cumulative_regret

First Order Bounds for k-Armed Adversarial Bandits

Classical adversarial bandit bounds scale as $O(\sqrt{KT})$, but this can be pessimistic when the loss sequence is "easy". First-order bounds adapt to the difficulty of the instance, achieving better performance when losses are small or when the best arm significantly outperforms others.

Define the total loss of the best arm: $L^* = \min_i \sum_{t=1}^T \ell_{i,t}$. First-order bounds have the form:

$$\mathbb{E}[R_T] = O(\sqrt{KL^* \log K})$$

When $L^* \ll T$, this is much better than the worst-case $O(\sqrt{KT})$ bound. The challenge is achieving such bounds while maintaining worst-case optimality.

Adaptive EXP3

The key insight is to adapt the learning rate based on observed losses. Standard EXP3 uses fixed $\gamma = \sqrt{\frac{2\log K}{KT}}$, but adaptive versions adjust $\gamma_t$ based on the cumulative loss observed so far.

The adaptive learning rate $\gamma_t$ decreases as cumulative loss increases, providing more aggressive exploitation when losses are small.

This bound interpolates between first-order and worst-case performance: when $L^* = O(\sqrt{T})$, we get the optimal first-order rate; when $L^* = \Theta(T)$, we recover the standard rate.

Connection to Online Mirror Descent

The first-order analysis reveals connections to adaptive online mirror descent. The key insight is that the effective learning rate should adapt to the magnitude of gradients observed so far.

In the online mirror descent framework, we use the update:

$$w_{t+1} = \arg\min_w \left\{ \langle \hat{\ell}_t, w \rangle + \frac{1}{\eta_t} D_{\psi}(w, w_t) \right\}$$

where $D_{\psi}$ is the Bregman divergence induced by $\psi$. For entropic regularization, this reduces to the exponential weights update.

Adaptive step sizes $\eta_t$ that depend on gradient norms can achieve first-order bounds. The general principle is that large gradients suggest we're far from optimal, justifying larger steps, while small gradients suggest we're close to optimal, calling for smaller steps.

The Variance of EXP3

A refined understanding of EXP3 comes from analyzing the variance of its importance-weighted estimators. This variance analysis leads to improved algorithms and tighter bounds.

Recall that EXP3 uses the estimator $\hat{\ell}_i(t) = \frac{\ell_{i,t} \mathbb{1}_{I_t = i}}{p_i(t)}$ with variance:

$$\text{Var}[\hat{\ell}_i(t)] = \ell_{i,t}^2 \frac{1-p_i(t)}{p_i(t)}$$

This variance can be large when $p_i(t)$ is small, leading to noisy updates. The key insight is that we can reduce variance by using different estimation strategies.

Variance-Reduced Estimators

Several approaches can reduce the variance of loss estimates:

1. Implicit Exploration: Instead of explicit $\gamma$ mixing, use the implicit exploration from the exponential weights:

$$\hat{\ell}_i(t) = \frac{\ell_{i,t} \mathbb{1}_{I_t = i}}{p_i(t)} - \frac{\bar{\ell}_t \mathbb{1}_{I_t \neq i}}{1-p_i(t)}$$

where $\bar{\ell}_t$ is an estimate of the average loss.

2. Control Variates: Use correlated random variables to reduce variance:

$$\hat{\ell}_i(t) = \frac{\ell_{i,t} \mathbb{1}_{I_t = i}}{p_i(t)} - c_{i,t}(X_t - \mathbb{E}[X_t])$$

where $c_{i,t}$ is chosen to minimize variance.

High-Probability Analysis

Variance analysis enables high-probability bounds for EXP3. The standard approach uses concentration inequalities for martingales with bounded differences.

Define the martingale $M_t = \sum_{s=1}^t (\hat{\ell}_{I_s,s} - \ell_{I_s,s})$. Using Azuma's inequality:

The variance-aware analysis can improve the constants and potentially the dependence on confidence level $\delta$.

Variance-Adaptive Algorithms

Recent work has developed algorithms that adapt to the variance of loss estimates, achieving improved performance when this variance is small. The idea is to use confidence intervals that adapt to the observed variance:

$$\text{CI}_i(t) = \hat{\mu}_i(t) \pm \sqrt{\frac{\hat{\sigma}_i^2(t) \log t}{N_i(t)}}$$

where $\hat{\sigma}_i^2(t)$ is an estimate of the variance for arm $i$.

Bayesian/Minimax Duality for Adversarial Bandits

One of the most elegant results in modern bandit theory is the duality between Bayesian and minimax approaches for adversarial bandits. This duality provides deep insights into the nature of optimal algorithms and fundamental limits.

The Duality Theorem

Consider the adversarial bandit game with $K$ arms and horizon $T$. The minimax regret is:

$$R^*_T = \inf_{\text{algorithms}} \sup_{\text{loss sequences}} \mathbb{E}[\text{Regret}]$$

On the Bayesian side, consider a prior $\Pi$ over loss sequences and define:

$$R^{\text{Bayes}}_T(\Pi) = \inf_{\text{algorithms}} \mathbb{E}_{\ell \sim \Pi}[\mathbb{E}[\text{Regret}]]$$

This theorem has several profound implications:

1. Algorithmic insight: The minimax-optimal algorithm can be found by solving a Bayesian problem
2. Lower bound technique: Lower bounds can be proved by exhibiting challenging priors
3. Adaptive optimality: The same algorithm that's worst-case optimal is also Bayes-optimal against the hardest prior

Construction of the Least Favorable Prior

For the $K$-armed bandit problem, the least favorable prior has a specific structure. It places mass on loss sequences that are "balanced" in a certain sense - no arm is too obviously better than others.

Specifically, $\Pi^*$ is supported on loss sequences where:

• Losses are independent across time and arms
• Each loss is Bernoulli with carefully chosen parameters
• The parameters are chosen to make all arms equally attractive a priori

The construction proceeds by analyzing the value function of the optimal stopping problem that underlies the Bayesian bandit. The least favorable prior makes this value function as flat as possible.

Implications for Algorithm Design

The duality result provides a principled approach to algorithm design:

1. Characterize the least favorable prior: Find the prior that makes the Bayesian problem hardest
2. Solve the Bayesian problem: Compute the Bayes-optimal algorithm against this prior
3. Verify minimax optimality: Show that this algorithm achieves the minimax regret

This approach has been successfully applied to various bandit settings, including:

• Multi-armed bandits with different action sets
• Linear bandits with structured loss sequences
• Contextual bandits with adversarial contexts

Connection to Game Theory

The duality theorem is a manifestation of the minimax theorem from game theory. The bandit problem can be viewed as a zero-sum game between the algorithm and the adversary, where:

• The algorithm chooses a (randomized) strategy
• The adversary chooses a loss sequence
• The payoff is the regret

Von Neumann's minimax theorem guarantees that:

$$\inf_{\text{algorithms}} \sup_{\text{sequences}} \mathbb{E}[\text{Regret}] = \sup_{\text{priors}} \inf_{\text{algorithms}} \mathbb{E}_{\Pi}[\text{Regret}]$$

The right-hand side is precisely the supremum over Bayesian problems, establishing the duality.

Computational Aspects

While the duality theorem is theoretically elegant, computing the least favorable prior and Bayes-optimal algorithm can be challenging. Recent work has developed approximation algorithms and computational techniques for specific cases.

For finite-horizon problems, dynamic programming can sometimes compute exact solutions. For infinite-horizon problems, approximation techniques based on convex optimization have been developed.

def bayesian_bandit_value(prior_params, K, T):
    """
    Compute value function for Bayesian bandit via dynamic programming

    Args:
        prior_params: parameters of Beta priors for each arm
        K: number of arms
        T: time horizon

    Returns:
        value: optimal Bayesian value
    """
    from scipy.special import beta as beta_function

    # Dynamic programming for Bayesian bandit
    # State: (t, alpha_1, beta_1, ..., alpha_K, beta_K)
    # Value[t][state] = optimal expected reward from time t onwards

    memo = {}

    def value(t, alphas, betas):
        if t == T:
            return 0

        state = (t, tuple(alphas), tuple(betas))
        if state in memo:
            return memo[state]

        # Compute expected reward for each arm
        arm_values = np.zeros(K)
        for i in range(K):
            # Expected immediate reward
            expected_reward = alphas[i] / (alphas[i] + betas[i])

            # Expected future value after pulling arm i
            # Update depends on observed outcome
            future_value_success = value(t+1,
                                       [alphas[j] + (1 if j == i else 0) for j in range(K)],
                                       betas)
            future_value_failure = value(t+1,
                                       alphas,
                                       [betas[j] + (1 if j == i else 0) for j in range(K)])

            prob_success = alphas[i] / (alphas[i] + betas[i])
            expected_future = (prob_success * future_value_success +
                             (1 - prob_success) * future_value_failure)

            arm_values[i] = expected_reward + expected_future

        optimal_value = np.max(arm_values)
        memo[state] = optimal_value
        return optimal_value

    # Start with prior parameters
    initial_alphas = [prior_params[i][0] for i in range(K)]
    initial_betas = [prior_params[i][1] for i in range(K)]

    return value(0, initial_alphas, initial_betas)

Synthesis and Future Directions

This journey from the 1933 insights to modern bandit theory reveals the mathematical elegance underlying sequential decision making under uncertainty. We've seen how sophisticated techniques from high-dimensional statistics, convex optimization, information theory, and game theory combine to provide both efficient algorithms and fundamental limits on learning.

Key Theoretical Insights

Several overarching themes emerge from modern bandit theory:

Structure enables efficient learning. From linear rewards to sparse effects, exploiting problem structure dramatically improves performance. The progression from $O(\sqrt{KT})$ for arbitrary arms to $O(s\sqrt{T \log d})$ for sparse linear bandits illustrates how structural understanding enables better algorithms.

Information theory provides fundamental limits on learning. The Lai-Robbins lower bounds, minimax theory, and mutual information arguments reveal what's statistically possible and impossible in sequential learning. These limits guide algorithm design and reveal phase transitions in learning requirements.

Adaptive algorithms are powerful but complex. Algorithms that adjust to emerging evidence can significantly outperform fixed strategies when problems have favorable structure. However, this adaptivity requires sophisticated analysis and careful implementation.

Bayesian-frequentist duality provides deep insights. The duality reveals that optimal algorithms for worst-case scenarios are also optimal for carefully constructed prior distributions. This connection bridges different statistical frameworks in learning theory.

Computational Frontiers

Modern applications demand computationally efficient algorithms that can handle massive scale:

• High-dimensional problems: With high-dimensional features, standard algorithms become computationally prohibitive. Techniques from high-dimensional statistics (sparse recovery, random projections) enable scaling to large feature spaces.
• Nonlinear rewards: Moving beyond linear models to neural networks and kernel methods while maintaining statistical guarantees.
• Distributed learning: Coordinating learning across multiple agents while handling federated data and communication constraints.

Beyond Classical Bandits

Several extensions push the boundaries of traditional bandit theory:

Sequential Decision Making: Multi-armed bandits provide the foundation for sequential decisions, where early actions affect future states. The exploration-exploitation trade-off becomes complex when actions have long-term consequences and state dependencies.

Causal Effects: When actions have complex causal pathways that need to be learned, traditional algorithms may fail to identify true mechanisms. Incorporating causal structure leads to new designs and identifiability conditions.

Multi-Agent Systems: When multiple agents make decisions simultaneously, their interactions create new challenges. Network effects, externalities, and coordination across agents all affect optimal policies.

Practical Impact

The theory developed in this series has found applications across diverse domains:

• Online advertising: Balancing exploration of new ads with exploitation of proven performers
• Recommendation systems: Learning user preferences while providing relevant content
• Resource allocation: Optimally distributing limited resources across competing demands
• A/B testing: Efficiently comparing alternatives while maximizing performance

The mathematical rigor of bandit theory provides both principled algorithms and performance guarantees that are essential for automated decision systems.

Open Problems

Several fundamental questions remain open:

1. Adaptive vs. Fixed Strategies: When do adaptive algorithms provide significant improvements over fixed strategies in practical settings?
2. High-Dimensional Limits: What are the precise statistical requirements for high-dimensional bandits with various structural assumptions?
3. Computational-Statistical Gaps: For which problems do computationally efficient algorithms achieve optimal statistical performance?
4. Robustness to Model Misspecification: How can algorithms maintain performance guarantees when modeling assumptions are violated?

The mathematical machinery we've explored - concentration inequalities, ellipsoidal confidence sets, information-theoretic arguments, game-theoretic duality - provides the foundation for attacking these problems. As machine learning systems become more autonomous and consequential, the principled approach to exploration and exploitation that bandit theory provides becomes increasingly valuable.

The elegance of the framework lies not just in its mathematical beauty, but in its direct relevance to fundamental questions about decision-making under uncertainty. Every time we face the explore-exploit trade-off - whether in online systems, recommendation engines, or resource allocation - we're engaging with the core insights that continue to shape modern learning theory.

References

• Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4), 285-294.
• Carpentier, A., & Munos, R. (2012). Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. AISTATS, 190-198.
• Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. NIPS, 2312-2320.
• Audibert, J. Y., & Bubeck, S. (2010). Best arm identification in multi-armed bandits. COLT, 13-30.
• Abernethy, J., Hazan, E., & Rakhlin, A. (2008). Competing in the dark: An efficient algorithm for bandit linear optimization. COLT, 263-274.
• Rakhlin, A., & Sridharan, K. (2013). Online learning with predictable sequences. COLT, 993-1019.
• Russo, D., & Van Roy, B. (2016). An information-theoretic analysis of Thompson sampling. Journal of Machine Learning Research, 17(1), 2442-2471.
• Lattimore, T. (2015). The minimax regret for multi-armed bandits. Theoret. Comput. Sci., 588, 91-95.
• Perchet, V., & Rigollet, P. (2013). The multi-armed bandit problem with covariates. Annals of Statistics, 41(2), 693-721.
• Bubeck, S., Cesa-Bianchi, N., & Kakade, S. M. (2012). Towards minimax policies for online linear optimization with bandit feedback. COLT, 41.1-41.14.
• Foster, D., Rakhlin, A., & Sridharan, K. (2019). Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective. arXiv preprint.
• Villar, S. S., Bowden, J., & Wason, J. (2015). Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical Science, 30(2), 199-215.
• Williamson, S. F., Jacko, P., Villar, S. S., & Jaki, T. (2017). A Bayesian adaptive design for clinical trials in rare diseases. Computational Statistics & Data Analysis, 113, 136-153.
• Wason, J. M., & Trippa, L. (2014). A comparison of Bayesian adaptive randomization and multi-stage designs for multi-arm clinical trials. Statistics in Medicine, 33(13), 2206-2221.