Multi Armed Bandits and Experimentation Questions

Covers adaptive experimentation methods that trade off exploration and exploitation to optimize sequential decision making, and how they compare to traditional A B testing. Core concepts include the exploration versus exploitation dilemma, regret minimization, reward modeling, and handling delayed or noisy feedback. Familiar algorithms and families to understand are epsilon greedy, Upper Confidence Bound, Thompson sampling, and contextual bandit extensions that incorporate features or user context. Practical considerations include when to choose bandit approaches versus fixed randomized experiments, designing reward signals and metrics, dealing with non stationary environments and concept drift, safety and business constraints on exploration, offline evaluation and simulation, hyperparameter selection and tuning, deployment patterns for online learning, and reporting and interpretability of adaptive experiments. Applications include personalization, recommendation systems, online testing, dynamic pricing, and resource allocation.

MediumTechnical

67 practiced

Implement the LinUCB contextual bandit algorithm in Python for real-valued rewards. API: LinUCB(num_arms, d, alpha) with select_arm(context_vector) and update(arm, reward, context_vector). Use per-arm matrices A and vectors b and compute p = theta^T x + alpha * sqrt(x^T A^{-1} x). Describe numerical-stability choices.

Sample Answer

To implement LinUCB, maintain per-arm A (dxd) and b (d) where theta = A^{-1} b. For select_arm, compute p = theta^T x + alpha * sqrt(x^T A^{-1} x) and pick argmax. Update by A += x x^T and b += reward * x. Use regularization, Cholesky solves, and incremental updates for numerical stability and efficiency.

python

import numpy as np

class LinUCB:
    def __init__(self, num_arms, d, alpha, lambda_reg=1.0):
        self.num_arms = num_arms
        self.d = d
        self.alpha = alpha
        self.lambda_reg = lambda_reg
        
        # Per-arm matrices and vectors
        # A = D x D positive-definite matrix, initialized to lambda * I
        # b = D vector of rewards
        self.A = [lambda_reg * np.eye(d) for _ in range(num_arms)]
        self.b = [np.zeros(d) for _ in range(num_arms)]
        # Optionally cache A_inv or Cholesky; we compute via cho_solve for stability
        from scipy.linalg import cho_factor
        self._cho_factors = [cho_factor(self.A[i], overwrite_a=False) for i in range(num_arms)]

    def select_arm(self, x):
        """
        x: context vector (d,)
        returns: arm index
        """
        x = np.asarray(x).reshape(-1)
        assert x.shape[0] == self.d
        best_arm = None
        best_p = -np.inf
        from scipy.linalg import cho_solve
        for a in range(self.num_arms):
            # Solve A^{-1} b robustly via Cholesky factors
            cho = self._cho_factors[a]
            theta = cho_solve(cho, self.b[a])
            # compute uncertainty term: sqrt(x^T A^{-1} x) via solve
            Ainv_x = cho_solve(cho, x)
            sigma = np.sqrt(np.dot(x, Ainv_x))
            p = np.dot(theta, x) + self.alpha * sigma
            if p > best_p:
                best_p = p
                best_arm = a
        return best_arm

    def update(self, arm, reward, x):
        """
        arm: int
        reward: real-valued reward
        x: context vector (d,)
        """
        x = np.asarray(x).reshape(-1)
        assert x.shape[0] == self.d
        # A += x x^T
        self.A[arm] += np.outer(x, x)
        # b += r * x
        self.b[arm] += reward * x
        # update Cholesky factor for numerical stability
        from scipy.linalg import cho_factor
        # Re-factor A; for high-throughput use rank-one Cholesky updates instead
        self._cho_factors[arm] = cho_factor(self.A[arm], overwrite_a=False)

Key choices and numerical-stability notes:- Initialize A = lambda * I (Tikhonov regularization) to keep A positive definite.- Use Cholesky factorization and cho_solve instead of explicit matrix inverse to avoid instability.- Recompute/update Cholesky factor after each A change; for performance, use rank-one Cholesky updates (not shown) to avoid O(d^3) per update.- Use double precision (numpy float64) and guard against ill-conditioned A by choosing sensible lambda_reg.Time complexity: select_arm O(K d^2) (solves per arm), update O(d^2) (refactor O(d^3) naive; with rank-one update O(d^2)). Edge cases: handle zero / near-zero contexts, out-of-range arm indices, and scale/normalize features to improve conditioning.

