Exploration vs Exploitation

Every learning agent (a foraging swarm, a recommendation engine, a rat in a maze) runs into the same wall. To know which option is best, you have to try them all. But trying the bad ones costs you. Knowledge and reward pull in opposite directions, and there is no way to buy both at once.

The restaurant you keep going back to

Forget robots for a second. You've just moved to a new city.

• Eat at the one good place you've found every single night? That's exploitation: safe, predictable, and you will never discover the better restaurant two blocks away.
• Try somewhere new every night? That's exploration: you'll eventually map the whole city, but you'll choke down a lot of mediocre dinners doing it.

The honest answer is neither, all the time. Early on, when you know almost nothing, explore aggressively. As evidence piles up, lean harder on your favourites, but never stop poking at the edges, because the city changes and so do you.

What it costs to be wrong: regret

To do better than vibes, we need a number to minimise. That number is regret: the difference between the reward you got and the reward you would have gotten if you'd known the best option from the start.

Picture two failing extremes:

• Pure exploitation locks onto the first option that looks decent and never tries the rest. If something better existed that it skipped, it pays that gap on every future pull. Regret climbs in a straight line, forever.
• Pure exploration picks at random the whole time. It does eventually learn which arm is best, but it keeps wasting most of its pulls re-confirming the losers. Same straight-line regret, different reason.

The whole game is to make that regret line bend toward flat: explore enough to find the best arm quickly, then stop paying for arms you've already ruled out.

UCB1: optimism in the face of uncertainty

Before the elegant fix, here is the crude one almost everyone reaches for first. It is called epsilon-greedy: pick the best-looking arm almost always, but every so often (say one pull in ten) flip a coin and try something random instead. That random sliver is your exploration budget. It works, and it is two lines of code, but it is dumb in one specific way: it keeps wasting those random pulls on arms it has already proven are terrible, right alongside the ones it is genuinely unsure about. The smarter rules below spend their curiosity where it actually buys information.

The elegant fix is a rule called UCB1, and its philosophy is one of the best in all of decision-making: be optimistic about what you haven't tried yet.

For each arm, don't judge it by its average reward alone. Judge it by its average plus a bonus that grows the less you've sampled it. An arm you've barely touched gets a big optimistic boost: maybe it's secretly great. An arm you've pulled a thousand times gets almost no bonus, because you already know what it is. Then simply pick the arm with the highest total. Exploration falls out automatically: under-tried arms float to the top and get a fair shot, while proven winners win on merit.

$UCB_i = \bar{x}_i + c \sqrt{\frac{\ln t}{n_i}}$

Here $\bar{x}_i$ is the average reward seen from arm $i$, $n_i$ is how many times you've pulled it, $t$ is the total number of pulls so far, and $c$ is an exploration constant (typically $\sqrt{2}$). The first term is exploitation; the second is exploration. Notice the $n_i$ in the denominator: pull an arm more and its bonus shrinks. Notice the $\ln t$ on top: as time passes, every arm slowly earns a little curiosity back, so the algorithm never goes permanently blind.

Same math, everywhere

The reason this matters far beyond casinos: the bandit is a universal shape. Any system that has to learn while it acts, paying real costs in real time, never getting a free practice round, is solving a bandit.

• A foraging swarm treats each region as an arm: exploit the patch that's been productive, but keep scouting the map in case a richer patch appears.
• The same math drives A/B testing, online ad selection, and adaptive clinical trials, where "exploration" means giving more patients the treatment that's looking better, and "regret" is measured in lives.

Different dressing, identical skeleton: try, measure, lean toward what works, never fully stop checking.

struct UCB1Arm {
    rewards: Vec<f32>,
    count: usize,
}

impl UCB1Arm {
    fn ucb(&self, total_count: usize, c: f32) -> f32 {
        if self.count == 0 { return f32::INFINITY; }

        let avg = self.rewards.iter().sum::<f32>() / self.count as f32;
        let exploration = c * (total_count as f32 / self.count as f32).ln().sqrt();
        avg + exploration
    }
}

Key takeaways

• Exploration gathers information; exploitation spends it. You cannot maximise both on the same pull.
• Regret, the reward gap versus an oracle who knew the best arm, is the single number the whole problem minimises.
• UCB1 picks the arm with the best optimistic bound: average reward plus a bonus that fades as you sample. It achieves optimal $O(\ln T)$ regret.
• The same structure governs swarm foraging, A/B tests, ad selection, and clinical trials: anywhere you must learn while you act.