Exploration vs exploitation tradeoff: Exercises

Before we start, one glossary of every symbol so nothing appears un-earned:

Definition Symbols used on this page

$A$ ::: the set of available actions; $∣ A ∣$ (its size) equals $K$ , the number of arms. We write $K$ when counting, $∣ A ∣$ when it appears inside a probability formula — they are the same number.
$K$ ::: the number of actions (arms) you can choose from, i.e. $K = ∣ A ∣$ .
$μ_{a}$ ::: the true (unknown) average reward of action $a$ .
$μ^{*}$ ::: the best possible average, $μ^{*} = max_{a} μ_{a}$ .
$a^{*}$ ::: the optimal action — the arm that attains $μ^{*}$ , i.e. $a^{*} = ar g max_{a} μ_{a}$ .
$a_{t}$ ::: the action actually chosen at step $t$ ; its mean reward is $μ_{a_{t}}$ .
$Δ$ ::: the gap of a suboptimal arm, $Δ = μ^{*} - μ_{a}$ ; the per-pull reward you lose by playing that arm instead of $a^{*}$ .
$Q_{t} (a)$ ::: your current estimate of $μ_{a}$ at step $t$ (a sample mean).
$N_{t} (a)$ ::: how many times you have tried action $a$ up to step $t$ .
$ϵ$ ::: probability of taking a random action in $ϵ$ -greedy.
$Regret (T)$ ::: the reward you lost over $T$ steps by not always playing the optimal arm. Precisely, it is the gap between what the optimal arm would have earned and what your chosen arms earn on average: $Regret (T) = T μ^{*} - \sum_{t = 1}^{T} μ_{a_{t}} = \sum_{t = 1}^{T} (μ^{*} - μ_{a_{t}}) = \sum_{t = 1}^{T} Δ_{a_{t}} .$ The last form shows regret is just the running total of per-pull gaps $Δ_{a_{t}}$ .
$c$ ::: a tuning knob that scales the UCB exploration bonus.

Level 1 — Recognition

Recall Solution 1.1

(a) Exploitation — it uses known good info, no new information gained. (b) Exploration — uncertain outcome, gathers information. (c) Exploration — landing in the $ϵ$ band forces a random pick to gather data.

Recall Solution 1.2

$μ^{*} = max (0.6, 0.8) = 0.8$ , and the optimal arm is $a^{*} = B$ .

Level 2 — Application

Recall Solution 2.1

Sample mean = sum of rewards / number of pulls. $Q_{t} (A) = \frac{1 + 0 + 1}{3} = \frac{2}{3} \approx 0.667, Q_{t} (B) = \frac{0}{1} = 0.$ Greedy picks the highest estimate → arm $A$ .

Recall Solution 2.2

$ϵ$ -greedy plays the best action with probability $1 - ϵ$ , and otherwise picks uniformly among all $∣ A ∣ = K$ actions (which can re-select the best one). (a) $P (best) = 1 - ϵ + \frac{ϵ}{∣ A ∣} = 1 - 0.2 + \frac{0.2}{4} = 0.8 + 0.05 = 0.85.$ (b) Each non-greedy action: $P = \frac{ϵ}{∣ A ∣} = \frac{0.2}{4} = 0.05.$ Sanity: $0.85 + 3 \times 0.05 = 1.0$ . ✓

Recall Solution 2.3

$ϵ_{100} = 0.5 \times 0.9 9^{100} = 0.5 \times 0.3660 \approx 0.1830.$ The agent starts exploring half the time and, by step 100, explores only ~18% of the time — exactly the "explore early, exploit later" schedule.

Level 3 — Analysis

Recall Solution 3.1

With $ln 100 = 4.6052$ : $UCB_{1} = 0.7 + 2 \frac{4.6052}{80} = 0.7 + 2 (0.2399) = 0.7 + 0.4798 \approx 1.180.$ $UCB_{2} = 0.6 + 2 \frac{4.6052}{10} = 0.6 + 2 (0.6786) = 0.6 + 1.357 \approx 1.957.$ $UCB_{3} = 0.5 + 2 \frac{4.6052}{10} = 0.5 + 1.357 \approx 1.857.$ Chosen: Action 2 (highest UCB $\approx 1.957$ ). Why: Actions 2 and 3 were tried only 10 times, so their exploration bonus ( $1.357$ ) is huge compared with Action 1's ( $0.48$ ). The bonus is the optimistic width of the confidence interval — under-sampled arms get the benefit of the doubt.

Edge case $N_{t} (a) = 0$ : the bonus $ln t / N_{t} (a)$ divides by $N_{t} (a)$ , so an untried arm would divide by zero. The standard convention is to treat an untried arm's UCB as $+ \infty$ — equivalently, UCB pulls every arm once first before the formula takes over. This guarantees no arm is ignored for lack of a single sample, and it removes the division-by-zero.

Reading the figure below. The chart stacks each arm's score into two coloured pieces: the cyan base is the estimate $Q (a)$ , the amber block on top is the exploration bonus $c ln t / N$ . Notice the amber blocks for Actions 2 and 3 are almost three times taller than Action 1's — that visual gap is exactly why Action 2's total (dashed line) overtakes Action 1 despite a lower cyan base. The amber annotation marks the winner.

Figure — Exploration vs exploitation tradeoff

Recall Solution 3.2

