Exploration versus exploitation: epsilon-greedy and UCB

WHAT THIS TESTS This probes whether you understand the central dilemma of online learning and can compare a naive and a principled exploration strategy with their trade-offs.

A GOOD ANSWER COVERS The exploration-exploitation trade-off is the tension between exploiting the action that currently looks best to maximize reward now, and exploring less-tried actions to gather information that may reveal a better choice later. A purely greedy agent risks committing to an action that only looked best due to early noise, never discovering a superior one. Epsilon-greedy handles this by choosing a random action with probability epsilon and the greedy action otherwise. It is trivial to implement but its exploration is undirected, wasting trials on clearly bad actions, and a fixed epsilon keeps exploring even after estimates converge, so epsilon is typically decayed over time. Upper Confidence Bound selects the action that maximizes its estimated value plus an exploration bonus proportional to uncertainty, which is large for rarely tried actions and shrinks with more samples. UCB explores in a directed, optimistic way and has strong theoretical regret guarantees, but it assumes stationary rewards and needs the bonus tuned.

COMMON WRONG ANSWERS Claiming pure exploitation is optimal. Keeping epsilon fixed indefinitely. Describing UCB as random exploration; it is deliberate and uncertainty-driven. Confusing UCB with Thompson sampling. Forgetting that nonstationary environments need ongoing exploration.

LIKELY FOLLOW-UPS How does Thompson sampling differ from both. Why decay epsilon, and on what schedule. What is regret and how do these methods compare on it.

ONE CONCRETE EXAMPLE In a three-armed bandit where arm payoffs are unknown, an epsilon-greedy agent with epsilon 0.1 pulls the current best arm ninety percent of the time and a random arm ten percent, eventually finding the best but wasting some pulls on the worst arm. A UCB agent instead favors arms it has pulled few times because their confidence bonus is high, so it quickly rules out poor arms and concentrates on the genuinely best one with less wasted exploration.