Multi-armed bandits quiz

Question 1

In the multi-armed bandit (MAB) problem, what does the exploration-exploitation tradeoff refer to?

Accepted Answer

Balancing the time spent gathering information vs. using current best estimates to maximize reward

Answer

Choosing between deterministic and stochastic reward models

Answer

Selecting between model-based and model-free reinforcement learning

Answer

Minimizing variance vs. minimizing bias in reward estimates

Question 2

In epsilon-greedy for MABs, what is the behavior when epsilon = 0?

Accepted Answer

The algorithm always selects the arm with the highest estimated mean (pure exploitation)

Answer

The algorithm samples all arms uniformly at random

Answer

The algorithm uses UCB indices to break ties between equal estimates

Answer

The algorithm follows a Boltzmann distribution over arm reward estimates

Question 3

How is cumulative regret defined in the stochastic MAB setting?

Accepted Answer

The total expected reward gap between the optimal arm and the arms actually played, summed over T rounds

Answer

The total number of times a suboptimal arm was chosen across T rounds

Answer

The sum of absolute differences between observed rewards and each arm's true mean

Answer

The variance of the arm-selection policy distribution over T rounds

Question 4

Write the UCB1 index for arm i at round t, and explain the role of the confidence bonus term.

Accepted Answer

mu_hat_i + sqrt(2 * ln(t) / n_i)

Answer

mu_hat_i + sqrt(ln(t) / (2 * n_i))

Answer

mu_hat_i + ln(t) / n_i

Answer

mu_hat_i + sqrt(2 * n_i / ln(t))

Question 5

Describe Thompson Sampling for a Bernoulli bandit with K arms. What prior/posterior pair is used and why?

Accepted Answer

Beta(alpha_i, beta_i) prior; increment alpha on success and beta on failure; select arm with highest Beta sample

Answer

Gaussian prior on mean; posterior updated via Kalman filter after each observation

Answer

Dirichlet prior on arm probabilities; select arm by sampling from the Dirichlet

Answer

Uniform prior; select arm by Laplace approximation of the posterior after each reward

Question 6

A slot machine pays $1 or $0 on each pull (Bernoulli reward). Which conjugate Bayesian model is standard for a bandit approach?

Accepted Answer

Beta-Bernoulli: Beta prior, Bernoulli likelihood, posterior stays Beta

Answer

Gaussian-Gaussian: Normal prior, Normal likelihood, exact posterior update

Answer

Gamma-Poisson: Gamma prior, Poisson likelihood for count-valued rewards

Answer

Dirichlet-Multinomial: for multi-outcome per pull

Question 7

State the Lai-Robbins lower bound for regret in stochastic MABs and explain its implication for algorithm design.

Accepted Answer

E[R(T)] >= Omega(ln T) with coefficient driven by KL-divergence — a logarithmic lower bound that optimal algorithms match asymptotically

Answer

O(sqrt(T)) is the best achievable in the worst case across all bandit algorithms

Answer

E[R(T)] >= Omega(T^{2/3}) for bandits with bounded Gaussian rewards

Answer

The lower bound is O(K * ln T) scaling linearly with the number of arms

Question 8

What distinguishes the stochastic MAB setting from the adversarial (non-stochastic) MAB setting?

Accepted Answer

Stochastic rewards are i.i.d. from fixed distributions; adversarial rewards are chosen by an opponent with no distributional constraint

Answer

Stochastic bandits have a finite arm set; adversarial bandits have a continuous arm space

Answer

In adversarial bandits rewards can be negative; in stochastic bandits they are always non-negative

Answer

Adversarial bandits require continuous action spaces; stochastic bandits are always discrete

Question 9

Describe the EXP3 algorithm and state its regret guarantee for adversarial MABs with K arms and T rounds.

Accepted Answer

EXP3 achieves O(sqrt(T * K * ln K)) regret, which is minimax optimal for adversarial bandits

Answer

