Bandit Problem

Imagine choosing among several slot machines, each with an unknown payout pattern. Every pull gives you money—or not—but it also teaches you something about that machine. The bandit problem captures the challenge of making good choices while learning which choices are good.

In a standard multi-armed bandit, an agent repeatedly selects one action, or “arm,” then immediately observes a reward for that choice. Unlike a full reinforcement-learning task, there are no changing states to navigate and no long chain of consequences: each round is a fresh choice. The difficulty is the exploration–exploitation trade-off:

• Exploit: choose the arm with the best estimated reward so far.
• Explore: try uncertain arms that could turn out to be better.

A purely greedy agent can get trapped: an arm pays well in its first few trials by luck, so the agent keeps selecting it and never discovers a stronger alternative. Bandit algorithms attach uncertainty to reward estimates and deliberately account for it. Upper Confidence Bound (UCB) chooses actions that are either promising or poorly tested. Thompson sampling instead samples a plausible reward model for each arm and acts according to the sampled winner. Their goal is low regret: the reward lost relative to always having chosen the best arm from the beginning.

Bandits fit decisions where feedback is quick and one choice does not substantially alter the next situation: selecting a website headline, routing a request between system variants, or choosing which diagnostic test to run first. A contextual bandit adds information available before acting—such as a user’s device or query—so it can learn that different actions suit different contexts. This makes bandits a useful bridge between supervised prediction and reinforcement learning: the system must collect its own informative data, yet it avoids the delayed-credit-assignment problem of multi-step control.