PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning

Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, Jimmy Ba

arXiv:2007.02832v1cs.LGcs.AIcs.ROstat.ML

TL;DR

Long-horizon multi-goal reinforcement learning lacks useful feedback when desired goals are too distant to reach through exploration. The paper selects intrinsic goals from sparsely explored achieved-goal regions to maximize achieved-goal entropy, then transitions toward desired-goal training. Across long-horizon tasks, this strategy achieves more than 10 times the sample efficiency of prior approaches.

  • Problem

    Sparse-reward learning becomes difficult when desired goals are too far from the agent’s initial state distribution to provide useful learning signals.

  • Method

    MEGA selects previously achieved goals in sparsely explored regions to maximize achieved-goal entropy, while OMEGA anneals this unsupervised objective into the desired-goal objective.

  • Results

    The strategy is more than 10 times as sample efficient as prior approaches across four long-horizon multi-goal tasks.

  • Takeaways & Limitations

    Focusing exploration on the frontier of the achievable goal set provides an automatic behavioural curriculum for long-horizon multi-goal tasks.

  • Takeaways & Limitations

    The experiments assume predefined, semantically meaningful, well-behaved goal spaces, leaving extension to learned latent goal spaces unresolved.

Abstract

from arXiv · show

What goals should a multi-goal reinforcement learning agent pursue during training in long-horizon tasks? When the desired (test time) goal distribution is too distant to offer a useful learning signal, we argue that the agent should not pursue unobtainable goals. Instead, it should set its own intrinsic goals that maximize the entropy of the historical achieved goal distribution. We propose to optimize this objective by having the agent pursue past achieved goals in sparsely explored areas of the goal space, which focuses exploration on the frontier of the achievable goal set. We show that our strategy achieves an order of magnitude better sample efficiency than the prior state of the art on long-horizon multi-goal tasks including maze navigation and block stacking.

1. Introduction

Long-horizon sparse-reward tasks make desired-goal training ineffective when those goals are too distant. The paper proposes intrinsic goal selection that maximizes entropy over achieved goals and reports substantially improved sample efficiency.

  • 1. Introduction: The paper introduces MEGA, which maximizes the entropy of the historical achieved-goal distribution for early unsupervised exploration.OMEGA anneals this objective into the desired-goal objective once supervised learning becomes tractable.
  • 1. Introduction: The framework is presented as an automatic behavioural goal curriculum for mastering long-horizon, sparse-reward tasks.
  • 1. Introduction: MEGA selects previously achieved goals in sparsely explored regions using a learned density model, pushing the frontier of achievable goals forward.This avoids spending environment steps on already mastered or unobtainable goals.
  • 1. Introduction: Combined with hindsight experience replay and off-policy learning, the method achieves more than an order of magnitude better sample efficiency on long-horizon mazes and block stacking.

2. The Long-Horizon Problem

Sparse rewards make long-horizon multi-goal learning difficult because useful feedback requires encountering distant goals. The paper organizes existing goal-selection mechanisms and proposes intrinsic frontier-focused selection to expand the achieved-goal distribution.

  • 2. The Long-Horizon Problem: Random exploration becomes exponentially less likely to discover useful successes as task horizon increases, causing vanilla sparse-reward agents to learn slowly or not at all.
  • 2. The Long-Horizon Problem: HER relabels trajectories with goals achieved later in the same episode, creating a curriculum that lets agents learn about goals encountered during exploration.However, HER still requires the agent to encounter the target or a sufficiently similar goal.
  • 2. The Long-Horizon Problem: When achieved and desired goal distributions do not overlap, learning signals for distant goals are unavailable, and DDPG+HER agents can fail on long-horizon tasks.The paper illustrates this failure with increasing-height box-lifting and disconnected initial and desired distributions.
  • 2. The Long-Horizon Problem: MEGA addresses the long-horizon problem by selecting previously achieved goals in sparse regions of the achieved-goal distribution, while OMEGA anneals intrinsic selection toward environment goals.Its contributions are a frontier-oriented selection mechanism and a practical transition from unsupervised to supervised goal selection.
  • 2. The Long-Horizon Problem: The unified framework separates multi-goal agents into SELECT, REWARD, and RELABEL procedures, allowing methods such as HER, achieved-goal sampling, and density-based strategies to be compared consistently.
  • 2. The Long-Horizon Problem: Relative to MEGA, diverse achieved-goal sampling still under-explores the frontier of the goal distribution.

