← Back to list
AI & Data
#멀티암드밴딧#탐험활용#톰슨샘플링#UCB#온라인학습
Last updated · 2026-11-19

Multi-Armed Bandit (MAB) and Optimal Exploration–Exploitation Allocation

1. Overview

Definition: The Multi-Armed Bandit (MAB) is a sequential decision-making problem — and a family of algorithms — in which, at each time step, one selects one of several options (arms) whose reward distributions are unknown, observes the resulting reward, and repeats, seeking to maximize cumulative reward (equivalently, minimize cumulative regret) by balancing exploration (gathering information about uncertain options) and exploitation (choosing the option that currently looks best).

The name comes from the gambler standing before several slot machines (each a "one-armed bandit"). Every arm pays out with a different — but unknown — probability, and within a limited number of pulls the gambler must constantly weigh the cost of learning which arm is good against the gain of harvesting rewards from the arm judged best. In the digital era this abstraction became the mathematical backbone of nearly every problem requiring "repeated choice among uncertain alternatives within limited opportunities" — ad-creative selection, recommendation, pricing, clinical-trial patient allocation, and more.

The essence of MAB is the exploration–exploitation dilemma. Exploit only, and you may be trapped by a lucky (or unlucky) early observation and forever miss a genuinely better option; explore only, and you waste resources on options already proven inferior. A good bandit algorithm mathematically implements the principle of "try sufficiently uncertain options more often, but cut losses quickly once evidence makes inferiority clear." The performance measure here is regret — the cumulative gap between the expected reward of always choosing the optimal arm and the reward the algorithm actually obtained — and the better the algorithm, the more slowly regret grows with time T (theoretically O(log T)).

Background and Necessity

A conventional A/B test splits users in fixed proportions (e.g., 50:50) and sends traffic to the inferior arm too, all the way to the end of a fixed period, declaring a winner for statistical significance at close. This is excellent for cleanly estimating causal effects, but it cannot escape the opportunity cost (experimentation regret) of exposing half of users to a clearly bad arm for the entire duration. Especially when there are dozens or hundreds of creatives, when creatives are short-lived because trends move fast (news headlines, fashion items), or when opportunities are scarce (clinical trials), "splitting fairly to the end" is inefficient.

MAB reduces this loss by reflecting learning into allocation immediately while experimenting. It routes ever more traffic to options that look good, so the experiment's own cumulative loss is small, achieving "convergence to the best arm" and "loss minimization" at once. Options can also be added or removed mid-stream, giving flexibility in dynamic environments. For these reasons, in areas like recommendation, advertising, and personalization — where alternatives are many and change fast — MAB has become a core technique that complements or replaces fixed A/B testing.

Problem Framing from the Professional Engineer's View

In an essay, writing MAB merely as "an algorithm that picks the good one more often" is a failure. The key axes are ① framing the exploration–exploitation dilemma as regret minimization, ② the principled differences and convergence guarantees of ε-greedy, UCB, and Thompson sampling, ③ extensions to real-world constraints such as context, non-stationarity, and delayed rewards, and ④ the division of roles with A/B testing and the trade-off in statistical inference, developed quantitatively and structurally.

2. Overall Structure and Core Components

MAB is a single online learning loop of "select → observe reward → update belief → select again." The structure below shows the agent–environment interaction and where the exploration–exploitation policy operates.

flowchart TD
  P["Policy: exploration-exploitation balance rule"] --> SEL["Select arm (a_t)"]
  SEL --> ENV["Environment: reward distribution unknown"]
  ENV --> R["Observe reward (r_t)"]
  R --> UPD["Update estimates (mean, uncertainty)"]
  UPD --> P
  UPD --> REG["Accumulate regret measurement"]
  CTX["Context: user, time features"] -.-> P
  REG -.->|"performance eval"| EVAL["Offline evaluation, IPS/DR"]

A bandit problem has four components. First, the set of arms are the alternatives the agent can choose, such as ad creatives, recommended items, or UI variants. Second, the reward is the outcome of each choice; its distribution differs by problem — click or not (Bernoulli), dwell time or revenue (continuous). Third, the policy is the rule that decides the next option given observations so far, and here the exploration–exploitation strategy is embedded. Fourth, regret is the performance metric, the cumulative loss versus the retrospectively known optimal arm.

