Multi-Armed Bandit Interview Questions: Regret, Exploration, and Offline Evaluation

Multi-armed bandit interview questions ask how to learn which action works while still choosing actions that produce useful rewards. Unlike a fixed experiment, the policy can adapt its choices as evidence accumulates. That creates an exploration problem and a logging problem: you observe the reward for the action you chose, not every action you could have chosen.

The strongest answers connect regret, exploration, and offline evaluation. A policy that looks successful on its own selected traffic may not be better, and a new policy cannot be evaluated fairly from logs that never tried its preferred actions.

This guide uses a recommendation example with simple numerical rewards. The numbers are illustrative, and the assumptions behind each estimator are stated explicitly.

What is a multi-armed bandit?

At each decision, a learner chooses one of several actions, often called arms, and observes a reward for the chosen action. It uses previous observations to improve later choices. The challenge is balancing exploitation of what currently looks best with exploration that reduces uncertainty.

For example, a recommendation slot can choose among several articles and observe whether the selected item is clicked. The learner does not observe whether the same user would have clicked every unshown article. Those missing counterfactual outcomes are central to both learning and evaluation.

In a contextual bandit, the policy uses information available before the decision, such as user or request features. A non-contextual policy estimates an overall action value without conditioning the decision on such features.

Define the action set and reward carefully. A click, a completed purchase, and long-term satisfaction are different objectives. Optimizing the easiest immediate signal can produce behavior that conflicts with the product's broader goals.

What is regret?

Regret compares the policy's reward with a defined reference, often the best action under a stationary non-contextual model. Expected pseudo-regret can be expressed through the gap between the best arm's mean reward and the mean reward of the chosen arm.

Suppose arm A has expected reward 0.08 and arm B has expected reward 0.05. Choosing B has an expected gap of 0.03 for that decision relative to A. Choosing B 100 times contributes an expected gap of three rewards under these simplified fixed-mean assumptions.

Best expected reward: 0.08
Chosen arm expected reward: 0.05
Expected regret for this pull: 0.03
100 such pulls: expected regret 3

Actual realized rewards vary. A particular pull of B may succeed while A would not have, but you generally do not observe both outcomes for that same decision. Do not confuse expected regret under a model with an observed per-user counterfactual.

How does epsilon-greedy work?

An epsilon-greedy policy usually chooses the currently estimated best action most of the time and explores according to a specified randomization rule with probability epsilon. Define whether exploration samples all arms or only alternatives, because that affects exact action probabilities.

With three arms and uniform exploration over all arms, an arm that is uniquely greedy has probability 1 - epsilon + epsilon/3. Each other arm has probability epsilon/3. Those probabilities matter if you later use the logs for offline evaluation.

The method is simple and provides exploration, but it does not automatically focus exploration on the most uncertain promising actions. A fixed epsilon also continues spending a fraction of decisions on exploration even after substantial learning.

In an interview, discuss initialization, ties, changing environments, and how epsilon is chosen or scheduled. Do not present one arbitrary value as universally optimal. The right setting depends on reward noise, traffic, action count, and the cost of trying a poor action.

How do UCB and Thompson sampling differ?

Upper Confidence Bound methods add an uncertainty-related bonus to estimated reward under their assumptions. An action with limited evidence can remain attractive because its plausible value is still high. The exact confidence formula depends on the reward model and algorithm.

Thompson sampling maintains a model of uncertainty and samples from it to choose an action. For a simple Bernoulli reward example, Beta distributions can represent uncertainty about each arm's success probability. After observing success or failure, update the corresponding posterior parameters.

Policy	Exploration mechanism	Question to ask
Epsilon-greedy	Explicit random exploration	Are action probabilities logged correctly?
UCB	Optimism through an uncertainty bonus	Do the confidence assumptions fit the rewards?
Thompson sampling	Sampling from modeled uncertainty	Is the prior and likelihood appropriate?

These are families of methods, not interchangeable guarantees. Nonstationarity, delayed feedback, dependent observations, and changing action sets can require adaptations. Explain the setting before comparing regret claims.

What changes in a contextual bandit?

The best action may depend on the context. An article that works well for a beginner may be less useful for an experienced reader. A contextual policy uses pre-decision features to choose among available actions.

Keep feature timing explicit. A feature derived from whether the user clicked after the recommendation is not available when choosing the recommendation. Using it during training or evaluation creates leakage.

Action availability also matters. If one item was unavailable for a particular request, an offline evaluator should not pretend the logging policy could have selected it. Log the candidate set or enough information to reconstruct the valid action space.

The context can improve decisions, but it also makes support and generalization harder. A policy may have many examples for an action overall and almost none in the subset of contexts where a new policy wants to use it.

What must the logging policy record?

At minimum for common off-policy evaluation approaches, record the context available at decision time, chosen action, observed reward under its defined window, and the probability that the behavior policy assigned to that chosen action. Also record policy version and action availability when needed to interpret the decision.

The probability is often called the propensity. It must reflect the actual randomized selection process, including exploration and any later filtering or reranking that changes what was shown. Logging a nominal epsilon is not necessarily enough to reconstruct the final action probability.

