Adaptive Intelligence, Part 2

“Yet knowing how way leads on to way,
I doubted if I should ever come back.”
— Robert Frost, The Road Not Taken

Maurício Veloso Brant Pinheiro

Founder and Editor, AI-Talks.org

17 Jul 2026

16–24 minutes

Abstract

This second article in the Adaptive Intelligence series examines the classical Multi-Armed Bandit problem, the simplest mathematical model of learning through repeated action, feedback, and uncertainty. Building on the previous discussion of the 37% Rule and the exploration–exploitation dilemma, the article explains how an agent must choose among uncertain options, estimate their value, and balance immediate reward against the need for information. It introduces the casino analogy, the basic mathematical structure of bandits, expected reward, regret, and early strategies such as random exploration, the greedy strategy , epsilon-greedy, optimistic initialization, Upper Confidence Bound, and Thompson Sampling. The central argument is that intelligent systems do not merely use data — they create data through action, paying the price of learning before they can make better decisions.

Keywords

Adaptive Intelligence, Adaptive AI, Artificial Intelligence, Multi-Armed Bandit, Exploration vs. Exploitation, Reinforcement Learning, Decision Making Under Uncertainty, Sequential Decision Making, Expected Reward, Regret, Epsilon-Greedy, Upper Confidence Bound, Thompson Sampling

Learning, Reward, and the Cost of Uncertainty

In the first article of the Adaptive Intelligence series, we began with a simple but unsettling idea: every intelligent decision begins before certainty arrives.

The 37% Rule showed us one version of that problem. When facing a sequence of options with no possibility of going back, the challenge is to decide when to stop searching and commit. Explore too little, and you choose blindly. Explore too long, and the best opportunity may disappear.

But many intelligent systems do not choose only once.

They choose again and again.

A recommendation system does not show one video and vanish. A scientist does not run one experiment and retire. A robot does not take one action and stop existing. A medical system does not evaluate only one treatment forever. An AI agent does not select one tool, one prompt, or one strategy for all possible futures.

Real intelligence often happens through repeated interaction:

choose, observe, update, choose again.

That is the world of the Multi-Armed Bandit.

The classical Multi-Armed Bandit is the cleanest possible model of learning by trial and error. There is no deep memory of the world. There is no changing environment. There is no long chain of consequences. There is only an agent, a set of uncertain actions, and a sequence of rewards.

That simplicity is exactly what makes the problem powerful.

The Multi-Armed Bandit strips decision-making down to one primitive question:

Which option should I try next?

The question is simple enough to formalize, but broad enough to appear almost everywhere. It is the skeleton beneath online advertising, recommendation systems, clinical trials, trading strategies, robotics, scientific discovery, and reinforcement learning.

In its classical form, the problem assumes a stable world. Each option has an unknown reward pattern, but that pattern does not change over time. The agent’s task is to discover, through repeated interaction, which option produces the highest expected reward.

This is uncertainty in laboratory form:

the world is hidden, but it is not moving.

That assumption will later become the central weakness of the classical model. But before we can understand restless worlds, changing environments, and adaptive AI, we need to understand why the classical Multi-Armed Bandit became so important.

The Casino Analogy

Imagine a gambler standing in front of several slot machines.

The name of the problem comes from old slot machines, often called one-armed bandits because they had a single lever — one “arm” — and a reliable tendency to take the gambler’s money over time. The Multi-Armed Bandit imagines several such machines, each with an unknown chance of paying out.

One machine may be generous. Another may be terrible. A third may look promising at first but disappoint later. The gambler does not know the true probability of reward behind any of them.

Each machine is an arm.

At every round, the gambler must choose one arm to pull. After pulling it, the gambler receives a reward or receives nothing. Then the process repeats:

choose, observe, update, choose again.

The goal is not simply to identify the best machine eventually. The goal is to maximize total reward during the entire learning process.

That distinction is crucial.

If the gambler wanted only knowledge, the best strategy would be to test every machine many times. But testing bad machines costs money. If the gambler wanted only immediate reward, the best strategy would be to keep pulling the machine that currently looks best. But that may trap the gambler in a mediocre option discovered early by chance.

