Bandit Optimization
Bandit optimization chooses actions to minimize loss when only the chosen action's outcome is observed, forcing a trade-off between exploration and exploitation.
Learning with partial feedback
In full-information online learning the loss of every possible action is revealed after each round. In the bandit setting only the loss of the action actually taken is observed; the outcomes of the alternatives stay hidden. This partial feedback is the defining feature and the core difficulty: to learn about an action you must try it, which costs the chance to play a better-known one.
Exploration versus exploitation
The central tension is between exploitation, playing the action that currently looks best, and exploration, trying uncertain actions to gather information that might reveal something better. Pure exploitation can lock onto a suboptimal action forever; pure exploration wastes rounds on bad actions. Every bandit algorithm is a rule for balancing the two, and its regret quantifies the cost of not knowing the best action from the start.
Settings
The stochastic bandit assumes each action's loss is drawn from a fixed unknown distribution; the adversarial bandit makes no such assumption and faces an opponent choosing losses. Contextual bandits reveal side information before each choice, so the best action depends on context. Continuous bandits (bandit convex optimization) have an infinite action set and must estimate gradients from single-point feedback.
- Stochastic K-armed: fixed reward distributions, UCB and Thompson sampling
- Adversarial: arbitrary losses, EXP3 achieves O(sqrt(TK)) regret
- Contextual: choose using features, links to supervised learning
- Bandit convex optimization: gradient estimation from function values
Applications
Bandit methods drive decisions where each choice yields feedback only about itself: A/B testing and content recommendation, clinical-trial allocation, adaptive experimental design, and hyperparameter search. They connect to reinforcement learning as its simplest, single-state case, and to online convex optimization as the limited-feedback version of the same game. The right algorithm depends on whether the environment is stochastic, adversarial, or context-dependent.