Multi-Armed Bandits: Exploration vs Exploitation

You have just joined a new coaching institute in a city you have never lived in before, and the exam you are preparing for is ten months away. Outside the institute gate there are four small stalls selling tea and a quick bite before the morning batch starts. You have time to stop at exactly one of them each day. Stall A is right at the gate — always convenient. Stall B has a long queue most mornings, which usually means something. Stall C opened only last month and nobody you know has tried it yet. Stall D is a five-minute walk further, near the bus stand, easy to ignore. On day one, you do not know which of these four is actually the best. You only find out how good a stall is by going there and trying it.

This is the exact situation this chapter is about — not chai stalls specifically, but the decision problem hiding inside them. Every morning you face a choice among a small set of options, each option gives you a reward only after you pick it, and you have a limited number of mornings before the exam. Do you keep returning to the stall you already know is decent, or spend a morning trying the one you have never visited, on the chance that it might be even better? Get this trade-off wrong in one direction and you keep eating mediocre food out of habit while a genuinely great stall sits five minutes away, undiscovered. Get it wrong in the other direction and you waste too many mornings sampling options instead of enjoying the one you already know is good. Computer scientists gave this exact dilemma a formal name and built algorithms that solve it well. It is called the multi-armed bandit problem, and it sits at the foundation of reinforcement learning.

What Exactly Is a Multi-Armed Bandit?

The name comes from old mechanical slot machines, nicknamed "one-armed bandits" — "bandit" because they steadily take your money, "one-armed" because of the single lever you pull. Now imagine a row of slot machines side by side, each with its own lever, each secretly programmed to pay out winnings at a different average rate. You may pull one lever per turn, for a fixed number of turns, and your goal is to walk away with as much money as possible. You are not told which machine pays best. The only way to find out is to pull levers and watch what comes out. A row of such machines is a multi-armed bandit, and this puzzle — figuring out which lever to trust while still making money along the way — is the multi-armed bandit problem.

Stripped of the slot-machine costume, a multi-armed bandit problem has three ingredients. First, a set of arms (also called actions) to choose from — in the casino, the levers; outside your coaching institute, the four stalls. Second, every arm has a true, fixed average reward it delivers when chosen, but this number is hidden from the decision-maker — imagine Stall A genuinely satisfies you 6 out of 10 on average, B is an 8, C is a 5, and D is a 9, but you, the person choosing, have no way of seeing these numbers directly. Third, the decision-maker — called the agent in reinforcement learning — repeatedly picks one arm at a time, observes only the reward from that single pick, and uses everything observed so far to decide what to pick next. The goal is to maximize total reward collected over all rounds put together, not to get lucky once.

This setup is a deliberately simplified cousin of the full reinforcement learning problem you may meet elsewhere in this course. A full RL agent acts inside a world that has state — its situation changes as a result of its actions, and today's choice affects what choices are even available tomorrow. A bandit agent lives in a world with exactly one state that never changes: every round is a fresh, independent shot at the same set of arms, and picking Stall B on Tuesday does not change what Stall B has to offer on Wednesday. This makes bandits the cleanest possible setting to study one specific problem in isolation — the tension between gathering information and using the information you already have — before that tension gets folded into the messier full RL problem you will meet later.

The Core Tension: Exploration vs Exploitation

At every round, the agent has two conflicting instincts.

Exploitation means picking the arm that currently looks best, based on everything observed so far, to collect the reward you are fairly confident about. If Stall B has given you an 8 and an 8.5 rating on your first two visits and nothing else has been tried yet, exploiting means going back to B tomorrow. Exploitation is what earns you reward right now.

Exploration means deliberately picking an arm that does not currently look like the best option, purely to learn more about it. Walking the extra five minutes to Stall D even though B has been fine so far is exploration. Exploration rarely earns you the highest possible reward on the day you do it — that is exactly why it feels wasteful in the moment — but it is the only way to discover that D was secretly a 9 all along.

Neither instinct alone is a good strategy over many rounds. Consider an agent that only ever exploits — a pure greedy strategy. On day one, with no information at all, it has to pick something, so say it defaults to Stall A and happens to get a reasonably good rating. From day two onward, since A now has a known score and every other stall's score is still a total unknown, a greedy agent has no way to prefer any untried stall over the one arm it has already sampled — it just keeps exploiting A, forever. It never learns that D exists at a 9 rating. Whatever A's true quality turns out to be, that is the ceiling on everything this agent will ever earn — and it locked in that ceiling based on a single data point from day one.

Now consider the opposite extreme: an agent that only ever explores, always picking a random, uniformly distributed stall regardless of what it has learned. Over many rounds this agent does eventually discover that D is the best stall, since it tries everything equally often. But knowing that fact does it no good, because it never acts on the knowledge — it keeps wasting a quarter of its visits (with four stalls) on the worst options right up to the final day before the exam.

