Exploration Strategies & Model-Based RL
An RL agent can only learn from experience. But to collect useful experience it must sometimes try actions it has never taken before. This is the exploration–exploitation dilemma — arguably the central challenge unique to RL.
Exploration is the data stage — happening live
Here is RL's most instructive twist on the ML project loop. In supervised learning the data slot is settled before training; in RL the agent creates its own dataset by acting, so exploration is the data-collection stage running online. Explore too little and your data never covers the states that matter (the model can't learn what it never sees); explore too much and you waste expensive interaction. Model-based RL is a data-stage move too — it manufactures synthetic experience from a learned world model. Read this whole dilemma as "how do I get good training data?" asked in real time.
At the same time, interacting with the real world is expensive: every training step might cost time, money, or physical wear. Model-based RL addresses this by learning a world model and generating synthetic experience for free.
The exploration–exploitation dilemma
At every step an agent faces a choice:
- Exploit: take the action it currently believes is best (maximize short-term reward)
- Explore: try something new to gather information that might lead to better long-term rewards
Too much exploitation: the agent gets stuck in a local optimum, never discovering better strategies. Too much exploration: the agent wastes time on suboptimal actions and accumulates poor rewards.
The challenge is that the agent doesn't know in advance which arms/actions are good. It has to discover this through interaction.
ε-greedy: the baseline
The simplest strategy, already used throughout Q-Learning: with probability take a random action; with probability take the greedy (currently best-estimated) action.
Decaying ε: Start with (pure exploration) and anneal toward over the first steps. This front-loads exploration when the Q-values are least reliable.
Limitation: ε-greedy explores blindly — every action gets equal random probability regardless of how uncertain we are about it. Better strategies should explore more in states where uncertainty is high.
Optimistic initialization
A simple trick: initialize all Q-values to a large positive number . Since the true rewards are usually smaller, any action taken will update the Q-value downward — making untried actions look better than tried ones. This naturally drives exploration early in training without any explicit randomness.
Works well when: the Q-table is small and you can initialize every entry. Less practical for large/continuous state spaces where you can't enumerate all pairs.
Upper Confidence Bound (UCB)
UCB makes exploration principled: prefer actions where the Q-estimate is either high or highly uncertain.
- — current value estimate (exploitation term)
- — uncertainty bonus (exploration term): large when action has been tried rarely ( small) relative to the total steps
- — exploration constant controlling the balance
Intuition: the bonus shrinks as an action is tried more (), but grows slowly as total time passes (). Every action is eventually tried infinitely often, but better actions are tried more.
Regret bound: UCB achieves regret in the multi-armed bandit setting — optimal up to logarithmic factors. This is provably better than ε-greedy.
UCB in practice
UCB requires maintaining visit counts for every action. In the tabular case this is straightforward. For deep RL with large state spaces, UCB-style bonuses are approximated using count models or uncertainty estimates from the neural network (e.g., ensemble disagreement).
Thompson Sampling
A Bayesian approach: maintain a posterior distribution over Q-values, sample a Q-function from the posterior, then act greedily with respect to that sample.
For the bandit case:
- Model each arm's reward as , with prior
- After observing successes and failures: posterior is
- At each step: sample for each arm; pull
Why it works: arms with high uncertainty have wide posteriors — they're likely to be sampled as the best arm. As you observe more data, the posteriors narrow and the agent converges to the optimal arm.
Thompson Sampling is Bayes-optimal for many bandit problems and often outperforms UCB in practice despite being simpler to implement.
Watching the three of them diverge
Three strategies described separately are three sets of rules. Put them on the same five arms with the same random seeds and the difference stops being a claim about regret bounds and becomes a shape you can see.
Three ways to spend a pull
% of pulls per arm
predicted tax = ε × mean gap = 0.0214 per pull
% of pulls per arm
late slope is 0.46× the early slope — exploration is winding down
simulating 200 runs…
Five Bernoulli arms with success rates 0.25 / 0.40 / 0.50 / 0.58 / 0.70. Each curve is the mean cumulative regret — reward given up against always pulling the best arm — over 200 independent runs of 3000 pulls, all strategies sharing the same seeds. Every number is simulated in your browser, not stored.
The right quantity to plot is cumulative regret — reward given up against an oracle that always pulls the best arm. Average reward would show all three converging on a flat line just under and hide everything interesting; regret keeps the history, so a strategy that never stops exploring at a fixed rate leaves a permanently rising line behind it.
ε-greedy pays a tax you can compute in advance
Once ε-greedy has actually identified the best arm, its behaviour is fully determined: it pulls the best arm of the time and each other arm of the time, forever. So its regret per step settles at
for these arms. That is the dashed line in the plot, and it is not an approximation. Measured over the last quarter of the run:
| ε | measured late slope | final regret | |
|---|---|---|---|
| 0.05 | 0.0170 | 0.0107 | 86.1 |
| 0.10 | 0.0223 | 0.0214 | 87.7 |
| 0.20 | 0.0429 | 0.0428 | 143.9 |
| 0.30 | 0.0642 | 0.0642 | 203.1 |
At and the prediction is exact. Below that the measured slope runs above it, and the gap is the interesting part, because it means the premise has failed: at 3000 pulls with the agent still has not reliably found the best arm, so it is losing reward to misidentification on top of the exploration tax. Those are the two costs ε-greedy trades between, and the slider moves you along the tradeoff: regret is at (pure greedy locks onto the wrong arm in nearly half of all runs), bottoms out around near , and climbs back to at . Both ends are bad for opposite reasons.
Press decay ε as 1/t and the tax stops accruing: starting from , regret falls from to — better than any fixed ε, which is exactly the argument for annealing.
The constant matters more than the algorithm
UCB and Thompson both bend. Compare each curve's slope over its last quarter against its first quarter: ε-greedy at scores (a straight line), while UCB scores and Thompson . They are still exploring, but less and less.
The uncomfortable part is the c slider:
| final regret | |
|---|---|
| UCB, (tuned) | 26.3 |
| Thompson (nothing to tune) | 34.2 |
| UCB, | 87.6 |
| ε-greedy, | 87.7 |
| UCB, | 155.6 |
Tuned UCB is genuinely the best thing here. But UCB at a perfectly plausible ties with the ε-greedy baseline it is supposed to dominate, and the textbook is worse than that. Thompson Sampling gets within of the tuned optimum with no hyperparameter at all — that, and not the regret bound, is why it is the default in practice. A provable guarantee about the shape of a curve says nothing about the constant in front of it, and the constant is what you have to live with at .
Push c down to and watch UCB's ratio jump to : with too small a bonus it stops exploring early and degenerates into greedy, straight line and all.
Count-based exploration
Give the agent a bonus reward for visiting rarely-seen states:
where counts visits to . Novel transitions get large bonuses; frequently visited ones get tiny bonuses, steering the agent away from repetitive paths.
In practice: exact counting is impossible for large state spaces. Approximations include:
- Pseudo-counts via density models (count states by how much a density model's loss changes upon adding a new observation)
- Hash-based counts using locality-sensitive hashing to group similar states
Curiosity-driven exploration (intrinsic motivation)
Rather than counting, train a forward dynamics model that predicts the next state: . Use its prediction error as an intrinsic reward:
The agent is rewarded for visiting states the model cannot predict — i.e., novel states. As the model improves, the intrinsic reward for familiar states drops to zero. Two key implementations:
- ICM (Intrinsic Curiosity Module): uses a self-supervised feature space (features learned to predict actions from state pairs) to filter out irrelevant visual variation — the agent isn't distracted by moving leaves or TV noise
- RND (Random Network Distillation): compare a fixed random network's output to a trained predictor; high error = novel state
Model-based RL
Model-free RL (Q-learning, policy gradient) learns by direct interaction: every gradient update requires a real environment step. This is sample-inefficient: DQN needs ~50M frames to match human performance on Atari.
Model-based RL breaks this bottleneck: learn an environment model and reward model , then generate synthetic rollouts from the model without real interaction.
Dyna-Q
The simplest model-based algorithm (Sutton, 1991):
for each real step:
1. Take action a in real env; observe (s, a, r, s')
2. Update Q(s, a) from real transition
3. Update model: M ← experience (s, a, r, s')
4. Repeat k times:
sample random (s̃, ã) from visited states/actions
r̃, s̃' ← M(s̃, ã) # synthetic rollout from model
Update Q(s̃, ã) from synthetic transition
With planning steps per real step, Dyna-Q is 50× more sample-efficient than Q-learning on tabular problems because each real interaction generates 50 gradient updates.
World models and deep model-based RL
Modern deep model-based RL learns a latent space world model:
- RSSM (Recurrent State Space Model) in Dreamer — encodes observations into compact latent states, learns transitions in latent space, imagines entire trajectories of future states, optimizes policy in imagination
- MBPO (Model-Based Policy Optimization): generates short rollouts ( steps) from a learned dynamics model, adds them to the replay buffer, trains any model-free algorithm on the mix
When model-based beats model-free
| Aspect | Model-free | Model-based |
|---|---|---|
| Sample efficiency | Low (millions of steps) | High (hundreds to thousands of steps) |
| Final performance | Often higher (less model bias) | Can suffer from model errors compounding |
| Environment realism | Irrelevant (learns directly) | Critical: model errors compound over long horizons |
| Best for | Simulatable environments (games) | Real-world robotics, drug discovery, limited data |
Model errors compound
A 1% per-step model error becomes accuracy after 50 steps. Long imaginary rollouts amplify model errors into catastrophic mispredictions. This is why model-based RL often uses short rollouts (Dyna uses to steps, MBPO uses ) or combines model-generated data conservatively with real data.
Connecting exploration to model-based RL
Model-based and exploration methods are complementary:
- A world model enables planning under uncertainty (MCTS-style search with the model)
- Exploration bonuses can be defined in latent space (explore states the model is uncertain about: high ensemble disagreement in )
- AlphaGo/AlphaZero uses UCB-style exploration within MCTS rollouts through a learned world model
Exercise
UCB selects actions using Q(s,a) + c√(ln t / N(a)). What happens to the exploration bonus as N(a) increases?
Need a hint?
N(a) is how many times action a has been tried.
Exercise
In Thompson Sampling for a Bernoulli bandit, after observing 3 successes and 7 failures from arm A, what is the posterior for its success rate θ_A?
Need a hint?
Bayesian update: Beta prior + Binomial likelihood = Beta posterior.
Exercise
Dyna-Q performs k planning steps after each real environment step. What is the purpose of these planning steps?
Need a hint?
The agent has a learned model — what can it do with it?
Common mistakes
- Exploring blindly forever. A constant high wastes late-training steps on random actions; decay it, or use an uncertainty-aware method (UCB, Thompson) that stops exploring arms it has learned.
- Ignoring the exploration bonus scale. Count-based and curiosity bonuses (, ) that dwarf the real reward produce an agent that tours novelty and never solves the task.
- Trusting long model rollouts. Model errors compound exponentially with horizon; keep synthetic rollouts short (Dyna/MBPO style) and mix them with real data.
- Using curiosity on stochastic distractors. Raw prediction error rewards the agent for watching noise (the "noisy TV problem"); use ICM-style learned features or RND to filter it.
Key takeaways
- ε-greedy is simple but explores blindly; decaying ε front-loads exploration when Q-values are least reliable.
- UCB adds an uncertainty bonus that shrinks as an action is tried more; it achieves provably sub-linear regret.
- Thompson Sampling samples from the posterior and acts greedily; it is Bayes-optimal and often outperforms UCB in practice.
- Count-based and curiosity-driven methods extend exploration to large state spaces by approximating novelty.
- Model-based RL learns a world model to generate synthetic rollouts, dramatically improving sample efficiency; compounding model errors mean short rollouts are preferred.
- Dyna-Q is the archetypal model-based algorithm: one real step followed by planning steps from the model.
Related concepts
- Q-Learning: the model-free baseline that Dyna-Q accelerates with planning
- Markov Decision Processes: the model-based vs. model-free distinction in its native setting
- Bayesian Inference: the posterior-sampling logic behind Thompson Sampling