Exploration vs Exploitation Explained: How Bandits Help Recommenders

It gets stuck. A new item has no history, so it never wins the top slot, so it never gets shown, so it never gets a history. The exploration exploitation tradeoff is the name for escaping that loop.

Picture a common setup. A short-stories app has one big slot on its home screen, called Story of the Day. About 2 lakh (200,000) readers open the app each day, and writers upload about 40 new stories a week. The setup is made up, but the problem is real.

The team fills the slot with a simple rule: show the story with the highest click rate so far. The click rate is clicks divided by times shown. For a few months the rule looks fine. Then the weekly numbers show three problems.

• The same Bengali ghost story has held the slot for six weeks, and its click rate is slowly falling as regular readers get bored.
• Almost none of the 40 new stories a week ever reach the slot, because each one starts with zero clicks.
• Two writers have stopped uploading, because they say nobody ever sees their stories.

So how does the team know the ghost story is still the best, when nothing else gets a fair trial? It does not know. The rule only exploits, and this guide fixes it step by step.

The exploration exploitation tradeoff is the tension between using the option you believe is best now and trying others to learn whether something better exists. On any one visit, the slot can do only one of the two.

Exploit means picking the best option based on what you know today. For the app, that is showing the ghost story again. Explore means picking an option you know less about, to gather information, such as a new Hindi story shown only 20 times.

Think of a Friday-night biryani run in Hyderabad. You have a usual joint, and you know its biryani is good. A new place opened two lanes away. If you always go to the usual joint, you never find out whether the new one is better.

Try a new place every Friday and you eat a lot of average biryani. The sensible plan sits in between: the usual joint most Fridays, a new place now and then. Each new trip costs maybe one weak dinner, and may find a favourite for years.

Map it back to the app. The usual joint is the best-known story, a new place is a new story, and one dinner is one visit to the home screen. A bad dinner is a reader who skips the slot.

Where the picture breaks: you choose dinner for one person, once a week. The app chooses for lakhs of different readers every day, and the best story differs by reader. That difference leads to contextual bandits, later in this guide.

A multi-armed bandit is a simple model of repeated choices. You pick one of several options, see a reward for that option only, and use it to choose better next time. The name comes from slot machines, nicknamed one-armed bandits.

Picture a row of slot machines, each paying out at a different hidden rate. You need four words to talk about this puzzle.

Arm. An arm is one option you can pick. For the app, each story that could go in the big slot is one arm. With 40 new stories a week, the list of arms keeps changing.

Reward. A reward is the number you get back after picking an arm. The team first uses 1 for a click and 0 for no click. Later in this guide that choice turns out to be a mistake.

Policy. A policy is the rule that picks the next arm. Show the highest click rate is a policy. So is show a random story one time in ten.

Regret. Regret is the reward you lost by not always picking the truly best arm. Say the best story earns 8 clicks per 100 shows, and you show one earning 6 per 100 for 1,000 shows. Your expected regret is 20 clicks.

The key detail is partial feedback. You see the reward only for the arm you picked. If a reader skipped the ghost story, you never learn whether they would have clicked the new Hindi story, so you must explore on purpose.

Auer, Cesa-Bianchi and Fischer (2002) call the bandit one of the simplest examples of this dilemma and measure a policy by its regret. They show simple policies can keep regret growing only with the logarithm of the number of plays.

That result holds for rewards between fixed bounds, such as 0 and 1. The paper also cites an earlier result by Lai and Robbins: in the long run, regret must grow at least logarithmically. So simple policies can match the best possible growth rate.

Here is the loop every bandit runs. Start at the reader opening the app and follow the arrows round. Notice that the policy only ever learns from the story it chose.

Epsilon-greedy picks a random arm a small fraction of the time, called epsilon, and the best-known arm the rest of the time. With epsilon at 0.1, about one visit in ten is a random pick.

A random pick can still land on the best story, so slightly fewer than one visit in ten truly explores. It is the biryani plan as code: the usual joint most Fridays, and roughly one Friday in ten, any place on the street.

Here is the team's first version. The stats dictionary maps each story id to two numbers: how many times it was shown, and how many clicks it got.

import random

EPSILON = 0.1  # about 1 visit in 10 is a random pick

def pick_story(stats):
    # stats: {story_id: [shows, clicks]}
    if random.random() < EPSILON:
        return random.choice(list(stats))
    return max(stats, key=lambda s: stats[s][1] / max(stats[s][0], 1))

def record(stats, story_id, clicked):
    stats[story_id][0] += 1
    if clicked:
        stats[story_id][1] += 1