A. The Exploration–Exploitation Dilemma and Regret

The exploration–exploitation dilemma runs through everything in MAB. Each option has a current estimated mean reward and the uncertainty of that estimate (larger when samples are few). Exploitation prefers the option with high estimated mean; exploration prefers the option with large uncertainty (not yet sufficiently tried). The key insight is that "an option with high uncertainty may actually be the best, so it is worth trying a few more times before ruling it out."

Regret quantifies this. Let the expected reward of option i be μ_i and the optimal option be μ*; after T selections, expected regret is defined as Σ(μ* − μ_{a_t}). A naive ε-greedy (fixed ε) keeps choosing arms at random with probability ε forever, so regret grows linearly (O(T)), whereas algorithms that handle uncertainty carefully, like UCB and Thompson sampling, increasingly avoid inferior arms, suppressing regret to logarithmic (O(log T)). For example, with two creatives of 10% and 5% click-through rate shown one million times, a fixed 50:50 experiment loses about 25,000 clicks on the inferior creative, whereas a good bandit converges with only a few thousand clicks lost.

B. Estimation and Belief Update

The heart of a bandit is the process of updating beliefs about each option with data. At its simplest, keep a sample mean reward per option and update in O(1) per observation via the incremental-mean formula Q ← Q + (r − Q)/n. In non-stationary environments, use a fixed learning rate α for an exponentially weighted moving average Q ← Q + α(r − Q) to forget the past.

A more refined approach maintains not only the mean but the entire uncertainty as a distribution. For Bernoulli rewards (click/no-click), place a conjugate prior Beta distribution on each option and accumulate successes and failures into the α and β parameters, so the posterior updates in closed form. Maintaining a "distribution" rather than a "point estimate" lets you naturally exploit uncertainty for exploration, as in the Thompson sampling described below.

C. Context and the Evaluation Problem

In reality, "which creative is good" differs by user. A good ad for a woman in her twenties differs from one for a man in his fifties. The contextual bandit reflects this: at each step it receives a feature vector x_t of user, time, and device, estimates "the expected reward of each option in this context" with a linear model or neural network, and layers an exploration rule on top (LinUCB, neural bandits, etc.). Whereas the context-free classic bandit finds the "best arm on average," the contextual bandit finds the personalized best arm.

Another hard problem is offline evaluation. A bandit does not observe the reward of options not chosen (the counterfactual), so it is hard to evaluate a new policy from past logs alone. For this, Inverse Propensity Scoring (IPS) and Doubly Robust estimators are used, and the probability (propensity) of each choice must be logged alongside it to enable unbiased offline evaluation. This design is a core decision that governs bandit reliability in practice.

3. Main Algorithms and Operating Procedure

The representative algorithms are distinguished by how they inject exploration. The process diagram below shows how the three families branch within one decision cycle.

flowchart TD
  START["Round t begins"] --> HOW{"exploration injection method"}
  HOW -->|"random mixing"| EG["ε-greedy: random with prob ε, best with 1-ε"]
  HOW -->|"optimistic bonus"| UCB["UCB: pick max of mean + confidence-upper bonus"]
  HOW -->|"posterior sampling"| TS["Thompson sampling: sample each arm posterior, pick max"]
  EG --> ACT["execute choice, observe reward"]
  UCB --> ACT
  TS --> ACT
  ACT --> UP["update estimates, posterior"]
  UP --> START

A. ε-greedy — The Simplest Exploration

ε-greedy chooses an arm at random with probability ε (exploration) and the arm with the highest current estimated mean with 1−ε (exploitation). It is so simple that an implementation fits in one line, which is why it is widely used as an industry-standard baseline. Yet it has two weaknesses. First, if ε is fixed, it keeps incurring ε-worth of loss even after learning is complete, so regret grows linearly. To mitigate this, use an ε-decay variant that shrinks ε over time. Second, because exploration is "fully random," it tries clearly bad options and promising ones equally, which is inefficient.

Even so, ε-greedy remains in steady use in practice because of its robustness and explainability. It makes almost no distributional assumptions, and even in non-stationary environments ε worth of exploration is always guaranteed, so it does not miss environmental change. As in Netflix's broad application of ε-greedy-family methods to early artwork (thumbnail) personalization to lift viewing engagement, it remains a top candidate wherever "operational simplicity and stability" matter more than "perfect optimality."