EXP3 achieves O(ln T) regret, matching the Lai-Robbins lower bound for stochastic bandits

Answer

EXP3 achieves O(T^{2/3}) regret because it must explore linearly in K each round

Answer

EXP3 achieves O(K * sqrt(T)) regret with no logarithmic correction factors

Question 10

How does Sliding Window UCB (SW-UCB) handle non-stationary bandit environments and what is its regret bound?

Accepted Answer

SW-UCB limits statistics to the tau most recent rounds, enabling adaptation to drifting reward distributions

Answer

SW-UCB adds a bonus proportional to arm age to penalize infrequently pulled arms

Answer

SW-UCB replaces the confidence term with a rolling variance estimate over all history

Answer

SW-UCB uses a Bayesian change-point prior and resets posteriors when a change is detected

Question 11

Describe the LinUCB algorithm for contextual bandits. What optimization problem does it solve internally at each step?

Accepted Answer

LinUCB solves ridge regression per arm and selects the arm maximizing the linear posterior mean plus an ellipsoidal confidence bound

Answer

LinUCB solves LASSO regression internally to enforce sparsity in context weights

Answer

LinUCB fits a neural network per arm and adds a Monte Carlo dropout uncertainty bonus

Answer

LinUCB uses a random forest per arm and takes variance of tree predictions as the exploration bonus

Question 12

What is Bayesian regret, and how does it differ from frequentist (worst-case) regret in MAB analysis?

Accepted Answer

Bayesian regret averages over the prior on arm parameters; frequentist regret is a worst-case bound over all possible parameter values

Answer

Bayesian regret is always lower than frequentist regret because the prior concentrates on easy instances

Answer

There is no practical difference — both definitions lead to identical algorithm rankings

Answer

Bayesian regret requires knowing the true prior; frequentist regret only requires observed rewards

Question 13

How does NeuralUCB extend UCB to deep neural networks, and what theoretical guarantee does it provide?

Accepted Answer

NeuralUCB uses the Neural Tangent Kernel to define a gradient-space confidence ellipsoid, yielding O(sqrt(T)) regret under NTK approximations for overparameterized networks

Answer

NeuralUCB trains an ensemble of networks and uses prediction variance across members as the uncertainty bonus

Answer

NeuralUCB uses Monte Carlo dropout at inference time to estimate each arm's reward uncertainty

Answer

NeuralUCB replaces the network with a Gaussian process posterior after each batch of observations

Question 14

Distinguish between the fixed-budget and fixed-confidence formulations of the Best Arm Identification (BAI) problem.

Accepted Answer

Fixed-budget BAI has a pre-specified pull budget and minimizes error probability; fixed-confidence BAI has a pre-specified error tolerance delta and minimizes total pulls

Answer

Fixed-budget BAI minimizes regret; fixed-confidence BAI minimizes the number of arm switches

Answer

Fixed-confidence BAI requires knowing the reward distributions in advance; fixed-budget does not

Answer

They are equivalent — any algorithm optimal for one is optimal for the other via a time-inversion argument

Question 15

What is a combinatorial bandit, and how does the CUCB algorithm handle it?

Accepted Answer

CUCB maintains per-base-arm UCB indices and calls a combinatorial oracle that maximizes f(S) over the confidence upper bounds

Answer

CUCB enumerates all subsets of arms at every round and picks the one with highest expected combined reward

Answer

CUCB reduces super-arm selection to a linear program and solves it exactly at each step

Answer

CUCB requires the combined reward function f to be separable (additive) across base arms

Question 16

How does KL-UCB differ from UCB1, and when does it perform better?

Accepted Answer

KL-UCB uses a tighter KL-divergence-based confidence index that matches the Lai-Robbins lower bound asymptotically; UCB1 uses a looser Hoeffding bound

Answer

KL-UCB is faster to compute because it avoids the square root used in UCB1

Answer

KL-UCB requires Gaussian rewards; UCB1 works for any sub-Gaussian distribution

