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.

EstimateA: 3/4, B: 1/2Chooseexplore BObservereward = 1Update B2/3 mean reward
Exploring B reveals one new reward and updates only B’s estimate.
EstimateA: 3/4, B: 1/2Chooseexplore BObservereward = 1Update B2/3 mean reward
Exploring B reveals one new reward and updates only B’s estimate.

How it works

  1. Define available actions and a measurable reward for each decision.
  2. Choose an action using an exploration rule such as epsilon-greedy, an uncertainty bonus, or posterior sampling.
  3. Observe the chosen action’s reward and update its estimate or posterior.
  4. 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

Learn it

Interview questions about bandits