Multi-Armed Bandits

The name comes from a row of slot machines ("one-armed bandits") in a casino, each with a different, unknown payout rate. You get to pull one arm at a time, you observe only the payout from the arm you pulled, and your goal is to make as much money as possible over a fixed number of pulls. This toy setup is the simplest possible formalization of the explore-exploit trade-off, and it is the model underneath every algorithm — epsilon-greedy, upper confidence bound, Thompson sampling — used to decide "which option should I try next" when trying an option is the only way to learn about it.

The setup, precisely

There are $k$ arms (options). Each arm $i$ has a true, fixed, unknown average payout $\mu_i$. At each round you choose one arm, pull it, and observe a random payout drawn from that arm's (unknown) distribution — you learn nothing about the arms you did not pull. Over $T$ total rounds, you want to maximize total payout, which is equivalent to minimizing regret: the gap between what you actually earned and what you would have earned by always pulling the single best arm from the start, had you known which one it was in advance.

$$\text{Regret}(T) = T \mu^* - \sum_{t=1}^{T} \mu_{a_t}$$

In words: regret is the best-possible total payout ($T$ rounds times the best arm's true average $\mu^*$) minus what you actually collected by pulling arms $a_1, a_2, \dots, a_T$ in sequence. Regret is unavoidable early on — you cannot know which arm is best without trying several — but a good bandit algorithm makes regret grow slower and slower as $T$ increases, eventually pulling the best arm almost every time.

Worked example: epsilon-greedy on three signals

Three trading signals are the three "arms," with true (unknown to the trader) average daily returns of 0.10%, 0.30%, and 0.20%. A simple epsilon-greedy policy: with probability $\varepsilon = 0.1$, pull a uniformly random arm (explore); otherwise, pull whichever arm currently has the highest sample average (exploit). After 20 initial rounds split evenly, suppose the sample averages read 0.05%, 0.35%, and 0.15% — noisy, but pointing toward arm 2. For the next 100 rounds the policy pulls arm 2 about 90% of the time and a random arm the other 10%. Over many rounds the sample averages converge toward the true 0.10%, 0.30%, 0.20%, and because arm 2 really is best, exploitation increasingly pays off — but the flat 10% exploration rate never shrinks, so epsilon-greedy keeps paying a fixed cost forever even once it is virtually certain which arm is best, its main known weakness relative to Thompson sampling.

Each arm's sample average behaves like the running average shown above: noisy over the first handful of pulls, converging toward the true value as pulls accumulate. Regret accumulates fastest during exactly this noisy early phase, which is why the choice of exploration strategy over the first rounds matters disproportionately.

What this means in practice

Firms testing several new trading signals with real (small) capital simultaneously are running a bandit problem whether or not they call it that: each signal is an arm, its "payout" is realized P&L, and the allocation decision each period is exactly which arm(s) to pull. The same framing underlies online A/B testing of anything with a measurable payoff, which is why bandit algorithms, not fixed 50/50 A/B splits, are increasingly used when the cost of running the losing variant is itself expensive.