Exploration-Exploitation

The exploration-exploitation dilemma is the trade-off an agent faces between trying unknown actions to gather information and exploiting the currently best action for reward — the two cannot be maximized simultaneously, and optimal exploration should be allocated by information gain. The simplest strategy is $\varepsilon$-greedy: with probability $1-\varepsilon$ pick the greedy action and with probability $\varepsilon$ explore uniformly, so the greedy action is chosen with $\pi(a|s) = 1 - \varepsilon + \frac{\varepsilon}{|A|}$ and every other action with $\frac{\varepsilon}{|A|}$; $\varepsilon$ is annealed (e.g. from $1.0$ to $0.01$), guaranteeing infinite exploration of every action so algorithms like Q-learning can converge. A better optimistic strategy is UCB1: $a_t = \arg\max_a \left[ \hat{\mu}_a + \sqrt{\frac{2\ln t}{n_a}} \right]$, where $\hat{\mu}_a$ is the empirical mean reward of action $a$, $n_a$ its visit count, and $t$ the total steps — the confidence bound shrinks as $n_a$ grows, balancing exploration and exploitation through "optimism in the face of uncertainty", achieving regret $R_T = \sum_{t=1}^T (\mu^* - \mu_{a_t})$ of $O(\ln T)$ on multi-armed bandits.

all online learning — multi-armed bandits, A/B and online decisions in recommendation/advertising, RL training (ε annealing, optimistic initialization), and RLHF sampling (needs diverse data); interviews often compare ε-greedy vs UCB vs Thompson sampling.

pure exploitation gets stuck in local optima (untried actions are underestimated) while pure exploration wastes reward; $\varepsilon$-greedy is simple but wastes linearly (always explores with a fixed random probability), whereas UCB/Thompson sampling weight exploration by uncertainty, cutting regret to logarithmic — exploration is paying for future information, so actions with high information gain deserve exploration first.

Test Your Knowledge: Practice Questions for "Exploration-Exploitation"

Single choice pitfall questions with instant feedback and mistake tracking.