Recall from the glossary that $Regret (T) = \sum_{t = 1}^{T} Δ_{a_{t}}$ — the running sum of gaps. Here every wrong pull has gap $Δ = μ^{*} - μ = 0.8 - 0.6 = 0.2$ , so regret is just $Δ$ times the number of wrong pulls. The whole question reduces to: how many wrong pulls does each strategy make?

Pure exploit stuck on the wrong arm: it plays the $0.6$ arm all $T$ steps → wrong pulls $= T$ → $Regret = Δ \cdot T = 0.2 \times 1000 = 200$ . Grows proportional to $T$ → linear.
Pure explore (random forever): on average half the pulls hit the wrong arm → wrong pulls $\approx T /2$ → $Regret \approx Δ \cdot \frac{T}{2} = 0.2 \times 500 = 100$ . Still proportional to $T$ → linear.
Balanced (UCB/decaying $ϵ$ ): here the number of wrong pulls does not grow like $T$ — it grows like $ln T$ . Why $ln T$ ? Sketch: UCB stops preferring the wrong arm once its exploration bonus $c ln t / N$ drops below the gap $Δ$ (below that, the bonus can no longer lift the wrong arm's optimistic score above the true best arm). Setting bonus $= Δ$ and solving for $N$ : $c ln t / N = Δ \Rightarrow N \approx \frac{c ^{2} ln t}{Δ ^{2}}$ . With the standard constant $c^{2} = 8$ this gives the classic bound $N_{T} (a) \approx \frac{8 ln T}{Δ ^{2}}$ . Because $N_{T}$ counts wrong pulls, the regret is $Regret \approx N_{T} (a) \cdot Δ = \frac{8 l n T}{Δ ^{2}} \cdot Δ = \frac{8 l n T}{Δ} .$ Plugging $Δ = 0.2$ and $T = 1000$ (so $ln 1000 \approx 6.908$ ): $Regret \approx \frac{8}{0.2} ln 1000 = 40 \times 6.908 \approx 276.$ The magnitude here happens to sit between the two extremes, but the point is not the number — it is the shape: this term grows like $ln T$ , so as $T$ keeps rising it eventually falls far below the linear lines, and the per-step regret $\frac{276}{1000} \to 0$ . That flattening is $O (lo g T)$ .

Reading the figure below. Three curves share one axis: cumulative regret vs steps $T$ . The amber and cyan straight lines are the two extremes — both climb without bending, the signature of $O (T)$ . The white curve (balanced) shoots up early while it is still learning, then bends into the gentle shape of $lo g T$ . The bending is the whole point: after the agent is confident, extra steps add almost no regret.

Level 4 — Synthesis

Recall Solution 4.1

Posterior update: $Beta (1 + s, 1 + f) = Beta (1 + 7, 1 + 3) = Beta (8, 4)$ . Mean $= \frac{α}{α + β} = \frac{8}{8 + 4} = \frac{8}{12} = \frac{2}{3} \approx 0.667.$ With only 10 observations the distribution is still moderately wide, so sampled draws $\tilde{μ}$ scatter around $0.667$ . Occasionally a high draw is produced → the agent still explores. As more data arrive, $α + β$ grows, the Beta narrows, and exploration fades automatically — no manual $ϵ$ schedule needed.

Recall Solution 4.2

Both $ϵ$ -greedy and UCB rely on already observing some reward difference to guide choices. In Montezuma's Revenge the probability of stumbling onto reward by random action is $\approx 1 0^{- 20}$ , so $Q_{t} (a)$ stays $0$ for every action — neither method has a signal to act on. The fix is an intrinsic reward for novelty: $r_{t} = r_{t}^{ext} + β r_{t}^{intrinsic}$ , i.e. curiosity-driven exploration. UCB/ $ϵ$ -greedy work when rewards are dense enough to differentiate arms (e.g. bandits); curiosity is needed when they are not.

Level 5 — Mastery

Recall Solution 5.1

$UCB_{1} = 0.55 + \frac{3.912}{45} = 0.55 + 0.2949 \approx 0.845.$ $UCB_{2} = 0.55 + \frac{3.912}{5} = 0.55 + 0.8845 \approx 1.435.$ Arm 2 is selected. Principle: when values tie, UCB breaks the tie toward the less-explored option. Optimism-under-uncertainty says the arm you know least about deserves a look — its true mean might be far above the tie value.

Recall Solution 5.2

Per suboptimal pull, the gap $Δ = 0.9 - 0.7 = 0.2$ . Using $Regret (T) = \sum_{t} Δ_{a_{t}}$ with only the $60$ wrong pulls contributing: Total regret $= m \cdot Δ = 60 \times 0.2 = 12.$ Average regret per step $= \frac{12}{2000} = 0.006.$ The count of exploratory pulls ( $60$ ) does not scale with $T$ ; if it grows like $ln T$ the total regret stays $\propto ln T$ while the per-step regret $\to 0$ . Since $12 ≪ Δ T = 400$ (what pure-exploit-on-wrong-arm would cost) and the per-step loss shrinks toward $0$ , this is sublinear ( $O (lo g T)$ ) — the hallmark of a good exploration schedule.

Recall Quick self-check clozes

UCB's exploration bonus grows with ::: $ln t / N_{t} (a)$ — up with time, down with visits. Thompson sampling explores because its posterior is ::: wide when data is scarce. Balanced strategies achieve regret of order ::: $O (lo g T)$ (sublinear). The per-step regret of a good strategy tends to ::: $0$ as $T \to \infty$ .