HardTechnical

33 practiced

Adaptive allocation complicates statistical inference. Describe approaches that yield valid inference under adaptive sampling: martingale-based sequential tests, e-values, and permutation/bootstrap variants that account for adaptivity. Provide a practical recipe to compute p-values or credible intervals for an adaptive experiment.

Sample Answer

Adaptive allocation (e.g., bandits) breaks iid assumptions; valid inference requires methods that respect the data-collection filtration. Three complementary approaches:

1) Martingale-based sequential tests / confidence sequences- Idea: construct nonnegative martingales (or supermartingales) under the null; apply Ville’s inequality to get anytime-valid p-values and time-uniform confidence sequences.- Examples: mixture/mixture-chi-sq martingales, sequential t-statistics with self-normalization, or betting-based confidence sequences (predictable nonnegative wealth processes).- Key property: validity under optional stopping and adaptive allocation as long as the process is adapted to the filtration.

2) E-values (e-processes)- E-values are nonnegative random variables with expectation ≤1 under the null; sequential combinations (products or mixtures) remain valid. They give straightforward testing (reject when e>1/α) and can be converted to anytime-valid p-values (p = 1/e).- Useful for composite nulls and combining streams or experts (growth-rate optimal bets).

3) Permutation / bootstrap variants that account for adaptivity- Plain resampling fails because assignments depend on past outcomes. Use conditional/randomization-based approaches: - Adaptive permutation: permute outcomes only within strata/blocks defined by the allocation history or conditional on assignment probabilities. - Rejection-sampling bootstrap: resample from a model fitted under the null while re-running the adaptive allocation policy (simulate the adaptive data-generating process).- These produce null distributions that preserve the adaptive mechanism.

Practical recipe to get p-values or credible intervals in an adaptive experiment:1. Define the estimand (difference in means, ATE, reward gap) and filtration (what the algorithm observed when).2. Choose approach: - If you need anytime-valid tests/CI: build a martingale/e-process (e.g., betting mixture or mixture-t) tailored to bounded or sub-Gaussian rewards. - If you prefer simulation-based nulls: implement a conditional randomization test by simulating assignments under the null policy and recomputing the statistic.3. Implementation steps for martingale/e-value: - Standardize rewards (or use bounded transforms). - Choose a prior/mixture over tuning parameters (variance, bet sizes). - Compute incremental nonnegative factors g_t = 1 + λ_t * (obs - null_mean) - adjustment, multiply to get E_t. - Convert to p_t = min(1, 1/E_t) or form confidence sequences by inversion.4. Implementation steps for permutation/bootstrap: - Fix the adaptive policy deterministically or probabilistically under the null. - Simulate many trajectories of assignments and outcomes under the null (or permute within conditional strata). - Build empirical null of the test statistic; p = fraction ≥ observed.5. Report: time-uniform p-value, or confidence sequence across time (coverage guaranteed regardless of stopping). Provide diagnostics: check calibration via offline sims that replicate adaptivity.

Practical tips:- Prefer martingale/e-values for streaming/anytime decisions and strong optional stopping guarantees.- Use conditional resampling when you need exact finite-sample nulls tied to your specific policy.- Always document the allocation policy and ensure simulations mirror its dependence on past data.

MediumTechnical

45 practiced

Design a simulation framework to test and compare bandit algorithms for a recommendation system. Describe how you would model user heterogeneity, contexts, reward noise, delayed conversions, and non-stationarity. What metrics, visualizations, and experiment controls would you provide to researchers and engineers?

Sample Answer

Overview: Build a modular, event-driven simulator that decouples (1) user population generator, (2) context/environment sampler, (3) bandit agent API, (4) reward & feedback model, and (5) logging/analysis. Run experiments deterministically with seed control and parallelization.

