PaperlayerView exact revision on arXiv

Source-linked AI summary

Keeping Your Distance: Solving Sparse Reward Tasks Using Self-Balancing Shaped Rewards

Alexander Trott, Stephan Zheng, Caiming Xiong, Richard Socher

arXiv:1911.01417v1cs.AI

TL;DR

Sparse-reward tasks can be difficult to learn, and distance-to-goal shaping can produce local optima. Sibling Rivalry uses paired rollouts to balance goal progress with avoiding those optima; the paper reports success across hard-exploration tasks and describes the method’s goal-reaching scope.

  • Problem

    Distance-to-goal reward shaping can create local optima that frustrate learning, while task assumptions define success as reaching a goal within a distance threshold.

    Source: §3 · p. 3, §2 · p. 3

  • Method

    Sibling Rivalry uses sibling rollouts and self-balancing rewards to shape distance-to-goal learning without problem-specific reward design.

    Source: §1 · p. 2

  • Results

    Sibling Rivalry is reported to solve hard-exploration sparse-reward tasks across four settings, including navigation, bit flipping, and Minecraft construction.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The method’s shaped reward converges to the original sparse reward as the policy learns to reach the goal.

    Source: §1 · p. 2, §3 · p. 5

    The intuition for choosing a fixed anti-goal varies with the environment, goal, and learning algorithm.

    Source: §3 · p. 4

Abstract

from arXiv · show

While using shaped rewards can be beneficial when solving sparse reward tasks, their successful application often requires careful engineering and is problem specific. For instance, in tasks where the agent must achieve some goal state, simple distance-to-goal reward shaping often fails, as it renders learning vulnerable to local optima. We introduce a simple and effective model-free method to learn from shaped distance-to-goal rewards on tasks where success depends on reaching a goal state. Our method introduces an auxiliary distance-based reward based on pairs of rollouts to encourage diverse exploration. This approach effectively prevents learning dynamics from stabilizing around local optima induced by the naive distance-to-goal reward shaping and enables policies to efficiently solve sparse reward tasks. Our augmented objective does not require any additional reward engineering or domain expertise to implement and converges to the original sparse objective as the agent learns to solve the task. We demonstrate that our method successfully solves a variety of hard-exploration tasks (including maze navigation and 3D construction in a Minecraft environment), where naive distance-based reward shaping otherwise fails, and intrinsic curiosity and reward relabeling strategies exhibit poor performance.

1 Introduction

Sparse rewards can be hard to learn from quickly, while shaped rewards may require problem-specific engineering and introduce local optima. The paper proposes Sibling Rivalry, which uses paired rollouts to balance progress toward goals with avoiding local optima, and reports success across hard-exploration settings.

1 Introduction

  • Distance-to-goal shaping can create environment- and task-dependent local optima that prevent learning the original task’s optimal behavior.This makes successful reward shaping problem-specific and can require domain expertise.Source: §1 · p. 2
  • Sibling Rivalry’s additional objective is self-scheduling: its shaped reward converges to the sparse reward as the policy learns to reach the goal.The method uses sibling rollouts to estimate local optima and encourage behaviors that avoid them while making progress toward the goal.Source: §1 · p. 2
  • Sibling Rivalry is a model-free dynamic reward-shaping method designed to preserve optimal policies on sparse-reward tasks.It uses sibling rollouts—independently sampled trajectories sharing a policy, starting state, and goal—to balance goal progress with avoiding local optima.Source: §1 · p. 2
  • The method is reported to solve hard-exploration tasks across four settings, including continuous navigation, bit flipping, hierarchical 3D navigation, and Minecraft construction.The authors contrast these results with baselines that often struggle to learn.Source: §1 · p. 2

2 Preliminaries

The preliminaries define an episodic reinforcement-learning objective and extend it to goal-conditioned tasks, where goals vary across episodes. They specify task assumptions, a distance-based success condition, and a sparse reward based on reaching the goal.