The bandit problem exists because learning itself is expensive.

In artificial intelligence, the casino metaphor becomes far more general.

An arm can be an advertisement shown to a user; the reward is a click, a purchase, or a conversion.

An arm can be a movie, video, or song recommendation; the reward is engagement, satisfaction, or retention.

An arm can be a drug candidate in a clinical trial; the reward is patient improvement, reduced symptoms, or survival.

An arm can be a trading strategy; the reward is profit adjusted by risk.

An arm can be a route chosen by a delivery robot; the reward is speed, safety, or energy efficiency.

An arm can be a prompt, tool, or model selected by an AI agent; the reward is task success, accuracy, or user satisfaction.

An arm can be a scientific hypothesis; the reward is experimental evidence, explanatory power, or a breakthrough.

In every case, the structure is the same: the agent must choose an option, observe the result, update its belief, and choose again.

This is why the Multi-Armed Bandit is not really about gambling. It is about the cost of learning in a world where feedback only arrives after action.

To make this structure precise, we now need to move from metaphor to mathematics.

The Basic Mathematical Structure

In the classical Multi-Armed Bandit, an agent has (K) possible actions, usually called arms.

At each time step (t), the agent chooses one arm from the available set. We denote the arm selected at time (t) by:

A_t

If the agent selects a particular generic arm (a), we write:

A_t = a

After choosing that arm, the agent receives a reward:

R_t

Each arm (a) has a true expected reward:

q^{\star}(a) = \mathbb{E}[R_t \mid A_t = a]

In plain language, q*(a) is the average reward the agent would expect to receive if it selected arm (a) many times under the same conditions.

The problem is that q*(a) is unknown.

The agent must estimate it from experience. Its estimate at time (t) is usually written as:

Q_t(a)

So the learning problem is:

Q_t(a) \approx q^{\star}(a)

The agent wants its estimate Q_t(a) to become close to the true value q*(a). But it faces a major limitation: it only observes the reward of the arm it actually selected.

If it chooses arm A, it learns something about A.

It learns nothing directly about B, C, or D.

This is called partial feedback.

In supervised learning, the model is usually given examples in advance. In a bandit problem, the agent creates its own training data by acting. That makes the learning process policy-dependent. What the agent chooses affects what it gets to know.

A simple estimate of an arm’s value is the sample average. If arm (a) has been selected N_t(a) times, then:

Q_t(a) = \frac{1}{N_t(a)} \sum_{i=1}^{N_t(a)} R_i(a)

The sum is taken over the rewards received from choosing arm (a).

This is intuitive. Try an option several times, average the results, and use that average as the estimate of its value.

But there is a trap.

An arm tried only twice may look excellent because of luck. Another arm tried only twice may look terrible because of bad luck. Early randomness can distort judgment. The agent must therefore decide not only which arm has the highest estimate, but also which estimate is trustworthy.

This is where exploration and exploitation become unavoidable.

Balancing Reward and Information

The agent has two competing objectives.

It wants reward now.

It wants information for later.

Exploitation means choosing the arm that currently appears to offer the highest estimated value. If the agent’s estimate of arm (a) at time (t) is Q_t(a), then a purely greedy strategy selects:

A_t = \arg\max_a Q_t(a)

In plain language: choose the arm with the highest current estimate.

This sounds rational. After all, why not choose the option that looks best?

The problem is that Q_t(a) is only an estimate. Early estimates may be based on very little evidence. An arm may look good because it was lucky. Another may look bad because it was unlucky. A greedy agent can therefore confuse noise with knowledge.

Suppose an agent tries three arms once.

Arm 1 gives a reward of 8, so:

Q_t(1) = 8

Arm 2 gives a reward of 2, so:

Q_t(2) = 2

Arm 3 gives a reward of 1, so:

Q_t(3) = 1

A greedy agent now compares these estimates and chooses the arm that maximizes Q_t(a):

A_{t+1} = \arg\max_a Q_t(a)