Modeling components:- User heterogeneity: sample user segments with latent features (age, intent, click propensity) and embed a user-specific reward function (linear or nonlinear) with per-user priors; allow continuous covariates and mixture-of-Gaussians for segments.- Contexts: support static (user features) and dynamic context (time-of-day, session history). Provide feature drift and feature-corruption operators.- Reward noise: add heteroscedastic noise (variance function of user/context) and Bernoulli/Poisson outcomes for clicks/conversions. Support realistic calibration to CTR/CVR distributions.- Delayed conversions: model multi-step events with conversion delays drawn from a configurable distribution; implement credit-assignment windowing and delayed reward buffers.- Non-stationarity: implement gradual drift (parameter random walks), abrupt changes (change-points), seasonal cycles, and user churn/arrival processes.

Metrics & visualizations:- Per-step & cumulative regret, cumulative reward, CTR/CVR, calibration (predicted vs observed), fairness/coverage across segments, sample efficiency (time-to-threshold).- Visuals: time-series plots of reward/regret, heatmaps per-segment performance, cohort-based survival/retention curves, waterfall for change-point effects, and confidence band overlays.- Diagnostics: action distribution, uncertainty estimates, delay distributions, and A/B comparator views.

Experiment controls:- Seeded reproducibility, configurable sandbox (number of users, horizon, parallel runs), grid/randomized hyperparameter sweeps, multi-armed treatment groups, and logging of deterministic traces.- Statistical tests: bootstrapped CIs, sequential testing corrections (alpha-spending), and power analysis utilities.- Production realism: ability to replay production logs, inject logging bias, and simulate logging loss or truncated sessions.

Outcomes: Provide ready adapters for agents (epsilon-greedy, UCB, Thompson, contextual RL), standard APIs for reward hooks, and exportable artifacts for downstream analysis and deployment validation.

MediumTechnical

42 practiced

Implement a bootstrap-based exploration method for contextual bandits (bootstrapped Thompson). Build a Python routine that maintains an ensemble of online regressors, uses bootstrap resampling or Poisson weights for updates, and selects arms by sampling one model per decision. Explain trade-offs compared to Bayesian Thompson sampling.

Sample Answer

Approach: maintain an ensemble of K online regressors (e.g., sklearn SGDRegressor or simple linear models). For each interaction, pick one model uniformly at random, use it to predict rewards for each arm given context, choose the arm with highest predicted reward, observe reward, and update all models using bootstrap — either by Poisson(1) weights or by Bernoulli resampling per-model so each model gets a noisy view of the data online.

python

import numpy as np
from sklearn.linear_model import SGDRegressor

class BootstrappedThompson:
    def __init__(self, n_arms, context_dim, K=10, lr=0.01, use_poisson=True):
        self.n_arms = n_arms
        self.K = K
        self.use_poisson = use_poisson
        # one regressor per model; predict expected reward given (arm, context)
        self.models = [SGDRegressor(learning_rate='constant', eta0=lr, max_iter=1, tol=None)
                       for _ in range(K)]
        # initialize with a single dummy fit to set dimensions
        X0 = np.zeros((1, context_dim + n_arms))
        y0 = np.zeros(1)
        for m in self.models:
            m.partial_fit(X0, y0)

    def _featurize(self, context, arm):
        # one-hot arms concatenated with raw context
        arm_onehot = np.zeros(self.n_arms)
        arm_onehot[arm] = 1.0
        return np.concatenate([arm_onehot, context])

    def select_arm(self, context):
        model_idx = np.random.randint(self.K)
        m = self.models[model_idx]
        preds = []
        for a in range(self.n_arms):
            x = self._featurize(context, a).reshape(1, -1)
            preds.append(m.predict(x)[0])
        return int(np.argmax(preds)), model_idx

    def update(self, context, arm, reward):
        x = self._featurize(context, arm).reshape(1, -1)
        for m in self.models:
            # decide multiplicity via Poisson(1) or Bernoulli(0.5)
            if self.use_poisson:
                k = np.random.poisson(1)
            else:
                k = np.random.binomial(1, 0.5)
            for _ in range(k):
                m.partial_fit(x, np.array([reward]))

