Exploration vs Exploitation

Measuring the cost of learning: regret

How do we score an exploration strategy? Not by raw reward, that depends on the arms' values, but by regret: how much reward we lost compared to an oracle that always pulls the best arm. If the best arm has mean $q_\star = \max_a q_\star(a)$, the total regret after $T$ rounds is:

$\text{Regret}(T) = T\, q_\star - \sum_{t=1}^{T} \mathbb{E}\big[\, r_t \,\big] = \sum_{t=1}^{T}\big(q_\star - q_\star(a_t)\big).$

Every time you pull a suboptimal arm you add its gap from the best arm to the regret total. Good strategies make regret grow sublinearly, the per-round regret shrinks toward zero as you learn, while a strategy that never stops exploring uniformly (or never explores at all and got unlucky) suffers regret growing linearly forever.

A tiny regret calculation

Suppose two arms with true means $q_\star(A) = 1.0$ and $q_\star(B) = 0.7$, so the gap is $0.3$. Over $T = 100$ rounds a strategy pulls the worse arm $B$ on $20$ of them and the best arm $A$ on the other $80$. The regret is simply the gap times the number of mistaken pulls:

$\text{Regret}(100) = 20 \times (1.0 - 0.7) = 20 \times 0.3 = 6.0.$

An oracle would have scored $100 \times 1.0 = 100$; this strategy expects $100 - 6 = 94$. The whole game of exploration design is driving that "6" down by making the bad-arm pulls both few and concentrated early, while still pulling $B$ enough to be sure it is worse.

Strategy 1: epsilon-greedy

The simplest workable rule. Maintain an estimate $Q(a)$ of each arm's mean. Most of the time act greedily (pick the highest estimate); occasionally, with small probability $\epsilon$, pick a random arm to keep gathering information.

$a_t = \begin{cases} \arg\max_a Q(a) & \text{with probability } 1 - \epsilon \\ \text{a uniformly random arm} & \text{with probability } \epsilon \end{cases}$

def epsilon_greedy(Q, epsilon=0.1):
    if random.random() < epsilon:
        return random.randrange(len(Q))   # explore: any arm
    return argmax(Q)                       # exploit: best estimate so far

Epsilon-greedy is trivial to implement and surprisingly effective, but it has a flaw: its exploration is undirected. It is equally likely to re-test an arm it already knows is terrible as one it is genuinely unsure about. And with a fixed $\epsilon$ it keeps making random pulls forever, so its regret grows linearly. The usual fix is to decay $\epsilon$ over time, explore hard early, then increasingly exploit.

Strategy 2: optimism under uncertainty

A smarter principle: be optimistic about what you have not yet tried. Initialize every arm's estimate to a high value. Then the agent, acting greedily, is naturally drawn to under-explored arms because their inflated estimates make them look attractive, until real data pulls the estimate down to its true level. Exploration becomes a built-in consequence of greedy behavior, requiring no randomness at all.

The slogan "optimism in the face of uncertainty" captures the intuition: assume the untried option might be great, try it, and let evidence correct you. Arms that really are good stay attractive; arms that are bad get demoted quickly. This directs exploration toward genuinely uncertain options instead of scattering it uniformly.

Strategy 3: UCB (upper confidence bound)

UCB makes optimism precise. Instead of a one-time optimistic initialization, it adds an explicit uncertainty bonus to each arm's estimate every round, larger for arms pulled fewer times. It then picks the arm with the highest optimistic upper bound:

$a_t = \arg\max_{a}\left[\, Q(a) + c\,\sqrt{\frac{\ln t}{N(a)}} \,\right],$

where $N(a)$ is the number of times arm $a$ has been pulled, $t$ is the current round, and $c > 0$ tunes exploration strength. Read the two terms:

• $Q(a)$, the exploitation term: how good the arm looks on average.
• $c\sqrt{\ln t / N(a)}$, the exploration bonus: large when $N(a)$ is small (little data, high uncertainty) and shrinking as the arm is pulled more. The $\ln t$ keeps a slow trickle of exploration alive so a neglected arm is eventually revisited.

Why exploration gets much harder in deep RL

Bandits are gentle: one decision, immediate feedback, a handful of arms. Full deep RL breaks all three assumptions, and exploration becomes one of its central open problems.

• Enormous state spaces. With images or text as states there are effectively infinitely many, so "try every state–action pair enough times" is impossible. UCB-style visit counts $N(s,a)$ do not even fit in memory; you need learned density models or hashing to approximate "how novel is this state?"
• Delayed and sparse rewards. In hard exploration games reward may come only after a long, specific sequence of correct actions. Random ($\epsilon$-greedy) exploration has a vanishing chance of stumbling onto it, like finding a needle by flailing.
• Deep exploration. The agent must sometimes take a coordinated sequence of exploratory actions to reach an informative region, not just one random step. Per-step randomness cannot plan such trajectories.

These pressures gave rise to modern methods: intrinsic motivation and curiosity (reward the agent for reaching surprising or novel states), count-based bonuses with pseudo-counts for high-dimensional states, and noise-in-parameters approaches like NoisyNets. The core principle you learned here, optimism and uncertainty-directed exploration, survives, but scaling it to rich environments remains an active research frontier.

Further reading

• Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), Chapter 2, bandits, epsilon-greedy, optimistic initialization, and UCB: http://incompleteideas.net/book/the-book.html
• Lattimore & Szepesvári, Bandit Algorithms, the rigorous modern reference on regret and UCB: https://tor-lattimore.com/downloads/book/book.pdf
• OpenAI Spinning Up, "Exploration vs. Exploitation" within the RL intro, a concise applied framing: https://spinningup.openai.com/en/latest/spinningup/rl_intro.html
• Bellemare et al., "Unifying Count-Based Exploration and Intrinsic Motivation" (2016), scaling optimism to deep RL via pseudo-counts: https://arxiv.org/abs/1606.01868
• UC Berkeley CS285, "Exploration" lectures, deep-RL exploration methods in depth: https://rail.eecs.berkeley.edu/deeprlcourse/