A multi-armed bandit is a sequential decision problem: repeatedly choose among actions with unknown reward rates while maximizing the total reward collected over a fixed or extended horizon. Each action reveals an uncertain outcome only after it is taken. section 5.1 section 5.5
Choosing a profitable slot machine
Imagine several slot machines, each with a hidden probability of returning coins. Pulling an arm supplies evidence about that machine, but also consumes an opportunity that could have been spent on another machine. A strong strategy must discover which machines pay well without neglecting promising alternatives. section 5.1.1
The central decision tension has three parts:
- Exploration tests under-sampled actions to learn their reward rates. section 5.5
- Exploitation selects actions already associated with high rewards. section 5.5
- The policy chooses the next action from past observations, balancing immediate reward against information gathering. section 5.1 section 5.5
Bandit policies connect directly to Bayesian optimization. Both optimize under uncertainty, but a bandit maximizes cumulative reward across finite actions, whereas Bayesian optimization seeks a high single observed value over potentially infinitely many, correlated actions. section 5.1.2