B. UCB — Optimism Toward Uncertainty

UCB (Upper Confidence Bound) implements the principle of "optimism in the face of uncertainty." For each option it computes the estimated mean plus a confidence-upper bonus (a value larger when observations are fewer, e.g., √(2 ln t / n_i)) and selects the option whose sum is largest. Less-tried options have large bonuses and are naturally selected, and once tried enough that uncertainty shrinks, the bonus falls and they compete on the mean alone. That is, exploration occurs not randomly but directionally, toward higher information value.

UCB's strengths are that a theoretical regret guarantee (O(log T)) is proven and that it operates deterministically without randomness, making it easy to reproduce and debug. Its weaknesses are that the bonus term is sensitive to reward-distribution assumptions (boundedness, etc.) and that tuning and computation become burdensome when options number in the thousands or tens of thousands or when context is high-dimensional. Its contextual extension, LinUCB, computes confidence intervals from a linear model's covariance and was widely used in news recommendation and the like.

C. Thompson Sampling — Sampling from the Posterior

Thompson sampling is a Bayesian approach that draws one sample from each option's posterior distribution of reward and selects the option whose sampled value is largest. For Bernoulli rewards, it samples a success rate from each option's Beta posterior and compares. Options with large uncertainty have wide posteriors, so a large value is occasionally drawn and they get explored; as evidence accumulates and distributions narrow, the probability of drawing inferior options plummets. Exploration and exploitation balance naturally and stochastically.

In practice, Thompson sampling has small average regret, is robust to delayed rewards and batch updates, and is surprisingly simple to implement, making it one of the most preferred algorithms. Google, Microsoft, and others applied it broadly in ad and recommendation systems, and many reports find it more stable than UCB in content optimization handling hundreds of creatives at once. That said, because one must define a prior and likelihood for the reward model, atypical rewards require modeling effort.

D. Algorithm Comparison

The three families differ in "where they draw exploration from." The table below compares key characteristics, but why those differences arise matters more than the numbers themselves. ε-greedy's linear regret comes from "a fixed proportion of mindless exploration"; UCB's and Thompson's logarithmic regret comes from "directed exploration proportional to uncertainty."

Aspect ε-greedy UCB Thompson Sampling
Exploration method random with prob ε confidence-upper bonus (deterministic) posterior sampling (stochastic)
Regret order O(T) (fixed ε) / improvable O(log T) O(log T)
Distributional assumptions almost none boundedness, etc. required prior, likelihood required
Delayed/batch rewards robust somewhat fragile robust
Implementation difficulty very low low medium
Explainability high high medium (stochastic)

4. Comparison and Application Cases

A. Relationship with A/B Testing — Division of Roles, Not Replacement

MAB and A/B testing are often presented as opposites, but in reality they are complementary tools with different goals. The goal of A/B testing is to keep traffic in fixed proportions to the end and obtain clean causal effects and confidence intervals. The goal of MAB, by contrast, is to reduce loss (regret) during the experiment and converge quickly to the best arm, so the moment traffic concentrates on the winner, the ability to "precisely estimate the effect size of the inferior arm" declines. That is, with MAB it is hard to state afterward, as a confidence interval, "B was exactly X% better than A."

Hence the practical principle is clear. If the goal is learning (precise effect estimation, a decision-making basis), use A/B testing; if the goal is revenue optimization (loss minimization, fast allocation), use MAB. When creatives are short-lived (headlines, promotion banners) or alternatives number in the dozens or more, MAB fits; when the long-term effect of a core feature must be rigorously verified, A/B testing fits. A hybrid that "filters candidates by A/B first, then optimizes allocation with MAB" is also common.

B. Industry Application Cases

Applications are broad. In digital advertising, Thompson sampling and UCB are used as standard to progressively increase exposure to the highest-CTR creative among dozens. At a scale of hundreds of millions of impressions daily, a 1% CTR improvement maps directly to enormous revenue, so "the speed of cutting inferior creatives" is revenue itself. In news and content recommendation, there are public cases where portals optimized per-user article placement with LinUCB-family contextual bandits and significantly lifted click-through rates.

In clinical trials, bandit ideas are used in response-adaptive randomization, assigning patients increasingly to the ethically more effective treatment arm. Since each patient is scarce and the ethical cost is high, MAB's goal of "minimizing experimentation regret" is directly tied to lives. Beyond these, bandits are used in dynamic pricing (exploring several price tiers to maximize revenue), recommendation-system cold start (allocating exposure to new items), and hyperparameter search.