Since Q_t(1) is currently the largest estimate, the greedy agent chooses arm 1 again.

This may look reasonable, but it can be misleading. The values Q_t(1) , Q_t(2) and Q_t(3) are based on only one observation each. Arm 1 may have been lucky. Arm 2 or arm 3 may have been unlucky. If the agent exploits arm 1 too soon, it may never collect enough evidence to discover that another arm has a higher true expected reward.

This is the danger of premature certainty:

when N_t(a) is small, the agent may mistake a fragile estimate Q_t(a) for the true value q*(a).

Exploration means deliberately choosing an arm that may not currently look best, but whose uncertainty is still worth investigating. Exploration protects the agent from being trapped by early randomness. It gives apparently weaker options a chance to reveal their true value.

But exploration also has a cost. Trying uncertain arms means sometimes ignoring the option that currently appears best. The agent may sacrifice immediate reward in exchange for information that may or may not prove useful later.

That is why the problem is not solved by simply saying “explore more.”

Too little exploration creates blindness.

Too much exploration creates waste.

The core challenge is to explore just enough.

This is why bandit algorithms are not merely reward-maximizing machines. They are uncertainty-management systems. A good bandit algorithm must decide not only which arm appears best, but also how reliable that appearance is.

At every step, it must ask:

How good does this option currently appear to be?

How uncertain is that estimate?

How much future value could be gained by learning more?

The classical Multi-Armed Bandit is important because it turns these questions into mathematics. It shows that intelligent action is not only about choosing the best-known option. It is about knowing when the best-known option is not yet known well enough.

To make that trade-off measurable, we need a way to evaluate not only how much reward the agent receives, but also how much reward it loses while learning.

This is where the idea of regret enters.

Expected Reward and Regret

The natural goal of the agent is to maximize total reward over time.

If the agent runs for (T) time steps, its total reward is:

R_1 + R_2 + R_3 + \cdots + R_T = \sum_{t=1}^{T} R_t

But in bandit theory, performance is often measured using regret.

Regret measures how much reward the agent loses by not always choosing the best possible arm.

Let a* be the optimal arm:

a^{\star} = \arg\max_a q^{\star}(a)

If the agent knew the true values q*(a), it would always choose a*. But it does not know them. It must learn through experience.

At time (t), if the agent chooses A_t instead of a*, the expected loss is:

\operatorname{Regret}(t) = q^{\star}(a^{\star}) – q^{\star}(A_t)

Cumulative regret over (T) steps is the total expected loss accumulated during learning:

\operatorname{Regret}(T) = \sum_{t=1}^{T} \left[ q^{\star}(a^{\star}) – q^{\star}(A_t) \right]

This idea is powerful because it treats mistakes as part of learning.

A learning agent cannot avoid regret completely. If the best arm is unknown, the agent must sometimes make suboptimal choices. The real question is not whether mistakes will happen, but whether those mistakes teach the agent something useful.