3. Maximum Entropy Goal Achievement

The MEGA objective addresses ill-conditioned distribution matching in long-horizon tasks by maximizing entropy over achieved goals, then anneals toward the desired-goal objective when appropriate. The practical method selects under-explored achievable goals, using entropy-gain reasoning and a minimum-density approximation to expand the explored goal set.

  • 3.1. The MEGA and OMEGA objectives: The intrinsic behavioural goal is chosen to improve the historical achieved-goal distribution, while goal relabeling allows replayed transitions to train for alternative goals.The forward-KL formulation emphasizes covering desired goals rather than matching them by leaving uncovered regions unexplored.
  • 3.1. The MEGA and OMEGA objectives: The original forward-KL objective is ill-conditioned or undefined when desired and achieved-goal supports do not overlap, whereas entropy maximization remains useful during early exploration.Forward KL seeks an achieved distribution that covers the desired distribution, which may fail before any overlap exists.
  • 3.1. The MEGA and OMEGA objectives: When achieved goals do not cover the desired distribution, MEGA maximizes achieved-goal entropy to expand coverage without relying on a potentially misleading exploration direction.This makes distribution matching tractable as the achievable support expands.
  • 3.1. The MEGA and OMEGA objectives: OMEGA interpolates between entropy maximization and desired-goal matching, using a mixture whose weighting increases as the achieved distribution approaches the desired distribution.In the experiments, the weighting is controlled by the divergence between desired and achieved distributions and uses bias b = −3.
  • 3.2. Optimizing the MEGA objective: In supervised tasks, OMEGA approximately optimizes the objective by choosing the environment goal with probability α and otherwise invoking MEGA selection.The resulting selection procedures are specified in Algorithm 2.
  • 3.2. Optimizing the MEGA objective: Entropy-gain exploration selects behavioural goals whose predicted outcomes are diverse and differ from historical experience, approximating constrained ascent on achieved-goal entropy.Because the conditional outcome distribution is difficult to estimate, the practical method uses a minimum-density heuristic over candidate goals and eliminates unachievable candidates.

4. Experiments

Across four long-horizon environments, MEGA and OMEGA expand achieved-goal coverage and solve tasks more sample-efficiently than the evaluated baselines, with OMEGA later shifting toward desired goals.

  • Environments: The experiments cover PointMaze, AntMaze, FetchPickAndPlace, and FetchStack2, spanning two- to six-dimensional goals and success criteria that differ across tasks.Maze tasks require reaching a goal once, while the robotic tasks require maintaining success through the episode.
  • Visualization of achieved goals: In PointMaze, MEGA and OMEGA spread behavioral and terminal goals outward from the start, reaching the desired area in approximately 2,000 episodes.Their progression resembles breadth-first search, whereas Diverse sampling remains relatively uniform but explores slowly.
  • Main results: O/MEGA solve PointMaze and AntMaze substantially faster than prior state-of-the-art methods, with nearly 100× and roughly 10× fewer time steps, respectively.On PointMaze, O/MEGA reach 90% success nearly 100 times faster than PPO+SR; on AntMaze, they are roughly 10 times faster than hierarchical PPO+SR.
  • Main results: MEGA and OMEGA are the only methods reported to solve the evaluated tasks with highest sample efficiency, while most baselines fail to bridge the initial-to-desired goal gap.Desired-goal sampling fails, and Achieved and Diverse sampling do not focus sufficiently on the frontier of achieved goals.
  • Maximizing entropy: MEGA and OMEGA increase achieved-goal entropy much faster than other samplers, and success begins as the maximum entropy is approached.GoalDisc is also a strong optimizer of the entropy objective on AntMaze and has comparable performance to MEGA there.
  • Maximizing entropy: OMEGA eventually shifts from intrinsic toward desired goals; this transition supports long-run stability in FetchStack2 but can reduce entropy as desired trajectories become overrepresented.The shift is represented by OMEGA’s α schedule and corresponds to declining entropy after desired-goal trajectories dominate.

