PaperlayerView exact revision on arXiv

Source-linked AI summary

Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills

Víctor Campos, Alexander Trott, Caiming Xiong, Richard Socher, Xavier Giro-i-Nieto, Jordi Torres

arXiv:2002.03647v4cs.LGcs.AIstat.ML

TL;DR

Existing information-theoretic skill-discovery methods often produce options with poor state-space coverage because their distribution estimates depend on the policy's already discovered behavior. EDL uses a fixed state distribution with variational inference and staged exploration, discovery, and learning, while optimizing the same information-theoretic objective. The paper's theoretical and empirical evidence shows that this approach improves state coverage and addresses limitations of existing methods.

  • Problem

    Existing information-theoretic skill-discovery algorithms have a common limitation: they discover options with poor state-space coverage.

  • Method

    EDL uses a fixed distribution over states, variational inference, and separate exploration, skill-discovery, and skill-learning stages while optimizing the information-theoretic objective.

  • Results

    Theoretical and empirical evidence shows that existing methods favor known states over new ones, while EDL discovers skills with better state-space coverage.

  • Takeaways & Limitations

    Separating exploration from skill discovery breaks the dependence on policy-induced state distributions and provides an alternative route to state-covering option discovery.

  • Takeaways & Limitations

    In bottleneck mazes, effective EDL evaluation required an oracle to simulate perfect exploration because the exploration method used could not explore those mazes effectively.

Abstract

from arXiv · show

Acquiring abilities in the absence of a task-oriented reward function is at the frontier of reinforcement learning research. This problem has been studied through the lens of empowerment, which draws a connection between option discovery and information theory. Information-theoretic skill discovery methods have garnered much interest from the community, but little research has been conducted in understanding their limitations. Through theoretical analysis and empirical evidence, we show that existing algorithms suffer from a common limitation -- they discover options that provide a poor coverage of the state space. In light of this, we propose 'Explore, Discover and Learn' (EDL), an alternative approach to information-theoretic skill discovery. Crucially, EDL optimizes the same information-theoretic objective derived from the empowerment literature, but addresses the optimization problem using different machinery. We perform an extensive evaluation of skill discovery methods on controlled environments and show that EDL offers significant advantages, such as overcoming the coverage problem, reducing the dependence of learned skills on the initial state, and allowing the user to define a prior over which behaviors should be learned. Code is publicly available at https://github.com/victorcampos7/edl.

1. Introduction

Unsupervised reinforcement learning seeks generally useful behaviors without task-specific rewards, often using empowerment and mutual information for skill discovery. The paper argues that existing methods poorly cover the state space and introduces EDL to address this limitation.

  • Unsupervised RL aims to learn generically useful behaviors before downstream tasks or task-specific rewards are available.
  • Empowerment frames unsupervised RL as discovering what an agent can do while learning how to do it.
  • Existing methods prematurely reinforce already discovered behaviors instead of exploring for novel options, producing poor state-space coverage.
  • EDL is a three-stage methodology designed to discover skills with much better coverage.
  • The paper combines theoretical analysis, empirical evidence, and controlled-environment evaluation to show existing failures and assess EDL.

2. Information-theoretic skill discovery

Information-theoretic skill discovery maximizes mutual information between states and latent skills, using variational approximations and policy-induced distributions. The paper identifies a shared failure: these methods reward revisiting known states more than discovering new ones, limiting state coverage.

  • Information-theoretic methods learn latent-conditioned policies and maximize mutual information between states S and latent variables Z.
  • The mutual-information objective has reverse and forward forms, which the paper uses to classify and compare existing methods.
  • Variational methods estimate unknown posteriors or state distributions from rollout data collected under the policy.
  • Existing methods include VIC, SNN4HRL, DIAYN, VALOR, and DADS, which differ in objectives, priors, rewards, or model-based formulations.
  • Known states can receive rewards up to rmax = log N, whereas previously unseen states receive rnew = 0 under both mutual-information forms.
  • In a bottleneck maze, existing methods mostly revisit regions reachable by a random policy instead of expanding the visited state set.