Key concepts:- Each model sees a stochastic subset/weighted copy of data → ensemble approximates posterior uncertainty.- Sampling one model per decision ≈ sampling from approximate posterior (hence "Thompson-like").

Complexity:- Per step: O(K * n_arms * D) prediction if evaluating each arm per sampled model, but we sample one model then evaluate n_arms with that single model → O(n_arms * D). Update cost O(K * D * expected multiplicity).

Edge cases & practical tips:- Use more expressive base learners or add regularization/learning-rate scheduling.- For large n_arms, cache or parallelize predictions.- If rewards are sparse/noisy, increase K or use larger Poisson mean to increase diversity.

Trade-offs vs Bayesian Thompson Sampling:- Pros: Simple, scalable, works with arbitrary online learners, easy to implement; nonparametric uncertainty from resampling.- Cons: Not a true posterior — can under/overestimate uncertainty depending on model and bootstrap scheme; may require many ensemble members; no closed-form credible intervals; Bayesian methods can be more sample-efficient when good priors/models exist.- Use bootstrap when Bayesian posterior is hard to compute or when using complex models (trees, neural nets) where approximate Bayesian is expensive.

MediumTechnical

34 practiced

Implement UCB1 for a K-armed bandit with rewards in [0,1] in Python. Provide a class with select_arm() and update(arm, reward), initialize by pulling each arm once, and simulate T=500 steps on arms with means [0.1, 0.4, 0.8]. Be careful to avoid log(0) when computing bonuses.

Sample Answer

To implement UCB1, we track counts and average rewards per arm. select_arm returns argmax of empirical_mean + sqrt(2 * log(total_pulls) / pulls_i). We avoid log(0) by using total_pulls = max(1, sum(counts)) (but we initialize by pulling each arm once so log argument >=1). update updates counts and incremental mean.

python

import math
import random

class UCB1:
    def __init__(self, k):
        self.k = k
        self.counts = [0] * k             # number of times each arm was pulled
        self.values = [0.0] * k           # empirical mean reward per arm
        self.total_pulls = 0

    def initialize(self, env):
        # Pull each arm once to avoid division by zero / log(0)
        for a in range(self.k):
            r = env.pull(a)
            self.update(a, r)

    def select_arm(self):
        # If any arm hasn't been pulled (shouldn't happen if initialize called), pick it
        for a in range(self.k):
            if self.counts[a] == 0:
                return a

        total = max(1, self.total_pulls)   # avoid log(0)
        ucb_values = []
        for a in range(self.k):
            bonus = math.sqrt((2 * math.log(total)) / self.counts[a])
            ucb_values.append(self.values[a] + bonus)
        return max(range(self.k), key=lambda i: ucb_values[i])

    def update(self, arm, reward):
        # Incremental mean update
        self.counts[arm] += 1
        self.total_pulls += 1
        n = self.counts[arm]
        # new_mean = old_mean + (reward - old_mean)/n
        self.values[arm] += (reward - self.values[arm]) / n

# Simple Bernoulli environment for simulation
class BernoulliEnv:
    def __init__(self, means):
        self.means = means

    def pull(self, arm):
        return 1.0 if random.random() < self.means[arm] else 0.0

if __name__ == "__main__":
    random.seed(0)
    means = [0.1, 0.4, 0.8]
    env = BernoulliEnv(means)
    T = 500
    k = len(means)
    agent = UCB1(k)
    agent.initialize(env)  # K initial pulls

    rewards = sum(agent.values[a] * agent.counts[a] for a in range(k))
    for t in range(k, T):
        a = agent.select_arm()
        r = env.pull(a)
        agent.update(a, r)
        rewards += r

    print("Counts:", agent.counts)
    print("Estimated means:", [round(v,3) for v in agent.values])
    print("Total reward:", rewards)

Key points:- Initialization by pulling each arm once prevents log(0) and zero division.- Time complexity per select_arm: O(k). Space: O(k).- Edge cases: non-initialized arms, non-Bernoulli rewards in [0,1] still valid. Alternative: use log(total_pulls + 1) explicitly if not initializing.

Unlock Full Question Bank

Get access to hundreds of Multi Armed Bandits and Experimentation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.