A Survey of Exploration Methods in Reinforcement Learning

1. Introduction

• Limited state-space visits leave an agent with limited knowledge and can lead to suboptimal decisions, while seeking new information can forgo immediate reinforcement.The exploration–exploitation trade-off is influenced by environment dynamics, state/action-space properties, and the number of allowed training interactions.Source: §1 · p. 2
• The survey reviews three decades of exploration methods, from pure randomization to methods with theoretical guarantees or empirical performance in large problems.Source: §1 · p. 2
• The survey proposes a more detailed categorization to clarify the goals and information used by current exploration methods, while allowing methods to appear in multiple categories when they overlap.Source: §1 · p. 2
• The survey focuses on sequential decision making rather than exploration methods designed specifically for bandits, and selects representative methods where the literature is extensive.It also omits mathematical details and theoretical results to keep the overview concise and accessible.Source: §1 · pp. 2–3

2. Notation and Background

• At each discrete time step, the agent selects an action in its current state, receives a reward, and transitions to a next state; tasks may be episodic or continuing.The survey uses capital and calligraphic letters for random variables and sets, respectively, unless stated otherwise.Source: §2 · p. 3

2.1 Markov Decision Processes

• An MDP models states, actions, transition probabilities, and rewards, with the next-state distribution depending only on the current state-action pair.The reward function maps a state-action pair to its expected immediate reward.Source: §2.1 · pp. 3–4
• A trajectory is a sequence of information drawn from the history of observations, actions, and rewards over a specified horizon.Source: §2.1 · p. 4

2.2 Reinforcement Learning Setting

• The RL objective is to find a policy that maximizes expected discounted cumulative future reward, with the return definition depending on whether the task has an infinite or finite horizon.A policy may be deterministic or stochastic; state-value and action-value functions describe expected returns under a policy.Source: §2.2 · p. 4

3. Categorization of Exploratory Techniques

• Thrun (1992) distinguishes undirected methods, which rely on randomness, from directed methods, which use exploration-specific knowledge to guide actions.The survey also notes that earlier categorizations did not provide a general foundation for classifying exploration techniques.Source: §3 · p. 6
• The proposed taxonomy divides methods into reward-free and reward-based exploration, with each group further divided by whether exploratory decisions rely on memory of the observed space.Some methods do not fit a single category and are included in multiple categories.Source: §3 · pp. 6, 8, Figure 1 · p. 7
• Reward-free methods choose actions without using rewards or value functions, either blindly or with intrinsic information such as intrinsic rewards.The survey notes that this can be useful when reward signals are sparse and not immediately available.Source: §3 · pp. 6–7
• Randomized action selection uses estimated values or rewards to assign action probabilities, or searches policy space for stochastic policies that balance exploration and exploitation.Source: §3 · p. 7
• Optimism/bonus-based methods prefer uncertain actions and add bonuses to extrinsic rewards to direct search through state-action spaces.Unlike intrinsically motivated methods, these techniques use extrinsic reward to motivate exploration.Source: §3 · pp. 7–8
• Deliberate exploration includes methods that seek to solve the exploration–exploitation trade-off optimally, including Bayesian model-based and meta-learning approaches.Source: §3 · p. 8
• Probability matching samples an environment or value function from a posterior, solves for that sample, and selects actions according to their probability of being optimal.Source: §3 · p. 8

4.1 Blind Exploration

• Random-walk and ϵ-greedy methods explore blindly, but random walks scale poorly and ϵ-greedy can remain suboptimal; ϵz-greedy instead repeats exploratory actions for extended durations.ϵ-greedy needs only one hyperparameter and no cached data, but its random exploratory actions may cause indecisiveness or local optima; ϵz-greedy was evaluated in tabular and deep RL settings with discrete actions.Source: §4.1 · pp. 9–10

4.2 Intrinsically-Motivated Exploration