3. Proposed method

EDL breaks the policy-dependent feedback loop by using a fixed state distribution and separating exploration, skill discovery, and skill learning. Variational inference assigns latent skills to regions of that distribution, after which a policy learns to realize them.

  • EDL replaces the policy-induced state distribution with a fixed distribution p(s), avoiding optimization over states selected by the current policy.
  • EDL separates the process into exploration, skill discovery, and skill learning, allowing the stages to be studied independently.
  • Exploration can use an oracle or a maximum-entropy exploration policy to obtain samples from states the skills should cover.
  • Variational inference models p(z|s) and p(s|z), assigning latent codes to state-space regions and identifying states each skill should visit.
  • Because exploration and discovery are disentangled, different skill priors can be learned without relearning the skill-conditioned policy from scratch.
  • The final policy maximizes mutual information against a fixed reward derived from the decoder rather than a reward that changes with policy behavior.

4. Experiments

Experiments in controlled continuous 2D mazes test EDL under exploration, initial-state, prior, bottleneck, and skill-interpolation conditions. EDL achieves broad state coverage, is less sensitive to initial-state distributions, incorporates behavioral priors, and generalizes between learned skills, while bottleneck exploration remains challenging.

  • Experimental setup: Controlled continuous 2D mazes vary topology and initial conditions to expose specific strengths and limitations of skill-discovery methods.The agent observes its position and controls its location, with wall collisions shaping behavior.
  • Exploration with SMM: EDL learns state-covering skills even when State Marginal Matching replaces an exploration oracle.SMM collected more samples near maze walls, producing slight differences in discovered options.
  • Impact of the initial state: Baselines vary substantially with p(s0), whereas EDL discovers very similar options across Ecenter and Eleft setups.The EDL setups differ in where exploration and skill discovery occur, while skills are later learned in both environments.
  • Encouraging specific behaviors: EDL incorporates a prior for skills on the maze’s right side by concentrating learned options within that region.Without a prior, EDL learns options across the whole state space.
  • Impact of bottleneck states: Bottleneck mazes expose EDL limitations: SMM exploration fails, and EDL’s reward functions create deceptive local optima without Sibling Rivalry.The evaluation therefore uses an oracle for perfect exploration, while Sibling Rivalry helps policies avoid getting stuck.
  • Interpolating between skills: Interpolating latent vectors produces skills that reach states corresponding to Euclidean interpolations between the original skills’ goals.The original skills are selected randomly from the learned options, and interpolated rollouts blend their colors for visualization.

5. Related work

Related work frames unsupervised option discovery alongside intrinsic rewards, novelty search, quality diversity, and goal-conditioned reinforcement learning. These approaches address exploration, behavioral diversity, or goal achievement using different sources of structure and supervision.

  • Option discovery: Option discovery automatically constructs temporally extended primitives, complementing approaches that define options while solving tasks or using demonstrations.Options are an important reinforcement-learning resource, but specifying them can require difficult task-specific knowledge.
  • Intrinsic rewards: Intrinsic rewards provide denser, task-agnostic signals such as state-visitation counts to alleviate inefficient exploration in sparse-reward settings.These rewards are computed automatically rather than supplied as task-specific objectives.
  • Novelty Search: Novelty Search seeks diverse task-agnostic behaviors without a fitness function, while Quality Diversity combines behavioral diversity with task-specific fitness.Both families rely on behavior characterization to represent behavioral variation.
  • Goal-oriented RL: Goal-oriented reinforcement learning conditions policies and rewards on goals, but defining the goal distribution requires expert domain knowledge.Known goal distributions enable techniques such as experience relabeling and reward shaping.

6. Discussion