Answer

KL-UCB and UCB1 have identical asymptotic regret; the difference is only in finite-time constants

Question 17

Describe GP-UCB for bandit optimization over continuous action spaces and state its regret dependence on the kernel.

Accepted Answer

GP-UCB regret is O(sqrt(T * gamma_T)) where gamma_T is the maximum information gain — O(log^{d+1} T) for the squared-exponential kernel

Answer

GP-UCB regret is O(sqrt(T * K)) since it discretizes the continuous space into K bins

Answer

GP-UCB requires i.i.d. observations and achieves O(ln T) regret under the Gaussian likelihood

Answer

GP-UCB has no finite-T regret bounds; only asymptotic consistency results are known

Question 18

How is Thompson Sampling adapted for Gaussian rewards with unknown mean and known variance sigma^2?

Accepted Answer

Use a Gaussian prior N(mu_0, sigma_0^2) per arm; update to exact Gaussian posterior after each pull; select arm with highest posterior sample

Answer

Use a Beta prior and update using the sign of the reward (positive = success, negative = failure)

Answer

Use a Gamma prior on the precision; sample from the induced t-distribution for arm selection

Answer

Use a uniform prior; select the arm whose draw from the prior exceeds all other draws

Question 19

What is the Whittle index policy for restless bandits, and under what condition is it asymptotically optimal?

Accepted Answer

Whittle index is a per-arm subsidy-based index that decouples arms; selecting the m highest-index arms is asymptotically optimal under the indexability condition

Answer

Whittle index policy is always exactly optimal for any finite K with no additional conditions

Answer

Whittle index is computed by solving a global MDP over all arms jointly and extracting per-arm values

Answer

Whittle index requires all arms to have identical state spaces and transition dynamics

Question 20

Explain the Successive Elimination algorithm for MAB best arm identification and how it achieves near-optimal sample complexity.

Accepted Answer

Successive Elimination maintains confidence intervals and eliminates arms whose UCB falls below any other arm's LCB, achieving near-optimal sample complexity

Answer

Successive Elimination halves the arm set randomly each phase regardless of observed rewards

Answer

Successive Elimination pulls arms round-robin and removes the arm with the lowest empirical mean each round

Answer

Successive Elimination requires knowing the gaps Delta_i in advance to set phase lengths correctly

Question 21

Describe Linear Thompson Sampling (LinTS) and its regret guarantee for contextual linear bandits.

Accepted Answer

LinTS maintains a Gaussian posterior on the linear weight vector and samples theta at each step, achieving O(d * sqrt(T) * polylog(T)) regret

Answer

LinTS achieves O(d^2 * T) regret because sampling from the posterior introduces additional variance

Answer

LinTS is only applicable when contexts are drawn i.i.d. from a known distribution

Answer

LinTS and LinUCB are identical in regret — they differ only in computational cost per step

Question 22

What are the key practical advantages of bandit algorithms over classical A/B testing for online product experiments?

Accepted Answer

Bandit algorithms reduce opportunity cost by routing more traffic to better variants during the experiment, unlike fixed-split A/B tests

Answer

Bandit algorithms always converge faster to the correct winner because they use Bayesian inference

Answer

Bandit algorithms eliminate the need for any post-experiment statistical analysis

Answer

Bandit algorithms are strictly better than A/B testing in all scenarios including high-arm-count experiments

Question 23

What is the Inverse Propensity Score (IPS) estimator in bandit off-policy evaluation, and what is its key limitation?

Accepted Answer

IPS is unbiased under the overlap condition but suffers high variance when importance weights are large; doubly-robust estimators reduce variance while retaining unbiasedness

Answer

IPS is biased by default and requires bias-correction terms in all practical applications

Answer

IPS requires the behavior policy to be the uniform random policy for the estimator to be consistent

Answer

IPS can only be applied when the target policy is deterministic and selects one arm per context

Question 24