Two lines matter. The random.random() check is the coin toss that decides explore or exploit. The max line picks the best click rate, and max(shows, 1) avoids dividing by zero for brand new stories.

The team ships it, and new stories finally get seen. Epsilon-greedy still has three weak spots.

• It explores blindly. A story already shown 5,000 times with a poor click rate gets the same random chance as one shown 10 times.
• It never stops. With a fixed epsilon, it keeps spending about one visit in ten on random picks, even when it is sure which stories are good.
• Picking epsilon is guesswork. Too low and new stories starve; too high and readers see many weak stories.

The 2002 paper also studies a version whose epsilon shrinks over time, roughly as one over the number of plays. Tuned well, it did very well in their tests. Tuned badly, its performance degraded rapidly.

UCB and Thompson sampling explore where they are unsure, instead of at random. A story with few shows gets extra chances, and a story with many poor shows gets fewer and fewer.

UCB gives the benefit of the doubt

UCB stands for upper confidence bound. For each arm, it adds a bonus to the average reward, then picks the arm with the highest total. The bonus is big when the arm has few tries and shrinks as tries grow.

Back to the biryani lanes. You tried a new joint once and it was only okay, but one visit tells you little. So you give it the benefit of the doubt, and stop going back after several average visits.

In the UCB1 policy from the 2002 paper, take two times the natural log of the visit number, divide by that arm's tries, and take the square root. Because the bonus divides by tries, every arm is tried once first.

import math

def pick_story_ucb1(stats, t):
    # t: number of this visit, starting at 1
    for story_id, (shows, clicks) in stats.items():
        if shows == 0:
            return story_id  # try every story once first
    return max(stats, key=lambda s: stats[s][1] / stats[s][0]
               + math.sqrt(2 * math.log(t) / stats[s][0]))

Thompson sampling picks in proportion to the chance of being best

Thompson sampling keeps a range of believable click rates for each arm, not one number. On each visit it draws one random guess from each range and shows the arm with the highest guess.

The effect is that each arm gets picked with the chance that it is the best arm, given the data so far. The 2017 tutorial by Russo and colleagues calls this probability matching.

Take two stories. The ghost story has 10,000 shows and 600 clicks, so its range sits tightly around 6 percent. A new Hindi story has 20 shows and 2 clicks, and the middle 95 percent of its range runs from about 3 to 30 percent.

About 87 percent of the new story's draws land above 6 percent, so it wins most rounds at first. Those visits are exploration. As it collects data, its range narrows, and it keeps winning only if it really is better.

Python's random module already has the Beta distribution, a standard way to describe a believable range for a click rate. Here is the whole policy.

import random

def pick_story_thompson(stats):
    # stats: {story_id: [shows, clicks]}
    best_story, best_draw = None, -1.0
    for story_id, (shows, clicks) in stats.items():
        misses = shows - clicks
        draw = random.betavariate(clicks + 1, misses + 1)
        if draw > best_draw:
            best_story, best_draw = story_id, draw
    return best_story

Only the betavariate line is new. It draws one guess for the story's click rate. The plus ones give a brand new story a flat range over every rate from 0 to 100 percent.

The same record function from before keeps the counts up to date. The tutorial uses the same Beta update: add each click to one count and each miss to the other.

Simulate it. Give a few made-up stories hidden click rates, let each policy run 20,000 visits, and count the regret. The script below uses the same policies as above and runs on plain Python with no installs. You can skip its lines and read only the output.

Story b is truly the best at 8 percent. The old story is listed first at 6 percent. Pause and predict: how often will the greedy rule, which never explores, show story b?

import math
import random

RATES = {"old": 0.06, "a": 0.05, "b": 0.08, "c": 0.04, "d": 0.07}  # made-up true click rates
VISITS = 20_000


def greedy(stats, t):
    return max(stats, key=lambda s: stats[s][1] / max(stats[s][0], 1))


def eps_greedy(stats, t, eps=0.1):
    if random.random() < eps:
        return random.choice(list(stats))
    return greedy(stats, t)


def ucb1(stats, t):
    for s, (shows, clicks) in stats.items():
        if shows == 0:
            return s  # try every story once first
    return max(stats, key=lambda s: stats[s][1] / stats[s][0]
               + math.sqrt(2 * math.log(t) / stats[s][0]))


def thompson(stats, t):
    return max(stats, key=lambda s: random.betavariate(
        stats[s][1] + 1, stats[s][0] - stats[s][1] + 1))


def run(policy, seed):
    random.seed(seed)
    stats = {s: [0, 0] for s in RATES}
    for t in range(1, VISITS + 1):
        s = policy(stats, t)
        clicked = random.random() < RATES[s]
        stats[s][0] += 1
        stats[s][1] += clicked
    best = max(RATES.values())
    regret = sum(shows * (best - RATES[s]) for s, (shows, _) in stats.items())
    return round(regret), stats["b"][0] / VISITS


