Exploration versus Exploitation

A learner that always picks what has worked best so far may never discover something better. One that keeps trying random options wastes time on bad ones. This tension, exploration versus exploitation, is clearest in the multi-armed bandit: several slot machines, each with an unknown payout, and a limited number of pulls.

Strategy Pulls per second

Three strategies

Greedy always picks the arm with the best average so far. ε-greedy does the same, but picks a random arm with probability $\varepsilon$. UCB adds a bonus for arms that have been tried less, so it is optimistic about what it does not know:

$$a_t = \arg\max_a\ \Big(\hat\mu_a + c\sqrt{\frac{\ln t}{n_a}}\Big),\ c = 0.5 \qquad \text{regret}(T) = \sum_{t=1}^{T}\big(\mu^* - \mu_{a_t}\big)$$

Regret measures how much was lost compared with always pulling the best arm.

What to notice

Greedy often locks onto a mediocre arm after a lucky early win, and its regret grows in a straight line forever. ε-greedy finds the best arm but keeps wasting 10 percent of pulls, so its regret also keeps growing, more slowly. UCB's regret flattens out, since it explores less as it grows sure, growing only like $\ln t$. Robots face the same trade-off when trying grasps, choosing where to explore a map, or tuning their own controllers.