The paper identifies poor state-space coverage as a predominant failure mode of existing skill-discovery methods and proposes EDL to address it while preserving the information-theoretic objective. EDL’s modular design also supports robustness to initial-state changes and user-defined behavioral priors, although its stages and distributional assumptions remain open challenges.

  • Discussion: EDL uses a fixed state distribution and variational inference to avoid dependence on policy-induced distributions while optimizing the same information-theoretic objective as prior methods.This design is intended to break the pathological training dynamics caused by approximating unknown distributions with policy-induced ones.
  • Discussion: EDL discovers state-covering skills in environments where previous methods fail and is more robust to changes in the initial-state distribution.The paper also reports that EDL enables users to incorporate priors over which behaviors are useful.
  • Discussion: EDL’s three-stage paradigm is modular, allowing each stage to incorporate advances from its respective research direction.Examples include state marginal matching, discrete-prior vector quantization, and relabeling techniques.
  • Discussion: EDL’s applicability depends on improvements in pure exploration methods, whose reward optimization remains challenging for current algorithms.The paper identifies this as a future-work direction for extending EDL to a broader range of environments.
  • Discussion: The Gaussian assumption for p(s|z) produced deceptive reward functions in the experiments and may be detrimental in other environments.The authors motivate learning state embeddings and reward functions that reflect similarity in controllable aspects of the environment.
  • Discussion: Information-theoretic methods may also support unsupervised task discovery in meta-RL, identified as another direction for future research.

A. Theoretical analysis of existing methods

The theoretical analysis examines why existing methods fail to encourage state-covering skills by studying their reward functions for known and novel states. It shows that the asymptotic reward behavior favors revisiting known states over discovering new ones.

  • Theoretical analysis: The analysis studies existing methods’ reward functions and their asymptotic behavior for known and novel states.The stated goal is to explain theoretically why these methods do not encourage state-covering skill discovery.
  • Theoretical analysis: Existing methods give agents larger rewards for visiting known states than for discovering new ones.

A.1. Reverse form of the mutual information

The reverse mutual-information analysis compares rewards assigned to states already associated with discovered skills against rewards assigned to previously unseen states. Under the stated assumptions, the reward function favors known states and thereby explains poor state-space coverage.

  • Reverse form of the mutual information: For known states, the reward function encourages skills to visit disjoint regions where ρπ(z′|s) approaches 1.
  • Reverse form of the mutual information: For previously unseen states, the analysis assumes a uniform skill prior because ρπ(z|s) is undefined there.
  • Reverse form of the mutual information: Adding a background class would assign null probability to unseen states, differing from the setup used in previous works.
  • Reverse form of the mutual information: As ρπ(z′|s) approaches zero for a new state, the reward tends to −∞ under the analyzed expression.
  • Reverse form of the mutual information: These reward differences explain why the learned skills provide poor coverage of the state space.

A.2. Forward form of the mutual information

The forward mutual-information formulation rewards skills for being predictable and diverse on known states, but gives less reward to novel states, discouraging state-space coverage. Its reverse form can be sparse and may produce unpredictable skills when combined with entropy regularization.

  • Forward mutual information: The objective approximates p(s|z) and p(s) with stationary state distributions estimated from policy-generated (s, z)-tuples.The analysis assumes perfect estimates of ρπ(s|z) when studying the reward asymptotically.
  • Forward mutual information: For known states, the reward favors predictable skills with ρπ(s|z′) approaching 1 and diverse skills with competing probabilities approaching 0.This behavior is derived for N discrete skills under the forward formulation.
  • Forward mutual information: For previously unseen states, all skill-conditioned stationary probabilities approach zero, producing a smaller reward than known states.The asymptotic comparison assigns known states a maximum reward of log N while novel states receive 0.
  • Forward mutual information: Because known states provide larger rewards than unseen states, the forward formulation produces options with poor state-space coverage.The toy gridworld illustrates this by rewarding visits to known, distinguishable states but not novel ones.
  • Forward mutual information: The forward formulation's reward landscape is analyzed under perfect density estimation, where both mutual-information forms coincide in the toy gridworld.Each skill starts from the central tile and receives reward for visiting known states where it is maximally distinguishable.
  • Reverse mutual information: The reverse form can be written using a categorical posterior q(z|s), with the constant log p(z) term removed under a uniform skill prior.This alternative models the unknown distributions differently from the forward form.
  • Reverse mutual information: The reverse-form reward is sparse because many states provide no reward and can assign maximum reward to many states, potentially causing unpredictable skills with entropy bonuses.The latter behavior may be undesirable when combining learned skills in a downstream controller.

