EasyDeepLearn
Reinforcement Learning · section 4 of 12

Exploration strategies

11 interview questions on exploration strategies, each answered in full. Free to read, no account needed.

What is the exploration-exploitation tradeoff?

easy
  • Exploitation uses the best-known action to maximize immediate reward; exploration tries new actions to discover potentially better ones.
  • Too much exploitation = premature convergence; too much exploration = wasted samples.
  • Strategies: epsilon-greedy, softmax/Boltzmann, entropy bonuses, UCB, Thompson sampling, curiosity/intrinsic rewards.
#explorationPermalink & quiz →

CEM — Cross-Entropy Method for planning.

medium
  • Sample-based optimization: (1) sample K action sequences from Gaussian, (2) evaluate returns, (3) select elite (top 10%), (4) refit Gaussian to elites, (5) repeat.
  • Simple, embarrassingly parallel, no gradients.
  • Used in model-predictive control (PETS, model-based RL) and QT-Opt (Google robotics).
  • Slower than gradient-based but more robust to non-differentiable models / rewards.
#planning#explorationPermalink & quiz →

ε-greedy — how do you schedule ε?

easy
  • Start ε high (0.5-1.0) for broad exploration, anneal linearly or exponentially to a small floor (0.01-0.1).
  • Atari DQN: linear 1.0 → 0.1 over first 1M steps, then 0.1 → 0.01 over 24M more.
  • Rule: schedule matches expected training length.
  • Alternative decays: 1/n schedule (asymptotic optimality for tabular bandits), exponential.
  • Modern deep RL often uses noisy nets or entropy bonus instead of ε-greedy.
#explorationPermalink & quiz →

How does posterior sampling drive exploration in deep RL?

hard
  • Maintain posterior over Q or model parameters.
  • To choose action: sample θ ~ p(θ  ∣  data)p({\theta}\; \mid \;\mathrm{data}), act greedily w.r.t. sampled θ.
  • Automatic exploration/exploitation via posterior uncertainty.
  • Beta-Bernoulli for binary bandit → closed-form.
  • Deep RL: Bootstrapped DQN samples one of K Q-heads per episode (approximate posterior); Bayesian NN with Gaussian variational posteriors; noisy nets.
  • Regret-optimal in many settings.
#exploration#bayesianPermalink & quiz →

Why is Montezuma's Revenge such a famous benchmark?

medium
  • Extreme sparse reward: dozens of steps needed before any positive reward.
  • DQN + ε-greedy scores 0.
  • Requires deep, temporally-extended exploration — random policies never find rewards.
  • Solved sequentially by intrinsic-motivation methods: pseudo-counts → RND → Go-Explore → Agent57 → NGU.
  • Became the canonical stress-test for exploration algorithms, similar to CIFAR-10 for image classification.
#explorationPermalink & quiz →

Parameter noise for exploration — how is it different?

medium
  • Plappert et al. 2017: add noise directly to policy parameters (θ + σε) instead of action noise.
  • Produces consistent behavior over an episode (θ is fixed until reset) → temporally-correlated exploration.
  • Contrast: action noise (ε-greedy, OU noise) is uncorrelated.
  • Adaptive σ tuned to match target action-level variability.
  • Foundation of noisy nets.
  • Empirically better on locomotion.
#explorationPermalink & quiz →

The 'noisy TV problem' in curiosity-driven exploration.

hard
  • If agent gets intrinsic reward for high prediction error, it can find sources of pure noise (TV showing static, random-generated stimuli) and stay 'exploring' those forever — infinite curiosity but no learning.
  • Fixes: (1) inverse-model features (ICM) — only rewards prediction errors about controllable aspects.
  • (2) RND — errors on RANDOM target eventually shrink, unlike true entropy.
  • Classic argument for control-relevant curiosity.
#explorationPermalink & quiz →

Emergent tool use in RL — canonical example.

medium
  • Baker et al. 2019 (OpenAI): hide-and-seek multi-agent RL discovered emergent tool use — hiders build ramps, seekers box surf, hiders lock ramps, seekers exploit physics glitches.
  • Six curriculum stages emerged without engineering.
  • Demonstrated that open-ended MARL environments produce increasingly sophisticated strategies.
  • Foundation of open-ended learning + emergent capabilities.
#multi-agent#explorationPermalink & quiz →

You want to optimize which of five banners to show. Bandit or full RL?

medium
  • A contextual bandit, because showing a banner does not meaningfully change the state the next user arrives in, so there is nothing to credit across time.
  • That single simplification removes the hardest part of reinforcement learning and gives you a problem with clean theory, fast convergence, and well-understood algorithms such as Thompson sampling or upper confidence bounds.
  • It also fails gracefully, since the worst case is exploring a mediocre banner slightly too often.
  • Full reinforcement learning becomes appropriate if the decision has genuine downstream consequences on the same user, such as sequencing a multi-step onboarding flow, where an early action changes what later actions are available or effective.
#applications#explorationPermalink & quiz →

How do you explore safely when the environment is real paying users?

hard
  • Bound the damage rather than trusting the algorithm.
  • Restrict exploration to a small traffic slice, so a bad action affects a known fraction of users, and exclude segments where the cost of a mistake is high.
  • Constrain the action set to options you have vetted, which turns unbounded exploration into a choice among acceptable alternatives.
  • Use off-policy evaluation on logged data to estimate a candidate policy's value before it ever serves traffic, remembering that this requires logged action probabilities, so instrument them from day one.
  • Monitor guardrail metrics with automatic rollback, and prefer optimistic or posterior-sampling exploration over epsilon-greedy, since random actions spend your budget on options already known to be bad.
#exploration#safety#applicationsPermalink & quiz →

The reward arrives only at the end of a 500-step episode. What do you do?

hard
  • Shorten the effective credit assignment problem.
  • Reward shaping is the direct approach, adding intermediate signal, and if you shape it as a potential-based difference the optimal policy provably does not change, which is the only shaping I would introduce without careful evaluation.
  • Curriculum learning starts with short easy episodes and lengthens them, so the agent learns the final part of the task before the whole.
  • Hindsight relabelling turns a failed trajectory into a successful one for whatever goal it actually reached, which manufactures dense signal from the same data in goal-conditioned settings.
  • Better value estimation helps too, via generalized advantage estimation to trade bias against variance.
  • And demonstrations, even a handful, bypass the search entirely for the early phase.
#reward-design#explorationPermalink & quiz →

Practise Reinforcement Learning

All 12 sectionsFlashcardsQuiz