• DIDO uses uncertainty reduction to select informative experiences, while competence maps and RDIA guide exploration through model accuracy or transition information gain.DIDO produced sensible experiences and good domain representations; competence maps outperformed random walk and purely greedy approaches in continuous robot navigation, and RDIA surpassed simple random search.Source: §4.2 · pp. 11–13
• Schmidhuber (1991a) used adaptive curiosity to seek hard-but-learnable states, reducing learning time by an order of magnitude versus random search in discrete toy environments.The approach models predictor reliability and maximizes expected cumulative changes in prediction reliability, enabling exploration in uncertain, non-deterministic environments.Source: §4.2 · p. 12
• Other intrinsic signals include Bayesian information gain, state-visitation entropy, and PolyRL’s trajectory spread, which encourages coverage in continuous state-action spaces.PolyRL was evaluated in continuous navigation and sparse-reward MuJoCo tasks, with improved results over several other exploration techniques.Source: §4.2 · pp. 13, 15, 16
• Pathak et al. (2017) define curiosity through action-consequence prediction error and use influential features to avoid unpredictable or unlearnable state components.Their Intrinsic Curiosity Module improved exploration with sparse or absent environmental rewards and transferred learned skills to new scenarios.Source: §4.2 · pp. 13, 15
• Forestier et al. (2017) proposed IMGEP, which samples self-generated goals for learning progress and demonstrated increasingly complex skill discovery on a humanoid robot.The agent updates its goal-sampling strategy and meta-policy using outcomes and intrinsic rewards from goal-directed exploration.Source: §4.2 · pp. 16–17
• GEP-PG combines goal exploration processes with DDPG, surpassing DDPG variants in Half-Cheetah performance, variability, and sample efficiency.The method was tested in Continuous Mountain Car and Half-Cheetah tasks.Source: §4.2 · p. 17
• Eigenoptions use proto-value functions to guide state-space exploration, while covering options target less-explored regions and reduced learning time in discrete sparse-reward domains.Deep covering options extend coverage to large or continuous spaces and were demonstrated in Pinball, MuJoCo, and Atari tasks.Source: §4.2 · pp. 17–18
• The method encourages agents to try new policies and explore unvisited states without extrinsic rewards, improving performance in grid worlds, Atari 2600, and MuJoCo.It aims to help agents avoid local optima caused by deceptive rewards and learn tasks with sparse rewards or large state spaces.Source: §4.2 · p. 18

5.1 Value-Based Methods

• Max-Boltzmann reduces exploration relative to exploitation and avoids over-exploration, but requires tuning both T and ϵ.It selects the maximum-Q action with probability 1−ϵ and otherwise samples from a Boltzmann distribution; Softmax’s temperature controls the trade-off between greedy and random action selection.Source: §5.1 · pp. 19–20
• VDBE-Softmax generally outperforms ϵ-greedy, Softmax, and VDBE in deterministic and stochastic reward environments.It combines state-dependent VDBE exploration probabilities with Boltzmann selection for exploratory actions.Source: §5.1 · p. 21

5.2 Policy-Search Based Methods

• Policy-search methods typically learn stochastic policies whose randomness drives exploration, while this survey focuses on single-task policies with their own representation.Policy-search approaches may perturb actions or policy parameters, and the survey organizes them by perturbation type and coherence.Source: §5.2 · pp. 21–22

5.2.1 Perturbed space and coherence

• High-coherence perturbations can evaluate a policy’s long-term effects, while low-coherence perturbations try more strategies per episode but may cause inefficient random walks.Intermediate coherence can compromise between these extremes; parameter-space exploration often uses episode-based perturbations, whereas action-space perturbations are commonly independent across time steps.Source: §5.2.1 · p. 24

5.2.2 Action-space perturbing strategies

• On continuous robot-control tasks, autocorrelated action noise achieved equivalent asymptotic performance, sometimes more slowly, while reducing trajectory jerkiness and joint stress.Other coherent action-space approaches include hierarchical subgoals and periodically switched policies; experiments found both benefited from temporal coherence, with meaningful goals potentially adding benefit.Source: §5.2.2 · pp. 25–26
• Learned behavior-policy variance, and especially a learned mean, improved learning speed and average rewards over exploration centered on the target policy.The method separately trains the off-policy target and behavior policies, attributing gains to more diverse samples and more global exploration.Source: §5.2.2 · pp. 26–27

5.2.3 Parameter-space perturbing strategies

