Does the learner observe every arm's outcome?

Usually only the selected arm's reward.

Must reward distributions be Bernoulli?

No; that is one convenient example.

Does stochastic imply stationary?

Not universally. The basic model is stationary, while extensions allow distributions to change.

AI Glossary / Reinforcement learning and robotics / Intermediate

Stochastic multiarmed bandit

Definition

A stochastic multiarmed bandit is a sequential decision problem in which a learner repeatedly chooses among actions with uncertain rewards. Each action, or arm, has a probability distribution that determines its reward. In the basic stationary model, these distributions remain fixed but are initially unknown. The learner balances gathering information about alternatives with choosing actions that appear rewarding.

What it means

The learner normally observes the reward only for the action it selected. It does not receive the rewards that every unchosen action would have produced on that round. This partial feedback creates the exploration problem.
Stochastic describes the reward-generation model. It does not require the learner to choose randomly on every round. An action-selection algorithm may use deterministic rules based on past observations or may randomize. The basic model also differs from a full sequential-control problem: actions do not move the system through an additional evolving state that determines future opportunities.

How it works

At each round, the learner selects an arm, observes a reward sampled from that arm's distribution, and updates its information. A simple estimate of an arm's mean is the average of the rewards observed from it. More sophisticated methods account for uncertainty when choosing the next arm.
Exploration can reveal that an apparently inferior arm is actually better. Exploitation uses current evidence to favor high estimated reward. Different algorithms, such as upper-confidence-bound methods and Thompson sampling, implement this tradeoff differently.
A common performance measure is expected regret relative to always selecting an arm with the highest true mean. For a stationary finite-armed problem, this can be expressed as the sum of each arm's mean-reward gap multiplied by its expected number of selections. This comparator is an informed benchmark, not an action the uninformed learner can necessarily identify immediately.
Real applications may violate stationarity or require context, delayed feedback, budgets, or other constraints. A suitable extended model is needed when those features materially affect decisions.

Three practical examples

Interface experiments: allocate comparable opportunities among variants when the chosen outcome can be measured consistently.
Simulation studies: compare exploration algorithms on actions with known synthetic reward distributions.
Resource trials: learn which of several fixed alternatives gives better average outcomes under a stable experimental setup.

Think of it this way

Think of repeatedly choosing among unfamiliar tools whose results vary. Trying a tool teaches you something about it, but each trial also uses an opportunity that could have gone to a better tool. A good strategy considers both what it earns now and what it learns for later choices.

Worked example

Consider a fictional stationary bandit with three Bernoulli arms. Each reward is either 1 for success or 0 for failure. The true success probabilities, known only for this explanatory calculation, are 0.60 for A, 0.45 for B, and 0.30 for C. Arm A therefore has the highest mean reward.
Suppose an algorithm's expected selection counts over 200 rounds are 120 for A, 50 for B, and 30 for C. Its expected total reward is 120 times 0.60 + 50 times 0.45 + 30 times 0.30 = 103.5. A benchmark always choosing A has expected reward 200 times 0.60 = 120. Expected regret is 16.5.
The gap calculation gives the same result: A's gap is 0, B's is 0.15, and C's is 0.30. Thus regret is 120 times 0 + 50 times 0.15 + 30 times 0.30 = 16.5. These are expected counts and outcomes, not a promise that a particular run produces fractional successes.
Early observations can still be misleading. After five trials of each arm, suppose observed successes are 2 for A, 4 for B, and 1 for C. The empirical means are 0.40, 0.80, and 0.20. A purely greedy choice based on those estimates selects B, even though A has the higher true mean in the constructed example.
This does not mean the observations are invalid. Random rewards can produce an unusual short sample. The challenge is how much additional evidence to collect before committing most opportunities to one arm.
Finally, suppose A's success probability later changes to 0.20. The stationary model used above no longer describes the entire experiment. An algorithm that averages all past observations equally may respond slowly. Detecting or adapting to that change belongs to a nonstationary extension, and the original fixed-mean regret calculation should not be silently reused.

Illustrative case study

Fictional case: AspenTrials compares three service-message formats using a bandit. A campaign changes the audience halfway through the experiment, and response rates shift. The team initially interprets the change as random noise, but stratified checks show the original stable-population assumption no longer holds.
It documents the change and evaluates whether contextual or nonstationary methods are appropriate. The case is invented and illustrates model selection; it does not report a real campaign outcome or endorse optimizing response rate as a complete measure of service quality.

Common misconceptions and mistakes

Common mistakes include assuming the highest observed average is already the best true mean, interpreting stochastic as unpredictable in every respect, and comparing algorithms without a common horizon or reward definition. Adaptive allocation also affects how experimental results should be analyzed; ordinary fixed-allocation statistical procedures should not be applied without checking their assumptions.

Business use

Businesses should use a bandit formulation only when the reward, decision opportunities, and feedback process are well specified. Evaluate the cost of exploration and whether important outcomes arrive too late or are missing. A high short-term reward can be an inadequate objective if actions influence longer-term user experience or future opportunities beyond the basic model.

Check your understanding

Which arm is best in the constructed stationary model?

Answer: A, with mean 0.60.

What is expected regret for the specified counts?

Answer: 16.5.

Why can B look best after five trials?

Answer: A short random sample can misrank the true means.

Related terms

Learn next

Next, simulate the three Bernoulli arms and compare several exploration strategies over multiple independent runs. Plot cumulative reward and regret, then deliberately change one arm's distribution to expose the stationarity assumption.

Sources

Alexander Jung and colleagues, The Aalto Dictionary of Machine Learning, stochastic multiarmed bandit: https://aaltodictionaryofml.github.io/ADictML_Main.pdf Tor Lattimore and Csaba Szepesvari, Bandit Algorithms, Chapter 4: https://tor-lattimore.com/downloads/book/book.pdf

Previous: Stochastic matrix Next: Stochastic neighbor embedding