Decisions and ranking
Bandits
Imagine choosing a lunch spot while occasionally trying somewhere new. A bandit learns which option pays off by observing rewards only for the options it chooses. It balances exploration with using the best estimate so far, without modeling a chain of future states.
How it works
- Define available actions and a measurable reward for each decision.
- Choose an action using an exploration rule such as epsilon-greedy, an uncertainty bonus, or posterior sampling.
- Observe the chosen action’s reward and update its estimate or posterior.
- Track cumulative reward and, when the benchmark is known or can be estimated, regret; adapt estimates if rewards change.
$$Q_{n+1}(a)=Q_n(a)+\frac{r-Q_n(a)}{n+1}$$
The knobs that matter
- epsilon
- sets the chance of random exploration in epsilon-greedy
- confidence bonus
- controls optimism toward uncertain actions
- prior
- sets initial beliefs for posterior sampling
- update window
- shorter histories adapt faster to changing rewards
What interviewers ask
- How would you balance exploration and exploitation in a recommendation bandit?
- How do epsilon-greedy, upper-confidence selection, and posterior sampling differ?
- How does a contextual bandit choose among candidates for different users?
- How would you evaluate a new bandit policy from logged interactions?
Common mistakes
- Treating unchosen actions as if they had observed zero rewards.
- Evaluating logged data without accounting for how actions were selected.
- Using a basic bandit when actions change future states and delayed outcomes matter.
When to use it
Use bandits for repeated choices with observable feedback and a mainly immediate objective. Use a sequential decision model when each action changes the future decision process.
Implement it (6 problems)
Build it step by step
- Bandits and Dynamic Programming from Scratch21 steps, your code runs in the browser