• Parameter perturbations can preserve policy structure and produce episode-coherent exploration; Sehnke et al. (2010) outperformed conventional action perturbations on simulated dynamical-system tasks.Finite-difference methods estimate policy gradients from rollouts with fixed episode perturbations, but stochasticity can make estimates high-variance; common random numbers can address this in simulation.Source: §5.2.3 · p. 27
• Episode-based exploration outperformed per-time-step and per-basis exploration on a simulated reaching task, while state-dependent exploration matches parameter-based exploration for linear policies.Per-basis perturbations are applied to the most active basis function and were observed to improve learning speed; state-dependent exploration generates action-space perturbations from a random vector and current state.Source: §5.2.3 · p. 28
• Salimans et al. (2017) found episode-level policy gradients competitive with A3C and an order of magnitude faster, while Conti et al. (2018) combined evolutionary strategies with novelty and diversity objectives.Salimans et al. also compared favorably with TRPO on simulated robotic tasks; Conti et al. outperformed regular evolutionary strategies and performed competitively with Fortunato et al. (2018), though their methods received more frames and ran faster through parallelization.Source: §5.2.3 · p. 28
• Autocorrelated parameter noise yielded intermediate trade-offs between independent and episode-based perturbations, enabling faster learning and control of state-space coverage and motor strain.Van Hoof et al. (2017) evaluated it on simulated and real continuous-control tasks and used joint sequence log-probabilities, requiring restricted policy classes such as linear policies.Source: §5.2.3 · pp. 28–29
• NoisyNet-A3C outperformed baseline A3C on a majority of 57 Atari games, while Plappert et al. (2018) variants of DDPG and TRPO beat action-noise baselines on several simulated robot environments.These methods apply episode-level parameter perturbations to deep networks; Plappert et al. used scheduled noise for DDPG and combined parameter perturbations with stochastic action selection for on-policy TRPO.Source: §5.2.3 · p. 29

5.2.4 The distribution of perturbations

• Policy-gradient adaptation can reduce uncertainty and cause premature convergence, motivating entropy or relative-entropy regularization to preserve exploration.Relative entropy policy search bounds divergence in the joint state-action distribution, while a combined joint- and expected-KL approach can be faithfully implemented in deep RL frameworks without further policy approximations.Source: §5.2.4 · pp. 30–31
• Haarnoja et al. (2017, 2018) encouraged policies to reach high-entropy future states, improving exploration by acquiring diverse behaviors.Source: §5.2.4 · p. 31

• Bonus-based methods augment extrinsic reward with a bonus intended to encourage actions leading to more uncertain, novel, or informative states.The bonus may be treated as intrinsic reward.Source: §6 · p. 31
• The survey identifies two design questions: how to specify an effective bonus and how to combine it with extrinsic reward.Source: §6 · p. 31
• The survey groups bonus calculations into optimism-based, count-based, and prediction-error approaches.Optimism can be embedded in initial value estimates, counts can track state-action visits, and prediction-error methods use a model of environment dynamics.Source: §6 · pp. 31–32
• Optimism-based and count-based methods can be difficult to distinguish, so the survey separates them by whether bonus definitions explicitly use counts.It treats optimistic initialization as a bonus for unseen state-action pairs.Source: §6 · p. 32
• The survey divides each of the three approaches into tabular and function-approximation methods.Tabular methods use lookup tables for small spaces; function approximation represents values with parameterized functions for large or infinite spaces.Source: §6 · p. 32

6.1 Optimism-based methods

• Optimism assigns high value to uncertain states, typically through optimistic initialization or upper confidence bounds (UCBs), while this section separates methods that do not explicitly use counts.Optimistic initialization treats unvisited state-action pairs as yielding the best outcome; UCB methods use the largest statistically possible reward.Source: §6.1 · p. 32

6.1.1 Optimism-based methods: tabular

• R-max initializes all actions with maximum reward and uses learned model estimates after a visitation threshold, making optimal actions either explore unknown states or obtain near-optimal reward.Its analysis reports near-optimal performance in polynomial time for finite state spaces.Source: §6.1.1 · pp. 32–33
• Optimistic Initial Model assigns maximum reward to unknown areas and uses dynamic programming with prioritized sweeping; its near-optimal convergence guarantee assumes a lower bound on Rmax.The survey reports empirical assessment against ϵ-greedy, Boltzmann, and other exploration methods across several environments.Source: §6.1.1 · p. 33

