PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Achievement Structure for Structured Exploration in Domains with Sparse Reward

Zihan Zhou, Animesh Garg

arXiv:2305.00508v1cs.LGcs.AI

TL;DR

Exploration in procedurally generated environments is difficult for state-frequency methods because states can be infinite and scattered. SEA learns achievement representations and dependencies from trajectories, then trains achievement-targeted policies; the paper reports recovering Crafter's structure and completing hard exploration tasks there.

  • Problem

    State-frequency exploration can be ineffective in procedurally generated environments, where states may be infinite and scattered despite a finite underlying structure.

    Source: §1 · p. 1

  • Method

    SEA learns achievement representations from collected trajectories, recovers their dependency graph, and uses a meta-controller with achievement-targeted sub-policies to reach known achievements and explore new ones.

    Source: §1 · p. 2, §4.3 · p. 6

  • Results

    SEA recovered Crafter's underlying achievement structure and completed hard exploration tasks, reaching the hardest achievement, collect diamond, at a non-negligible frequency while tested baselines completed none of the hard achievements.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The authors argue that achievement-based environments can be easier to design than task-specific reward systems, and that SEA's structure recovery can alleviate the need for a high-quality achievement set.

    Source: §1 · p. 2

    The recovered dependency graph may include extra edges because of non-causal correlations from agent preferences or insufficient data.

    Source: §4.2 · p. 6

Abstract

from arXiv · show

We propose Structured Exploration with Achievements (SEA), a multi-stage reinforcement learning algorithm designed for achievement-based environments, a particular type of environment with an internal achievement set. SEA first uses offline data to learn a representation of the known achievements with a determinant loss function, then recovers the dependency graph of the learned achievements with a heuristic algorithm, and finally interacts with the environment online to learn policies that master known achievements and explore new ones with a controller built with the recovered dependency graph. We empirically demonstrate that SEA can recover the achievement structure accurately and improve exploration in hard domains such as Crafter that are procedurally generated with high-dimensional observations like images.

1 INTRODUCTION

State-frequency exploration can falter in procedurally generated environments, where states may be infinite and scattered despite a finite underlying structure. SEA recovers achievement structure and uses it to explore; the paper reports hard-achievement progress in Crafter and accurate structure recovery.

1 INTRODUCTION

  • Procedurally generated environments can make state-frequency exploration ineffective because states may be infinite and scattered, even when a finite underlying structure gives the environment meaning.Achievement-based environments also provide sparse and potentially confusing rewards because only first-time achievement completion is rewarded, and distinct achievements can grant the same reward.Source: §1 · pp. 1–2
  • SEA recovers achievement structure from collected trajectories, then uses a nonparametric meta-controller and sub-policies to reach discovered achievements and explore new ones.The paper argues that structure recovery can help discover a progression route without requiring a high-quality achievement set.Source: §1 · p. 2
  • In Crafter, SEA consistently completes hard exploration achievements and reaches collect diamond at a non-negligible frequency, while tested baselines complete none of the hard achievements.The paper also reports accurate recovery of achievement dependencies in Crafter and TreeMaze.Source: §1 · p. 2
  • The authors argue that achievement-based reward systems can be easier to design than task-specific rewards, and that achievements need not be semantically relevant to the task in TreeMaze.They say SEA's structure recovery can alleviate the need for a high-quality achievement set.Source: §1 · p. 2

2 RELATED WORK

The related work covers exploration, hierarchical reinforcement learning, world models, and reward machines. SEA is distinguished by focusing on achievement structure rather than state archives or environment-provided subgoal information.

Exploration in reinforcement learning

  • Intrinsic-motivation methods encourage visits to infrequent states, while Go-explore archives states and trains policies to reach archived cells; both approaches can be ineffective in procedurally generated environments.Go-explore's image down-sampling can be ineffective in such settings, and SEA groups only important states rather than archiving all states and learning all corresponding policies.Source: §2 · p. 2

Hierarchical reinforcement learning

  • Hierarchical reinforcement learning divides complex tasks into subtasks, but related methods often assume environment-provided subtasks or subgoal completion signals, which SEA does not assume.The paper also characterizes its problems as involving more tasks and image-based, procedurally generated environments.Source: §2 · pp. 2–3

Building world models

  • L3P clusters states into graph nodes like SEA, but learns representations to recover reachability, which the authors say is not guaranteed to help exploration..Source: §2 · p. 3

Reward machines

  • Reward machines use linear temporal logic to describe non-Markovian rewards, but cited approaches depend on environment-provided labeling functions rather than learning them from the environment.The paper describes achievement-based environments as a special instance of reward machines because each achievement is rewarded only once per episode.Source: §2 · p. 3