There is an important subtlety here: the agent usually cannot calculate true regret while it is learning. The quantities (q^{\star} q*(a*) and q*(A_t) are unknown. If the agent already knew the true value of every arm, there would be no bandit problem.

For this reason, regret is best understood as a theoretical benchmark. It tells us how much reward was lost compared with an ideal agent that already knew the optimal arm from the beginning.

In simulations, this can be calculated because the true reward distributions are known by design.

In real applications, regret must usually be estimated after the fact, using accumulated data, controlled experiments, or comparison with the best-performing option observed over time.

The agent itself does not observe regret directly.

It only observes rewards.

It tries to reduce future regret indirectly by improving its estimates, exploring uncertain arms, and exploiting arms that appear reliable.

Bad regret comes from ignorance that never improves.

Good regret comes from exploration that reduces uncertainty.

The goal of a bandit algorithm is not to make no mistakes. That would be impossible. The goal is to make mistakes that become less frequent, less costly, and more informative over time.

In a good algorithm, cumulative regret grows slowly. The agent learns enough about the arms to concentrate more and more on the best options.

In a bad algorithm, regret grows quickly. The agent either explores too much, wasting reward on poor options, or commits too early to the wrong option and never recovers.

This is one of the most important lessons for artificial intelligence:

learning is not free.

Every intelligent system pays for information through time, computation, risk, or lost reward.

Early Strategies for Solving the Bandit Problem

The first strategies for the Multi-Armed Bandit are simple, but they reveal the logic behind nearly all later approaches. Each strategy defines a policy: a rule that tells the agent which arm (A_t) to choose at time (t), given what it currently knows.

The central question is always the same:

How should an agent act when its own knowledge is still incomplete?

Some policies explore randomly. Some exploit the best current estimate. Others try to measure uncertainty directly. What changes from one strategy to another is not the problem, but the way the agent manages ignorance.

Pure Random Exploration

Pure random exploration is the simplest strategy. The agent chooses an arm at random at every step, ignoring everything it has learned so far. If there are (K) arms, each arm has the same probability of being selected:

A_t \sim \operatorname{Uniform}\left({1,2,\ldots,K}\right)

or, equivalently:

P(A_t = a) = \frac{1}{K}

This guarantees that all options will eventually be tested, so no arm is ignored forever. But it also wastes knowledge. Even when one option clearly looks better, the agent continues testing weak options as if nothing had been learned.keeps testing weak options as if nothing had been learned. Randomness produces information, but by itself it is not intelligence.

Greedy Exploitation

Greedy exploitation does the opposite. The agent always chooses the arm that currently looks best. If (Q_t(a)) is the estimated value of arm (a) at time (t), then the greedy policy is:

A_t = \arg\max_a Q_t(a)

This can work well when the estimates are reliable, but it is dangerous at the beginning, when the agent has very little evidence. A lucky first result can make a mediocre arm look excellent, while an unlucky result can make a good arm look bad. Greedy exploitation uses information, but it may trust that information too soon.

Epsilon-Greedy

The epsilon-greedy strategy is a simple compromise between exploration and exploitation. Most of the time, the agent chooses the arm that currently looks best. But occasionally, with a small probability called eepsilon (ε), the agent ignores its current estimates and explores by choosing a random arm.

Let ( $\mathcal{A}$ ) be the set of all available arms — that is, all the options the agent can choose from.

With probability (1-ε), the agent exploits:

A_t = \arg\max_{a \in \mathcal{A}} Q_t(a)

With probability ε, the agent explores:

A_t \text{ is chosen randomly}

For example, if ε = 0.1, the agent exploits the best current estimate 90% of the time and explores randomly 10% of the time. This prevents it from becoming completely trapped by early mistakes. Its weakness is that exploration is still blind: the agent may keep testing arms that already appear poor instead of focusing on options whose uncertainty truly matters.

Optimistic Initialization

Optimistic initialization uses the same greedy policy, but changes how learning begins. The agent starts by assuming that every arm might be very good:

Q_0(a) = Q_{\text{high}}

where ( $Q_{\text{high}}$ ) is an intentionally optimistic initial value. Then the agent follows the greedy rule:

A_t = \arg\max_a Q_t(a)

Untested arms look attractive at the beginning, which forces the agent to explore them. When an arm is tried and produces disappointing rewards, its estimate becomes more realistic. The beauty of this strategy is that curiosity is created by optimism. The limitation is that the result depends heavily on how optimistic the initial assumptions are. Too little optimism ends exploration too early; too much optimism wastes time.

Upper Confidence Bound

Upper Confidence Bound, or UCB, makes exploration more disciplined. Instead of asking only which arm looks best, it asks which arm could plausibly be best given what is still unknown. A common UCB policy is:

A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]

The first term, Q_t(a), measures current estimated reward. The second term is an uncertainty bonus. If an arm has been tried only a few times, N_t(a) is small, so the uncertainty bonus is large. As the arm is selected more often, uncertainty decreases and the bonus shrinks. UCB is powerful because exploration is no longer random; it is directed toward uncertainty.

Thompson Sampling

Thompson Sampling takes a probabilistic view. Instead of treating each arm as having one fixed estimate, the agent keeps a probability distribution over the possible value of each arm. At each time step, it samples one possible value for every arm:

\theta_a \sim P(q^{\star}(a) \mid \text{data})

Then it chooses the arm with the highest sampled value:

A_t = \arg\max_a \theta_a

This makes exploration emerge naturally. Arms with high uncertainty sometimes receive high sampled values, so they continue to be explored. Arms that are clearly poor are selected less often because their probability of being the best becomes small. Thompson Sampling explores each option roughly in proportion to the probability that it might actually be optimal.

The Common Logic Behind Bandit Strategies

All these strategies are different ways of managing uncertainty.

Pure random exploration says: test everything.

Greedy exploitation says: choose what currently looks best.

Epsilon-greedy says: most of the time, use the best current estimate; occasionally, explore.

Optimistic initialization says: treat the unknown as promising until evidence says otherwise.

Upper Confidence Bound, or UCB, says: choose based on reward plus uncertainty.

Thompson Sampling says: choose according to the probability that each arm might be best.

They all try to solve the same fundamental problem:

How should an agent act when its own knowledge is incomplete?

The classical Multi-Armed Bandit answers this question under one powerful simplifying assumption: the world is stationary. The reward distribution of each arm does not change while the agent learns.

This assumption makes the mathematics beautiful.

It also makes the model incomplete.

Conclusion: The Price of Learning

The classical Multi-Armed Bandit teaches a hard lesson: intelligence is not free.

To learn, an agent must act. To act, it must risk being wrong. Every experiment has a cost. Every uncertain choice spends time, attention, computation, or reward. The agent cannot stand outside the world and wait for perfect information. It must create information by touching reality.

That is why the bandit problem is so important for artificial intelligence. It shows that learning is not merely the passive extraction of patterns from pre-existing data. Learning is an active process of deciding what data should exist next.

A purely greedy system is fragile because it trusts early evidence too much.

A purely random system is wasteful because it ignores what it has learned.

An intelligent system must live between these two failures.

It must exploit what seems reliable without becoming trapped by premature certainty. It must explore what remains uncertain without dissolving into useless randomness. It must pay the price of learning, but not pay it forever.

The classical Multi-Armed Bandit gives this problem its simplest and cleanest mathematical form. It reveals the central architecture of adaptive decision-making: reward, uncertainty, feedback, estimation, regret, and action.

But it also leaves us with a deeper question.

Is there a way to compress this entire trade-off — exploration and exploitation, immediate reward and future information, uncertainty and action — into a single elegant rule?

That question leads directly to one of the most beautiful results in decision theory:

the Gittins Index.

The next article in the Adaptive Intelligence series will examine the Gittins Index: how it emerged from the classical bandit problem, why it is mathematically elegant, and why it remains one of the most important ideas for understanding optimal decision-making under uncertainty.

References and Suggested Reading

Why Every Intelligent Decision Begins Before Certainty

The 37% Rule

Christian, Brian, and Tom Griffiths. Algorithms to Live By: The Computer Science of Human Decisions. New York: Henry Holt and Company, 2016.

Sutton, Richard S., and Andrew G. Barto. Reinforcement Learning: An Introduction. 2nd ed. Cambridge, MA: MIT Press, 2018.

Robbins, Herbert. “Some Aspects of the Sequential Design of Experiments.” Bulletin of the American Mathematical Society 58, no. 5, 1952: 527–535.

Ferguson, Thomas S. “Who Solved the Secretary Problem?” Statistical Science 4, no. 3, 1989: 282–289.

Gittins, John C. “Bandit Processes and Dynamic Allocation Indices.” Journal of the Royal Statistical Society: Series B 41, no. 2, 1979: 148–177.

Whittle, Peter. “Restless Bandits: Activity Allocation in a Changing World.” Journal of Applied Probability 25, 1988: 287–298.

Editorial transparency note: This article, as with all articles published on this site, was conceived, directed, written, and reviewed by Prof. Maurício Veloso Brant Pinheiro. Artificial intelligence was used as an assistant for editorial refinement, formatting, image generation, SEO metadata, and publication workflow.