A good bandit algorithm needs both instincts, blended in the right proportion. Early on, when almost nothing is known, exploring is cheap because there is not much of a known-good option to give up by trying something new. Later, once the agent has strong evidence about which arms are good and which are poor, exploring becomes more expensive relative to just exploiting what is already known well. The gap between what an agent actually earns and what it could have earned by always picking the single best arm from the very first round is called regret. Minimizing cumulative regret — not maximizing any single round's reward — is the real objective in a bandit problem, and it is regret that makes exploration worthwhile in the first place: a small, controlled amount of regret spent early on information-gathering buys a much larger reduction in regret for every round that follows.

Formalizing It: Values, Estimates, and a Useful Update Rule

To build an actual algorithm, the vague phrase "looks best so far" needs a precise number attached to it. Call the true, hidden average reward of arm a its action-value, written q*(a) — the star marks that this is the real answer, unknown to the agent. Since the agent cannot see q*(a) directly, it keeps a running estimate instead, written Q(a), simply the average of all rewards actually received from arm a so far. The whole point of the algorithm is to make Q(a) converge toward the true q*(a) for every arm, using as few rounds as possible on the arms that turn out not to matter.

The most direct way to compute Q(a) would be to store every past reward from arm a and re-average the whole list each time a new one arrives. That works but wastes memory — after two hundred visits to a stall you would be storing and re-adding two hundred numbers just to update one running score. There is a cheaper, mathematically identical way. Let N(a) be the number of times arm a has been chosen so far, and let Q_old(a) be its current estimate. When a fresh reward R arrives from arm a, the count becomes N_new(a) = N(a) + 1, and the new estimate can be computed directly from the old one:

Q_new(a) = Q_old(a) + (R - Q_old(a)) / N_new(a)

Read this as: take the old estimate, find the error between the new reward and that old estimate, shrink that error by dividing by the new visit count, and nudge the old estimate by the shrunk amount. Early on, when N(a) is small, each new reward has a large effect on the estimate, because there is not much history to outweigh it. Later, when N(a) is large, a single new reward barely moves the estimate, because it is now one data point among many. This single line of arithmetic removes the need to store any history at all — the agent only ever needs to remember two numbers per arm, Q(a) and N(a), no matter how many rounds have passed.

Epsilon-Greedy: A Simple Fix That Works Remarkably Well

The most widely taught bandit algorithm fixes the greedy trap with one small addition, controlled by a single number called epsilon (written ε), some small probability such as 0.1 or 0.2. On every round, the agent first decides, at random, whether this round will be spent exploring or exploiting:

Initialize Q(a) = 0 and N(a) = 0 for every arm a

For each round t = 1, 2, 3, ...:
    Draw a random number p between 0 and 1
    If p is less than epsilon:
        choose a uniformly random arm          (explore)
    Otherwise:
        choose the arm with the highest Q(a)   (exploit)
    Observe reward R from the chosen arm
    N(a) = N(a) + 1
    Q(a) = Q(a) + (R - Q(a)) / N(a)

With ε = 0.2, roughly one round in five is spent exploring at random, and the remaining four out of five rounds go to whatever currently looks best. This is called epsilon-greedy. It is not a clever algorithm — it does not even try to explore the arms it is most uncertain about more than the ones it is fairly sure of — and yet, because it guarantees that no arm is ever permanently ignored, it comfortably beats pure greedy on almost every bandit problem worth solving.

Tracing Epsilon-Greedy by Hand, Day by Day

Return to the four stalls, with true (hidden) average satisfaction ratings out of 10: A = 6, B = 8, C = 5, D = 9. The agent does not know these numbers — they exist only so we, watching from outside, can check whether the algorithm is learning correctly. Use ε = 0.2. To get every arm off the ground, the first four days are spent trying each stall exactly once, a common and sensible starting move before epsilon-greedy takes over — four untested stalls cannot be meaningfully compared to each other anyway.