6.1.2 Optimism-based methods: function approximation

• For continuous state spaces, Fitted R-max combines R-max with fitted value iteration and estimates visitation using unnormalized kernel values derived from the learned dynamics.The survey reports tests in Mountain Car and Puddle World.Source: §6.1.2 · p. 34
• Function-approximation approaches include UCLS, whose context-dependent confidence bounds encourage exploration of higher-variance states, and actor-critic methods using upper and lower value bounds.UCLS outperformed DGPQ, UCBootstrap, and RLSVI in the listed environments, while OAC showed marginal improvement over SAC on high-dimensional MuJoCo tasks.Source: §6.1.2 · p. 35
• Other approaches decouple optimistic Q-value initialization from network initialization in OPIQ, or use DOVE to learn transition and reward functions and propagate information through local perturbations.The survey reports OPIQ evaluations in toy randomized Markov chain, Maze, and Montezuma’s Revenge, and DOVE benchmarks in high-dimensional continuous-control MuJoCo tasks.Source: §6.1.2 · p. 35

6.2.1 Count-based bonus: tabular

• A count-based bonus is largest for a novel state-action pair and decays as that pair is revisited, but such definitions are mainly suited to finite tabular spaces.Dyna-Q+ adds a bonus proportional to the square root of time since the action was last tried; its reported Blocking and Shortcut experiments outperformed Dyna-Q variations without the bonus.Source: §6.2.1 · p. 37
• Tabular methods include known-versus-unknown state schemes such as E3 and threshold-based count bonuses; the survey also describes average-reward H-learning and Bayesian Exploration Bonus.Metric-E3's time-complexity bound depends on state-space covering numbers rather than state-space size; H-learning and its extension are evaluated in grid-world and AGV-scheduling tasks.Source: §6.2.1 · p. 38
• Jin et al. (2018) report O(√T) regret dependency for the Hoeffding-style bonus and an H improvement with the Bernstein-style bonus; Wang et al. (2020) address sample efficiency and analyze a lower bound for Delayed Q-learning.The Wang et al. passage describes an Ω(1/ϵ^3) lower bound instance for Delayed Q-learning, leaving a quadratic gap in 1/ϵ from the best known lower bound among UCB-based exploration algorithms.Source: §6.2.1 · pp. 39–40

6.2.2 Count-based: function approximation

• For large state spaces, pseudo-counts connect density-model novelty with count-based exploration, and PixelCNN-based density modeling is reported to yield state-of-the-art results in difficult Atari games.The pseudo-count result depends on assumptions about asymptotic density-model behavior and learning rate.Source: §6.2.2 · p. 40
• Function-approximation methods also estimate novelty through discriminative exemplar models, hashing, or successor representations rather than relying only on raw state counts.The hashing approach is reported to outperform Houthooft et al. (2016) in some rllab tasks and vanilla DQN in some Atari games; successor-representation bonuses are evaluated in tabular and function-approximation settings.Source: §6.2.2 · pp. 41–42

6.3 Prediction error-based bonus

• Prediction-error bonuses use changes in knowledge about environment dynamics, with larger discrepancies between predicted and observed outcomes treated as more informative.The survey defines prediction error relative to differences between true model parameters and estimates used to predict transitions.Source: §6.3 · p. 42

6.3.1 Prediction error-based bonus: Tabular

• Tabular approaches include uncertainty-based bonuses for non-stationary finite POMDPs, model-based interval estimation, entropy bonuses, and prediction-loss progress.Lopes et al. (2012) use changes in mean and variance of prediction loss to modify R-Max and Bayesian exploration bonuses, particularly with incorrect prior transition knowledge or changing dynamics.Source: §6.3.1 · pp. 42–44

6.3.2 Prediction error-based bonus: Function Approximation

• For large or infinite state spaces, Stadie et al. (2015) assign bonuses according to disagreement with a learned dynamics model and evaluate the method on 14 Arcade Learning Environments.Their prediction model is a two-layer neural network, with error measured using the l2 Euclidean norm.Source: §6.3.2 · p. 44
• Experiments across 54 environments highlight feature learning's role in generalizability and demonstrate limitations of prediction-based bonuses.Other function-approximation approaches include diversity-based bonuses and information-gain methods, including a variational approach whose lower-bound computation involves posterior probabilities.Source: §6.3.2 · pp. 44–45