5. Other Related Work

Related work distinguishes MEGA’s exploratory goal selection from methods that only reshape training distributions or optimize empowerment on-policy. The paper instead uses off-policy behavioral goals to maximize entropy over achieved goals.

  • Maximum entropy-based prioritization: MEP reweights training experiences to increase goal entropy but does not set intrinsic goals, so it cannot directly drive exploration across long-horizon gaps.MEP remains limited to observed achieved-goal support and must rely on function-approximator generalization.
  • Maximum entropy-based prioritization: MEGA selects sparsely explored achieved goals to influence behavior, whereas MEP only changes optimization weighting after data are collected.Combining them has limited effect because MEGA may already produce an approximately uniform achieved-goal distribution.
  • Curiosity: MEGA’s goal-space entropy objective is related to state-entropy, novelty, and frontier-exploration methods, but MEGA agents choose their own goals because the policy changes with the goal.This distinguishes goal-conditioned exploration from noise-conditioned and variational exploration approaches.
  • Empowerment: The combined MEGA objective has an empowerment-like interpretation: maximize historical achieved-goal entropy while minimizing conditional entropy of achieved goals given potential goals.Empowerment is described as maximizing mutual information between goals and achieved goals, roughly enlarging the achievable goal set.
  • Empowerment: Unlike common on-policy empowerment methods that fix or parameterize the optimized goal distribution, MEGA lets off-policy behavioral goals gather data for optimizing empowerment over all potential goals.This reframes behavioral goal selection as exploration for the off-policy objective rather than restricting behavior to the distribution being optimized.

6. Limitations and Future Work

The work is limited to predefined, semantically meaningful, well-behaved goal spaces and assumes a suitable goal representation. It also relies on an achievability approach whose broader applicability remains open.

  • Experiments focus on predefined, semantically meaningful, well-behaved goal spaces rather than learned latent goal spaces.The authors identify extension to automatically learned goal spaces as future work.
  • Differential entropy is sensitive to feature-space reparameterization, requiring well-behaved goal spaces or a more parameterization-robust objective.
  • MEGA’s minimum-density heuristic depends on an achievability approach, leaving its broader applicability as a limitation.

7. Conclusion

The paper addresses long-horizon sparse-reward multi-goal reinforcement learning by maximizing the entropy of historical achieved goals. It selects sparsely explored achieved goals to explore the frontier of achievable goals and reports more than 10 times better sample efficiency than prior approaches across four tasks.

  • More than 10 times better sample efficiency than prior approaches is reported across four long-horizon multi-goal tasks.
  • The method maximizes entropy of the historical achieved goal distribution by pursuing past achieved goals in sparsely explored regions.
  • The efficient computation reduces complexity from O(d^3) to O(d^2), where d is the support size.
  • The continuous formulation extends the entropy-gradient objective using a density model with full support, obtained by treating achieved observations as noisy.
  • Under deterministic goal transitions, the entropy-gradient objective reduces to selecting goals with minimum achieved-goal density.

C. Implementation Details

The implementation combines online goal relabeling, density modeling, achievability filtering, and additional exploration around repeatedly achieved goals. KDE is selected for density modeling because it performs similarly to Flow while outperforming RND in PointMaze.

  • Goal Relabeling: The rfaab strategy relabels transitions with real, future, actual, achieved, and behavioral goals to combine cross-trajectory generalization with optimization of desired and intrinsic goals.
  • Density Modeling: KDE and Flow obtain similar PointMaze performance, while RND makes very slow progress; KDE is selected for its speed, simplicity, and effectiveness.The authors note that Flow or a VAE-like model may be needed in higher-dimensional spaces.
  • Cutoff mechanism and Go Exploration: The cutoff mechanism rejects candidate goals whose critic-estimated Q-values fall below a dynamic cutoff, helping especially when desired goals are added to MEGA’s candidate set.
  • Cutoff mechanism and Go Exploration: Go Exploration increases epsilon exploration by 10% after each behavioral-goal re-achievement, reaching purely random exploration after 10 achievements in an episode.
  • Cutoff mechanism and Go Exploration: Antmaze trajectories travel toward achieved goals and then explore around them, forming a flowery pattern that fills low-density regions.

