Exploration vs. Exploitation

Why Does This Exist?

An agent that always takes the action it currently estimates as best will never discover that a different action might be better — especially early in training when all estimates are unreliable. An agent that always takes random actions never benefits from what it has learned.

This tension is fundamental: you must try things to know if they're good, but trying random things wastes time you could spend using what you already know. The exploration-exploitation tradeoff is the core tension every RL algorithm must navigate.

Think of It Like This

How It Actually Works

$\varepsilon$-greedy

The simplest strategy: with probability $\varepsilon$ take a uniformly random action; with probability $1 - \varepsilon$ take the greedy (best-estimated) action.

1if random.random() < epsilon:2    action = env.action_space.sample()  # explore3else:4    action = np.argmax(Q[state])         # exploit

Strength: Simple, widely used, works well in practice.
Weakness: Wastes exploration budget on clearly suboptimal actions — treats all non-greedy actions equally, regardless of how bad they are.
Fix: Anneal $\varepsilon$ over time: $\varepsilon_t = \varepsilon_0 \cdot \text{decay}^t$, converging toward pure exploitation.

Upper Confidence Bound (UCB)

UCB adds an uncertainty bonus to less-visited actions — optimism in the face of uncertainty:

$a^* = \arg\max_a \left[Q(a) + c\sqrt{\frac{\ln t}{N(a)}}\right]$

Where $N(a)$ is the visit count for action $a$ and $t$ is the total number of steps taken. As an action is visited more, its uncertainty bonus $\sqrt{\ln t / N(a)}$ shrinks toward zero.

UCB achieves $O(\ln t)$ regret — provably better than $\varepsilon$-greedy's $O(t^{2/3})$ regret for the bandit problem.

Thompson Sampling (Bayesian exploration)

Maintain a posterior distribution over Q-values (or reward probabilities) for each action. At each step, sample one Q-value from each action's posterior and take the action with the highest sample:

1. For each arm $a$, sample $\tilde{q}_a \sim \text{Posterior}(Q(a))$
2. Take action $a^* = \arg\max_a \tilde{q}_a$
3. Observe reward; update posterior

As data accumulates, posteriors tighten and exploration naturally decreases. Empirically excellent across many bandit settings.

Curiosity-driven / intrinsic motivation

For sparse-reward environments where the agent rarely encounters the extrinsic reward, add an intrinsic reward based on novelty or prediction error:

$r_{\text{total}} = r_{\text{extrinsic}} + \beta \cdot r_{\text{intrinsic}}$

Where $r_{\text{intrinsic}}$ measures how surprising the transition was — typically the prediction error of a neural network trained to predict next states. Surprising transitions (high prediction error) get a bonus reward, systematically driving exploration toward novel areas.

Code

1import numpy as np2
3class MultiArmedBandit:4    """k-armed bandit with Gaussian rewards."""5    def __init__(self, k=10):6        self.k = k7        self.true_means = np.random.normal(0, 1, k)8    9    def pull(self, arm):10        return self.true_means[arm] + np.random.normal(0, 1)11    12    @property13    def optimal_arm(self):14        return np.argmax(self.true_means)15
16
17def epsilon_greedy(bandit, n_steps=2000, epsilon=0.1):18    Q = np.zeros(bandit.k)19    N = np.zeros(bandit.k)20    rewards = []21    for t in range(n_steps):22        action = (np.random.randint(bandit.k)23                  if np.random.random() < epsilon24                  else np.argmax(Q))25        reward = bandit.pull(action)26        N[action] += 127        Q[action] += (reward - Q[action]) / N[action]  # incremental mean28        rewards.append(reward)29    return rewards30
31
32def ucb(bandit, n_steps=2000, c=2.0):33    Q = np.zeros(bandit.k)34    N = np.zeros(bandit.k) + 1e-5  # avoid division by zero35    rewards = []36    for t in range(1, n_steps + 1):37        ucb_values = Q + c * np.sqrt(np.log(t) / N)38        action = np.argmax(ucb_values)39        reward = bandit.pull(action)40        N[action] += 141        Q[action] += (reward - Q[action]) / N[action]42        rewards.append(reward)43    return rewards44
45
46def thompson_sampling(bandit, n_steps=2000):47    """Beta-Bernoulli Thompson Sampling (assumes rewards in [0,1])."""48    alpha = np.ones(bandit.k)  # successes + 149    beta  = np.ones(bandit.k)  # failures + 150    rewards = []51    # Normalize true means to [0,1] for this demo52    means_01 = (bandit.true_means - bandit.true_means.min())53    means_01 /= means_01.max() + 1e-854    for _ in range(n_steps):55        samples = np.random.beta(alpha, beta)56        action = np.argmax(samples)57        # Simulate binary reward58        reward = float(np.random.random() < means_01[action])59        alpha[action] += reward60        beta[action]  += 1 - reward61        rewards.append(reward)62    return rewards63
64
65# Compare strategies66np.random.seed(42)67bandit = MultiArmedBandit(k=10)68print(f"Optimal arm: {bandit.optimal_arm}, true mean: {bandit.true_means[bandit.optimal_arm]:.2f}")69
70eg_r  = epsilon_greedy(bandit)71ucb_r = ucb(bandit)72ts_r  = thompson_sampling(bandit)73
74print(f"ε-greedy (ε=0.1) avg reward: {np.mean(eg_r):.3f}")75print(f"UCB (c=2.0)       avg reward: {np.mean(ucb_r):.3f}")76print(f"Thompson sampling avg reward: {np.mean(ts_r):.3f}")

Watch Out For

The Quick Version

• Exploration (trying new actions) and exploitation (using known good actions) must be balanced at every step.
• $\varepsilon$-greedy: simplest — take random action with probability $\varepsilon$, anneal over time.
• UCB: optimism in uncertainty — add $c\sqrt{\ln t / N(a)}$ bonus to less-visited actions.
• Thompson Sampling: sample from posterior, act on the sample — provably excellent empirically.
• Intrinsic motivation: add novelty rewards for sparse-reward environments where extrinsic signal is rare.