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.

Write the ε-greedy policy formula and explain why the greedy action gets 1-ε+ε/|A|.

Write the UCB1 selection formula and explain each term. Why does √(2ln t/n_a) shrink with n_a?

Compare ε-greedy, UCB, and Thompson sampling: exploration logic, regret bounds, use cases.

What is regret? Why does UCB achieve O(ln T) regret on MABs?

Why should optimal exploration be allocated by information gain? Other exploration tricks in RL (optimistic init, count-based bonuses)?