7.1 Solving the exploration-exploitation trade-off optimally

• Bayes-adaptive planning makes exploration and exploitation part of one optimal action choice, but its reachable hyperstates grow exponentially with the horizon.The BAMDP augments the physical state with a posterior over unknown transition and reward models; its optimal policy acts on these hyperstates. The growth can make planning intractable as state, action, or horizon size increases.Source: §7.1 · pp. 47–48

7.2 Bayesian Methods

• Bayesian Q-Learning selects actions using expected Q-value plus value of perfect information, while Optimal Probe approximates BAMDP policies with an actor-critic and sampled policy gradients.Bayesian Q-Learning uses distributions over Q-values and proposes moment-matching or mixture updates; Optimal Probe assumes value functions are relatively smooth over information states, trading policy-class bias for complexity independent of the number of hyperstates, but remains feasible only for small information-state spaces.Source: §7.2 · pp. 49–50
• Bayesian Sparse Sampling adaptively expands promising actions using Thompson-sampling heuristics, while BEETLE parameterizes optimal value functions with multivariate polynomials for efficient offline policy optimization.Bayesian Sparse Sampling reports improved action-selection quality when Bayesian posteriors are conveniently calculable. BEETLE’s optimization remains efficient when the number of unknown transition parameters is small, and action selection and belief monitoring occur online.Source: §7.2 · pp. 50–51
• BAMCP samples a transition model at the search-tree root and uses Monte Carlo tree search; it outperforms BOSS and BEB in finite domains and greatly outperforms baselines in an infinite grid.Root-only posterior inference means BAMCP is limited by planning time rather than the infinite grid’s state-space size, which the baselines cannot handle (Guez et al., 2012).Source: §7.2 · pp. 51–52

7.3 Meta-learning

• Black-box meta-RL maps interaction histories to actions, learning exploration behavior that is competitive with classical methods on discrete tasks and applies to challenging visual exploration (Duan et al., 2016b; Wang et al., 2016a).In dependent-arms bandits, Wang et al. (2016a) learn to explore once without reward and then exploit; recurrent-model training tends to require many samples and substantial time. Garcia and Thomas (2019) instead use an advisor to choose exploratory actions, reporting strong performance against base algorithms, random exploration, and MAML on continuous-control tasks.Source: §7.3 · pp. 53–54
• Meta-learning exploration bonuses over programs yields methods that outperform human-designed approaches and generalize across different state and action spaces (Alet et al., 2020).The method searches a combinatorial program space for curiosity mechanisms or bonuses, then uses the adapted reward in a standard reinforcement-learning inner loop; examples span image-based gridworlds and Mujoco environments such as Acrobot.Source: §7.3 · pp. 54–55
• E-MAML learned faster than MAML benchmarks and scored higher on exploration metrics, with similar results for E-RL2, which ignores rewards from exploratory roll-outs (Stadie et al., 2018; Duan et al., 2016b).E-MAML addresses MAML's failure to assign credit to pre-update trajectories.Source: §7.3 · p. 55
• On locomotion benchmarks, Rothfuss et al. (2019) found that a low-variance Hessian estimator improved MAML performance; qualitatively, LVC learned good exploration and exploited gathered information better than MAML or E-MAML.Their analysis found MAML did not learn a good exploration strategy, while E-MAML struggled to assign credit to individual actions.Source: §7.3 · p. 55
• Frans et al. (2018) meta-learned a shared hierarchy in which a master policy explores efficiently, and its sub-policies transferred from small mazes to sparse-reward navigation.The hierarchy's parameters are not updated in the inner update, and second-order gradients are not passed to outer updates.Source: §7.3 · pp. 55–56
• Inference-based meta-RL separates inference about the current MDP from action selection, typically using learned latent embeddings and approximate inference for continuous-state, nonlinear tasks (Gupta et al., 2018; Rakelly et al., 2019).This structure mirrors classical strategies for solving POMDPs or BAMDPs.Source: §7.3 · p. 56
• MAESN learns a latent exploration space for episode-level structured stochasticity and strongly outperforms baseline strategies in learning speed and performance after 100 learning iterations (Gupta et al., 2018).Posterior-sampled latent variables remain constant during an episode, enabling exploration over coherent strategies for the trained environment family.Source: §7.3 · p. 56
• Rakelly et al. (2019) used an amortized inference network for posterior sampling and reported improved results over earlier meta-learning methods, attributing gains presumably to structured exploration and off-policy data.The network minimizes a chosen loss while staying close to a prior; decoupling inference and acting enables use of off-policy data.Source: §7.3 · p. 56
• Zintgraf et al. (2019a) optimized embeddings to decode transition and reward information and reported that their method strategically explored gridworlds, outperforming black-box meta-learning methods by a large margin in preliminary experiments.The policy was conditioned on the mean and covariance of the full variational posterior rather than using posterior sampling.Source: §7.3 · p. 56

