This is the most human lesson in all of ML. Try the new restaurant or go back to your favorite? Study a new topic or deepen what you know? You face this dilemma every day — and so does every RL agent at every step. The math behind the optimal answer (UCB, Thompson sampling) is older than RL itself, and now powers everything from Netflix recommendations to A/B testing to drug-trial design.
Learning Objectives
After this lesson, you will be able to:
Understand the core tension: should I try something new (explore) or stick with what works (exploit)?
Learn the multi-armed bandit problem and three strategies for solving it: epsilon-greedy (probabilistic random exploration), UCB (uncertainty-directed exploration), and Thompson Sampling (Bayesian posterior sampling)
Know how regret measures the cost of suboptimal exploration and why sublinear regret is the gold standard for bandit algorithms
Know which exploration strategy to use in different situations -- and understand why epsilon-greedy's blind random exploration fails compared to UCB and Thompson Sampling's principled approaches
Do you go back to the reliable Italian place (exploit what you know) or try somewhere new (explore the unknown)?
If you always exploit, you guarantee a good meal but never discover the amazing Thai place around the corner. If you always explore, you waste most evenings on mediocre food and never enjoy your known favorite.
The optimal strategy is somewhere in between -- and it changes over time. On night one, explore aggressively (you have the whole week ahead). On night six, exploit your best find (little time left for new information to pay off).
This is the exploration-exploitation dilemma. Every RL agent faces it at every time step, and getting the balance right is one of the deepest challenges in the field.
The exploration-exploitation tradeoff is not just an RL problem -- it appears everywhere in life and engineering. Should a company invest in R&D (exploration) or optimize its current product (exploitation)? Should a clinical trial test a promising new drug (exploration) or stick with the current best treatment (exploitation)? Should you read a new book (exploration) or reread your favorite (exploitation)?
In RL, the tradeoff is stark: the agent must take actions to learn about the environment, but every exploratory action might mean missing out on reward from the best known action. Too little exploration means the agent converges prematurely to a suboptimal policy. Too much exploration wastes time on bad actions the agent already knows are bad.
The simplest setting to study exploration-exploitation is the multi-armed bandit problem. Imagine a row of slot machines ("one-armed bandits") in a casino. Each machine pays out with a different (unknown) probability. You have a fixed number of pulls. Which machines do you play to maximize total payout?
Goal: maximize t=1∑Trtwhere rt∼Distributionk for chosen arm k
This is a simplified RL problem with no state transitions -- just repeated action selection. But it captures the core exploration-exploitation tension perfectly.
Try it! Before reading about the algorithms, try this thought experiment: you have 5 slot machines and 100 pulls. Machine A paid out $3 on your first pull. You have not tried the others. What do you do? Pull A again (exploit) or try B (explore)? What if you had 1000 pulls instead of 100? Notice how more time left makes exploration more attractive.
Try it: Pull the LeversInteractive
Experiment with different exploration strategies on a multi-armed bandit. Switch between epsilon-greedy, UCB, and Thompson sampling to see how each balances exploring unknown arms with exploiting the best-known arm. Watch the regret accumulate -- smarter strategies waste less reward on bad arms.
How do we measure how well an agent balances exploration and exploitation? Regret -- the difference between the reward the agent actually received and the reward it would have received if it always pulled the best arm:
Regret(T)=T⋅μ∗−t=1∑TμAt
A perfect agent (which somehow knows the best arm from the start) has zero regret. A pure explorer has linear regret (it wastes half its pulls on bad arms). Good exploration strategies achieve sublinear regret -- the regret grows, but slower and slower as the agent learns.
The simplest exploration strategy: with probability epsilon, take a random action (explore). With probability 1 - epsilon, take the action with the highest estimated value (exploit).
At={argmaxaQt(a)random actionwith probability 1−ϵwith probability ϵ
Pros
Dead simple to implement
Guaranteed to explore every action infinitely often (so it will find the best one eventually)
Works surprisingly well in practice
Cons
Explores uniformly at random -- does not prioritize promising actions
Wastes exploration on actions already known to be bad
The fixed epsilon means it keeps exploring at the same rate even after it has found the best action
A common improvement: start with a high epsilon (lots of exploration) and gradually decrease it (shift toward exploitation as you learn):
ϵt=max(ϵmin,ϵ0⋅αt)
What Do You Think?
With epsilon-greedy (epsilon=0.1) and 10 arms, what fraction of time does the best arm get pulled?
The best arm gets pulled 90% of the time (when greedy) plus 1% of the time (when exploring, 10% * 1/10 arms), totaling 91%. The remaining 9% is wasted on the other 9 suboptimal arms. This is epsilon-greedy's fundamental inefficiency -- it explores bad arms just as much as promising ones.
UCB takes a smarter approach: explore actions you are uncertain about, not random ones. Each action gets a confidence bonus that is large when you have not tried it much and shrinks as you gather more data:
At=argamax[Qt(a)+cNt(a)lnt]
The intuition: "Be optimistic about uncertainty." If you have only tried an arm once and got a moderate reward, maybe you were unlucky -- the arm could actually be great. UCB gives it the benefit of the doubt and tries it again. After many pulls, the confidence interval narrows, and the bonus shrinks -- the agent stops exploring arms whose values are well-estimated.
Pros
Smarter exploration: prioritizes uncertain actions over well-known bad ones
Thompson sampling is a Bayesian approach that maintains a probability distribution over each arm's true reward. Instead of computing confidence bounds, it samples from each distribution and pulls the arm with the highest sample:
θa∼Beta(αa,βa)for each arm aAt=argamaxθa
Pros
Often the best empirical performance of all bandit algorithms
Naturally balances exploration and exploitation through posterior sampling
Handles non-stationary environments well (distributions can be "decayed")
Elegant Bayesian interpretation
Cons
Requires choosing a prior distribution family
Can be computationally expensive for complex reward models
Harder to analyze theoretically than UCB (though results exist)
Figure
A balance scale with "Explore" on one side (a question mark over unknown restaurants) and "Exploit" on the other (a gold star over a known favorite) -- tilting toward explore early in the process and toward exploit later as knowledge accumulates.
Exploration vs exploitation: try new or stick with known?
Which exploration strategy will accumulate the MOST regret over 10,000 pulls on a 10-arm bandit?
Pure greedy (epsilon=0) often has the highest regret because it locks onto the first arm that looks good and never explores alternatives. If the first few pulls of the truly best arm happen to give below-average rewards, pure greedy might permanently ignore it. Among the exploration strategies, epsilon-greedy with no decay typically has the highest regret because it keeps exploring uniformly at a fixed rate even after the solution is clear. UCB and Thompson sampling have comparable (and much lower) regret, with Thompson sampling often winning empirically.
In bandits, exploration means trying different arms. In full RL with states, exploration is much harder because the agent must visit new states as well as try new actions. Some important states might only be reachable through a long sequence of specific actions.
Sparse rewards: If the agent only gets reward at the end of a long episode, it may never stumble upon the rewarding states through random exploration. Imagine a maze where the reward is only at the exit -- random actions will almost never reach it.
Deceptive rewards: Local reward traps can lure the agent away from the globally optimal solution. The agent finds a small reward nearby and never explores far enough to find the big reward.
High-dimensional state spaces: In Atari, there are billions of possible screen configurations. The agent cannot exhaustively explore them all. It must generalize.
Intrinsic motivation / Curiosity-driven exploration: Give the agent a bonus reward for visiting novel states. "I have never seen this before -- it must be interesting." The agent is rewarded for surprise itself.
Count-based exploration: Track how often each state has been visited and give a bonus inversely proportional to the visit count. Rarely-visited states get higher bonus.
Random Network Distillation (RND): Use the prediction error of a random neural network as a novelty signal. States the agent has seen many times are easy to predict (low error = low bonus). New states are hard to predict (high error = high bonus).
Exploration-exploitation is the fundamental RL tradeoff. Should you exploit the best-known option for guaranteed reward, or explore unknown options that might be even better?
Epsilon-greedy is the simplest exploration strategy. With probability epsilon, take a random action; otherwise, take the greedy action; decreasing epsilon over time balances early exploration with later exploitation
UCB selects actions based on uncertainty. Upper Confidence Bound favors actions with high estimated value AND high uncertainty, automatically balancing exploration and exploitation without a random exploration rate
Thompson sampling uses Bayesian probability. By sampling from posterior distributions over reward estimates, it naturally explores uncertain options proportionally to their probability of being optimal
Interactive Lab
Pull on a multi-armed bandit with epsilon-greedy, UCB, and Thompson sampling side by side — watch regret curves diverge and feel the difference between random exploration and uncertainty-driven exploration.
In epsilon-greedy with epsilon=0.2, what percentage of the time does the agent exploit the best known action?
You now understand the exploration-exploitation tradeoff and the key strategies for balancing them. Next up: Q-learning -- where the agent builds a table of how valuable each state-action pair is and uses it to find the optimal policy.