3 PROBLEM SETUP

The problem setup presents Crafter as a procedurally generated game with achievements and dependencies, then formalizes achievement completion and its first-time reward in an MDPA. The formulation explains how an achievement-based reward can be represented in a standard MDP by extending states with completion information.

3.1 CRAFTER

  • Crafter is a procedurally generated 2D open-world game with 21 achievements, whose dependencies form a directed acyclic graph.For example, making a wood pickaxe depends on placing a table because crafting requires the agent to be near one.Source: §3.1 · p. 3

3.2 MARKOV DECISION PROCESS WITH ACHIEVEMENTS

  • An MDPA specifies states, actions, transitions, achievements, and an achievement-completion function that maps each transition to an achievement or none.The reward derived from a trajectory is awarded only for a first-time completion; extending states with achievement-completion information yields a standard MDP.Source: §3.2 · p. 4

4 METHOD

SEA treats achievements as checkpoints for divide-and-conquer exploration, recovering their structure from prior data before training subpolicies to reach known achievements and explore new ones.

4.1 ACHIEVEMENT LEARNING

  • Achievement learning embeds reward-unlock transitions, maximizes normalized pairwise separation with a determinant loss, then clusters representations and thresholds distant samples as new achievements.The loss discourages achievement representations from forming clusters; the classifier labels unrecognized samples as -1.Source: §4.1 · p. 5

4.2 ACHIEVEMENT DEPENDENCY GRAPH

  • Trajectory heuristics add edges when i precedes j in nearly all occurrences of j, then prune edges whose removal preserves topological order.For small ϵ, the initial graph is guaranteed to be a DAG.Source: §4.2 · pp. 5–6
  • Recovered graphs may contain extra dependency edges when agent preferences or insufficient data produce non-causal correlations.Source: §4.2 · p. 6

4.3 SUB-POLICY LEARNING AND EXPLORATION

  • Achievement-conditioned subpolicies receive reward only for their target; a topological controller selects eligible unfinished targets, favoring direct children but occasionally sampling randomly.The occasional random target selection is intended to support recovery of a more accurate graph.Source: §4.3 · p. 6

5 EXPERIMENTS

Across the experiments, SEA recovers achievement structure and supports exploration of hard achievements while maintaining close-to-optimum easy-set reaching rates. The evaluations cover achievement learning, graph recovery, and sub-policy learning in TreeMaze and Crafter.

5.1 EXPERIMENT SETUP

  • The experiments use TreeMaze variants with 4, 10, or 18 rooms and 9, 19, or 30 achievements, plus Crafter-Limited with 7 of Crafter’s 21 achievements.TreeMaze room locations vary while its dependency graph stays fixed; full Crafter’s easy set contains 17 discovered achievements, with four classified as hard.Source: §5.1 · pp. 6–7

5.4 SUB-POLICY LEARNING AND EXPLORATION

  • SEA learns slightly slower than vanilla IMPALA on easy achievements but reaches hard achievements at a significant rate, while vanilla IMPALA reaches none.Figure 4 compares mean unlocking rates for easy and hard achievement sets.Source: Figure 4 · p. 7, §5.4 · p. 9

5.2 ACHIEVEMENT LEARNING

  • The determinant-based method clusters almost perfectly across tested environments, while the latent-space baseline is meaningful only in the two easiest and mean-distance performs slightly worse.Table 1 reports clustering accuracies.Source: Table 1 · p. 7, §5.2 · p. 7
  • In preliminary tests outside the achievement-reward assumption, the latent-space baseline separated reward sources better in some environments.The determinant loss does not depend on that assumption.Source: §5.2 · p. 8
  • With 1 million Crafter data steps, clustering exceeds 99% accuracy for all 17 clusters and achievements; 200,000 steps exceed 90% for 16 of 17.The reported sample-efficiency experiments also include a 50,000-step condition.Source: §5.2 · p. 8

5.3 STRUCTURE RECOVERY

  • SEA recovers exact dependency graphs in all TreeMaze variants and Crafter-Limited; in full Crafter, its graph differs in 11 of 272 adjacency-matrix entries.Figure 6 compares recovered dependency graphs.Source: §5.3 · p. 8, Figure 6 · p. 8

5.4 SUB-POLICY LEARNING AND EXPLORATION

  • A graph-based meta-controller learns sub-policies much faster than a random controller.Figure 7 compares their mean achievement-unlocking rates.Source: Figure 7 · p. 8, §5.4 · p. 8
  • SEA alone consistently reaches hard-set achievements while maintaining close-to-optimum easy-set reaching rates, and reaches Crafter’s collect-diamond achievement with non-negligible probability.The achievement-unlock comparison is reported in Table 2.Source: Table 2 · p. 9, §5.4 · p. 9

