🎰 One Armed Bandit Problem

Trade-off between exploration and exploitation in sequential decision making.

The Problem

Imagine N slot machines (bandits), each with unknown probability of paying out. Pull one lever at a time. Every pull costs something (time, money). Goal: maximize total reward over a fixed budget of pulls.

The dilemma: spend pulls learning which machine is best (exploration) vs. keep pulling the machine you think is best (exploitation).

Formal Setup

K arms (slot machines) with reward distributions unknown
T total time steps (budget of pulls)
At each step t, choose arm i and receive reward r_t from that arm's distribution
Goal: maximize cumulative reward ∑ r_t over T steps
Regret: the difference between your total reward and the reward if you'd known which arm was best

Classic Strategies

1. Greedy (Exploit Only)

Always pull the arm with the highest observed average so far. Fast, low regret initially. But if one arm got lucky early, you might miss better arms forever.

2. Epsilon-Greedy

With probability ε, pick a random arm (explore). With probability 1−ε, pick the best observed arm (exploit). Simple, works well in practice. Choose ε as a trade-off: larger ε explores more but may waste pulls on weak arms.

3. UCB (Upper Confidence Bound)

Pick the arm with the highest upper confidence bound on its expected reward. Arms with high uncertainty get bonus credit for exploration. Mathematically optimal in many settings.

UCB = observed_average + C × √(ln(T) / pulls_so_far)

4. Thompson Sampling

Maintain a posterior distribution over each arm's reward rate. Sample from each posterior, pick the arm with the highest sample. Bayesian; adapts as data accumulates.

Regret Bounds

How many pulls are wasted by not knowing the optimal arm in advance?

Random: Ω(T) — linear regret, wastes nearly all pulls
Greedy: Ω(T) in worst case (if unlucky early)
Epsilon-Greedy: O(K ln(T) / ε) — logarithmic in T, linear in K
UCB: O(K ln(T)) — optimal up to constants
Thompson Sampling: O(K ln(T)) — achieves optimal asymptotic rate

Real-World Applications

A/B Testing: Which version of a webpage is better? Each "arm" is a version.
Recommendation Systems: Which item to show next? Balance showing popular items vs. learning user preferences.
Resource Allocation: Allocate budget to campaigns with uncertain ROI. Explore new channels or double down on proven ones?
Drug Trials: Test multiple treatments, adapt as results come in (adaptive trial design).
Game AI: Explore game strategies vs. exploit the currently best strategy.

Key Insight

The explore/exploit trade-off is fundamental: exploration is an investment that pays off later (you might find a better arm). Exploitation cashes in on what you know now. The art is knowing how much to explore before committing.