for name, policy in [("greedy", greedy), ("epsilon 0.1", eps_greedy),
                     ("UCB1", ucb1), ("Thompson", thompson)]:
    regret, share = run(policy, seed=7)
    print(f"{name:12} regret {regret:5} clicks, best story shown {share:.0%}")

Save it as simulate.py and run python3 simulate.py. On Python 3.13.16 this printed the lines below. Regret is in expected clicks lost, and the share is how often story b filled the slot.

greedy       regret   400 clicks, best story shown 0%
epsilon 0.1  regret    44 clicks, best story shown 91%
UCB1         regret   291 clicks, best story shown 33%
Thompson     regret    53 clicks, best story shown 85%

What just happened? On visit one every rate was zero, and max() breaks ties by taking the first story. After the old story's first click, no untried story could beat it, so greedy never showed story b.

Greedy's regret is exactly 2 percent of 20,000 visits, and it stays at 400 on every seed. Seed 7 was the best of 10 seeds for epsilon-greedy and tied best for Thompson sampling, so epsilon-greedy edged ahead here. Across 10 seeds, the median regret was 88 for epsilon-greedy, 292 for UCB1 and 78 for Thompson sampling. Other Python versions may print different digits for the random policies.

The gap grows with time. At 200,000 visits, the median regret was 448 for epsilon-greedy and 111 for Thompson sampling. Thompson won on all 10 seeds. A fixed epsilon keeps paying forever: 10 percent random picks, each losing 0.02 clicks on average, cost about 400 clicks over 200,000 visits.

Why UCB1 lagged behind

UCB1's bonus is built for any reward between 0 and 1, so it assumes the widest possible spread. Click rates near 5 percent vary far less, so the bonus is far too generous and UCB1 keeps exploring.

At visit 20,000, a story with 1,000 shows gets a bonus of about 0.14. The standard error (the typical size of measurement noise) of a 6 percent click rate over 1,000 shows is about 0.0075, so the bonus is nearly 19 times larger.

The 2002 paper offers a variant, UCB1-Tuned, that scales the bonus by each arm's measured variance. The authors report it did substantially better than UCB1 in essentially all their experiments, though they prove no bound for it.

Across the same 10 seeds, it cut the median regret from about 290 to 150 at 20,000 visits, and from about 1,480 to 270 at 200,000. Plain UCB1 is a fine teaching tool; on low click rates, test a tuned variant.

A contextual bandit is a bandit that also looks at context, such as who the user is and when they visit, before picking an arm. It learns which arm is best for which kind of visit, not one winner for everyone.

The app needs this. A Hindi reader at 11 at night and a Bengali reader at 8 in the morning should not see the same story. One global winner hides that difference.

Context. Context is the information you know before choosing. For the app, the team uses the reader's preferred language, the hour of the day, the genres they finished last week, and whether they are on a phone or tablet.

Each story also has features, such as its language, genre and length. A small model learns how context and story features combine into a click chance. It also tracks how unsure it is, and adds an exploration bonus there.

This is the idea behind LinUCB, from a 2010 paper by Li, Chu, Langford and Schapire. They tested it on news article picks for the Yahoo! Front Page Today Module, using a dataset of over 33 million events.

They reported a 12.5 percent click lift over a standard bandit that ignored context. They also reported that the advantage grew when data was scarcer, which fits a feed where fresh items keep arriving with little history.

The app has thousands of stories, and exploring each of them in turn would waste visits. So the bandit sits at the end of a longer pipeline. Follow the diagram from the reader to the log, and notice where exploration happens.

The full design of the candidate and ranking stages belongs to recommendation system design and feed ranking. Here the point is narrower: the bandit decides how much to trust the ranker's top picks, and how often to test the ones just below.

The nightly update matters for the choice of policy. Between updates, a deterministic rule like UCB1 shows every reader with the same context the same story. Chapelle and Li (2011) found Thompson sampling held up better than UCB when feedback is delayed, because its random draws keep spreading traffic. In their simulation, UCB's regret grew from 2.65 to 3.82 times Thompson's as the delay rose from 1 to 1,000 steps.

You test it offline by replaying logged visits where the story was chosen at random. You keep only the visits where your new policy would have picked the same story, and average their rewards.

Testing a bandit is harder than testing a normal model. The log has rewards only for stories that were shown. If the new policy would pick a different story, you have no idea how the reader would have reacted.