6 CONCLUSION AND DISCUSSION

The paper argues that achievement-based environments can support hard exploration in procedurally generated settings, and calls for their broader consideration in environment design. SEA recovers achievement structure in Crafter and uses it to complete hard exploration tasks.

6 CONCLUSION AND DISCUSSION

  • SEA recovers Crafter’s underlying achievement structure and uses it to complete hard exploration tasks.The paper argues that achievement-based environments are easy to design and can support hard exploration without a particularly good achievement set.Source: §6 · p. 9
  • State-frequency-based exploration methods are often ineffective in procedurally generated environments, making exploration there particularly hard.Source: §6 · p. 9
  • The reported unlock rate is the frequency of unlocking a particular achievement.The evaluation’s aggregate measure uses the percentage unlock rate for each achievement.Source: §6 · p. 9

A.1 CRAFTER INDIVIDUAL ACHIEVEMENT LEARNING CURVE

The appendix presents individual Crafter achievement-learning curves, identifies the easy and hard achievement sets, and lists changes made to the original environment.

A.1 CRAFTER INDIVIDUAL ACHIEVEMENT LEARNING CURVE

  • Figures 8 and 9 plot Crafter achievement unlock-rate curves by individual task, respectively excluding and including DreamerV2.Source: Figure 8 · p. 12, Figure 9 · p. 13

B.1 COMPLETE CRAFTER ACHIEVEMENT LIST

  • The appendix divides Crafter achievements into 17 easy tasks solvable by vanilla IMPALA and four hard tasks, including collecting diamond and defeating zombies.Source: §B.1 · pp. 13–14

B.2 MODIFICATIONS TO THE ORIGINAL CRAFTER ENVIRONMENT

  • The Crafter modifications remove health rewards and health loss, end games after 100 steps without an achievement, and alter creature damage behavior.The creature change lets eat cow, defeat skeleton, and defeat zombie connect to the main dependency graph rather than remain independent nodes.Source: §B.2 · p. 14

C.1.1 META-CONTROLLER DETAILS

The meta-controller uses the dependency graph and completed-achievement set to select targets, balancing exploration with progression through related achievements. It updates the completed set after target selection.

C.1.1 META-CONTROLLER DETAILS

  • At episode start, the controller randomly selects an achievement with no dependencies; after an unlock, it forms the available set from uncompleted achievements whose dependencies are complete.Source: §C.1.1 · p. 14
  • After an achievement is completed, the controller selects an exploration task with 40% probability, a direct descendant with 48%, a neighbor with 6%, or a jump target with 6%.Source: §C.1.1 · p. 14
  • After selecting the next target, the controller adds the just-completed achievement to its completed set.Source: §C.1.1 · p. 14

C.2 IMPLEMENTATION

The implementation adapts torchbeast’s open-source IMPALA code, and the appendix includes a table of experiment-specific IMPALA hyperparameters.

C.2 IMPLEMENTATION

  • The authors adapt their code from the open-source torchbeast implementation of IMPALA.Source: §C.2 · p. 15
  • The authors state that the complete code is available at a linked location.Source: §C.2 · p. 15

C.3 HYPERPARAMETERS

  • Table 4 lists IMPALA hyperparameters for different experiments.Source: Table 4 · p. 15

C.4 IMPLEMENTATION OF ACHIEVEMENT REPRESENTATION FUNCTION φ φ

The representation function combines encodings of the current and next states with the current action to form an achievement representation. Unlike HRL subgoals, achievements are equal in nature, and SEA can identify which may serve as subgoals for others.

C.4 IMPLEMENTATION OF ACHIEVEMENT REPRESENTATION FUNCTION φ φ

  • The representation function encodes the current and next states with two networks, concatenates them, then appends a one-hot encoding of the current action before a fully connected layer produces xrep.The two state networks share the policy network's structure.Source: §C.4 · p. 15
  • The final output of φ is the sum of xobs and xrep.xobs contains the concatenated encodings of the two states.Source: §C.4 · p. 15

D.1 COMPARISON WITH HRL

  • SEA can identify achievements that may be useful as subgoals for other achievements, without requiring carefully crafted intermediate steps.The paper distinguishes achievements, which are equal in nature, from HRL subgoals and subtasks that normally lead toward an ultimate goal.Source: §D.1 · p. 15
Loading 2305.00508v1…