Multi-armed bandit

As explained in Experimentation for Engineers

A multi-armed bandit is a sequential decision problem of choosing among alternatives with unknown reward distributions while learning which maximizes cumulative reward.

A multi-armed bandit is a sequential experiment that chooses among candidate system versions while learning which produces the highest business metric. Each version is an arm; each observed click, revenue event, or other measurement is feedback. The goal is not only to identify the best arm, but to route more measurements to it while the experiment runs. section 3.0 section 3.2

This reframes the cost of ordinary A/B testing. Equal randomization spends half its traffic on an underperforming version when one candidate is better. Simply stopping early can create false positives; a bandit instead changes the randomization procedure to preferentially select the arm with stronger realized results while continuing to explore alternatives. section 3.0 section 3.1.1

Epsilon-greedy is a practical bandit policy:

• Explore with probability epsilon by selecting an available arm at random. section 3.2
• Exploit otherwise by selecting the arm with the highest mean business metric observed so far. section 3.2
• Treat the current version and all proposed changes symmetrically; A, B, C, and later candidates are all arms. section 3.2
• Reduce epsilon over time and stop when it falls below a chosen threshold, balancing continued exploration against traffic cost. section 3.2

Choosing among click models

An ad selector can evaluate four click models with click-through rates increasing from 0.005 to 0.011. Under epsilon-greedy, random exploration still samples every model, but exploitation increasingly selects the model with the best observed mean CTR. In the simulation, arm 3 is learned as best and the overall achieved CTR reaches 0.0108, close to that arm’s 0.0110 CTR. section 3.2

Figure 3.11 The ad selector testing multiple click models—or “arms”—using epsilon-greedy. With probability 1-epsilon, the system chooses the model with the highest mean CTR so far. Otherwise (probability epsilon) the system chooses with equal probability from the available models.

This flow shows the operational decision at each measurement: choose the current highest-CTR model with probability 1 − epsilon, or explore uniformly with probability epsilon. section 3.2

How Experimentation for Engineers covers it

How deep it goes

Defines arms and epsilon-greedy, then works through multi-arm selection and simulated CTR outcomes without detailing Thompson sampling.

Examples

Uses an ad selector, click-model arms, simulated clicks, and four alternatives with CTRs from 0.005 to 0.011.

What it assumes

Builds from A/B testing while defining candidate versions as arms and motivating adaptive randomization from zero.

What you can do after

Apply it via epsilon-greedy to allocate production measurements across competing versions while favoring stronger observed metrics.

How it connects

Connects A/B testing, epsilon-greedy, click-through rate, randomization, exploration, and business metrics.

liveBookmanning.com

Read Experimentation for Engineers on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Optimization Algorithms: AI techniques for design, planning, and control problemsA multi-armed bandit is a sequential decision model in which an agent repeatedly chooses among uncertain actions to maximize cumulative reward without changing the underlying state.
• 

  liveBookmanning.com
  Bayesian Optimization in ActionA multi-armed bandit is a sequential decision problem in which an agent repeatedly selects among actions with uncertain reward distributions to balance information gathering and reward seeking.
• 

  liveBookmanning.com
  Delivering Machine Learning Projects: From design to deploymentA multi-armed bandit is an adaptive sequential decision method that allocates trials among alternatives while balancing exploration and reward.
• 

  liveBookmanning.com
  Reinforcement Learning from Human FeedbackA bandit problem is a sequential decision problem in which an action produces an outcome without a multi-step state-transition sequence.

Compare how 5 books explain multi-armed bandit →

Related concepts

• exploitationuses · In optimization and decision-making, exploitation is selecting an option currently believed, based on available information, to yield high value.
• epsilon-greedyaddressed by · Epsilon-greedy is an action-selection strategy that chooses a random action with probability epsilon and otherwise selects the currently highest-valued action.
• policykind of · A policy is a rule, strategy, or mapping that governs or determines decisions, actions, permissions, or behavior under specified conditions.
• Thompson samplingincludes · Thompson sampling is a Bayesian sequential decision method that samples from posterior beliefs about uncertain rewards or outcomes and selects an action according to the sampled values.
• actionproduces · An action is a choice or operation selected or performed by an actor that can affect a system or environment or produce an outcome.

This explainer was generated by Manning's knowledge graph from the text of Experimentation for Engineers. The section links point to the parts of the book it draws on.