Li, Chu, Langford and Wang (2011) describe this as the partial-label nature of the data. They note that building a simulator of readers is hard and adds modelling bias. Their replay method is purely data-driven and provably unbiased.

That guarantee has two conditions. Visits must be independent and drawn the same way over time, and the logging policy must have picked each arm uniformly at random. Their experiments compared replay with live bucket tests on the same news site.

So the team sets aside 2 percent of visits as a random bucket. On those visits, the big slot shows a uniformly random story from the top 20. The bucket costs a few clicks a day, and buys honest test data.

1. 1

   Collect random rounds

   For two weeks, log every visit in the random bucket: the context, the story shown and whether the reader clicked.

2. 2

   Replay them in order

   Feed each logged visit to the new policy, in time order, and ask which story it would pick for that context.

3. 3

   Keep only the matches

   If the policy picks the logged story, count that reward and let the policy learn from it. If not, skip the visit entirely.

4. 4

   Compare the averages

   The average reward over kept visits estimates live performance. Compare it with the current policy, replayed the same way on the same log.

5. 5

   Confirm with live traffic

   Give the winner a small live share of traffic first. Offline replay narrows the choice, and a live test confirms it.

Replay throws away most of the log. With 20 candidate stories, each logged visit matches with chance 1 in 20, and a quick simulation kept 4.96 percent of 200,000 visits. Honest testing needs a lot of random data.

Use a bandit when you have many short-lived options and want to lose few clicks while you learn. Use an A/B test when you need a clear, trusted answer to one big decision.

An A/B test splits users into fixed groups, often half and half, until the test ends. Then you check which group did better. It spends traffic on the weaker option for the whole test, but its answer is clean and easy to defend.

A bandit moves traffic towards the winner while it is still learning. It wastes less traffic, but its answer is harder to read. The losing option got little traffic, so you know less about exactly how much worse it was.

The team settles on a simple split. Story of the Day uses a bandit, because new stories arrive every week and each matters for a few weeks only. A new ranking model goes through an A/B test, because it changes the whole feed.

Here is the decision as a small diagram. Start at the top question and follow the answers.

Bandits fail in production when the reward is the wrong number, when rewards arrive late, when tastes change, or when exploration has no limits. Each problem needs a guard designed in from day one.

The app hit the first one in week three. A story with a shocking title won the slot with a 14 percent click rate, and most readers left within a minute. The bandit had learned exactly what it was asked for: clicks.

• Wrong reward. Clicks reward catchy titles, so the team changes the reward to 1 only when a reader finishes at least 70 percent of the story.
• Late rewards. A finish arrives minutes after the show, so the team waits 30 minutes before counting a show as a miss.
• Changing tastes. A story's appeal fades over weeks, so the team counts only the last 14 days and old success stops counting.
• Too many arms. Hundreds of weak arms waste exploration, so the ranker passes only its top 20 and the bandit explores among sensible choices.
• Unlimited exploration. A badly tuned policy can explore far too much. An exploring visit shows a story other than the leader by average so far, and the team caps these at 40 percent and alerts.
• Unsafe content. Exploring must never show a story that failed review, so safety filters run before the bandit, never after.

These thresholds are made up for the scenario. Across 10 seeds of the simulation above, the median share of exploring visits by that measure was 8 percent for epsilon-greedy, 22 percent for Thompson and 66 percent for UCB1. Pick your limits from your own logs, and replay-test any change to them.

There is a quieter problem too: the feedback loop. Stories shown often collect more data, so the system grows more confident about them. Exploration is what breaks this loop for new and niche stories.

This links to the cold start problem, where a new item or user has no history at all. A bandit does not remove cold start. It gives new items a planned, limited trial, so they can earn a history.

Explain it as a cost now for knowledge later, then show where a bandit fits in the recommender and how you would keep it safe. Interviewers want the tradeoff and the guards more than the maths.

1. 1

   Name the trap

   Say that a recommender which only exploits never shows new items, so it never learns about them. Give one concrete example, like a stuck top slot.

2. 2

   Define the bandit

   Arms are items, the reward is a measurable good outcome, and the policy picks an arm each visit. Mention regret as the cost of exploring.

3. 3

   Pick a policy and say why

   Start with epsilon-greedy for simplicity. Move to Thompson sampling or a tuned UCB to explore where the system is unsure.

4. 4

   Add context

   Use a contextual bandit so different readers can get different winners. Place it after candidate generation and ranking, on a short list.

5. 5

   Choose the reward carefully

   Prefer a reward close to real value, like a finished read, over raw clicks. Say how you handle rewards that arrive late.

6. 6

   Show how you test and guard it

   Log the chance of each choice, keep a small random bucket for replay, cap exploration and track long-term metrics.