Thompson Sampling and PSRL

• Thompson Sampling chooses actions according to their posterior probability of being optimal; PSRL adapts posterior sampling by using one sampled MDP throughout an episode.For Bernoulli bandits, the example updates Beta priors from observed successes and failures before sampling arm means.Source: §8 · p. 57

Posterior Sampling for Reinforcement Learning

• PSRL outperforms UCRL2 in the surveyed six-state chain and random ten-state, five-action domains.It updates a full posterior over MDP models, samples a model each episode, and plans for that episode.Source: §8 · p. 57

Other posterior-sampling methods

• BOSS combines sampled posterior models into an optimistic MDP, while Agrawal and Jia combine posterior sampling with optimism to obtain near-optimal worst-case regret bounds for communicating MDPs.BOSS reports superior results to BEETLE and RMAX on a five-state chain and 6x6 grid-world; Agrawal and Jia report no experiments.Source: §8 · p. 58

Randomized Value Functions

• Randomized Value Functions sample a value function at each episode’s start, sustaining a consistent strategy and supporting function approximation.They model value-function distributions rather than MDP distributions; exact inference over value functions may still be computationally intractable.Source: §8 · pp. 58–59

Randomized Least Square Value Iteration

• RLSVI uses Bayesian linear regression to sample uncertain value functions and is reported efficient for linear value approximators, including a 100-state chain.It outperforms LSPI and LSVI on Tetris and recommendation tasks with appropriate basis functions, but its approximate posterior is not a coherent Bayesian belief update.Source: §8 · p. 59

Limitations

• Posterior distributions over value functions can be as complex as transition-model distributions, making exact Bayesian inference potentially intractable.RLSVI provides a computationally tractable way to sample value functions without explicitly maintaining and updating coherent beliefs.Source: §8 · p. 59

Bootstrapped Q-learning

• Bootstrapped-DQN follows one of K bootstrapped Q-function heads per episode and learns faster with higher final scores on most Atari games than DQN.The approach uses parallel estimates to approximate Q-value uncertainty when exact Bayesian inference is intractable.Source: §8 · p. 59

Successor Uncertainties

• Successor Uncertainties outperforms Bootstrapped-DQN on 36 of 49 Atari games and scales to chains of 200 states.It models posteriors over rewards and transitions directly, then derives value-function posteriors analytically.Source: §8 · p. 61

Taxonomy

• The taxonomy divides exploration into reward-free methods and reward-based methods, with the latter further divided into memory-free and memory-based approaches.Reward-free methods can be useful when extrinsic rewards are sparse; reward-based methods use reward information in exploratory action selection.Source: §9 · p. 61

Purpose

• The survey aims to give practitioners a big-picture guide to method choices, rather than review the field’s abundant theoretical sample-complexity results.It describes methods’ strengths and limitations and notes that useful empirical results may occur even when theoretical assumptions are unmet.Source: §9 · p. 61

Scope

• Coverage is limited to sequential decision making in MDPs; POMDPs and bandits are not treated in detail, and some similar methods are omitted.Safe exploration is identified as an emerging topic that the survey does not focus on because relatively little had been written about it.Source: §9 · pp. 61–62

Evaluation challenges

• Comparisons are complicated by differing evaluation measures and a lack of standard experimental tasks across exploration methods.The survey also notes discrepancies between theoretical guarantees and experimental conditions, limiting reliable guarantees in more involved environments.Source: §9 · p. 62