Regret and the Exploration-Exploitation Tradeoff

A system chooses among several options repeatedly and observes the outcome only for the option it chose. Choosing the current best exploits what is known and forgoes information about the others; choosing something else buys information at the cost of a probably worse outcome now. The bandit framework is the clean formalisation of that tension, and it describes a great deal of production machine learning.

The setting

At each round \(t\), choose an arm \(a_t\) from \(K\) options and receive a reward \(r_t\) drawn from that arm's unknown distribution. Two properties define the problem.

Partial feedback. You observe the reward only for the arm you pulled, never the counterfactual. This is what separates bandits from supervised learning, where the label for every example is available regardless of what the model predicted.

No state. The arms' distributions do not change in response to your actions, and there is no transition dynamics. This is what separates bandits from full reinforcement learning, and it is why bandit problems have much stronger theoretical guarantees.

Regret

The performance measure is cumulative regret: the difference between the reward the best fixed arm would have accumulated and what the algorithm actually accumulated.

Regret is the natural objective because absolute reward depends on the problem's scale while regret measures the cost of not knowing. An algorithm with sublinear regret has average regret per round going to zero, which means it eventually plays the best arm almost always. Linear regret means it never learns.

The logarithmic lower bound

Lai and Robbins established that no algorithm can do better than \(\Omega(\log T)\) regret asymptotically, with a constant determined by the KL divergence between each suboptimal arm's reward distribution and the best arm's. Arms that are hard to distinguish from the best one cost more to rule out.

This bound is the most important thing to understand about the field, because of what it implies: exploration can never stop entirely. Any algorithm that commits permanently to an arm after finite evidence risks committing to the wrong one, which gives linear regret. The optimal algorithms explore forever, at a rate that decays as \(\log T\), and the practical consequence is that a production system should always retain a small exploration budget rather than converging to a fixed policy.

When it breaks

Epsilon-greedy with fixed epsilon has linear regret. Exploring a constant fraction of the time forever means a constant per-round cost that never decays, so regret grows linearly. Decaying epsilon on a \(1/t\) schedule recovers logarithmic regret and is the minimum correction, though it is still worse in constant factors than UCB or Thompson sampling.

Regret is defined against a fixed best arm. If the best arm changes over time, the benchmark is wrong and the guarantees do not apply. Non-stationary settings need a different notion, typically regret against the best arm in each window.

Cumulative regret is not the only objective. Best-arm identification, where you explore for a fixed budget and then commit, has a different optimal strategy: it explores far more aggressively, because the cost of exploration during the identification phase is not counted. Choosing the wrong objective produces a well-implemented solution to the wrong problem.

The independence assumption is usually false. Standard bandits treat arms as unrelated, so learning about one teaches nothing about another. Real arms share structure, and exploiting it through a contextual or structured formulation is what makes the approach usable at realistic \(K\).