D. Additional Experiment Details and Experiments

Additional experiments average results across multiple seeds and modify FetchPickAndPlace’s desired-goal distribution to test HER and OMEGA under a uniform distribution. The supplied details specify evaluation reproducibility and this distributional modification.

  • Figures use averages across seeds with shaded regions representing one standard deviation, while Figures 2, 8, and 13 use three seeds.
  • FetchPickAndPlace’s desired-goal distribution was modified to be uniform over the range stated in Figure 2’s legend before evaluating HER and OMEGA.

D.3. Minimum Density Approximation Versus Learned Conditional for Entropy Gain

The section compares a learned conditional entropy-gain estimator with the simpler minimum-density heuristic for selecting behavioral goals. Although the conditional can accelerate early test-success learning, minimum density is retained because it offers similar performance with substantially lower complexity and runtime.

  • The conditional models q(g′|ˆg) by factorizing it into a KDE-estimated joint distribution divided by a KDE-estimated behavioral-goal marginal.
  • For each sampled behavioral-goal candidate, the method samples K = 10 achieved goals and uses a Monte Carlo estimate of expected entropy gain from Equation 9.
  • The learned conditional gives slightly faster learning progress on PointMaze, including fewer environment steps to reach 95% success.
  • The comparison evaluates test success, achieved-goal-buffer KDE entropy, and OMEGA’s α parameter on PointMaze.
  • The conditional estimator initially produces lower achieved-goal entropy, then overtakes minimum density as its model improves during training.
  • Similar test success and MEGA objective performance, with much simpler and faster execution, motivate using minimum density for the remaining experiments.

D.4. Ablation of implementation features

The section ablates three implementation features beyond the MEGA objective: rfaab sampling, Q-value filtering of unachievable candidates, and increased action exploration after intrinsic-goal achievement. These features are evaluated on PointMaze and FetchStack2.

  • The ablation studies rfaab goal sampling, a Q-value cutoff for unachievable candidates, and increased action exploration after intrinsic-goal achievement.
  • Figure 12 evaluates these implementation features on PointMaze and FetchStack2.

D.5. MEGA Tested on Smaller AntMaze

The section evaluates HER and MEGA on a smaller AntMaze using a desired-goal grid aligned with Florensa et al.’s coverage objective. The reported comparison is qualified because this smaller environment is not truly long-horizon.

  • HER and MEGA are tested on an AntMaze matching Florensa et al.’s size and desired-goal grid, making test success comparable to their coverage objective.
  • Figure 13 reports the small AntMaze results.
  • The smaller AntMaze is not really long horizon, so its faster performance primarily reflects off-policy learning and goal relabeling rather than MEGA.

D.6. Toy Example: Discrete Entropy Gain

A discrete toy MDP compares four behavioral-goal policies and shows how minimum-density selection approximates entropy-gain maximization. Minimum density nearly matches an oracle entropy-gain policy and expands support faster than achieved-goal or diverse sampling.

  • The toy MDP starts with buffer B = {n}, samples an achieved goal from q(g′|ˆg), and adds it to the buffer after each behavioral-goal choice.
  • The transition model assigns probabilities 0.4, 0.2, and 0.1 to the current goal and offsets of one and two, with boundary truncation and renormalization.
  • The four policies are achieved-goal sampling, diverse support sampling, minimum-density sampling, and an oracle choosing the goal with maximum next-step entropy gain.
  • Minimum density is almost as fast as oracle entropy-gain sampling and reaches the maximum-entropy distribution much faster than achieved-goal and diverse sampling.The comparison uses n = 50 and averages results over 50 trials.
  • Figure 14 measures empirical buffer entropy and support size over time, while Figure 15 visualizes achieved-goal log probabilities across iterations.
  • Oracle entropy-gain sampling expands buffer support consistently each iteration, whereas minimum density spends time sampling goals in the interior.
Loading 2007.02832v1…