Question bank — Exploration vs exploitation tradeoff

True only if the estimates are correct — but early on they never are, so exploitation locks onto a wrong "best" arm and regret grows linearly.

False — regret is defined against ${\mu }^{\ast }$, the mean of the best arm; expected regret is $\ge 0$, though a single lucky run of samples can look favourable, it does not lower the expectation.

False — a constant $ϵ$ keeps taking random (often bad) actions at a fixed rate, so regret stays $O(ϵT)$, i.e. linear. You need $ϵ$ to decay for sublinear regret.

False — its exploration is implicit: wide posteriors occasionally sample a high value, so under-sampled arms get chosen without any hand-added bonus.

True — UCB always picks the arm with the highest $Q_t(a)+c\sqrt{\ln t/N_t(a)}$, so with identical state it makes the identical choice; the other two involve a coin flip or a sample.

False — it is $1-ϵ+\frac{ϵ}{|A|}$, because the random branch can also land on the greedy action by chance.

Partly — regret against ${\mu }^{\ast }$ can be zero either way, but the agent still spends samples discovering they are equal, so there is still an information cost early on.

False — with a perfect model there is no uncertainty to resolve, so pure exploitation is optimal; the tradeoff exists only because reward distributions are unknown.

Wrong — both extremes give linear regret. Pure exploitation commits to a possibly wrong arm forever, so it loses ${\mu }^{\ast }-{\mu }_a$ every step.

The bonus grows in $\ln t$ but the arm's own $N_t(a)$ also grows roughly linearly for played arms, so the bonus of the chosen arms shrinks; only neglected arms accumulate a rising bonus, which is exactly the self-correcting behaviour we want.

The tail $\sum 1/t$ diverges, so every action is still tried infinitely often — exploration never truly stops, it just becomes rare enough that exploitation dominates.

No — that would be pure exploitation. Thompson Sampling picks the arm with the highest posterior sample ${\tilde{\mu }}_a$; the sampling step is what injects exploration.

It is intentional. During the random branch every action, greedy included, is equally likely, so the greedy action's total probability is $1-ϵ+ϵ/|A|$.

More random actions do not help when the reward requires a long precise sequence — random walks reach it with probability $\approx 10^{-20}$. You need directed exploration such as 5.3.05-Curiosity-Driven-Exploration.

With $c=0$ the whole bonus vanishes, leaving pure greedy selection on $Q_t(a)$ — no exploration at all regardless of $t$.

Because you can never be certain an arm is optimal from finite samples; you must occasionally re-check under-sampled arms, and the minimal necessary re-checking scales like $\ln T$.

Averaging $N$ samples reduces variance by $N$, and the standard error is the square root of variance, giving $1/\sqrt{N}$ — this is exactly the ​ inside UCB's bonus.

In supervised learning the dataset is fixed and given; an RL agent must generate its own data through actions, so what it learns depends on what it chooses to try — see 5.2.03-Multi-Armed-Bandits.

Optimistically over-valuing an arm means we try it; if it is genuinely good we gain, and if it is bad its estimate quickly drops and we stop — either way uncertainty is resolved cheaply.

Because behaviour depends on the exploration policy, not just the values — one may be greedy, another $ϵ$-greedy, another UCB, giving different action choices from identical estimates.

Excess exploration keeps chasing noisy estimates instead of committing, much as 4.5.07-Overfitting-and-Regularization warns against fitting noise; both trade a controllable knob to balance signal against variance.

The bonus $\sqrt{\ln t/0}$ is infinite, so UCB forces every untried arm to be selected first — this is a deliberate initialization rule, not a math error.

The $\ln t$ factor is zero only at the very first step; conventionally each arm is played once first anyway, and by $t\ge 2$ the bonus is positive again, so exploration resumes immediately.

Beta$(1,1)$ is uniform on $[0,1]$, so its samples are spread across the whole range — maximally uncertain, so the arm is very likely to sometimes sample high and get explored.

No strategy can lower expected regret below zero because every arm is optimal; the strategies differ only in variance of outcomes, not in expected regret.

No — geometric decay makes $\sum {ϵ}_t$ converge, so total exploration is finite and some arm may be dropped forever, risking a permanent wrong commitment; use ${ϵ}_0/t$ if infinite exploration is required.

Exactly one — a single pull reveals its true value with certainty, so the standard-error argument collapses and the only remaining tradeoff is trying each arm once.