What is a decaying epsilon schedule for epsilon-greedy, and why does epsilon_t = 1/sqrt(t) have theoretical appeal?

Accepted Answer

epsilon_t = 1/sqrt(t) limits total exploration to O(sqrt(T)) and has theoretical appeal; the optimal decaying schedule achieves O(T^{2/3}) regret, worse than UCB asymptotically

Answer

epsilon_t = 1/sqrt(t) yields O(sqrt(T)) regret exactly matching UCB1

Answer

epsilon_t = 1/sqrt(t) yields O(ln T) regret, matching the Lai-Robbins lower bound

Answer

Any decaying epsilon schedule yields identical asymptotic regret regardless of the specific decay rate

Question 25

What are batched bandits, and how does the number of batches B affect achievable regret?

Accepted Answer

With B = O(log log T) batches regret matches the sequential setting at O(sqrt(T * ln T)); fewer batches lead to worse O(T^{2/3}) regret

Answer

Batched bandits always achieve the same regret as sequential bandits regardless of B

Answer

Even a single batch is sufficient to achieve O(sqrt(T)) regret if the exploration phase is sized correctly

Answer

Batched bandits have regret O(B * sqrt(T)) so more batches always improve performance linearly

Question 26

What happens to regret in contextual bandits when the reward model is misspecified (e.g., rewards are non-linear but LinUCB is applied)?

Accepted Answer

Under epsilon-misspecification LinUCB regret becomes O(d * sqrt(T) + epsilon * T), which can be linear in T for large epsilon

Answer

Misspecification causes a constant additive penalty but regret remains O(d * sqrt(T))

Answer

Misspecification causes LinUCB to explore more aggressively, which actually reduces regret over time

Answer

LinUCB is robust to any polynomial misspecification due to the ridge regularization term

Question 27

How do dueling bandits relate to RLHF (Reinforcement Learning from Human Feedback)?

Accepted Answer

RLHF uses dueling bandit principles: pairwise preference feedback replaces scalar rewards, and the Condorcet winner corresponds to the optimal LLM output

Answer

Dueling bandits use scalar rewards between 0 and 1 to rank arms, differing from the RLHF pairwise setup

Answer

RLHF is a contextual bandit problem, not a dueling bandit problem, because the prompt serves as context

Answer

Dueling bandits are relevant only for ranking problems and have no connection to language model training

Question 28

What is the regret of a policy that always selects the arm with the highest true mean reward (the oracle policy)?

Accepted Answer

The oracle policy has exactly zero regret because it always selects the true best arm

Answer

The oracle policy has O(ln T) regret because it must still explore during early rounds

Answer

The oracle policy has O(sqrt(T)) regret due to stochastic reward variance

Answer

The oracle policy has O(K) regret from the initial round of pulling each arm once

Question 29

In Softmax (Boltzmann) exploration for MABs, how does the temperature parameter tau control the exploration-exploitation balance?

Accepted Answer

Lower tau concentrates probability on the best arm (exploitation); higher tau spreads probability uniformly (exploration)

Answer

Higher tau concentrates probability on the best arm (more exploitation); lower tau spreads probability uniformly (more exploration)

Answer

Tau controls only the variance of reward estimates, not the arm selection probabilities

Answer

Softmax with tau = 1 is equivalent to epsilon-greedy with epsilon = 0.1 for any reward scale

Question 30

What is the H_1 complexity measure for pure exploration in MABs, and how does it determine sample complexity lower bounds?

Accepted Answer

H_1 = sum_i 1/Delta_i^2 and sample complexity is Omega(H_1 * ln(1/delta)), reflecting that small-gap arms dominate the difficulty

Answer

H_1 = K / Delta_min^2, treating all arms as having the hardest gap Delta_min

Answer

H_1 = ln(K) / Delta_min^2, capturing both the number of arms and the minimum gap jointly

Answer

H_1 is only defined for the two-arm case; multi-arm BAI uses a different complexity measure

Test yourself