• Day 1: try A (forced first visit). Reward = 6. Now Q(A) = 6, N(A) = 1.
• Day 2: try B (forced first visit). Reward = 8. Now Q(B) = 8, N(B) = 1.
• Day 3: try C (forced first visit). Reward = 5. Now Q(C) = 5, N(C) = 1.
• Day 4: try D (forced first visit). Reward = 9. Now Q(D) = 9, N(D) = 1. Current standings: A = 6, B = 8, C = 5, D = 9 — D looks best, but on a single visit each, that could easily be luck.
• Day 5: the random draw says exploit. The highest Q is D, so visit D again. Reward = 8. Update: Q(D) = 9 + (8 − 9) / 2 = 8.5, N(D) = 2.
• Day 6: the random draw says explore (roughly one day in five, on average). The random pick lands on B. Reward = 7. Update: Q(B) = 8 + (7 − 8) / 2 = 7.5, N(B) = 2.
• Day 7: exploit. D is still highest at 8.5, so visit D. Reward = 10. Update: Q(D) = 8.5 + (10 − 8.5) / 3 = 9.0, N(D) = 3.
• Day 8: exploit. D is highest at 9.0, so visit D. Reward = 9. Update: Q(D) = 9.0 + (9 − 9.0) / 4 = 9.0, N(D) = 4 — the reward matched the estimate exactly, so the estimate does not move.
• Day 9: explore again. The random pick lands on C. Reward = 4. Update: Q(C) = 5 + (4 − 5) / 2 = 4.5, N(C) = 2.
• Day 10: exploit. D is still highest at 9.0, so visit D. Reward = 8. Update: Q(D) = 9.0 + (8 − 9.0) / 5 = 8.8, N(D) = 5.

After ten days: Q(A) = 6 (visited once), Q(B) = 7.5 (twice), Q(C) = 4.5 (twice), Q(D) = 8.8 (five times). The algorithm has already worked out, correctly, that D deserves more than double the visits of any other stall, using nothing but the update rule from the previous section applied ten times in a row. Add up the ten rewards actually received — 6 + 8 + 5 + 9 + 8 + 7 + 10 + 9 + 4 + 8 — and the total comes to 74. Compare that to what an all-knowing agent would have earned by picking D, the true best arm, on all ten days: 10 × 9 = 90. The difference, 90 − 74 = 16, is the regret accumulated over these ten days: the price paid for starting with zero knowledge and spending several of the ten days on stalls that were not the best.

Scaling Up: Simulating Two Hundred Days in Code

Ten days by hand is enough to see the update rule working, but the real test of an algorithm is a long run, with real randomness in the rewards rather than numbers chosen by hand to make a point. The following Python program builds exactly the scenario above — the same four stalls, the same true ratings — but simulates a full 200-day run, with each day's reward drawn from a small random spread around the stall's true average rather than landing on it exactly.

import random

random.seed(7)

# True average satisfaction for each stall (the AGENT never sees these numbers directly)
true_rating = {"A": 6.0, "B": 8.0, "C": 5.0, "D": 9.0}
stalls = list(true_rating.keys())

def visit(stall):
    """Simulate one visit: reward varies a little around the true average."""
    return random.gauss(true_rating[stall], 1.2)

def epsilon_greedy(epsilon, days):
    Q = {s: 0.0 for s in stalls}   # estimated satisfaction per stall
    N = {s: 0 for s in stalls}     # number of visits per stall
    total = 0.0

    for day in range(days):
        if random.random() < epsilon:
            choice = random.choice(stalls)        # explore
        else:
            choice = max(Q, key=Q.get)             # exploit

        reward = visit(choice)
        N[choice] += 1
        Q[choice] += (reward - Q[choice]) / N[choice]
        total += reward

    return Q, N, total

Q, N, total = epsilon_greedy(epsilon=0.2, days=200)

print("Estimated satisfaction:", {s: round(v, 2) for s, v in Q.items()})
print("Number of visits:      ", N)
print("Total satisfaction over 200 days:", round(total, 1))

Running this program produces:

Estimated satisfaction: {'A': 6.29, 'B': 8.06, 'C': 4.66, 'D': 8.98}
Number of visits:       {'A': 15, 'B': 21, 'C': 7, 'D': 157}
Total satisfaction over 200 days: 1706.2

Two things are worth noticing. First, the estimated values the code arrived at on its own — roughly 6.3, 8.1, 4.7, and 9.0 — line up closely with the true hidden values of 6, 8, 5, and 9, even though the code never had access to those true values; it only ever saw noisy individual rewards, one at a time. Second, look at the visit counts: 157 of the 200 days went to Stall D, the true best arm, while the two worst stalls, A and C, received only 15 and 7 visits combined once the algorithm worked out they were not worth returning to. Epsilon-greedy did not need to know the answer in advance — it found the answer, and then mostly stopped paying the cost of looking further.

Now change one line — set epsilon=0.0, removing exploration entirely — and rerun. The pure greedy agent visits Stall A on day one, receives a decent but unremarkable rating, and from that point on, since every other stall's estimate is still stuck at its untouched starting value of zero, greedy exploitation keeps sending the agent back to A for all 200 days — it never tries B, C, or D again, not even once. Its total satisfaction over 200 days comes to 1193.8, noticeably below epsilon-greedy's 1706.2, and far below the 1800 an all-knowing agent would earn by picking Stall D, the true best option, every single day. The entire gap between 1706.2 and 1193.8 is the value that a controlled 20% of "wasted" exploration bought back in discovered knowledge.