Domestically too, bandit adoption is spreading in the personalization areas of e-commerce, OTT, and portals. For example, preparing dozens of banner/coupon creatives on a product detail page and optimizing exposure with a bandit lets you weigh the entire creative pool in real time, without the bottleneck of fixed A/B testing's "verify two or three at a time over several weeks." In particular, for short-lived creatives like promotions and seasonal items, by the time an A/B test secures statistical significance the season is already over, so the bandit's advantage of "allocate immediately while learning" stands out. Conversely, changes that are hard to reverse and whose long-term impact must be rigorously verified, like a checkout flow change, are still safer with a fixed experiment — so organizations should agree in advance on the decision criteria (reversibility of the change, creative lifespan, need for effect estimation) for the two tools.

5. Advanced — Extensions to Context, Non-Stationarity, and Reinforcement Learning, and Recent Trends

MAB extends to more general sequential decision-making, and at that boundary recent research is active. First, the extension from contextual bandits to deep-neural-network-based (neural) bandits. To escape linear assumptions and learn complex user–creative interactions while preserving exploration, techniques approximate uncertainty with dropout, ensembles, or Bayesian neural networks. However, one must manage the risk that the neural network's overconfidence causes exploration to collapse prematurely.

Second, non-stationary bandits. In a reality where user tastes and trends change over time, one must not trust past data infinitely. Sliding-window UCB, discounted UCB, and change-point-detection-combined methods track environmental change while "appropriately forgetting the past." This also touches model-drift monitoring.

Third, the relationship with reinforcement learning (RL). A bandit can be seen as a special RL in which "there is no state, or the choice does not affect the next state." When choices change the environment state and rewards are delayed and accumulate, it becomes full RL (an MDP), and the bandit's exploration–exploitation principles (UCB, Thompson) carry over directly as RL exploration strategies. Recently, trends include modeling response-candidate selection as a bandit in LLM-based recommendation and dialogue optimization, and grafting bandit theory onto reward-model search in RLHF. Fourth, with the advance of offline policy evaluation (OPE) in ad and recommendation platforms, an MLOps practice is taking hold of safely pre-verifying new bandit policies "without live traffic" through IPS, DR, and switch estimators.

6. Considerations and Implications

When designing and evaluating MAB adoption from the professional engineer's view, consider the following in balance.

  • Judging fit of purpose (learning vs. revenue): Bandits are strong at loss minimization but weak at precise effect-size estimation. Split so that strategic changes needing "evidence-based decisions" use A/B testing and "operational optimization" uses bandits, but a portfolio strategy that weaves the two in a hybrid is desirable.

  • Trade-off with statistical inference: The adaptive data created as traffic concentrates on the winner biases simple means and standard errors. Post-hoc analysis needs IPS and doubly robust estimation and reliability correction, which presuppose logging the choice probability (propensity). Omit this design and you get a black box that is "optimized but impossible to explain or verify."

  • Managing non-stationarity and delayed rewards: If rewards arrive late (purchase-conversion delay) or distributions shift, a naive bandit concentrates on the wrong option. You need algorithm and cadence design matched to environmental traits — windowing, discounting, batch updates, and choosing Thompson sampling, which is robust to delayed rewards.

  • Fairness, safety, and guardrails: A bandit that maximizes only revenue may systematically disadvantage certain groups (fairness) or concentrate on extreme creatives and harm brand and user experience. Put in safeguards with minimum-exposure guarantees (a floor of traffic to each option), guardrail-metric monitoring, and exploration caps.

  • Operational complexity and organizational capability: Contextual and neural bandits demand feature pipelines, real-time inference, and an offline-evaluation system. A maturity roadmap that starts with a simple method like ε-greedy, advances gradually, and integrates with the experimentation platform, MLOps, and monitoring determines success.

References


In one line: The multi-armed bandit is a sequential decision-making technique that minimizes cumulative regret by balancing exploration and exploitation across options with uncertain rewards; ε-greedy, UCB, and Thompson sampling are its representative algorithms, and it complements A/B testing in advertising, recommendation, pricing, and clinical domains where one must converge to the best arm quickly while reducing loss.