2 Preliminaries

  • The agent’s objective is to maximize expected discounted cumulative reward over trajectories sampled under its policy and the environment dynamics.An episode’s length is determined by a maximum length or task-specific termination conditions.Source: §2 · p. 2
  • Goal-oriented learning uses a goal-conditioned policy that must choose actions leading to states consistent with episode-specific goals.The task is framed as optimizing a set of potential rewards by exploiting shared structure across tasks.Source: §2 · p. 2
  • A goal-oriented task samples starting states and goals, maps states to equivalent goals, and defines success as reaching distance d(s, g) ≤ δ.The distance function applies the state-to-goal mapping internally when states are used as inputs.Source: §2 · p. 3
  • The task’s sparse reward is defined by goal completion, and the learning objective is to maximize expected terminal reward.The terminal state determines the trajectory reward; episodes terminate on reaching the goal or taking the maximum number of actions.Source: §2 · p. 3

3 Approach

Distance-to-goal shaping can preserve the goal optimum yet trap learning in local optima, while choosing an anti-goal depends on the environment, goal, and algorithm. Sibling Rivalry uses paired rollouts to estimate and destabilize such optima while retaining progress toward the goal.

3 Approach

  • Paired rollouts estimate local optima from policy behavior, avoiding the need to hand-pick anti-goals whose useful locations vary by environment, goal, and learning algorithm.A fixed anti-goal can itself introduce new local optima.Source: §3 · p. 4
  • Each sibling treats the other rollout’s terminal state as its anti-goal when relabeling rewards.The two rollouts share a starting state and goal, and the closer rollout is identified by its higher naive distance-based reward.Source: §3 · pp. 4–5
  • Sibling rollouts balance minimizing distance to the goal with destabilizing local optima; as the policy learns to reach the goal, the shaped reward converges to the sparse reward.The closer rollout’s terminal states can remain concentrated around an optimum as learning moves from an early local optimum toward the global goal.Source: §3 · p. 5
  • Sibling Rivalry integrates sibling-rollout sampling, mutual reward relabeling with a self-balancing reward, and selective exclusion of closer trajectories from gradient estimation.The inclusion threshold ϵ controls when the closer trajectory may also contribute.Source: §3 · p. 5
  • SR always uses the farther rollout for gradient estimation and includes the closer one only if it reaches the goal or meets the ϵ inclusion criterion.Ignoring the closer rollout can help prevent convergence to local optima, while including it can be beneficial in practice.Source: §3 · p. 5
  • SR requires full-episode rollouts between parameter updates and experimental control over episode starting states and goals.The requirement follows from using a sibling’s terminal state as the anti-goal.Source: §3 · p. 6

4 Experiments

The experiments test Sibling Rivalry (SR) on goal-reaching tasks where local optima interfere with distance-based shaping, comparing it with naive shaping and sparse-reward methods. SR solves tasks across continuous and discrete settings, including hierarchical navigation and Minecraft construction.

2D Point-Maze Navigation

  • 1 of 5 HER runs reached the point-maze goal; PPO+SR consistently solved it while distance-shaped PPO stayed in the top corridor.ICM did not discover the sparse reward at the same rate, and RND never found the goal.Source: §4 · p. 7

Ant-Maze Navigation using Hierarchical RL

  • In the ant U-maze, PPO gets trapped by the wall-induced local optimum while PPO+SR escapes; ICM found a path in 2 of 5 runs, and 3 of 5 HER runs found the goal but remained low-performing.Source: §4 · p. 7

Application to a Discrete Environment

  • PPO+SR enables bitmap learning where naive shaping suppresses toggling; Figure 4 plots goal-completion rates averaged over five experiments.Source: Figure 4 · p. 7, §4 · p. 8

3D Construction in Minecraft

  • In Minecraft, naive shaping led the agent to avoid placing blocks for roughly 1,000 episodes, whereas SR achieved high construction accuracy and exact-match success.The experiment illustrates SR's scalability rather than providing a detailed comparison with other methods.Source: §4 · p. 8, Figure 5 · p. 8

5 Related Work

Related approaches use intrinsic motivation, curriculum or self-play, hindsight relabeling, and latent representations to support learning. Sibling Rivalry instead uses the policy itself to encourage exploration and combines asymmetric objectives in one reward function.

Intrinsic Motivation

  • Intrinsic-motivation methods reward novel or surprising states, whereas Sibling Rivalry uses the policy itself to estimate and encourage exploratory behavior.Source: §5 · p. 9