Use a stable decision identifier to join delayed rewards. Define how repeated events, missing feedback, and reward-window expiration are handled. A duplicated click join can make a policy appear better without any change in user behavior.

Data quality is part of the statistical method. An unbiased estimator formula cannot repair incorrect propensities or rewards joined to the wrong decisions.

Why can a naive offline comparison be biased?

Suppose the old policy showed article A mostly to highly engaged users and article B mostly to new users. Comparing raw click rates by article mixes action effects with the contexts selected by the policy.

A new policy may choose different actions for those contexts, but the log contains only the outcomes for the old choices. Treating unobserved outcomes as zero is wrong, and simply dropping all disagreements can produce a biased or inefficient comparison depending on the logging design and estimator.

The solution requires explicit assumptions and an appropriate off-policy estimator, not just a larger dataframe. Ask how the data was collected and whether the behavior policy explored the actions the target policy needs.

This is the central distinction from ordinary supervised evaluation: labels for every candidate action are not available. The policy determines which feedback enters the dataset.

How does inverse propensity scoring work?

For a target policy pi and behavior policy b, a basic IPS estimate averages observed rewards weighted by pi(action | context) / b(action | context). Under the required assumptions, weighting accounts for how differently the two policies select observed actions.

IPS contribution = observed reward
                 × target probability of chosen action
                 ÷ behavior probability of chosen action

Suppose a logged action had behavior probability 0.20, the target would choose it with probability 0.50, and the observed reward was one. Its contribution is 2.5 before averaging over all logged decisions. An individual contribution greater than one is possible even for binary rewards; it is a weighted estimator term, not a predicted click probability.

The support condition is essential: the behavior policy must assign positive probability wherever the target policy acts in relevant contexts. If an action was impossible under the log-generating policy, weighting cannot invent its missing outcomes.

Why can IPS have high variance?

Small behavior probabilities produce large weights. A few rare observations can dominate the estimate, making it unstable even when the estimator is unbiased under its assumptions. Report uncertainty and weight diagnostics rather than only one reward number.

Clipping weights can reduce variance but generally introduces bias. Self-normalized importance sampling changes the estimator and its properties. Doubly robust methods combine a reward model with importance weighting, but still require careful assumptions and implementation; the name does not remove all data-quality or support problems.

Inspect effective sample size or related diagnostics, weight distributions, and performance by relevant slices. A million logged decisions may contain little usable evidence for the actions and contexts a very different target policy emphasizes.

In an interview, explain the trade-off in plain language: correcting for rare action selection makes each rare example count more, but that also makes the result sensitive to a small number of observations.

How is replay evaluation different?

Replay-style evaluation can accept logged events when the target policy's action matches the recorded action, under an appropriate randomized logging setup. The cited contextual-bandit research explains conditions under which this can provide an unbiased evaluation.

The method can discard many events, especially with large action spaces, so data efficiency matters. Its assumptions about how actions were randomized and how the target policy evolves must be respected.

Do not apply a replay rule blindly to arbitrary deterministic production logs and call the result unbiased. The collection process is part of the estimator's validity. State the logging design before selecting the method.

For an adaptive target policy, keep the order and learning updates consistent with the evaluation procedure. Updating on feedback from actions the policy would not have taken changes the experiment you claim to simulate.

What happens when rewards are delayed or the world changes?

Delayed rewards mean recent decisions have incomplete feedback. Treating all pending outcomes as failures biases estimates toward actions whose rewards arrive quickly. Define a reward window and distinguish pending from observed zero.

Nonstationarity means arm values can change over time. An article becomes outdated, a promotion ends, or user preferences shift. Methods that average all historical observations equally may adapt too slowly. Sliding windows, discounting, or change-aware approaches are options, but each changes the assumptions and trade-offs.

Also consider actions that affect future context. A simple bandit model may be inadequate when today's recommendation substantially changes long-term user state or when repeated actions have delayed cumulative effects. Explain the limitation rather than promising that a one-step reward model solves every sequential decision problem.

How should you compare a bandit with an A/B test?

A fixed randomized experiment is often used to estimate a treatment effect under a defined design. A bandit adaptively allocates actions to learn and earn reward. They can serve different goals, and adaptive allocation complicates naive inference.

Ask whether the priority is efficient reward during learning, a precise causal comparison, or a constrained rollout. Also state any safety or product constraints that restrict exploration. A bandit should not explore an action that the product has already ruled out as unacceptable.

For a practical interview exercise, simulate three arms with known means, compare policies over repeated runs, and plot cumulative reward and regret with variation. Then create randomized logs and evaluate a target policy using IPS, checking propensities and support. This connects online learning with the evidence needed to assess a policy before deployment.

Sources and Further Reading

• Microsoft Research: unbiased offline contextual-bandit evaluation
• Original offline-evaluation paper
• Vowpal Wabbit: offline policy evaluation
• Bandit Algorithms textbook

Research checked September 24, 2026. Numerical examples assume the simplified reward and logging models stated in the text; estimator guarantees depend on their full assumptions.