C. Implementation Details

The experiments use partially observable maze environments, PPO-trained agents, and independently tuned exploration and skill-discovery components. SMM exploration, VQ-VAE skill discovery, and environment-specific hyperparameter searches support the implementation.

  • Environments: Maze agents infer wall locations from experience because walls are unobserved, and each episode starts from a sampled 1 × 1 tile.The maze environments are adapted from an open-source implementation.
  • Environments: The experiments report environment details in Table 2.The supplied table caption identifies the table as containing environment details.
  • RL agents: Agents use Beta-distribution policies, entropy regularization, a uniform categorical skill prior, PPO, and Adam, with hyperparameters tuned independently for each method.The action distribution is shifted and scaled to the task action range.
  • Exploration: SMM exploration uses a mixture of policies targeting a uniform state distribution, with its density model approximated by a VAE.States from the replay buffer are used in the exploration implementation.
  • Exploration: The implementation samples replay-buffer states non-parametrically, but exponential sampling may be needed elsewhere to avoid oversampling states from initially random policies.The implementation follows released code and tunes hyperparameters independently for each environment.
  • Skill discovery: Skill discovery uses a VQ-VAE with discrete latents and a commitment loss, setting codebook size to the desired number of skills.Hyperparameters are tuned independently for each environment and exploration method.

D. Figure details

The figure details specify the experimental sampling protocol: agents learn ten skills, each evaluated with twenty rollouts, while random-policy visualizations use one hundred rollouts per untrained skill.

  • Sampling protocol: All experiments learn 10 skills to balance behavioral variety with visualization ease.The learned policies are stochastic, so the paper reports multiple rollouts per skill.
  • Sampling protocol: The evaluation reports 20 rollouts per learned skill.This count is used because the learned policies are stochastic.
  • Sampling protocol: Table 4 documents the hyperparameters used for SMM-based exploration.The table caption states that bracketed values were searched independently for each environment.
  • Sampling protocol: Random-policy visualizations collect 100 rollouts for each untrained skill.Trajectories overlap substantially, so they are rendered using one color to reduce clutter.

E. Additional visualizations

Additional visualizations examine discovered goals, reward landscapes, and skill interpolation, extending the paper's main results with diagnostic views of the learned representations and behaviors.

  • Goal states: The supplementary visualizations include goal states discovered by methods using the forward mutual-information form.Figure 7 compares discovered goals across methods.
  • Additional visualizations: The supplementary material documents additional skill interpolations alongside the goal-state and reward-landscape visualizations.These figures provide further insight into results omitted from the main paper because of space constraints.
  • Goal states: EDL's uniform state distribution enables goal discovery across the state space, unlike a baseline whose policy seldom leaves the initial room.Goals are defined as the most likely state under qφ(s|z) for each skill.
  • Reward landscapes: A reward-landscape visualization shows that some maximum-reward points lie in unexplored regions because of the Gaussian assumption over p(s|z).The figure also plots trajectories from each skill and marks each skill's maximum-reward point.
  • Reward landscapes: The posterior qφ(z|s) partitions the state space into disjoint regions, allowing skills to maximize reward by entering their corresponding regions.The posterior also extrapolates this partition to states that have not been visited.
  • Reward landscapes: Another reward landscape uses bell-shaped functions centered on skill centroids, creating dense signals but leaving training prone to local optima.These landscapes are shown for the agent in Figure 1's right panel.
  • Skill interpolation: Skill interpolation blends the latent z vectors of two randomly selected learned skills and blends their visualization colors.The original skills occupy the first row and column of the interpolation figure.
Loading 2002.03647v4…