Curriculum Learning and Self-Play

  • Self-play and asymmetric self-play can encourage exploration through balanced objectives, while Sibling Rivalry combines asymmetric objectives into a single reward function.Source: §5 · p. 9

Learning via Generalization

  • Hindsight Experience Replay relabels failed rollouts for off-policy learning, and asymmetric competition has been used to ease its generalization burden through an automatic exploration curriculum.Source: §5 · p. 9

Latent Reward Shaping

  • Latent reward-shaping methods estimate goal-state similarity or distance using learned representations, including policy-based distances, learned goal spaces, and discriminative training.Source: §5 · p. 9

6 Conclusion

Sibling Rivalry uses sibling rollouts and self-balancing rewards to prevent learning from stabilizing around local optima induced by distance-based shaping. The experiments span continuous and discrete tasks, hierarchical RL, and demanding environments.

6 Conclusion

  • Sibling Rivalry applies to generic distance-based shaped rewards and uses sibling rollouts with self-balancing rewards to prevent stabilization around local optima.Source: §6 · p. 9
  • The method avoids carefully designed, problem-specific reward functions by leveraging the distance metric that defines the underlying sparse reward.Source: §6 · p. 9
  • Experiments demonstrate applicability in continuous and discrete domains, hierarchical RL, and demanding environments where naive shaping fails and sparse-reward methods struggle to explore or generalize.Source: §6 · p. 9

A Formal Motivation

The formal motivation compares trajectories sampled under the same goal-conditioned policy by their shaped reward. It uses sibling-rollout distributions to explain how policy-gradient updates can counter local-optimum convergence.

A Formal Motivation

  • Sibling rollouts are independently sampled trajectories sharing a policy, starting state, and goal; τc denotes the sibling that ends closer to the goal than τf.Source: A Formal Motivation · p. 12
  • φπ_g(τ) is the probability that trajectory τ earns a higher reward than a sibling trajectory sampled from the policy.Source: A Formal Motivation · p. 12
  • The closer and farther sibling trajectories define marginal distributions ρc and ρf; π(τ|g) denotes the product of action probabilities along a trajectory.Source: A Formal Motivation · p. 12
  • The policy-gradient comparison highlights ρc(τ|g) − ρf(τ|g): it favors trajectories overrepresented among closer siblings and underrepresented among farther siblings.Source: A Formal Motivation · p. 12
  • Sibling samples estimate these distributions; limiting closer-sibling gradient use and avoiding their terminal states can counter convergence to a local optimum.Source: A Formal Motivation · p. 12

B Additional Examples

Sibling Rivalry (SR) solves corridor and U-shaped mazes, including variants where distance-to-goal rewards create severe local optima. Its performance in the hardest U-shaped mazes depends strongly on the inclusion threshold ϵ.

B Additional Examples

  • The maze comparison examines the trade-off between avoiding local optima induced by distance and pursuing the global distance optimum.The experiments vary maze side length and compare corridor and U-shaped layouts.Source: B Additional Examples · p. 12, Figure 6 · p. 13
  • In the longest tested corridor and U-shaped mazes, curiosity (ICM) and HER fail.The U-shaped maze’s local optimum is especially difficult to escape because nearly all points yield worse distance-to-goal reward.Source: B Additional Examples · p. 13
  • SR quickly solves corridor mazes across the tested ϵ settings, where distance-to-goal is a useful shaped reward.The tested settings include fairly aggressive exclusion of the closer-to-goal sibling rollout.Source: B Additional Examples · p. 13, Figure 6 · p. 13
  • SR solves U-shaped mazes with severe local optima, though performance on the hardest variants depends strongly on ϵ.As the distance function becomes more misaligned with the environment, the range of effective ϵ values shrinks.Source: B Additional Examples · p. 13, Figure 6 · p. 13
  • SR disrupts learning dynamics around non-global local optima without interfering with corridor solving, and sibling-rollout reward relabeling tailors the signal to the task.The corridor lacks problematic local optima, unlike the U-shaped maze.Source: B Additional Examples · p. 13

C Controlling the Inclusion Hyperparameter

The inclusion threshold ϵ controls whether the closer-to-goal sibling trajectory is used, tuning learning between exploration and exploitation. In point mazes, low, intermediate, and high settings produce over-exploration, successful learning, and under-exploration, respectively.