Smarter Exploration: A Glimpse Beyond Epsilon-Greedy

Epsilon-greedy has one obvious flaw: when it decides to explore, it picks completely at random among all arms, including ones it has already tried hundreds of times and is quite sure about. A smarter agent would explore the arms it is most uncertain about and mostly leave alone the arms it has already measured carefully, whether they turned out good or bad. Two well-known approaches do exactly this.

Upper Confidence Bound (UCB) replaces the coin-flip decision with a single formula applied to every arm, picking whichever arm scores highest on:

Q(a) + c * sqrt( ln(t) / N(a) )

The first term, Q(a), is the familiar estimate. The second term is a bonus that rewards uncertainty: N(a) sits in the denominator, so an arm tried only a handful of times gets a large bonus added to its score, while an arm tried hundreds of times gets almost no bonus at all, since its value is already well known, good or bad. As the round number t grows, the bonus grows too, but only very slowly, through the natural logarithm ln, which keeps a trickle of exploration alive across every arm without ever letting it dominate. The constant c controls how generous that bonus is. This principle — stay optimistic about anything you are not yet sure of — is often summarized as "optimism in the face of uncertainty," and it tends to reach the best arm faster than epsilon-greedy because it directs its exploration purposefully instead of scattering it uniformly at random.

Thompson Sampling takes a different route: instead of one number per arm, it keeps an entire probability distribution representing everything it currently believes about that arm's true value. On each round it draws one random sample from every arm's belief distribution and picks whichever sampled value is highest, then narrows that arm's distribution slightly using the new observation. Arms with wide, uncertain distributions occasionally produce a high sample purely by chance, which naturally sends the algorithm to explore them; arms already pinned down tightly rarely produce a surprising sample. The idea predates modern computing by decades — the statistician William Thompson proposed essentially this method in 1933, in the context of deciding which of two medical treatments to give more patients to while a trial was still running, which is exactly a bandit problem: the goal is to help the patients inside the trial, not only the ones who arrive after it ends.

Where Bandits Run in the Real World

The chai-stall version of this problem is small enough to trace by hand, but the identical structure — a limited number of options, an unknown payoff for each, and a stream of decisions to make one after another while learning — shows up anywhere a system has to learn while it operates.

• Website design testing. Choosing between two versions of a checkout button is a bandit problem, with each design as an arm and "did the visitor complete the purchase" as the reward. Treating it as a bandit instead of a fixed 50/50 split lets a site automatically send more visitors to whichever version is winning as evidence builds up, rather than waiting for a test to fully conclude before acting on what it already strongly suspects.
• Recommendation and content platforms. Choosing which thumbnail image best represents a show, out of several candidates, is a bandit problem with clicks as the reward — streaming platforms have publicly written about using this style of algorithm for artwork personalization.
• Online advertising. Deciding which advertisement to place in front of a given visitor, out of many eligible ads, is a bandit problem with a click or purchase as the reward.
• Clinical trials. Deciding how many patients to allocate to each of several treatments while a trial is still running is the very problem Thompson Sampling was invented for. Here the regret being minimized is not money but patient outcomes, which is exactly why shifting weight toward the better-performing treatment sooner rather than later matters so much.

In every one of these examples, the two failure modes from the chai-stall story reappear in disguise. Pure exploitation looks like a company that redesigns its homepage once, likes the first result, and never questions it again, even as better alternatives go untested. Pure exploration looks like a system that keeps testing everything forever and never actually commits to serving its users the best option it has already found. The organizations that get this right are, whether they use the term or not, running some version of epsilon-greedy, UCB, or Thompson Sampling underneath.

Back to the Chai Stalls

Ten months of coaching is roughly two hundred mornings — close to the two hundred days simulated in the code above. Walking to Stall A out of habit every single day is pure exploitation, and it caps your mornings at whatever Stall A happens to be worth, forever, with no chance of improvement. Trying a different stall every single day out of pure curiosity is pure exploration, and it guarantees you will eventually know which stall is best while still eating at the worst ones on a quarter of your mornings, right through to the week before the exam. The better approach, and the one this chapter built up from scratch, is neither: spend most mornings at whichever stall currently looks best, but deliberately keep a small, steady slice of mornings — a fifth, a tenth, whatever the situation calls for — for the stall you have not fully tested yet. That slice feels like a loss each time you spend it. Over two hundred mornings, it is the only reason you end up finding Stall D at all.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where multi-armed bandits: exploration vs exploitation is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting multi-armed bandits: exploration vs exploitation to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind multi-armed bandits: exploration vs exploitation, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.