Stochastic Bandit
A stochastic bandit is a stripped-down decision problem: choose one option, receive a reward, and repeat. Each option has an uncertain payoff, so the challenge is not merely finding the option that looks best today, but learning which one is genuinely best while still earning reward along the way.
How the setup works
The name comes from slot machines: each “arm” is a lever with its own unknown reward distribution. At round t, the learner picks an arm At and observes one reward. Pulling arm A might produce a reward drawn independently from a distribution with mean 0.6; another arm might have mean 0.7. The learner does not know these means in advance, but the distributions themselves stay fixed throughout the problem.
Exploration versus exploitation
A good strategy must balance two competing choices:
- Exploration: try arms with uncertain estimates, because one could be better than the current favourite.
- Exploitation: choose the arm with the strongest evidence so far, collecting reward from what has already been learned.
For example, an online service choosing between two button designs cannot declare a winner after a handful of clicks: a design that initially looks weak could simply have been unlucky. Upper Confidence Bound (UCB) methods add an optimism bonus to poorly sampled arms, while Thompson sampling samples plausible reward models and acts according to them. Both deliberately gather information, rather than greedily committing to the current highest sample average.
Why it matters
Performance is commonly measured by regret: the reward lost compared with always choosing the best arm, which is known only in hindsight. A stochastic bandit isolates the central reinforcement-learning difficulty that labelled datasets avoid: actions determine what evidence becomes available. Unlike a full RL task, there are no states to navigate, no changing dynamics, and no delayed credit assignment; reward follows immediately from the chosen arm. That simplicity makes bandits a practical foundation for adaptive experiments, recommendation choices, and clinical trial allocation, where wasting too many decisions on inferior options has a real cost.
A stochastic bandit is a sequential decision problem in which each action, or arm, produces rewards drawn independently from a fixed but unknown probability distribution. The learner repeatedly chooses arms to maximize cumulative reward while balancing exploration of uncertain arms against exploitation of arms with high estimated value. It provides the core formal setting for studying efficient reward-driven action selection and regret minimization.
Picture a row of slot machines in a casino. Each one pays out differently, but not predictably: the same machine might win sometimes and lose other times. You have limited pulls, so you must decide which machines to keep trying and which promising one to use more often.
A stochastic bandit is this kind of decision problem. “Stochastic” simply means outcomes include chance. It helps describe situations where an AI learns from repeated choices and rewards: for example, choosing which headline to show a reader when no headline works perfectly every time. The challenge is balancing trying unfamiliar options with sticking to options that have paid off so far.