C Controlling the Inclusion Hyperparameter

  • Low ϵ over-explores, an intermediate range supports successful learning, and high ϵ under-explores in the point-maze analysis.Low settings discard closer-to-goal trajectories more aggressively; high settings permit their inclusion and can lead to a local optimum.Source: Figure 7 · p. 14
  • At ϵ = 0, the closer-to-goal trajectory is included only if it reaches the goal; at ϵ = Inf, both trajectories are always used while diversity is still encouraged.The threshold can tune learning toward exploration or exploitation of the distance-to-goal reward.Source: C Controlling the Inclusion… · pp. 13–14
  • Figure 8 compares shared versus independently sampled sibling starting states in the point-maze and pixel-grid tasks.The curves average training progress over five experiments.Source: Figure 8 · p. 15
  • The three learning modes can be identified using the reported metrics, and a coarser search over ϵ should suffice to find a good range.The point-maze experiments tested ϵ values from 0 to 10 distance units.Source: C Controlling the Inclusion… · pp. 14–15

D Robustness to Different Starting States

Sibling Rivalry remains effective when sibling rollouts start from independently sampled states rather than a shared state. The reported outcomes differ by task, and the analysis is not exhaustive.

D Robustness to Different Starting States

  • Independent starting states yield faster convergence in the 2D point maze and roughly similar performance in the pixel-grid task.The comparison uses independent samples from each task’s underlying start-state distribution.Source: D Robustness to Different Starting… · p. 15
  • The results suggest robustness to starting-state noise and possible benefit, but the analysis is not exhaustive.Outcomes may differ in environments where starting states lead policies toward different local optima.Source: D Robustness to Different Starting… · p. 15
  • The results indicate SR can be applied where exact control over the episode’s starting state is not feasible.Source: D Robustness to Different Starting… · p. 15

E Comparison to Grid Oracle Baseline

Sibling Rivalry (SR) and the Grid Oracle baseline use different shaped rewards to support maze exploration. SR solves the 2D point and ant mazes more consistently, while only slightly lagging Grid Oracle in sample complexity.

E Comparison to Grid Oracle Baseline

F Implementation Details and Experimental Hyperparameters

The experiments use PPO and ICM baselines across maze navigation, hierarchical control, bit flipping, and Minecraft construction, with task-specific implementation choices. In Minecraft, naive distance shaping failed, while per-block reward densification was associated with faster training.

Training algorithms

  • PPO collected full trajectories before network updates and performed multiple minibatch optimization epochs; rollout collection used 20 parallel threads.The authors standardized PPO settings and report that the full-rollout scheduling modification did not meaningfully affect learning.Source: F Implementation Details and… · p. 16

Baselines

  • ICM received intrinsic-reward weight 0.01 relative to sparse reward, and its curiosity modules trained at 0.05 the policy-and-value-module rate.In these settings, ICM had only sparse extrinsic reward and received intrinsic reward until a goal region was possibly discovered.Source: F Implementation Details and… · p. 17

Point maze

Ant maze

  • In ant-maze HRL, a high-level policy proposed subgoals every 20 environment steps, while the low-level policy trained on each interval as a mini-episode.The low-level policy was trained with two PPO epochs per full episode using distance-to-subgoal reward.Source: F Implementation Details and… · p. 18

U-maze

  • The U-maze goal distribution excludes the full maze range, requiring traversal from one end to the other before the agent can receive sparse reward.The authors chose this harder setting rather than assuming goals naturally span easy-to-reach through difficult locations.Source: F Implementation Details and… · p. 18

Bit flipping

  • In 2D bit flipping, naive distance rewards were prone to brittle local optima; vanilla DQN learned only with per-step shaped rewards at γ = 0.98.The terminal-only reward-delivery variant never learned.Source: F Implementation Details and… · p. 19

Minecraft construction

  • In Minecraft, naive distance shaping quickly led the agent to stop placing blocks; the experiments were limited to demonstrating Sibling Rivalry because of computational cost.The agent learned this behavior within roughly 1,000 episodes.Source: F Implementation Details and… · p. 19
  • Per-block distance-change rewards with γ = 0.99 produced faster training in the complex Minecraft environment.Source: F Implementation Details and… · p. 19
Loading 1911.01417v1…